nano-vLLM Part 1: Reading the Scheduler One Step at a Time

nano-vLLM Part 1: Reading the Scheduler One Step at a Time

There are already useful high-level descriptions of nano-vLLM, a compact implementation of several ideas popularized by vLLM: batched inference, paged KV cache, prefix caching, tensor parallelism, CUDA graphs, and more. I wanted a more concrete answer to a simpler question:

When several prompts are in flight, which tokens does the engine actually run next, where do their KV states live, and why does the scheduler keep taking sequences out of a deque and putting them back?

This post reads the relevant code path—LLMEngine, Scheduler, Sequence, BlockManager, and ModelRunner—with numerical examples. The code discussed here is the version on the repository’s main branch at the time of writing.

1. Runtime fundamentals: what the engine is managing

1.1 The execution loop

The engine repeats one small control loop:

Scheduler chooses a batch
        ↓
ModelRunner runs one GPU forward pass
        ↓
Scheduler postprocesses outputs and updates sequence state
        ↓
repeat

Each request becomes a Sequence. A sequence begins in waiting, moves to running after all of its prompt tokens have been prefetched, and finally becomes finished after EOS or max_tokens.

There are two kinds of GPU batch:

Batch kind	GPU input for each sequence	Main work	What comes out
Prefill	A prompt, or an unprocessed chunk of it	Compute KV states for many prompt tokens	The first completion token only when the final prompt chunk is processed
Decode	The sequence’s previous output token	Compute KV state for one new token while attending to cached history	One next-token sample

The important mental model is: a decode step does not finish a request. It advances every selected live request by one token. A running sequence must therefore return to the running deque after selection, unless it later finishes or is preempted.

1.2 Scope: nano-vLLM is not an online serving stack

The repository describes nano-vLLM as lightweight, readable offline inference. Its public generate() method adds every supplied prompt first and then repeatedly calls step() until waiting and running are both empty. There is no HTTP server, continuous request admission loop, queue limit, request cancellation protocol, or load balancer in this repository.

LLMEngine.add_request() is still useful for understanding a serving design: it tokenizes a prompt, creates a fresh Sequence, and appends it to scheduler.waiting. But an application that keeps receiving client traffic would need to wrap this engine with its own admission control, API layer, metrics, cancellation/deadline handling, and load balancing.

That distinction matters for a few questions below. The scheduler explains the core mechanics; it is not itself a production serving policy.

1.3 The objects that carry and manage state

Sequence: one inference request, not one user or conversation

When add_request() receives a prompt, it constructs a Sequence with a monotonically assigned seq_id. The object holds:

• token_ids: prompt tokens followed later by generated tokens;
• num_prompt_tokens, num_tokens, and last_token;
• num_cached_tokens: tokens whose KV values have already been computed;
• block_table: logical-token-block to physical-KV-block mapping;
• sampling controls such as temperature, max_tokens, and ignore_eos.

The engine does not know that two requests come from the same person, browser session, or chat. Two turns from one user are two separate Sequence objects unless an application builds a continuation protocol around the engine.

If the application sends the entire chat transcript again for the next turn, the new request is prefetched as a new sequence. nano-vLLM can share an identical, whole-block token prefix with another sequence, but that is content-addressed sharing—not conversational memory. It does not recognize “the same user” or attach a new request to a completed sequence automatically.

BlockManager: the CPU-side map of GPU KV-cache slots

The actual KV cache is allocated by ModelRunner.allocate_kv_cache() as one large GPU tensor. The BlockManager is a small CPU-side allocator that decides which physical block IDs a sequence may use.

The default block size is 256 tokens. For every transformer layer, each block corresponds to 256 positions of keys and values. A sequence’s block_table is a page table: logical block 0, 1, 2, … map to physical slots such as [17, 4, 92, ...] in the large GPU cache.

The manager keeps:

• a deque of free physical block IDs;
• a set of used IDs;
• a reference count per block;
• a hash map for reusable full blocks.

Only complete blocks are hashed for prefix caching. If two prompts begin with the same 512 tokens, their first two 256-token blocks can refer to the same physical blocks. A partial final block is deliberately not reused by this simple implementation.

Scheduler: two deques and a batch decision

The scheduler owns:

waiting: [ sequences that still need prompt prefill ]
running: [ sequences that can generate another completion token ]

Its configuration has two particularly visible per-batch limits:

• max_num_seqs (default 512): how many sequences may be selected for one batch;
• max_num_batched_tokens (default 16,384): how many prefill tokens can enter one forward pass.

