HedgeSpec: no bandit needed to pick the best speculative-decoding drafter, beating EAGLE3 by nearly 2x

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

Hongyi Liu, Jiaji Huang, Zhen Jia, Youngsuk Park, Yu-Xiang Wang

ICLR'26

cs.LG

2025-10-23

Speculative decoding's verification step already reveals every draft model's quality for free, so HedgeSpec needs no exploration to pick the best one. It beats EAGLE3 by nearly 2x on Qwen-3-32B.

What problem this solves

Speculative decoding is the standard way to speed up LLM serving: a small "draft" model guesses the next several tokens, and the big target model verifies them in a single parallel forward pass. Every correctly guessed token is a forward pass you skip. The better the draft matches the target, the bigger the speedup.

The catch: no single draft model matches the target everywhere. A draft fine-tuned for Python loses on SQL; one tuned for medical QA loses on summarization. Run the wrong drafter and the target rejects most of its guesses, wasting the speculative work. The prior fix, BanditSpec, treats picking the drafter as a multi-armed bandit: you only see how the chosen drafter did, so you must pay to explore (try drafters you are unsure about), and that cost grows as the pool grows.

Method

The reframe is that speculative decoding's verification step is already a full-information oracle. When the target verifies a chunk, it exposes its own distribution over the next token. That distribution is enough to compute, counterfactually, how well any drafter would have done on this chunk, not just the one you ran. Theorem 3 makes this rigorous: a single verified trajectory yields an unbiased estimate of every drafter's expected acceptance length, with no extra calls to the target.

So the problem moves from a bandit (partial feedback) to full-information online learning. HedgeSpec runs a NormalHedge exponential-weights learner over the drafters, updating each weight from this counterfactual loss. Regret is O(sqrt(T log N)), logarithmic in the number of drafters, versus the polynomial-in-N dependence of bandit methods. Double the pool and HedgeSpec barely blinks; EXP3/UCB degrade visibly.

Design choices, each motivated:

• NormalHedge over vanilla Hedge: parameter-free, no learning rate to retune across domains.
• Loss targets expected acceptance length, not acceptance probability, because length tracks end-to-end throughput directly.
• Accepted tokens arrive in chunks, so feedback is delayed (the "censoring" problem); they plug in delayed-feedback online learning (Joulani et al. 2013) with a feedback queue.

Cost: evaluating a drafter is about 1/25 of a target forward pass (2.5 ms vs 75.7 ms in their setup), and parallelizable. One extra accepted token pays for evaluating roughly 25 drafters.

Results

Three target models, each with 7 domain-specialized drafters (Python, math, biology, chemistry, MedQA, CNN/DM summarization, SQL), against EAGLE3, BanditSpec (EXP3/UCB), and a static BERT router:

In throughput: LLaMA-3.1-8B about 21.6%, Qwen-3-8B about 46.1% (SQL domain 83.7%), Qwen-3-32B about 94.7%. As the drafter pool grows, HedgeSpec holds steady while bandit methods fall apart.

Distribution shift tells the other half. The offline BERT router misroutes catastrophically on reworded prompts (98% on MedQA, 90% on math); HedgeSpec adapts at runtime and reaches up to 2.34x over the static router.

Why it matters

In practice, production traffic is mixed: code, math, summarization, and chat arrive together, and one general drafter cannot cover all of it. HedgeSpec lets you keep a stable of specialists and route online, for free.

The bigger takeaway is conceptual: speculative decoding's verification step was hiding a full-information oracle all along, and bandit-style exploration was the wrong frame here from the start. The honest caveat is that the win has a precondition. You need to actually have specialized drafters to choose among. With a single generic drafter, there is nothing to route.

Limitations

• Drafters are built on EAGLE-3. The counterfactual estimator itself is general (single-draft, multi-draft, draft-tree; discussed in the appendix), but other speculative-decoding frameworks are not fully validated.
• The headline gain on Qwen-3-32B (about 95%) is partly inflated by a weak EAGLE3 baseline there (only 2.88 accepted tokens, 20.76 tok/s). Whether the baseline was tuned fairly is not discussed; worth asking.
• Open-source models only, with curated 7-drafter pools; no large-scale serving validation.
• Evaluation overhead is real, just amortized. On very short queries it may not pay off.

Terms

• Speculative decoding: a small draft model guesses several tokens; the target verifies them in one parallel pass, so each correct guess skips a target forward pass.
• Drafter (draft model): the small model that proposes tokens.
• Acceptance length: how many consecutive tokens the target accepts in a chunk; drives the speedup directly.
• Multi-armed bandit: you only observe feedback for the action you chose, so you must explore to learn the others.
• Full-information online learning: you see every option's feedback at each step; no exploration needed.
• Regret: cumulative loss minus the best fixed choice in hindsight; "no-regret" means it grows sublinearly.

Source

• arXiv 2510.20064v2
• PDF
• Hugging Face

What people are saying

• Paper: HedgeSpec Enables Provably No-Regret Drafter Selection for LLMs D3VAUX

Related papers

• AstroPT Recovers Galaxy Properties in Known Difficulty Order, a Calibration Test for LLM Probes
• Mol-JEPA Masks 14 Modalities Instead of Perturbing Molecules, Average MAE 0.402
• Same 24 slots: 12 narrow RAG rounds beat one wide pass by 14.4 recall points
• RiboSpan Trains a 1.61B RNA Encoder Natively at 10,240 nt and Leads Frozen Long-RNA Identity
• LaProp Decouples Adam's Momentum from Adaptivity and Survives Noise Adam Cannot
• 49 hours of dry EEG still do not saturate open-vocabulary silent-reading decoding

All paper explainers