Backoff Decoding: A Language Model Inference Acceleration Framework with a Tunable Efficiency-Performance Tradeoff

Authors: Maximilian Holsman, Yukun Huang, Rickard Stureborg, Bhuwan Dhingra
Primary area: foundation or frontier models, including LLMs
Keywords: language modeling, inference acceleration, decoding strategies

Abstract:
In current transformer-based language models, all tokens in a sequence are generated by identical forward passes and thereby incur the same inference cost. However, tokens vary widely in their importance to the overall generation and their difficulty for models to generate correctly, making this equal allocation of inference resources suboptimal. We introduce backoff decoding, a framework for efficient language model inference that dynamically allocates token generations between two (or more) models of different sizes, according to an arbitrary decision function. By modifying how this decision function allocates generations between the differently sized models, users can tune their generation along an efficiency-performance tradeoff to suit the needs of their application. Backoff decoding can be used on any set of models with the same tokenizer and does not require any training or finetuning of the models themselves. As a demonstration of our framework, we show that backoff decoding with a large and a small model can significantly reduce inference cost while sacrificing virtually no performance compared to the standalone large model. We then show that inference costs can be reduced even further, achieving inference accelerations of up to 3-4x in exchange for reductions in model performance, demonstrating an efficiency-performance tunability not found in other inference acceleration techniques.

Decision: reject
Reviewer scores: 3, 3, 5

Reviews and discussion:
<thread>
creation date:
1730512957369

thread_type:
official_review

<thread_object>
creator: reviewer_jk23

<content>
summary:
This paper proposes a novel generation strategy called backoff decoding that aims to improve efficiency of the inference by re-routing per-tokens generations between smaller and larger LLM depending on the difficulty of the token to be predicted. The core idea is to approximate the difficulty using the divergence between distributions induced by small and large model. Authors empirically show that this approximation works very well in practice, and further propose a model that can estimate this divergence without running the large model. 

Authors performed experiments on multiple tasks using the proposed method showing that they could achieve substantial speed-ups with very minor performance degradation. Authors also provide connections to related work such as speculative sampling by highlighting its similarities and differences.

strengths:
* This method provides a practical solution to achieve low-latency inference with very large LLMs.
* The method involves the original decision function that is defined so that there is a big room for further research improving the design of that component that will lead to lower approximation error.
* Experiments are clearly written and are easy to follow.

weaknesses:
* Real-world results might be less predictable than the experiments presented in the paper. For instance, current LLMs are trained with trillions of tokens, which implies that the decision function might need much more training data in order to cover enough amount of text.
* There is no comparison with the speculative decoding in terms of quality vs. speed up. In contrast to this approach, speculative sampling is guaranteed to sample from the target model distribution thus does not have quality degradation. Authors made verbal connection with this related work and compared the speed-ups under oracle decision function, but it really needs an experiment comparing the speed and quality.

questions:
* Following the weakness point above, why there is no experiment comparing with speculative decoding w.r.t. both speed and quality? I suspect this will be a question every reader will have if this is published at the conference. And if speculative decoding is faster, then why would we want to use back off decoding and risk performance degradation? These days speculative decoding advanced into using MLP based and ngram based speculators which are much faster than small LLMs. I suspect that under such comparison this method will be slower and show quality degradation. Am I correct that Fig. 2 shows how backoff decoding is always worse than speculative sampling assuming that speculative sampling should achieve performance of the large model?
* How would one choose the backoff threshold parameter in real life? Imagine that we want to get a solution that works the best in general setting (i.e. all domains) and its not feasible to tune T for each input we are getting. What shall we do? This feels like a major question to answer.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730613080658

thread_type:
official_review

<thread_object>
creator: reviewer_bman

<content>
summary:
This paper proposes an approach to reduce inference cost for larger language models (LLM). The proposed approach backs off to a smaller LM for decoding when the KL divergence between the large and smaller LMs are not too high. The decision for backing-off is made by a classifier trained to predict whether the KL divergence is above or below a threshold. The paper observes that in most cases, the divergence between small and large models are relatively small, hence this back-off strategy effectively reduces cost without hurting much quality.

strengths:
This paper made interesting observations that on the tasks being considered (GSQA, GSM8K, ASQA), the KL divergence between large and smaller models are mostly very small. This insight justifies utilizing smaller models to handle a majority of decoding steps.