These are batch limits, not an HTTP request-queue capacity. In particular, waiting itself is just a deque; the minimal implementation does not impose an admission limit on its length.

1.4 One step() precisely

The engine’s step() is remarkably small:

The following is the complete control hand-off in LLMEngine.step():

seqs, is_prefill = self.scheduler.schedule()
num_tokens = sum(seq.num_scheduled_tokens for seq in seqs) if is_prefill else -len(seqs)
token_ids = self.model_runner.call("run", seqs, is_prefill)
self.scheduler.postprocess(seqs, token_ids, is_prefill)
outputs = [(seq.seq_id, seq.completion_token_ids) for seq in seqs if seq.is_finished]
return outputs, num_tokens

schedule() mutates CPU scheduling state and returns a list of sequences plus a single batch-wide Boolean. ModelRunner.run() prepares tensors, executes the model on GPU, and samples one token per selected sequence. postprocess() advances cached-token counts, appends generated tokens where appropriate, hashes newly completed KV blocks, and frees finished sequences.

The GPU/CPU division is therefore mostly as expected:

CPU orchestration: LLMEngine, Scheduler, Sequence, BlockManager metadata
GPU execution:    model weights, attention kernels, KV cache, forward pass

It is not a hard purity boundary—the runner also performs CPU work to prepare tensors and coordinate tensor-parallel processes—but the expensive neural computation and the KV tensor are on CUDA devices. ModelRunner explicitly calls torch.cuda.set_device(rank) and puts the model and cache on the GPU.

2. Prefill: turn a prompt into attention history

The scheduler always tries waiting first. Its high-level logic is:

while waiting and batch_has_sequence_room:
    look at waiting[0]
    check batch token room
    allocate/reuse KV blocks if this is a new sequence
    schedule prompt tokens (possibly a chunk)
    if all prompt tokens are now scheduled:
        move it waiting -> running
    add it to this prefill batch

if anything was scheduled:
    return that prefill batch

Here is the corresponding prefill branch from Scheduler.schedule():

while self.waiting and len(scheduled_seqs) < self.max_num_seqs:
    seq = self.waiting[0]
    remaining = self.max_num_batched_tokens - num_batched_tokens
    if remaining == 0:
        break
    if not seq.block_table:
        num_cached_blocks = self.block_manager.can_allocate(seq)
        if num_cached_blocks == -1:
            break
        num_tokens = seq.num_tokens - num_cached_blocks * self.block_size
    else:
        num_tokens = seq.num_tokens - seq.num_cached_tokens
    if remaining < num_tokens and scheduled_seqs:
        break
    if not seq.block_table:
        self.block_manager.allocate(seq, num_cached_blocks)

    seq.num_scheduled_tokens = min(num_tokens, remaining)
    num_batched_tokens += seq.num_scheduled_tokens
    if seq.num_cached_tokens + seq.num_scheduled_tokens == seq.num_tokens:
        seq.status = SequenceStatus.RUNNING
        self.waiting.popleft()
        self.running.append(seq)
    scheduled_seqs.append(seq)

if scheduled_seqs:
    return scheduled_seqs, True

During a prefill forward pass, ModelRunner.prepare_prefill() sends the not-yet-cached slice

seq[num_cached_tokens : num_cached_tokens + num_scheduled_tokens]

to the model. The attention code writes each token’s key and value into the physical slots determined by block_table. On the final prompt chunk, the logits also yield the first completion token. postprocess() then appends that token to seq.token_ids.

For an earlier chunk, there is no completion token appended yet: postprocess() increments num_cached_tokens, sees that it is still less than num_tokens, and continues. This is a useful detail because the model can return a sampled ID for every forward call, while the scheduler deliberately ignores it until the prompt is complete.

2.1 Example: three prompts in one prefill batch

Assume:

max_num_batched_tokens = 16
max_num_seqs = 3
waiting = [A: 6 prompt tokens, B: 7, C: 5]
running = []

The scheduler selects A (6 tokens), then B (7 tokens). There are 3 token positions left. It looks at C, notices remaining < C's 5 tokens and that scheduled_seqs already contains requests, and stops. The special rule is:

if remaining < num_tokens and scheduled_seqs:
    break  # chunk only the first sequence in a prefill batch

So the returned GPU batch is [A(6), B(7)], not [A(6), B(7), C(3)]. If each of A and B has had its complete prompt scheduled, both have already been moved to running before the GPU call. After the forward pass, postprocessing caches their prompt states and appends one first generated token to each.

At that point, the state is conceptually:

waiting = [C]
running = [A, B]

2.2 A 500k-token prompt is a good thought experiment—with two caveats

