Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Optimization
Authors: Rahul Krishna Thomas
Arka Pal
Venue: ICLR 2026 Oral (2026)
Keywords: LLMs
Inference
Optimal Transport
Speculative Decoding
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We reduce optimal multi-draft speculative sampling to a convex minimization problem, and solve a truncated version to achieve state-of-the-art acceptance with negligible performance degradation.

Abstract: 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 $V^n$ 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.

Published as a conference paper at ICLR 2026
GLOBAL RESOLUTION: OPTIMAL MULTI-DRAFT SPEC- ULATIVE SAMPLING VIA CONVEX MINIMIZATION
Rahul Krishna Thomas 1.2+
Arka Pal
Ritual
"Columbia University
Ritual
ABSTRACT
Speculative sampling reduces the latency of autoregressive decoding for target model LLMs without sacrificing inference quality, by using a cheap draft model suggest candidate token and verification criterion to accept resample this token. To improve acceptance and decoding efficiency, recent work has explored the multi-draft extension, where at each step ni 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, is called the optimal transport (OT). However, finding the OT is difficult, as it is the solution of a linear program (OTLP) over V variables, with V being the vocabulary size. Two recent theoretical works have reframed the OTLP in terms of importance sampling or subset selection. this work, we prove that these formulations are equivalent to exponentially large relaxed OTLP, so it remains infeasible to solve. Then, we reverse engineer subset selection to formulate the OTLP as a max- problem. With novel application of polymatroid theory, 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--raft 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.
INTRODUCTION
Language models have demonstrated state-of-the-art performance over wide variety of tasks, such as code generation, language processing, and complex reasoning (Zhu et al., 2024; Kasneci et al., 2023; Thirunavukarasu et al., 2023). Many transformer-basee based language model families, like GPT (Radford et al., 2018; 2019; Brown et al., 2020; OpenAI, 2023) and Llama (Touvron et al., 2023b;a), use autoregressive decoding, where tokens are generated sequentially. However, autoregressive decoding leads to significant computational bottlenecks. For LLMs with hundreds of billions of parameters, these bottlenecks are generally dominated by memory bandwidth, not raw FLOPs (Fu et al., 2024).
Speculative sampling was proposed by Chen et al. (2023); Leviathan et al. (2023) to reduce the punitive costs of autoregressive decoding for an expensive target model. Motivated by speculative exccution in compilers, this uses light draft model to generate draft sequence. Each token of the draft sequence is then accepted or resampled using a criterion, which ensures that the first resampled token and all prior accepted tokens follow the true target distribution. The greatest speedup is obtained by maximizing the acceptance probability, as accepted tokens are generated with essentially no inference overhead.
Recent extensions of speculative sampling have fixed the draft sequence length to one (single-step) and focused on the theoretical properties of the multi-draft setting. In this setting, 2 draft tokens are generated at the single draft sequence position, for example by sampling from one or more draft models. The corresponding target logits are efficiently computed in parallel, adding minimal overhead to single target forward pass for reasonable batch sizes n. Finally, conditional
"Correspondence rahul kri Shhathomas@gma1 com.

---

Published as a conference paper at ICLR 2026
distribution over the n draft tokens (verification criterion) generates verified token, which must respect the true target distribution. This conditional distribution called the optimal transport (OT) when the verified token lies among the draft tokens with maximal probability, thereby giving the optimal acceptance probability and speedup.
The first theoretical work in the multi-draft setting was by Sun et al. (2023), who proved that the OT is a solution to an optimal transport linear program (OTLP). This LP has a number of variables exponential in the vocabulary size, so it is not even feasible write down for large vocabularies. However, Khisti et al. (2025) recently compactified this into a two-step canonical decomposition: importance sampling and single-draft speculative sampling. When n = 2 draft tokens are sampled from one draft model. this leads to an explicit expression for the optimal acceptance probability. Concurrently, Hu et al. (2025) has reframed optimal acceptance as the solution to subset selection problem, which matches this n = 2 expression and generalizes it to n 2 3 draft tokens.
While these works can compute optimal acceptance for n 2 2, they do not solve the OTLP. There is therefore, to the best of our knowledge, no exact and efficient method to solve the OTLP and find the optimal verification criterion in multi-draft speculative sampling. The only known exact method an LP solver, which has exponential time complexity for the OTLP. Existing approximation algorithms such as K-SEQ (Sun et al., 2023), MSS (Miao et al., 2024), RSD (Jeon et al., 2024), and LP and vocabulary truncation (Khisti et al., 2025) cannot guarantee near-optimal speedups: K-SEQ has (1 - 1 /e/e) approxxtttiiiio guarantee, but the others have no formal guarantees.
Our main contribution is the first efficient algorithm to compute the OT to arbitrary accuracy when n 2 2 draft tokens are i.i.d. sampled from a draft model, in the single-step multi-draft setting. Our algorithm is fast for much larger vocabularies and choices of than previous works, permitting higher acceptances rates. Altogether, our theoretical and experimental contributions are:
We show how the canonical decomposition (Khisti et al., 2025) of the OTLP is exactly equivalent to LP relaxation in the derivation of the subset selection formulation (Hu et al., 2025), unifying the current state-of-the-an in multi-draft theoretical literature.
We reverse the derivation in (Hu et al., 2025) to obtain a max-flow algorithm to compute the OT for arbitrary Pdraft While the max-flow network is enormous, one can compute feasible flows along source edges in near-linear time with a greedy polymatroid algorithm. With these flows set, the OT can be computed to arbitrary accuracy by solving truncated convex minimization problem. This leads to our global resolution OT algorithm in the i.i.d. setting.
We compute optimal acceptance rates and algorithm runtimes for various choices of n and top-k sampling of the draft model in the i..dd setting. Our algorithm permits practical choices of & and n where acceptance rates are over 90% and average runtime under 100 ms/token, whereas generic OTLP solvers can only achieve 84% in the same limit. Thus, obtain a new state-of-thh-ar in optimal multi-draft speculative sampling.
2 RELATED WORK
To improve the number of accepted tokens, most theoretical extensions of speculative sampling have been split into multi-step and multi-draft, which alter the verification or drafting mechanisms.
In the multi-step setting, which was outlined in the first few speculative sampling works (Chen et al., 2023; Leviathan et al., 2023), the draft model autoregressively generates sequence of candidate tokens, and accepts the longest prefix of tokens that pass verification. Some work has fixed verification as independent single-step verification, and focused on improving acceptance through smarter drafting. such as database retrieval (He et al., 2023), cascading (Chen et al., 2024), hierarchial drafting (Sun et al., 2024a), knowledge distillation (Zhou et al., 2023b; Liu et al., 2023), layer skipping (Zhang et al., 2023; Elhoushi et al., 2024), or multi-token sampler heads Gloeckle et al. (2024); Samragh et al. (2025). Other work has developed new verification protocols, such as tree Monte Carlo (Hu & Huang, 2024) and block verification (Sun et al., 2024b), with the latter shown to be naturally optimal.
While most multi-step works are based on lingle-draft speculative sampling, tree-based attention frameworks (Sun et al., 2023; Spector & Re, 2023; Cai et al., 2024; Li et al., 2024) extend to the dulti-draft setting by creating a draft tree of token sequences. Our work instead focuses on the single-step, multi-draft setting, which is key to improving these frameworks. For example, SpecTr
2

---

Published as a conference paper at ICLR 2026
(Sun et al., 2023) any single-step, multi-draft method, e.g. approximate OTLP solver like
K-SEQ. By improving the single-step OTLP solver, we see efficiency gains in multi-step SpecTr.
BACKGROUND ON MULTI-DRAFT SPECULATIVE SAMPLING
For review multi-draft speculative sampling, see Appendix Here, we review the theory of single-step multi-draft speculative sampling, which is primarily based on the OTLP (Sun et al., 2023) and its subset selection formulation (Hu et al., 2025).
3.1 THE OPTIMAL TRANSPORT LP
Many multi-draft procedures respect the target model distribution (e.g. K-SE)), but interested in the one with greatest speedup. In the single-step setting, the parameters of this optimal sampling optimal transport linear program (OTLP) (Sun al., 2023). In
procedure solutions terms of the number of draft models n, the target model distribution over the vocabulary V. and the n-token draft distribution Pdraft over V", the OTLP has V*+1 nonnegative variables C, for i v,ïe T and is written as:
max Ch0
ΣEO C5
s.t.
cc. VIEV, TEV"
ΣGE Pimffi (7) LEV
ViEV V".
(1)
iEViEA:
Here, A; = (i ym : E set(i)} is the incidence set of each i E V over all drafted n-tuples. The optimal objective value the optimal acceptance rate a", and optimal parameters C give joint distribution (í., 8) over V V with marginals p. Panat The optimal transport (OT) is the induced conditional distribution x {i]l),, which gives the probability of verifying i E V given n draft-sampled tokens e V*. Solving the OTLP in this form is infeasible due to its exponential size, even for 2 and V small 1000: Section 7.
3.2 SUBSET SELECTION FORMULATION
Computing the optimal objective of the OTLP can be far simpler than solving it. Hu et al. (2025) show this by reducing the optimal acceptance computation to subset selection (Equation (4)) for any Pdmat This allows them bypass the OTLP and quickly solve for a* for some choices of Pana (see Section 5.1). To do this, they form a relaxed OTLP in nonnegative variables S for E V. V":
max 5z0
Σ Sia
s.t.
Σ
15,55p00 VIEV, Σ
S S Pama SEV
Vi VM
SEV TEVO
TEVa
(2)
=
Vi v.i A+.
One can get OTLP solution C' from relaxed OTLP solution S with residuals:
10s (i) (i)
C S + (te)
5
(1) p(1)
Σ
Parafi i Paran
Si.
(3)
SEV
LEV
They then dualize the relaxed OTLP and simplify it to the following. We defer details to Appendix E. Theorem 3.1 (Hu et al. (2025)). The optimal acceptance rate a² can be computed as
a' = = min (H), ((H) = -Er(0 Σ NEH TEH
Panff
(4)
HCV
4 CANONICAL DECOMPOSITION BY RELAXED LP
The main result of Khisti al. (2025) is the canonical decomposition of the OT: it can be split into importance sampling and single-draft speculative sampling. First, after sampling the n draft tokens i ~ Paraft samples token in set(i) using importance-weighte distribution B(1lī). Then, one applics single-draft speculative sampling from Chen et al. (2023); Leviathan et al. (2023) on i. Canonical decomposition thus computes the OT by solving non-linear /-optimization problem.

---

Published as a conference paper at ICLR 2026
In this section, prove that solving the B-optimization problem is mathematically equivalent to solving the relaxed OTLP from Equation (2). The optimal importance sampling parameters in the canonical decomposition can be formed by normalizing the optimal relaxed LP parameters S in non-degenerate cases, and choosing a uniform split in degenerate cases. The proof is in Appendix B. Theorem 4.1. Define D - v to be the set of E V where all S 1,
= 0 in Equation (2). Then
i &
D
Ejev St
8(17)
33
(5)
1/i E ser(i)] iE
[sec(3) solve the importance sampling optimization problem in canonical decomposition.
Thus, canonical decomposition provides computational advantage over the relaxed OTLP.
5 OPTIMAL MULTI-DRAFT SPECULATIVE SAMPLING BY MAX-FLOW
Much of the work by Hu et al. (2025) employs subset selection (Equation (4)) to efficiently compute the optimal acceptance a* 1 v (H)) for some Paran schemes. However, they do not have method for computing the OT efficiently from H They only solve for the OT when Pamni is greedy (choose the top solving the OTLP Excluding this Pdma. there is no known method which computes the OT for and faster than directly solving the OTLP or relaxed OTLP with an LP solver; this includes canonical decomposition, since Theorem 4.1 shows it reduces to the relaxed OTLP.
tokens in a draft model q and sample the last without replacement), by directly
In this section, we formulate more efficient method solve the OT, using H* We first enumerate cases where efficient computation of H is possible, building on Hu et al. (2025). Then, we show how solving for 5* in the relaxed OTLP is a max-flow problem. Finally, we reverse the subset selection derivation using complementary slackness, to obtain a more compact feasibiliiy max- max-flow problem that depends on H This allows simplification of Equation (3) to a sparser form.
5.1 EFFICIENT RECOVERY OF H
Computing a reduces to minimizing the set function 1 2 - IR defined in Equation (4). While this is NP-hard for general th, there are polynomial & is submodular. In their work, Hu et al. (2025) show submodularity holds if Pánat samples i.i.d. times from a single draft distribution q. In Appendix C, we generalize their argument to paran that samples independently from any draft distributions. These polynomial -ime algorithms are often impractical for large V. but the use of top-p/k /k sampling on the draft model(s) can restrict the domain V and make this feasible. Also, when n = 2, minimizing v is submodular quadratic psuedo-boolean optimization (QBPO), where far more efficient algorithms exist: see Appendix D for more details.
approaches (Iwata, 2008; Orlin, 2009) when
When Parat samples i..dd from q. Hu et al. (2025) able to improve on standard submodular algorithms to obtain an O(V log V) approach. They show that it suffices to sort i E V in decreasing order of (i)/p(i), and select the prefix of this list which minimizes th. We will mainly be concerned with this setting, rather than general submodular v setting, which we leave to future work.
5.2 MAX-FLOW REDUCTION OF RELAXED OTLP
We now describe the relaxed OTLP (Equation (2)) as max-flow problem. Max-flow solvers are much faster than general LP solvers here, as we empirically demonstrate in Section 7.
Define bipartite network Ω with source s, left vertices V. right vertices V and sink L. We draw edges + i with capacity p()) for i E V. edges i + ī with capacity oo for E V, E A,, and edges 7-> f with capacity Paran (?) for E y", Considering variables 5,5 as flows along i - i, we see the capacity constraints exactly reduce to the inequalities in the relaxed OTLP, and the maximization objective is the same maximizing the flow. The zero equality constraints are handled by the fact that we only draw edges i + E A4. Thus, S can be computed by running max-flow on Ω.
Here, only O(V) possible draft n-tulees can he sampled, rather than V/ the OTL. is feasible solve.
4

