Skip to content

AdaPLD: Adaptive Retrieval and Reuse for Efficient Model-Free Speculative Decoding

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Speculative Decoding, Model-Free Inference, Context Reuse, Adaptive Retrieval, Draft Tree Construction

TL;DR

AdaPLD is a training-free, model-free speculative decoding framework that breaks the candidate reachability bottleneck via lexical-first matching with semantic embedding fallback, and mitigates the brittleness of deterministic span copying through branched draft tree construction with successor extensions, delivering up to 3.10× end-to-end decoding speedup across diverse generation, editing, and reasoning benchmarks while strictly preserving the target model's output distribution.

Background & Motivation

Large language models (LLMs) have achieved remarkable capabilities across open-ended generation, code manipulation, and multi-step complex reasoning, yet their practical serving remains fundamentally bottlenecked by autoregressive decoding latency. Because generating each output token requires a full sequential forward pass through the deep network conditioned on prior sequence states, GPU memory bandwidth becomes severely underutilized. Speculative decoding (SD) breaks this sequential dependency by employing a lightweight draft proposer to generate multiple speculative tokens and verifying them in parallel with the target model within a single forward pass. However, conventional speculative sampling relies on training, maintaining, and serving an auxiliary draft language model, which incurs substantial GPU memory overhead, domain transfer friction, and engineering deployment complexity. Model-free speculative decoding addresses these practical burdens by entirely eliminating auxiliary models, instead constructing draft tokens directly from the context and model activations already present during generation.

Despite this operational elegance, existing reuse-based model-free approaches suffer from fundamental limitations across both the retrieval and reuse construction stages. In the retrieval phase, current paradigms—such as Prompt Lookup Decoding (PLD) and suffix-based matching—rely almost exclusively on exact lexical overlap (such as token n-grams). When the most recently decoded token does not appear verbatim in the observed prompt or generation history due to minor surface-form variations, synonyms, or structural shifts, lexical retrieval immediately yields an empty candidate set. Under this "no-hit" condition, speculative decoding completely fails and collapses back to single-token autoregressive generation, even when rich semantically equivalent contexts are readily accessible. While PLD+ incorporates representation similarity to rerank lexically matched candidates, its semantic scoring operates strictly downstream of lexical filtering, leaving the critical candidate reachability bottleneck entirely unaddressed. In the reuse construction phase, once an anchor is identified, prior methods deterministically copy a single contiguous slice of text from memory. Because local textual anchors naturally support multiple plausible continuation paths, this deterministic single-path assumption is fragile: a mismatch on the very first copied token invalidates the entire speculated sequence, discarding potential acceleration gains.

To overcome the dual bottlenecks of lexical no-hit retrieval failures and deterministic copying brittleness without introducing auxiliary neural networks, this paper investigates how to integrate adaptive semantic reachability and non-linear continuation exploration into a unified, zero-overhead framework. Core idea: integrate a strict lexical-first retrieval policy backed by lightweight embedding-similarity fallback to eliminate no-hit candidate failures, while expanding retrieved anchors into compact draft trees composed of distribution-derived branches and successor extensions to absorb local continuation uncertainty.

Method

Overall Architecture

AdaPLD operates over a unified memory consisting of the input prompt concatenated with the decoded token history. At each decoding iteration, the framework executes four tightly integrated stages: adaptive two-tier candidate retrieval, hidden-state compatibility reranking, multi-branch and successor draft tree construction, and target model tree attention verification. The system first checks for exact lexical matches against the latest decoded anchor; if no candidates emerge, it seamlessly activates cosine-similarity fallback over pre-cached token embeddings. Once candidate anchors are ranked via hidden-state prefix alignment, AdaPLD extracts a primary copy continuation (if lexically anchored) and branches over alternative next tokens using the model's top-\(K\) cached logits, appending a single-token successor extension to each branch. The resulting compact draft tree is verified in parallel via tree attention under standard speculative rejection sampling, guaranteeing strict mathematical losslessness.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Observed Context Memory<br/>M_i = [Prompt x, History y_<i]"] --> B["Adaptive Two-Tier Retrieval<br/>Exact Lexical Match / Embedding Fallback"]
    B --> C["Prefix Representation Reranking<br/>Intermediate Layer Hidden-State Alignment"]
    C --> D["Multi-Branch Hypothesis Expansion<br/>Top-K Local Continuation Branches"]
    D --> E["Lightweight Successor Drafting<br/>Single-Token Reused Branch Extension"]
    E --> F["Draft Tree Parallel Verification<br/>Tree Attention & Lossless Rejection Sampling"]
    F -->|Accepted Tokens / Residual Correction| G["Context Update & Next Step"]

