When Drafts Evolve: Speculative Decoding Meets Online Learning

Speculative decoding has emerged as a widely adopted paradigm for accelerating large language model inference, where a lightweight draft model rapidly generates candidate tokens that are then verified in parallel by a larger target model. However, due to limited model capacity, drafts often struggle to approximate the target distribution, resulting in shorter acceptance lengths and diminished speedup. A key yet under-explored observation is that speculative decoding inherently provides verification feedback that quantifies the deviation between the draft and target models at no additional cost. This process naturally forms an iterative "draft commits--feedback provides--draft adapts" evolving loop, which precisely matches the online learning paradigm. Motivated by this connection, we propose OnlineSPEC, a unified framework that systematically leverages interactive feedback to continuously evolve draft models. Grounded in dynamic regret minimization, we establish a formal link between online learning performance and speculative system's acceleration rate, and develop novel algorithms via modern online learning techniques, including optimistic online learning that adaptively reuses historical gradients as predictive update hints, and online ensemble learning that dynamically maintains multiple draft models. Our algorithms are equipped with theoretical justifications and improved acceleration rates, achieving up to 24% speedup over seven benchmarks and five foundation models.

Speculative decoding accelerates large language model inference by pairing a large, accurate model with a small, fast "draft" model that proposes candidate text in advance, but the draft model is fixed after training and cannot adapt to the diverse inputs it encounters in deployment, leading to frequent rejections and diminished speedup. We observe that every time the large model rejects a draft, it implicitly reveals where the draft went wrong: a free feedback signal that existing methods discard. We propose OnlineSPEC, a framework that treats this as an online learning problem: the draft model continuously updates itself using verification feedback, getting smarter with every query it processes. Building on this idea, we develop principled algorithms grounded in online learning theory and achieve up to 24% speedup over previous state-of-the-art methods across seven benchmarks and five foundation models.