推理：KV Cache、解码与推理时计算

所属： 训练推理平台层。本页边界： 固定权重后，模型怎样逐 token 生成、缓存历史并用更多计算提升答案。

#核心公式

M_{\mathrm{KV}}\approx 2BLnH_{\mathrm{kv}}d_h b

#符号说明

符号	含义	单位/条件
$M_{\mathrm{KV}}$	所有活跃序列的 KV Cache 近似占用	Byte
$2$	每层同时缓存 Key 和 Value 两组张量	固定因子
$B$	并发序列数	正整数
$L$	Transformer 层数	正整数
$n$	每条序列当前已缓存的 token 数	正整数
$H_{\mathrm{kv}}$	每层 KV 头数	正整数
$d_h$	每个注意力头的维度	个元素
$b$	每个缓存元素的存储字节数	Byte
$S,G$	后文中的输入 prompt 长度与生成长度	token 数
$T_{\mathrm{queue}},T_{\mathrm{prefill}},T_{\mathrm{decode}}$	排队、预填充、逐步解码时间	s
$T_{\mathrm{request}},\ t$	单请求总时延、当前解码步编号	s、正整数
$p$	单次采样的成功率	$[0,1]$
$N$	采样次数或候选数	正整数

公式假设每层、每序列长度相同，并忽略分页元数据、内存对齐与碎片。

#技术要点

prefill 并行处理 prompt；decode 每步生成一个 token。
KV Cache 避免重复计算旧 token 的 key/value。前缀共享通过 Radix Tree 实现全局缓存复用，配合页级管理可将复用粒度降到单个 token。
temperature、top-p、min-p 改变采样策略；min-p 在高温度下比 top-p 更平衡创造性与连贯性，已被主流推理框架采用。
自回归解码存在固有并行性，部分回答片段可并行生成；ASPD 在通用任务上实现最高 3.19 倍加速且质量损失小于 1%。
CoT、best-of-N、搜索和 verifier 用更多推理时计算换成功率。自验证能力随候选池增大而增强，这一反直觉现象是推理时扩展可扩展性的关键机制。
并行协调推理（PaCoRe）通过消息传递架构将推理时计算扩展到约两百万 token 的有效规模，使 8B 模型在 HMMT 2025 上达到 94.5%，超越 GPT-5 的 93.2%。

#原理与演进

#Prefill、Decode 与 KV Cache

Prefill 一次处理输入 prompt，产生首个输出 token，同时为各层建立历史 K/V。
Decode 每步只计算新增 token 的 Q/K/V；Q 与缓存的历史 K/V 做注意力，避免重复跑过往 token。自回归概率分解见概率语言模型。
页首公式给出近似 KV 占用： $B$ 是并发序列数， $L$ 是层数， $n$ 是已缓存 token 数， $H_{\mathrm{kv}}$ 是 KV 头数， $d_h$ 是每头维度， $b$ 是每元素字节数。GQA/MQA 降低 $H_{\mathrm{kv}}$ ；原理见Transformer。

#解码算法改变什么

方法	规则	收益	代价
贪心	每步取最大概率	确定、便宜	容易局部最优
温度 / top-p	重标定并截断分布后采样	多样性可控	高温度下连贯性下降
min-p	基于 top token 概率动态调整截断阈值	高温度下兼顾创造性与连贯性	需调节基础阈值
Beam search	保留多条高分前缀	搜索更广	更多计算，可能偏向模式化回答
投机解码	小模型提议，大模型并行验证	减少串行等待	提议质量差时收益低
并行解码	同时生成多个可并行 token	减少解码步数	依赖模型固有并行结构

#推理时计算的演进

单条直接回答 → 多条候选再选择 → 搜索/验证器反馈 → 并行协调推理。额外计算可提高某些可验证任务成功率，却不能把错误验证器变成正确监督；best-of- $N$ 的收益必须连同 $N$ 倍候选成本报告。请求级批处理与延迟权衡在服务层。

#1. 自回归推理的时序瓶颈

输入长 $S$ 、输出长 $G$ 。Prefill 对已有 token 可并行计算，通常更偏计算密集；decode 的第 $t$ 步依赖第 $t-1$ 步结果，不能将整个输出一次并行算完。无 KV 缓存时每步重复处理历史前缀；有缓存后只追加新 K/V，但每步仍需读取历史 KV，注意力读取量随已生成长度增长。

简化延迟：

