🤖 machine learning

Approximate Speculative Decoding

This paper introduces Approximate Speculative Decoding (ASD), a training-free method that accelerates autoregressive generation by selectively accepting draft token mismatches based on a regret budget to reuse valid suffixes, thereby improving throughput without requiring new draft models or fine-tuning.

Original authors: Yuannuo Feng, Zegang Peng, Yuxin Xie, Yubing Ye, Yizhe Chen, Wenshuai Yao, Wenyong Zhou, Wang Kang

Published 2026-08-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuannuo Feng, Zegang Peng, Yuxin Xie, Yubing Ye, Yizhe Chen, Wenshuai Yao, Wenyong Zhou, Wang Kang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to write a story with a very smart, but incredibly slow, friend. Every time you want to add a new word to your story, you have to wait for your friend to think hard, check their entire library of knowledge, and tell you exactly which word comes next. This is how modern AI language models work: they generate text one word at a time, and the "thinking" part takes up most of the time, making the process feel like watching paint dry. To speed this up, scientists invented a trick called "speculative decoding." Think of it like having a fast, junior assistant who guesses the next few words for you. You then ask your slow, expert friend to quickly check if those guesses are right. If the expert agrees, you get to write several words at once instead of just one, saving a massive amount of time.

However, there's a catch. The expert friend is a stickler for rules. If the assistant guesses even one word that isn't the absolute perfect choice the expert would have picked, the expert stops the whole process immediately. They throw away all the other words the assistant guessed for that turn, even if most of them were actually perfect. It's like a teacher grading a test who stops reading the moment they see one wrong answer, tossing the rest of the paper in the trash. This "all-or-nothing" rule keeps the story perfect, but it wastes a lot of the assistant's hard work and slows things down.

This paper introduces a new method called Approximate Speculative Decoding (ASD), which acts like a smarter, more flexible teacher. Instead of throwing away the whole test just because of one small mistake, ASD asks: "Is this mistake tiny? And did the assistant get the next few words right anyway?" If the answer is yes, ASD accepts the small mistake, keeps the good words that followed, and moves on. It's like a teacher who says, "You got the spelling of 'because' wrong, but you spelled the next ten words perfectly, so let's just fix the one word and keep going." The researchers found that by being slightly more lenient with tiny errors, they could make the AI write significantly faster without ruining the quality of the story.

The Story of the "Budgeted" Assistant

The core idea behind ASD is to stop treating every mistake as a disaster. In the old way, if your assistant guessed a word that wasn't the top choice, the system would stop immediately. But the authors realized that sometimes, the assistant's "wrong" guess is actually very close to the right one, and the words that follow it are still perfect.

To fix this, the team created a system with a budget. Imagine you have a jar of "mistake tokens." You are allowed to make a few small mistakes, but you have to pay for them from your jar.

The Local Gate: Before accepting a mistake, the system checks how "bad" it is. If the assistant's guess is only slightly less likely than the perfect word, it's a cheap mistake. If it's a huge error, it costs too many tokens, and the system says "no."
The Block Cap: You can't make too many mistakes in a single batch of guesses. This prevents the assistant from getting too inaccurate all at once.
The Request Budget: This is the total jar of tokens for the whole conversation. Once you run out of tokens, you have to go back to being perfect (strictly following the old rules) for the rest of the story.

The magic happens when the system accepts a small mistake. Because the assistant's next few guesses were actually perfect (they matched what the expert would have chosen), the system can "reuse" them. It doesn't need to ask the slow expert to check them again. It just accepts them and moves forward. This turns a "stop and throw away" moment into a "fix and keep going" moment.

What They Found

The researchers tested this idea using some very popular AI models (like Qwen3 and DeepSeek) on a variety of tasks, from solving math problems to writing code. They didn't need to retrain the models or teach the assistant anything new; they just changed how the "teacher" (the verifier) graded the work.

The results were quite promising. By using this budgeted approach, the system became faster without needing any extra training.

