Prefix Caching

KV Cache aware routing

• Router 层面(业务层面）做 prefix matching： 因为所有请求都会先经过 router，所以 router 可以看到所有 incoming requests，基于这些 request stream，router 可以维护一个 database/ middleware，用来记录 prefix 和 server 的关系。当一个请求到来时，router 可以先做 prefix matching， 找到 longest prefix match，然后把请求发送到对应的 server。

  • 优点：实现比较直接，可以针对不同的业务做不同策略。
  • 缺点：router 会和 KV Cache Management 强耦合，会让 router 变得很重。

• Router 查询 KV Cache Management：有一套 KV Cache 管理的系统，在 route 上对 KV Cache 管理的系统发一个 request，询问到底哪一个节点有可复用的 KV Cache，收到 response 之后再把 request 放到对应的节点。

  • 优点：router 与 KV CacheManagement 解耦，router 不需要关心 Cache 是如何实现的
  • 缺点：router 多了一次查询,一旦 cache manager 查询偶尔变慢，就会影响请求尾延迟。

KV Cache routing 和 load balance 有本质冲突：

• 因为 KV-cache-aware routing 可能会把大量请求集中路由到同一个节点，这样虽然 Cache hit 很高，但很容易 overloaded.
• 如何 trade off

Table of contents

Prefix caching

llm.inference(
	input_tokens: list[int], # N tokens
	previous_kv_cache: list[Tensor], # M kv cache for prefix tokens and M < N
) -> output_tokens, new_kv_cache

output_tokens: # generated tokens, length N'
new_kv_cache: # kv cache for N + N' tokens

Why M < N ?

• N means the length of the current full input prompt.
• M means the length of the prefix that has already hit the cache and can be reused.
• Therefore, previous_kv_cache only covers input_tokens[:M]

tokens 是 key，KV cache tensors 是 value。因此我们可以先想象一个 KVCacheStore，它只暴露两个接口：store(tokens, kv_cache) 和 retrieve(tokens)。

class KVCacheStore:
	def store(self, tokens, kv_cache_tensors):
		pass
	def retrieve(self, tokens):
		return kv_cache_tokens

普通 key-value store 的语义是：key 完全相等才返回 value。但 LLM 前缀复用需要更细的语义。

假设系统已经缓存了 prompt ABCDE 对应的 KV Cache，当新请求是 ABCDF 时，前四个 token ABCD 的 KV Cache 仍然可复用。

从算法角度看，最长前缀匹配可以用 Trie 做。但讲者强调，工程实现不一定要直接维护复杂 Trie。vLLM serving 通常会把 token 序列切成固定大小的 block，再对每个 block 计算 prefix-aware hash。

Chunk Hash

用块级哈希实现前缀索引。

如果逐 token 建索引，元数据数量和查找开销会变大；如果把整个 prompt 建成一个 key，又无法做前缀复用。vLLM 采用折中方式：把 token 序列切成固定大小 block，然后按 block 计算前缀相关的 hash。

Prefix caching 的目标是：当多个请求共享相同 prompt prefix 时，复用已经计算好的 KV cache，减少 prefill 开销。

在 serving engine 内部，prefix cache 通常和 KV cache 的 block/page 管理绑定。例如 vLLM 的 PagedAttention 会把 KV cache 拆成固定大小的 block；block size 可以理解为一种 chunk size。SGLang 则使用 RadixAttention，通过 radix tree 管理 token prefix 和 KV cache 的复用。

如果把 KV cache 放到 Redis / CPU / Disk 这种外部存储中，一般不需要每个路由节点都维护完整 trie。更常见的方式是把 prompt tokens 按 chunk size 切分，对每个 chunk 计算 hash，然后用 hash 映射到对应的 KV cache object。新请求到来时，系统按 chunk 顺序查询 Redis，找到最长连续命中的 prefix，然后只对 miss 的后缀重新 prefill。

chunk size 是一个 tradeoff：

chunk size 小：

• prefix match 更精细
• cache hit token ratio 更高
• 但 object 数量更多，metadata 更多，Redis/network/serialization overhead 更大

chunk size 大：

• object 数量更少
• 存取和传输更高效
• 但 match 粒度更粗，尾部不满一个 chunk 的 prefix 无法复用，可能降低有效 hit rate

因此 chunk size 的优化不能只看 hit rate，而要综合看。本质目标是最大化：节省的 prefill compute - 额外的 cache lookup / transfer / management overhead