Prefix Cache · LLM Glossary

与单请求 KV Cache 的边界

KV Cache在一个请求内部跨 decode step 保存历史状态。Prefix Cache 在不同请求或同一会话的后续请求之间识别相同 token prefix，让新请求跳过已缓存部分的 prefill，直接引用已有 KV blocks。

它优化重复 prefill 的计算与 TTFT，不减少该请求后续 decode 对历史 K/V 的读取，也不改变 attention 数学。没有重复 prefix、cache 已驱逐、模型状态不兼容或命中太短时，不会受益。

安全 cache identity 包含什么

最小 key 以 token ids 为核心，还要纳入任何会改变 KV 的状态：

tokenizer/chat template/special-token 产生的完整 ids；
model/checkpoint revision、权重 hash、dtype/量化、LoRA adapter id/version与位置编码配置；
LoRA/adapter、prompt tuning 或其他修改层输出的状态；
multimodal inputs、tool schema 等被编码进模型状态的内容；
block 的 parent prefix identity，防止同一 token block 出现在不同历史后被误复用。

一个 block-chain hash：

h_i=H(h_{i-1},\ \text{token\_block}_i,\ \text{model state})

只比较当前 4 个 token 的 hash 不够，因为相同局部 block 在不同先前 context 下的 KV 不同。

Block 对齐、命中与 copy-on-write

与 PagedAttention 配合时，prefix cache 通常以完整 physical blocks 共享。block size 为 $P$ ，最长完整 block 命中 $n$ 个时，复用 token 数为 $nP$ ；未满尾 block 是否可共享取决于实现，最稳妥设计只缓存 full blocks。

两条请求共享 physical block 后，block 是只读的。若某个分支需要修改尚未满的共享 block，runtime 必须分配私有副本（copy-on-write），更新引用计数，再写新 KV；否则会破坏另一请求状态。

可运行身份与 COW 实验

import hashlib,platform
BLOCK_SIZE=4

def block_hash(parent,token_block,model_revision,adapter):
    payload=parent+model_revision.encode()+b"\0"+adapter.encode()+b"\0"
    payload+=b"".join(t.to_bytes(4,"little") for t in token_block)
    return hashlib.sha256(payload).digest()

def prefix_chain(token_ids,model_revision="model-v1",adapter="none"):
    parent,hashes=b"root",[]
    for start in range(0,len(token_ids)-BLOCK_SIZE+1,BLOCK_SIZE):
        parent=block_hash(parent,token_ids[start:start+BLOCK_SIZE],model_revision,adapter)
        hashes.append(parent)
    return hashes

def longest_hit(query,cached):
    count=0
    for q,c in zip(query,cached):
        if q!=c: break
        count+=1
    return count*BLOCK_SIZE

def copy_on_write(block,refcount):
    return (list(block),refcount-1) if refcount>1 else (block,refcount)

def main():
    a=[256,257,10,11,12,13,14,15,16]
    b=[256,257,10,11,12,13,99,98]
    chain_a,chain_b=prefix_chain(a),prefix_chain(b)
    hit=longest_hit(chain_b,chain_a)
    assert hit==4 and prefix_chain(a,adapter="lora-x")!=chain_a
    shared=a[:BLOCK_SIZE]
    private,remaining=copy_on_write(shared,2); private[0]=999
    assert shared[0]==256 and private[0]==999 and remaining==1
    print(f"python={platform.python_version()} block_size={BLOCK_SIZE}")
    print(f"request_a={a} request_b={b}")
    print(f"full_block_hashes_a={[h.hex()[:12] for h in chain_a]}")
    print(f"full_block_hashes_b={[h.hex()[:12] for h in chain_b]}")
    print(f"longest_cached_prefix_tokens={hit}")
    print(f"partial_tail_a={a[len(chain_a)*BLOCK_SIZE:]}")
    print(f"copy_on_write_shared_first={shared[0]} private_first={private[0]}")

if __name__=="__main__": main()

完整文件位于 examples/prefix_cache_reference.py。本例两个请求的第一个 block hash 相同，第二个不同，因此命中 4 tokens；A 的尾部 token 16 不进入 full-block chain；adapter 变化使身份不同；COW 后共享 block 保持 256，私有副本变为 999。

成本与失败场景

Prefix Cache 增加 hash/index、引用计数、LRU/eviction、metadata 和 cache 容量竞争。命中率必须结合命中长度和节省的 prefill FLOPs 报告；“请求命中”但只命中一个很短 block，TTFT 收益可能被 lookup/scheduling 遮住。

常见失败场景：

多租户不应越权共享敏感 prefix，cache key/隔离策略错误会泄漏状态或侧信道；
热 prefix blocks 占用 KV 容量，挤压 active decode，导致 preemption 或更低并发；
位置编码/滑动窗口/adapter 不兼容却误命中，产生静默错误；
cache 驱逐导致性能抖动，命中率随工作集变化；
把 prefix 命中时间从 TTFT 中减掉，却不计 lookup、block pinning 与网络/跨实例取回。

上下游关系

Tokenizer/Chat Template定义 token ids 与 model-facing prefix，不同模板会改变 key。
KV Cache定义被复用的层级状态；Prefix Cache 把其生命周期扩展到请求之间。
PagedAttention提供可共享 physical blocks、block table 与 copy-on-write 基础。
Continuous Batching的 scheduler 决定命中 blocks 如何计入 token/KV budget、何时 pin/evict。

与单请求 KV Cache 的边界

安全 cache identity 包含什么

Block 对齐、命中与 copy-on-write

可运行身份与 COW 实验

成本与失败场景

上下游关系

参考资料