Ouroboros: Generating Longer Drafts Phrase by Phrase for Faster Speculative Decoding (2024)

Abstract: Speculative decoding is a widely used method that accelerates the generation process of large language models (LLMs) with no compromise in model performance. It achieves this goal by using an existing smaller model for drafting and then employing the target LLM to verify the draft in a low-cost parallel manner. Under such a drafting-verification framework, drafting efficiency has become a bottleneck in the final speedup of speculative decoding. Therefore, generating longer drafts at less cost can lead to better decoding speedup. To achieve this, we introduce Ouroboros, which can generate draft phrases to parallelize the drafting process and meanwhile lengthen drafts in a training-free manner. The experimental results on various typical text generation tasks show that Ouroboros can achieve speedups of up to 2.4\times over speculative decoding and 3.9\times over vanilla decoding, without fine-tuning draft and target models. Code available at https://github.com/thunlp/Ouroboros.

## introduction benefiting from recent advances in parallel computing devices and distributed training algorithms @xcite , the training time of llms has been significantly shortened. however, it is still challenging to achieve parallelization in model inference because most llms rely on autoregressive generation mechanisms that exhibit sequential dependencies among generated tokens. for these autoregressive llms, they have to generate tokens one by one. to accelerate the inference of llms, typical model compression methods such as quantization @xcite @xcite and pruning @xcite figure 1 : the trade-off between drafting efficiency and effectiveness. the figure illustrates the optimal speculative decoding speed of llama-2-chat-70b on mt-bench @xcite and the corresponding average number of accurate draft tokens at each iteration. @xcite ) may cause model performance degradation and sometimes even require non-negligible additional training costs. to losslessly accelerate the inference of llms, speculative decoding @xcite @xcite has been proposed. given a target llm, speculative decoding selects a much smaller llm as the draft model to generate multiple tokens as a draft. the target llm then reviews the draft in parallel, accepting the longest accurate prefix while discarding the remaining draft tokens. under such a drafting-verification framework, how to efficiently generate long and accurate drafts has become a critical factor in accelerating llm inference. as in figure 1 , we examine the trade-off between draft model size and speculative decoding speed. we observe that larger draft models tend to achieve higher draft accuracy, but the cost of generating drafts also rises, so that medium-sized models offer the best decoding speed. besides, we investigate the trade-off between draft length and speculative decoding speed. our findings indicate that the target model can accept more tokens per iteration on average when the draft is longer, but longer drafts introduce more forward passes required for the draft model, and thus, the opti-mal draft length in speculative decoding is not the largest one. based on the further analysis of the above pilot experimental results, it is not difficult to observe the limitations of speculative decoding regarding drafting efficiency: (1) insufficient draft. drafting too short misses potential acceleration. however, because of the time overhead involved in drafting itself, generating long drafts may result in high costs when these drafts fail. if longer drafts can be generated more efficiently, the acceleration effect will be enhanced significantly. (2) underutilized draft. for current speculative decoding, tokens that are not accepted by the target model are completely discarded, resulting in a high failure cost when generating long drafts. in fact, some of the discarded tokens may contain useful information that could be utilized in future drafting iterations. to overcome the above limitations, this paper introduces a more efficient decoding framework named ouroboros, whose improvements over speculative decoding are as follows: ## preliminary for a target model t to accelerate inference, speculative decoding first finds a suitable draft model s. given an input prefix x 1•••n , speculative decoding uses the draft model s to generate a draft d 1•••γ consisting of γ tokens in an autoregressive manner, then, the target model t verifies the draft d 1•••γ , by inputting d 1•••γ and conducting the next token prediction task using a single forward. each verification result v i is sampled from the next token prediction distribution of the target model, here, v 1•••a+1 will be the same as the result when the target model autoregressively generates a + 1 tokens from x, because at this time, ## method in ouroboros, we first accelerate drafting via phrases, so that we can generate γ tokens with fewer forward passes of the draft model, and we denote this reduction ratio as c. subsequently, due to the fact that function a(γ) is monotonically non-decreasing, we lengthen drafts via phrases, enabling the generation of more tokens without the need for additional forward passes. we denote this costless extended length as β. following these two optimization directions, eq. ( 5 ) becomes we further enlarge c by heuristically generating phrases from verification results and reusing phrases from historically generated contexts, which can lead to better drafting efficiency. next, we will delve into the details for each part of ouroboros. ## experiments this section focuses on evaluating ouroboros on various text generation tasks to demonstrate the efficiency and effectiveness of ouroboros. ## related work this section introduces existing efforts for efficient llm inference, including efficient decoding, efficient implementation and model compression. ## conclusion in this paper, we propose a practical algorithm ouroboros to improve drafting efficiency for speculative decoding. we generate phrases in a heuristic manner and use phrases to help draft models accelerate drafting and lengthen drafts. our experiments verify that, compared to typical baselines vanilla speculative decoding and lookahead decoding, ouroboros respectively achieves speedups of 2.8× and 1.9× and does not affect the generation quality at all. our method is completely trainingfree, to make it easier to adopt for the users of speculative decoding. and the training-based version of ouroboros towards extreme acceleration will be our next work.