---

Published as a conference paper at ICLR 2026
5.3 OPTIMIZING MAX-FLOW WITH COMPLEMENTARY SLACKNESS
While the max-flow formulation is advantageous over a general LP solver, it can still be prohibitive for large yd, Is there any way use information like H* to reduce the size of the network !?? We find the answer is affirmative through complementary slackness, a method to reverse the dualization step in Section 3.2. For background on the dualization and the proof of below, see Appendix E. Theorem 5.1. Any nonnegative S defined over V x y satisfies the following system,
Σ ?g(H-)"
H
Σ S Panatl (7)
vi Φ (H*)",
(6a)
Σ
p(i) ViE H"
Σ
Vi E (H*)", S (1)
(6b)
(E(H")"
NEH-
11;=0 (
Wi E v As, =
(6c)
if and only if is an optimal solution to the relaxed OTLP.
Once we eliminate all zero variables in Equation (6c) from the top two lines, call Equation (6a) the outer system and Equation (6b) the inner system. These are independent, as the former has terms with i & H 7 (H*)", 7 E A; and the latter has terms with E H In the same way as the relaxed OTLP, these represent max-flow problems over a bipartite network: see Appendix F for a proof of this equivalence. Thus, we can solve the outer and inner systems by creating corresponding flow networks, solving for the max-flow, and then recovering the variables along the sc-capacity edges. To form the flow network for the outer system, we restrict S from Section 5.2 to left vertices V \ H" and right vertices V \. (H*)". For the inner system, we restrict Q to left vertices H' and right vertices (H*)". The complexity of these networks depends on H
(H*)", A;
Finally, to compute C from the full S* given by the outer and inner system solutions, we use Equation (3). In fact, the equality conditions in Theorem 5.1 tell us some residuals are zero:
(1) 0
E H" Parat (i) = O Vi & (H*)",
Thus, when we sample the n-tuple of draft tokens w E V", and aim to compute the slice of the OT (+lw) along this n-tuple, we only need to solve for the variables Cj,,, for i E V. which simplify to
S
E <ete(w).
Peraft (w) Ejer plos (j) p (1), i w W (11*),,
Crus
(8)
else,
by application of Equation (3). In fact, by independence of the outer and inner systems, examining the variables above, we only need to solve the outer system if w & (H* When H' is large, this is a significant speedup, as the outer system network is far smaller than the one in Section 5.2.
6 NEAR-LINEAR SAMPLING VIA GLOBAL RESOLUTION
Our max-flow reduction of complementary slackness shows that for arbitrary Pdraf, we should not expect to be able to compute C* in less time than the max-flow approach. Across all flow networks we constructed, the capacities were p(t),Purall Pi)an() for i E V. V V", which are essentially free parameters. Thus, a faster algorithm would likely require faster general max-flow solver.
However, when Paran is formed by i.i.d. sampling from a draft model q. we can exploit additional structure to solve the complementary slackness system efficiently. First, we show how to compute feasible values of the outer residuals ( for i E V H' using polymatroid theory. This turns all conditions in Theorem 5.1 involving p(i) into equalities. Once these are equalities, there exists a solution to the outer and inner systems parametrized by variables for i E V H" and i E H" such that each row of the solution is a softmax over a slice of variables. These variables can be computed by minimizing associated convex functions. We call this approach global resolution. While this is not efficient for large V. by truncating the convex functions to a smaller subset of variables, we can solve approximate optimization problem with negligible accuracy loss.
5

---

Published as a conference paper at ICLR 2026
Global resolution (Algorithm 1) follows three key steps. For discussion non-ii.d. extensions of these steps, such as to distinct independent drafts or sampling without replacement, see Appendix
1. We solve for H* _ V. As per Section 5,1, existing methods (Hu et al., 2025) allow recovery of H" in O(V log V) time, so we take access to H* for granted throughout this section.
2. With H* we solve for the outer residuals yTh (i) for i V H in the outer system. This can be done in O(V log V) time with polymatroid theory, as in Section 6.1. This allows us to replace the p(i) upper bounds in Equation (37a) with equalities to p; p(i) (i)
3. We solve truncated convex minimization problems in Theorem 6.4 (requires p; from above) and Theorem 6.5 to find approximate global solutions to the outer and inner systems". These problems are defined for general truncated variables sets T in Section 6.2. In Section 6.3, we show how to carefully choose T, and then compute the OT from the convex solutions, to get strong provable approximation guarantees. We also show in Appendix K. how to keep the convex problems under (([T)"/n)) variables and generally speed up minimization.
Prior our work, progress had only been made step 1. Knowledge of only H* allows computation of the optimal acceptance a = v5( H"),, but not the optimal verification algorithm itself.
Excluding step our algorithm is O log V). The runtime of step 3 is quite variable, and can depend significantly on the and y distributions. In some cases, the minimum truncation size [T] required to achieve a good provable approximation too large run on the order of milliseconds, so we terminate global resolution early. Nevertheless, in practice (Table 1), this is not prohibitive.
6.1 OUTER RESIDUAL LP
From Equation (7), there are two classes of nontrivial residuals: the outer residuals p** for i V \ H* and the inner residuals pa (7) for (H*)". While solving for the inner residuals is difficult', we can compute outer residuals with the outer residual LP (Theorem 6.1, see Appendix G).
Theorem 6.1 (Outer Residuals). We have 0 < p. s p(t) for E VV H are feasible in
ΣNS Σ p(1) (VVSS) VS
iES
ÉES
with equality at V H and only (*) p(i) - ps are feasible in the outer system.
This LP has up to 2 constraints, so it is infeasible to even write down. Fortunately, most of these constraints are redundant when v is submodular. By applying polymatroid theory (see Appendix H), we get closed-fom solution by taking consecutive differences of minimums of tb.
Theorem 6.2. Suppose va is submodular. Fix any ordering { en of
H Then
Po. = p(e:) + min (T) min (T) Vi [k]].
(10)
T2H
T2H:
is a solution to Theorem 6.1, where H; = H" U (U:...,, vb) for each E [A]]
Computing the min & terms is extremely prohibitive, since there are O(V) of them, so could require up to V submodular minimization calls. However, for the i.i.d. Piran construction, each call can be made O(V log V) with a procedure that evaluates across prefixes of a sorted list, by following the q-convexity approach in Section 4.2 of Hu et al. (2025) verbatim.
Lemma 6.3. Suppose Panaft is formed by sampling i.i.d. from g. Fix subsets A C C.V. Then min ((LLUA) osis BYAl
min ACSCB
(SS)=
(11)
B
where L; is the ith prefix of B \ A when its elements x are sorted by decreasing ((x)/p(x).
We can further optimize this to total runtime of O(V log V) across all calls, by exploiting the fact that the ordering of V H in Theorem 6.2 arbitrary. By selecting ......, Up in increasing order of p())/ know from Lemma 6.3 that each min (T) lies among (HH,). ..., (HH)) Thus, using cumulative minimums, we can get all min tp terms in (V log V).
2 As mentioned the end of Section 5.3, we only need to solve the outer system w & (H*)". This is primarily due to the exponential number of inner residuals. Even if Para is i.i.d., it is not guaranteed that some Pain admits similar i.i.d. structure, without additional assumptions on p and q.

---

Published as a conference paper at ICLR 2026
6.2 TRUNCATED OUTER AND INNER CONVEX SOLVERS
Once we have computed feasible values for the outer system residuals (1) - p(t) ps for i V H (Theorem 6.2), we can turn all p(i) upper bounds in the outer system (Equation (6a)) into P; equality bounds. Our key observation is that as the outer system is feasible, it has some global low-dimensional solution parametrized over H The rows of this solution are formed by taking the softmax of slices of the parameters, and the parameter values can be computed to arbitrary accuracy by minimizing a truncated convex function as Theorem 6.4 (proof in Appendix I),
Theorem 6.4 (Outer Convex Solver). Fix and T S V H Define DT VW + IR by:
@r (()()))))))
E (H
Peraft (i) log
Σ
E
PeOs-
(12)
ieT
This is constant over 04 for i & Then there is some (0 (eE) such that
VVr cc cr
Σ (
(13)
VEEH-UT
Furthermore, for any (as)ee,, the following variables solve the outer system,
ea
S Σ EjEmt(i) eag (Drrof Vi ser(i)
H P,, (H*)",
(14)
with al most | ((x))enn)) + 3er total LI deviation from the p(i) equality constraints.
The inner system can be approached similarly, but the function now includes a slack term*, as we have not solved for the inner residuals Paraf (7). The proof can be found in Appendix
Theorem 6.5 (Inner Convex Solver). Fix e > 0 and T C H Define Or : R 7 IR by:
Or((Oz))EH))
Σ Pdrafp log
Σ
cas
Σ iET
p(i)a
(15)
TET
(Exer(i)
This is constant over a; for H \T Then there some (af) such that
[VOr((a.))EH))) )l1 SE+ YT Σ
q())
Σ
(16)
Furthermore, for any (as)EEH- the following variables solve the inner system,
ea:
S I Ejeme(s) eaj PPdrafi ( Vi ser(),, (1*)",
(17)
with at most [[ )ll 3yr total LI deviation from the p(i) equality constraints.
In essence, solving for global softmax solution in complementary slackness reduces to minimizing (finding a point with near-zero gradient) a convex function defined over variables the truncated set T: this is Φr for the outer system and Or for the inner system. When minimizing Φ and O7, the total deviation from the p(i) equality constraints is guaranteed fall under 5eg and 5 respectively, by setting ég, Tr in the solvers and using the gradient existence statements from the theorems.
When we increase the size T,, the error bounds eT and "r (the tunable errors) approach zero. Thus, approximate the true complementary slackness solution to arbitrary accuracy. To prevent excessive runtime, we may terminate early the size [T] of the convex minimization problem exceeds preset threshold, maximum iteration count in the minimization algorithm is reached. Due to space constraints, we clarify these details and our minimization approach in Appendix K.
WWe cannot do this for the outer system. This solver has one variable for each equality constraint. However, the outer system has exponentially many ((²2 (H+*)" equalities hefore outer residual computation. Thus, the polymatroid approach necessary make even truneated convex solver practical for the outer system.
7

---

Published as a conference paper at ICLR 2026
Algorithm 1: Global Resolution
Input: V. p. q, n, error threshold т, draft count n, drafted n-tuple w (w1,...,wn) ~ g(-)
Output: Optimal transport slice T(|Ww)
Compute H' from
V. n as Section 5.1
Compute Pj for all V \ H" from p. q. V, in Theorem 6.2 and Lemma 6.3
if Wf::...,,,, w,,,
E H" then
Choose minimal T S H* such that 7T T
Find inner system variables S using Theorem 6.5, stop at | s 5T
return normalized C.w from S and p: in Lemma 6.6
Choose minimal T' S H" such that ET T
Find outer system variables S1, using Theorem 6.4, stop at V S 5r
return normalized C., from S in Lemma 6.6
6.3 TRUNCATION SELECTION AND APPROXIMATION GUARANTEES
Once we have used the outer and inner convex solvers to compute the approximation the real complementary slackness solution S (all variables not in these systems are zero), we plug in the former into Equation (3) to obtain an approximation C' to the real optimal transport solution C*:
E set(i),
p(i) - Pi E JEV (p(i) -P))
C5.=
Paraft (7)
Σ (Eset(?)
S
i i4 (18)
else.
The following lemma (proof Appendix I.) ensures that the tunable errors Theorem 6.4 and Theorem 6.5 translate directly to bounds on deviations in the OTLP solution and acceptance rates.
Lemma 6.6 (Approximation Guarantee). Solve for ps over i E V H' as in Theorem 6.2. Using these values, let S be defined as in Theorem 6.4 with LII deviation and Theorem 6.5 with LI deviation 3. Then C2, as defined in Equation (18) satisfies the OTLP, with to + 23 total LI deviation in the p(i) equality constraints and a + 3 total deviation in the optimal acceptance rate.
Using the guaranteed 5ET and 5-T deviations for the outer and inner solvers, we can therefore choose suitable 7 to ensure the tunable errors ÉT, do not exceed a specified error threshold as Lemma 6.6 ensures that sampling from the OT induced by this approximate C' will deviate by most 157 from the true target distribution in L1 distance, and deviate from the optimal acceptance rate by at most 10r. We present the full global resolution algorithm with the error threshold in Algorithm 1.
EXPERIMENTS
In this section we empirically test the efficacy of our new algorithms for i.i.d. multi-draft, single-step setting. First, we show that optimal acceptance rates can substantially increase with a higher number of drafts n, and larger k in top-k sampling of the draft model. We then compare times against a standard LP solver for various k; n. Our algorithms are practical for a much wider range of k n, achieving state-of-the-art optimal acceptance rates in multi-draft speculative sampling. Details on our setup for both acceptance and solve time experiments are given in Appendix M.
algorithmss' solve
7.1 OPTIMAL ACCEPTANCE FOR INCREASING k AND n
For target and draft models, use the pairs Gemma-2 27B/2B and Llama-3 70B/8B (Touvron al., 2023a; Team, 2024). We test < 10 and k {10, 100, ... 10 log Vl V). Note that top-k sampling truncates the vocabulary V to size l in the relaxed OTLP, so that compute- heavy baseline approaches like LP and nax-flow solvers remain feasible. For more detail, see Appendix N.
Our results are shown in Figure| We observe significant improvements in acceptance as k increases from 10 to 1000: for example, a marginal increase from 0.8 0.95 means nearly 10% more tokens
8

---

Published as a conference paper at ICLR 2026
generated at extra cost. However, there diminishing returns for k 2 10000. Thus, top-k sampling is a viable method to reduce OTLP complexity without sacrificing acceptance. There also steady improvement from increasing n for larger k, demonstrating the utility of higher draft counts.
Acceptances
Acceptances
1.00
0191
0/91
Optred 1tes
0.97
0.90
0.83
0.03
0.80
6.00
0.75
2-1000
0.79
0-1000
0.70
0.70
n.number tehars))
Figure 1: Optimal acceptance rates from n i.i.d drafts with top-k sampling with with target/draft pairs of Gemma-2 27B/2B and Llama-3 70/8B, Increasing k improves acceptance rate significantly up to k 1000, and increasing n also results steady increase in optimal acceptance.
Further, in Appendix O, compare these acceptance rates to those for the greedy construction by Hu et al. (2025), described at the start of Section 5. For both Gemma-2 and Llama-3, we find that i.idd acceptance rates are higher than greedy for lo 2 100, with improvements near 2% for larger & and
(ks n)
General LP
Max-Flow
Opt. Max-Flow
G.R. (r 10 10
G.R. (T 10
(10, 2)
4.07
2.45
2.51
5.27 (98%)
7.62 (93%)
(10, 3)
30.14
3.80
3.88
17.35 (98%)
23,95 (87%)
(10, 4)
4000+
74.21
74.37
40.30 (97%)
54.84 (86%)
(10,
400000+
10000+
10000+
70.75 (96%)
94.79 (85%)
(100, 2)
4000+
72.28
63.03
23.92 (38%)
25.47 (23%)
(100, 3)
400000+
200000+
200000+
30,52 (23%)
38.44 (14%)
(1000, 2)
OOM
400000+
400000+
34.94 (31 %)
47.46 (15%)
Table 1: Average Llama-3 solve times (ms/token) over k n, for the five i.i.d. OTLP solvers. General LP and max-flow are baselines, and optimized max-flow and global resolution are ours. Lower numbers are better. Red numbers are lower bounds from small scale tests due to excessive runtime. Global resolution can be 10,000+ times faster than others. Global resolution deviates from the target distribution by at most 157 in LI distance, and from optimal acceptance by most 10r. We include success rates for global resolution can terminate early sometimes.
10-3 10-1) 1)
7.2 OTLP SOLVE TIME EXPERIMENTS
Here, we compute empirical average solve times (per token) for the relaxed OTLP across 40 random prompts from each dataset, for five methods: (1) a general LP solver, (2) a max-flow solver (Sec- tion 5.2). (3) an optimized max-flor flow solver (Section 5.3, but using normal max-flow when solving both inner and outer systems for stability), (4) global resolution (Section 6) with r 0.001, and (5) global resolution with 7 = 0.0001. Lemma 6.6 ensures (4) and (5) deviate from the target distribution by at most 0.015 and 0.0015 in L1 distance, and are within 0.01 and 0.001 of optimal acceptance.
Our compared average solve times for Llama-3 are shown in Table 1. For global resolution, we also include solve success rates, since it can terminate early. We only include (k, n) pairs where least one of the first three solvers finishes in under ten minutes per token. We see that the global resolution solver is sometimes nearly thousand times faster than the other three methods, with runtimes always under 100 ms/token. In Appendix P, Gemma-2 results show a similar trend.
Finally, in Table 2, enforce average time limits of 10 and 100 ms/token, and compute the acceptance for each solver's 's best (k, n) setting that adheres to the limit. Since global resolution can fail, we default the best of solvers (1), (2), (3) in this case, and only keep settings whose aggregate

---

Published as a conference paper at ICLR 2026
average runtime falls under the time limit. For Llama-3, global resolution with 7 0.001 and
r = 0.0001 achieve 1.03% and 0.47% higher acceptances than the other solvers for 100 ms/token, and 1.71% and 1.16% higher acceptances for 10 ms/token. While the improvements for Gemma-2 are smaller, they are significant. Thus, global resolution is the state-of-the-art OTLP solver.
Limit
Llama-3
Gemma-2
(ms/tok)
Gen. LP
M.F.
G.R.
G.R.
Gen. LP
M.F
G.R.
G.R.
7 10
7 10
T
3
T 10"
10
82.53%
83,94%
85.65%
85. 10% 89.46%
79.03 79.03%
80.69%
81.90%
81.35%
100
83.94%
89.01 %
90.04% %
80.69%
85.83%
86.60%
86.07%
Table 2: Best acceptance rates for baseline solvers (general LP) and ours (max flow, optimized max-flow, global resolution with r = 10 10=4)00+00 on Llama-3 and Gemma-2 under average solve time limits of 10 and 100 ms/token. Optimized max-flow numbers are the same as max-flow.
7.3 TEMPERATURE EXPERIMENTS
All results above are for the temperature 1 sampling the target model. In Appendix Q, we extend our acceptance rate analysis to temperature 0.2, 0.4, 0.6, 0.8 target sampling Gemma-27B/2IB We find that for temperatures below 0.8, increasing & from 10 rarely improves the optimal acceptance rate. This has the implication that approaches other than global resolution (general LP. max-flow, optimized max-flow) can be efficient and achieve high acceptance in low temperature settings.
In Appendix Q, also plot the solve time and success rate of global resolution with 10-4 as temperature varies. We find that global resolution has significantly lower failure rates and solve times low temperatures, because truncation can both be efficient and give a robust approximation for more concentrated distributions. In other words, our results use the worst setting for global resolution.
7.4 MULTI-STEP EXPERIMENTS
We extend method the multi-step framework SpecTr (Sun et al., 2023) to evaluate the real-world latency of global resolution. Our results are shown in Appendix R, alongside theoretical explanations of how global resolution errors scale with draft block length in the multi-step setting. We that global resolution is highly effective when integrated into multi-step frameworks, improving walltime decoding by nearly 2x compared the baseline, even when using a naive OTLP heuristic in failure cases. By using better OTLP solvers, such as K-SEQ (Sun et al., 2023), in such failure cases, we expect further decoding improvements to materialize.
CONCLUSION
Building on previous theoretical work in multi-draft speculative sampling, we derived comple- mentary slackness system to solve for the optimal transport (OT) parameters. We showed how this could speed up max-flow OT solvers through an approach called global resolution. We empirically demonstrated our algorithm achieved high acceptance rates with little overhead. Future work could examine the efficacy of this algorithm in the multi-step setting, or extend it to non-i.i.d. draft settings.
REPRODUCIBILITY STATEMENT
The majority of work is theoretical, and can be verified through the in-depth proofs we have provided in Appendices B to J. While the details behind our convex minimization approach are not included in the main body due to space constraints, we provide all necessary information to reproduce the gradient descent approach for our convex solvers in Appendix K. This includes our simplification of the functions to minimize, how to efficiently compute gradient values, what open-source minimizer to use, what thresholds are set, and how many iterations to run. We also describe our precise machine setup, dataset composition. and LP and max- max-flow solvers for baseline approaches in Appendix M, and we describe our experimental approach in Section 7.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min mnin-cut/max-flov algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1 00.109//PAM..2004..00
26(9):1 124-1114111 117,, 2004.
Arne Brøndsted and Ralph Tyrrell Rockafellar. On the subdifferentiabiiity of convex functions. Proceedings of the American Mathematical Society, 16(4):605-61) 611, 1965.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng. Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple I1m inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401.10774 2024.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/8, 2023.
Mark Chen, Jerry Tworek, Heewoo Jun, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03377 2021.
Ziyi Chen, Xiaocong Yang. Jiacheng Lin, Chenkai Sun, Kevin Chang, and Jie Huang. Cascade speculative drafting for even faster Ilm inference. Advances in Neural Information Processing Systems, 37:86226-86244 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Ostendorf, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 141468 2021.
Mostafa Elhoushi, Akshat Shrivastava, Diana Liskovich, Basil Hosmer, Bram Wasti, Liangzhen Lai, Anas Mahmoud, Bilge Acun, Saurabh Agarwal, Ahmed Roman, al. Layerskip: Enabling early exit inference and self-speculative decoding. arXiv preprint arXiv:2404.167110 2024.
Yichao Fu, Peter Bailis, Ion Stoica, and Hao Zhang. Break the sequential dependency of Ilm inference using lookahead decoding. arXiv preprint arXiv:2402.002 020057 2024.
David Gale. A theorem on flows in networks. In Classic Papers in Combinatorics, pp. 259-268.
Springer, 1957.
Fabian Gloeckle, Badr Youbi Idrissi, Baptiste Rozière, David Lopez-Paz, and Gabriel Synnaeve. Better & faster large language models via multi-token prediction. arXiv preprint 4rXiv:2404.19737, 2024.
Zhenyu He, Zexuan Zhong, Tianle Cai, Jason Lee, and Di He. Rest: Retrieval- based speculative decoding. arXiv preprint arXiv:2311.08252, 2023.
Alan J Hoffman and Joseph B Kruskal. Integral boundary points of convex polyhedra. In 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Ai pp. 49-76. Springer, 2009.
Zhengmian Hu and Heng Huang. Accelerated speculative sampling based on tree monte carlo. In Forty-first International Conference on Machine Learning, 2024.
Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A Rossi, Yihan Wu, Dinesh Manocha, and Heng Huang. Towards optimal multi-draft speculative decoding. arXiv preprint a7Xiv:2502.18779, 2025.
Qi Huangfu and Julian AJ Hall. Parallelizing the dual revised simplex method. Mathernttcaa Programming Computation, 10(1):119-142, 2018.
Satoru Iwata. Submodular function minimization. Mathematical Programming, 112:45-64 2008

---

Published as a conference paper at ICLR 2026
Wonseok Jeon, Mukul Gagrani, Raghavy Goel, Junyoung Park, Mingu Lee, and Christopher Lott. Recursive speculative decoding: Accelerating Ilm inference via sampling without replacement. arXiv preprint WrXh:22402114166 2024.
Enkelejda Kasneci, Kathrin Seßler, Stefan Küchemann, Maria Bannert, Daryna Dementieva, Frank Fischer, Urs Gasser, Georg Groh, Stephan Günnemann, Eyke Hüllermeier, Stephan Krusche, Gitta Kutyniok, Tilman Michaeli, Claudia Nerdel, Juergen Pfeffer, Oleksandra Poquet, Michael Sailer, Albrecht Schmidt, Tina Seidel, and Gjergji Kasneci. Chatgpt for good? on opportunities and challenges of large language models for education. Learning and Individual Differences, 103: 102274, 01 2023. doi: hit.1//..inii..2223.......
Ashish J Khisti. MohammadReza Ebrahimi, Hassan Dbouk, Arash Behboodi, Roland Memisevic, and Christos Louizos. Multi-draft speculative sampling: Canonical decomposition and theoretical limits. In The Thirteenth International Conference on Learning Representations, 2025.
Vladimir Kolmogorov and Ramin 7abih, What energy functions can be minimized via graph cuts? IEEE Transactions Pattern Analysis and Machine Intelligence, 26(2):147-159, 2004. doi: N0.1109//PAM.22004022000
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint arXiv:240..10077, 2024.
Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Alvin Cheung, Zhijie Deng, lon Stoica, and Hao Zhang. Online speculative decoding. arXiv preprint arXiv:2310.07117, 2023. 2023.
Alex Mallen, Akari Asai, Victor Zhong, et al. When not to trust language models: Investigating effectiveness of parametric and manparametric memories. arXiv preprint arXiv:2212.105111 2022.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang. Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang. Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume pp. 932-949, 2024.
OpenAl. Gpt-4 technical report. arXiv preprint 23Xi::2033.88744 2023.
James B Orlin. A faster strongly polynomial time algorithm for submodular function minimization. Mathematical Programming, 118(2):2372511, 2009.
Tiago P. Peixoto. The graph-tool python library. figshare, 2014. doi: 1060600/..iggaaaaatt 164194.
URL BRRLttt///Egsheeee com/aa/.c/ooo/ooo artaacieeeeeaa/.a atticlee/grap__too//1L1
Alec Radford, Karthik Narasimhan, Tim Salimans, and llya Sutskever. Improving language un-
derstanding by generative pre-training. https: wtt. http::////ddoooooi..o.eaaoa wtt.///eeeeeccc//ccocooooooe pdf, 2018
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. https://cdn.co
modell htageeeeedeesssttgeeeeeeeeee ure.uussreeeeeseeeriisieeeeee miltitask_ pdf, 2019.
Mohammad Samragh, Arnav Kundu, David Harrison, Kumari Nishu, Devang Naik, Minsik Cho, and Mehrdad Farajtabar. Your 11m knows the future: Uncovering its multi-token prediction potential. arXiv preprint arXiv:2507.11822 2025.
Alexander Schrijver et al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
Liwei Shen, Ruoxi Tao, Jinchang Ye, et al. Wildjailbreak: A dataset of adversarial chatbot jailbreak prompts. arXiv preprint arXiv:2406. 18510, 2024.
12

---

Published as a conference paper at ICLR 2026
Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308. 23000006038, 2023.
Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. Triforce: Lossless acceleration of long sequence generation with hierarchical speculative decoding. arXiv preprint wwXiv:2404.11912 2024a.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances Neural Information Processing Systems, 36:30222-30222, 2023.
Ziteng Sun, Uri Mendlovic, Yaniv Leviathan, Asaf Aharoni, Jae Hun Ro, Ahmad Beirami, and Ananda Theertha Suresh. Block verification accelerates speculative decoding. arXiv preprint arXiv:2403. 10444, 2024b.
Gemma Team. Gemma Improving open language models practical size. arXiv preprint arXiv:2408.00111 2024.
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature Medicine, 29: 1930-1940, 2023, doi: 10. 00.1038/441511-03-02222 articles/see /541e 023 02459- w. Review Article, Published: 17 July 2023.
w. URL https:/ www. nature. com/
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Naman Goyal, Eric Hambro, Haoran Azhar, Alice Rodriguez, al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint urXiv:2310.11387. 2023a.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Haoran Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 2093b,
Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Couraapea,, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.:: fundamental algorithms for scientific computing in python. Nature Methods, 17(3):261-21 2020.
Jun Zhang, Jue Wang, Huan Li, Lidan Shou, Ke Chen, Gang Chen, and Sharad Mehrotra. Draft & verify: Lossless large language model acceleration via self-speculative decoding. arXiv preprint arXiv:2309.08166 0816099........... 2023.
Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, et al. Instruction--flllwingg evaluation for large language models. arXiv preprint arXiv:2311.07911 2023a.
Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, Sanjiv Kumar, Fran-orasçois Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.00 084611, 2023b.
Wenhao Zhu, Hongyi Liu, Qingxiu Dong, Jingjing Xu, Shujian Huang, Lingpeng Kong, Jiajun Chen, and Lei Li. Multilingual machine translation with large language models: Empirical results and analysis, 2024. URL https: / arxiv. org/ abs
ab//////s/322////////////////3// 2304. 04675.
13

---

Published as a conference paper at ICLR 2026
A REVIEW OF SINGLE-STER SPECULATIVE SAMPLING
Single-draft speculative sampling aims to accelerate the autoregressive decoding of an expensive target model Mp with cheaper draft model Mg. which share common vocabulary V of size V. In autoregressive decoding, the token context с induces target and draft distributions p(z|c), q(ylc), Note that top-p/k k and temperature sampling simply change how p, q are computed from the logits Mp(c), (c()), so these can be plugged into any speculative sampling method.
Now, joint coupling (xx; y) of p, q is any joint distribution over V x V with marginal distributions P. P. Each coupling induces a transport πT (zly) from to p. which is conditional distribution where sampling yo ~ q(y) and zo <<rly))
equivalent sampling æg ~ p(z). speculative sampling, one samples candidate token from the draft distribution and passes it through the transport induced by some valid coupling v, to ensure the output matches the target distribution p.
The full single-step procedure is as follows. The key assumption which allows speculative sampling to improve latency is that computing p(x]cc; p(a] c, 3/) in parallel is not much slower than computing p(ælcc) alone, since LLM inference is often memory semory-bound rather than compute-bound.
1. Given a context c, sample ~ q(vlc) from the draft model.
2. Compute target probabilities p(z|c), p(x|(, c, yo) in parallel.
3. Sample To ~ (x))))) for some valid transport и,, and append the context c.
4. If wo you sample token from p(yle, 20) and append it to the context
Thus, whenever zu = Yo above, we generate two tokens (steps 3 and 4) at the cost of essentially one target forward pass, obtaining nearly 2x speedup. This means to maximize the speedup and achieve optimal single-draft speculative sampling, one must maximize P(zo- vo) = Exgy ((z a), achieved for the optimal transport π². This is called the acceptance rate, the probability that the g-sampled token is not altered by the transport. In the original speculative sampling work, Chen et al. (2023); Leviathan et al. (2023) computed a closed-form expression for x based on p(x|c), q( (c).
Sun al. (2023) extended this procedure to single-step multi-draft, by replacing ((xl)c with general n-token distribution Parn (y c) over y E V", which can be formed by i..dd sampling one draft model, independently sampling different draft models, or a variety of other methods. Now, a joint coupling π (Ir, y) of p. Päma is a joint distribution over V x y with marginals p. Pana, which induces transport и (arly) from Paran p. Here, the key assumption computing p(x|e), p(x|c, c, yo), p(z|c, Dn-1) is parallel is not much slower than computing p(æ[cc alone. This is generally true long as n too large. The procedure is:
make is slightly stronger: that
1. Given context c, sample (Jo...-, 1n-1) Paran from the draft scheme.
2. Compute target probabilities p(r]c), p(a|c, (o), ..p))...,p(((..... p(z/e, Bw-1) in parallel.
3. Sample xp ~ (<rlyo, 1n- for some valid transport ग, and append to the context c.
4. If xo E .vo...., In- }. sample token from p(yl c, z0) and append it to the context c.
Similar the single-draft case, we now get nearly 2x speedup whenever 2i E (Vo. 1n-11 Thus, we want to maximize the probability that zo lies among the n sampled draft tokens, which is the multi-draft acceptance rate. Combined with the conditions necessary for be valid joint coupling, this leads to the OTLP formulation.
B EQUIVALENCE OF CANONICAL DECOMPOSITION AND RELAXED LP
We first state canonical decomposition. Note that the 3-optimization problem below is exponentially large and is not an LP, so is infeasible solve without truncating V. as Khisti et al. (2025) do.
Theorem B.1. (Khisti et al., 2025) Define variables (illi) for E V*, i V. set to zero for & set(i). Then the 3 which solves the following gives the optimal importance sampling parameters:
max 82
min
p()).
Σ VEVi
2
s.t.
3(1 =1 vi Vmh
(19)
TEV
SVV
14

---

Published as a conference paper at ICLR 2026
In fact, the objective value achieved by this optimal 3 is the optimal acceptance rate a* Now, we prove Theorem 4.1, by showing that our defined 1, satisfy the constraints above.
Proof. We first show these satisfy the constraints Theorem B. Indeed, these are all nonnegative. Also, by the relaxed LP constraints, we have S incidence set A, and considering the first and second cases in the definition, have ((1 0 if i set Furthermore, for all E V", we see that
for all i & A,. Thus, by definition of the
Σ B(1D) = Σ kEV
=1
(20)
S iEV
Σ
jeV
the case that é & D. We also see that
Σ 3(1
set(
Σ 0=1 0 igset(F)
(21)
(E)et())
if E D. Thus, all constraints are satisfied.
Now, we show that the objective value with these in Theorem B.1 least the optimal objective value with 8 in the relaxed LP. This will complete the proof, as the optimal objective values in Theorem B. and the relaxed LP are both a*. show this, we use the other relaxed LP constraints. By the the second inequality constraint,
Parali (i)
Σ KEVI
((ili) (t) N Σ ((dli)
= ign
S
(22)
E
igD
33
igD
for all E V. Furthermore, for all i E nr, the first inequality constraint in the relaxed LP shows that
min
p()), Σ
1,3
S T
Σ
1,
(23)
igD
Therefore, the objective in Theorem B.1 is at least
ΣΣST S ΣE
S
Σ iEVn iEV
Σ
=aa=a
(24)
REV IED
EE
This completes the proof that our defined /3 are optimal.
C COMPUTING H FOR INDEPENDENT DRAFTS IS SUBMODULAR MINIMIZATION
Here, we show that the subset selection problem a* 1+ mingcy (HH) an instance of submod- ular minimization when Paran is formed by independently sampling from .1...., to get n tokens. This generalizes the work of Hu al. (2025), who proved this the case 91 =.... qa-
Theorem C.I. When Panoft independently samples from qı,.. Ins the set function up in submodular.
Proof. First, define (HH) P(H) Q(H), where
P(H)
EE<2 p()). Q(H)
Σ
Paran (
(25)
iEH
TEH"
Then, because Paran (i1,...,ún)) (i1) qu (in). we have
22 II
Q(H)= Σ (9))
Σ
(26)
E
NiEH
15

---

Published as a conference paper at ICLR 2026
Note that P(H1 n H2) P(H, U P(H)) + function. Thus, to show & = P - Q is submodular, it suffices to show that Q is supermodular.
P(H2)
for any H1. H2 C V, so P is modular
To this end, take any H1, H2 V. We want to show Q(Hn QQ(H
+
For each j = ,....,,, n,, denote aj = EiEH, 9j(1). by Eien, q;(1), and ej = EieHinHt 95(t).
Then, we see aj + bj Cj = LH (z(1), and aj bj 2 Cj 2 0 by nonnegativity of qj. The condition want show is equivalent to
- cj) -
II
1I j=1
9
11 1=1
bj. j=1
(27)
==1
Now, define the sums B and C as
B =
Σ
II jEA
( -g) II KE(R)AA
bj
(28)
AA
C=
Σ
II (aa
II C3
(29)
AC
We can see B 2 C by comparing corresponding terms in the sum, since each by 2 cj 2 and each aj -- Cy 2 0. Furthermore, we have the following identities by straightforward expansion of products of terms of the form aj - Cj + *:
(aj - 9j +b,)
by B, j=1
(30)
n
YI
II a - 9j +c)
II
Cj
C.
(31)
j=1
j=1
Subtracting these and using B 2 C gives
n
n
n1
(I + ba
I1 2
0 a
11
(32)
j=1
j=1
j=1
j=1
as desired, which completes the proof.
D COMPUTING H FOR n = INDEPENDENT DRAFTS IS SUBMODULAR QPBO
Here, we describe the reduction of H' computation to submodular quadratic psuedo-boolens opti- mization (QPBO) when Parat samples independently from n draft models Q1 92. By writing vb (H) in the same form as in Appendix C, but now for the case n = 2, we see
(H = -ErO) p(1)
Σ (0)
Σ (1)
(33)
iEH
VEH
VEE
Denote the indicator vector æ with 23 = 1/1 E H] for each E V. Then this becomes
p(x)= Σ p(i)
ΣΣ ai (1920))a
(34)
iEViEV
Minimizing (H) over all И C thus equivalent to minimizing p(x) over all binary vectors E 1 This is precisely the form of QPBO, and we already know yb is submodular from Appendix C, so it is indeed an instance of submodular QPBO.
Our submodular QPBO instance is dense, with n V variables and m ((V2) pairwise terms. By previous work, this reduces to a single s t min-cut computation (Kolmogorov Zabih, 2004). Using a max-flow algorithm, the theoretical runtime is O(m)/)) = O(V2.5). In fact, practical implementations like the push-relabel algorithm can achieve quadrataiiicc runtime (Boykov & Kolmogorov, 2004). This is far better than the general submodular minimization algorithm (Orlin, 2009), which takes 8 + V8) = O(V8) time, where = O(V) is the time complexity of evaluating v..
16

---

Published as a conference paper at ICLR 2026
E COMPLEMENTARY SLACKNESS DERIVATION
We first review the details of dualization and simplification to subset selection, starting from the relaxed OTLP (Equation (2)). These details are necessary to formulate complementary slackness.
Proof. Dualizing the relaxed OTLP gives the dual LP. The zero equality constraints correspond to eliminating entries of æ, and can be ignored. So, to transform to the dual, one introduces a variable for each inequality constraint, say yı for constraints over E V, and for constraints over i v":
min M
Σ MP((t)+ iEV
Σ TEV"
Z.Paran (i)
y1 ++ VEEV s.t.
(35)
Finally, to reduce the dual LP, Hu et al. (2025) observe that the inequality constraints form a TUM matrix. Any LP with integral inequality bounds and such constraints has integral optimal solution (Hoffman & Kruskal, 2009). Also, any y; 2 2 or 2 2 2 can be reduced to while upholding each constraint Y; 27 2 1 and not increasing the objective value: this means that some optimal solution is binary. Then, denoting H = {i E V y; 1}. one can compute optimal y, z given fixed H as:
1 i H, 0 H H
+ == f
H H
(36)
Putting this back into the dual LP and simplifying gives the subset selection formulation.
Now, we provide a proof of Theorem 5.1, which makes use of the idea of complementary slackness. Primal and dual LPs have the same optimal objective value, and complementary slackness allows one to get from any optimal solution of the dual to some optimal solution of the primal. This asserts that the following two conditions are equivalent for any pair of feasible solutions (ax", (3r) to the primal and dual LPs: (A) a² is optimal in the primal I.P and 3 is optimal in the dual LP, and (B) each variable in ; 3 is zero, or its corresponding inequality constraint in the other LP is an equality.
In our case, considering the primal and dual LPs as the relaxed OTLP and its dual, we already have the optimal solution 3* to the dual from Equation (36) and the H computation. Thus, computing an optimal primal solution a is equivalent to jointly solving the complementary slackness constraints in (B) alongside the feasibility constraints for a in the primal LP.
Proof. For the relaxed OTLP and its dual LP, complementary slackness constraints become:
vt 0
Σ S =
Vi V.
(37a)
TEVe
24 = 0 or Σ S =
Paran (i)
Vi V"
(37b)
iEV
8 0 or
V1 + + =1
Vi VEVE V".
(37c)
Given the optimal solution y", z" to the dual LP, we only need to solve this system, alongside the original constraints in the primal (relaxed) LP, to obtain the optimal solution S* to the primal LP. This can be done by using the binary vector expressions for y" 2² in terms of H* in Equation (36). First, for Equation (37a), observe that y * 0 if and only if E H Thus, it is equivalent to
Σ $ Viei H TEVa
(38)
Next, for Equation (37b), recall that 27 + 0 if and only i & (H+)". So, this condition becomes
Σ S = Paraft i)
Vi E (
(39)
17

---

Published as a conference paper at ICLR 2026
Finally, by observing the four joint cases for y 2f, have
i He
vi +
(40)
i (H)), 0 i H H'
so that Equation (37c) is equivalent to
S 0 vie H (
(41)
S = v H , (H*)".
The second of these can be eliminated, as it is redundant with the zero equality constraint in the relaxed OTLP: if i H* and E (II*),, then i cannot lie in the incidence set A,, St already,
Finally, combining three new conditions with the feasibility constraints in the relaxed OTLP, any solution to the following system is an optimal solution S in the relaxed OTLP, and vice versa:
Σ PEVn
S/ S p(i)
VIEV,
Σ iEV
S S Paran (1) Vi E V"
Σ S p(i)
ViEH',
Σ
S Pdran i NEV
vi (H")"
(42)
ievn
', - NEV A.
- ViE (H"))
Finally, note that some inequality constraints are redundant. We no longer require the p(1) inequalities for E H" and we no longer require the (i) inequalities for i (H*)". This directly reduces the above system, which is equivalent to the relaxed OTLP, to the desired system.
F MAX-FIOW TRANSFORMATION DERIVATION
Although it is a standard network reduction technique to reduce row and column sum constraints to nlx-flow over bipartite network, we provide proof of Lemma F.1 here for completeness.
Lemma F. (Bipartite-Flon Flow Equivalence). Let = (AU B. E C A x B) be a bipartite graph, with (-)) denoting neighborhoods. Let æ RA, y R , E R be nonnegative. Define a network Ω on nodes {s, U U B, with capacity Ia edges - a for a E A, capacity edges b - t t.for b E B, and co-capacity edges bbr (a, E E. Then these
conditions are equivalent:
(1) EbEN(A) Z(a.b) = Ia for all a E A and Emen(()) a I for all E B,
(2) f(s - a) = Fa. f(a b) 2(a,)), f(b 1) EmEN(s) ((a is a maximal flow in Q.
Proof. Suppose condition (1) holds. Then the flow assignment f in the second condition satisfies f(s + a) Ia
Σ
2(a,b)
Σ
((a+b),
(43)
BEN(a)
bEN(a)
f(b (tb+t)=
Σ ((a,b) = Σ f(a + b).
(44)
aEN(b)
aEN(b)
This means flow conservation holds. Also, f(s + a) < xa for each a E A, and f(b < yo for each e B from the inequality constraints, so the capacity constraints hold. Thus, the assignment ff is feasible. In fact, its value is E.cA f(s a) = EnEA Za, and no flow assignment in Ω can exceed this value since the total flow along edges s - a cannot exceed the sum of the capacities Ta- This shows the f is indeed the maximal flow, so condition (2) is satisfied, as desired.
Conversely, suppose condition (2) holds. Then flow conservation at each E shows
Ha [(s + a)
Σ BEN(a)
Σ [(a.b)-
(45)
NEN
Also, the capacity b + shows s(s b) b) EeEN(s) 2(a,b) S ybb Thus, condition (1) holds.
n
18

---

Published as a conference paper at ICLR 2026
G PROOFS OF RESIDUAL LPS
In this appendix, prove the reduction the outer residual LP. We will use the following lemma. Note that each Za and y/ must be nonnegative, as per the requirements of Lemma F.I.
Lemma G.I. From Lemma F.I, consider condition (1) as a system in nonnegative variables be with Ta eququiitty constraints and Wi-inequality constraints. This is feasible if and only if
Σ
Σ yb AS BEN(S)
(46)
OES
When yo constraints are equalities, feasibility is equivalent to the above and Eac to = =YEEB yb.
Proof. The first part follows from the equivalence of conditions (1) and (2) in Lemma F.1, and Gale's feasibility theorem for bipartite supply-demane networks applied to condition (2) (Gale, 1957). The second part holds as LaeA La = LbEB combines with condition (1),
Σ Fa - (()
Σ Ea
((a.b)
Σ Σ
((a.b)
Σ yb- beB
(47)
OE (a)
bEB aE
force the equalities
Σ ELEN(H) F(a.b) = yb for b B, as required.
Now, prove the reduced LP for outer system residuals (i) in Theorem 6.1.
Proof. To solve for the residuals in the outer system, we need to find 0 S p: p(i) where
Σ S WEV H'
Σ S/ Paran (i) "EV
Vi E V" (H*)", (48)
(H"")
feasible for nonnegative S*. When this system is feasible, its solution S will also be a solution to the outer system, nonnegative, we can use Lemma G.I, to show that the above system is feasible and only if:
simply recover the residuals as p**(i) p(i) pt- Since all ps
Σ P H
Σ (E
Paran (i),
Σn P iES
Σ (EN(S)
Paran
VS
(49)
where N(S) C V" \ (H** denotes the neighborhood of S C V\ H' in the bipartite graph with left vertices V H* right vertices V" \ (H**"" and edges (i, î) with i set(i). Note N(S) contains precisely the n-tuples in y with at least one element in S. Therefore, we can write
Σ TEN(S)
Parnft (i)
Σx( =
Σr(1 p(1)
Σ 7E(V(S)"
Paratt (1) = (VV \\ ().
(50)
iE
Substituting this back and simplifying with v., our condition becomes:
Σpe = Σ p(i) (HH") Σnl S Σ p(i) -
AA VS (VVSS) H*
(51)
*EVIH"
ES
FS
Including the original constraints 0 < p, S p(i) completes the proof.
H GREEDY POLYMATROID ALGORITHM FOR OUTER RESIDUAL LP
Here, prove Theorem 6.2 by using polymatroids. Polymatroids are subsets of Euclidean spaces associated with submodular functions: they defined as the feasibility set of subset sum inequality constraints with bounds being evaluations of the submodular function. Thus, they directly related to the outer residual LP. In our proof, we refer only to standard polymatroid theory from Chapter 44 in Schrijver al. (2003).
19

---

Published as a conference paper at ICLR 2026
Proof. Because (S) is submodular in S, and
Eses p(1) is modular (additive) in S, then
((5) = Σ p()) + (VV (1\)= =1
Σ
Paraft (1)
(52)
iES
iE(V)S)"
submodular in S. Therefore, solving Theorem 6.1 amounts to finding æ EE& n Bp with and 1 Φ(V H where By is the feasibility set of all constraints p; S p(i), and EPs is the extended polymatroid associated with the submodular function Φ:
EP = a Σ 3. S (SS) iE
AS
(53)
By Equations 44.8 and 44.9 in Schrijver et al. (2003), the box-pot pox-polymatroid intersection EPs O Bp is also an extended polymatroid EP's associated with the following submodular function ølp:
())
min TCS
Σ p(i) (1))+00 (())) iESYT
p(i) + min (TT). Ep(i) EE
(54)
VISET
Since our system feasible, and has the inequality constraint 1. x S 6(V Ht) and equality constraint 1 <(V), \ H)),, we can replace the equality constraint with an objective max 1 This turns Theorem 6.1 into the following extended polymatroid optimization problem:
max 1 x s.t E EEPpps
z 0.
(55)
We first ignore the nonnegativity constraint. To solve this simplified version, we can use the two-step greedy algorithm from Theorem 44.3 in Schrijver et al. (2003). First, we reorder V \ H² in increasing order of the weights 1. This can be arbitrary, Then, we compute consecutive differences z., = (ølp) (S: where S { 0 the ith prefix of \ H We can compute this explicitly as
we specify it as the given ordering {UI,..., U
Σ p(t) + min
(TT) - Σ p(i) min (5())
(56)
VSSETT
ST
IES.
iES.11
-(())
min (T")
min
(TT)
(57)
H H- (P)
H H
(
min H.IST
(TT)
min H.ST
(T).
(58)
This matches the desired expression, so to complete the proof, it suffices to show æ 2 0, i.c. each Te; 2 0. Indeed, suppose 7" 2 Hit1 minimizes the first of the two min terms above. Since H, H4+1 (vc). we will have T U (ex) 2 H,, and thus
min (TT) $ (T U (vi)) H.ST
(59)
Σ p(x)
Σ
Päran
(60)
=E(TTU(F:)
"E(T-U((.))"
S <p(v:) Σ p(z) -E Paran (i)
(61)
zET"
iE(T-)m
p(v:)) (TT)) = p(v:) + min (T).
(62)
H
Rearranging this exactly gives Fe, 2 0, as required.
I GLOBAL OUTER SOLUTION
Here, we prove Theorem 6.4. We will use the following lemma, which relates the minimization of feasibility of transport system to the nonnegativity of an associated convex function.
20

---

Published as a conference paper at ICLR 2026
Lemma 1.1 (Convex Transport Solver 1). Let G (AUB.E A B) be bipartite graph without isolated points (each neighborhood nonempty). Suppose the following system is feasible in nonnegative variables f (a,b) E:
Σ NEN())
Sab Ha E A,
Σ
Sab
yh
Ab B.
(63)
@EN(h)
Then the following function &b : R + IR is convex and nonnegative:
((((a)DEA) =
Σ
Ub log
Σ en
Σ
Ialla-
(64)
BEB
(EN(
aEA
Furthermore, for any é >> 0, there exists (Oa)aE with [ S..
Proof. We will use the Hall-type conditions from Lemma G.I. By feasibility of the system,
Σ
16
Σ RES
Ta
A,
Σ BEB
Σ
Ta.
(65)
NEN(S)
aEA
Now, it is clear that is convex in since is linear combination of terms convex in a (LogSumExp and linear). To show it is nonnegative at a particular point a, relabel A = (1,2..... m) such that an 2 ... 2 am. For each b E B, we have the lower bound
log Σ n
2 max Oa. (EN(D)
(66)
(E)
Now, let N& N((I,...,,A)) \ for each b Nk. because & (b) and 1.....k 1 N(b). Furthermore, the sets N1.... Nn are disjoint, with union N((1...., m)]) B. Using this, we can lower bound
13) for each A. We have maX On = ON
Φ((aa)aE)) 2
Σ BEB
max da (EN(b)
Σ aaa
(67)
REA
ybak
Taaaa
(68)
k= BE
a=1
yb
Fo
Og-
(69)
Denote the coefficient of a, by ca. For any
S. k S m, we see by applying the Hall conditions that
Ca
Σ
Yb
Fa
(70)
UE..U...UN
a=1
Σ
yb
Σ
Fz 2
(71)
DEN(HI..... k))
GE
(E(....,kk
with equality at h: = m. Thus, each Or a1+1, we have the desired nonnegativity:
m
m
(((aa)oEA) >
Σ
Co Σ
cala amm)
(72)
Ca (a(aa-1 a3))
(73)
a=1 f=0+1
m-1 1
Ca (a. - as+1)
(74)
a=1
m-1
= Σ
Ca
(aj -aj+1) 2 0.
(75)
==1
n=1
21

---

Published as a conference paper at ICLR 2026
Because & is convex and bounded below, by the Brondsted-Rockafduee Rockafellar approximation theorem (Brøndsted & Rockafellar, 1965), there are points on with arbitrarily small subgradients. As 4 is continuously differentiable, then for each >> 0, some (aa)ae satisfies [ S.
For the outer system, we can apply Lemma 1.1 with bipartite components A = V H" and 7m (H*)", edges (a. b) E E and only if E set(b), and bounds Za Pa for all A and = (b) for all b E B. (Here, Pa are the outer residual LP variables we solved for in Theorem 1. given by Pa p(a) - (a)) The key idea that the gradient norm bound from the lemma bounds the total deviation from p(i) equality constraints in the outer system, which allows us to prove Theorem 6.4.
Proof. We first show that || S + er feasible. Define $ RR
-
R as Lemma L.::
((ai)eer)))) =
Σ
Päraf (i) log
Σ
eat
Σ
p:a.
(76)
TEV")(H-)
(ESCU())) A
iEV\
By the lemma, there is some (ot)ev with [V
|| c.
Thus,
OP(a))
(a(aa))
Σ
Σ
Se.
(77)
Oox
iET
VEV..*
We can also compute the absolute difference in the ith partial derivatives of 4 dr for any E 7 as
@vr(at)
@{(aa)
e 1 set(i) H*] ΣxEsett) e²i
E
Pdraft (
(78)
Da:
Da;
(EV"((H"
Thus, summing the above over all E T gives
@Tr(a))
@T(a?)
Σ
c 1 set(i) \ H*) Σ
Paran
(79)
do:
da:
Ejene e²i
IET
NEV"
iET
Σ
Paratt (1) =1--1
((1)
cr.
(80)
"EV"A(H"UT)"
VIEN-UT
Because T is constant over o; for i & T, and thus has zero partial derivative at these variables, the Triangle Inequality implies that ||V falls below c + cT at (av)),
(a(a)))
@Pr(a))
o0(a;) < e ET.
[V )l1 <
+ Σ
(81)
da:
da;
IET
TE
Now, we prove the second part of the theorem for arbitrary (au)iev,N>. First, we bound the sum of the partial derivatives of over E V (H* UT):
Σ
OΦ Das
Σ
Σ
e. Pdraft (i) ps
(82)
Ejenr eaj
UT)
(EV)(H-UT)
"E \/ iEset(T))HH
Σ
Σ
e Ejeset eo
Pdraft (i) + Pi
(83)
(EV)(H
TEv"\(H J2)" iT)a
Σ
Paraft (
Σ P.
(84)
(HrU)T
(ETT(
2
Σ
Paran 1i)
2
(85)
22

---

) Published as a conference paper at ICLR 2026
where the last inequality holds by Equation (49). Therefore, we have by the Triangle Inequality and Equation (80) (holds for any point) that
(((()))en
Σ RET
(86)
doa
doc
EE(V)B))
(pp((a))
ab(aa)
V ((a))ee)i 1l1
2eT
(87)
da;
da;
| ((os)eee H-
3er.
(88)
Finally, using the explicit representation for partial derivatives of and substituting in S from Equation (14), get
Σ
Σ
c,
Pdranl (i) Pi
Σ
Σ
S
(89)
E)Ema()) H 6a (()
iEVi.
(H"")
VE
iE
(Exe(())
(Vr((as))e + 3ET,
(90)
hence 51, satisfy the equality constraints of the outer system with up to / ((s))e))) 3er total leeway. They also satisfy the Paran( (i) equality constraints exactly, as
Σ
S
E
Σjenatiy -1- ca Páraft () Pdraft (7).
e
(91)
This completes the proof.
J GLOBAL INNER SOLUTION
Now, we prove Theorem 6.5. We will use the lemma below, which is quite similar to Lemma I.I in Appendix I, except that it contains an extra slack term in the LogSumExp to deal with a bipartite transport system with equalities
side and inequalities the other side.
Lemma J.1 (Convex Transport Solver 2). Let G = (AU L,UBE Ax B) be bipartite graph without isolated points (each neighborhood nonempty). Suppose the following system feusible in nonnegative variables Sa, for (a, b) E:
Σ (EN(o)
Sab= = Da
Va
Σ
Sab
Sab
bb B.
(92)
oEN(b)
Then the following function + FRI - Re is convex and nonnegative:
(((a))EE))
Σ log
1+
Σ
aa
Σ
Talaa-
(93)
bEB
aEN(b)
aEA
Furthermore, for any >> O, there exists (aa)aEA with ([ S..
Proof. We add a vertex an to A C G. with edges from ag to all b E B, to form the graph G' = (AU (ao) U E'). Now, let S.,b for (a,b) E satisfy the given system. We define Sy, for (a,b) E'. such that Sy,, Sa. for a # ao and St yb E.ENO) Sa. 2 Also, define x' for all AU {ao} such that s' = va a & ag and x', = E yh - E.EA Ea 2 0, and define va for all b E such that 1/ = yb- Then we see the following, where N'() now denotes G" ni-eeighbbrhoods:
Σ (eo)
Sayb= =
Σ BEB
yb Σ
Sab
=
Σ 9b E be B
Σ
Sab = 2ne
(94)
@EN(
at A DEN((a)
23

---

Published as a conference paper at ICLR 2026
and for each b B, have
Σ
Sab=
Σ
Sa.b + Sag. ybb yb-
(95)
(B)
(EN
This shows the following system feasible:
Σ
Sab= - d'
Va E
Σ OEN'())
Sa, - v/
vb E B.
(96)
(EN
Hence, apply Lemma 1.1 to show that
+ ((0a)oEAUta))) = Σ BEB
36 log
Σ (EN'(b)
Σ aEAu(ao)
Laaa
(97)
convex and nonnegative. Restricting this the slice aaa 0 gives (((a))oEA) defined in the theorem, each Nb) contains dg, corresponding to the +1 term in log, and the Faa Qn contribution cancels. Thus, θ is also convex and nonnegative. The existence of arbitrarily small gradient norms then follows from the same argument as in the proof of Lemma I.1.
For the inner system, we can apply Lemma J.1 with bipartite components A = H* and B = )H*)", edges (a, b) E if and only if set(b), and bounds xa p(a) for all and yb = Paran (b) for all b E B. Once more, the gradient norm bound from the lemma bounds the total deviation from p(i) equality constraints the inner system, proving Theorem 6.5.
Proof. We first show that 1/ v 6 + "T is feasible. Define θ R. - as in Lemma J.1:
e((o))ee--)
Σ
(iran()) log 1+ Σ cai
p(i)az.
(98)
x)
tEset(s)
By the lemma, there some (at) with || )ll S Thus,
(0(a))
(0(a)))
Σ
S.
(99)
do:
RET
iE
We can also compute the absolute difference in the ith partial derivatives of θ Or for any i E T as
(00r(a))
o0(a))
e 1[i E set(i))
Σ
+ EsEme( ea Paran (7).
(100)
da:
da;
(E("T))AT
Thus, summing the above over all E T gives
00r(a?)
a0(at)
Σ eat 1li set(i))
Σ
1 1 Ejeso( e² PPraaf (7).
(101)
da:
Oa;
ET
"E(H")"\'"" ieT
Puran ( =
Σ E(( g(i) ViEH
Σ (0)) LET
(102)
(E(
Because Or is constant over a, for i & T. and thus has zero partial derivative at these variables, the Triangle Inequality implies that || | falls below + pr at (a Ne)=:
(a(a))
(00 00(a;)
IVer((a))een )l1 <
+
S sc+rr.
(103)
da;
Oas
da:
IE
iE
24

---

Published as a conference paper at ICLR 2026
Now, prove the second part of the theorem for arbitrary (os)iE First, we bound the sum of the partial derivatives & over E H T::
d0 dai
c
Σ
Σ iE(H")"
Ejese( en Pdran (i) p(i)
(104)
I+
(T
iEH'AT
iEsot(i)
6
Σ
Σ
1+ Ejeso(() e% Puran (8) p())
(105)
iE
iE(MIY" (Eset(1)
Paran (i) +
Σ p(i)
(106)
iE(H)) 1m
iEH'AT
< 2
Σ
Paran ( 27r,,
(107)
(E("T""
where the last incquality using the fact that is minimized at H
0 (TT) (11'))
(108)
Σp(i)
p())
Σ
Paran (2) - Σ p(i) +
Σ
Paran
(i)
(109)
IET
TET
iEH!"
iE(H²)"
Σ
Párafi
Σ
p(i)
Σ
p(i).
(110)
3E(H")"TT"
iEH*
iEH-AT
Therefore, we have by the Triangle Inequality and Equation (102) (holds for any point) that [[V((()))E==)l)
d0
)|11
Σ
+
Σ
(111)
dos
day
iET
iEH'
00
00(a;)
)l1
+
+ 2
(112)
da,
da,
GE
[ ||l + 3
(113)
Finally, using the explicit representation for partial derivatives of θ, and substituting in S from Equation (17), we get
Σ
Σ kE(Hry"
Ejesent) ea, Paran (7) p(i)
ea:
=
Σ
Σ
S
-(i)
(114)
iEH-
iEH*
(E(
iEsei())
sEseUT)
<
[|V )ll + 3rT,
(115)
hence S1,3 satisfy the pe equality constraints of the inner system with up (10r((()))em))]11+ +3m total leeway. They also satisfy the Paran (+) inequality constraints, as
ea
S (
Σ
Σ
1+ Exemnoo ea Pdrati ( S Pérafi (
(116)
(Ese(()
This completes the proof.
K TRUNCATED SOLVER DETAILS
In this section, we discuss the specific implementation details for convex minimization our inner and outer solvers, including under what conditions solver fails.
25

---

Published as a conference paper at ICLR 2026
The first step is group coefficients of the same LogSumExp terms, obtain more compact representation of Dr and 9r. For Dr in the outer system, the coefficient a term containing ai (none of i .......4 i lie in H*) is explicitly
precisely "i....,,
E (E(H"UTY" ((rT)) H (h
Pdrafi (
Σ
(-1)"-1A1
E sE(H"UA)"
Pdraft (
(117)
Ac(
Σ
(-1)*-141
Σ VEEAA
g(i)
(118)
AC(t.....te)
The second expression is consequence of the principle of inclusion and exclusion (PIE). The last expression can be computed efficiently using dynamic programming. Similarly, for Or in the inner system, the coefficient of term containing precisely Oçi 0ig is
Pdraft (
Σ
(-1)a-14)
Σ Páraft
(119)
PET" (11...)))
A AC
#EA"
E
(-1)k-1A)
Σ 9(1)
(120)
ACto....da
uEA
Again, this formula can be derived with PIE, and can be computed efficiently with dynamic program- ming. Once have grouped coefficients, both 4 Or have at most
|T| n!!
Σ
(121)
terms. With this compact representation, one can quickly compute the gradients of Φ and Or. We manually implement a function that returns the value of each of these functions and the corresponding gradient at an input point. Then, we use the the standard L-BFGS-B minimizer from SciPy (Virtanen al., 2020) to run gradient descent, to converge to point with near-zero gradient norm. This an ideal al algorithm for gradient descent because it converges quite fast for convex functions in few variables, and we require execution on the order of milliscconds. The SciPy API also returns the final gradient norm value, and allows early termination when the gradient norm falls below threshold. To ensure our approach remains on the order of milliseconds, we limit L-BFGS-B B to 25 iterations.
Finally, discuss the issue of early termination, i.e. solve failure. There consider: (a) T is too large, (b) the gradient norm does not fall below the desired threshold. For (a). we have set the following hard limits [T] through experimentation: 50 for
situations to
20 for = 3, 10 for n = 4, and 10 for n 5. Note that these numbers are quite conservative: future work could aim improve runtime and reduce early terminations by using non-fixed threshold, or an alternative gradient descent method that works better for larger I.. For (b), because the SciPy API terminates when the threshold is reached, this can only occur if the maximum iterations are reached, and the gradient norm is too large. In practice, we find this is rarely the case: [T| being too large is usually the reason for failure.
L APPROXIMATION GUARANTEES
Here, we prove Lemma 6.6, which translates the inner and outer solver deviations into concrete bounds on deviations in the approximate OTLP solution.
Proof. Define the row-wise sums 2/. - EiESo( Sr, Also, denote the residuals r(7) Paratt (i) Eienati S.z- From Theorem 6.5 and Theorem 6.4, we know that Σieh- lpl - p(i) < and
Eier 1i, pil S We first show that the Paran equalities in the OTLP hold. For ñ (H*)*.
26

---

Published as a conference paper at ICLR 2026
we have
p(i) - Pi Ejerr (p(i) pÿ)
ΣOu=
Σ (E)ot(?)
S +
E
(())
(122)
AVV
*EVIH
Σ iE
S + r(i)
Paraft (i).
(123)
Also, for i & (H*)", using the equality guarantee of the outer solver,
EG.= Σ
S = Pdrat (7).
(124)
iEV
=Esei())
Now, we bound the deviation from the p(i) equality constraints in the OTLP. We have for all E H
that
EG==
Σ
S P/:
(125)
iE
and we have for all E H that
p(i) - Pi
ΣG1= Σ
S + Σ
EjerY (p(i)-pj) (1)
(126)
iEVn
SEV* (H,
iE(H-)"
vl p(i) -Pi
Σ
Pdraft (7)
Σ S3
(127)
jEVEH (p(i) - Pi)
iE(H">"
(ESO((T)
p(1) Pi
r/ WjEViH (p(i) p.)
Σ
Puran 7
Σ D//
(128)
(E(NT)"
JEH-
= r/ p(1) Pt
Σ (p(s)-pa) - 11/) - -(((H))
(129)
(H-
IEH'
= p(1) + (p) p.) + p(i) Pi
Σ (p(i) p/).
(130)
(HH
jEH
In the fourth equality, we used the equality condition of Theorem 6.1, and the definition of sb. Since 2 ) < 0 and ps S p()). this allows us to bound the difference to p(i) for i & H as
C,, NEV* Hence, summing over all i gives
CC, - p(i) S lp4- - pil+ pii) (H))
Pi
Σ JEH
1//
p()1 S lo pal + p(i) Pb (HHH)
B. (131)
p(i) Pi
Σ Σ C53 CC p(i) SEV TEVa
S Σ 114 p(i)+
Σ 144 p.l+ Σ 1E -W(H+)
(132)
iEH-
1EV
8 + + 3 a 23.
(133)
In fact, each C,27 is nonnegative as all S, nonnegative, and each r 2 0 (by the incquality
constraint of the inner system, which is exactly satisfied even for the truncated solver) and p(i) 2 p:. Therefore, C,7 represents a solution to the OTLP with total deviation at most a + 2/3 from the p(i) cquality constraints. Finally, the acceptance, i.c. the objective value in the OTLP, is
Σ Σ
C = Σ
S
Σ P/:
(134)
TEV" (E
TEVn (E
REV
By the Triangle Inequality, the fact that
2 Σ
- (p--p(1)) = + (H") a*
(135)
SEH*
1EV'H-
*EV'H-
is the optimal objective in the OTLP, and the fact that E- vol-p(i)) ~ 3 and Eiev Ip(-pal I o, this new objective value deviates by most from the optimal acceptance, desired. n
27

---

Published as a conference paper at ICLR 2026
M EXPERIMENTAL SETUP
We run all experiments on Paperspace machines. For Llama-3 70/8B, we use a setup with 4xA6000 and Intel Xcon Gold 5315Y CPU (32 cores, 3.20 GHz). For Gemma-2 27/2B, we use setup with an A A100-80GB and an Intel Xeon Gold 6342 CPU (12 cores, 2.80 GHz). We use temperature sampling from the target and draft models all settings.
Our data consists of 500 random eval prompts from GSM8K, HumanEval (only 164 total), IfEval, PopQA, and WildJailbreak, five diverse benchmarks spanning math reasoning, coding, instruction following, knowledge retrieval, and safety (Chen et al., 2021; Zhou et al., 2023a; Cobbe et al., 2021; Shen al., 2024; Mallen et al., 2022). We take prompts only from the eval split to avoid test set contamination. For acceptance experiments, we compute token- avee-aaeeegee acceptances per dataset, and perform a simple average across datasets. For solve time experiments, as times are fairly prompt-agnostic, we select 40 random prompts from each dataset.
For our solve time experiments, we use the HiGHS LP solver (Huangfu & Hall, 2018) SciPy's optimization module (Virtanen al., 2020). We also graph-tools (Peixoto, 2014), heavily optimized Python network analysis package with a C++ backend and OpenMP support, to solve max-flow. To solve the convex minimization problem, (Virtanen et al., 2020). All solvers are only run on the CPU with numpy arrays, to minimize the impact of GPU setup differences on solve times.
use the L-BFGS-B solver from SciPy
N T SAMPLING FOR THE RELAXED OTLP
Here, we formally describe how top-k sampling of the draft model g impacts the relaxed OTLP when Pdmmi is formed by i.i.d. sampling q. Suppose that the top k tokens of form Vo C V. This means O whenever & Vo- Now, recall the relaxed OTLP is
Páraft
Σ iEV
Σ
s.t.
S S(t SS
ViEV,
SS Spian AEV
Vi e V",
9-0
iev"
(136)
S Vi V
For any E V E Vo the Paran (2) = upper bound constraint and nonnegativity of variables forces
S. = O. Furthermore, for any e Vo, J E Vi, because 7 & A, (it cannot contain as it has all elements in Vo), the zero equality constraint above gives S,, 0. This means the only nonzero variables are those where i E Vo, E Vo. Plugging these into the above, simplifying the objective, and eliminating trivial constraints and variables we know to be zero, we get the following LP:
max 9
S s.t.
Σ Sp() p(1)
Vi Vo.
ΣS SPaaa
Vi E VD
iEVo
iEVE
(137)
= ViE Vo, E Vo, set
This is exactly the same as the original relaxed OTLP was replaced by Vn, and p and Paraft replaced by their slices along Vi and Vy. Thus, top-k sampling essentially reduces the problem to a smaller version of the relaxed OTLP, with kn+1 parameters rather than pn+11
O GREEDY VS. LII.. ACCEPTANCE RATES
In Figure 2 and Figure 3, we compare acceptance rates for the i.i.d. and greedy Parani construction Gemma-2 and Llama-3. We find i.i.d. performs worse than greedy for k 10, but does better for all k 2 100. In particular, it is nearly 2% better for most 2 4 in the latter case. Interestingly, the i.i.d. advantage seems decrease as n increases for higher le in Llama-3, but not in Gemma-2. Exploring these trends is an interesting avenue for future work.
28

---

Published as a conference paper at ICLR 2026
IID Minus Greedy Optimal Acceptances for Gemma-2 27B/2B
256000
0.015
k (top-k sampling of draft)
100000
0.010
0.005
10000
0.000
1000
0.005
100
0.010
-0.015
10
3
4
5
6
7
8
9
10
(number of draft tokens)
Figure 2: Comparison of i.i.d. versus greedy acceptance rates for Gemma-2 27B/2B across various choices of and top-k sampling of the draft.
IID Minus Greedy Optimal Acceptances for Llama-3 70B/8B
128256
0.015
k (top-k sampling of draft)
100000
0.010
0.005
10000
0.000
1000
0.005
100
0.010
0.015
10
2
4
5
6
7
8
9
10
(number of draft tokens)
Figure 3: Comparison of i.i.d. versus greedy acceptance rates for Llama-3 70B/8B across various choices of and top-k sampling of the draft.
29

---

Published as a conference paper at ICLR 2026
P GEMMA-2 SOLVE TIME COMPARISON
Here, in Table we compare the four methods' solver times for Gemma-2. Again, global resolution can hundreds of thousands times faster than the other methods. We also observe global resolution solve times for Gemma-2 are generally larger than those for Llama-3 (Table 1), but it not clear how much of this is due to environment setup differences (CPU-only).
(k. n)
General LP
Max-Flow
Opt. Max-Flow
G.R. (7 = 9
G.R. (T = 10
(10, 2)
7.85
3.18
3.26
7.46 (98.87%)
10.63 (92.75%)
(10, 3)
59.43
5.05
5.10
24.64 (98.54%)
33.95 (88.06%)
(10, 4)
4000+
95.73
94.21
57.21 (98.31%)
77.42 (86.21%)
(10, 5)
400000+
10000+
10000+
98.10 (97.77%)
130.68 (85,36%)
(100, 2)
4000+
95.13
82,94
49,58 (36.64%)
43.49 (18,58%)
(100, 3)
400000+
200000+
200000+
107.66 107.65 (19.53%)
32.81 (8. 18%)
(1000, 2)
OOM
400000+
400000+
60.05 (27.5%)
141.25 (8.04%)
Table 3: Average Gemma-2 solve times (ms/token) over k, n, for the five i...d OTLP solvers. General LP and max-flow are baselines, and optimized max- flow and global resolution (T = 10 10-+) ours. Lower numbers are better. Red numbers are lower bounds from small scale tests due to excessive runtime. Global resolution can be 10,000+ times faster than others. Global resolution deviates from the target distribution by most 15r in 1.1 distance, and from optimal acceptance by at most 10T. We include success rates for global resolution as it can terminate early sometimes.
Q TEMPERATURE ABLATIONS
In this section, we extend our results to different settings of target model sampling. We use Gemma- 27B/2B with the same aggregate dataset our acceptance rate experiments, and test temperature 0.2, 0.4, 0.6, 0.8 sampling from the target model. We do not change the temperature of the draft distribution, it remains 1.0. Again, test the effects of top-k draft sampling.
Temp=0 Acceptancess
Tump-0
0.85
0.65
010
0.8
0.00
035
Taps
035
of buito
beiae
0.75
0.1
Trancer of triens
Tiramber
1D 6 Optimal Acceptances Gemma-2 278:28
temp-0 Opt Acceptances for Gemma-2 278:28
3.52
3.50
0.55
2.82
2.42
035
035
tapkaarrping soido
0.2
10
10
Figure 4: Optimal acceptance rates from n i.i.d drafts with top-k sampling with with the target/draft pair Gemma-2 27B/2B, for various target temperature settings (0.2, 0.4, 0.6, 0.8). Until temperature 0.8, increasing & past 10 results in little acceptance gains for reasonable values of n.
30

---

Published as a conference paper at ICLR 2026
We begin by plotting the acceptance rates in Figure 4. We observe that for temperatures 0.2, 0.4, the & = 10 setting achieves essentially the highest acceptance rate for values n: increasing does not lead any noticeable acceptance gains. For temperature 0.6, k 10 performs better until around n = 4, but afterwards & 2 100 performs better (although the difference not significant). For temperature 0.8, k 10 is significantly worse than other settings increases, although has comparable acceptances to k 2 1000. These results demonstrate that decreasing the temperature allows top-k sampling achieve extremely high acceptance rates for small values of k, thereby making approaches which staunchly rely on it (e.g. LP and max-flow solvers) feasible and effective.
100
G.R. (taum0 000000 Temperature Dependence for km10
G.R. (tau 0.0000 Temperature Dependence for km100
Sohre Sohre (mnttnec1
200
250
37.5
oate (% tovens
35.0
nete tovems
70
20.0-
50
7.5
2.5
0.2
0.4
0.5
0.6
0.7
0.8
1.0
G.R. (t3u-0.0001) Temperature Dependence for k-1000
G.R. (tou-0.0001) Temperature Dependence for k-10000
700
200
Sahi time (michuke))
100
200
50-
100
100
Fall cate 8% (okens)
60
20-
0.2
0.3
0.4
0.5
0.5
0.7
0.8
0.9
1.0
0.
0.3
0.4
0.5
0.5
0.7
0.8
09
1.0
Temperature
Terperature
Figure 5: Solve times and failure rates of global resolution with == 10-4 (Gemma-2 27B/2B) for choices of E (10, 100, 1000, 10000) and n E (2,3, 4, 5), plotted over increasing temperature.
We also examine the efficacy of global resolution with 10 as temperature varies in Figure 5. For l > 10 (not the top left graphs), failure rates increase significantly with temperature: global resolution is most applicable solve times increase until a certain temperature, and then decrease thereafter. Given the high success rate and low solve times lower temperatures, global resolution shows great promise in this regime.
low temperature settings. Also, for all & and n, global resolution
31

---

solve time Published as a conference paper at ICLR 2026
R MULTI-STEP EXPERIMENTS
Here, we implement global resolution in the framework SpecTr (Sun et al., 2023) to measure end-to- end latency in multi-step speculative decoding systems. SpecTr first drafts K i..dd paths of length autoregressively from the draft model to form a draft tree, and then incrementally uses any OTLP solver (with n being set to the number of child nodes) to advance from the root of the tree to child nodes, until it lands off the tree. We use global resolution for our OTLP solver with k = 100 for top-k draft sampling, and when it fails, we resort to standard sampling from p. We run our experiments on Gemma-27B/2B with temperature 1.0 target sampling the same dataset experiments. Our results for K 2, 3, 4 and L = 8 are shown in Table 4.
K
Block efficiency
Walltime speedup (relative to vanilla)
(tokens/ Mp call)
2.23
1.84
2.54
1.89
2.65
1.98
Table 4:
Block efficiency (number of decoded tokens per call target model) in and walltime speedup (over vanilla autoregressive decoding) for SpecTrr with global resolution under different values of K (number of i.i.d. paths). Experiments are run Gemma-27B/2B with L 8.
Our walltime speedups in the best setting (K 4) are nearly 2x better than vanilla decoding. We also emphasize that these numbers are highly conservative estimates. Unlike previous OTLP solvers used in the SpecTr framework, global resolution is situational: it provably nearly optimal, but cannot always be used. This means the walltime and efficiency numbers above can be improved significantly by using other OTLP solvers like K-SEQ (Sun et al., 2023) or vocabulary truncation (Khisti et al., 2025) when global resolution fails, rather than our simple p-smmpinng heuristic (which valid OTLP solver, but has poor acceptances). Furthermore, by modifying the choice of A in top-k draft sampling, one might be able to use global resolution to get high acceptances in failure scenarios for other We leave such selection of OTLP solvers and their parameters to future work.
We also theoretically examine the properties of error compounding in multi- stepi--teppee setups. We observe that the multi-step error scales approximately linearly with the draft block length L.
Theorem R.1 (Multi-Step Error). Let PL(-) denote the distribution of the next L tokens, under autoregressive decoding from the target model. Let p-.(-) denote the same joint distribution, but now under decoding by global resolution with error tolerance т. Then [pr. pr. S 15LT.
Proof. For each j = ..... L. define PT. to be the distribution of the next L tokens, under autore- gressive sampling from the target model for the first j tokens and then decoding by global resolution with tolerance r thereafter. We use the shorthand notation 01-L to denote sequence of L tokens (o......az) in Vr. with ai denote the slice of the first tokens and a1.u = 0. By applying the Triangle Inequality, it suffices to show for each j O, L that
(
(++1) PL
Σ
(++1) PL
(aI.)) - PL (anL) < 157,
(138)
as then adding up these inequalities gives the desired upper bound of 15r L. To prove this, observe for any a1.1 that
PL
(++1)
(aI.L)
( PL (a1.z)
(139)
L-1
L-1 II p(a, (a1)) II p ((1d)
[ plaa++1aaia lans)
II p(an+1lan)) i=j+1
(140)
i=j
II p(a, (11:))
II ((a+1l(1s))
Maattaan)) - p(ay-1lazg))
(141)
+=/+1
32

---

Published as a conference paper at ICLR 2026
where p(-l-) and p(-1-) are the conditional next-token distributions that induce the joint distributions PL. PL. By the global resolution approximation guarantee on LI target distribution error at the end of that each [|p(-(a=s)) p(((ar::)lI - 15r. Therefore, summing the above bound over all #1:L E V4 gives the desired bound. Below, our sole inequality uses the L. approximation bound, and the third line cancels out the summation of p products a2+2:L to one.
Section 6.3,
Σ PL (a1.)) -PL (01:))
(142)
A1LLEVL
Σ
II i=0
plact1 ((1s) 1=++1
II Martllass) (aas+lanss) - plas+1
(143)
OLLEVE
Σ
πI p((attzlass)) 1==
(blast1lass) -
(144)
Σ
II plantilass)
Σ BiIIEV
((ajtilann) - -pppppaal/pp p(oz+1la1))1)
(145)
a1yEW+1
j-1 p(a 157.
Σ
157
II p(a (01.))
= 15r
Σ
(146)
aLyEWIL i=0
This completes the proof of the multi-step compounding error.
GENERALIZING TO NON-IID DRAFTS
Here, we describe the potential extending global resolution to non-ii.d. drafting frameworks. We consider three regimes: sampling from a single distribution without replacement, sampling n = independent non-identical draft models, and sampling n 2 2 independent non-identical draft models. In Table 5, we examine the step breakdown of global resolution from the beginning of Section 6. For each of the three regimes, we classify its extension to each of the three steps under Yes (extension is immediate), Possible (extension is likely possible but requires additional work), and No (fundamental roadblock prevents the approach from going through).
Drafting
Step 1
Step 2
Step 3
Sampling without replacement
Yes
Yes
Possible
2 independent and distinct
Yes
Possible
Possible
n 2 independent and distinct
No
No
Possible
Table Extending global resolution to three non-i.i.d drafting regimes. Yes means the extension is immediate; Possible means it requires some work; No means there is major obstacle.
We first cover step 1: the computation of H In sampling without replacement, this is straightforward by following the O(V log V + nV) algorithm Theorem 4 and Section 4.2.2 of Hu al. (2025). For n 2 distinct independent drafts, this is now possible following our reduction to QBPO in Appendix D. However, for
distinct independent drafts, this QBPO reduction longer holds. While our work in Appendix C shows this is still an instance of submodular minimization, the most efficient algorithms (Iwata, 2008) would require at least O(V log V) work, which is infeasible for most vocabularies. Approximating H' is possible, but this is totally separate direction of work, and ensuring that these H" approximations give strong bound on the final error may be difficult.
Now, we cover step 2: the calculation of outer residuals p;- The key idea here is that the construction of the outer residual LP (Appendix G) and the greedy polymatroid algorithm to get p. (Appendix O) only rely on the fact that v is submodular, and then we compute min & terms and take consecutive differences to get p.. For sampling without replacement, as in the above paragraph, the algorithm from Hu et al. (2025) facilitates the same approach and even allows the O(V log V) optimization (cumulative minimums) at the end of Section 6.1 to hold. For n = 2 distinct independent drafts, the only roadblock is that computing consecutive differences of min & terms may be costly without
33

---

Published as a conference paper at ICLR 2026
approach like cumulative minimums, some additional work is required on this front. For 2 3 distinct independent drafts, the runtime concerns in the above paragraph again prevent us from even computing single min e term, this again appears intractable roadblock.
Finally, we cover step 3: the convex minimization approach. On their own, nothing from Theorem 6.4 and Theorem 6.5 inherently relies the structure of the drafts, once p: and H are solved for in steps I and 2. The only dependence on drafting comes in computing provable error bounds and selecting the truncation set T. For all three drafting regimes, given that there is a simple form for the sum of Pdmm over Cartesian products of sets (which are used in tunable error bounds), it seems highly likely that this approach could work with some modifications.
To summarize, sampling without replacement seems almost immediately tractable for global reso- lution, and so does 2 independent distinct drafts with some additional work on outer residual computations. However, n 2 3 independent distinct drafts seems intractable due to the higher-degree submodular minimization bottleneck, and would likely require different approach.
We also note that while global resolution requires all three of these steps to go through, our other baseline solvers do not. General LP and max-flow solves require none of these steps, and optimized max-flow only requires step 1 (and none of these assume any information about the structure of paran). Thus, all these drafting regimes, these methods can be used after top-k draft sampling reduces the OTLP size.
34


Reviews:
[{"review_id": "pmLjYEr8nf", "reviewer": "Reviewer_UvVU", "summary": "First, I apologize for the late review; I was invited to join late.\n\nThe paper studies the problem of speculative sampling with a draft sequence length of one (single-step), which can be formulated mathematically as an optimal transport (OT) problem. The paper studies when the optimal transport problem can be efficiently solved (which lets one hence compute the optimal acceptance ratio). In particular cases, the authors derive an efficient algorithm to solve the OT problem. Several experiments demonstrate the empirical efficacy of the proposed method in solving the OT problem vs other approaches, and also demonstrate the effect of changing various parameters on the resulting acceptance rates.", "questions": "Could the authors please clarify weakness 2 above, on the computational efficiency of the proposed algorithm?\n\nIt would be also nice if the authors could add some more references and discussion on why solving the single-step speculative sampling problem is important in practice.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper establishes an algorithm for solving the optimal transport (OT) problem arising from speculative sampling. The algorithm has some compelling theoretical properties and has interesting connections with seemingly unrelated topics like max flow and linear programming. Experimental results comparing the resulting proposed algorithm vs other methods of solving the OT problem are convincing of the algorithm's efficacy in solving the OT problem compared to off-the-shelf solving methods. While I had some issues with the theory (see below), the experimental improvements combined with the proposed theory for solving the OT are convincing.", "weaknesses": "The main weakness of the work is as follows:\n1. It would be interesting to see that the proposed algorithm improves on one way to demonstrate this improvement would be to demonstrate that the proposed algorithm is better empirically. However there is no empirical comparison to Hu et al (2025) or other papers that have studied this problem. \n\n2. The proposed algorithm seems to require enumerating over $(H^{\\star} \\cup T)^n - (H^{\\star})^n$ (see Theorem 6.4) (e.g. to compute gradients of $\\Phi_T$). Yes $T$ can be chosen, but as $|T| \\ge 1$ this still takes time at least $|H^{\\star}|^{n-1} \\cdot |T| \\cdot n \\ge |H^{\\star}|^{n-1}$. As such, how is the proposed algorithms computationally efficient (which is the point of the paper), am I missing something? It would be great if the authors could clarify this point.\n\n3. The writing could be significantly improved. It seems more conventional to present Theorems 6.4 and 6.5 to begin with, describe (at least at a high level) the algorithm, and then argue for its correctness. The current presentation does so backwards. It also took several reads for me to understand some of the key points of the paper, like how $H^{\\star}$ can be obtained efficiently in $O(V \\log V)$ time from Hu et al 2025 so therefore it is reasonable to assume knowledge of $H^{\\star}$, and that the crucial point is to solve the OT rather than compute $\\alpha^{\\star}$. Overall the paper has interesting ideas but it was hard to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e0WAJpTEqq", "reviewer": "Reviewer_ZwDM", "summary": "This paper addresses the inefficiency of *multi-draft speculative decoding* for large language models (LLMs), where computing the optimal transport (OT) verification criterion requires solving an exponentially large linear program (OTLP) over \\(V^n\\) variables. The authors first unify two prior theoretical formulations—importance sampling and subset selection—showing that both are equivalent to a relaxed exponential OTLP. They then reverse-engineer the subset-selection view and reformulate the problem as a max-flow optimization, which, via a novel application of polymatroid theory, is further reduced to a convex minimization problem with at most \\(V\\) variables.  This reduction yields a new algorithm called Global Resolution, which achieves provably optimal acceptance rates in the i.i.d. single-distribution setting where \\(n\\) draft tokens are sampled from the same draft model. Empirically, the paper measures acceptance rates and solver runtimes across different numbers of drafts \\(n\\) and top-\\(k\\) sampling configurations. Results show that the proposed solver can achieve over 90% acceptance with less than 100 ms overhead per token, and negligible deviation from the true target distribution.", "questions": "1. Can you give more details about how you construct the distribution in your experiments, e.g., tempearture. \n2. Can you add some temperature experiments?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical contribution of this paper is substantial. It successfully unifies two previously disjoint theoretical perspectives on speculative decoding—importance sampling and subset selection—into a single coherent framework. Building upon this, the authors further derive a novel convex minimization formulation via polymatroid theory, which drastically reduces the exponential complexity of the original OT linear program to a problem in at most \\(V\\) variables.", "weaknesses": "This paper does not discuss the robustness of the proposed algorithm with respect to temperature. Intuitively, different temperature values shape different draft and target distributions, which could significantly affect the optimal acceptance rate. It remains unclear how the proposed approach performs under varying temperature settings. Moreovere, this paper does not intergrate their algorithm in real-world speculative decoding systems to show how the algorithm/theory can improve the latency of LLM decoding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hM9OTIXLLP", "reviewer": "Reviewer_YzHd", "summary": "This paper addresses the computational intractability of optimal multi-draft speculative sampling. Previous work either computed optimal acceptance analytically (for restricted cases) or estimated it without recovering the optimal transport (OT) itself. The authors prove the equivalence of prior formulations (subset selection and canonical decomposition) and introduce Global Resolution, a convex-optimization-based solver that achieves near-optimal OT in the i.i.d. draft setting. The method reduces an exponentially large LP to a convex problem, with guaranteed deviation and practical runtimes (< 100 ms/token).", "questions": "Do Global Resolution extends (with guarantees) to independent but non‑identical drafts or sampling without replacement drafts?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Important problem. Tackles a key bottleneck in speculative decoding efficiency for LLM inference.\n\nTheoretical soundness. Clear equivalence proofs (Sec. 4), a max‑flow reduction with complementary slackness (Sec. 5), and convex programs for inner/outer systems with explicit error bounds (Theorems 6.4–6.5, Lemma 6.6). \n\nPractical algorithm. Global Resolution achieves < 100 ms/token OT‑solve time while maintaining near‑optimal acceptance. This is a substantial empirical improvement over generic LP/max‑flow baselines in the tested regime.", "weaknesses": "Not a major weakness, but the current method is limited to i.i.d. drafts. In practice, sampling without replacement (i.e., enforcing distinct drafts) typically yields better performance. Extending the approach to that regime, as well as to multi‑step setups, is left for future work. However, overall, the paper already makes great progress.\n\nTypos:\nTheorem 4.6, Equation (17): missing a summation on the LHS.\nEquations (22), (23): the conditional distributions are omitted in the notation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NhgZTELXkE", "reviewer": "Reviewer_TpbB", "summary": "The paper studies multi-draft speculative sampling for autoregressive decoding. It (i) proves that recent importance-sampling and subset-selection formulations are equivalent to an exponentially large relaxed OTLP, which is still intractable, (ii) reverse-engineer subset selection to a max-flow formulation, and (iii) apply polymatroid theory to reduce the problem to a convex program for i.i.d. drafts from a single draft model. Theoretical guarantees are given and empirical results demonstrate the effectiveness of the proposed method.", "questions": "- When extending to the multi-step case, can the authors comment on how the compounding error is expected to scale?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper turns an exponential OTLP into a convex program in tolerable number of variables (under i.i.d. drafts) is a substantial conceptual and practical advance.\n- It also provides approximation error guarantees, which helps to determine the time-precision trade-off.\n- The experiments demonstrated the strong performance of the proposed method.", "weaknesses": "- The main convex reduction requires i.i.d. drafts from a single $q$. There are some works adopt mixture drafts across experts. The iid configuration may be one concern of the proposed method.\n- The analysis focuses on solver runtime rather than full end-to-end throughput.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)