Approximate Speculative Decoding
Yuannuo Feng, Zegang Peng, Yuxin Xie, Yubing Ye, Yizhe Chen, Wenshuai Yao, Wenyong Zhou, Wang Kang
cs.LG, cs.AI
2026-08-04
ASD accepts budgeted greedy mismatches and reuses scored suffixes, adding 7.78% mean and up to 15.26% TPS over strict speculative decoding.
Speculative decoding lets a small drafter propose a block of tokens and has the large target score them in one parallel pass. Standard greedy verification stops at the first draft token that is not the target argmax, and throws away the rest of a block the target already scored. A near-tie is treated the same as a token the target strongly dislikes.
That discarded suffix is often still useful. The verification pass is teacher-forced, so later logit rows are already conditioned on the draft prefix, including any earlier mismatch. If the verifier accepts that mismatch, later draft tokens may already be target-greedy under the history that was just realized. They can be committed with no extra target forward pass.
Accepting a non-greedy token changes the trajectory. This is not a lossless speedup. A purely local rule can stack cheap mismatches across a long completion; resetting an allowance every draft block forgets exceptions already spent. The job is to allow a few explicit exceptions and keep their cumulative local regret under a request-level cap.
Approximate Speculative Decoding (ASD) is a training-free verifier that runs after the ordinary target pass. When the request regret budget B is zero, it dispatches to ordinary token-ID greedy verification, including the case where several tokens tie for the top logit.
Local regret at a position is the target's top logit minus the logit of the drafted token. After the softmax normalizer cancels, that is also the target's conditional log-probability preference. It is an accounting quantity, not a calibrated error probability and not a promise about task quality.
A candidate prefix is feasible only if it clears three gates:
ASD returns the longest contiguous feasible prefix. It never skips an infeasible token to harvest a later one; that would desynchronize the target rows used for scoring from the KV cache that actually gets committed. After an accepted exception, a run of later tokens that already match the target argmax is reused at no extra regret and no extra target pass. The verifier itself is O(K) arithmetic.
The frozen operating point for the main tables is B=8, g=0.25, M=2, selected on disjoint GSM8K slices and then held fixed.
The primary matrix is Qwen3-14B with DSpark-14B on one NVIDIA L20, greedy decoding. Against matched strict speculative decoding, fixed-workload tokens-per-second rises on all seven tasks, by 7.78% on average. Mean accepted length moves from 3.85 to 4.20 tokens per round, with MATH-500 and GSM8K picking up 0.67 and 0.49 tokens.
| Task | Strict SD vs target-only | ASD | vs strict | ΔAcc (pp) |
| GSM8K | 5.58× | 6.30× | +10.08% | +0.15 |
| MATH-500 | 6.88× | 7.32× | +11.73% | +1.17 |
| HumanEval | 4.68× | 5.14× | +6.90% | −0.61 |
| MBPP | 5.04× | 5.36× | +3.64% | +0.54 |
| MMLU | 3.30× | 3.54× | +4.41% | +0.73 |
| MT-Bench | 4.68× | 5.16× | +7.79% | −0.64 |
| Alpaca | 4.22× | 4.66× | +9.94% | +0.10 |
Across DSpark, EAGLE3, and Medusa, all ten cells are positive, averaging 7.52%. The peak is Llama-3.1-8B + EAGLE3 on GSM8K at +15.26%; the same pair gets +11.94% on MMLU. Medusa starts from a shorter accepted length and gains less: +6.72% on GSM8K, +4.70% on MMLU. Every reported 95% interval sits strictly above zero. Strict SD already spans 1.82×–6.88× over target-only decoding; ASD lifts that range to 1.94×–7.32×.
Under a matched maximum-realized-regret constraint, ASD is +6.5% on GSM8K versus +5.3% for a MARS-style local rule and +5.1% for a Fuzzy-style rule; on MATH-500 the three numbers are +9.7%, +6.0%, and +7.3%. In synchronized profiling, verifier logic costs an extra 0.045–0.083 ms per output token while target verification drops by about 1.48–1.51 ms. The win is fewer expensive verify rounds.
DeepSeek-V4-Flash with DSpark on eight H20 GPUs reports acceptance only. The drafter is FP4; Hopper natively wants FP8, so extra quantize/dequantize steps sit on the path and end-to-end TPS is not claimed. On a held-out 1,000-example GSM8K-Confirm split, g in {2, 3} raises accepted draft tokens per proposal by 10.08%–11.48%, with accuracy moving by at most 0.30 points. The abstract quotes roughly 10%–16% acceptance gains on GSM8K and MATH-500.
For a stack that already runs greedy speculative decoding, this is a verifier-side drop-in: no new drafter, no fine-tuning, no extra target pass. The percentages sit on top of an already strong strict-SD baseline, not on top of naive decoding.
What is being sold is a controlled speed-behavior trade, not output identity. On GSM8K and MATH-500 the output hash diverges on more than 95% of prompts while measured accuracy does not fall, which means the reasoning path changed and the final answer often still matched. The intended deployment is explicit: freeze controls on disjoint data, then audit natural-EOS quality per target, drafter, and workload.
Batch jobs that care about throughput more than token-level traces are the natural fit. Workloads that must reproduce the target greedy trajectory can set B=0 and fall back to strict verification.
The ledger bounds the sum of local regrets from accepted exceptions. It is not a sequence-level likelihood-ratio bound. The paper states that it does not imply identical outputs, distributional equivalence, semantic preservation, safety, or task correctness.
Accuracy is much less consistent than throughput. Two of seven primary tasks drop (HumanEval −0.61, MT-Bench −0.64). The worst cross-family cell is Medusa + Llama-3.1-8B on GSM8K at −1.52 points. Hyperparameters were searched on GSM8K slices and then frozen, so transfer to other tasks can still be GSM8K-shaped. In Table 3, B=4 already costs −0.78 points on GSM8K while B=8 shows +2.34; quality is budget-sensitive, and those deltas come from natural-EOS decoding, not the fixed-workload TPS protocol.
The large-model study does not report end-to-end TPS because of the FP4-to-FP8 compatibility path, so system-level gain at that scale is still unmeasured. All main experiments are greedy; rejection-sampling speculative sampling is out of scope. Table 1 and Table 2 disagree on Qwen3-14B MMLU ΔAcc (0.73 vs 0.22) with no explanation in the text.