Suppose an application configures a model and cache capable of a 500,000-token prompt, and a new sequence Long arrives. The default nano-vLLM max_model_len is only 4,096, so this is explicitly a hypothetical configuration, not something the default settings can accept.

Assume a 256-token block size and a prefill budget of 16,384 tokens. Long occupies

ceil(500,000 / 256) = 1,954 KV blocks.

The scheduler may run its prompt in approximately 31 forward passes: 30 chunks of 16,384 tokens and one final chunk of 8,480 tokens. After each non-final pass, it retains the sequence in waiting and raises num_cached_tokens by 16,384. On the final pass it changes the status to RUNNING, puts Long into running, and postprocessing appends the first generated token.

The subtle but important caveat: chunked prefill limits how many prompt tokens are computed per GPU forward pass; it does not allocate KV blocks gradually in this code. On a fresh sequence, can_allocate() checks whether enough blocks exist for seq.num_blocks, and allocate() assigns the full block table before the first chunk runs. Therefore, the 1,954 blocks must be available up front, even though the prompt computation is chunked.

Prefix reuse can reduce the number of new blocks if Long begins with whole blocks already cached by another sequence. But the allocator still needs sufficient physical capacity for the entire logical prompt after accounting for reusable blocks.

3. Decode: one token per live sequence, batched together

When schedule() cannot schedule any prefill tokens, it enters the decode loop. For each selected sequence it does:

seq.num_scheduled_tokens = 1
seq.is_prefill = False
self.block_manager.may_append(seq)
scheduled_seqs.append(seq)

The surrounding Scheduler.schedule() decode branch makes the capacity check and victim choice explicit:

seq = self.running.popleft()
while not self.block_manager.can_append(seq):
    if self.running:
        self.preempt(self.running.pop())
    else:
        self.preempt(seq)
        break
else:
    seq.num_scheduled_tokens = 1
    seq.is_prefill = False
    self.block_manager.may_append(seq)
    scheduled_seqs.append(seq)

self.running.extendleft(reversed(scheduled_seqs))

ModelRunner.prepare_decode() then constructs a batch of exactly one model input token per sequence:

input_ids.append(seq.last_token)
positions.append(len(seq) - 1)
context_lens.append(len(seq))

This is the autoregressive recurrence in operational form:

1. The prompt forward pass produced completion token y₁.
2. Decode consumes y₁ as the new input token, uses the cached KV states of the prompt as attention history, and writes y₁’s KV state.
3. The logits sample y₂.
4. Postprocessing appends y₂.
5. The next decode consumes y₂, writes its KV state, samples y₃, and so on.

It is easy to say “decode generates one token,” but this code makes the one-token offset precise: the token already sampled on the preceding step is the GPU input; the new sample is appended after the forward pass.

3.1 Example: running = [B, A, C]

Assume no requests are waiting, max_num_seqs >= 3, and B, A, and C each have unfinished completions. The scheduler pops all three, creates:

scheduled_seqs = [B, A, C]

Then the model runs one batched decode forward pass. It does not finish B before beginning A. B, A, and C each advance by one token in that same model call. In simple notation:

before: B has …, yB₁     A has …, yA₁     C has …, yC₁
GPU input:       yB₁              yA₁              yC₁
after:  append   yB₂              yA₂              yC₂

The order determines their row order in the batch; it does not turn the sequence list into “run B until completion, then A.”

3.2 Why pop from running and then put the same sequences back?

running is the durable set of active requests, not a one-shot work queue. Selecting a request means “give it one token this step,” not “remove it from the system.” Unless postprocessing finds EOS or reaches max_tokens, that request needs selection again next step.

The scheduler temporarily removes candidates with popleft() because it must inspect their cache capacity and may need to preempt a different running request. Once it has chosen the batch, it restores the selected live sequences:

self.running.extendleft(reversed(scheduled_seqs))

Why reverse? deque.extendleft() adds elements one at a time to the left, which reverses their apparent order. With:

initial running     = [A, B, C, D]
after three pops    = [D]
scheduled_seqs      = [A, B, C]

these two operations differ:

extendleft([A, B, C])           -> [C, B, A, D]  # wrong order
extendleft(reversed([A, B, C])) -> [A, B, C, D]  # original order restored

The reinsertion happens before the GPU forward pass returns. If a selected sequence then finishes, postprocess() removes it from running and deallocates its KV blocks. If it remains unfinished, it is already in the right place for a later decode selection.

4. KV pressure, preemption, and serving-policy limits

4.1 KV pressure and preemption

