算法分析与设计

Appearance

6.5 LLM 与动态规划的同构性——记忆化的现代重生 ​

问题情境：KV-Cache 的效率之谜 ​

推理慢的困境 ​

2026 年，研究员 Alice 在使用 LLM 时遇到一个问题：

场景：用户问了多个相关问题，如：

  • Q1："什么是动态规划？"
  • Q2："动态规划的核心思想是什么？"
  • Q3："动态规划和分治的区别是什么？"

每次回答，LLM 都要重新计算整个 context（包括 Q1、Q2 的内容）。

问题：Q3 的推理时间是 Q1 + Q2 + Q3 的总时间，越来越慢。

Alice 想："能不能缓存已计算的部分，避免重复计算？"

KV-Cache 的解决方案 ​

Alice 查阅文献，发现 KV-Cache 技术：

核心思想：缓存已计算的 Key-Value 向量，下次推理时直接复用。

效果：Q3 的推理时间只计算新增部分，不再重复计算 Q1 和 Q2。

效率提升：3 倍加速（假设 Q1、Q2、Q3 长度相同）。

困惑：这不就是 DP 的记忆化吗？ ​

Alice 想起动态规划的记忆化：

  • Fibonacci：缓存 fib(k)，避免重复计算
  • KV-Cache：缓存 token 的 K-V 向量，避免重复计算

困惑：KV-Cache 和 DP 记忆化的条件是否相同？什么情况下缓存有效？

同构的发现 ​

Alice 继续思考，发现两者的共同条件：

DP 记忆化KV-Cache共同条件
子问题重叠 → 同一 fib(k) 被多次调用Prefix reuse → 同一前缀被多次查询缓存复用的必要性
参数有限 → fib(k) 的 k ∈ [0, n]Token 有限 → token 数固定缓存空间可控
DAG 依赖 → fib(k) 依赖 fib(k-1), fib(k-2)Token DAG → token 依赖前缀 token依赖关系 DAG

核心洞察：这不是类比，而是同构——同一计算思想的不同实例化。

直观思路：从 DP 到 KV-Cache 的映射 ​

四对核心映射 ​

DP 概念LLM 对应映射关系
记忆化KV-Cache缓存已计算结果，避免重复
子问题图Token DAG依赖关系 DAG
最优子结构Markov 假设状态最优不依赖路径历史
状态设计Prompt 设计影响推理效率

映射详解 ​

1. 记忆化 ↔ KV-Cache ​

DP 记忆化：

  • 第一次计算 fib(k)，存入 memo[k]
  • 后续调用 fib(k)，直接返回 memo[k]

KV-Cache：

  • 第一次计算 token t 的 K-V 向量，存入 cache
  • 后续推理时，直接复用 cache 中的 K-V 向量

共同条件：

  • 子问题重叠 → prefix reuse
  • 参数有限 → token 数有限

2. 子问题图 ↔ Token DAG ​

DP 子问题图：

  • 节点：子问题 fib(k)
  • 边：fib(k) → fib(k-1), fib(k) → fib(k-2)
  • DAG（无环）

Token DAG：

  • 节点：token t
  • 边：token t 依赖前缀 token（attention）
  • DAG（无环，因为 attention 只看之前的 token）

共同性质：DAG 依赖关系 → 可以按拓扑序计算。

3. 最优子结构 ↔ Markov 假设 ​

DP 最优子结构：

  • 子问题最优 → 整体最优
  • 例如：最短路径的子路径最优

LLM Markov 假设：

  • 状态最优不依赖路径历史
  • 例如：ToT 的分支独立评估

共同前提：状态之间的独立性。

4. 状态设计 ↔ Prompt 设计 ​

DP 状态设计：

  • 状态维度影响复杂度
  • 状态太少 → 无法正确刻画子问题
  • 状态太多 → 空间爆炸

Prompt 设计：

  • Prompt 长度影响推理效率
  • Prompt 太短 → 信息不完备
  • Prompt 太长 → 计算成本高

共同权衡：维度与效率的平衡。

规范定义：KV-Cache 的数学模型 ​

KV-Cache 的本质 ​

定义：KV-Cache 是 LLM 推理时缓存已计算的 Key-Value 向量的机制。

公式化：

设 token 序列为 t_1, t_2, ..., t_n。

  • Key 向量：K_i = f_K(t_i)
  • Value 向量：V_i = f_V(t_i)
  • Attention：Attention(t_i) = softmax(K_j · K_i / √d) · V_j for j < i

