Async Scheduling: Planning a Step Before the Last One Finishes

The idea in one minute#

To keep the GPU from idling between steps, the engine schedules step N+1 while step N is still running. But step N+1 of a generating request must feed the model the token that step N is about to sample — a token that does not exist yet. vLLM resolves this by scheduling a placeholder: the scheduler reserves one position for “whatever step N produces”, and the worker, which will hold the real token on the GPU by then, fills it in. The scheduler runs one step ahead of reality and reconciles when results arrive. This is on by default, it is why two counters in the scheduler seem to disagree, and it costs one wasted forward pass for every request that ends with a stop token.

A picture#

flowchart LR
  subgraph T1["While step N runs on the GPU"]
    direction TB
    S["schedule(N+1)<br/><small>this request: 1 token, ID unknown</small>"] --> PH["num_output_placeholders += 1<br/><small>num_computed_tokens += 1</small>"]
  end
  subgraph T2["Step N finishes"]
    direction TB
    W[":nvidia: worker keeps the sampled<br/>token on the GPU"] --> U["update_from_output(N)<br/><small>real token ID arrives<br/>placeholders -= 1</small>"]
  end
  subgraph T3["Step N+1 starts at once"]
    direction TB
    X[":nvidia: worker substitutes its own<br/>last sampled token as the input"]
  end
  T1 --> T2 --> T3
  class S,PH queue
  class W,X compute
  class U neutral

How it really works#

When it is on#

--async-scheduling defaults to “decide automatically”, and the automatic answer is yes unless one of these holds (from vllm/config/vllm.py):

When it is on, the scheduler class is AsyncScheduler, a subclass of Scheduler that overrides just two methods. You can force it off with --no-async-scheduling.

The problem, precisely#

In the synchronous engine, a generating request looks like this just before schedule():

num_tokens          = 107      (100 prompt + 7 output; the 7th was just sampled)
num_computed_tokens = 106      (the 7th has not been through the model)
gap                 = 1

Schedule one token. The worker runs token 107 through the model and samples token 108. Repeat.

Now let schedule() for the next step run before the current step has returned. The scheduler’s num_tokens is still 107, because token 108 does not exist yet. And _update_after_schedule already advanced num_computed_tokens to 107 when the current step was scheduled. The gap is zero. By the ordinary rule there is nothing to schedule, and the overlap would be worthless.

The fix: count the token before it exists#

AsyncScheduler._update_after_schedule adds one line of bookkeeping for every scheduled request that will sample this step:

for req_id in scheduler_output.num_scheduled_tokens:
    request = self.requests[req_id]
    if request.is_prefill_chunk:
        continue
    # The request will generate num_sampled_tokens_per_step new tokens
    # plus num_spec_tokens in this scheduling step.
    cur_num_spec_tokens = len(spec_decode_tokens.get(req_id, ()))
    request.num_output_placeholders += (
        self.num_sampled_tokens_per_step + cur_num_spec_tokens
    )

A placeholder is a promise: “a step in flight will produce one token for this request.” Now the gap formula from One Scheduling Step shows why it always included a term that was zero until now:

num_new_tokens = (
    request.num_tokens_with_spec
    + request.num_output_placeholders
    - request.num_computed_tokens
)

With the numbers above: 107 + 1 − 107 = 1. The request is scheduled for one token. The scheduler does not know its ID, and does not need to: it only needs to reserve the position and a slot in the KV cache.

is_prefill_chunk is what decides whether a step samples:

request.is_prefill_chunk = request.num_computed_tokens < (
    request.num_tokens + request.num_output_placeholders
)

A step that ends in the middle of the prompt is a prefill chunk: nothing will be sampled, so no placeholder is added.

Who knows the token#

The worker. After sampling in step N, the model runner keeps the sampled token IDs in a tensor on the GPU. When step N+1 arrives saying “one token for this request, at position 108”, the runner writes its own previous sample into that position of the input. The token ID never travels worker → scheduler → worker; it goes worker → worker, on the GPU, and a copy is sent to the scheduler afterwards for bookkeeping, detokenising and stop checks.

This is also why CachedRequestData.new_token_ids carries the comment “only used for pipeline parallelism”: in the ordinary case the scheduler sends no token IDs for a running request at all.

Reconciling when the result arrives#

AsyncScheduler._update_request_with_output:

new_token_ids, stopped = super()._update_request_with_output(request, new_token_ids)

# Placeholders were zeroed at preemption; a stale delivery must not
# decrement them (it would underflow).
if not is_stale:
    request.num_output_placeholders -= len(new_token_ids)
    assert request.num_output_placeholders >= 0

# Cache the new tokens. Preempted requests should be skipped.
if status_before_update == RequestStatus.RUNNING:
    self.kv_cache_manager.cache_blocks(
        request, request.num_computed_tokens - request.num_output_placeholders
    )