weaknesses:
1. The proposed approach did not show superior performance in comparison to existing and similar techniques like speculative decoding. 2. The experimental results are not substantial enough to support the proposal: Only three tasks (GSQA, GSM8K, ASQA, as shown in Fig. 2) are considered, and only a single large-small model combination (Llama 70B, 8B) was experimented.
3. Although the proposed approach claims that it does not require finetuning the models itself (line 114), it nevertheless requires training a dedicated classifier to make it work. What is more, this classifier depends on the choice of the smaller LM, making this approach difficult to generalize. Lastly, the cost of running this classifier at each step did not seem to be accounted for in this paper.
4. The classifier decision threshold needs to be calibrated for each task, again making this approach difficult to use and generalize.

questions:
1. All findings and experimental results in this paper came from the single choice of language model pair (Llama 70B, 8B), I wonder whether these observations and analysis still holds for more a broader range of models (e.g. Gemma).

2. It seem the proposed approach has no particular advantage over speculative decoding, as can be seen from Fig 1 and 2: Both performance and inference cost matches at around 80% backoff ratio, which means that the same cost allocated to speculative decoding can achieve about the same quality.

3. The paper claims that "Backing off on even just 0.07% of the highest KL divergence generations (Kl div. ≥ 10) noticeably degrades the performance" (line 382-383), however it seems from Table 2, at 0.07% back-off percentage, the quality didn't degrade at all (68.8 vs. 68.3 with full M_L)?

4. What is the size and cost overhead of the MLP used by the classifier? The paper did not seem to mention these info.

5. In the leftmost chart in Fig. 2, when backoff percentage is 100%, the M_S performance should be the same as Oracle, but this did not seem to be the case?

6. The paper should have provided some analysis over the quality degradation as the generation lengths increases, as the longer the generation, the less accurate smaller models will be. The KL divergence between large and smaller models should be a function of decoding step time.

7. Typos:
- Line 110: "users to not" => "users do not"
- Line 151: "achieves achieves" => "achieves"
- Table 1: "<=2" => ">=2"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730710185510

thread_type:
official_review

<thread_object>
creator: reviewer_7zcr

<content>
summary:
This paper proposes backoff decoding for inference acceleration of LLMs. Speculative decoding generates draft tokens from a small model and verifies these tokens by the large model. The authors believe that the validation is not necessary, and if the KL divergence of the next token of two models is below a threshold, the result of the small model can be adopted directly. In order not to calculate the KL divergence  every time, backoff decoding trains a classifier for determining whether the next token uses the token from small model or from the large model.

strengths:
1. The trade-off between acceleration and accuracy in Backoff decoding is adjustable, making it adaptable to various scenarios.

2. The analysis on predicting KL divergence using a classifier is particularly interesting.

weaknesses:
1. A large portion of the content overlaps with speculative decoding, including parts of the introduction, lines 143-155 in the methods section, and the whole Section 3.2.

2. The experimental setup is insufficiently detailed, lacking specifications on hardware. Additionally, while the authors present accuracy and inference cost results relative to the Backoff percentage, they do not visually display the trade-off between accuracy and inference cost in a single figure, which would be more intuitive.

3. The assumption that speculative decoding achieves consistent speedups across different benchmarks is questionable. SpecBench[1] shows that decoding speeds can vary by domain. The authors only used a few benchmarks; running speculative decoding on these additional benchmarks does not seem particularly costly.

4. The figures in the paper are not in vector format."

5. The 5-6x speedup mentioned in the abstract is exaggerated. Achieving a 5-6x speedup requires a Backoff percentage of 95%, at which point the performance degradation is not a 'small reduction'—it is almost equivalent to the performance of a smaller model. If 'small reductions' refer to absolute performance changes, the performance gap between the large and small models on the selected benchmarks is inherently small, making it reasonable to simply use the smaller model.

[1]  Xia, Heming, et al. "Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding." arXiv preprint arXiv:2401.07851 (2024).

questions:
1. A large portion of the paper’s content overlaps with speculative decoding. Why not introduce Backoff decoding from speculative decoding? This would create a more cohesive flow, making it easier for readers to understand and would also save considerable space.

2. In Figure 1, why does the initial cost increase? Is it because the proportion of token acceptance is insufficient to cover the model switching cost and the classifier computation cost?

3. In Table 1, should the '<=2' actually be '>=2'?
</content>
</thread_object>

</thread>


Metareview: