BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms

• URL: http://arxiv.org/abs/2505.15141v1
• Date: Wed, 21 May 2025 05:56:31 GMT
• Title: BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms
• Authors: Yunlong Hou, Fengzhuo Zhang, Cunxiao Du, Xuan Zhang, Jiachun Pan, Tianyu Pang, Chao Du, Vincent Y. F. Tan, Zhuoran Yang,
• Abstract summary: Speculative decoding has emerged as a popular method to accelerate the inference of Large Language Models (LLMs)<n>This paper proposes a training-free online learning framework to adaptively choose the configuration of the hyper parameters for speculative decoding as text is being generated.
• Score: 101.9736063064503
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution [31.385024956599676]
  Large language models (LLMs) exhibit diverse response behaviors, costs, and strengths.<n>We develop a LinUCB-based algorithm that provably achieves sublinear regret without relying on future context prediction.<n>Our algorithms are theoretically grounded and require no offline fine-tuning or dataset-specific training.
  arXiv  Detail & Related papers  (2025-06-21T10:01:46Z)
• HyperArm Bandit Optimization: A Novel approach to Hyperparameter Optimization and an Analysis of Bandit Algorithms in Stochastic and Adversarial Settings [0.0]
  The paper introduces a novel framework, HyperArm Bandit Optimization (HABO), which applies EXP3 to hyper parameter tuning in machine learning models.<n>HABO treats individual hyper parameters as super-arms, and its potential configurations as sub-arms, enabling dynamic resource allocation and efficient exploration.
  arXiv  Detail & Related papers  (2025-03-13T11:50:28Z)
• Chimera: A Lossless Decoding Method for Accelerating Large Language Models Inference by Fusing all Tokens [15.566726645722657]
  We propose a novel framework specifically designed for speculative sampling. Within this framework, we introduce a lightweight draft model that effectively utilizes previously generated tokens to predict subsequent words. We demonstrate impressive results, achieving an average latency speedup ratio of 2.7x compared to the vanilla auto-regressive decoding approach.
  arXiv  Detail & Related papers  (2024-02-24T08:10:39Z)
• LLM can Achieve Self-Regulation via Hyperparameter Aware Generation [88.69052513433603]
  Large Language Models (LLMs) employ diverse decoding strategies to control the generated text. Are LLMs conscious of the existence of these decoding strategies and capable of regulating themselves? We propose a novel text generation paradigm termed Hyperparameter Aware Generation (HAG)
  arXiv  Detail & Related papers  (2024-02-17T11:18:22Z)
• Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding [46.485363806259265]
  Speculative Decoding has emerged as a novel decoding paradigm for Large Language Models (LLMs) inference. In each decoding step, this method first drafts several future tokens efficiently and then verifies them in parallel. This paper presents a comprehensive overview and analysis of this promising decoding paradigm.
  arXiv  Detail & Related papers  (2024-01-15T17:26:50Z)
• Speculative Contrastive Decoding [55.378200871224074]
  Large language models(LLMs) exhibit exceptional performance in language tasks, yet their auto-regressive inference is limited due to high computational requirements and is sub-optimal due to the exposure bias. Inspired by speculative decoding and contrastive decoding, we introduce Speculative Contrastive Decoding(SCD), a straightforward yet powerful decoding approach.
  arXiv  Detail & Related papers  (2023-11-15T14:15:30Z)
• LAMBO: Large AI Model Empowered Edge Intelligence [71.56135386994119]
  Next-generation edge intelligence is anticipated to benefit various applications via offloading techniques. Traditional offloading architectures face several issues, including heterogeneous constraints, partial perception, uncertain generalization, and lack of tractability. We propose a Large AI Model-Based Offloading (LAMBO) framework with over one billion parameters for solving these problems.
  arXiv  Detail & Related papers  (2023-08-29T07:25:42Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  In contextual bandits, an agent sequentially makes actions from a time-dependent action set based on past experience. We propose the first online continuous hyperparameter tuning framework for contextual bandits. We show that it could achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2023-02-18T23:31:20Z)
• Text Generation with Efficient (Soft) Q-Learning [91.47743595382758]
  Reinforcement learning (RL) offers a more flexible solution by allowing users to plug in arbitrary task metrics as reward. We introduce a new RL formulation for text generation from the soft Q-learning perspective. We apply the approach to a wide range of tasks, including learning from noisy/negative examples, adversarial attacks, and prompt generation.
  arXiv  Detail & Related papers  (2021-06-14T18:48:40Z)
• Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms [74.55200180156906]
  The contextual bandit problem models the trade-off between exploration and exploitation. We show our Syndicated Bandits framework can achieve the optimal regret upper bounds.
  arXiv  Detail & Related papers  (2021-06-05T22:30:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.