PaperlayerView exact revision on arXiv

Source-linked AI summary

Speculative Speculative Decoding

Tanishq Kumar, Tri Dao, Avner May

arXiv:2603.03251v3cs.LG

TL;DR

Autoregressive decoding and ordinary speculative decoding retain sequential bottlenecks between token generation, drafting, and verification. The paper introduces SSD and Saguaro to predict verification outcomes and precompute matching speculations, achieving 30% average speedups over speculative-decoding baselines and up to 5x over autoregressive generation. The approach improves the latency-throughput frontier, while its broader composition and scaling tradeoffs remain open.

  • Problem

    Speculative decoding accelerates inference but drafting and verification remain synchronous, limiting parallelization of the full process.

  • Method

    SSD runs drafting and verification in parallel, while Saguaro predicts likely verification outcomes, precomputes corresponding speculations, and adds optimized sampling and fallback strategies.

  • Results

    30% faster on average than the strongest speculative decoding baselines and up to 5x faster than autoregressive generation across datasets and model families.

  • Takeaways & Limitations

    SSD pushes the latency-throughput Pareto frontier, improving both latency and throughput even after accounting for additional hardware.

  • Takeaways & Limitations

    The joint design space for combining SSD with EAGLE and token-tree speculation remains largely unexplored, and scaling draft devices eventually has diminishing returns.

Abstract

from arXiv · show

Autoregressive decoding is bottlenecked by its sequential nature. Speculative decoding has become a standard way to accelerate inference by using a fast draft model to predict upcoming tokens from a slower target model, and then verifying them in parallel with a single target model forward pass. However, speculative decoding itself relies on a sequential dependence between speculation and verification. We introduce speculative speculative decoding (SSD) to parallelize these operations. While a verification is ongoing, the draft model predicts likely verification outcomes and prepares speculations pre-emptively for them. If the actual verification outcome is then in the predicted set, a speculation can be returned immediately, eliminating drafting overhead entirely. We identify three key challenges presented by speculative speculative decoding, and suggest principled methods to solve each. The result is Saguaro, an optimized SSD algorithm. Our implementation is on average 30% faster than optimized speculative decoding baselines and up to 5x faster than autoregressive decoding with open source inference engines.

1 Introduction

Speculative decoding reduces autoregressive inference latency but retains a sequential dependence between drafting and verification. SSD parallelizes these operations by predicting verification outcomes and precomputing corresponding speculations; Saguaro addresses the resulting design challenges and improves speed.

  • Motivation: Speculative decoding uses a fast draft model to propose tokens that the target verifies in one parallel forward pass.The verification algorithm preserves the target model's token distribution.
  • SSD: SSD predicts likely verification outcomes during verification and precomputes speculations for them, returning cached tokens immediately after a matching outcome.SSD places the draft model on hardware distinct from the target.
  • Challenges: SSD must predict both the number of accepted tokens and the sampled bonus token, balance cache-hit probability against speculation quality, and handle failed predictions.Failures become more frequent at larger batch sizes and temperatures.
  • Saguaro: Saguaro uses constrained outcome prediction, a sampling method that balances cache hits and acceptance, and batch-size-dependent fallback strategies.Its bonus-token prediction reaches up to 90% accuracy, and the fallback strategy varies with batch size.
  • Results: 30% faster on average than optimized speculative decoding baselines and up to 5x faster than autoregressive decoding, Saguaro improves end-to-end inference speed.The comparison covers four datasets spanning math, code, and chat under the Figure 1 setup.

2 Background

Speculative decoding accelerates target-model sampling by drafting candidate continuations and verifying them in parallel, but remains synchronous between rounds. Related approaches overlap computation or expand candidate trees, while retaining limitations such as restricted outcome coverage or sequential speculation.

  • Speculative Decoding: Speculative decoding drafts candidate continuations from a cheaper distribution and selectively accepts them using the target distribution.Accepted draft tokens are verified in parallel, with a bonus token sampled after rejection or full acceptance.
  • Speculative Decoding: The expected tokens generated per round depend on the conditional acceptance rate, which reflects how closely the draft distribution approximates the target.This connects draft quality to speculative-decoding efficiency.
  • Definitions: A speculation is a draft-generated sequence of K tokens, where K is the speculative lookahead.The sequence is proposed autoregressively at a decoding round.
  • Definitions: A verification outcome records accepted draft tokens together with the bonus token sampled from the residual or target distribution.This outcome determines the next decoding state.
  • Related Work: Existing parallel approaches overlap drafting and verification but may prepare only the all-accepted outcome or verify multiple sequences with distinct verifier copies.Some related methods use just-in-time fallback speculation that struggles at higher temperatures and batch sizes.
  • Related Work: Tree-based methods offer multiple token choices but remain sequential and add substantial verifier computation.SSD differs by parallelizing the drafting and verification dependence itself.