T_{\mathrm{request}}\approx T_{\mathrm{queue}}+T_{\mathrm{prefill}}(S)+\sum_{t=1}^{G}T_{\mathrm{decode}}(S+t).

因此长 prompt 首 token 慢、长输出总延迟长，是不同瓶颈。TTFT（首 token 时间）与 TPOT（输出 token 间隔）须分别报告。服务层讨论并发调度。

#1.1 Prefill 与 Decode 分离部署

Prefill 是计算密集型（大批量矩阵乘），Decode 是带宽密集型（逐 token 读取权重和 KV）。两者的硬件需求、批处理策略和延迟目标截然不同。Prefill-Decode 分离部署将两类请求分配到不同的硬件实例上，各自优化资源利用率。分离后可以独立扩缩容：在 prefill 密集场景（如长文档摘要）增加 prefill 实例，在 decode 密集场景（如多轮对话）增加 decode 实例。代价是需要在 prefill 和 decode 实例之间传输 KV Cache，引入额外的网络开销和调度复杂度。

#2. KV Cache 的复用、压缩与分页

KV Cache 将注意力推理的时间复杂度从二次降为线性，但也引入了内存管理、复用和压缩的挑战。以下三类技术分别解决不同层面的问题。

#2.1 前缀共享与 Radix Tree

多请求共享相同系统提示时，可共享或复用前缀 KV，减少重复 prefill。基于 Radix Tree 的系统实现全局前缀共享：将不同请求的 token 序列组织为一棵树，相同前缀路径上的 KV Cache 只需计算一次。当新请求到来时，系统沿树匹配最长公共前缀，复用已缓存的 KV，仅对未匹配的后缀执行 prefill。Radix Tree 支持动态节点删除，当某个前缀不再被任何活跃请求引用时自动释放。

与页级管理结合后，前缀共享的粒度可以降低到单个 token 级别，同时保持内存的非连续分配。这一机制对系统提示占比高的场景（如多轮对话、RAG 固定模板）效果显著。

#2.2 量化与紧凑编码

KV Cache 量化通过降低每元素位宽来减少容量和带宽，但引入注意力误差。主要方法包括：

分组量化：对 KV Cache 按组应用 4-bit 量化，无需额外 I/O 开销。
逐通道/逐 token 量化：Kivi 等方法对每个通道或每个 token 独立计算量化参数，比全局量化保留更多信息。
混合精度：Atom 等方法对重要 token 使用高精度、对不重要 token 使用低精度，在相同显存预算下保留更多有效信息。
层间相似性压缩：MiniCache 利用相邻层的 KV 相似性进行跨层压缩。
紧凑编码：CacheGen 使用自定义张量编码器将 KV Cache 压缩为紧凑比特流，以最小的解码开销节省带宽。

KV Cache 的丢弃策略也是一个独立方向。与压缩不同，丢弃策略根据注意力权重动态决定哪些 KV 对可以被移除，在固定显存预算下保留更多有效信息。

#2.3 分页、卸载与分层管理

分页 KV Cache 借鉴操作系统虚拟内存机制，将 KV Cache 以固定大小的页为单位分配，允许非连续存储。这消除了连续大块预留导致的内存碎片，提高 GPU 利用率。

卸载将不活跃的 KV Cache 转移到 CPU 内存，释放 GPU 显存。按层卸载的策略在需要某层 KV 时再加载，将显存-带宽权衡从容量扩展到带宽。

分层分配结合分页和卸载，根据 KV 的活跃程度将其分配到不同存储层级。缓存仅对重复访问有效；一次性流式数据应优化顺序读取。

#2.4 三类技术的分工

技术类别	解决的问题	代表方法	核心代价
复用（Radix Tree、页级管理）	避免重复计算相同前缀	PagedAttention、vLLM	非连续布局的访问开销
压缩（量化、紧凑编码）	减少每元素字节数	分组量化、CacheGen	注意力误差或编解码开销
丢弃（注意力筛选）	移除低重要性 KV	基于注意力权重的动态丢弃	可能丢失远距信息

三者分别解决重复计算、每元素大小、有效信息密度，不要混为一种算法。

#3. 采样策略的演进

温度变换见式（1）：式（2）使分布更尖锐，式（3）增加随机性。Top- $p$ 保留最小集合 $V_p$ 使式（4）成立，再重归一化。

式（1）：

p_T(i)=\exp(z_i/T)/\sum_j\exp(z_j/T)

式（2）：

T<1

式（3）：

T>1

式（4）：

