前缀缓存命中之后：五个推理框架如何把一段旧 KV 接进一次新前向

匹配入口：get_computed_blocks

vLLM V1 的调度器在把一个 waiting 请求放进本轮 batch 之前，先调用 KVCacheManager.get_computed_blocks。这个函数的返回值是三元组：命中块、命中 token 数、以及一个 shared_prefix_boundary。

1
def get_computed_blocks(self, request: Request):
2
    if not self.prefix_cache_lookup_enabled(request):
3
        return self.empty_kv_cache_blocks, 0, 0
4

5
    # 全命中时也必须重算最后一个 token 以得到 logits
6
    max_cache_hit_length = request.num_tokens - 1
7
    computed_blocks, num_new_computed_tokens, num_uncached = (
8
        self.coordinator.find_longest_cache_hit(
9
            request.block_hashes, max_cache_hit_length
10
        )
11
    )
12
    ...
13
    blocks = self.create_kv_cache_blocks(computed_blocks)
14
    return blocks, num_new_computed_tokens, shared_prefix_boundary

这里有两个细节值得停下来看。第一，max_cache_hit_length 被截断到 num_tokens - 1。原因写在注释里：如果所有 token 都命中，模型没有任何新 token 可算，就拿不到 logits。所以必须留最后一个 token 重算。第二，因为 allocate_slots 要求 num_computed_tokens 按块对齐，这个截断在实践中会触发整个最后一块的重算，而不仅仅是一个 token。注释也坦承“移除这个限制可以在未来略微提升性能”。

find_longest_cache_hit 本身在两种协调器里实现不同。UnitaryKVCacheCoordinator 是单组，直接把 block_hashes 交给唯一的单类型管理器；HybridKVCacheCoordinator 要处理多个 KV 组（例如 Mamba + 全注意力），用迭代不动点的方式不断降低候选长度：

1
while True:
2
    curr_hit_length = hit_length
3
    for idx, (spec, group_ids, manager_cls, use_eagle) in enumerate(
4
        self.attention_groups
5
    ):
6
        ...
7
        hit_blocks, _new_hit_length = manager_cls.find_longest_cache_hit(
8
            block_hashes=block_hashes, max_length=_max_length,
9
            kv_cache_group_ids=group_ids, block_pool=..., kv_cache_spec=spec,
10
            drop_eagle_block=drop_eagle_block,
11
            alignment_tokens=self._cache_hit_alignment_tokens,
12
            dcp_world_size=..., pcp_world_size=...,
13
        )

每个注意力类型要么接受当前长度，要么降低它。只要有一类降低了，循环就从头再检查所有类型。因为长度单调下降且下界为 0，算法收敛。全注意力组有一个优化：它是“向下封闭”的，一旦查过一遍缓存块，后续只按降低后的长度裁剪即可，无需再查树。

FullAttentionManager.find_longest_cache_hit 的第一阶段是从头开始的连续整块遍历：

