# Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization arXiv: https://arxiv.org/abs/2511.15898 ยท HTML: https://mlsanity.com/paper/2511.15898/ ## Key facts - Cited by 2 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 31 of its 48 references that are in the map. - First posted on arXiv 19 Nov 2025. ## Placed in - Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/) ## Builds on (most cited first, 30 of 31) - [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020) - [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023) - [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023) - [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021) - [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024) - [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022) - [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023) - [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022) - [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) - [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024) - [SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification](https://mlsanity.com/paper/2305.09781/) (2023) - [Better & Faster Large Language Models via Multi-token Prediction](https://mlsanity.com/paper/2404.19737/) (2024) - [LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding](https://mlsanity.com/paper/2404.16710/) (2024) - [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024) - [DistillSpec: Improving Speculative Decoding via Knowledge Distillation](https://mlsanity.com/paper/2310.08461/) (2023) - [Multilingual Machine Translation with Large Language Models: Empirical Results and Analysis](https://mlsanity.com/paper/2304.04675/) (2023) - [Accelerating LLM Inference with Staged Speculative Decoding](https://mlsanity.com/paper/2308.04623/) (2023) - [REST: Retrieval-Based Speculative Decoding](https://mlsanity.com/paper/2311.08252/) (2023) - [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023) - [Online Speculative Decoding](https://mlsanity.com/paper/2310.07177/) (2023) - [TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding](https://mlsanity.com/paper/2404.11912/) (2024) - [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015) - [Cascade Speculative Drafting for Even Faster LLM Inference](https://mlsanity.com/paper/2312.11462/) (2023) - [Your LLM Knows the Future: Uncovering Its Multi-Token Prediction Potential](https://mlsanity.com/paper/2507.11851/) (2025) - [Block Verification Accelerates Speculative Decoding](https://mlsanity.com/paper/2403.10444/) (2024) - [Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement](https://mlsanity.com/paper/2402.14160/) (2024) - [Towards Optimal Multi-draft Speculative Decoding](https://mlsanity.com/paper/2502.18779/) (2025) ## Built on by (most cited first, 2 of 2) - [UniVer: A Unified Perspective for Multi-step and Multi-draft Speculative Decoding](https://mlsanity.com/paper/2605.04543/) (2026) - [Dynamic Delayed Tree Expansion For Improved Multi-Path Speculative Decoding](https://mlsanity.com/paper/2602.16994/) (2026) ## Abstract (arXiv) Speculative sampling reduces the latency of autoregressive decoding for target model LLMs without sacrificing inference quality, by using a cheap draft model to suggest a candidate token and a verification criterion to accept or resample this token. To improve acceptance and decoding efficiency, recent work has explored the multi-draft extension, where at each step n draft tokens are generated, and the verification criterion is a distribution conditioned on these. When this criterion maximizes the probability of accepting some draft token, it is called the optimal transport (OT). However, finding the OT is difficult, as it is the solution of a linear program (OTLP) in over Vn variables, with V being the vocabulary size. Two recent theoretical works have reframed the OTLP in terms of importance sampling or subset selection. In this work, we prove that these formulations are equivalent to an exponentially large relaxed OTLP, so it remains infeasible to solve. Then, we reverse engineer subset selection to formulate the OTLP as a max-flow problem. With a novel application of polymatroid theory, we reduce the exponentially large OTLP to a convex optimization problem in at most V variables. This allows us to devise an algorithm for optimal n-draft speculative sampling when the n tokens are chosen i.i.d. from a single draft model, which can be tuned to arbitrary accuracy. Finally, we measure acceptance rates and algorithm runtimes for various n and top-k draft sampling settings. Our findings give the first multi-draft algorithm with 90% acceptance and under 100 ms of overhead per generated token with negligible deviation from the target model distribution.