Adaptix: Adaptive Draft-Verification for Efficient LLM Decoding

News and Updates:

🚀 Dec 2024: Our paper Adaptive Draft-Verification for Efficient Large Language Model Decoding is accepted at the AAAI 2025. See you in Philadelphia!🌎

To address these issues, we introduce a novel methodology called Adaptix, which  is a kind of Retrieval Based Speculative Decoding method 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 accelerates the decoding process while maintaining high accuracy, making it suitable for deployment in a wide range of practical applications. 

Speed Up on Vicuna-7B

 Advantages of Adaptix:

Pipeline of Adaptix:

This figure illustrates the data processing workflow of Adaptix. Initially, the input tokens undergo preprocessing to calculate their tri-grams, which serve to update the tri-gram matrix. Subsequently, the updated matrix, in conjunction with the last two tokens of the input, is used to retrieve potential token sequences. These sequences are ranked, and the top-k sequences are selected, and then appended to the original input. Finally, these extended sequences are inputted into the Large Language Model for prediction.

Experimental Results of Adaptix:

In the experiments, we compare the efficacy of different baselines applied to various models, utilizing three datasets: MT-Bench, Human-Eval, and Alpaca. We focus on metrics of Accept Length, Latency, and Speedup Ratio.

On the three datasets. Adaptix consistently demonstrates lower latency, 

For instance, on MT-Bench, Adaptix achieves a latency of 12.95 ms for vicuna-7B, which is lower than REST (16.31 ms), REST Single Thread (17.36 ms), and Lookahead (18.93 ms). 

Notably, the memory required for Adaptix (574MB) is only 5.6% of that required for REST (12GB). Even when Adaptix uses a smaller corpus (253MB, which is just 2.5% of REST's requirements), it still achieves lower latency than REST. This trend is also observed on Alpaca, where Adaptix achieves a latency of 12.81 ms for vicuna-7B, compared to 14.24 ms for REST, 14.58 ms for REST Single Thread, and 18.73 ms for Lookahead.

The accept length results in this table indicate the quality of the generated outputs, with longer accept lengths suggesting more coherent and contextually relevant text. Our method, Adaptix, outperforms other methods across different models on all three datasets, showcasing its superior language generation capabilities.

Speedup ratio are used to evaluate the efficiency. 

Adaptix consistently shows a significant improvement in speed up across all datasets.

This efficiency is noticeable on the MT-Bench, Alpaca and Human-Eval datasets, where Adaptix not only reduces latency but also enhances the overall processing speed.

For instance, Adaptix achieves a speedup of 1.92x on MT-Bench with the vicuna-13B model, outperforming REST, REST Single Thread, and Lookahead. On the HumanEval dataset, the vicuna-33B model, for example, demonstrates a speedup of nearly 2.5x when using Adaptix .

Effect of MCTS : 

 The result of Vicuna-7B and Vicuna-13B models on the MT-Bench dataset shows the impact of different MCTS search counts on performance. We find that for both models, increasing the number of searches improves performance, while the optimal number varies by model size. The average exact length and latency are plotted against the number of searches, illustrating the trade-off between performance and computational cost. 

As shown in the figure, there is a notable improvement in the average exact length as the number of searches increases, along with an increase in latency, indicating a balance between search depth and generation time.

We further compare greedy search with MCTS(full traversal is not feasible due to the huge search space) while keeping the number of 150 search iterations constant.

The results show that the average accept length of the greedy search is only 1.493, significantly lower than that obtained by MCTS, demonstrating the superiority of MCTS in efficiently managing the vast decision spaces.