\sum_{i\in V_p}p_T(i)\ge p

#3.1 min-p 采样

Top-p 在高温度下面临一个结构性缺陷：截断阈值固定为累计概率 $p$ ，当模型置信度低（分布平坦）时，top-p 可能保留大量低概率 token，导致输出不连贯；当模型置信度高（分布尖锐）时，top-p 可能截断过少或过多。

min-p 采样通过将截断阈值与模型置信度解耦来解决这一问题。其核心机制是使用 top token 的概率作为缩放因子，动态调整截断阈值：

\text{threshold} = p_{\text{base}} \cdot \max_i p(i)

只有当某个 token 的概率超过 $p_{\text{base}} \times p_{\text{max}}$ 时才被保留。当模型高度自信时（ $p_{\text{max}}$ 接近 1），阈值较高，只保留少量高概率 token；当模型不确定时（ $p_{\text{max}}$ 较低），阈值相应降低，保留更多候选 token。这种自适应行为使 min-p 在高温度下仍保持连贯性，在低温度下不损失多样性。

在 GPQA、GSM8K 和 AlpacaEval Creative Writing 基准上，min-p 在 Mistral 和 Llama 3 系列模型（1B 到 123B 参数）上均优于 top-p，人类评估也显示出对 min-p 的明显偏好。min-p 已被 Hugging Face Transformers、vLLM 等主流推理框架采用。

#3.2 采样与搜索的边界

温度、top-p、min-p 调整输出多样性，不能把事实错误修复为正确知识。Beam search 近似最大化下式所示的序列对数概率，并不直接最大化人类质量。Best-of- $N$ 用评分器从 $N$ 个完整候选中选择，评分器误差会被更大 $N$ 放大。

\sum_t\log p(y_t\mid y_{<t},x)

#4. 投机解码的改进与并行解码

#4.1 投机解码的核心机制

投机解码：小模型提议多 token → 目标模型并行给出对应条件概率 → 按接受/拒绝规则修正。正确规则可保持目标模型采样分布；简单地“只接受相同 argmax”不等价。收益取决于接受率、草稿模型开销和目标模型并行效率。

#4.2 草稿模型的结构优化

草稿模型的提议质量直接决定投机解码的加速比。Gumiho 的理论分析表明，草稿序列中早期 token 比后期 token 更重要——早期错误会导致整个后续序列被拒绝。基于这一洞察，Gumiho 采用混合架构：早期草稿头使用完整的 Transformer 架构（串行配置）以提升准确性，后期草稿头使用轻量级 MLP 并行运行以提高效率。

DREAM 针对视觉-语言模型（VLM）的投机解码，引入三项创新：基于交叉注意力的特征注入机制（将目标模型的中间特征注入草稿模型）、基于注意力熵的自适应中间特征选择、以及视觉 token 压缩以减少草稿模型延迟。在 LLaVA、Pixtral 等 VLM 上实现最高 3.6 倍加速。

LongSpec 针对长上下文场景，在五个长上下文理解数据集上实现最高 3.26 倍加速，在 AIME24 长推理任务上实现 2.25 倍墙钟时间缩减。

#4.3 并行解码：利用自回归模型的固有并行性

自回归解码的串行特性是推理延迟的主要来源，但模型输出中存在固有并行性——某些回答片段（如列表项、枚举内容、结构化输出）在语义上可以并行生成，而非严格逐 token 依赖。

ASPD（Adaptive Serial-Parallel Decoding） 通过分析自回归模型输出，自动提取和验证可并行结构。在通用任务中，可并行片段占比达到 70.2%；在数学任务中为 30.6%。ASPD 的混合解码引擎支持串行和并行模式之间的无缝切换，同时维护可复用的 KV Cache。在 Vicuna Bench 上实现最高 3.19 倍加速（平均 1.85 倍），响应质量与自回归模型的差异在 1% 以内。

dParallel 针对扩散语言模型（dLLM），通过 certainty-forcing 蒸馏训练模型在掩码 token 上更快达到高确定性，从而解锁并行解码能力。在 LLaDA-8B-Instruct 上，GSM8K 解码步数从 256 降至 30（8.5 倍加速），MBPP 从 256 降至 24（10.5 倍加速），均无性能退化。

#5. 推理时计算的技术路线

