PaperlayerView exact revision on arXiv

Source-linked AI summary

Double: Breaking the Acceleration Limit via Double Retrieval Speculative Parallelism

Yuhao Shen, Tianyu Liu, Junyi Shen, Jinyang Wu, Quan Kong, Li Huan, Cong Wang

arXiv:2601.05524v3cs.CL

TL;DR

PSD is limited by a draft-to-target speed-ratio ceiling and by waste from mid-sequence rejections. DOUBLE addresses both through double retrieval, reporting training-free, lossless speedups of 5.3× on LLama3.3-70B and 2.8× on Qwen3-32B, while its current unified datastore and synchronized retrieval depth leave room for model-specific optimization.

  • Problem

    PSD remains constrained by a theoretical speedup ceiling and mid-sequence rejection waste, while existing methods trade proposal speed against precision.

  • Method

    DOUBLE uses iterative retrieval in the draft model to expand candidate lengths and target-side retrieval to provide multi-token guidance that mitigates potential rejections.

  • Results

    5.3× on LLama3.3-70B and 2.8× on Qwen3-32B are reported as training-free, lossless speedups, surpassing EAGLE-3.

  • Takeaways & Limitations

    DOUBLE establishes a new SOTA for LLM inference while compensating for the limitations of draft-side and target-side retrieval.

  • Takeaways & Limitations

    The unified datastore and synchronized retrieval depth simplify deployment and memory management but may not fully exploit the distinct capabilities of the draft and target models.

Abstract

from arXiv · show

Parallel Speculative Decoding (PSD) accelerates traditional Speculative Decoding (SD) by overlapping draft generation with verification. However, it remains hampered by two fundamental challenges: (1) a theoretical speedup ceiling dictated by the speed ratio between the draft and target models, and (2) high computational waste and pipeline stall due to mid-sequence token rejections of early errors. To address these limitations, we introduce \textsc{Double} (Double Retrieval Speculative Parallelism). By bridging the gap between SD and PSD, our framework resolves the Retrieval \emph{Precision-Efficiency Dilemma} through a novel synchronous mechanism. Specifically, we enable the draft model to execute iterative retrieval speculations to break the theoretical speedup limits; to alleviate rejections without rollback, the target model performs authoritative retrieval to generate multi-token guidance. \textsc{Double} is entirely training-free and lossless. Extensive experiments demonstrate state-of-the-art speedup of $\textbf{5.3}\times$ on LLaMA3.3-70B and $\textbf{2.8}\times$ on Qwen3-32B, significantly outperforming the advanced method EAGLE-3 that requires extensive model training.

1 Introduction

Existing speculative-decoding methods trade proposal speed against precision: PSD overlaps drafting and verification but remains limited by a draft-speed ceiling and mid-sequence rejection waste. DOUBLE uses retrieval on both draft and target sides to expand proposals, guide verification, and improve speed without training.

  • Motivation: Autoregressive decoding remains memory-bandwidth-bound because each token depends on its predecessors.SD addresses this limitation with a lightweight draft model, but sequential draft-and-verify execution creates underutilized GPU resources.
  • Challenges: PSD overlaps drafting and verification to reduce latency, but its speedup is capped by the draft-to-target latency ratio.Off-the-shelf draft models yield modest ratios of 1.5–5× relative to large targets; PEARL reaches 1.3× on Qwen-0.6B/14B with C = 1.6.
  • Challenges: Mid-sequence rejection wastes generated tokens after early errors, while pre-verification can add overhead and offline predictors require training and remain lossy.PEARL’s single-token predictions provide low returns, whereas SpecBranch adds training costs and does not match target-model predictions.
  • DOUBLE: DOUBLE applies double retrieval: the draft iteratively retrieves to expand candidate length, while the target retrieves multiple tokens for verification and guidance.The design addresses the precision-efficiency dilemma by using both models’ retrieval capabilities within the parallel pipeline.
  • Results: 5.3× on LLama3.3-70B and 2.8× on Qwen3-32B are reported as DOUBLE’s SOTA speedups, surpassing EAGLE-3 despite its sophisticated training.The paper evaluates multiple datasets and model pairs, including HumanEval and CNN/DM.

