PaperlayerView exact revision on arXiv

Source-linked AI summary

Ouroboros: Generating Longer Drafts Phrase by Phrase for Faster Speculative Decoding

Weilin Zhao, Yuxiang Huang, Xu Han, Wang Xu, Chaojun Xiao, Xinrong Zhang, Yewei Fang, Kaihuo Zhang, Zhiyuan Liu, Maosong Sun

arXiv:2402.13720v3cs.CL

TL;DR

Speculative decoding accelerates LLM generation without compromising performance, but its speedup depends on efficiently producing long drafts. Ouroboros uses phrases to parallelize and lengthen drafts in a training-free manner; across typical text-generation tasks, it reports speedups of up to 2.8× over speculative decoding and 3.9× over vanilla decoding without fine-tuning.

  • Problem

    Speculative decoding’s speedup depends on efficiently generating long, accurate drafts, while autoregressive LLM generation remains sequential.

    Source: §1 · p. 1

  • Method

    Ouroboros uses phrases to parallelize drafting and lengthen drafts, including phrases reused from verification, without additional training.

    Source: §3 · p. 3, §3.1 · p. 3

  • Results

    Ouroboros reports speedups of 2.8× over speculative decoding and 1.9× over lookahead decoding, with no effect on generation quality.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The training-free framework is presented as practical for speculative-decoding users and preserves generation quality.

    Source: §6 · p. 9

    The paper focuses on single-query inference; batched speculative sampling is outside its scope.

    Source: Limitations · p. 9

Abstract

from arXiv · show

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.8\times$ over speculative decoding and $3.9\times$ over vanilla decoding, without fine-tuning draft and target models. The source code of Ouroboros is available at https://github.com/thunlp/Ouroboros.

1 Introduction

Ouroboros targets the drafting-cost trade-off in speculative decoding by using phrases to generate and extend drafts and reuse phrase information. The paper reports lossless task performance and speedups over speculative decoding, lookahead decoding, and naive autoregressive decoding without fine-tuning.

1 Introduction

  • Autoregressive LLMs generate tokens sequentially, limiting parallelization during inference.Source: §1 · p. 1
  • Speculative decoding’s speedup depends on efficiently generating long, accurate drafts, but longer drafts also increase drafting cost.The target accepts more tokens per iteration on average with longer drafts, yet the optimal draft length is not the largest one.Source: §1 · pp. 1–2
  • Short drafts miss potential acceleration, while rejected draft tokens are discarded even though some may help future drafting.Long drafts can be costly when they fail.Source: §1 · p. 2
  • Ouroboros drafts at the phrase level, extends drafts with matching phrases, and reuses phrases from verification or similar-task histories.Concatenating k phrases creates k longer drafts for target verification at almost zero additional cost.Source: §1 · p. 2
  • Up to 2.8× over speculative decoding, 3.9× over naive autoregressive decoding, and 1.9× over lookahead decoding, with no task-performance loss or model fine-tuning.The reported speedups are for Ouroboros.Source: §1 · p. 2

2 Preliminary

Speculative decoding drafts tokens autoregressively with a smaller model, then verifies the draft using the target model. The verification accepts an accurate prefix and discards the remaining draft tokens.

2 Preliminary

  • The draft model generates γ draft tokens autoregressively, conditioning each later token on the input prefix and earlier draft tokens.Source: §2 · p. 2
  • The target model verifies the draft in one forward pass and produces token predictions conditioned on the input prefix and preceding draft tokens.Source: §2 · p. 2
  • Verification accepts A accurate draft tokens plus the target model’s next token, while discarding the remaining draft tokens.The exposition sets draft-model sampling temperature to 0 for clarity and states that this does not affect target-model correctness.Source: §2 · pp. 2–3
  • The speedup ratio compares vanilla target-model generation time with speculative-decoding time.Source: §2 · p. 3

3 Method

Ouroboros accelerates speculative decoding by drafting phrase-by-phrase, extending drafts with phrases, and reusing phrases found in verification results and earlier generations.

3 Method

  • Ouroboros generates γ tokens with fewer draft-model forward passes, then extends drafts by β tokens without additional forward passes.The reduction ratio is c, and β denotes the costless extended length.Source: §3 · p. 3

3.1 Accelerating Drafting via Phrases

  • Each draft-model forward generates multiple new phrases in parallel, making drafting phrase-by-phrase rather than token-by-token.This uses phrases to accelerate the draft model indirectly, so a target-model forward can verify multiple phrase rounds.Source: §3.1 · p. 3

3.2 Lengthening Drafts via Phrases

  • For a draft ending in dγ, Ouroboros selects K phrases sharing that token, concatenates them into longer drafts, and verifies them in one target-model forward.The attention masking mechanism computes the verification results for the longer drafts in parallel.Source: §3.2 · p. 4