3 The Speculative Speculative Decoding Framework

SSD runs speculator and verifier processes asynchronously on separate hardware, caching speculations for predicted verification outcomes. Its speed depends on cache hits, generated tokens, and fallback behavior, with theory establishing advantages over autoregressive and ordinary speculative decoding.

  • Framework: SSD introduces a framework for asynchronous speculative decoding and compares its expected speed with autoregressive and ordinary speculative decoding baselines.The framework underlies the Saguaro instantiation.
  • Algorithm: While the verifier processes round T, the speculator predicts likely outcomes and caches speculations for round T + 1.A cache hit immediately supplies the corresponding token sequence; a miss triggers fallback handling.
  • Algorithm: The SSD implementation launches the speculator asynchronously while the verifier receives, verifies, and returns outcomes until an end token appears.The two processes exchange speculations and verification outcomes across separate hardware.
  • Theoretical Results: speedup_SSD = [p_hit · E_hit + (1 − p_hit) · E_miss] / [p_hit · max(1, T_p) + (1 − p_hit) · (1 + T_b)] combines expected tokens with expected iteration latency.The numerator counts generated tokens, while the denominator measures latency relative to autoregressive decoding.
  • Theoretical Results: SSD with identical primary and backup speculators is no worse than SD and is strictly better when p_hit > 0 and T_SD > 0.This follows from the strict-faster-than-SD corollary.
  • Theoretical Results: SSD speedups arise from hiding draft latency and increasing expected generated tokens, but low cache-hit probability limits effectiveness.The speedup bound makes both contributions explicit.

4 Saguaro: An Optimized SSD Algorithm

Saguaro optimizes SSD through cache construction, sampling, and fallback strategies that address verification prediction, cache-hit trade-offs, and cache misses. Its geometric fan-out, sampling controls, and batch-dependent fallback improve cache behavior and end-to-end decoding speed.

  • Saguaro organizes its optimized SSD algorithm around cache construction, sampling, and fallback optimizations.These correspond to Sections 4.1, 4.2, and 4.3.
  • Saguaro cache construction: The speculation cache stores precomputed continuations for selected verification outcomes under a budget on the number of outcomes.The outcome space is approximately (K + 1)V, so constrained optimization selects outcomes likely to maximize cache hits.
  • Saguaro cache construction: Saguaro’s cache construction uses top-Fk draft logits at each lookahead position, excluding the sampled verification token, to predict bonus-token outcomes.Fan-out Fk denotes the number of cached verification outcomes with k accepted tokens; primary and backup speculators have separate fan-out values.
  • Saguaro cache construction: The optimal fan-out follows a capped geometric series under acceptance-rate and power-law cache-hit assumptions, allocating fewer guesses where longer verified strings are unlikely.This allocation maximizes speedup subject to a cache-size constraint.
  • Saguaro cache construction: Geometric fan-out improves cache-hit rate and end-to-end decoding speed over uniform fan-out, especially at higher temperatures.The comparison is averaged over four datasets, and SSD with either fan-out strategy outperforms ordinary speculative decoding at all temperatures.
  • Saguaro sampling: Saguaro sampling trades cache-hit rate against speculative acceptance rate by biasing draft probabilities to increase residual mass on cached tokens.Lower values of C increase cache-hit rates but lower acceptance rates; the sampling scheme’s cache-hit rate increases monotonically as C approaches zero.
  • Saguaro fallback: Saguaro’s optimal fallback uses the slow, accurate speculator below a batch-size threshold and the fast speculator above it.Theorem 17 derives this batch-dependent choice for two speculators with different speeds and quality.

5 End-to-End Evaluation

Saguaro is evaluated against speculative decoding and autoregressive baselines across datasets and inference engines. It improves decoding speed and the throughput-latency trade-off.

  • The evaluation compares Saguaro with ordinary speculative decoding, vLLM, SGLang, and EAGLE-3 where supported.SGLang is used as the main baseline because it usually outperforms vLLM in the authors’ experiments.
  • 30% faster on average than the strongest speculative decoding baselines and almost 5x faster than the autoregressive baseline.The comparison includes the authors’ speculative-decoding implementation and open-source engines such as vLLM and SGLang.
  • SSD pushes the throughput-latency Pareto frontier, with the biggest gains at lower batch sizes.The figure compares end-to-end decoding speed across four datasets on Llama-3.1-Instruct 70B.
  • SSD improves the best possible decoding speed and is more compute efficient per device.

