Research map / Large language models / Reasoning and chain of thought

Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Speculative decoding · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes HedgeSpec, a full-information online learner that selects among multiple draft models for speculative decoding by counterfactually estimating every drafter's acceptance length from one target trajectory, with no-regret guarantees.

Problem

Online drafter selection in speculative decoding: choosing, per query, which of several draft models to use so performance matches the best drafter in hindsight, without extra target-model calls.

Approach

Instead of bandit feedback that reveals only the chosen drafter's acceptance, an off-policy estimator uses a single verified target trajectory to compute an unbiased acceptance-length estimate for all drafters, turning the problem into full-information online learning (NormalHedge with delayed feedback) with regret that scales with log N rather than exponentially worse bandit rates.

Key results

• On Qwen-3-8B, HedgeSpec reaches avg MAT 6.37 and 69.44 token/s versus EAGLE 4.23 and 47.53, a 46.1% average gain reported in the text.
• On SQL with Qwen-3-8B, HedgeSpec improves MAT from 4.20 to 7.52 and token/s from 44.60 to 81.94 (83.7% token/s gain).
• On Llama-3.1-8B-IT, HedgeSpec averages MAT 7.15 and 90.41 token/s versus EAGLE 5.69 and 74.34 and bandit baselines (UCBSpec 5.09, EXP3Spec 4.86).

Surprising findings

• A BERT router achieving 100% in-distribution accuracy misrouted 98% of MedQA and 90% of Math queries under a natural prompt variation, while HedgeSpec stayed robust.
• Individual domain-specialized drafters perform worse on average than the vanilla EAGLE drafter, yet orchestrating them yields large speedups.

Limitations

• Theoretical guarantees rely on a stochastic/iid heuristic approximation; the adversarial-style delayed-feedback bounds are applied heuristically to a Markov LLM process.
• Experiments only use EAGLE-3 drafters and three target models; the 21 drafters are self-curated and no code/data release statement is given in the extract beyond a repository link.
• Censoring of acceptance-length estimates can underestimate alternative drafters; the token-level delayed game is more expensive than chunk-level.

Experimental setup

Datasets: Python Math Biology Chemistry MedQA CNN_DM SQL GSM8K HumanEval

Benchmarks: Python Math Biology Chemistry MedQA CNN_DM SQL GSM8K HumanEval

Metrics: MAT (mean accepted tokens) Token/s cumulative regret speedup

Baselines: EAGLE-3 UCBSpec EXP3Spec Static BERT router LLaMA-3.1-8B-IT autoregressive decoding

Builds on: EAGLE-3 BanditSpec MetaSD NormalHedge Hedge

Closest papers by meaning

• BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms (ICML 2025 · similarity 0.95)
• Learning To Draft: Adaptive Speculative Decoding with Reinforcement Learning (ICLR 2026 · similarity 0.93)
• Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration (NeurIPS 2024 · similarity 0.92)
• Online Speculative Decoding (ICML 2024 · similarity 0.92)
• Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.92)
• Training-Free Loosely Speculative Decoding: Accepting Semantically Correct Drafts Beyond Exact Match (ICLR 2026 · similarity 0.91)