3.3 Generating Phrases from Verification

  • When a draft is not fully accepted, Ouroboros filters discarded subsegments matching the verification results and adds them to the phrase pool.The paper reports that the total number of matched tokens can exceed the accurate-prefix length.Source: §3.3 · p. 4

3.4 Reusing Phrases from History Contexts

  • Ouroboros reuses phrases from previous generations to accelerate drafting, unlike lookahead decoding, which cleans up historical phrases for subsequent queries.The reuse strategy is motivated by similarities between adjacent user conversations.Source: §3.4 · p. 4

3.5 The Advantages of the Training-free Framework

  • Ouroboros is training-free: heuristic phrases accumulate during generation without large-corpus preparation, and it can be applied to an existing draft model without additional costs.The framework does not use distillation to increase A(γ) or compression to decrease tS.Source: §3.5 · p. 5

4 Experiments

Experiments evaluate Ouroboros across code generation, arithmetic reasoning, summarization, and translation, then examine overall speed, component effects, and comparisons with other methods.

4.1 Experimental Settings

  • Evaluation spans HumanEval, MBPP, GSM8K, CNN/DM, and WMT16, comparing against vanilla autoregressive, speculative, and lookahead decoding.Source: §4.1 · p. 5

4.2 Overall Results

  • 61.2 token/s at maximum generation length 512 yields speedups of 3.9× over greedy decoding, 2.8× over speculative decoding, and 1.9× over lookahead decoding.Source: Figure 5 · p. 6, §4.2 · p. 6
  • Table 2 reports substantial speedups on natural-language tasks, where lookahead decoding and speculative decoding achieve limited acceleration.Source: Table 2 · p. 6, §4.2 · p. 6
  • On Llama-2-chat-70B/7B, Ouroboros also applies to random sampling, with baseline speedups not much different from those in greedy decoding.Source: Table 3 · p. 6, §4.2 · p. 6

4.3 Ablation Studies and Analyses

  • Ablations show that every component adds speed, with phrase-based drafting acceleration and draft lengthening most effective.Source: Table 4 · p. 7, §4.3 · p. 7
  • Figure 6 shows a best phrase count K: verifying fewer or more phrases slows decoding.Source: Figure 6 · p. 7, §4.3 · p. 7

4.4 Comparing with Training-based Methods

  • Against Eagle, the training-free method is only slightly slower despite Eagle's much smaller trained draft model; Eagle's lower acceptance reflects reduced draft effectiveness.Source: Table 5 · p. 7, §4.4 · p. 7

4.5 Comparing with Phrases-based Methods

  • Ouroboros substantially outperforms PLD and REST, which retrieve phrases for direct target-model verification; the draft model filters low-quality phrases first.Source: §4.5 · p. 7, Table 6 · p. 8

5 Related Work

The related work covers efficient decoding, implementation, and model compression, positioning Ouroboros among approaches to faster LLM inference.

5.1 Efficient Decoding

  • Drafting-then-verifying methods avoid serial generation and accelerate inference without reducing model performance, unlike non-autoregressive methods that can hurt performance.Source: §5.1 · p. 8
  • Prior decoding approaches use smaller or selected-layer draft models, trained auxiliary heads, input suffixes, or target-model-generated n-gram pools.Source: §5.1 · p. 8
  • PLD, LLMA, and REST directly verify retrieved phrases, while Ouroboros first uses a draft model to filter low-quality phrases.Source: §5.1 · p. 8
  • Ouroboros accelerates a small draft model with phrases and tests phrase sources from the draft model, verification, and historical contexts.Source: §5.1 · p. 8

5.2 Efficient Implementation; 5.3 Model Compression

  • Efficient implementations and model-compression methods are orthogonal to Ouroboros and can be combined with it for further acceleration.Source: §5.2 · p. 9, §5.3 · p. 9

6 Conclusion

Ouroboros improves speculative-decoding draft efficiency by using heuristically generated phrases to accelerate drafting and lengthen drafts. It is training-free and reports speedups over vanilla speculative and lookahead decoding without affecting generation quality.

6 Conclusion

  • Ouroboros uses heuristically generated phrases to accelerate draft models and lengthen drafts for speculative decoding.Source: §6 · p. 9
  • It achieves speedups of 2.8× over vanilla speculative decoding and 1.9× over lookahead decoding without affecting generation quality.Source: §6 · p. 9
  • The method is training-free; a training-based version aimed at extreme acceleration is future work.Source: §6 · p. 9

Limitations

