Research map / Large language models / Language, safety and interpretability

Adaptive Draft-Verification for Efficient Large Language Model Decoding

AAAI 2025 · Large language models › Language, safety and interpretability · approach: Parallel and early-exit decoding · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ADED, a fine-tuning-free draft-verification LLM decoding method that builds drafts with an adaptive tri-gram matrix guided by MCTS and PUCT, reporting lower latency than REST and Lookahead decoding on Vicuna and LLaMA2 models.

Problem

Autoregressive LLM decoding requires one forward pass per token, which is slow for latency-sensitive use; existing draft-verification methods either need draft-model fine-tuning or use fixed retrieval schemes that do not adapt to the LLM's output distribution.

Approach

Replace fixed retrieval drafts with a tri-gram-matrix LLM representative that is updated with the LLM's own outputs during decoding, and search over draft candidates with an MCTS whose PUCT-style score balances the tri-gram probabilities against exploration.

Key results

• On MT-Bench with Vicuna-7B, ADED latency is 12.95 ms versus 16.31 ms for REST and 18.93 ms for Lookahead, with accept length 2.42 versus 1.97 for REST.
• The paper reports up to 2.5x speedup and about 20% average acceptance-rate improvement over existing methods.
• A greedy-search ablation on MT-Bench gives an average accept length of 1.493, below the MCTS result.

Measured effects reported in the paper

Surprising findings

• Bi-gram and 4-gram variants reach accept lengths of only 1.80 and 1.82 versus 2.30 for tri-grams, so the choice of n-gram order matters a lot.
• Using a smaller corpus (253MB, 121k conversations) still gives lower latency than REST, with only a small accept-length drop (2.30 vs 2.42).

Limitations

• Retrieval-based drafts do not yet match the accuracy of draft-model methods, per the authors.
• MCTS adds computation overhead, leaving the acceleration ratio below the theoretical maximum accept length.
• Evaluation is limited to five models from the Vicuna and LLaMA2 families and three datasets, all with greedy sampling in the main experiments.

Experimental setup

Datasets: The Stack UltraChat ShareGPT MT-Bench Alpaca HumanEval

Benchmarks: MT-Bench Alpaca HumanEval

Metrics: latency average accept length speedup ratio

Baselines: REST REST Single Thread Lookahead Decoding Autoregressive decoding

Builds on: Speculative Decoding REST Lookahead Decoding PUCT Medusa

Closest papers by meaning

• Multi-Branch Self-Drafting for LLM Inference Acceleration (AAAI 2025 · similarity 0.93)
• AdaDecode: Accelerating LLM Decoding with Adaptive Layer Parallelism (ICML 2025 · similarity 0.90)
• Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration (NeurIPS 2024 · similarity 0.90)
• Free Draft-and-Verification: Toward Lossless Parallel Decoding for Diffusion Large Language Models (NeurIPS 2026 · similarity 0.89)
• Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.89)
• Learning To Draft: Adaptive Speculative Decoding with Reinforcement Learning (ICLR 2026 · similarity 0.89)