The promise is redeemed: num_tokens goes up by one (the real token is appended) and num_output_placeholders goes down by one. Their sum is unchanged, so the gap is unaffected.

The last statement matters for the prefix cache. Blocks may only be given a hash once their contents are final, and a hash depends on token IDs. num_computed_tokens includes positions whose IDs are still unknown, so the cacheable frontier is num_computed_tokens − num_output_placeholders.

Not scheduling past the end#

A request that is about to hit max_tokens should not be scheduled again. That much is knowable in advance, and the first check in pass 1 handles it:

if (
    request.num_output_placeholders > 0
    # This is (num_computed_tokens + 1) - (num_output_placeholders - 1).
    and request.num_computed_tokens + 2 - request.num_output_placeholders
    >= request.num_prompt_tokens + request.max_tokens
):
    # Async scheduling: Avoid scheduling an extra step when we are sure that
    # the previous step has reached request.max_tokens.
    req_index += 1
    continue

What cannot be known in advance is whether the token in flight is end-of-sequence. If it is, the step already scheduled behind it is pure waste: it computes one token for a request that has finished. update_from_output handles the leftover like this:

if request is None or request.is_finished():
    # The request is already finished. This can happen if the
    # request is aborted while the model is executing it (e.g.,
    # in pipeline parallelism or in async scheduling).
    continue

So the cost of async scheduling is one extra token of compute per request that ends on a stop token, in exchange for no idle gap on every step of every request. For a 300-token answer that is a third of a percent of work.

Blocks must not be recycled too early#

A second hazard: when a request finishes, its blocks go back to the pool. With a step still in flight, the GPU may be about to write to one of those blocks (the wasted step above does exactly that). If the pool handed the block to another request immediately, two requests would write the same memory.

The scheduler guards against this with a sequence number, a fence:

def _request_blocks_can_be_freed(self, request: Request) -> bool:
    # We must defer freeing blocks if an async kv connector may
    # write to them immediately (not ordered with GPU stream).
    return not self.defer_block_free or (
        request.last_sched_seq <= self.processed_step_seq
    )

Each non-empty step gets a number when scheduled (sched_step_seq), and a second counter (processed_step_seq) advances when its output is processed. Where deferral is enabled, a request’s blocks are parked on a deferred_frees list and returned to the pool only after every step that might touch them has completed.

Preemption while steps are in flight#

Suppose a request is preempted while one of its steps is still on the GPU. The scheduler has just reset it (num_computed_tokens = 0, placeholders zeroed), and then a result arrives for the old step. _preempt_request prepares for that:

# Async scheduling: mark all in-flight output as stale. Its tokens are
# still delivered on return (dropping them would perturb spec-decode
# acceptance) but must not mutate the reset counters; ...
request.num_stale_output_tokens = request.num_in_flight_tokens
request.num_output_placeholders = 0

The late token is still valid — it was sampled from a correct context — so it is delivered to the client. But it must not be subtracted from the freshly reset counters. is_stale in the code above is that distinction. And pass 2 will not re-admit the request while stale output is still outstanding:

if request.num_stale_output_tokens and not request.drop_stale_output:
    # Deliverable stale output still in flight: resuming now
    # could resample a position that output later delivers.
    skip_request(request_queue)
    continue

Structured output gives up part of the overlap#

A grammar constrains the next token given all previous ones. To build the mask of allowed tokens for step N+1, the grammar must first consume the token from step N. That token is exactly what async scheduling does not have yet.

So for these requests the engine cannot sample ahead. AsyncScheduler flags the step:

scheduler_output.pending_structured_output_tokens |= (
    request.use_structured_output and request.num_output_placeholders > 0
)

and step_with_batch_queue reacts by starting the forward pass for step N+1 right away but deferring its sampling until step N’s output has been processed and the grammar has advanced:

if not scheduler_output.pending_structured_output_tokens:
    grammar_output = self.scheduler.get_grammar_bitmask(scheduler_output)
    future = self.model_executor.sample_tokens(grammar_output, non_block=True)
else:
    # We need to defer sampling until we have processed the model output
    # from the prior step.
    deferred_scheduler_output = scheduler_output

The forward pass still overlaps; only sampling waits. Structured output therefore keeps most of the benefit, which is the reason execute_model and sample_tokens are two separate calls.

The counters, in one table#

The invariant that keeps everything consistent: a request needs scheduling exactly when num_tokens + num_output_placeholders > num_computed_tokens.

Code#

One request through an engine with a batch queue of depth two. Watch placeholders rise when a step is scheduled and fall when its result arrives — and watch what happens when the model ends the answer itself.

package main

import "fmt"

