Skip to content

24. Prefix Cache Matching and Reuse | Prefix Cache 匹配与复用 ​

难度: Hard | 环境: CPU 主线 | 标签: 推理优化, KV Cache, Prefix Cache | 目标人群: 理解注意力与 KV 缓存的学习者

🚀 云端运行环境

本章节的实战代码可以点击以下链接在免费 GPU 算力平台上直接运行:

Open In ColabOpen In Studio (国内推荐:魔搭社区免费实例)


本节导读 ​

许多请求会共享系统提示词、工具说明或多轮历史的开头。若每次都重新执行预填充,这段相同输入对应的 KV Cache 会被重复计算;前缀缓存的任务是识别连续共享前缀,并让后续请求直接复用已有状态。

本节沿着“登记 → 最长匹配 → 复用账本 → 写回新状态”理解前缀缓存。从中区分匹配到的词元范围、实际可跳过的计算,以及仍被缓存占用的容量。

关键词: 前缀缓存, 最长前缀匹配, 缓存复用

运行环境 ​

  • 基础练习: 使用 BASE-CPU,运行本页题目与测试。

前置阅读 ​

先理解 KV Cache 如何保存已处理词元的状态,再观察多个请求为何只能复用从开头连续相同的输入。

Step 1:共享前缀为什么值得复用 ​

预填充(Prefill)处理输入词元并形成键值缓存(KV Cache)。在模型权重、适配器、位置编号、缓存表示相同且权限允许共享时,若多个请求从开头开始拥有连续相同的词元,这一段状态可以登记到前缀缓存;后续请求命中后不必再次计算。第一个不一致词元之后的内容是本次仍需处理的后缀。

概念它在请求路径中的含义本次请求如何处理
请求输入可能包含重复的系统提示词、工具说明或历史上下文与已登记路径比较
共享前缀从请求开头连续相同的词元区间复用对应 KV Cache 状态
未命中后缀从第一个不一致词元开始的剩余内容继续预填充并产生新状态
新状态本次后缀对应的新增 KV Cache写回前缀缓存或进入解码

前缀身份、对象匹配与后缀计算

Step 2:最长前缀匹配如何确定复用范围 ​

最长公共前缀描述两个序列从开头相同的范围;实际可复用长度还取决于哪些缓存对象已经登记并驻留。若仅登记 [1,2,3],请求 [1,2,9] 虽有两个公共词元,本页按完整对象登记的模型仍返回零;另行登记 [1,2] 后才可以命中两个。中间子串相同不构成前缀命中。

prompt=reusable_prefix+suffix

上式表示输入序列的拼接,而非数值相加。匹配确定候选范围后,还需确认对应 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,词元数守恒账本与空输入
python
from typing import List, Sequence, Tuple
python
class 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}

测试 ​

python
# 机制测试:按输入契约、登记去重、最长命中、请求拆分和复用账本分别定位问题。
# 下面使用按机制拆分的测试入口。
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

先完成题目并运行测试,再展开参考代码。











参考代码与解析 ​

代码 ​

python
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 数守恒。

相关阅读 ​

接着把完整前缀对象组织成压缩树,并用真实服务核对命中与首词元延迟。

Released under the MIT License.