首次揭示大模型推测生成的理论极限，为加速推理提供根本指导。
Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks
- 将分枝随机游走理论引入推测生成，建模最优草稿树选择问题。
- 证明每轮推测最多成功生成约 (μ+μ_(2))log(P)/μ² 个令牌。
- 理论结果与实际测试一致，适合研究推理加速的学者参考。
推测生成已成为加速大语言模型推理的有前景技术，通过并行验证多个草稿令牌实现提速。然而，可达到的加速上限仍不清晰。本文首次建立确定性推测生成算法的紧致下界，通过将令牌生成过程类比为分枝随机游走，分析最优草稿树选择问题。在基本假设下，我们证明每轮推测中成功预测的令牌期望数量满足：𝔼[X] ≤ (μ + μ_(2))log(P)/μ² + O(1)，其中 P 为验证器容量，μ 为验证器输出分布的期望熵，μ_(2) 为期望二阶对数矩。该结果揭示了并行令牌生成的理论极限，可指导未来推测解码系统的设计。对 Llama 模型的实证评估验证了理论预测，确认了界限在实际场景中的紧致性。
原文摘要 · Abstract (English)
Speculative generation has emerged as a promising technique to accelerate inference in large language models (LLMs) by leveraging parallelism to verify multiple draft tokens simultaneously. However, the fundamental limits on the achievable speedup remain poorly understood. In this work, we establish the first ``tight'' lower bounds on the runtime of any deterministic speculative generation algorithm. This is achieved by drawing a parallel between the token generation process and branching random walks, which allows us to analyze the optimal draft tree selection problem. We prove, under basic assumptions, that the expected number of tokens successfully predicted per speculative iteration is bounded as $\mathbb{E}[X] \leq (μ+ μ_{(2)})\log(P )/μ^2 + O(1)$, where $P$ is the verifier's capacity, $μ$ is the expected entropy of the verifier's output distribution, and $μ_{(2)}$ is the expected second log-moment. This result provides new insights into the limits of parallel token generation, and could guide the design of future speculative decoding systems. Empirical evaluations on Llama models validate our theoretical predictions, confirming the tightness of our bounds in practical settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。