6 Conclusion and Limitations

The paper introduces SSD to parallelize drafting and verification, then distills its design into Saguaro. It reports faster decoding and Pareto-frontier gains, while identifying several open design directions and implementation assumptions.

  • SSD parallelizes the sequential dependence between drafting and verification, and Saguaro is the resulting optimized algorithm.The paper derives performance bounds and studies components of the SSD design space.
  • 30% faster on average than the strongest speculative decoding baselines and up to 5x faster than autoregressive generation across datasets and model families.
  • SSD improves both latency and throughput even after accounting for the additional hardware used.The paper reports these gains on the latency-throughput Pareto frontier, including throughput-bound workloads.
  • The joint design of SSD with EAGLE and token-tree speculation remains largely unexplored, and scaling draft devices has diminishing returns.The paper also proposes sharing speculation endpoints across target-model deployments as a future direction.
  • The implementation assumes primary speculation finishes before verification and that batch sequences are unrelated with iid cache-hit probability.

A.1 Theorem 7 proof: Modeling the speedup from SSD

Theorem 7 models SSD speedup by separating cache-hit and cache-miss outcomes, then establishes when SSD is no worse or strictly better than speculative decoding.

  • SSD speedup equals expected generated tokens divided by expected latency, weighted separately over cache hits and misses.Cache hits contribute Ehit tokens and latency max(1, Tp); misses contribute Emiss tokens and latency 1 + Tb.
  • The overall cache-hit rate depends recursively on whether the previous iteration used the primary or backup speculator.The closed form is phit = phit,b / (1 + phit,b − phit,p).
  • SSD with identical primary and backup speculators is no worse than SD and is strictly better when phit > 0 and TSD > 0.If either phit = 0 or TSD = 0, the SSD and SD speeds are equal.
  • The speedup analysis assumes primary drafting time Tp is less than one verifier time unit and backup drafting time Tb can be modeled separately.Under these conditions, cache-hit and cache-miss iterations have distinct latency expressions.

A.2 Theorem 12 Proof: Optimizing Saguaro cache topology

The cache-topology analysis optimizes fan-out values under a budget, yielding geometric fan-out under power-law cache-hit assumptions. The sampling analysis shows how changing draft probabilities can improve cache hits and end-to-end speed.

  • Cache topology: The cache-hit objective depends on how many tokens were accepted, whether all tokens were accepted, and which speculator produced the previous round.These conditional quantities can be estimated empirically from draft and target distributions on a calibration set.
  • Cache topology: The optimal Saguaro cache topology maximizes primary and backup cache-hit rates under the fan-out budget constraint.The optimization is formulated using acceptance rates and conditional cache-hit functions, with Lagrange multipliers used in the proof.
  • Cache topology: Under a power-law cache-hit rate and acceptance-rate assumptions, the optimal fan-out values follow a geometric series.An equivalent result holds for the backup speculator.
  • Saguaro sampling: Saguaro’s cache-hit rate increases as C approaches zero, while increasing C shifts draft probability toward cached tokens and away from uncached tokens.The proof uses the resulting monotonic changes in residual probability mass.
  • Saguaro sampling: There exist target and draft distributions where Saguaro sampling preserves a 0.98 acceptance rate while strictly increasing cache-hit rate and end-to-end speed.The constructed example therefore yields faster end-to-end decoding than direct sampling from the original draft distribution.

A.4 Corollary 16 and Theorem 17 Proofs: Optimizing Saguaro Fallback strategy

The fallback strategy compares slow and fast backup speculators through expected speedup, yielding a batch-size threshold that selects the primary below the threshold and the fast backup at or above it.

  • Corollary 16: Corollary 16 expresses SSD’s expected speedup at batch size b in terms of cache-hit probability and hit or miss token yields.The derivation models expected generated tokens as phit · Ehit + (1 − phit) · Emiss and batch latency through cache-hit behavior.
  • Cache-hit analysis: Cache-hit analysis conditions phit on the prior primary speculation, and improving this conditional acceptance rate suffices to improve the unconditional rate.The proof notes that the relevant conditional cache-hit quantity is shared across the compared draft distributions.
  • Theorem 17: The optimal cache-miss strategy uses the high-quality primary speculator for b < b∗ and the negligible-latency backup otherwise.The threshold b∗ is obtained by equating the expected speedups of the slow-primary and fast-backup strategies.
  • Theorem 17: The slow-backup speedup decreases with batch size, whereas the fast-backup speedup is batch-size independent.This monotonicity establishes which strategy is better on either side of b∗.
  • Implementation: Saguaro implements the fallback design in a custom PyTorch engine using paged attention, continuous batching, tensor parallelism, BF16 precision, compilation, and CUDA graphs.The target model is split across four devices, while a small draft model runs on a separate device and communicates through NCCL.
  • Implementation: All F(K + 1) branches are decoded in parallel with a sparse mask, but mask materialization and fragmented KV-cache locations add substantial critical-path overhead.The implementation therefore performs an extend operation before each asynchronous decoding round to let forked branches attend to a shared prefix.

