BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
Speculative decoding has emerged as a popular method to accelerate the
inference of Large Language Models (LLMs) while retaining their superior text
generation performance. Previous methods either adopt a fixed speculative
decoding configuration regardless of the prefix tokens, or train draft models
in an offline or online manner to align them with the context. This paper
proposes a training-free online learning framework to adaptively choose the
configuration of the hyperparameters for speculative decoding as text is being
generated. We first formulate this hyperparameter selection problem as a
Multi-Armed Bandit problem and provide a general speculative decoding framework
BanditSpec. Furthermore, two bandit-based hyperparameter selection algorithms,
UCBSpec and EXP3Spec, are designed and analyzed in terms of a novel quantity,
the stopping time regret. We upper bound this regret under both stochastic and
adversarial reward settings. By deriving an information-theoretic impossibility
result, it is shown that the regret performance of UCBSpec is optimal up to
universal constants. Finally, extensive empirical experiments with LLaMA3 and
Qwen2 demonstrate that our algorithms are effective compared to existing
methods, and the throughput is close to the oracle best hyperparameter in
simulated real-life LLM serving scenarios with diverse input prompts.
682f4442cec9e7ed3c25ae8a
Yunlong Hou
682f4442cec9e7ed3c25ae8b
Fengzhuo Zhang
682f4442cec9e7ed3c25ae8c
Cunxiao Du
682f4442cec9e7ed3c25ae8d
Xuan Zhang
682f4442cec9e7ed3c25ae8e
Jiachun Pan
682f4442cec9e7ed3c25ae8f
Tianyu Pang
claimed_verified
2025-05-26T08:17:25.835Z
63d91b6d255ef6add20e1b38
https://cdn-avatars.huggingface.co/v1/production/uploads/1675921369867-63d91b6d255ef6add20e1b38.jpeg
Tianyu Pang
user
P2333
682f4442cec9e7ed3c25ae90
Chao Du
682f4442cec9e7ed3c25ae91
Vincent Y. F. Tan
682f4442cec9e7ed3c25ae92
Zhuoran Yang
extracted_pending
2025-05-22T15:35:31.349Z
6397873ec0b27f432db8693f
/avatars/1db65fe55002ad5c137c4a59bbcd239d.svg
Zhuoran Yang
user
zhuoran
BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
Speculative decoding has emerged as a popular method to accelerate the
inference of Large Language Models (LLMs) while retaining their superior text
generation performance. Previous methods either adopt a fixed speculative
decoding configuration regardless of the prefix tokens, or train draft models
in an offline or online manner to align them with the context. This paper
proposes a training-free online learning framework to adaptively choose the
configuration of the hyperparameters for speculative decoding as text is being
generated. We first formulate this hyperparameter selection problem as a
Multi-Armed Bandit problem and provide a general speculative decoding framework
BanditSpec. Furthermore, two bandit-based hyperparameter selection algorithms,
UCBSpec and EXP3Spec, are designed and analyzed in terms of a novel quantity,
the stopping time regret. We upper bound this regret under both stochastic and
adversarial reward settings. By deriving an information-theoretic impossibility
result, it is shown that the regret performance of UCBSpec is optimal up to
universal constants. Finally, extensive empirical experiments with LLaMA3 and
Qwen2 demonstrate that our algorithms are effective compared to existing
methods, and the throughput is close to the oracle best hyperparameter in
simulated real-life LLM serving scenarios with diverse input prompts.
The paper introduces a training-free online learning framework, BanditSpec, to adaptively select hyperparameters for speculative decoding in Large Language Models, demonstrating superior performance and throughput compared to existing methods.
speculative decoding Large Language Models hyperparameter selection Multi-Armed Bandit BanditSpec UCBSpec EXP3Spec stopping time regret stochastic adversarial reward information-theoretic impossibility oracle best hyperparameter