For decode, can_append(seq) checks whether the next input token starts a new 256-token KV block. It needs a free block only at that boundary. may_append(seq) reserves that block before execution when required.

If no block is free, the scheduler preempts work:

if self.running:
    self.preempt(self.running.pop())
else:
    self.preempt(seq)

preempt() changes the selected victim back to WAITING, marks it as prefill, deallocates all of its blocks, and puts it at the front of waiting. The next time it is admitted, it will rebuild or reuse its prefix cache. This is recomputation in exchange for allowing another request to progress under tight KV memory.

The whole preempt() method is only four lines:

def preempt(self, seq: Sequence):
    seq.status = SequenceStatus.WAITING
    seq.is_prefill = True
    self.block_manager.deallocate(seq)
    self.waiting.appendleft(seq)

So, if the KV cache is full, both paths feel the pressure, but in different ways:

Case	Scheduler reaction
A fresh prefill cannot allocate its prompt blocks	Stop scheduling prefill at that point.
A running sequence needs a new decode block	Preempt another running sequence when possible; otherwise preempt the current sequence.

The result is not that a full cache somehow “switches the engine to decode.” Full cache blocks fresh allocation and can force decode preemption too. Preemption frees blocks by discarding one request’s private cache state; it does not create extra cache capacity.

4.2 Does the scheduler fairly alternate prefill and decode?

Not by itself. This is the most important correction to a tempting high-level interpretation.

schedule() returns immediately if it scheduled any prefill sequence:

if scheduled_seqs:
    return scheduled_seqs, True

The decode loop is reached only when zero prefill work could be scheduled: for example, because waiting is empty or the next waiter cannot allocate KV blocks. Consequently, if an online wrapper continually supplies prefillable requests and memory is available, this particular prefill-first policy can delay decode requests indefinitely. The batch-size limits constrain each prefill step, but they do not make the scheduler alternate modes.

For its intended offline generate() usage, all prompts are enqueued up front. The engine prefills them and later drains decode, which keeps the design compact and easy to study. A production server normally needs a deliberate scheduling policy on top of these mechanics, such as:

• a time or token budget reserved for decode every iteration;
• a cap on queued and active requests;
• maximum queue-wait and time-to-first-token objectives;
• request cancellation and deadline-aware admission;
• queue-length, KV-utilization, and throughput metrics for a router/load balancer;
• multiple replicas with routing/backpressure rather than unlimited local waiting.

This is also why “the load balancer should look at queue size” is a sound intuition, but it is only one layer. The replica needs bounded admission and a fair internal policy; the router needs live signals beyond queue length, such as KV-cache pressure, active sequences, predicted prompt cost, and current token throughput.

4.3 What “the limits of this small offline engine” means

“Small” is a strength here: the repository is short enough to expose the core ideas without hiding them behind a serving framework. It also means several production concerns are intentionally outside its scope:

Present in nano-vLLM	Not provided by this minimal implementation
Offline batch generation: enqueue prompts, then drain them to completion	An HTTP/OpenAI-compatible server that keeps admitting requests while generation runs
One prefill-only or decode-only batch per step()	A fairness policy that guarantees decode progress while new prefills keep arriving
Block allocation, prefix reuse, and preemption	Queue admission limits, cancellation, deadlines, request priorities, and backpressure
Qwen3 model execution on one or more CUDA ranks	A broad model-architecture ecosystem and the operational features of full vLLM
Chunked prompt computation	Incremental KV allocation: a long prompt still needs its full block table reserved before its first chunk
Preemption by cache deallocation	Lossless suspension: the preempted sequence must prefill/recompute its KV state later

These are design boundaries, not bugs in a teaching implementation. They explain why nano-vLLM is excellent for learning the inference core while a production service needs additional scheduling, networking, observability, and reliability layers around it.

5. What to carry into Part 2

The scheduler is small because it focuses on a narrow contract: select a homogeneous prefill or decode batch, maintain a logical-to-physical KV mapping, and recover space via preemption. That makes it an excellent learning implementation—not a complete production scheduler.

The durable picture to keep is:

new prompt
  -> fresh Sequence in waiting
  -> prefill one or more chunks; KV states are written
  -> final prompt chunk samples first output; Sequence enters running
  -> batched decode repeatedly consumes prior output and samples the next one
  -> EOS / max_tokens frees KV blocks and marks finished

under KV pressure: running -> waiting, cache discarded, then re-prefill later

In Part 2, I plan to go one level lower into the block table, prefix-cache hashes, attention slot mapping, and why paged KV cache avoids treating each request’s context as one contiguous GPU allocation.