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

Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Speculative decoding

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.

Shows that recent optimal-transport (OT) reformulations for multi-draft speculative sampling are equivalent to a relaxed LP, reduces it to max-flow and polymatroid-based convex minimization ("global resolution"), enabling near-exact OT computation for i.i.d. drafts with much lower runtime.

Problem

Computing the optimal transport (verification criterion) for single-step multi-draft speculative sampling is an LP with exponentially many variables in the vocabulary size and draft count, so exact optimal acceptance is infeasible to find for realistic vocabularies.

Approach

Shows canonical decomposition equals a relaxed OTLP, converts the subset-selection formulation into a max-flow problem with complementary slackness, and uses polymatroid theory to reduce the outer system to a truncated convex minimization over at most V variables (global resolution) for i.i.d. drafts.

Key results

• Global resolution (tau=1e-3) solves (k=10,n=4) Llama-3 OTLP in 40.30 ms/token at 97% success, versus 4000+ ms/token for general LP, and runs under 100 ms/token across settings.
• Under a 100 ms/token limit, global resolution (tau=1e-3) achieves 90.04% acceptance on Llama-3 vs 89.01% for max-flow and 83.94% for general LP.
• In the multi-step SpecTr setting, global resolution improves walltime decoding by nearly 2x over the baseline.

Surprising findings

• For temperatures below 0.8, increasing k beyond 10 rarely improves optimal acceptance, so simpler exact solvers can suffice at low temperature.

Limitations

• Global resolution can fail to terminate within budget, falling back to other solvers in some cases.
• Results and algorithm are restricted to i.i.d. draft sampling from a single draft model; non-i.i.d. extensions are left to future work.
• Experiments use top-k truncation of the vocabulary; full-vocabulary performance is not reported.

Experimental setup

Datasets: random prompts from each dataset (40 per dataset)

Benchmarks: OTLP solve time on Llama-3 and Gemma-2 target/draft pairs optimal acceptance rate over top-k and n

Metrics: optimal acceptance rate average solve time (ms/token) solve success rate walltime speedup (multi-step SpecTr)

Baselines: general LP solver max-flow solver optimized max-flow K-SEQ greedy multi-draft construction MSS RSD

Builds on: speculative sampling SpecTr K-SEQ canonical decomposition of optimal transport subset selection formulation of multi-draft acceptance

Closest papers by meaning

• Towards Optimal Multi-draft Speculative Decoding (ICLR 2025 · similarity 0.91)
• Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits (ICLR 2025 · similarity 0.90)
• A Theoretical Perspective for Speculative Decoding Algorithm (NeurIPS 2024 · similarity 0.90)
• Cactus: Accelerating Auto-Regressive Decoding with Constrained Acceptance Speculative Sampling (ICLR 2026 · similarity 0.89)
• Speculative Decoding with CTC-based Draft Model for LLM Inference Acceleration (NeurIPS 2024 · similarity 0.89)
• Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs (ICLR 2026 · similarity 0.89)