Approximate Speculative Decoding
Proposes Approximate Speculative Decoding (ASD), a zero-training verifier that boosts throughput by up to 15.26% via budgeted longest-prefix selection.
Key Findings
Methodology
ASD introduces a training-free verifier that replaces binary first-mismatch truncation with a budgeted longest-prefix selection mechanism. It measures local target-logit regret at each mismatch, accepting mismatches within a predefined regret gate, exception cap, and request-level regret budget. Accepted mismatches allow reusing contiguous target-greedy suffixes without additional model passes or approximate token decisions. This approach maintains standard greedy verification when the budget is zero and significantly improves throughput across multiple tasks. Experiments on Qwen3-14B+DSpark-14B show an average throughput increase of 7.78%, with gains up to 15.26%, and a 10-16% increase in verifier acceptance rate on DeepSeek-V4-Flash (284B).
Key Results
- Across seven tasks, ASD achieves an average throughput boost of 7.78%, with the maximum reaching 15.26%, outperforming strict greedy verification. It effectively reuses target-greedy suffixes after accepting low-regret mismatches, reducing redundant computations.
- On DeepSeek-V4-Flash (284B), ASD raises acceptance rates by 10-16% on GSM8K and MATH-500, demonstrating robustness and generalization across models and tasks. The method's parameters, such as budget and gate thresholds, are tuned to balance speed and accuracy.
- Ablation studies confirm that the combination of local regret gate, block cap, and request budget controls the trade-off, with larger budgets yielding higher throughput but slight accuracy variations, indicating practical flexibility.
Significance
This work advances the field of autoregressive decoding by introducing a simple yet effective verification strategy that does not require retraining or additional model forward passes. It addresses the longstanding bottleneck in large language model inference, enabling faster deployment and real-time applications. The approach’s generality and minimal overhead make it highly applicable in industry settings, especially for large-scale models where inference speed is critical. By controlling approximation through a budget mechanism, it offers a practical solution to balance speed and reliability, paving the way for more efficient AI systems.
Technical Contribution
The key technical innovation lies in formulating verification as a budgeted longest-prefix selection problem, leveraging a persistent ledger to track cumulative local regret. This systematic approach bounds the total deviation from the target trajectory, enabling the reuse of target-greedy suffixes after accepting low-regret mismatches. The method integrates seamlessly with existing greedy decoders, requiring only target logits and no retraining, thus providing a lightweight yet powerful acceleration technique. The theoretical framework offers bounds on cumulative regret, contributing to the understanding of approximate decoding strategies.
Novelty
This study is the first to formalize a verification mechanism based on budgeted longest prefix selection, combining local regret measurement with a persistent ledger to control cumulative deviation. Unlike prior semantic or divergence-based relaxation methods, ASD explicitly bounds the total approximation error, ensuring a controlled trade-off between speed and output fidelity. Its training-free nature and simplicity distinguish it from existing approaches, offering a new paradigm for efficient autoregressive decoding.
Limitations
- ASD cannot guarantee semantic equivalence or task correctness; accepting mismatches introduces potential errors, especially at higher budgets. The method relies on parameter tuning, which may affect robustness across different models and tasks.
- In extremely large models, the additional overhead for maintaining budgets and regret calculations may impact efficiency. The approach assumes that low-regret mismatches are safe, which may not hold in all scenarios.
- Future work should explore adaptive parameter tuning, integration with learning-based verifiers, and extension to multi-modal or multi-task settings to address these limitations.
Future Work
Future directions include developing adaptive mechanisms for dynamically tuning budgets and gate thresholds based on task complexity, integrating learning-based verification modules for improved accuracy, and extending the framework to multi-modal generation tasks. Additionally, exploring theoretical bounds on output fidelity and robustness under various approximation levels will further solidify ASD’s practical deployment. Combining ASD with proposal model improvements could yield even greater speedups while maintaining quality.
AI Executive Summary
Large autoregressive language models have revolutionized natural language processing, but their inference speed remains a critical bottleneck. Traditional greedy decoding guarantees exact output trajectories but often underutilizes potential speedups due to conservative verification stopping at first mismatch. Recent efforts introduced speculative decoding, pairing lightweight drafters with target models, yet these approaches still rely on binary acceptance criteria that discard valuable suffixes when mismatches occur. This paper introduces Approximate Speculative Decoding (ASD), a novel, training-free verifier that employs a budgeted longest-prefix selection strategy. ASD measures local target-logit regret at each token, accepts mismatches within a predefined budget, and reuses contiguous target-greedy suffixes without extra model passes. This systematic control over approximation enables significant throughput gains—up to 15.26% on benchmark tasks—while maintaining task performance within acceptable bounds. Extensive experiments across multiple models and datasets demonstrate ASD’s robustness, generality, and ease of integration. The core innovation lies in transforming verification into a budgeted prefix selection problem, leveraging a persistent regret ledger to bound cumulative deviation. Although it introduces some approximation, the method offers a practical balance between speed and accuracy, making it highly suitable for real-time AI applications. Future work will focus on adaptive parameter tuning, multi-modal extensions, and theoretical guarantees to further enhance its utility and reliability.
Deep Analysis
Background
近年来，自回归大规模语言模型（如GPT-3、BERT变体）在自然语言处理领域取得了巨大突破，但其逐词生成的特性导致推理速度成为限制实际应用的瓶颈。早期的块式解码技术（如Leviathan、Wang等提出的方案）尝试通过并行预测多个候选词，提升推理效率，但验证策略仍是关键瓶颈。传统的贪婪验证策略简单高效，但在偏差控制方面存在局限，容易因早期偏差累积而导致输出质量下降。近年来，学者们提出多种放宽验证条件的方法，包括语义一致性、分歧约束和不确定性阈值（如Bachmann、Holsman等），旨在在保证输出质量的同时提升吞吐量。然而，这些方法多依赖训练或复杂模型调优，限制了其广泛应用。本文在此背景下，提出一种无需训练的验证机制，结合预算最长前缀选择策略，旨在在保证输出质量的基础上实现高效推理。
Core Problem
当前的验证策略在遇到偏差时会立即停止，导致已验证的连续目标后缀无法复用，限制了推理速度提升。偏差的累积可能引入错误，影响任务性能。如何在保证输出质量的前提下，合理放宽验证策略，提升系统吞吐量，成为亟待解决的问题。现有方法多依赖训练或复杂调优，缺乏通用性。本文试图通过引入预算机制，控制偏差累积，实现无训练的高效验证策略，从而突破这一瓶颈。
Innovation
核心创新在于提出基于预算最长前缀选择的验证策略，将偏差控制转化为预算限制问题。引入局部目标-logit遗憾门控、块级异常上限和请求级遗憾预算，有效限制偏差累积，允许在满足预算条件下提前复用目标贪婪后缀。该方法无需训练，直接在标准验证基础上实现，简化系统架构。最大创新在于利用已接受异常后，系统性地复用连续目标后缀，显著提升推理吞吐量，同时保持任务性能。
Methodology
- �� 输入：待解码的draft块和目标贪婪序列；目标模型输出的logits。
- �� 计算每个位置的偏差指标（目标对数遗憾）和门控参数。
- �� 设定预算参数，包括遗憾总预算、块级异常上限和请求级偏差。
- �� 在每个块中，逐位置评估偏差，满足门控和预算条件的最长连续目标贪婪前缀。
- �� 允许接受偏差，复用已验证的目标贪婪后缀，无需额外模型前向。
- �� 更新偏差账本，确保偏差不超出预算。
- �� 输出：最长满足条件的前缀和对应的目标后缀，继续下一轮解码。
Experiments
采用Qwen3-14B+DSpark-14B在多任务（GSM8K、MATH-500、HumanEval等）上的评估，比较传统严格验证与ASD的吞吐量和接受率。调节预算和门控参数，分析不同配置对性能的影响。采用多次重复实验确保统计显著性，评估指标包括吞吐量（tokens/sec）、任务准确率和偏差度。还在不同模型架构（如EAGLE3、Medusa）上验证泛化能力，进行消融分析以确认各参数的重要性。
Results
ASD在七个任务中平均提升吞吐量7.78%，最高达15.26%，在GSM8K和MATH-500任务中表现尤为突出，接受率提升10%-16%。调节预算和门控参数，验证了偏差控制的有效性。实验还显示，ASD在不同模型和提案架构下均能实现性能提升，且对任务准确率影响有限，部分任务甚至略有提升。消融实验确认预算和门控参数对性能的调节作用，验证了方法的鲁棒性和适应性。
Applications
该方法适用于大规模自动文本生成、问答系统、对话机器人等场景，尤其在对推理速度要求较高的应用中。无需额外训练或模型调整，便于在现有模型基础上快速部署。未来可结合多模态信息或自适应调节策略，进一步提升系统效率和鲁棒性，推动智能系统的实时交互能力。
Limitations & Outlook
ASD不能保证输出的语义等价性，偏差可能在某些任务中累积导致错误。参数设置敏感，需调优以适应不同模型和任务。高偏差预算可能引入错误风险，且在超大模型中计算开销增加，未来需优化算法效率和偏差控制策略。
Plain Language Accessible to non-experts
想象你在厨房里做饭，厨师（模型）需要逐步准备一道菜（生成文本）。传统的方法就像每次只做一份菜，等到确认味道好才继续下一步，速度慢但保证质量。而投机解码像是提前准备好多份菜的不同部分，但如果发现味道不对，就只能扔掉一部分。这个研究提出一种聪明的厨房管理方式，允许厨师在一定范围内提前接受一些可能不完美的步骤，只要整体味道还能保证。这样，厨师可以提前用掉一些已经准备好的材料，节省时间，做菜更快。这就像给厨师设定一个预算，只允许接受一定的偏差，既保证了菜的质量，又大大缩短了做菜时间。
ELI14 Explained like you're 14
想象你在玩一个超级复杂的拼图游戏，你要一步步拼出完整的图案。以前的方法就像每拼完一块都要确认无误才继续，太慢了。这次的办法就像你给自己设个规则：只要拼的块差不多对了，就可以先放一边，继续拼下一块。只要总的差错不超过一定的预算，你就可以快点完成拼图。这样，你就不用每次都反复检查，节省了很多时间，但拼出来的图可能会有点小瑕疵。这个新方法让你在保证大致效果的同时，拼图速度快了很多，特别适合需要快速完成的任务。虽然不能保证每一块都完美，但整体看起来还是很棒的！
Abstract
Speculative decoding accelerates autoregressive generation by verifying a draft block with a target model in parallel. Under standard greedy verification, decoding stops at the first draft token that differs from the target argmax, discarding the remaining target-scored suffix. Although accepting such a mismatch changes the decoding trajectory, it can make a contiguous suffix reusable when its tokens remain target-greedy under the realized prefix. In this paper, we introduce \textbf{Approximate Speculative Decoding (ASD)}, a training-free verifier that replaces binary first-mismatch truncation with budgeted longest-prefix selection. ASD accepts selected mismatches subject to a local target-logit regret gate, a per-block exception cap, and a persistent request-level regret budget, then reuses the contiguous target-greedy suffix without additional approximate decisions or target-model forward passes. ASD requires neither a new draft model nor fine-tuning, and exactly reduces to standard greedy verification when the budget is zero. Experiments show that ASD improves fixed-workload throughput by $3.05\%$--$15.26\%$ over matched strict verification and averages a $7.78\%$ gain across seven Qwen3-14B + DSpark-14B tasks. On DeepSeek-V4-Flash (284B) with DSpark it also raises verifier-side acceptance by roughly $10\%$--$16\%$ on GSM8K and MATH-500 in an FP4-to-FP8 compatibility setting. The source code is publicly available at: https://github.com/Kissmetothemoon/ASD