走进 vLLM（二）：chunked prefill、prefix caching 与 guided decoding

原文 · English中文译文

原文：Inside vLLM: Anatomy of a High-Throughput LLM Inference System，作者 Aleksa Gordic，2025-09-05 发布于 vLLM 官方博客。

本文是系列《走进 vLLM：高吞吐 LLM 推理系统解剖》的第 2 篇，共 5 篇。承接第 1 篇（LLM Engine 与 Engine Core）。

本站中英对照排版：左栏英文原文，右栏中文译文；不好翻译的术语保留英文写法。

Advanced Features — extending the core engine logic

Advanced Features —— 把核心 engine 逻辑扩出去

With the basic engine flow in place, we can now look at the advanced features.

基础 engine 流程就位之后，我们可以来看高级特性了。

We’ve already discussed preemption, paged attention, and continuous batching.

Next, we’ll dive into:

我们已经聊过 preemption、paged attention 和 continuous batching。接下来依次深入：

Chunked prefill
Prefix caching
Guided decoding (through grammar-constrained finite-state machines)
Speculative decoding
Disaggregated P/D (prefill/decoding)

Chunked prefill
Prefix caching
Guided decoding（通过 grammar 约束的有限状态机）
Speculative decoding
Disaggregated P/D（prefill/decode 分离）

Chunked prefill

Chunked prefill is a technique for handling long prompts by splitting their prefill step into smaller chunks. Without it, we could end up with a single very long request monopolizing one engine step disallowing other prefill requests to run. That would postpone all other requests and increase their latency.

Chunked prefill 是用来处理长 prompt 的技术：把一个 prompt 的 prefill 拆成更小的 chunk。没有它的话，我们可能会遇到一个超长请求独占某一步 engine step，别的 prefill 请求根本排不进去，结果就是所有其他请求都被往后推、延迟被拉高。

For example, let each chunk contain n (=8) tokens, labeled with lowercase letters separated by “-”. A long prompt P could look like x-y-z, where z is an incomplete chunk (e.g. 2 toks). Executing the full prefill for P would then take ≥ 3 engine steps (> can happen if it’s not scheduled for execution in one of the steps), and only in the last chunked prefill step would we sample one new token.

举个例子，假设每个 chunk 装 n（= 8）个 token，用小写字母加 “-” 来标记。一个长 prompt P 可能长这样：x-y-z，其中 z 是个不完整的 chunk（比如只有 2 个 token）。那么把 P 的 prefill 整个跑完，至少需要 3 个 engine step（> 是因为它可能某一步没被调度上），而且只有最后一个 chunked prefill step 才会采样出一个新 token。

Here is that same example visually:

同一个例子画出来是这样：

Figure 5: Chunked prefill

Implementation is straightforward: cap the number of new tokens per step. If the requested number exceeds long_prefill_token_threshold, reset it to exactly that value. The underlying indexing logic (described earlier) takes care of the rest.

实现很直接：限制每一步的新增 token 数。如果请求的数量超过了 long_prefill_token_threshold，就把它重置成正好等于这个值。剩下的交给前面讲过的底层索引逻辑。

In vLLM V1, you enable chunked prefill by setting long_prefill_token_threshold to a positive integer. (Technically, it can happen irrespective of this, if the prompt length exceeds the token budget we truncate it and run a chunked prefill.)

在 vLLM V1 里，把 long_prefill_token_threshold 设成一个正整数就启用了 chunked prefill。（严格说，即使不设也可能触发：如果 prompt 长度超过了 token budget，我们会把它截断并做一次 chunked prefill。）

Prefix Caching

To explain how prefix caching works, let’s take the original code example and tweak it a bit:

为了讲清楚 prefix caching 是怎么回事，我们把最开始的代码例子稍微改一下：

from vllm import LLM, SamplingParams

long_prefix = "<a piece of text that is encoded into more than block_size tokens>"

prompts = [
    "Hello, my name is",
    "The president of the United States is",
]

sampling_params = SamplingParams(temperature=0.8, top_p=0.95)

def main():
    llm = LLM(model="TinyLlama/TinyLlama-1.1B-Chat-v1.0")

    outputs = llm.generate(long_prefix + prompts[0], sampling_params)
    outputs = llm.generate(long_prefix + prompts[1], sampling_params)