Key Designs

1. Adaptive Two-Tier Retrieval: Lexical no-hit bottleneck -> Lexical-first matching backed by token embedding fallback -> Maximized candidate recall while preserving exact match precision
To resolve the vulnerability where surface-form variations lead to empty candidate sets, AdaPLD implements a prioritized backoff retrieval mechanism. At decoding step \(i\), let \(a_i = y_{i-1}\) be the query anchor and \(M_i = \text{concat}(x, y_{<i})\) be the unified context. AdaPLD initially attempts exact lexical retrieval: $\(C_{\text{lex}} = \{j \mid 1 \le j < |M_i|, M_{i,j} = a_i\}\)$ If \(C_{\text{lex}} \neq \emptyset\), these exact matches are directly retained as the candidate set \(C_i = C_{\text{lex}}\). If \(C_{\text{lex}} = \emptyset\), rather than abandoning speculation, the system dynamically falls back to semantic retrieval by computing cosine similarity between the query token embedding \(e_{a_i}\) and all historical token embeddings \(e_{M_{i,j}}\) from the target model's input embedding table: $\(C_{\text{sem}} = \{j \mid 1 \le j < |M_i|, \cos(e_{M_{i,j}}, e_{a_i}) \ge \tau\}\)$ where \(\tau\) is a similarity threshold (empirically set to 0.1). Because token embeddings are statically cached model parameters, this fallback involves only a lightweight vector-matrix dot product, incurring negligible runtime cost while reliably bridging surface-form disparities.

2. Prefix Representation Reranking: Polysemous or noisy candidates -> Intermediate layer hidden-state cosine compatibility -> Contextually optimal anchor selection
Because a frequent token may appear dozens of times in a long context, or semantic fallback may return multiple candidate positions, selecting an improper anchor leads to low draft acceptance. AdaPLD applies hidden-state reranking over the candidate set \(C_i\). For each candidate position \(j \in C_i\), it extracts the hidden representation \(h_{i,j-1}^{(\ell)}\) at transformer layer \(\ell\) corresponding to the prefix preceding \(j\), and compares it against the prefix representation of the current decoding step \(h_{i,|M_i|-1}^{(\ell)}\): $\(s(j) = \cos\left(h_{i,j-1}^{(\ell)}, h_{i,|M_i|-1}^{(\ell)}\right), \quad j^\star = \arg\max_{j \in C_i} s(j)\)$ By aligning prefix hidden states rather than isolated token identities, this step effectively filters out superficial matches and selects the anchor position \(j^\star\) whose syntactic and semantic trajectory best mirrors the current generation context.

3. Multi-Branch Hypothesis Expansion: Fragility of single deterministic span copying -> Branching over anchor-conditioned distribution -> Resilient multi-path draft exploration
Recognizing that local context matching often supports diverging next-token paths, AdaPLD departs from naive single-span copying by treating anchor \(j^\star\) as a branching hub. When \(j^\star\) is derived from lexical matching (\(C_{\text{lex}} \neq \emptyset\)), AdaPLD extracts a main direct continuation span \(\hat{y}_{i:i+\ell_i-1}^{\text{main}} = M_{i, j^\star+1 : j^\star+\ell_i}\) bounded by maximum length \(\ell_m\). Simultaneously, it queries the target model's next-token distribution conditioned on the anchor prefix, taking the top-\(K\) tokens \(\tilde{B}_i = \text{TopK}(p(\cdot \mid M_{i,\le j^\star}), K)\). To eliminate redundant computation, the first token of the main path is pruned from the branch set: \(B_i = \tilde{B}_i \setminus \{M_{i, j^\star+1}\}\). When the anchor originates from semantic fallback, direct copying is skipped and \(B_i = \tilde{B}_i\). Each token \(b \in B_i\) instantiates an independent speculative branch \(\hat{y}_i^{(b)} = b\).

4. Lightweight Successor Drafting: Shallow single-token branch depth -> Secondary anchor retrieval and single-token extension -> Extended multi-token speculative depth
While branching improves local tolerance to continuation uncertainty, a single-token branch yields minimal throughput acceleration upon acceptance. To deepen branch hypotheses with negligible overhead, AdaPLD applies successor drafting to each branch token \(b \in B_i\). Treating \(b\) as a secondary query anchor, the system re-executes the adaptive lexical-first retrieval rule over context positions that possess an observed subsequent token, obtaining secondary candidate set \(C_i^{(b)}\). It selects optimal successor anchor \(j_b^\star = \arg\max_{t \in C_i^{(b)}} \cos(h_{i,t-1}^{(\ell)}, h_{i,j^\star}^{(\ell)})\) via prefix hidden-state similarity, and extends branch \(b\) with the succeeding token: $\(\hat{y}_{i+1}^{(b)} = M_{i, j_b^\star+1}\)$ This operation deepens branch hypotheses from length 1 to length 2, allowing branch paths to deliver multi-token progress during target model verification.

