Adaptive Draft-Verification for Efficient Large Language Model Decoding

Xukun Liu, Bowen Lei, Ruqi Zhang, Dongkuan Xu

Abstract

Large Language Models (LLMs) typically rely on autoregressive decoding, a process that is computationally expensive and memory-bandwidth intensive. We present Adaptix, a fine-tuning-free framework designed to accelerate LLM decoding by up to 2.5x. Adaptix utilizes a dynamic tri-gram matrix updated in real-time alongside a Monte Carlo Tree Search (MCTS) draft maker to generate high-quality candidate tokens. These candidates are verified by the target LLM in a single forward pass using tree attention. Our results across multiple benchmarks demonstrate significant speedups and improved token acceptance rates while maintaining extreme memory efficiency compared to existing retrieval-based methods.

Introduction

The standard autoregressive decoding paradigm in LLMs—predicting one token at a time—creates a significant bottleneck in real-time applications. While techniques like Speculative Decoding attempt to mitigate this by using smaller "draft" models to predict multiple tokens ahead, they often require expensive training of auxiliary models or rely on static retrieval databases that fail to adapt to specific contexts.

Comparison of Adaptix with existing decoding strategies like Speculative Decoding and REST.

Adaptix addresses these limitations by introducing an adaptive, search-based drafting system. Unlike prior methods, it does not require fine-tuning and dynamically adjusts its drafting strategy based on the model's actual output history.

The Adaptix Framework

Adaptix consists of three core components that work in tandem to optimize the drafting process:

  • Adaptive Tri-gram Matrix: Instead of a complex neural network, Adaptix employs a lightweight tri-gram matrix to track token sequences. This matrix is initialized from a corpus but is updated dynamically during inference. As the LLM generates accepted tokens, the tri-gram statistics are refined, allowing the drafter to align more closely with the model's specific distribution for the current task.
  • MCTS Draft Maker: To navigate the potential sequences suggested by the tri-gram matrix, Adaptix uses Monte Carlo Tree Search (MCTS). This approach balances the exploitation of high-probability sequences with the exploration of diverse paths, ensuring the generated drafts are both likely and varied.
  • Tree Attention Verification: Multiple draft sequences are organized into a tree structure. The target LLM then verifies all branches of this tree simultaneously in one forward pass. This "tree attention" mechanism maximizes the number of tokens that can be accepted in a single cycle, significantly reducing total latency.

Experimental Evaluation

We evaluated Adaptix using a variety of models, including Vicuna (7B, 13B, 33B) and LLaMA2-chat (7B, 13B). Performance was measured across three major benchmarks: MT-Bench (general reasoning), Alpaca (natural language tasks), and HumanEval (Python code generation). Initial tri-gram distributions were distilled from conversational (UltraChat) and code-based (The Stack) datasets.

Results and Discussion

Adaptix demonstrates robust performance gains across all tested models and benchmarks.

Decoding speedup (tokens per second) of Adaptix vs. standard Auto-Regressive decoding across MT-Bench, Alpaca, and Human-Eval.

Performance Gains

As shown in the results, Adaptix achieves up to a 2.5x speedup in decoding latency. In structured tasks like code generation (HumanEval), speedups reached as high as 2.69x. The average token acceptance rate improved by approximately 20% over baselines such as Lookahead Decoding and REST.

Efficiency and Robustness

A key advantage of Adaptix is its memory efficiency. It requires only ~574MB of memory, a fraction of the 12GB needed by state-of-the-art retrieval methods like REST. Furthermore, the system is robust to variations in sampling parameters like "top-p" and "temperature," maintaining its speedup advantages where other speculative methods often falter.

Conclusion

Adaptix provides a highly efficient, adaptive solution for accelerating LLM inference without the need for additional model training. By combining real-time tri-gram updates with MCTS, it offers a scalable path toward more responsive AI systems. Future work will focus on scaling these techniques for massive production environments and exploring higher-order n-gram structures for even greater drafting accuracy.

Summary updated

Abstract

Large language model (LLM) decoding involves generating a sequence of tokens based on a given context, where each token is predicted one at a time using the model's learned probabilities. The typical autoregressive decoding method requires a separate forward pass through the model for each token generated, which is computationally inefficient and poses challenges for deploying LLMs in latency-sensitive scenarios. The main limitations of current decoding methods stem from their inefficiencies and resource demands. Existing approaches either necessitate fine-tuning smaller models, which is resource-intensive, or relying on fixed retrieval schemes to construct drafts for the next tokens, which lack adaptability and fail to generalize across different models and contexts. To address these issues, we introduce a novel methodology called Adaptix, which accelerates LLM decoding without requiring fine-tuning. Our approach involves an adaptive draft-verification process that evolves over time to improve efficiency. We utilize a tri-gram matrix-based LLM representation to dynamically approximate the output distribution of the LLM, allowing the model to adjust to changing token probabilities during the decoding process. Additionally, we implement a draft construction mechanism that effectively balances exploration and exploitation, ensuring that the drafts generated are both diverse and close to the true output distribution of the LLM. The importance of this design lies in its ability to optimize the draft distribution adaptively, leading to faster and more accurate decoding. Through extensive experiments on various benchmark datasets and LLM architectures, we demonstrate that Adaptix significantly accelerates the decoding process while maintaining high accuracy, making it suitable for deployment in a wide range of practical applications.
BibTeX
@inproceedings{liu2025adaptive,
  author = {Xukun Liu and Bowen Lei and Ruqi Zhang and Dongkuan Xu},
  title = {{Adaptive Draft-Verification for Efficient Large Language Model Decoding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i23.34647},
}
Figure