3 Theoretical Analysis and Motivation

The analysis unifies SD and PSD across multiple rounds and proves that PSD has a hard speedup ceiling determined by the draft-to-target speed ratio. Retrieval is therefore motivated as a way to decouple draft length from draft latency.

  • Unified analysis: The multi-round analysis models SD and PSD jointly using continuously accepted tokens followed by a rejection round.The formulation approximates a bimodal acceptance distribution and defines C = T_p/T_q from target and draft single-token decoding times.
  • Speedup ceiling: PSD strictly dominates SD in the theorem but remains upper bounded by C, the draft-to-target speed ratio.The ceiling follows because an autoregressive draft can produce at most approximately C tokens during one target verification step, even when α = 1.
  • Implication: Standard PSD with off-the-shelf models cannot exceed the C ≈ 2–5 ceiling regardless of acceptance rate.The analysis identifies decoupling draft length from draft latency as necessary to break this barrier.
  • Motivation: Applying retrieval to PSD exposes a precision-efficiency dilemma, motivating retrieval-based acceleration that overcomes the draft model’s autoregressive barrier.The motivation is to maximize the effective speed ratio without sacrificing proposal quality.

1 Target-Side Retrieval (High Precision, Low Efficiency)

Prior retrieval methods trade precision against efficiency: target-side retrieval is accurate but latency-bound, while draft-side retrieval is faster but prone to rejection and serial bottlenecks. DOUBLE addresses this gap with synchronized retrieval on both sides, using iterative draft retrieval and target-guided verification to extend or correct sequences.

  • Target-Side Retrieval (High Precision, Low Efficiency): Target-side retrieval methods are bottlenecked by target-model latency and verification overhead, placing them in a low-efficiency regime.
  • Draft-Side Retrieval (High Efficiency, Low Precision): Ouroboros shifts retrieval to the draft model, but small-draft retrieval frequently fails verification and remains purely serial.
  • DOUBLE: DOUBLE runs retrieval on both draft and target sides simultaneously to fill the precision-efficiency gap.
  • Iterative Retrieval Drafter: Iterative draft retrieval generates more than C tokens within one target forward-pass interval, with effective draft length approximately C × (1 + AMT).The draft retrieves phrases sequentially and appends each phrase to the context for the next iteration.
  • Target-Guided Verification: Target-guided verification retrieves high-confidence multi-token guidance to mitigate rollback from mid-sequence draft errors.The target retrieval can provide multi-token pre-verification and forward guidance for subsequent unverified tokens.
  • Target-Guided Verification: DOUBLE’s workflow uses target retrieval for both correction of rejected tokens and extension beyond the drafted sequence.Figure 4 identifies these operations as Correction and Extension.

1 Multi-token Pre-verify

DOUBLE combines draft-side iterative retrieval with target-side retrieval guidance, using the latter to correct mismatches and extend verified output without rollback. Across benchmarks and model configurations, this design improves speedup while preserving acceptance, including under stochastic sampling.

  • Multi-token Pre-verify: The target model matches the draft chain against a retrieved guide, replacing the first mismatch and appending remaining target tokens to avoid pipeline stalls.The final sequence concatenates the verified draft prefix with the target-guidance suffix, unifying correction and extension.
  • Main Results: 1.6×–5.3× speedups across five benchmarks show that DOUBLE exceeds the PSD ceiling and improves throughput over representative retrieval and parallel baselines.On the Qwen3-14B pair, DOUBLE reaches 1.89× on CNN/DM versus PEARL’s 1.28×; on Deepseek-33B, speedup rises from 1.96× to 4.05×.
  • Main Results: 5.33× and 2.84× speedups on HumanEval for LLaMA-3.3 and Qwen3-32B, respectively, exceed or match the training-based EAGLE-3 despite zero training.The reported comparison positions DOUBLE as a training-free alternative to expensive architectural modifications.
  • Multi-token Pre-verify: Target guidance reduces rejection loss by correcting draft errors and preserving high acceptance; removing it lowers Mean Accepted Tokens from 14.35 to 11.5.The target-side component acts as a correction filter for tokens otherwise meant to be rejected.
  • Ablation Study: Retrieval depth d is selected as 10 because Mean Accepted Tokens saturate beyond d = 10 while speedup fluctuates and longer chains reduce accuracy.The datastore initialization likewise selects K = 10, where gains saturate at 9.5 MB and further rounds add storage with diminishing returns.

