title: BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
summary: 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.
paper_authors._id: 682f4442cec9e7ed3c25ae8a
paper_authors.name: Yunlong Hou
paper_authors._id: 682f4442cec9e7ed3c25ae8b
paper_authors.name: Fengzhuo Zhang
paper_authors._id: 682f4442cec9e7ed3c25ae8c
paper_authors.name: Cunxiao Du
paper_authors._id: 682f4442cec9e7ed3c25ae8d
paper_authors.name: Xuan Zhang
paper_authors._id: 682f4442cec9e7ed3c25ae8e
paper_authors.name: Jiachun Pan
paper_authors._id: 682f4442cec9e7ed3c25ae8f
paper_authors.name: Tianyu Pang
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-05-26T08:17:25.835Z
paper_authors._id: 63d91b6d255ef6add20e1b38
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/1675921369867-63d91b6d255ef6add20e1b38.jpeg
paper_authors.fullname: Tianyu Pang
paper_authors.type: user
paper_authors.user: P2333
paper_authors._id: 682f4442cec9e7ed3c25ae90
paper_authors.name: Chao Du
paper_authors._id: 682f4442cec9e7ed3c25ae91
paper_authors.name: Vincent Y. F. Tan
paper_authors._id: 682f4442cec9e7ed3c25ae92
paper_authors.name: Zhuoran Yang
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2025-05-22T15:35:31.349Z
paper_authors._id: 6397873ec0b27f432db8693f
paper_authors.avatarUrl: /avatars/1db65fe55002ad5c137c4a59bbcd239d.svg
paper_authors.fullname: Zhuoran Yang
paper_authors.type: user
paper_authors.user: zhuoran
paper_title: BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: 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