直接回答（低计算、错误难纠）→ 思维链提示（分解中间步骤但可能自信地错）→ 多样本投票（减小随机采样方差但耗费 $N$ 倍）→ 过程/结果验证器选择（质量受验证器上限限制）→ 搜索或工具反馈（扩展探索但引入外部错误与成本）→ 并行协调推理（突破单条推理轨迹的上下文限制）。

#5.1 自验证的隐式扩展

采样式搜索涉及生成多个候选回答并选择最好的。一个反直觉的发现是：自验证能力随候选池增大而增强——候选池越大，验证器区分正确和错误回答的能力越强。这一现象被称为隐式扩展。

这一发现的方法论意义在于：验证器不需要从一开始就完美，只需在更大的候选池中相对更准确。实验表明，使用随机采样和直接自验证的最小化实现，在 Gemini v1.5 Pro 上即可将推理能力提升至超越 o1-Preview 的水平。在 AIME 考试中，自验证能够在不到 1% 的生成回答正确时挑出正确答案。

两个提升自验证能力的原则：（1）跨回答比较提供关于错误和幻觉位置的有用信号；（2）不同模型输出风格适用于不同上下文——思维链对推理有用但更难验证。

#5.2 自适应计算分配

传统推理时扩展均匀分配计算、使用固定采样策略、仅在重排序时应用验证。PRM 引导的自适应框架将推理视为迭代轨迹生成和选择：对每个问题，agent 运行多轮推理迭代，每轮可选地产生高层计划、选择推理工具集和计算策略，然后生成候选推理轨迹。过程奖励模型（PRM）作为统一控制信号——迭代内，步骤级 PRM 分数聚合以指导生成中的剪枝和扩展；迭代间，聚合的轨迹奖励用于选择最终回答。

在 MATH-500 上实现显著增益，在 AIME24 和 AMO-Bench 等更难基准上实现数倍提升。计算强度指标（惩罚浪费的生成和工具开销）表明，验证引导的分配将计算集中在高效用推理路径上。

#5.3 并行协调推理

PaCoRe（Parallel Coordinated Reasoning） 通过消息传递架构驱动推理时计算：每轮启动大量并行推理轨迹，将发现压缩为上下文受限的消息，综合这些消息以指导下一轮并最终产生答案。端到端使用大规模基于结果的强化学习训练，模型掌握 PaCoRe 所需的综合能力，可扩展到约两百万 token 的有效推理时计算而不超出上下文限制。

在 HMMT 2025 数学竞赛中，PaCoRe 使 8B 模型达到 94.5%，超越 GPT-5 的 93.2%。这一结果表明，通过并行协调而非单纯增加序列长度，推理时计算的规模可以突破单条推理轨迹的瓶颈。

#5.4 推理时计算的比较口径

比较直接回答、思维链、多样本投票或搜索，固定任务集后应画出“准确率—平均生成 token—P99 延迟”的三维关系。若方法 A 只在花费 10 倍 token 时高 2 个点，它不是在相同预算下的纯模型能力提升。可验证任务还需分别报告生成器和验证器的错误：验证器若误判，搜索越强可能越容易利用该误差。

设单次成功率为 $p$ ，若 $N$ 次独立采样且有完美选择器，至少一次成功率为 $1-(1-p)^N$ 。实际样本相关、验证器不完美，真实收益低于这一理想边界；必须报告成功率、token 数、延迟和验证器开销。

#6. 输出长度的成本不是常数

若当前缓存长度满足式（1），每步注意力需读与 $n_t$ 成比例的 KV；生成 $G$ 个 token 的历史读取量级约为式（2），忽略层数、头数和块复用。权重读取也随每步重复发生。因而将“生成 1000 token 的成本”简单写成“10 倍生成 100 token”只在部分近似区间成立；长对话时 KV 项会更显著。

式（1）：

n_t=S+t-1

式（2）：

\sum_{t=1}^{G}(S+t)=GS+G(G+1)/2

#7. 压缩历史与共享前缀的取舍

多用户共享相同系统提示时，可共享或复用前缀 KV，减少重复 prefill；但用户特定消息不能错误复用。历史摘要可缩短 prompt，却可能丢失事实、时间和约束；应保留来源与关键状态，避免让摘要中的模型推断成为“确定事实”。

当 KV 太大时，滑窗只保留近邻上下文、KV 量化降低字节数、GQA 降低 KV 头数，分别改变可见历史、表示精度、架构头数。三者不能直接比较一个“压缩率”而忽略任务质量。

#原始资料

本页由仓库中的 Markdown 生成。具体技术结论请结合正文引用与实验条件理解。