6 Related Work

Prior work improves speculative decoding through trained auxiliary modules, retrieval on one model side, or parallel execution. DOUBLE combines retrieval across draft and target models to address the resulting precision–efficiency trade-off and speed ceiling.

  • Speculative Decoding: Training-based speculative decoding methods improve acceptance, while training-free verification trees provide an alternative; recent methods still use sequential draft-then-verify execution.The related-work discussion contrasts auxiliary modules such as Medusa and EAGLE with tree-based methods such as SpecInfer.
  • Parallel Speculative Decoding: Parallel speculative decoding overlaps drafting and verification, but remains bounded by the draft-to-target speed ratio and is sensitive to latency penalties from mid-token rejection.PEARL and SpecBranch are cited as examples of pipelined execution.
  • Retrieval Speculative Decoding: Retrieval-based methods typically accelerate either the target side or draft side, creating a precision–efficiency dilemma that DOUBLE addresses through coordinated retrieval on both models.The paper frames this coordination as a way to break the theoretical ceiling of existing parallel frameworks.

7 Conclusion

DOUBLE combines iterative draft-side retrieval with target-side retrieval in a parallel speculative decoding framework. It reports training-free, lossless speedups while identifying unified retrieval settings as a limitation.

  • The method proposes double retrieval on both draft and target models within a parallel speculative decoding framework.
  • DOUBLE uses iterative drafting to expand candidate lengths beyond theoretical limits and target-side retrieval to repair potential rejections.
  • The framework achieves training-free and lossless speedup, reaching 5.3× against EAGLE3 and establishing a new SOTA for LLM inference.
  • DOUBLE uses a unified datastore and synchronized retrieval depth, which may not fully exploit the distinct capabilities of the two models.
  • DOUBLE inherits the biases and safety risks of its underlying models and does not mitigate their existing risks.

A Procedures of DOUBLE

This section presents the procedures and formal setup underlying speculative decoding. It defines the expected multi-round token length and the standard speedup assumptions used for analysis.

  • The procedures are described in Algorithm 1 and Algorithm 2 for Double Retrieval Speculative Parallelism.
  • The formal analysis defines α as token acceptance rate, γ as draft length, and C as the target-to-draft latency ratio Tp/Tq.
  • The expected token length over k rounds combines k − 1 fully accepted rounds with a final rejected round modeled through the acceptance rate α.
  • The speedup derivation assumes verification time dominates under compute-bound execution.

B.3 Proof of Theorem 3 (Speedup Ceiling)

Theorem 3 establishes that parallel speculative decoding improves on sequential speculative decoding but remains bounded by the draft-to-target speed ratio. The proof derives this ceiling under optimal pipelining and perfect acceptance.

  • Theorem 3 states the speedup ordering SSD ≤ SPSD ≤ C.
  • PSD pipelines drafting and verification, but the previous round’s verification token is not free for drafting.
  • Under optimal pipelining, the per-round cost is dominated by max(γTq, Tp), typically with γ approximately equal to C.
  • The proof introduces the nonnegative shift term ∆ = (k − 1)C when expressing SPSD through SSD components.
  • Even with perfect acceptance, the generated length per round is limited to γ, yielding SPSD < C.

C Evaluation Details