The experiments focus on decoder-only models and single-query scenarios, while the method is described as extendable to other model structures. The current approach is training-free; improved consistency through future training could yield greater acceleration.

Limitations

  • The experiments focus on decoder-only model structures, although Ouroboros is described as extendable to other structures.The method currently focuses on training-free optimization; the authors say future training to improve large- and small-model consistency could increase acceleration.Source: Limitations · p. 9
  • Efficient implementation and model compression are orthogonal to Ouroboros and can be combined with it for further speedup.Source: Limitations · p. 9
  • The evaluation is limited to the single-query scenario; batched speculative sampling is outside the paper’s scope.The authors refer readers to Liu et al. (2024), Qian et al. (2024), and Chen et al. (2024) for batched inference.Source: Limitations · p. 9

Ethical Considerations

This material reports no notable task-performance degradation, discusses hyperparameter stability and tuning, and evaluates theoretical Block Efficiency. It also states an ethical consideration about training-free operation and unchanged generation results.

Ethical Considerations

  • The authors state that training-free operation does not affect generation results and therefore poses no potential risk.Source: Ethical Considerations · p. 9

A Ouroboros does not cause any performance degradation

B Hyperparameters

  • Hyperparameter grid-search results are described as stable, supporting a general recipe or heuristic search instead of repeated grid search.The search tested γ ∈ [3, 5], W ∈ [14, 16], and β ∈ [5, 7] on GSM8K with Yi-34B/6B.Source: B Hyperparameters · p. 13, Table 10 · p. 13

B.1 Hyperparameters Recipe

  • The tuning recipe distinguishes high-homogeneity tasks such as code generation from low-homogeneity tasks such as machine translation.The recipe is presented as an empirical hyperparameter-tuning guide.Source: §B.1 · pp. 13–14, Table 11 · p. 14

B.2 Hyperparameters Tuning

  • The proposed heuristic search selects γ, W, and β sequentially by minimizing clock time, with K fixed at 3 in the experiments.Source: §B.2 · p. 14

B.3 Hyperparameters Used in Our Experiment

  • The reported experiment settings use γ = 12, W = 20, β = 8, K = 3 in Table 4, and γ = 6, W = 18, β = 6, K = 3 in Table 17.Figure 6 uses γ = 12, W = 20, β = 8; Table 13 follows Table 12’s settings.Source: §B.3 · p. 14

C Block Efficiency

  • Block Efficiency ignores drafting time and represents a theoretical upper bound; Ouroboros has relatively high values in most tested scenarios.The reported comparison uses Yi-34B/6B on five datasets; the authors describe the larger ideal speedup as potential for future algorithms or systematic implementation.Source: C Block Efficiency · p. 14, Table 13 · p. 14

D Comparing with other draft-accelerated methods

Ouroboros is compared with Cascade Speculative Decoding, which uses a still smaller model to draft for the draft model. The reported comparison favors Ouroboros, while the authors suggest model-output discrepancies may slow Cascade.

D Comparing with other draft-accelerated methods

  • Ouroboros outperforms Cascade Speculative Decoding in the reported GSM8K comparison.Table 14 compares Ouroboros with various Cascade versions.Source: D Comparing with other… · p. 14, Table 14 · p. 15
  • Cascade Speculative Decoding accelerates drafting by using an even smaller model to draft for the draft model.Source: D Comparing with other… · p. 14
  • Cascade runs slower than original speculative decoding in the reported setting; the authors suggest output discrepancies from unofficial tiny models as one possible reason.The cited examples are Llama-160M and TinyLlama-1.1B used with Llama-2-7B.Source: D Comparing with other… · pp. 14–15

E Ouroboros under various generation lengths

Across the tested generation-length limits, Ouroboros outperforms autoregressive, speculative, and Lookahead decoding. Short limits truncate answers, while limits of 256 and 512 yield close task performance and speedup ratios.

E Ouroboros under various generation lengths

F Context Locality

Phrase reuse remains effective across tasks even when context locality is low, while higher locality improves decoding less than enabling phrase reuse.

F Context Locality

  • The experiment sampled 20 entries each from MBPP, GSM8K, CNN/DM, and WMT16, varying consecutive same-dataset entries; higher CN means better locality and shuffle the worst.Source: F Context Locality · p. 15
  • With phrase reuse, CN=20 decodes faster than the shuffle setting.The results are reported in the context-locality ablation.Source: F Context Locality · p. 15, Table 17 · p. 16
  • Approximately 3 token/s faster than cold start, lower-CN and shuffled reuse remain effective across tasks, while locality’s effect is smaller than enabling phrase reuse.The reported comparison covers lower-CN and shuffle settings against cold start.Source: F Context Locality · p. 16
Loading 2402.13720v3…