Benchmark & Evaluation Protocol

Experiments are conducted on 8 NVIDIA H20 GPUs in FP16 precision across Vicuna-v1.3 (7B, 13B, 33B) and Qwen3-8B. The evaluation spans three diverse benchmark suites: (1) Input-Guided Generation: Spec-Bench Summarization, Multi-Turn Conversation (MT-bench), and Retrieval-Augmented Generation (RAG); (2) Input-Guided Editing: CodeEditorBench (covering Debug, Polish, Translate, and Switch tasks); and (3) Structured Complex Reasoning: AIME 2024, MATH-500, and MMLU-Pro. Baselines include Autoregressive Decoding (AR), Token Recycling (TR), SAM Decoding (SAMD), Prompt Lookup Decoding (PLD), PLD+, and LogitSpec. Default parameters are set to branch width \(K=8\), maximum draft length \(\ell_m=30\), and semantic threshold \(\tau=0.1\). Verification is performed via tree attention under standard speculative sampling.

Key Experimental Results

Main Results

Target Model Method Spec-Bench (Sum) Spec-Bench (RAG) Spec-Bench (MT) CodeEditor (Avg.) MATH-500 AIME 2024 Decoding Speed (#tok/s)
Vicuna-7B AR 1.00× 1.00× 1.00× 1.00× 1.00× 1.00× 59.55
TR 1.81× 1.61× 2.05× 2.04× 2.36× 2.22× 109.11
SAMD 2.64× 1.70× 1.70× 1.87× 2.32× 2.78× 120.39
PLD 2.18× 1.53× 1.39× 1.56× 1.74× 2.01× 100.23
PLD+ 2.77× 1.71× 1.63× 1.87× 2.42× 2.61× 121.72
LogitSpec 2.59× 1.70× 1.88× 2.08× 2.68× 3.15× 123.17
AdaPLD (Ours) 3.02× 1.93× 1.83× 2.00× 2.55× 2.98× 135.08
Vicuna-13B AR 1.00× 1.00× 1.00× 1.00× 1.00× 1.00× 47.87
TR 1.32× 1.26× 1.48× 1.54× 1.65× 1.64× 65.06
SAMD 2.17× 1.62× 1.60× 2.52× 1.95× 2.34× 86.30
PLD 1.90× 1.46× 1.34× 1.78× 1.64× 1.73× 75.09
PLD+ 2.22× 1.60× 1.50× 2.41× 1.98× 2.36× 85.09
LogitSpec 2.03× 1.60× 1.65× 2.21× 2.12× 2.33× 84.40
AdaPLD (Ours) 2.45× 1.79× 1.70× 2.71× 2.26× 2.56× 94.88
Vicuna-33B AR 1.00× 1.00× 1.00× 1.00× 1.00× 1.00× 27.43
TR 1.22× 1.15× 1.25× 1.35× 1.41× 1.37× 33.18
SAMD 1.91× 1.41× 1.53× 2.85× 1.75× 1.84× 44.34
PLD 1.66× 1.19× 1.28× 2.11× 1.53× 1.50× 37.85
PLD+ 1.95× 1.38× 1.48× 2.90× 1.83× 1.86× 43.98
LogitSpec 1.65× 1.22× 1.30× 2.14× 1.64× 1.60× 38.10
AdaPLD (Ours) 2.10× 1.50× 1.62× 3.10× 2.02× 2.10× 47.70

Ablation Study & Retrieval Hit-Rate Analysis

Component Configuration MT SUM RAG Debug Polish Translate Switch Average Speedup Description
Full AdaPLD 1.70× 2.45× 1.79× 2.28× 2.34× 1.70× 4.51× 2.40× Full architecture on Vicuna-13B
w/o Successor Drafting 1.60× 2.41× 1.77× 2.26× 2.34× 1.69× 4.51× 2.37× Removes secondary single-token branch expansion
w/o Embedding Fallback (Lexical-Only) 1.62× 2.37× 1.74× 2.20× 2.23× 1.63× 3.91× 2.24× Omits semantic retrieval; drops 0.60× on Switch task
w/o Branch & Successor Drafting 1.53× 2.25× 1.64× 2.03× 2.07× 1.51× 4.22× 2.18× Reduces to single deterministic span copying

Key Findings

  • Branch and successor drafting are decisive for robust reuse: Eliminating both branch and successor drafting causes the average speedup to drop from 2.40× to 2.18×, representing the largest degradation across all component ablations. This demonstrates that multi-path exploration is critical to resolving continuation uncertainty.
  • Semantic fallback effectively mitigates the lexical no-hit crisis: Empirical hit-rate profiling reveals that exact lexical matching achieves an initial hit rate of only 61.17%–73.43% across benchmarks. Semantic fallback successfully recovers 67.37%–80.07% of the remaining lexical-miss cases, contributing over 20% absolute hit-rate gain across all tasks.
  • Search budget exhibits clear saturation dynamics: Varying the branch width \(K\) from 2 to 64 steadily increases the mean accepted tokens, but verification overhead escalates concurrently. The net speedup peaks around \(K \in [8, 16]\) and degrades sharply at \(K=64\). Similarly, maximum draft length reaches optimal efficiency at \(\ell_m = 30\), beyond which verification costs outweigh reuse depth.
  • System profiling demonstrates minimal computational overhead: Detailed latency profiling on Vicuna-33B indicates that semantic fallback, hidden-state reranking, branch construction, and successor drafting collectively consume only 0.212 ms per speculative step, representing just 0.53% of the target model's forward verification pass (39.195 ms).

Highlights & Insights

  • Strictly prioritized retrieval hierarchy: Rather than blindly relying on heavy vector search or dense indexing, AdaPLD preserves \(O(1)\) exact lexical matching as the primary retrieval path and invokes token embedding cosine similarity strictly as a fallback. This achieves an optimal balance between precision and recall at zero supplementary model cost.
  • Transforming deterministic copying into structured tree expansion: By recognizing that cached target-model logits inherently provide free next-token proposals, AdaPLD enriches copied memory fragments with branched hypotheses and short successor reuse steps, effectively converting fragile linear spans into resilient speculative trees.
  • Effective context self-reuse in complex reasoning: Even in tasks without direct input-copying requirements (such as AIME 2024 and MATH-500), AdaPLD achieves over 2.5× speedup by harvesting reusable syntactic structures and intermediate derivation patterns from the model's own unfolding chain-of-thought traces.

Limitations & Future Work

  • Dependency on contextual grounding: As a model-free reuse paradigm, performance gains naturally depend on the presence of reusable textual anchors within the prompt or generation history. In unconstrained, free-form creative generation with sparse prompt guidance, reuse opportunities diminish, resulting in modest acceleration.
  • Static token-level embedding granularity: Semantic fallback currently relies on static single-token embedding similarity. While computationally inexpensive, token-level matching cannot capture phrase-level semantics or deeper structural relationships. Extending semantic fallback to lightweight phrase-level representations remains a promising avenue.
  • Static draft construction hyperparameters: The current system employs fixed hyperparameter configurations (branch width, copy length, and similarity threshold). Dynamically adjusting draft tree topology conditioned on generation uncertainty or local entropy could further enhance inference throughput.
  • vs PLD & PLD+: Prompt Lookup Decoding (PLD) relies strictly on n-gram matching and deterministic span copying, failing whenever surface forms diverge. While PLD+ reranks lexical candidates using hidden states, it operates solely downstream of exact matching and cannot recover from lexical misses. AdaPLD resolves both issues via adaptive semantic fallback and branched draft trees.
  • vs SAM Decoding (SAMD): SAMD employs a suffix automaton to efficiently locate the longest common substrings in the context memory. However, SAMD remains fundamentally bound to exact lexical matches and lacks semantic recovery mechanisms. AdaPLD offers superior flexibility when surface-form variations occur.
  • vs Learned Speculative Proposers (EAGLE / Medusa / DFlash): Learned speculative decoding architectures require dedicated training and serving of auxiliary models or prediction heads, posing substantial deployment overhead and domain shift risks. AdaPLD is completely training-free, requires zero additional GPU memory, and is universally applicable to any autoregressive LLM.

Rating

  • Novelty: ⭐⭐⭐⭐☆ Elegantly addresses the twin limitations of model-free speculative decoding through adaptive backoff retrieval and branched successor tree construction.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across 7B to 33B model scales, diverse generation/editing/reasoning benchmarks, latency profiling, and ablation studies.
  • Writing Quality: ⭐⭐⭐⭐⭐ Rigorously formulated, logically structured, and supported by thorough empirical diagnostics.
  • Value: ⭐⭐⭐⭐⭐ Highly practical, training-free, and mathematically lossless, providing immediate serving acceleration for production LLM deployments.