KV-Cache：存储 (K_j, V_j) for j ∈ [1, i-1]，避免重新计算。

Prefix Reuse 的条件 ​

定义：Prefix reuse 是多个推理请求共享相同前缀 token。

示例：

  • Request 1："什么是动态规划？" → Prefix: "什么是动态规划？"
  • Request 2："什么是动态规划？核心思想是什么？" → Prefix: "什么是动态规划？"（相同）

KV-Cache 有效条件：

  • Prefix 相同 → K-V 向量相同 → 可以复用
  • Prefix 不同 → K-V 向量不同 → 不能复用

KV-Cache 的复杂度分析 ​

无 KV-Cache：

  • 每次推理：计算所有 token 的 K-V 向量
  • 时间：O(n · d²)，n 是 token 数，d 是向量维度

有 KV-Cache：

  • 只计算新 token 的 K-V 向量
  • 时间：O((n - m) · d²)，m 是已缓存 token 数

效率提升：n → n - m，节省 m 的计算量。

算法实现：KV-Cache 策略 ​

简化 KV-Cache 模型 ​

python
class KVCache:
    def __init__(self):
        self.keys = []
        self.values = []
    
    def append(self, key, value):
        """添加新 token 的 K-V 向量"""
        self.keys.append(key)
        self.values.append(value)
    
    def get_prefix_cache(self, length):
        """获取前缀 token 的 K-V 向量"""
        return self.keys[:length], self.values[:length]
    
    def reuse_prefix(self, prefix_tokens, new_tokens):
        """复用前缀，只计算新 token"""
        prefix_len = len(prefix_tokens)
        prefix_keys, prefix_values = self.get_prefix_cache(prefix_len)
        
        # 只计算新 token 的 K-V 向量
        for token in new_tokens:
            key = compute_key(token)
            value = compute_value(token)
            self.append(key, value)
        
        return prefix_keys + self.keys[prefix_len:], 
               prefix_values + self.values[prefix_len:]

Prefix Reuse 检测 ​

python
def detect_prefix_reuse(requests):
    """检测多个请求的共享前缀"""
    prefixes = {}
    for request in requests:
        # 找最长共享前缀
        max_prefix_len = 0
        for cached_prefix in prefixes:
            if request.startswith(cached_prefix):
                max_prefix_len = len(cached_prefix)
                break
        
        # 新 token 部分
        new_part = request[max_prefix_len:]
        prefixes[request] = {
            'reuse_len': max_prefix_len,
            'new_tokens': new_part
        }
    
    return prefixes

正确性分析：KV-Cache 何时有效？ ​

KV-Cache 有效条件 ​

条件 1：Prefix reuse 存在。

若所有请求的 prefix 都不同，KV-Cache 无效——每次都要重新计算。

类比 DP：若无子问题重叠，记忆化无效——每次子问题参数不同。

条件 2：缓存空间足够。

KV-Cache 需存储大量 K-V 向量，内存限制。

类比 DP：记忆化需要 memo 表，空间 O(子问题数)。

条件 3：Token 依赖 DAG。

Token 的 attention 只看之前的 token，形成 DAG。

类比 DP：子问题图是 DAG，保证计算顺序正确。

KV-Cache 失效案例 ​

案例 1：完全不同的请求。

每次请求的 prefix 不同，无 reuse。

类比 DP：无子问题重叠（如 Quicksort）。

案例 2：缓存溢出。

Token 数太多，内存不够存储所有 K-V 向量。

类比 DP：状态空间爆炸（如 TSP）。

复杂度分析与优化 ​

KV-Cache 空间复杂度 ​

空间：O(n · d)，n 是 token 数，d 是向量维度。

优化：

  • 状态压缩（类似 DP 的状态压缩）：只缓存关键 token
  • Quantization（量化）：降低向量精度，减少空间

KV-Cache 时间复杂度 ​

无 KV-Cache：O(n · d²) 每次推理。

有 KV-Cache：O((n - m) · d²)，m 是 reuse token 数。

效率提升：m 越大，效率越高。

反例与变式 ​

反例 1：无 Prefix Reuse ​

场景：每个请求的 prefix 都不同。

KV-Cache 策略：缓存无效。

类比 DP：无子问题重叠 → 记忆化无效。

反例 2：Token 依赖非 DAG ​

场景：某 LLM 设计允许 token 看之后的 token（非因果 attention）。

问题：Token 依赖有环，无法按拓扑序计算。

类比 DP：子问题图有环 → 无法用 DP。