if __name__ == "__main__":
    main()

Prefix caching avoids recomputing tokens that multiple prompts share at the beginning - hence prefix.

Prefix caching 避免了对多个 prompt 共享的开头部分做重复计算——所以叫 prefix（前缀）。

The crucial piece is the long_prefix: it’s defined as any prefix longer than a KV-cache block (16 tokens by default). To simplify our example let’s say long_prefix has exactly length n x block_size (where n ≥ 1).

关键角色是那个 long_prefix：它被定义为任何长度超过一个 KV-cache block（默认 16 个 token）的前缀。为了简化例子，假设 long_prefix 的长度正好是 n × block_size（n ≥ 1）。

说明

i.e. it perfectly aligns with block boundary - otherwise we’d have to recompute long_prefix_len % block_size tokens as we can’t cache incomplete blocks.

说明

也就是说，它完美对齐到 block 边界——否则我们就得重算 long_prefix_len % block_size 个 token，因为不完整的 block 是没法缓存的。

Without prefix caching, each time we process a new request with the same long_prefix, we’d recompute all n x block_size tokens.

没有 prefix caching 时，每处理一个带相同 long_prefix 的新请求，都要把 n × block_size 个 token 全部重算一遍。

With prefix caching, those tokens are computed once (their KVs stored in KV cache paged memory) and then reused, so only the new prompt tokens need processing. This speeds up prefill requests (though it doesn’t help with decode).

有了 prefix caching，这些 token 只算一次（它们的 KV 存进 KV cache 的 paged memory），之后直接复用，只需要处理新增的那部分 prompt token。这能加速 prefill 请求（不过对 decode 没帮助）。

How does this work in vLLM?

在 vLLM 里这是怎么实现的？

During the first generate call, in the scheduling stage, inside kv_cache_manager.get_computed_blocks, the engine invokes hash_request_tokens:

第一次调用 generate 时，在调度阶段、在 kv_cache_manager.get_computed_blocks 里，engine 会调用 hash_request_tokens：

This function splits the long_prefix + prompts[0] into 16-token chunks.
For each complete chunk, it computes a hash (using either the built-in hash or SHA-256, which is slower but has fewer collisions). The hash combines the previous block’s hash, the current tokens, and optional metadata.

这个函数把 long_prefix + prompts[0] 切成 16 个 token 一块。
对每个完整的块算一个 hash（用内置 hash，或者更慢但碰撞更少的 SHA-256）。这个 hash 由前一个 block 的 hash、当前 token，以及可选的 metadata 组合而成。

说明

optional metadata includes: MM hash, LoRA ID, cache salt (injected into hash of the first block ensures only requests with this cache salt can reuse blocks).

说明

可选 metadata 包括：MM hash、LoRA ID、cache salt（把它注入第一个 block 的 hash，可以保证只有带这个 cache salt 的请求才能复用这些 block）。

Each result is stored as a BlockHash object containing both the hash and its token IDs. We return a list of block hashes.

每个结果都存成一个 BlockHash 对象，同时包含 hash 和它的 token ID。我们返回一个 block hash 的列表。

The list is stored in self.req_to_block_hashes[request_id].

这个列表存进 self.req_to_block_hashes[request_id]。

Next, the engine calls find_longest_cache_hit to check if any of these hashes already exist in cached_block_hash_to_block. On the first request, no hits are found.

接着，engine 调用 find_longest_cache_hit，检查这些 hash 里有没有哪个已经存在于 cached_block_hash_to_block 里。第一个请求当然是全部未命中。

Figure 6: Prefix caching - hash function

Then we call allocate_slots which calls coordinator.cache_blocks, which associates the new BlockHash entries with allocated KV blocks and records them in cached_block_hash_to_block.

然后我们调用 allocate_slots，它进而调用 coordinator.cache_blocks，把新的 BlockHash 条目和已分配的 KV block 关联起来，记录到 cached_block_hash_to_block。

Afterwards, the forward pass will populate KVs in paged KV cache memory corresponding to KV cache blocks that we allocated above.

之后，forward pass 会把 KV 写进上面这些 KV cache block 对应的 paged KV cache 显存里。

说明

After many engine steps it’ll allocate more KV cache blocks but it doesn’t matter for our example because the prefix has diverged immediately after long_prefix.

