24. Prefix Cache Matching and Reuse | Prefix Cache 匹配与复用
难度: Hard | 环境: CPU 主线 | 标签: 推理优化, KV Cache, Prefix Cache | 目标人群: 理解注意力与 KV 缓存的学习者
🚀 云端运行环境
本章节的实战代码可以点击以下链接在免费 GPU 算力平台上直接运行:
本节导读
许多请求会共享系统提示词、工具说明或多轮历史的开头。若每次都重新执行预填充,这段相同输入对应的 KV Cache 会被重复计算;前缀缓存的任务是识别连续共享前缀,并让后续请求直接复用已有状态。
本节沿着“登记 → 最长匹配 → 复用账本 → 写回新状态”理解前缀缓存。从中区分匹配到的词元范围、实际可跳过的计算,以及仍被缓存占用的容量。
运行环境
- 基础练习: 使用 BASE-CPU,运行本页题目与测试。
前置阅读
先理解 KV Cache 如何保存已处理词元的状态,再观察多个请求为何只能复用从开头连续相同的输入。
- Part 01 · 11. KV Cache and Memory Growth | KV Cache 与显存增长
- Part 02 · 22. vLLM PagedAttention | vLLM 分页注意力
Step 1:共享前缀为什么值得复用
预填充(Prefill)处理输入词元并形成键值缓存(KV Cache)。在模型权重、适配器、位置编号、缓存表示相同且权限允许共享时,若多个请求从开头开始拥有连续相同的词元,这一段状态可以登记到前缀缓存;后续请求命中后不必再次计算。第一个不一致词元之后的内容是本次仍需处理的后缀。
| 概念 | 它在请求路径中的含义 | 本次请求如何处理 |
|---|---|---|
| 请求输入 | 可能包含重复的系统提示词、工具说明或历史上下文 | 与已登记路径比较 |
| 共享前缀 | 从请求开头连续相同的词元区间 | 复用对应 KV Cache 状态 |
| 未命中后缀 | 从第一个不一致词元开始的剩余内容 | 继续预填充并产生新状态 |
| 新状态 | 本次后缀对应的新增 KV Cache | 写回前缀缓存或进入解码 |
Step 2:最长前缀匹配如何确定复用范围
最长公共前缀描述两个序列从开头相同的范围;实际可复用长度还取决于哪些缓存对象已经登记并驻留。若仅登记 [1,2,3],请求 [1,2,9] 虽有两个公共词元,本页按完整对象登记的模型仍返回零;另行登记 [1,2] 后才可以命中两个。中间子串相同不构成前缀命中。
上式表示输入序列的拼接,而非数值相加。匹配确定候选范围后,还需确认对应 K/V 的计算条件、驻留与访问权限;真实后端的可复用粒度可能不同。
| 机制量 | 含义 | 后续用途 |
|---|---|---|
| 命中长度 | 从请求开头连续命中的词元数 | 确定可复用状态范围 |
| 可复用前缀 | 已缓存且命中的前缀 | 跳过这段预填充 |
| 未命中后缀 | 首个不一致词元之后的剩余部分 | 产生本次新增状态 |
| 无命中 | 命中长度为零 | 整个输入仍需预填充 |
Step 3:用复用账本判断本次新增工作
命中不会让请求“没有计算”,而是把本次工作从完整输入缩为未命中后缀。记录命中词元、未命中词元和复用比例,才能估算减少的输入工作。完全命中也不自动意味着零首词元成本:若还缺少生成下一词元所需的分数,执行器仍有工作;实际跳过量要读取后端计数。
| 账本量 | 含义 | 还应与哪些证据一起查看 |
|---|---|---|
| 命中词元数 | 本次可复用的前缀长度 | 后端的 KV 占用和 TTFT |
| 未缓存词元数 | 仍需执行预填充的后缀长度 | 预填充耗时和吞吐 |
| 复用比例 | 命中词元数除以输入词元数 | 匹配工作负载下的命中率分布 |
| 新增状态 | 后缀计算后写入的 KV Cache | 驱逐、迁移与生命周期记录 |
Step 4:实现匹配、拆分与复用账本
本题的 PrefixCacheManager 用整数词元序列和完整登记对象演示匹配,不存储真实 K/V。你将完成输入检查、去重登记、最长有效命中、拆分与账本;测试区分“存在公共词元”与“已有可复用对象”。
| TODO / 函数 | 学习者完成的机制 | 必须满足的约束 | 测试证据 |
|---|---|---|---|
TODO 1:规范词元输入_normalize | 统一词元容器并校验整数输入 | 保持顺序;非法词元不能进入缓存索引 | 输入契约 |
TODO 2:登记共享前缀add_prefix | 登记非空且不重复的共享前缀 | 重复登记不增加索引条目 | 登记与去重 |
TODO 3:计算最长命中match_prefix | 从请求开头选择最长连续命中 | 中间子串不能算命中 | 最长命中与零命中 |
TODO 4:拆分请求输入split_prompt | 按命中长度拆出可复用前缀和未命中后缀 | 两段拼接后必须还原原输入 | 前缀/后缀契约 |
TODO 5:生成复用账本cache_stats | 统计命中、未命中和复用比例 | 空输入返回 0.0,词元数守恒 | 账本与空输入 |
from typing import List, Sequence, Tupleclass PrefixCacheManager:
"""登记完整前缀对象,计算逻辑复用范围;不存储真实 K/V。"""
def __init__(self):
self.cached_prefixes: List[Tuple[int, ...]] = []
def _normalize(self, tokens: Sequence[int]) -> List[int]:
"""转换词元容器,并拒绝非整数元素。"""
# ==========================================
# TODO 1:保持顺序并统一词元容器。
# ==========================================
# normalized = ??? # 按原顺序排列的词元列表。
raise NotImplementedError("请完成 TODO 1:normalized")
if any(not isinstance(token, int) for token in normalized):
raise TypeError('tokens 必须是整数序列')
return normalized
def add_prefix(self, prefix_tokens: Sequence[int]) -> None:
"""登记完整前缀对象,空对象失败,重复对象去重。"""
# ==========================================
# TODO 2:规范并登记完整前缀对象。
# ==========================================
# prefix = ??? # 规范化后的词元元组,保持输入顺序。
raise NotImplementedError("请完成 TODO 2:prefix")
if not prefix:
raise ValueError('prefix_tokens 不能为空')
if prefix not in self.cached_prefixes:
self.cached_prefixes.append(prefix)
def match_prefix(self, prompt_tokens: Sequence[int]) -> int:
"""返回与请求开头一致的最长完整登记对象长度。"""
prompt = self._normalize(prompt_tokens)
best_len = 0
for cached_prefix in self.cached_prefixes:
if len(cached_prefix) > len(prompt):
continue
# ==========================================
# TODO 3:判断完整对象是否匹配请求开头。
# ==========================================
# is_match = ??? # 当前完整对象与等长请求开头一致时为 True。
raise NotImplementedError("请完成 TODO 3:is_match")
if is_match:
best_len = max(best_len, len(cached_prefix))
return best_len
def split_prompt(self, prompt_tokens: Sequence[int]) -> Tuple[List[int], List[int], int]:
"""按命中长度拆分请求,保证两段拼接还原原输入。"""
prompt = self._normalize(prompt_tokens)
hit_len = self.match_prefix(prompt)
# ==========================================
# TODO 4:拆出复用前缀和待处理后缀。
# ==========================================
# reusable_prefix = ??? # 命中范围覆盖的请求开头。
# suffix = ??? # 命中边界之后的全部剩余词元。
raise NotImplementedError("请完成 TODO 4:reusable_prefix、suffix")
return reusable_prefix, suffix, hit_len
def cache_stats(self, prompt_tokens: Sequence[int]) -> dict:
"""返回逻辑复用账本,不将词元计数解释为实测性能。"""
prompt = self._normalize(prompt_tokens)
# ==========================================
# TODO 5:统计命中、未命中和词元复用比例。
# ==========================================
# hit_tokens = ??? # 完整对象提供的最长命中词元数。
# uncached_tokens = ??? # 仍需处理的输入词元数。
# reuse_ratio = ??? # 命中数占输入数的比例;空输入为 0.0。
raise NotImplementedError("请完成 TODO 5:词元复用账本")
return {'hit_tokens': hit_tokens, 'uncached_tokens': uncached_tokens, 'reuse_ratio': reuse_ratio}测试
# 机制测试:按输入契约、登记去重、最长命中、请求拆分和复用账本分别定位问题。
# 下面使用按机制拆分的测试入口。
def _prefix_cache_fixture():
manager = PrefixCacheManager()
manager.add_prefix([1, 2, 3])
manager.add_prefix([1, 2, 9])
manager.add_prefix([1, 2, 3])
return manager
def test_prefix_input_contract():
"""验证空前缀和非整数 token 会被拒绝。"""
manager = PrefixCacheManager()
for invalid_prefix in ([], [1, 'bad']):
try:
manager.add_prefix(invalid_prefix)
except (ValueError, TypeError):
pass
else:
raise AssertionError('空前缀或非整数 token 应被拒绝')
def test_prefix_registration_and_deduplication():
"""验证非空前缀登记以及重复前缀去重。"""
manager = _prefix_cache_fixture()
assert manager.cached_prefixes == [(1, 2, 3), (1, 2, 9)]
def test_longest_prefix_match():
"""验证只从 prompt 开头计算最长连续命中。"""
manager = _prefix_cache_fixture()
assert manager.match_prefix([1, 2, 3, 9]) == 3
assert manager.match_prefix([1, 2, 9, 8]) == 3
assert manager.match_prefix([1, 2, 0]) == 0
manager.add_prefix([1, 2])
assert manager.match_prefix([1, 2, 0]) == 2
assert manager.match_prefix([0, 1, 2, 3]) == 0
def test_prefix_suffix_split_and_stats():
"""验证 prefix/suffix 拆分和 token 级复用账本。"""
manager = _prefix_cache_fixture()
prefix, suffix, hit_len = manager.split_prompt([1, 2, 3, 9])
assert (prefix, suffix, hit_len) == ([1, 2, 3], [9], 3)
assert manager.cache_stats([1, 2, 3, 9]) == {'hit_tokens': 3, 'uncached_tokens': 1, 'reuse_ratio': 0.75}
assert manager.cache_stats([]) == {'hit_tokens': 0, 'uncached_tokens': 0, 'reuse_ratio': 0.0}
def test_prefix_cache_manager():
test_prefix_input_contract()
test_prefix_registration_and_deduplication()
test_longest_prefix_match()
test_prefix_suffix_split_and_stats()
print('✅ PrefixCacheManager 机制测试通过')
test_prefix_cache_manager()🛑 STOP HERE
先完成题目并运行测试,再展开参考代码。
参考代码与解析
代码
class PrefixCacheManager:
"""登记共享前缀,并计算一次请求可复用与仍需 Prefill 的 token 账本。
`cached_prefixes` 是逻辑索引;本题不实现真实 KV Tensor、物理 block 或淘汰策略。
"""
def __init__(self):
self.cached_prefixes: List[Tuple[int, ...]] = []
def _normalize(self, tokens: Sequence[int]) -> List[int]:
"""按原顺序转换词元容器,并拒绝非整数元素。"""
# TODO 1: 统一 token 表示,便于做前缀匹配
normalized = list(tokens)
if any(not isinstance(token, int) for token in normalized):
raise TypeError('tokens 必须是整数序列')
return normalized
def add_prefix(self, prefix_tokens: Sequence[int]) -> None:
"""登记非空完整前缀对象,相同对象只保留一次。"""
# TODO 2: 登记一个可复用的共享前缀
prefix = tuple(self._normalize(prefix_tokens))
if not prefix:
raise ValueError('prefix_tokens 不能为空')
if prefix not in self.cached_prefixes:
self.cached_prefixes.append(prefix)
def match_prefix(self, prompt_tokens: Sequence[int]) -> int:
"""选择与请求开头一致的最长完整登记对象。"""
# TODO 3: 返回 prompt 能命中的最长缓存前缀长度
prompt = self._normalize(prompt_tokens)
best_len = 0
for cached_prefix in self.cached_prefixes:
if len(cached_prefix) > len(prompt):
continue
is_match = prompt[:len(cached_prefix)] == list(cached_prefix)
if is_match:
best_len = max(best_len, len(cached_prefix))
return best_len
def split_prompt(self, prompt_tokens: Sequence[int]) -> Tuple[List[int], List[int], int]:
"""按命中边界拆分请求,保持词元顺序与数量守恒。"""
# TODO 4: 拆出可复用前缀和待处理 suffix
prompt = self._normalize(prompt_tokens)
hit_len = self.match_prefix(prompt)
reusable_prefix = prompt[:hit_len]
suffix = prompt[hit_len:]
return reusable_prefix, suffix, hit_len
def cache_stats(self, prompt_tokens: Sequence[int]) -> dict:
"""返回 token 级复用账本;不代表真实 KV 显存收益或吞吐。"""
# TODO 5: 统计命中、未命中与复用比例
prompt = self._normalize(prompt_tokens)
hit_tokens = self.match_prefix(prompt)
uncached_tokens = len(prompt) - hit_tokens
reuse_ratio = hit_tokens / len(prompt) if prompt else 0.0
return {'hit_tokens': hit_tokens, 'uncached_tokens': uncached_tokens, 'reuse_ratio': round(reuse_ratio, 4)}解析
TODO 1:统一 token 表示
- 把输入转换为保持顺序的整数 token 序列。非法 token 不能进入缓存索引,转换前后的 token 顺序不变。
- 输入契约测试覆盖合法序列、非法元素和空输入。
TODO 2:登记共享前缀
- 把非空前缀登记为可复用候选。相同前缀只登记一次,空前缀不进入索引。
- 登记与去重测试检查索引条目数。
TODO 3:返回最长连续命中长度
- 只接受完整登记对象与请求开头一致的情况,在这些对象中选最长者。中间偶然相同的 token 不能构成前缀命中。
- 测试用未登记的公共前缀与显式登记的短前缀作对照,检查复用粒度。
TODO 4:拆分请求
- 按命中长度拆出可复用前缀和未命中后缀。两段重新拼接后必须还原原 prompt。
- 完整命中、部分命中和零命中测试检查拆分结果。
TODO 5:生成复用账本
- 统计命中 token、未缓存 token 和复用比例。命中与未缓存 token 数之和等于 prompt 长度,空 prompt 的复用比例为零。
- 账本与空输入测试检查 token 数守恒。
相关阅读
接着把完整前缀对象组织成压缩树,并用真实服务核对命中与首词元延迟。