On a set of seven different tasks, the system got 7.78% faster on average compared to the strict, old-fashioned method.
In the best cases, like on the MATH-500 dataset, it sped up by 11.73%.
When they tested it on a massive model called DeepSeek-V4-Flash, they saw acceptance rates (how many guesses the system kept) go up by roughly 10% to 16%.

The paper is careful to note that this isn't a magic wand that makes everything perfect. The authors explicitly state that this method changes the path the AI takes to get to the answer. Sometimes, the story might be slightly different, or the "hash" (a digital fingerprint of the text) might change, even if the final answer is still correct. For example, on some coding tests, the accuracy dipped slightly (by less than 1.5 percentage points), but on many other tasks, the accuracy stayed exactly the same or even improved slightly.

Why This Matters

The beauty of this paper is that it doesn't require building a new, faster AI or training a new assistant. It just changes the rules of the game for the one you already have. It's like realizing that a strict traffic cop is slowing down the whole city because they stop the car for every single minor infraction, when a more flexible approach would keep traffic flowing smoothly with only tiny, manageable risks.

The authors suggest that this method is a great way to squeeze more speed out of current AI systems. They emphasize that while the speed gains are real and measurable (up to 15.26% in some cases), users need to be aware that they are trading a tiny bit of strict perfection for a lot of speed. It's a calculated trade-off: you get your story written much faster, and for most people, the tiny differences in the wording won't matter at all. The paper concludes that this "budgeted" approach is a practical, training-free way to make AI generation faster, provided you check the results to make sure the quality is still good enough for your needs.

Technical Summary: Approximate Speculative Decoding (ASD)

Problem Statement

Autoregressive Large Language Models (LLMs) generate tokens sequentially, creating a significant inference bottleneck due to repeated executions of a large target model. Speculative decoding addresses this by using a lightweight "drafter" model to propose a block of future tokens, which are then verified in parallel by the target model.

Under standard greedy verification, the process is strictly binary: the verifier commits the longest prefix of draft tokens that exactly match the target model's argmax (greedy) tokens. The process stops at the first mismatch, discarding the remaining draft tokens and appending a single target recovery token. This approach has two primary limitations:

Inherent Binary Truncation: It treats a draft token with a near-tied target logit (low regret) identically to a strongly disfavored token, stopping immediately upon any mismatch.
Wasted Computation: In a teacher-forced verification pass, the target model has already scored subsequent draft tokens conditioned on the prefix (including the mismatch). If an early mismatch is accepted, a contiguous suffix of subsequent draft tokens may already be "target-greedy" under this new realized prefix. Standard verification discards these reusable tokens, requiring additional target forward passes to recover.

The core challenge is that accepting a non-greedy token alters the decoding trajectory. While this can unlock reusable suffixes, it is not a lossless optimization; uncontrolled accumulation of mismatches can degrade task quality. The paper posits that the goal is not to ignore mismatches, but to permit a bounded number of explicit exceptions while controlling their cumulative magnitude.

Methodology: Approximate Speculative Decoding (ASD)

ASD is a training-free verifier-side method that replaces the "first-mismatch truncation" rule with a budgeted longest-prefix selection strategy. It operates without modifying the draft model, requiring no fine-tuning, and adds no additional target-model forward passes.

Core Mechanisms