1
for block_hash in itertools.islice(full_block_hashes, max_length // block_size):
2
    cached_block = block_pool.get_cached_block(block_hash, kv_cache_group_ids)
3
    if not cached_block:
4
        break
5
    for computed, cached in zip(computed_blocks, cached_block):
6
        computed.append(cached)
7
hit_length = len(computed_blocks[0]) * block_size

链式哈希保证了“碰到第一个 miss 就可以停”。如果哈希块大小小于缓存块大小（细粒度哈希），还有第二阶段：在第一个未满块内部，从高到低探测内部哈希边界，找到最长命中。这是 hash_block_size < block_size 的细粒度模式下才有的路径。

命中之后：allocate_slots 的三段布局

命中块拿到手之后，调度器进入 allocate_slots。这个函数的 docstring 里画了一张布局图，几乎就是 vLLM 对“命中之后”的完整定义：

1
| < comp > | < new_comp > | < ext_comp >  | < new >  | < lookahead > |

其中 comp 是请求此前已经计算过的 token（同一请求在分块 prefill 中上一轮算过的部分），new_comp 是本轮刚刚通过前缀缓存命中的本地块，ext_comp 是 KV connector 从别的实例加载来的块，new 是本次要新计算并分配的 token 数，lookahead 是投机解码草稿需要的预留槽。

这个布局有一个很实际的后果：num_computed_tokens 是三个来源之和，而注意力 kernel 只看到 num_computed_tokens 这一个标量。命中段和已有段在 kernel 眼里没有区别，都是“可以直接读的 KV”。

位置与 mask：从 num_computed_tokens 出发

命中写入请求状态后，后续所有派生量都从这个数字出发。在 gpu_model_runner.py 里：

1
self.positions[:total_num_scheduled_tokens] = (
2
    self.num_computed_tokens[req_indices_gpu].to(torch.int64)
3
    + self.query_pos.gpu[:total_num_scheduled_tokens]
4
)
5
self.seq_lens[:num_reqs] = (
6
    self.num_computed_tokens[:num_reqs] + num_scheduled_tokens_gpu
7
)

位置 = 已计算 token 数 + 本批内查询序号。如果命中 2048 个 token、本轮调度的查询是 256 个 token，位置就是 2048 到 2303。query_start_loc 按请求累加本批调度 token 数，seq_lens 是“已计算 + 本批调度”，注意力 kernel 用两者推导 chunked prefill 的 mask。

（图源：vLLM 官方设计文档“Automatic Prefix Caching”。图中空队列与可复用队列的分离，解释了为什么命中块的重新占用必须走“从空队列取出”而不是从缓存队列直接拿。）

一个容易被忽略的细节在细粒度哈希模式下：_cache_partial_tail_block 只把 prompt 的最后一个哈希边界注册为部分前缀项，中间边界故意不登记。原因是重复发送的 prompt 最多命中 prompt_len - 1，而 EAGLE 的查找会读过整个 prompt 再丢掉一个哈希单位。这些设计共同决定了：vLLM 的命中永远是“从头开始、整对齐、最后一个 token 必重算”。

EAGLE 的额外扣减

find_longest_cache_hit 在启用 EAGLE / MTP 时还有一个 drop_eagle_block：命中后主动丢掉最后一个命中单位。原因在 docstring 里：EAGLE 需要生成点之前的 token 重新计算，以得到 hidden states 供草稿头使用。细粒度模式下丢一个哈希单位，粗粒度模式下丢一个缓存块，然后按 alignment_tokens 向下取整、裁剪多余块。

这一条对后面横向对比很关键：投机解码会主动缩短前缀命中。同一段 prompt，开不开 EAGLE，命中长度就可能差一个块。

RadixKey.match：指数搜索加二分

RadixKey.match 负责在两个 token id 数组之间找公共前缀长度。它不是逐 token 循环，而是用「倍增窗口 + 二分」的方式，在 C 层做切片比较：

1
matched_tokens = n
2
lo = 0
3
step = 1
4
while lo < n:
5
    hi = lo + step if lo + step < n else n
6
    if t0[lo:hi] != t1[offset + lo : offset + hi]:
7
        while hi - lo > 1:
8
            mid = (lo + hi) // 2
9
            if t0[lo:mid] == t1[offset + lo : offset + mid]:
10
                lo = mid
11
            else:
12
                hi = mid
13
        matched_tokens = lo
14
        break
15
    lo = hi
16
    step *= 2
17

18
matched_tokens = min(matched_tokens, len(self), len(other) - offset)
19
if page_size == 1:
20
    return matched_tokens
21
return (matched_tokens // page_size) * page_size

最后两行是重点：页大小大于 1 时，命中长度向下取整到页边界。这与 vLLM 的整块对齐是同一种思想的两种表达——只不过一个按哈希块，一个按页。

match_prefix 与节点分裂

match_prefix 返回 device_prefix_len 与 last_device_node。遍历过程中，如果匹配停在一个已存段的中间，会调用 _split_node 把这个段一分为二，让命中边界成为树上的真实节点。这样后续的“锁路径”和“插入”都落在精确边界上。

命中之后，SGLang 并不是立刻把节点锁死给请求；它要等 prefill 真正插入了这段 KV、完成 checkpoint 之后，才把 req.lock 从旧节点切换到新节点：

1
self.token_to_kv_pool_allocator.free_segment(
2
    kv_indices[req.kv.cache_protected_len : result.prefix_len],
3
    start_pos=req.kv.cache_protected_len,
4
)
5
return radix_key, kv_indices, result.prefix_len

这段代码出现在 _insert_cache 之后：cache_protected_len 是请求仍然私有的部分，prefix_len 是整个前缀。已经被树保护的部分归还给分配器，请求只保留自己额外拿到的段。

prefix_len 如何变成 batch 的 prefix_lens

命中长度最终要落到 ScheduleBatch 上。SGLang 在组 batch 时，把每个请求的 prefix_len 和 extend_len 放进列表：

1
self.prefix_lens = prefix_lens
2
self.extend_lens = extend_lens
3
self.seq_lens = seq_lens_tensor
4
self.extend_num_tokens = extend_num_tokens

这里还有一个多模态的剔除步骤：如果编码器输出的 token 已经算过，encoder_len 会从 prefix_lens 和 extend_lens 里扣掉，保证“prefix 不跨编码器边界”。这说明前缀命中在 SGLang 里不是一个孤立数字，而是要在 prefill 输入组装阶段和编码器、图像 token 边界一起被修正。

位置：compute_position 从 extend_prefix_lens 开始

ForwardBatch.init_new 里，extend 模式会调用 compute_position，后者按每个请求的 extend_prefix_lens 和 extend_seq_lens 生成位置序列：

1
positions = torch.cat([
2
    torch.arange(prefix_len, prefix_len + extend_len, device=...)
3
    for prefix_len, extend_len in zip(extend_prefix_lens, extend_seq_lens)
4
], dim=0)

这与 vLLM 的表达式在数学上完全等价，只是 vLLM 用“标量 + 批内序号”，SGLang 用“每个请求的 prefix_len 生成 arange”。两种写法对 kernel 的语义是一样的：命中段的位置已经被占用，新查询从 prefix_len 开始编号。

KV 写入：out_cache_loc 只覆盖新算段

SGLang 的 alloc_for_extend 返回 out_cache_loc，它是“新算 token 的 KV 槽位”，不是“命中 token 的槽位”。命中段的槽位已经在请求的 req_to_token_pool 行里，或者已经在树的路径上。forward 结束后，这些新槽位通过 checkpoint 写回树，成为后续请求可命中的部分。

（图源：RadixAttention 论文（SGLang） 图 8。左侧击中率消融说明树缓存对请求序列的敏感性，右侧 RadixAttention 对比说明共享前缀在多轮任务中的收益规模。）

slot 选择：LCP 相似度

server-context.cpp 在选择空闲 slot 时，会计算每个已缓存 slot 的公共前缀长度与输入长度的比值：

1
const size_t lcp_len = tokens.get_common_prefix(task.tokens);
2
const float f_sim_cur = float(lcp_len) / task.tokens.size();
3
if (f_sim_cur > f_sim_best && f_sim_cur > slot_prompt_similarity) {
4
    f_sim_best = f_sim_cur;
5
    ret = &slot;
6
}

如果选中的 slot 会丢掉它超过一半的已有上下文，就先把当前上下文存进 prompt cache（update_cache = true），然后再进入下一步。

n_past 与 seq_rm

真正的交接发生在 slot 开始处理新任务时。n_past 是“可以复用的 token 数”，由 get_common_prefix(input_tokens) 得到，再用几项硬上限裁剪：

1
n_past = slot.prompt.tokens.get_common_prefix(input_tokens);
2
if (slot.task->n_tokens_shared > 0) n_past = std::min(n_past, slot.task->n_tokens_shared);
3
if (n_decision_first >= 0) n_past = std::min(n_past, n_decision_first);
4
if (slot.alora_invocation_start > 0) n_past = std::min(n_past, slot.alora_invocation_start - 1);

这几项硬上限分别对应：共享前缀的子请求不能越过父请求的共享边界；decision 任务必须重新评估首位置；alora 调用之后的部分不能被缓存。这些限制不是“优化”，而是正确性边界。

然后是最关键的一步：把上下文里的 KV 裁剪到 n_past。裁剪之前还要处理 SWA 与 checkpoint：

1
const llama_pos pos_eval = pos_next - (has_new_tokens ? 0 : 1);
2
const auto pos_min_thold = std::max(0, n_swa > 0 ? pos_eval - n_swa + 2 : pos_eval);

如果当前上下文的最小位置 pos_min 已经不满足 SWA 窗口要求（例如 SWA 或混合循环层已经丢掉了更早的 KV），就会尝试恢复最近的 checkpoint；如果没有可用 checkpoint，就强制全量重算：

1
if (do_reset) {
2
    pos_next = 0;
3
    n_past = 0;
4
}

最后还有一个“至少算一个 token”的保护：

1
if (n_past == slot.task->n_tokens() && n_past > 0) {
2
    n_past--;
3
}

这和 vLLM 的 num_tokens - 1 截断是同一个道理的两种写法。

n_cache_reuse：块移位复用

llama.cpp 还有一个 vLLM / SGLang 都没有的机制：n_cache_reuse。当新 prompt 与旧 prompt 不只是头部相同，而是中段也有大块相同文本时，可以把旧 KV 的一段平移到新位置复用：

1
while (head_c < slot.prompt.tokens.size() && head_p < input_tokens.size()) {
2
    size_t n_match = 0;
3
    while (head_c + n_match < ... && slot.prompt.tokens[head_c + n_match] == input_tokens[head_p + n_match]) n_match++;
4
    if (n_match >= (size_t) n_cache_reuse) {
5
        const int64_t kv_shift = (int64_t) head_p - (int64_t) head_c;
6
        slot.mem.seq_rm(slot.id, head_p, head_c);
7
        slot.mem.seq_add(slot.id, head_c, head_c + n_match, kv_shift);
8
        ...
9
    } else {
10
        head_c += 1;
11
    }
12
}

前提是 llama_memory_can_shift 为真。它本质上把“前缀命中”从“头部公共前缀”扩展到了“中段块匹配”，代价是需要按位置平移 KV，并且对不支持 shift 的注意力类型（例如部分 SWA 实现）会直接禁用。

位置与写入

llama.cpp 的位置来自 slot.prompt.tokens.pos_next(n_past)，它是“token 序列中第 n_past 个 token 的绝对位置”。命中段的 KV 已经在上下文里，新 token 继续往后追加；seq_rm 已经删掉了 n_past 之后的部分，所以 seq_add 只会写入新的 token。

llama.cpp 的代表性在于：它没有块池，也没有跨请求共享的树，命中收益来自“同一个 slot 的上下文复用”。这让它的命中粒度最细（token 级），但命中范围也最窄（只在同一 slot 的保留上下文中）。

微批调度器只看到估算值

TensorRT-LLM 的 MicroBatchScheduler 在准入时使用的是一个估算值 estimated_reusable_tokens，它来自 radix 树的探测。真正的复用长度 prepopulated_prompt_len 是在 KVCacheManager.addSequence 里算出来的：

1
for (size_t i = 0; i < n; ++i) {
2
    auto& llmRequest = llmRequests[i].get();
3
    if (mEnableBlockReuse) {
4
        llmRequest.setPrepopulatedPromptLen(minPrepopulatedLen[i], getTokensPerBlock());
5
        llmRequest.setEstimatedReusableTokens(0);
6
    }
7
}

minPrepopulatedLen 是“所有窗口里最小的预填充长度”。Variable SWA 下同一个序列会被多个窗口管理器处理，每个窗口能匹配的长度不同，取最小值保证所有窗口都对得上。

事后校正：maybe_fit_token_budget

问题在于估算值和真实值可能不一致。resource_manager.py 里有一段很长的注释，解释为什么必须在所有管理器跑完之后再裁剪 token 预算：

The micro-batch scheduler admits the batch on estimated_reusable_tokens (a radix-tree guess). The real reuse is prepopulated_prompt_len, computed inside addSequence. #13318 is the case where the two differ, so no check running before addSequence can see the divergence.

Until setPrepopulatedPromptLen runs, context_chunk_size still spans the reusable prefix — it is not a token count, and reading it as one over-charges a reuse hit by the whole cached prefix.

这段注释直接回答了本文的核心问题之一：命中长度在调度器的两个阶段是两个不同的数字，一个是估算，一个是真相。TensorRT-LLM 选择“先按估算准入，再用真相修正”，修正点放在 prepare_resources 的末尾：

1
def prepare_resources(self, scheduled_batch):
2
    for _, resource_manager in self.resource_managers.items():
3
        if hasattr(resource_manager, "prepare_resources"):
4
            resource_manager.prepare_resources(scheduled_batch)
5
    self.maybe_fit_token_budget(scheduled_batch)

裁剪之所以安全，是因为它只缩小、不推迟：没有请求被移出 batch，因此注意力 DP 的投票、PP 的 inflight 集合、前面所有管理器的每请求状态都与当时计算的 batch 一致。

资源探测接口：probe_prefix_match_length

TensorRT-LLM 还暴露了一个独立的探测接口，供 cache-aware 路由使用：

1
def probe_prefix_match_length(self, input_tokens, lora_task_id=None, cache_salt=None):
2
    if not self.enable_block_reuse:
3
        return 0
4
    ...
5
    block_key = BlockKey(tokens=input_tokens, lora_task_id=lora_task_id)
6
    unique_tokens = block_key.unique_tokens
7
    dummy_req = CppLlmRequest(request_id=0, max_new_tokens=0, input_tokens=input_tokens, ...)
8
    summary = self.impl.analyze_prefix_reuse(unique_tokens, dummy_req)
9
    return summary.reusable_blocks_all * self.tokens_per_block

注意它用的是 reusable_blocks_all 而不是 reusable_blocks_allocated。前者是“树上存在”的块，后者是“当前仍被引用、一定可用”的块。路由阶段还没有分配，所以用前者；真正 addSequence 时会再检查引用状态。analyzePrefixReuse 的底层实现还显式禁用了 partial reuse：

1
auto reuseMatches = findReusableBlockMatches(
2
    blockKeys, /*enablePartialReuse=*/false, /*copyOnPartialReuse=*/false, ...);

这是因为分析阶段不应该产生副作用（复制或部分复用会改块状态），真正复用时才按配置启用。

位置：context_current_position

TensorRT-LLM 的 LlmRequest 有两个容易混淆的位置量：context_current_position 与 context_chunk_size。命中之后，context_current_position 从 prepopulated_prompt_len 开始；_pack_context_requests 里：

1
begin_compute = request.context_current_position
2
end_compute = begin_compute + request.context_chunk_size
3
prompt_tokens = request.get_tokens_range(0, begin_compute, end_compute)
4
position_ids.extend(range(begin_compute, begin_compute + len(prompt_tokens)))

位置 = 当前上下文位置到当前 chunk 结束。context_chunk_size 在 setPrepopulatedPromptLen 之前包含整个复用前缀，所以不能在之前把它当成 token 数；这也正是 maybe_fit_token_budget 必须后移的原因。

还有一个“lookahead token”的细节：如果当前 chunk 不是最后一个，会取 chunk 结束处的下一个 token 作为 context_prompt_lookahead，供某些模型在最后一块时预测下一块的开头。命中长度改变 chunk 边界时，这个 lookahead 也要跟着变。

命中数是一个外部注入的标量

Sequence 的 C++ 状态里，命中数不是一个专门的 hit_tokens 字段（虽然存在 cached_hit_tokens 属性，但在开源路径里并不参与调度），而是 cache.num_tokens：

1
struct KvCacheState {
2
    int block_size{0};
3
    int previous_num_tokens{0};
4
    int num_tokens{0};
5
    int hit_tokens{0};
6
    int swa_valid_start{0};
7
    std::vector<int> block_table;
8
    int state_id{-1};
9
    int last_copy_state_token_idx{0};
10

11
    void set_num_tokens(int value) {
12
        num_tokens = value;
13
        previous_num_tokens = value;
14
    }
15
};

外部系统把 KV 块直接写进 GPU 池、把块表填进 block_table，然后把 num_tokens 设为命中长度。调度器只关心 num_tokens > 0 且 block_table 非空。

fork：把一段前缀复制给一批请求

DeepInfer 提供了一个 fork_seq 接口，给测试与上层系统复用：从一个已经 prefill 过前缀的源序列，fork 出一批共享同样前缀的新序列：

1
SequencePtr fork_seq(const SequencePtr &seq, py::object blocks, std::string &&target_branch_id, ...) {
2
    TORCH_CHECK(seq->cache.num_tokens > 0, "Cannot fork a sequence without a computed prefix");
3
    const bool prompt_incomplete = seq->cache.num_tokens < seq->get_len() - 1;
4
    ...
5
    init.cache.block_table = seq->cache.block_table;   // 或外部传入的 blocks
6
    ...
7
    fork_seq->cache.set_num_tokens(std::min(seq->cache.num_tokens, fork_seq->get_len() - 1));
8
    ...
9
    block_manager->pin_blocks(fork_seq->cache.block_table);
10
    if (state_manager) {
11
        fork_seq->cache.state_id = seq->cache.state_id;
12
        state_manager->pin_block(seq->cache.state_id);
13
    }
14
    if (prompt_incomplete) {
15
        waiting.emplace_front(fork_seq);
16
    } else {
17
        prompted.emplace_back(fork_seq, true);
18
    }
19
}

三个细节：set_num_tokens(min(num_tokens, get_len() - 1)) 同样保留了最后一个 token；块表被 pin 住，防止源序列释放后 fork 的序列读到已回收块；如果源序列的 prompt 已经完整（prompt_incomplete 为假），fork 出来的序列直接进 prompted 队列，跳过 prefill。

注意 state_branch_id 与 block table 的关系：fork 时如果不提供 blocks，新序列直接引用源序列的块表、并把它们 pin 住。这意味着上层系统只负责“源序列的命中段在哪”，DeepInfer 自己负责引用计数。

命中之后的调度：chunked prefill 从 num_tokens 起算

_schedule_prefill 里，num_prompt_tokens = seq->get_len() - seq->cache.num_tokens。如果 num_tokens == 0，走普通前缀查找分支（开源版里其实是“没有命中”）；如果 block_table 非空，则走 branch_id 以 _ 开头的 fork 分支：

1
if (seq->schedule.branch_id.compare(0, 1, "_") == 0) {
2
    _clone_state(*seq);
3
    auto new_blocks = block_manager->allocate_nolock(to_allocate_blocks);
4
    if (seq->cache.num_tokens % seq->cache.block_size) { // 有尾巴，需要 copy
5
        clone_blocks.emplace_back(seq->cache.block_table[num_reserve_blocks]);
6
        clone_blocks.emplace_back(new_blocks.front());
7
    }
8
    for (size_t i = ...; i < seq->cache.block_table.size(); ++i) {
9
        clone_blocks.emplace_back(seq->cache.block_table[i]);
10
        clone_blocks.emplace_back(0);
11
    }
12
}

fork 的序列如果与源序列共享最后一个不完整块，会先把那个块复制到新块（clone_blocks 是 (src, dst) 对，dst=0 表示只归还 src），然后让新序列拥有自己的尾巴块。这是分叉的核心：共享的块保持引用计数，写的位置用私有块。

位置与 SWA：seqlen_k 与 swa_valid_start

DeepInfer 的注意力元数据不是“position 数组 + mask”，而是“seqlen_q / seqlen_k + 压缩比例 + SWA 有效下界”。命中之后，seqlen_k 从 cache.num_tokens 加本批查询长度；位置在 prepare_tensor_input_v4.cpp 里由 seqlen_k - seqlen_q 推出：

1
int32_t q_start = p_seq->seqlen_k - q_len;

也就是“本 chunk 的起始绝对位置”。这与前四个框架的位置表达式完全同构，只是它不显式构造位置数组，而是在 kernel 内按绝对位置索引 RoPE 表。

SWA 层的 KV 读取则多了一层 padding_len：

1
const int32_t history_end = p_seq->seqlen_k - p_seq->seqlen_q;
2
const int32_t history_begin = history_end - window_size;
3
const int32_t padding_len = std::clamp(p_seq->swa_valid_start - history_begin, 0, window_size);
4
const int32_t valid_begin = history_begin + padding_len;
5
builder.append_zero_fill(padding_len);
6
builder.append_ring_range(p_seq->state_id, valid_begin, history_end);

如果 swa_valid_start 大于窗口左边界，说明窗口左侧一部分 KV 已经被清零（零状态重算），这段要用零填充而不是读 ring buffer。这就是“命中之后”在 SWA 模型上多出来的第 7 个问题：命中段的 SWA 状态是否还完整。

YoCo 有界重放：命中长度在 prefill 里被重新定义

DeepInfer 对 SWA 模型的 prefill 有一个额外机制：YoCo 有界重放。当 DEEPINFER_YOCO_PREFILL_TRUNCATION_MODE 非 off 且 keep_tokens 为 140 时，长 prompt 的 prefill 只计算最后一段矩形区、再用 SWA 可见性拼出窗口：

1
int32_t abs_lo = std::clamp(std::max({pos - window_size + 1, rect_lo, valid_start}), 0, pos + 1);
2
int32_t start_slot = abs_lo - (q_start - window_size);
3
...
4
return {start_slot, window_size - start_slot, k_lo, new_len};

其中 rect_lo = data_len - keep_tokens，valid_start 是 SWA 状态的有效下界。compact 模式会截掉矩形之前的行，mask 模式不截行但把可见域收窄。在有界重放开启时，命中长度小于等于 keep_tokens 时直接收益为零，因为这段本来就会被重放覆盖；只有命中超过窗口长度之外的前缀部分才有收益。这一条在 vLLM 的 DSV41 路径里也有类似的处理（prefix_replay_tokens）。

统计：num_cached_tokens_gpu

DeepInfer 的 SchedulerOutputs 带一个 num_cached_tokens_gpu，统计层把它和 num_batched_tokens 相加作为“总需要访问的 token”：

1
calc_tokens = s.num_batched_tokens + s.num_cached_tokens_gpu
2
self._prefill_cached_tokens.append((calc_tokens, s.num_cached_tokens_gpu))

这个口径对应“命中率”的另一种定义：不是“命中 token / prompt token”，而是“命中 token / （新算 token + 命中 token）”。在分块 prefill 场景下，这个口径更能反映实际节省的注意力计算量。

命中长度上限：为什么所有框架都留一个 token

五个框架都做了同一件事：命中长度最多到 len - 1。原因不是实现偷懒，而是因果 LM 的性质：最后一个 token 的 logits 必须由模型计算出来。如果最后一个 token 也命中，模型就没有可算的查询，采样器拿不到 logits。

但“留一个 token”和“留一个块”是两个不同的实现。vLLM 因为 allocate_slots 要求块对齐，实际上会重算整个尾块；SGLang 的页大小小于 token 数时，可能只重算一个页；TensorRT-LLM 的 prepopulated setter 要求 prepopulated < promptLen，只保证最后一个 token 不在命中段里。

这个细节对 TTFT 的影响是：块越大，多算的 token 越多。128 token 的块在短 prompt 上可能多算 127 个 token，在 8k prompt 上可以忽略。这也是页面粒度在短请求上差异明显、在长请求上差异不明显的原因。

只读段的表达：三种完全不同的接口

vLLM 表达只读段的方式最“干净”：命中块直接进块表，注意力 kernel 用 num_computed_tokens 推出“前 num_computed_tokens 个 token 不需要查询”。SGLang 表达只读段的方式是 prefix_lens + extend_lens，attention backend 用这两个数组生成各自的 metadata（FlashAttention 用 seq_lens 和 extend_start_loc，FlashInfer 用 prefix_lens 与页表）。llama.cpp 表达只读段的方式最粗暴：seq_rm 直接把尾巴删掉，KV 数组里只剩下命中的那一段，新 token 直接 seq_add 追加。

TensorRT-LLM 和 DeepInfer 则介于两者之间：TensorRT-LLM 用块表加 prepopulated_prompt_len，DeepInfer 用块表加 swa_valid_start。区别在于：DeepInfer 多了一个“哪些命中段不可读”的维度。当 swa_valid_start > 0 时，命中段里可能有一部分 KV 是被清零的，kernel 必须用零填充而不是读取。

命中之后是否还要算：全命中的分歧

全命中时，vLLM / SGLang / llama.cpp / TensorRT-LLM 都会把请求丢进 prefill，只算最后一个 token（或最后一块）；DeepInfer 的 fork_seq 在 prompt_incomplete 为假时，会把 fork 出来的序列直接放进 prompted 队列，跳过 _schedule_prefill，由 decode 分支处理。这两条路径的差别在于“谁来算最后一个 token”和“KV 写入边界在哪里”，但结果一样：只算一个 query。