B.2 Experimental Design

The experiments measure decode throughput under controlled sampling and hardware settings, comparing Saguaro-related modes with established open-source inference engines and speculative-decoding baselines.

  • Datasets and metrics: The evaluation uses 512 prompts across HumanEval, Alpaca, GSM8K, and UltraFeedback, generating 512 tokens per prompt with vanilla sampling.Throughput measurements exclude prefill and use 128 prompts from each dataset.
  • Hardware and configurations: Experiments run on a single NVIDIA H100 node, using tensor parallelism across four GPUs for autoregressive and standard speculative decoding and five for SSD.The default setting is a single concurrent request unless batch-size scaling is being evaluated.
  • Baselines: Baselines include vLLM 0.16.0 and SGLang 0.5.9 with autoregressive decoding, standalone speculative decoding, and EAGLE-3.Standard speculative decoding uses a small draft model and proposes five draft tokens per step.
  • Baselines: The implementation’s vanilla speculative-decoding speed is comparable to vLLM and SGLang, supporting their use as strong baselines.The comparison includes both open-source inference engines under the stated tensor-parallel configurations.

C SSD Overhead

SSD trades additional computation, memory, and speculative work for lower latency, while targeting the sequential drafting-verification bottleneck and remaining compatible with complementary inference methods.

  • Compute: SSD decodes B(K + 1)F draft tokens per step, incurring a factor of ĉ(K + 1)F more draft FLOPs than ordinary speculative decoding.The extra work comes from decoding K steps of B(K + 1)F branches in parallel with a custom attention mask.
  • Compute: Pre-emptively decoded chains for incorrect verification outcomes become wasted compute, creating new compute-latency tradeoffs beyond standard speculative decoding.SSD follows the strategy of spending more FLOPs to reduce latency, but adds outcome-conditioned speculative work.
  • Memory: The speculation cache stores length-K continuations for B(K + 1)F possible outcomes, including logits, with total size O(BFK(K + 1)(V + 1)) bits.This cache grows with batch size, lookahead, fan-out, and vocabulary size.
  • Communication: Draft-target communication occurs once per speculation round, and the device-to-device NCCL traffic is not a practical bottleneck.The target sends O(B) outcome information, while the draft returns tokens and logits requiring O(BKV) bits.
  • Complementarity: SSD targets the sequential dependence between drafting and verification and is complementary to hardware-aware, KV-cache, sparse-attention, and tree-based acceleration methods.Token-tree methods can be combined by pre-speculating and verifying a tree for each possible verification outcome.
  • EAGLE-3: When combined with EAGLE-3, SSD can condition on up to 2K self-generated tokens, lowering acceptance on the latter K tokens.Training the draft to preserve acceptance over longer self-conditioning can mitigate this effect.

F Additional Experiments

Additional Qwen-3 experiments reproduce the main trends across model sizes, datasets, speed comparisons, cache behavior, and batch sizes.

  • Additional experiments: The Qwen-3 experiments reproduce similar trends from the main text, indicating that the reported results and algorithms extend across models and datasets.The appendix explicitly characterizes these trends as model and dataset agnostic.
  • Activation conditioning: Figure 9 compares activation conditioning in EAGLE-3 and SSD-EAGLE-3 when target activations are unavailable during pre-emptive speculation.SSD-EAGLE-3 substitutes draft activations for unavailable target activations, and more draft conditioning can degrade speculation quality.
  • Cache scaling: Figure 10 examines rejection-rate and cache-hit-rate scaling for the Qwen-3 family as cache fan-out F increases.The caption reports an approximate power-law relationship in fan-out, with cache-hit rates increasing as F grows.
  • Speed comparisons: Figures 11 and 12 compare Qwen-3 end-to-end decoding speed for SSD against speculative-decoding, autoregressive, and synchronous baselines.Figure 11 focuses on Qwen-3 32B across four datasets, while Figure 12 covers the Qwen-3 model family.
  • Batch scaling: Figure 13 evaluates how Qwen-3 throughput scales with batch size relative to synchronous baselines.The figure isolates batch-size scaling as the comparison dimension for the model family.
Loading 2603.03251v3…