# Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs arXiv: https://arxiv.org/abs/2510.20064 ยท HTML: https://mlsanity.com/paper/2510.20064/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Placed in Speculative decoding, one of 12 directions in Efficient LLM inference and serving. - Builds on 35 of its 62 references that are in the map. - First posted on arXiv 22 Oct 2025. ## Placed in - Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/) ## Builds on (most cited first, 30 of 35) - [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025) - [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021) - [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022) - [Jailbreaking Black Box Large Language Models in Twenty Queries](https://mlsanity.com/paper/2310.08419/) (2023) - [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023) - [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024) - [Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyond](https://mlsanity.com/paper/1602.06023/) (2016) - [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024) - [Jailbreaking ChatGPT via Prompt Engineering: An Empirical Study](https://mlsanity.com/paper/2305.13860/) (2023) - [Fast-dLLM: Training-free Acceleration of Diffusion LLM by Enabling KV Cache and Parallel Decoding](https://mlsanity.com/paper/2505.22618/) (2025) - [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024) - [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023) - [EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test](https://mlsanity.com/paper/2503.01840/) (2025) - [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024) - [OpenMathInstruct-2: Accelerating AI for Math with Massive Open-Source Instruction Data](https://mlsanity.com/paper/2410.01560/) (2024) - [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023) - [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013) - [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023) - [Online Speculative Decoding](https://mlsanity.com/paper/2310.07177/) (2023) - [Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding](https://mlsanity.com/paper/2402.12374/) (2024) - [GliDe with a CaPE: A Low-Hassle Method to Accelerate Speculative Decoding](https://mlsanity.com/paper/2402.02082/) (2024) - [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (2024) - [Envisioning Outlier Exposure by Large Language Models for Out-of-Distribution Detection](https://mlsanity.com/paper/2406.00806/) (2024) - [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025) - [Towards Optimal Multi-draft Speculative Decoding](https://mlsanity.com/paper/2502.18779/) (2025) - [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021) ## Built on by (most cited first, 7 of 7) - [Fail Fast, Win Big: Rethinking the Drafting Strategy in Speculative Decoding via Diffusion LLMs](https://mlsanity.com/paper/2512.20573/) (2025) - [AdaFlash: Adaptive Speculative Decoding via On-Policy Distilled Diffusion Drafters](https://mlsanity.com/paper/2607.19223/) (2026) - [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026) - [WhiFlash: Accelerating Speculative Decoding with Token-Level Cross-Paradigm Routing](https://mlsanity.com/paper/2606.07710/) (2026) - [Fully Rotation-Equivariant Spectral-Spatial Learning for Multispectral Object Detection](https://mlsanity.com/paper/2607.05148/) (2026) - [MemSpec: Memory-Aware Runtime for Adaptive Draft Scheduling in Speculative Decoding on Edge Devices](https://mlsanity.com/paper/2608.10362/) (2026) - [SP2ec: Adaptive Self-Speculative Decoding for Vision-Language Models](https://mlsanity.com/paper/2610.18735/) (2026) ## Abstract (arXiv) Speculative decoding is widely used in accelerating large language model (LLM) inference. In this work, we focus on the online draft model selection problem in speculative decoding. We design an algorithm that provably competes with the best draft model in hindsight for each query in terms of either the token acceptance probability or expected acceptance length. In particular, we show that we can accurately evaluate all draft models, instead of only the chosen model without incurring additional queries to the target model, which allows us to improve exponentially over the existing bandit-based approach as the number of draft models increases. Our approach is generically applicable with any speculative decoding methods (single draft, multi-drafts and draft-trees). Moreover, we design system-efficient versions of online learners and demonstrate that the overhead in computation and latency can be substantially reduced. We conduct extensive experiments on open-source LLMs and diverse datasets, demonstrating that our methods substantially outperform the state-of-the-art EAGLE3 and the BanditSpec baseline in a variety of domains where specialized domain-expert drafters are available, especially when long reasoning chains are required.