The evaluation covers multiple model families and five task types, comparing DOUBLE with standard, retrieval-based, parallel, and training-based baselines. Experiments emphasize wall-time speedup, accepted length, and latency-critical batch size one, while also examining high-concurrency scalability.

  • Tasks and Datasets: DOUBLE is evaluated on LLaMA-2, LLaMA-3, Deepseek-Coder, and Qwen3 configurations spanning lightweight to large-scale models.
  • Tasks and Datasets: The benchmarks cover code generation, mathematical reasoning, summarization, and instruction following through HumanEval, GSM8K, CNN/DM, Alpaca, and MT-Bench.
  • Baselines: The comparison includes standard SD, target-side retrieval, draft-side retrieval, PEARL, and the training-based method EAGLE3.
  • Implementation and Metrics: Experiments use 8 NVIDIA A100 GPUs, greedy sampling, batch size 1, and model parallelism for 70B models.
  • Implementation and Metrics: The reported metrics include Wall-Time Speedup, Mean Accepted Length, and Average Matched Tokens, with AMT determining effective speedup.
  • Scalability: The primary evaluation targets latency-critical scenarios with batch size 1, while larger batches may expose compute saturation and dynamic-tree overhead.
  • Scalability: At batch size 16, EAGLE-3 reaches 1.13×, whereas NANO-PEARL sustains 1.73× speedup; DOUBLE is described as suited to this linear-retrieval architecture.

D.2 Proof of Lossless Acceleration

DOUBLE preserves the target model’s output distribution through target-guided verification in both greedy and stochastic decoding. Exact-match experiments show unchanged accuracy across temperatures while retrieval caching supports the lossless acceleration design.

  • DOUBLE’s Target-Guided Verification strictly preserves the target output distribution p(x) under both greedy and stochastic decoding.
  • Greedy Decoding (T = 0): In greedy decoding, replacing a rejected draft token with the target token is equivalent to residual rejection sampling.
  • Greedy Decoding (T = 0): In greedy decoding, subsequent target-retrieved tokens remain valid because they follow the corrected target-model path.
  • Stochastic Sampling (T > 0): In stochastic decoding, rejected tokens use residual-distribution sampling, and subsequent target guidance is discarded after rejection.
  • Empirical Verification: 0.93, 0.92, and 0.89 are DOUBLE’s GSM8K accuracies on LLaMA-3.3-70B at T = 0, 0.5, and 1.0, matching the Vanilla baseline.The reported speedup is 3.67×.
  • Retrieval Cache: The rejected-token cache improves average speedup from 2.14× to 2.30× across benchmarks.

D.4 Time Consumption

DOUBLE’s runtime is dominated by model computation, while retrieval adds little overhead; however, communication and KV-cache operations limit realized wall-time speedup. The method occupies the high-precision, high-efficiency regime relative to single-sided retrieval variants.

  • Latency Breakdown: 86.2% of Retrieval Forward latency is Model Forward, while Retrieval contributes only 1.9% overhead.
  • Engineering Gap Analysis: Communication and KV-cache operations create a gap between retrieval-based AMT gains and realized wall-time speedups.
  • Precision-Efficiency Analysis: Without draft retrieval, autoregressive drafting remains constrained by the theoretical speed ceiling C and yields low efficiency.
  • Precision-Efficiency Analysis: Without target retrieval, limited draft-model capacity causes frequent verification failures, producing low AMT and suboptimal speedups.
  • Precision-Efficiency Analysis: DOUBLE achieves AMT > 0.9 and Speedup > 4.0×, occupying the scatter plot’s Pareto-optimal top-right regime.

D.6 Analysis of Memory-Constrained Scenarios

DOUBLE adapts to different hardware settings through independent deployment, pipeline interleaving, or serialized execution. It retains useful acceleration under constrained resources, while its strongest configuration assumes sufficient hardware separation.

  • Deployment Modes: DOUBLE is designed for parallel computation rather than the underutilized hardware of draft-then-verify execution.
  • Resource-Abundant Scenarios: In resource-abundant environments, placing draft and target models on independent processors prevents memory contention from slowing target inference.
  • Memory-Constrained Scenarios: Under shared-GPU constraints, modified Pipeline Parallelism interleaves draft computation on an idle GPU with target computation on the active GPU.
  • Memory-Constrained Scenarios: Pipeline Parallelism preserves approximately 90% of DOUBLE’s ideal acceleration in memory-constrained scenarios.
  • Scope and Future Work: DOUBLE currently uses a standard draft model, leaving integration with EAGLE’s dedicated draft design as future work.
Loading 2601.05524v3…