BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
Authors: name: Yunlong Hou, name: Fengzhuo Zhang, name: Cunxiao Du, name: Xuan Zhang, name: Jiachun Pan, name: Tianyu Pang, name: Chao Du, name: Vincent Y. F. Tan, name: Zhuoran Yang

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.