说明

很多个 engine step 之后它会分配更多 KV cache block，但这对我们的例子没影响，因为前缀在 long_prefix 之后立刻就开始分叉了。

图 7：Prefix caching —— 把 KV 写进 paged memory

Figure 7: Prefix caching - populate KVs in paged memory

On a second generate call with the same prefix, steps 1-3 repeat, but now find_longest_cache_hit finds matches for all n blocks (via linear search). The engine can reuse those KV blocks directly.

第二次用同一个前缀调用 generate 时，步骤 1–3 重复一遍，但这次 find_longest_cache_hit 通过线性搜索命中了全部 n 个 block，engine 可以直接复用这些 KV block。

Figure 8: Prefix caching - reuse KVs

If the original request were still alive, the reference count for those blocks would increment (e.g. to 2). In this example, the first request has already completed, so the blocks were freed back to the pool and their reference counts set back to 0. Because we were able to retrieve them from cached_block_hash_to_block we know they’re valid (the logic of the KV cache manager is setup in such a way), so we just remove them from free_block_queue again.

如果原来那个请求还活着，这些 block 的引用计数会递增（比如加到 2）。在这个例子里第一个请求已经完成了，所以这些 block 被还回池子、引用计数归 0。因为我们是能从 cached_block_hash_to_block 里把它们取出来的，所以知道它们仍然有效（KV cache manager 的逻辑就是这么设计的），于是我们只需把它们再次从 free_block_queue 里摘掉。

Advanced note:

KV-cache blocks become invalid only when they’re about to be reallocated from the free_block_queue (which pops from the left) and we discover the block still has an associated hash and is present in cached_block_hash_to_block. At that moment, we clear the block’s hash and remove its entry from cached_block_hash_to_block, ensuring it can’t be reused via prefix caching (at least not for that old prefix).

进阶注解

只有当 KV-cache block 即将从 free_block_queue（从左端弹出）被重新分配，而我们发现这个 block 仍带着 hash、并且还存在于 cached_block_hash_to_block 里时，它才会失效。那一刻我们会清掉这个 block 的 hash，并从 cached_block_hash_to_block 里删掉它的条目，确保它没法再被 prefix caching 复用（至少对那个旧前缀是这样）。

And that’s the gist of prefix caching: don’t recompute prefixes you’ve already seen — just reuse their KV cache!

这就是 prefix caching 的全部要点：别重算你已经见过的前缀，直接复用它们的 KV cache。

If you understood this example you also understood how paged attention works.

如果你看懂了这个例子，你其实也就看懂了 paged attention 是怎么工作的。

Prefix caching is enabled by default. To disable it: enable_prefix_caching = False.

Prefix caching 默认开启。关掉它：enable_prefix_caching = False。

Guided Decoding (FSM)

Guided decoding is a technique where, at each decoding step, the logits are constrained by a grammar-based finite state machine. This ensures that only tokens allowed by the grammar can be sampled.

Guided decoding 是这样一种技术：在每一个 decoding step，用一台基于 grammar 的有限状态机（FSM）来约束 logits，从而保证只有 grammar 允许的 token 才可能被采样到。

It’s a powerful setup: you can enforce anything from regular grammars (Chomsky type-3, e.g. arbitrary regex patterns) all the way up to context-free grammars (type-2, which cover most programming languages).

这套机制很强：从正则语法（Chomsky type-3，比如任意 regex 模式）一路到 context-free grammar（type-2，覆盖了大多数编程语言），你都能约束。

To make this less abstract, let’s start with the simplest possible example, building on our earlier code:

为了让这件事不那么抽象，我们从最简单的例子开始，接着前面的代码写：

from vllm import LLM, SamplingParams
from vllm.sampling_params import GuidedDecodingParams

prompts = [
    "This sucks",
    "The weather is beautiful",
]

guided_decoding_params = GuidedDecodingParams(choice=["Positive", "Negative"])
sampling_params = SamplingParams(guided_decoding=guided_decoding_params)

def main():
    llm = LLM(model="TinyLlama/TinyLlama-1.1B-Chat-v1.0")

    outputs = llm.generate(prompts, sampling_params)

if __name__ == "__main__":
    main()

