Skip to content

SuffixDecoding: Extreme Speculative Decoding for Emerging AI Applications

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SuffixDecoding is a model-free speculative decoding method that builds suffix trees over prompt and prior-output token sequences to exploit the long, repetitive token patterns characteristic of agentic LLM workloads. By adaptively scaling speculation depth to pattern-match length, it achieves up to 5.3× speedup over vanilla decoding on agentic benchmarks—2.8× faster than EAGLE-2/3 and 1.9× faster than Token Recycling.

Problem

Standard speculative decoding methods (model-based like EAGLE-2/3, model-free like Prompt Lookup Decoding and Token Recycling) are designed for diverse, single-turn requests. Agentic workloads—multi-agent pipelines, self-refinement loops, self-consistency sampling—produce highly repetitive, long token sequences that these methods fail to exploit: model-based methods incur GPU overhead that becomes prohibitive at long speculation lengths, while existing model-free methods use fixed speculation depths regardless of acceptance likelihood, wasting verification compute.

Method

SuffixDecoding maintains two suffix trees (using Ukkonen's online construction): a global tree over previous request outputs and a per-request tree over the current prompt and generation. At each decoding step, it pattern-matches the most recent tokens against both trees to find candidate continuations. A speculation tree is grown greedily by selecting leaf expansions with highest estimated acceptance probability D(N) (product of per-token empirical frequencies along the path). The tree size is bounded by MAX_SPEC(p) = αp, where p is the pattern-match length—longer matches justify larger speculation budgets. Across all combinations of tree source and pattern length, the candidate with highest SCORE(T) = Σ D(N) is selected for a single parallel LLM verification pass. A hybrid mode falls back to a model-based speculator (e.g., EAGLE-3) when SCORE falls below a threshold τ, covering non-repetitive workloads. Draft token generation costs ~20 µs/token with zero GPU overhead.

Key Contributions

  • Suffix-tree-based model-free speculative decoding tailored to agentic workload repetition patterns
  • Adaptive speculation depth (MAX_SPEC = αp) that scales aggressiveness to pattern-match confidence, avoiding fixed-length waste
  • Frequency-based scoring function to select the best speculation tree across multiple candidate trees (two suffix trees × multiple pattern lengths)
  • Hybrid fallback mechanism enabling a single deployment to handle both agentic (repetitive) and open-ended (diverse) workloads
  • vLLM integration with end-to-end evaluation on live OpenHands/SWE-Bench showing 4.5× speculative speedup including prefill and code execution

Results

  • AgenticSQL: 5.3× speedup over vanilla decoding; 2.8× over EAGLE-2/3; 1.9× over Token Recycling; 6.3 mean accepted tokens/step vs. 3.6 (EAGLE-3) and 3.2 (Token Recycling)
  • SWE-Bench (simulated): 2.5× over vanilla; 1.7× over PLD (EAGLE-2/3 fail on >8192-token contexts)
  • SWE-Bench end-to-end (vLLM, live OpenHands): 1.8–4.5× speculative speedup; 1.3–3× over PLD; preserves 37.2% SWE-Bench Verified score
  • Hybrid (SuffixDecoding + EAGLE-3) on Spec-Bench: 2.5× speedup, marginally outperforming standalone EAGLE-3 (2.4×)
  • Hybrid on AgenticSQL: 4.1× speedup, better than standalone EAGLE-2/3 (1.9×)
  • All experiments on Llama-3.1-8B-Instruct, single H100 GPU (except end-to-end: 4× H100 tensor parallel)

Limitations

  • Performance advantage diminishes on non-agentic, open-ended workloads where token repetition is low (underperforms EAGLE-2/3 on Spec-Bench without hybrid fallback)
  • Global suffix tree requires CPU memory proportional to historical output volume; cache eviction policy needed after ~1 month of output accumulation at typical server scale
  • Ablations show that combining both suffix trees can occasionally hurt performance on individual subtasks (Enrich, Extract in AgenticSQL) due to suboptimal tree selection
  • Evaluation limited to greedy sampling; behavior under temperature-sampled or beam-search decoding not assessed
  • Hybrid threshold Ï„ requires tuning per workload mix; miscalibration degrades either agentic or open-ended performance

Relevance to Agentic AI / LLM Agents

Inference latency is a primary bottleneck for deployed LLM agents, particularly in multi-agent pipelines and self-refinement loops where dozens to hundreds of LLM calls are chained. SuffixDecoding directly targets this bottleneck by recognizing that agentic workloads have fundamentally different statistical properties than single-turn chat—high token repetition across requests—and exploiting this at the inference-system level rather than the algorithm level. The 4.5× end-to-end task-completion speedup on SWE-Bench with OpenHands demonstrates production-grade impact, and the model-free design means it requires no retraining or draft-model alignment, making it drop-in compatible with any new agent-specialized LLM. For researchers building or studying agentic systems, this work establishes that workload-aware inference optimization is a high-leverage lever orthogonal to prompt engineering, planning algorithms, or model capability.