Local Target-Logit Regret:
For a draft token $x_i$ and target argmax $y^*_i$ , ASD calculates the local regret $r_i = z_i(y^*_i) - z_i(x_i)$ , representing the target's preference for the correct token over the draft token.
Three-Layer Control System:
ASD accepts a mismatch only if it satisfies three constraints, allowing it to select the longest feasible contiguous prefix:
- Local Regret Gate ( $g$ ): A normalized gate $r_i / q_i \leq g$ (where $q_i$ is the remaining proposal length) filters individually costly mismatches, favoring exceptions that are proportionate to the potential suffix reuse.
- Per-Block Exception Cap ( $M$ ): Limits the number of exceptions within a single draft block to prevent concentration of errors.
- Persistent Request-Level Regret Budget ( $B$ ): Maintains a ledger of cumulative regret ( $s$ ) across the entire request. A prefix is feasible only if its cumulative regret $C_t \leq B - s$ . This bounds the total deviation over the generation.
Realized-Prefix Suffix Reuse:
Once ASD commits a prefix ending at an accepted mismatch, it reuses subsequent draft tokens that remain target-greedy under the realized history (the history including the accepted mismatch). These tokens are committed without further approximate decisions or additional target forward passes.
Vectorized Implementation:
The algorithm constructs a feasibility mask for each position in the draft block based on the constraints above. The accepted length is the longest all-true prefix of this mask, computable via cumulative sums and products in $O(K)$ time. When the budget $B=0$ , ASD exactly recovers standard strict greedy verification.

Key Contributions

The paper makes three primary contributions:

Formulation: It formulates approximate greedy verification as a budgeted longest-contiguous-prefix selection problem, utilizing a persistent request-level ledger to account for accepted draft-target mismatches.
Mechanism Identification: It identifies and formalizes realized-prefix suffix reuse, demonstrating that after an accepted exception, a contiguous target-greedy suffix can be committed without additional approximate decisions, provided caches are updated consistently.
Empirical Validation: It provides experimental evidence that this training-free verifier improves throughput significantly across various models and tasks without requiring changes to the proposal generation mechanism.

Experimental Results

Experiments were conducted on Qwen3-8B/14B, Llama-3.1-8B, and Qwen2.5-7B targets paired with DSpark, EAGLE3, and Medusa drafters across benchmarks including GSM8K, MATH-500, HumanEval, MBPP, MMLU, MT-Bench, and Alpaca.

Throughput Gains: ASD improves fixed-workload throughput by 3.05%–15.26% over matched strict speculative decoding.
- On Qwen3-14B + DSpark-14B, the average gain across seven tasks is 7.78%.
- The highest gain observed was 15.26% on GSM8K with Llama-3.1-8B + EAGLE3.
Accuracy Trade-offs: The method is a controlled approximation, not an output-preserving optimization.
- On the primary DSpark-14B matrix, five of seven tasks showed non-negative accuracy changes.
- Observed accuracy reductions were small (e.g., -0.61 points on HumanEval, -0.64 on MT-Bench) and task-dependent.
- On GSM8K and MATH-500, hash divergence exceeded 95%, indicating altered trajectories, yet measured accuracy remained stable or improved.
Scalability: Gains persist across different drafter families (DSpark, EAGLE3, Medusa) and target models, indicating the benefit is driven by the verifier-side mechanism rather than specific proposal architectures.
Large Model Compatibility: On DeepSeek-V4-Flash (284B) with DSpark in an FP4-to-FP8 compatibility setting, ASD raised verifier-side acceptance by roughly 10%–16% on GSM8K and MATH-500.

Significance and Claims

The paper claims that ASD provides a broadly compatible, training-free path to faster greedy blockwise speculative decoding. Its significance lies in:

Decoupling Verification from Proposal: Unlike prior work that focuses on improving the drafter, ASD optimizes the verifier's commitment decision after scoring is complete.
Explicit Trade-off Control: By introducing a persistent regret budget and local gates, ASD allows users to explicitly tune the speed-accuracy frontier, moving beyond the binary "all-or-nothing" nature of strict verification.
System Efficiency: The method reduces the number of expensive target verification rounds by reusing target-scored suffixes, achieving throughput gains without additional forward passes or model retraining.

The authors emphasize that ASD bounds accumulated local regret but does not guarantee identical outputs, semantic preservation, or task correctness. Consequently, they advocate for a deployment model where verifier controls are frozen on disjoint data, followed by a natural-EOS task-quality audit for each specific target, drafter, and workload combination.