变式 1：动态 KV-Cache 管理 ​

场景：缓存空间有限，需要动态丢弃部分 K-V 向量。

策略：

  • LRU（最近最少使用）：丢弃最久未用的缓存
  • 关键 token 优先：保留对推理影响大的 token

类比 DP：滚动数组，只保留必要状态。

变式 2：Batch 推理优化 ​

场景：多个请求同时推理，共享 prefix。

策略：将共享 prefix 的请求 batch 处理，一次计算共享部分。

类比 DP：批量计算共享子问题。

LLM 推理策略的 DP 视角 ​

CoT（Chain-of-Thought） ​

类比：线性 DP（无分支）。

局限：一步错全错（无回溯）。

类比 DP：递推式无分支，依赖顺序固定。

ToT（Tree-of-Thought） ​

类比：回溯 + 记忆化。

局限：评估函数依赖人设计。

类比 DP：最优子结构需要人验证。

GoT（Graph-of-Thought） ​

类比：DAG 推理。

局限：思想聚合需要启发式。

类比 DP：子问题图 DAG，状态聚合。

常见错误诊断 ​

错误 1：误以为 KV-Cache 对所有请求有效 ​

澄清：需要 prefix reuse 条件。

错误 2：忽略 Token 依赖 DAG ​

澄清：若 token 依赖非 DAG（如双向 attention），KV-Cache 策略需调整。

错误 3：缓存管理不当 ​

澄清：缓存空间有限，需要动态丢弃策略（类似滚动数组）。

练习 ​

基本理解 ​

  1. 概念解释：KV-Cache 和 DP 记忆化的共同条件是什么？

  2. 映射分析：解释"子问题图 ↔ Token DAG"的映射关系。

  3. 画图验证：画出 Token DAG 的结构，类比 Fibonacci 子问题图。

方法应用 ​

  1. Prefix Reuse 检测：实现 prefix reuse 检测算法。

  2. KV-Cache 管理策略：设计动态 KV-Cache 管理策略（如 LRU）。

  3. 效率计算：计算有/无 KV-Cache 的推理时间对比。

错误诊断 ​

  1. 诊断失效：给定一个无 prefix reuse 的场景，分析 KV-Cache 失效原因。

  2. DAG 破坏：如果 token 依赖非 DAG，会发生什么问题？

  3. 缓存溢出：缓存空间不够时，如何管理？

方案比较 ​

  1. CoT vs ToT vs GoT：对比三种推理策略的 DP 对应。

  2. KV-Cache vs 无缓存：对比两种策略的效率差异。

  3. 动态管理 vs 固定缓存：对比两种缓存管理策略。

开放设计 ​

  1. 新缓存策略设计：设计一个基于 DP 思维的 KV-Cache 优化策略。

  2. 推理复杂度分析：分析 ToT 的推理复杂度，类比回溯。

  3. Prompt 设计优化：基于状态设计思维，优化 Prompt 结构。

综合应用 ​

  1. 真实场景分析：分析实际 LLM 推理场景的 prefix reuse 率。

  2. 推理优化方案：设计 LLM 推理优化方案，组合 KV-Cache 和 batch 推理。

  3. 综合挑战：设计一个 Agent，动态选择 KV-Cache 管理策略。

思考题 ​

为什么 KV-Cache 和 DP 记忆化同构？

因为共同条件：

  • 子问题重叠 → prefix reuse（缓存必要性）
  • 参数有限 → token 有限（空间可控）
  • DAG 依赖 → token DAG（计算顺序）

如何识别 KV-Cache 有效模式？

类比 DP 的子问题重叠识别：

  • 检测 prefix reuse（多个请求共享前缀）
  • 计算缓存复用率
  • 设计缓存策略（类似记忆化）

KV-Cache 的局限？

  • 需要 prefix reuse 条件
  • 缓存空间有限
  • Token 依赖必须是 DAG

总结：DP 记忆化 ↔ KV-Cache 同构，理解 DP → 理解 LLM 推理优化。但识别有效模式需要人的判断——这是机器做不了的。

参考文献：

  • Yao S, Yu D, Zhao J, et al. Tree of Thoughts[C]//NeurIPS. 2023.
  • Besta M, et al. Graph of Thoughts[C]//AAAI. 2024.
  • Crystal-KV. arXiv 2026-01.
  • Cormen T H, et al. Introduction to Algorithms[M]. 4th ed. MIT Press, 2022. Chapter 15.

新时代的算法课程