In the toy example I gave (assume character-level tokenization): at prefill, the FSM masks logits so only “P” or “N” are viable. If “P” is sampled, the FSM moves to the “Positive” branch; next step only “o” is allowed, and so on.

在我举的这个玩具例子里（假设是字符级 tokenization）：prefill 时，FSM 会把 logits 遮掉，只留下 “P” 或 “N” 两个可能。如果采样出 “P”，FSM 就走到 “Positive” 这个分支；下一步只允许 “o”，依此类推。

Figure 9: Toy example FSM

How this works in vLLM:

在 vLLM 里这是怎么实现的：

At LLM engine construction, a StructuredOutputManager is created; it has access to the tokenizer and maintains a _grammar_bitmask tensor.
When adding a request, its status is set to WAITING_FOR_FSM and grammar_init selects the backend compiler (e.g., xgrammar [7]; note that backends are 3rd party code).
The grammar for this request is compiled asynchronously.
During scheduling, if the async compile has completed, the status switches to WAITING and request_id is added to structured_output_request_ids; otherwise it’s placed in skipped_waiting_requests to retry on next engine step.
After the scheduling loop (still inside scheduling), if there are FSM requests, the StructuredOutputManager asks the backend to prepare/update _grammar_bitmask.
After the forward pass produces logits, xgr_torch_compile’s function expands the bitmask to vocab size (32x expansion ratio because we use 32 bit integers) and masks disallowed logits to –∞.
After sampling the next token, the request’s FSM is advanced via accept_tokens. Visually we move to the next state on the FSM diagram.

构造 LLM engine 时会创建一个 StructuredOutputManager；它能访问 tokenizer，并维护一个 _grammar_bitmask tensor。
添加请求时，它状态被置为 WAITING_FOR_FSM，grammar_init 选出后端编译器（比如 xgrammar [7]；注意后端是第三方代码）。
这个请求的 grammar 被异步编译。
调度时，如果异步编译已经完成，状态切到 WAITING、request_id 被加进 structured_output_request_ids；否则它被放进 skipped_waiting_requests，等下一个 engine step 重试。
调度循环结束后（仍在调度阶段内），如果有 FSM 请求，StructuredOutputManager 会让后端准备/更新 _grammar_bitmask。
forward pass 产出 logits 之后，xgr_torch_compile 的函数会把 bitmask 扩展到 vocab 大小（扩展倍率是 32×，因为我们用的是 32 位整数），并把不允许的 logits 遮成 –∞。
采样出下一个 token 之后，请求的 FSM 通过 accept_tokens 前进一格。视觉上，就是在 FSM 图上走到下一个状态。

Step 6 deserves further clarification.

第 6 步值得再解释一下。

If vocab_size = 32, _grammar_bitmask is a single integer; its binary representation encodes which tokens are allowed (“1”) vs disallowed (“0”). For example, “101…001” expands to a length-32 array [1, 0, 1, …, 0, 0, 1]; positions with 0 get logits set to –∞. For larger vocabularies, multiple 32-bit words are used and expanded/concatenated accordingly. The backend (e.g., xgrammar) is responsible for producing these bit patterns using the current FSM state.

如果 vocab_size = 32，_grammar_bitmask 就是一个整数；它的二进制表示编码了哪些 token 允许（“1”）、哪些不允许（“0”）。比如 “101…001” 扩展成长度 32 的数组 [1, 0, 1, ..., 0, 0, 1]；位置上是 0 的 logits 会被设成 –∞。词表更大时，会用多个 32 位字，并相应扩展、拼接。后端（比如 xgrammar）负责根据当前 FSM 状态产出这些 bit pattern。

说明

Most of the complexity here is hidden in the 3rd party libs like xgrammar.

说明

这里的大部分复杂度都藏在 xgrammar 这类第三方库里。

Here is an even simpler example with vocab_size = 8 and 8-bit integers (for those of you who like my visuals):

下面是一个更简单的例子，vocab_size = 8、用 8 位整数（给喜欢看图的朋友）：

Figure 10: Toy example

You can enable this in vLLM by passing in a desired guided_decoding config.

在 vLLM 里，传入想要的 guided_decoding 配置就能启用它。

下一篇：高级特性（下）—— speculative decoding 与 disaggregated P/D。

注释

“XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models” —— https://arxiv.org/abs/2411.15100

Advanced Features — extending the core engine logic