type request struct {
	prompt, maxTokens int
	output            int // tokens whose IDs the scheduler knows
	computed          int // num_computed_tokens (advanced at schedule time)
	placeholders      int // num_output_placeholders
	finished          bool
}

func (r *request) numTokens() int { return r.prompt + r.output }

type step struct {
	id      int
	samples bool // false for a prefill chunk that does not reach the prompt's end
}

// run drives one request through an engine with a batch queue of depth 2.
// eosAt is the output position at which the model emits end-of-sequence (0 = never).
func run(r *request, budget, eosAt int) {
	var inFlight []step
	wasted := 0
	for id := 1; !r.finished || len(inFlight) > 0; id++ {
		// --- schedule(): runs before the previous step's output is known ---
		scheduled := false
		surelyDone := r.placeholders > 0 &&
			r.computed+2-r.placeholders >= r.prompt+r.maxTokens
		if !r.finished && !surelyDone {
			gap := r.numTokens() + r.placeholders - r.computed
			if n := min(gap, budget); n > 0 {
				r.computed += n
				s := step{id: id, samples: r.computed == r.numTokens()+r.placeholders}
				if s.samples {
					r.placeholders++ // a token will exist; its ID is not known yet
				}
				inFlight = append(inFlight, s)
				scheduled = true
				fmt.Printf("  schedule step %d: %d token(s)  -> computed=%d known=%d placeholders=%d\n",
					id, n, r.computed, r.numTokens(), r.placeholders)
			}
		}
		if scheduled && len(inFlight) < 2 {
			continue // keep the batch queue full before waiting on the GPU
		}

		// --- update_from_output(): the oldest step finishes ---
		s := inFlight[0]
		inFlight = inFlight[1:]
		switch {
		case r.finished:
			wasted++
			fmt.Printf("  output   step %d: request already finished, result discarded\n", s.id)
		case s.samples:
			r.output++
			r.placeholders--
			what := fmt.Sprintf("token %d", r.output)
			if r.output == eosAt {
				what += " = EOS, finished (stop)"
				r.finished = true
			} else if r.output == r.maxTokens {
				what += ", finished (length)"
				r.finished = true
			}
			fmt.Printf("  output   step %d: %s  -> known=%d placeholders=%d\n",
				s.id, what, r.numTokens(), r.placeholders)
		default:
			fmt.Printf("  output   step %d: prefill chunk, nothing sampled\n", s.id)
		}
	}
	fmt.Printf("  wasted forward passes for this request: %d\n\n", wasted)
}

func main() {
	fmt.Println("Case 1: 6-token prompt, budget 4, stops at max_tokens=3")
	run(&request{prompt: 6, maxTokens: 3}, 4, 0)

	fmt.Println("Case 2: same request, but the model emits EOS as its 2nd token")
	run(&request{prompt: 6, maxTokens: 8}, 4, 2)
}

In case 1, look at the line after “schedule step 4”: no step 5 is scheduled, because the max_tokens check knew the request was about to end. In case 2 there is no such knowledge. Step 4 is already on the GPU when step 3 returns end-of-sequence, and its result is thrown away. That single discarded step is the whole price of the optimisation.

Remember this#

• Async scheduling plans step N+1 while step N is on the GPU; it is the default for generative models.
• A placeholder is a scheduled position whose token ID is not known yet.
• The gap is num_tokens + num_output_placeholders − num_computed_tokens.
• The worker feeds its own last sampled token into the next step; the ID does not round-trip through the scheduler.
• Requests reaching max_tokens are not over-scheduled; requests ending on a stop token waste one step.
• Blocks are cached only up to num_computed_tokens − num_output_placeholders.
• Structured output defers sampling, not the forward pass.

Try it#

1. In case 2, move the EOS to the 1st token. How many steps are wasted? Can it ever be more than one with a queue depth of two?
2. Change the queue depth test from < 2 to < 3 (as with pipeline parallelism of 2 on the newer runner). How many steps are wasted on EOS now? Relate this to max_concurrent_batches.
3. Start a server with --no-async-scheduling and one with the default, and compare tokens per second at 64 concurrent requests with vllm bench serve.

Check yourself#

1. Why is the ordinary gap zero when scheduling one step ahead, and what makes it one again?
2. Which component substitutes the real token for a placeholder, and why is it that one?
3. Why can blocks holding placeholder positions not be added to the prefix cache yet?

Sources#

Checked on 5 October 2026 against main at commit 0c16eee.

• vllm/v1/core/sched/async_scheduler.py
• vllm/v1/core/sched/scheduler.py — the max_tokens guard, stale output, deferred frees
• vllm/v1/engine/core.py — step_with_batch_queue, deferred sampling
• vllm/config/vllm.py — when async scheduling is enabled