betaFeedback

WorksComputer Science

Adaptive Multi-Token Prediction: How far should we go?

Abstract

Multi-token prediction (MTP) can accelerate language-model decoding by drafting several tokens and verifying them in a single target-model pass. However, the best speculation horizon changes with context: longer drafts offer greater amortization when reliable, but can waste compute on suffixes discarded after a rejection. Unlike autoregressive drafting, where a stopping rule can decide token by token, MTP must fix the horizon before drafting, as all heads fire in the same forward pass. We therefore formulate horizon selection as an online control problem, using verification feedback to learn how far the draft can be trusted in each context, and introduce Adaptive Multi-Token Prediction (AMTP): a lightweight controller that requires no retraining and leaves the exact verifier unchanged. To guide horizon selection, we characterize the expected number of tokens committed at each horizon via acceptance survival, the probability that a draft prefix is fully accepted. Before each round, AMTP predicts how far the draft is likely to survive and picks the horizon with the highest expected tokens per second, learning freely from every verification pass. Theoretically, we show that any online learner's prediction error translates into throughput regret against the best horizon for each context, and in turn into a bound on wall-clock completion time. With online gradient descent, this regret is sublinear. Across five draft-target pairings built on Llama-3.1-8B-Instruct with Medusa heads, Meta's MTP models, and Qwen3-4B-Inst-2507-MTP, evaluated on AIME 2025 and GSM8K, AMTP decodes up to 4.1x faster than standard decoding and matches or outperforms the fixed window in 8 of 10 settings, with throughput gains of up to 10%.

Introduction

Autoregressive decoding generates each new token through an evaluation of a target language model. Speculative decoding reduces this sequential bottleneck by using a cheaper draft mechanism to propose several tokens and evaluating them in parallel with the target model [33, 20, 9]. With an appropriate acceptance-and-correction rule, this procedure preserves the target distribution while committing multiple tokens in a single round [20, 9, 34]. Multi-token prediction (MTP) provides a natural proposal mechanism by predicting several future tokens from a shared representation [14, 7, 5], and have witnessed enormous success in practice: for instance, MTP modules are now shipped in frontier models [12], and pretrained next-token models can be converted into MTP drafters without architectural changes [32, 18, 39]. These methods create an inference-time decision that is distinct from learning a good draft model: how many tokens should be proposed before the next verification step? We refer to this quantity as the speculation horizon.

The speculation horizon directly affects decoding efficiency. A longer horizon amortizes verification over more committed tokens when the draft is reliable, but after an early rejection the discarded suffix adds latency and no output. Horizon selection therefore balances the expected gain from additional accepted tokens against the risk of speculating too far. We evaluate each horizon by its conditional throughput: the ratio of its expected number of committed tokens to its expected round latency. Even for a fixed draft-target pair, the throughput-maximizing horizon varies with context, because acceptance probabilities at each draft position depend on context. For MTP, this choice has a structure that isn’t exploited in current methods [4]: an autoregressive drafter can decide token by token whether to keep drafting, but MTP heads produce all draft tokens in a single forward pass, so the horizon must be fixed before drafting, from information available at that point.

Existing adaptive methods do not make this decision without additional training. Most stop an autoregressive drafter token by token, using a trained classifier or acceptance head [30, 17], entropy-based bounds [1, 38], or parallel drafting and verification [28]. Others shape draft trees from confidence after drafting [22, 23, 8], prune verification prefixes with predicted survival probabilities [10], or train reinforcement-learning policies for draft depth [35]. Concurrent work trains a router that selects the span length before decoding, but requires new prediction heads and verifies against greedy decoding only [11]. In fact, to our knowledge, AMTP is the first training-free method that selects the MTP horizon before drafting at every round. A complementary line of work uses verification feedback online to adapt the draft model [29, 31] or to select among drafters and hyperparameter configurations with regret guarantees against the best fixed choice [27, 16]. However, in this work, we compare against the stronger benchmark of the best horizon at each visited context. We study how learning acceptance behavior from verification feedback affects horizon-selection performance, and, for a given target model and draft mechanism, we develop an online controller and bound its conditional throughput regret relative to the best horizon at each visited context in terms of cumulative prediction error. § 2 discusses related work in detail.

To relate prediction error to horizon-selection, we first identify the acceptance statistics that influence the expected number of committed tokens for each horizon. A draft token can be committed as an accepted proposal only if all prior proposals are also accepted. We characterize the joint acceptance event via acceptance survival, the probability that a draft prefix is fully accepted, which further determines the expected number of committed tokens exactly. We express them in terms of conditional rejection hazards, where the hazard at a position is its rejection probability given acceptance of all prior proposals. Our analyses holds for general causal proposals, including independent and correlated prediction heads [7, 5]. Estimating the hazards requires distinguishing between proposed and surviving prefixes: verification provides draft-target discrepancies along sampled proposal prefixes, whereas the hazards average these discrepancies under the distribution of prefixes that survive verification. So, we derive a survival-weighted regression objective that targets these conditional hazards, and its excess population loss is the survival-weighted hazard-prediction error that enters our throughput-regret bound, mirroring decision-focused learning, where prediction losses are judged by the induced decisions (Elmachtoub and Grigas, 2022).

We use this objective to develop Adaptive Multi-Token Prediction (AMTP), a training-free horizon controller equipped with an online adaptive learning algorithm. Before drafting, AMTP combines hazard-based forecasts of committed tokens with estimates of round latency to evaluate the throughput of each horizon. Short horizons, however, conceal verification feedback at later positions. To learn under this partial feedback, AMTP combines greedy throughput-based selection with randomized full-horizon exploration [19] and uses inverse-probability weighting to obtain unbiased estimates of the survival-weighted regression loss.

Our contributions are as follows:

  • Acceptance survival. We characterize horizon selection through accepted-prefix survival and round cost for general causal proposals, showing how survival determines the expected number of committed tokens for each horizon (§ 3).

  • AMTP. We introduce a training-free online controller that chooses the MTP horizon before each round, by maximizing predicted tokens per second, learning from partial feedback of short horizons via randomized exploration and inverse-probability weighting (§ 4).

  • Prediction error to wall-clock time. We show that the prediction error of any online learner translates into throughput regret against the best horizon for each context, and in turn into a bound on expected completion time. With online gradient descent Zinkevich, [40] under partial feedback, the regret is O(T4/5(1+PT)1/5)O(T^{4/5}(1+P_T)^{1/5}), which is sublinear (§ 5).

  • Experiments. Across five draft–target pairings and two reasoning benchmarks, AMTP decodes up to 4.1×4.1\times faster than standard decoding and matches or outperforms the fixed window in 8 of 10 settings, with throughput gains of up to 10%10\% (§ 6).

Related Work

Speculative decoding and multi-token proposals. Speculative decoding drafts tokens with a cheap proposal and verifies them in parallel with the target model, using an acceptance-and-correction rule that leaves the target distribution unchanged [20, 9]. Most work uses a separate next-token draft model, or, as in EAGLE, a lightweight head that drafts autoregressively at the feature level [21]. Multi-token prediction (MTP) instead trains several future-token heads on a shared representation [14]; Medusa adds such heads to an existing model and verifies candidate continuations with tree attention [7], and recent work obtains MTP models from pretrained next-token models by self-distillation [18]. Joint multi-token prediction studies how to learn representations that support predicting several tokens at once [2]. We keep the exact verifier and study a different question: given a fixed proposal, how many tokens should we draft in each round?

Adaptive draft length for autoregressive drafters. A substantial line of work adapts the draft length of a next-token drafter. DISCO trains a classifier that decides after each drafted token whether to continue [30]; SpecDec++ adds an acceptance-prediction head to the draft model and stops once the predicted probability of a rejection crosses a threshold [17]; AdaEDL stops when an entropy-based lower bound on the acceptance probability falls below a threshold [1]; and SVIP derives a similar entropy-based stopping policy for long-form generation [38]. EAGLE-2 instead grows a draft tree whose shape follows context-dependent confidence [22], and Learning to Draft trains reinforcement-learning policies for draft depth and verification size with throughput rewards [35]. These methods share a structural assumption: drafting is sequential, so the decision to stop can be made token by token, after each drafted token is observed and before the next one is paid for. However, MTP removes this option. All heads fire in the same forward pass, so the cost of drafting is incurred up front and the horizon must be fixed before any draft token is sampled. Truncating a complete MTP draft afterwards saves verification cost but not drafting cost, and choosing the cut point after inspecting sampled tokens can break exactness (Appendix 3.1). AMTP is designed for this setting: it chooses the horizon from pre-draft information only, and our statistical and online-optimization analysis of horizon selection and acceptance survival applies to any causal proposal, including both independent and correlated heads.

Online learning for speculative decoding. Verification feedback has also been used to adapt speculative decoding online. OnlineSpec updates an evolving draft model and relates its dynamic regret to accepted length at a fixed candidate length [31]. Not-a-Bandit gives no-regret guarantees for selecting among draft models [27]. BanditSpec treats speculative-decoding hyperparameters, including the speculation length, as bandit arms and bounds regret against the best fixed configuration [16]. Our guarantee uses a stronger comparator, the best horizon for each context along the realized decoding trajectory, and is learner-agnostic: any online regression method’s prediction error transfers to throughput regret, with online gradient descent [40] as one instantiation. The broader strategy of translating prediction or optimization error into decision quality is related to perturbation-based model predictive control [24] and online adaptive policy selection [25, 26], which rely on assumptions about the controlled dynamics, such as contractive perturbations, that we do not impose on the language-model prefixes.

Speculation as a Survival Problem

We first describe one round of speculation, and then show that a single sequence of rejection hazards determines the expected gain of every horizon.

One Round of Speculation: Draft, Verify, Commit

At round tt, let Ht=x1:ntH_t = x_{1:n_t} be the committed prefix and let Ft\mathcal{F}_t contain all information available before the next horizon is chosen, including HtH_t, system state, and the controller parameters. For 1≤k≤K1 \le k \le K, we define the target and proposal block laws

Pt(k)(y1:k)=∏j=1kpt,j(yj∣y<j),Qt(k)(y1:k)=∏j=1kqt,j(yj∣y<j),(1)P_t^{(k)}(y_{1:k}) = \prod_{j=1}^{k} p_{t,j}(y_j \mid y_{<j}), \qquad Q_t^{(k)}(y_{1:k}) = \prod_{j=1}^{k} q_{t,j}(y_j \mid y_{<j}), \tag*{(1)}

where conditioning on HtH_t and the fixed proposal parameters ϕ\phi is suppressed. We let Pt:=Pt(K)P_t := P_t^{(K)} and Qt:=Qt(K)Q_t := Q_t^{(K)}. In this lens, independent MTP heads form the special case qt,j(⋅∣y<j)=qt,j(⋅∣Ht)q_{t,j}(\cdot\mid y_{<j}) = q_{t,j}(\cdot\mid H_t), where recurrent or otherwise correlated heads (Ankner et al., [5]) keep the dependence on y<jy_{<j}, and our analytic framework covers both of these cases.

The horizon (or action) kt∈{1,…,K}k_t \in\{1,\ldots,K\} is chosen before the current draft is sampled. Moreover, every horizon truncates the same causal law QtQ_t, so changing kk does not change the distribution of earlier draft tokens: it only decides how many of them are drafted and sent to the verifier. A round proceeds as in Figure 1: the drafter samples Y1:k∼Qt(k)Y_{1:k} \sim Q_t^{(k)}, and a single target pass scores all kk positions. Exact speculative verification (Leviathan et al., [20]; Chen et al., [9]) then checks the draft from left to right, accepting YjY_j with probability

MTP with exact verification

Figure 1. MTP with exact verification. Proposal heads condition on earlier sampled tokens. One target pass scores pj(⋅∣Ht,Y<j)p_j(\cdot\mid H_t,Y_{<j}), and circles denote prefix-ordered acceptance. Rejection emits a residual correction ZZ. The dashed bonus branch requires full acceptance.

αt,j:=min⁡{1,pt,j(Yj∣Y<j)qt,j(Yj∣Y<j)},(2)\alpha_{t,j} := \min\left\{1,\frac{p_{t,j}(Y_j\mid Y_{<j})}{q_{t,j}(Y_j\mid Y_{<j})}\right\}, \tag*{(2)}

where qt,j(Yj∣Y<j)>0q_{t,j}(Y_j\mid Y_{<j}) > 0 on a sampled proposal. At the first rejection, the verifier draws a correction token from the normalized positive part of pt,j−qt,jp_{t,j}-q_{t,j}. If all kk proposals are accepted, it draws a bonus token from the target conditional at the end of the draft. So, a round with horizon kk commits Lt(k)=1+At(k)L_t(k) = 1+A_t(k) tokens, where At(k)A_t(k) is the length of the accepted draft prefix, and the committed tokens follow the target law exactly (Leviathan et al., [20]; Chen et al., [9]). We analyze a fixed output-token budget where truncating the final output preserves its target law.

Exactness requires choosing the horizon before drafting. Exactness continues to hold when ktk_t is chosen adaptively, provided it depends only on Ft\mathcal{F}_t and on randomness independent of the current draft. Earlier acceptance decisions depend only on earlier proposals and independent coins, so the verifier reaches position jj with the proposal still distributed as qt,j(⋅∣Y<j)q_{t,j}(\cdot\mid Y_{<j}), and the standard one-step argument applies at every position and every round, however poorly the horizon is chosen. However, choosing the horizon after seeing the draft can break this, even for a perfect drafter. To see this, let p=qp=q be independent fair bits, draw Y1,Y2Y_1,Y_2, and keep k=2k=2 if Y2=1Y_2=1 and k=1k=1 otherwise. Every drafted token is accepted, so the second emitted token is Y2=1Y_2=1 on the long branch and a new fair bonus token on the short one. It equals 11 with probability 3/43/4 rather than 1/21/2. AMTP therefore fixes ktk_t before sampling the draft. Sampling transformations such as temperature or top-pp truncation must be built into the pp and qq the verifier uses.

Moreover, how likely a draft token is to pass depends on how far the proposal is from the target at that position. For a proposed prefix u=y<ju=y_{<j}, we can measure this by the local discrepancy

et,j(u):=TV⁡(pt,j(⋅∣u),qt,j(⋅∣u))=12∥pt,j(⋅∣u)−qt,j(⋅∣u)∥1,(3)e_{t,j}(u) := \operatorname{TV}(p_{t,j}(\cdot\mid u),q_{t,j}(\cdot\mid u)) = \frac{1}{2}\lVert p_{t,j}(\cdot\mid u)-q_{t,j}(\cdot\mid u)\rVert_1, \tag*{(3)}

which is exactly the probability that position jj is rejected given that the verifier reaches it along prefix uu: equivalently, E[αt,j∣Y<j=u,Ft]=1−et,j(u)\mathbb{E}[\alpha_{t,j}\mid Y_{<j}=u,\mathcal{F}_t]=1-e_{t,j}(u).

Importantly, accurate token marginals do not guarantee an accurate multi-token proposal. For instance (as in Appendix § 10), independent MTP heads can fit every position perfectly while missing dependencies among future tokens. The block KL divergence splits into a marginal fitting error and a dependence term that remains even for exact marginals. In a simple repeated-bit example, the block mismatch approaches its maximum while the expected number of committed tokens per round stays below three for every horizon, so longer windows add a verification cost with little additional token gain. The horizon should therefore be chosen from how long draft prefixes actually survive verification, and from what each round costs, rather than from marginal prediction accuracy alone.

Survival and the Rejection Hazard

We now make the the notion of “how long draft prefixes survive” precise, and formally define the acceptance survival and rejection hazard. For a virtual full draft Y∼QtY \sim Q_t, we define the prefix acceptance weight via Wt,0=1W_{t,0}=1 and Wt,j=∏r=1jαt,rW_{t,j}=\prod_{r=1}^{j}\alpha_{t,r}, which is the probability that the verifier accepts all of Y1:jY_{1:j} given the sampled tokens.

Definition 1 (Acceptance survival). The acceptance survival is the probability of accepting at least jj draft tokens, conditional on Ft\mathcal{F}_t, and is given by st,j=EQt[Wt,j]s_{t,j}=\mathbb{E}_{Q_t}[W_{t,j}] with st,0=1s_{t,0}=1.

Definition 2 (Rejection hazard). The rejection hazard at position jj is the probability of rejection there, given that the preceding j−1j-1 proposals were accepted, and is given (conditional on Ft\mathcal{F}_t) by

ht,j=EQt[Wt,j−1et,j(Y<j)]st,j−1.(4)h_{t,j}=\frac{\mathbb{E}_{Q_t}[W_{t,j-1}e_{t,j}(Y_{<j})]}{s_{t,j-1}}. \tag*{(4)}

When st,j−1=0s_{t,j-1}=0, we set ht,j=0h_{t,j}=0, as later survival probabilities are zero regardless of this convention. Since E[αt,j∣Y<j,Ft]=1−et,j(Y<j)\mathbb{E}[\alpha_{t,j}\mid Y_{<j},\mathcal{F}_t]=1-e_{t,j}(Y_{<j}), the survival and expected gain follow from the hazard:

st,j=∏r=1j(1−ht,r),Gt(k):=E[Lt(k)∣Ft]=1+∑j=1kst,j.(5)s_{t,j}=\prod_{r=1}^{j}(1-h_{t,r}), \qquad G_t(k):=\mathbb{E}[L_t(k)\mid\mathcal{F}_t]=1+\sum_{j=1}^{k}s_{t,j}. \tag*{(5)}

where quantities indexed by an action refer to the potential outcome of choosing that horizon, even if the policy assigns it zero probability. To justify why hazards are the right prediction target, we point to (5): a single vector (ht,1,…,ht,K)(h_{t,1},\ldots,h_{t,K}) determines the expected gain of all KK horizons at once, so a controller that predicts it can score every horizon before drafting. Indeed, the identities need no independence between draft positions, so they hold for correlated heads as well as independent ones.

Why the hazard is survival-weighted. The numerator of (4) weights each prefix by its likelihood of surviving to position jj. Replacing ht,jh_{t,j} with the unweighted mean discrepancy EQt[et,j(Y<j)]\mathbb{E}_{Q_t}[e_{t,j}(Y_{<j})] is generally incorrect since prefixes that survive verification are distributed differently from arbitrary draft prefixes. For instance, consider a binary vocabulary {a,b}\{a,b\}. The first head proposes aa or bb with probability 1/21/2 each, while the target places mass 3/43/4 on aa, so αt,1=1\alpha_{t,1}=1 on aa, αt,2=1/2\alpha_{t,2}=1/2 on bb, and st,1=3/4s_{t,1}=3/4. Then, suppose the second head matches the target exactly after aa but has disjoint support from it after bb, so et,2(a)=0e_{t,2}(a)=0 and et,2(b)=1e_{t,2}(b)=1. The unweighted mean discrepancy at position 2 is 1/21/2, but ht,2=1/43/4=1/3h_{t,2}=\frac{1/4}{3/4}=1/3, since a draft that starts with the well matched token bb is less likely to reach position 2 at all. Here, the true gain is G2(2)=1+34+12=2.25G_2(2)=1+\frac{3}{4}+\frac{1}{2}=2.25, and plugging this in the unweighted mean gives 2.125. Section 4 shows how to build this change of prefix distribution into the learning objective.

Online Horizon Control

Each round of speculative decoding poses a one-step control problem: before drafting, choose the horizon ktk_t that maximizes throughput. If the rejection hazards were known, Section 3 would solve this problem exactly, since (5) gives the expected gain of every horizon. However, since they are not known, AMTP uses certainty equivalence: it plugs in predicted hazards, acts on them, and updates the predictor via online gradient descent (OGD) from the feedback that verification provides. Algorithm 1 gives the full loop and Figure 2 illustrates it.

AMTP’s online control loop

Figure 2. AMTP’s online control loop. Before drafting, it picks the horizon with the highest predicted throughput. Verification feedback at every drafted position, including those after a rejection, enters the weighted loss in Equation 8, and an OGD step updates the hazard predictor.

The Control Problem. Let Ct(k)C_t(k) be the conditional expected cost of a round with horizon kk, including drafting, verification, synchronization and all controller overhead, with 0<cmin⁡≤Ct(k)≤cmax⁡<∞0<c_{\min}\le C_t(k)\le c_{\max}<\infty. We compare horizons at the same learner state and under the same update protocol, where the controller’s objective is its throughput, and the optimal horizon at the current history is

Rt(k)=Gt(k)Ct(k),kt∗∈arg⁡max⁡1≤k≤K Rt(k).(6)R_t(k)=\frac{G_t(k)}{C_t(k)}, \qquad k_t^*\in\underset{1\le k\le K}{\arg\max}\ R_t(k). \tag*{(6)}

Algorithm 1 Adaptive Multi-Token Prediction

Require: Maximum horizon KK; parameter set Θ\Theta and θ1∈Θ\theta_1 \in\Theta; exploration rate ε∈(0,1]\varepsilon\in(0,1]; step sizes ηt\eta_t; initial cost model C^1\widehat{C}_1

  1. for each speculative round t=1,2,…t=1,2,\ldots do

  2. Observe pre-draft features ztz_t; predict hazards h^θt,t,j\widehat{h}_{\theta_t,t,j} and costs C^t(j)\widehat{C}_t(j) for j=1,…,Kj=1,\ldots,K

  3. Set κt←arg⁡max⁡kG^t(k)/C^t(k)\kappa_t \leftarrow\arg\max_k \widehat{G}_t(k)/\widehat{C}_t(k) using equation 7 ▷ plug-in control, O(K)O(K)

  4. With probability ε\varepsilon set kt←Kk_t \leftarrow K; otherwise kt←κtk_t \leftarrow\kappa_t ▷ exploration

  5. Draft Y1:kt∼Q(kt)Y_{1:k_t} \sim Q^{(k_t)} and verify all ktk_t positions in one target pass

  6. Commit the accepted prefix and one correction or bonus token

  7. For j≤ktj \le k_t: record et,jobs=et,j(Y<j)e^{\mathrm{obs}}_{t,j}=e_{t,j}(Y_{<j}), Wt,j−1=∏r<jαt,rW_{t,j-1}=\prod_{r<j}\alpha_{t,r}, and πt,j=(1−ε)1{j≤κt}+ε\pi_{t,j}=(1-\varepsilon)\mathbf{1}\{j\le\kappa_t\}+\varepsilon

  8. Update θt+1←ΠΘ(θt−ηt∇ℓ^t(θt))\theta_{t+1}\leftarrow\Pi_\Theta(\theta_t-\eta_t\nabla\widehat{\ell}_t(\theta_t)) with ℓ^t\widehat{\ell}_t from equation 8 ▷ OGD

  9. Record the measured round cost ctc_t and update the cost model C^t+1\widehat{C}_{t+1}

  10. end for

AMTP predicts the rejection hazards h^θt,t,j∈[0,1]\widehat{h}_{\theta_t,t,j}\in[0,1] from pre-draft features ztz_t and position jj, and estimates rounds costs C^t(k)>0\widehat{C}_t(k)>0, where the predictions are Ft\mathcal{F}_t-measurable. It converts the hazard predictions into survival probabilities and expected token gains and selects a candidate horizon:

s^t,j=∏r=1j(1−h^θt,t,r),G^t(k)=1+∑j=1ks^t,j,κt∈arg⁡max⁡1≤k≤KG^t(k)C^t(k).(7)\widehat{s}_{t,j}=\prod_{r=1}^{j}(1-\widehat{h}_{\theta_t,t,r}), \qquad\widehat{G}_t(k)=1+\sum_{j=1}^{k}\widehat{s}_{t,j}, \qquad\kappa_t\in\arg\max_{1\le k\le K}\frac{\widehat{G}_t(k)}{\widehat{C}_t(k)}. \tag*{(7)}

with a fixed tie-breaking rule. A running product and a running sum score all KK horizons in O(K)O(K) time, and the controller does not assume that throughput is unimodal in kk, and so the only part of (7) that must be learned is the hazard forecaster θt\theta_t.

Learning the hazards via Online Gradient Descent (OGD)

OGD needs a loss whose error is reflective of the error attributed to the control problem. Following the change of prefix distribution in Section 3.2, we use the survival-weighted population loss

ℓt(θ)=EQt[∑j=1KWt,j−1(et,j(Y<j)−h^θ,t,j)2],(8)\ell_t(\theta)=\mathbb{E}_{Q_t}\left[\sum_{j=1}^{K}W_{t,j-1}\left(e_{t,j}(Y_{<j})-\widehat{h}_{\theta,t,j}\right)^2\right], \tag*{(8)}

conditional on Ft\mathcal{F}_t, with the proposal law and features held fixed. Let ℓtB\ell_t^B be the same expression with the true hazards ht,jh_{t,j} in place of h^θ,t,j\widehat{h}_{\theta,t,j}. Then, ℓtB\ell_t^B represents the minimum loss over unrestricted pre-draft hazard predictions. We then show the following calibration identity:

Lemma 1 (Calibration identity). For every Ft\mathcal{F}_t-measurable parameter θ\theta,

Et(θ):=ℓt(θ)−ℓtB=∑j=1Kst,j−1(h^θ,t,j−ht,j)2.(9)\mathcal{E}_t(\theta):=\ell_t(\theta)-\ell_t^B=\sum_{j=1}^{K}s_{t,j-1}\left(\widehat{h}_{\theta,t,j}-h_{t,j}\right)^2. \tag*{(9)}

Expanding the weighted square around ht,jh_{t,j} yields the identity, and the cross term vanishes by the hazard definition in (4); so, the loss is minimized by the true hazards, and its excess is a hazard error weighted by how often each position is reached: it is weighted less on positions that are less likely to survive verification. Section 5 shows that this excess controls the throughput lost.

The ideal learner. If verification revealed et,jobs=et,j(Y<j)e^{\mathrm{obs}}_{t,j}=e_{t,j}(Y_{<j}) and Wt,j−1W_{t,j-1} at all KK positions of a draft Y∼QtY\sim Q_t, then the realized loss ℓ~t(θ)=∑j=1KWt,j−1(et,jobs−h^θ,t,j)2\widetilde{\ell}_t(\theta)=\sum_{j=1}^{K}W_{t,j-1}(e^{\mathrm{obs}}_{t,j}-\widehat{h}_{\theta,t,j})^2 would be unbiased for ℓt(θ)\ell_t(\theta), and the controller would simply run projected OGD [40, 15]:

θt+1=ΠΘ(θt−η∇ℓ~t(θt)).(10)\theta_{t+1}=\Pi_\Theta\left(\theta_t-\eta\nabla\widetilde{\ell}_t(\theta_t)\right). \tag*{(10)}

where ΠΘ(⋅)\Pi_\Theta(\cdot) is the projection onto the (convex) set of parameters Θ\Theta. For an affine forecaster h^θ,t,j=⟨θ,xt,j⟩\widehat{h}_{\theta,t,j}=\langle\theta,x_{t,j}\rangle, the gradient is −2∑jWt,j−1(et,jobs−⟨θ,xt,j⟩)xt,j-2\sum_j W_{t,j-1}(e^{\mathrm{obs}}_{t,j}-\langle\theta,x_{t,j}\rangle)x_{t,j}. This learner always acts greedily, and § 5 shows that its throughput regret is sublinear in the number of rounds. However, this is an idealization as the discrepancy et,je_{t,j} compares the draft with the target distribution pt,jp_{t,j}, and the target computes pt,jp_{t,j} only at positions it verifies. So, a round that drafts kt<Kk_t < K tokens gives no feedback at positions kt+1,…,Kk_t+1,\ldots,K, and observing every position at each round would mean drafting and verifying the full window each time, which defeats the purpose of choosing the horizon. AMTP avoids this: it drafts the full window only in a small random fraction of rounds and re-weights the feedback so that the loss stays unbiased (§ 4).

Learning from partial feedback

A round with horizon ktk_t reveals feedback only at positions 1,…,kt1,\ldots,k_t. If a greedy controller under-estimates late-position survival, its drafts might be short, it may never observe late positions, and it might never corrects the estimate. To address this, AMTP makes two changes to the ideal learner.

Exploration. With probability 1−ε1-\varepsilon the controller drafts kt=κtk_t=\kappa_t, and with probability ε\varepsilon it drafts the full window kt=Kk_t=K [19]. The randomness here is independent of the draft given Ft\mathcal{F}_t, so position jj is observed with known probability πt,j=(1−ε)1{j≤κt}+ε≥ε\pi_{t,j}=(1-\varepsilon)\mathbf{1}\{j\le\kappa_t\}+\varepsilon\ge\varepsilon. Other exploration schemes, such as Thompson sampling for contextual bandits [37, 3], could replace uniform full-horizon exploration. We use ε\varepsilon-greedy exploration because it gives known inclusion probabilities, which is needed for inverse-probability weighting.

Inverse-probability weighting. After verification, et,jobse^{\mathrm{obs}}_{t,j} and Wt,j−1W_{t,j-1} are available for every j≤ktj\le k_t. Then, reweighting each observed term by its inclusion probability gives

ℓ^t(θ)=∑j=1ktWt,j−1πt,j(et,jobs−h^θ,t,j)2,E[ℓ^t(θ)∣Ft]=ℓt(θ).(11)\hat{\ell}_t(\theta)=\sum_{j=1}^{k_t}\frac{W_{t,j-1}}{\pi_{t,j}}\left(e^{\mathrm{obs}}_{t,j}-\hat{h}_{\theta,t,j}\right)^2,\qquad\mathbb{E}[\hat{\ell}_t(\theta)\mid\mathcal{F}_t]=\ell_t(\theta). \tag*{(11)}

AMTP runs (10) with ℓ^t\hat{\ell}_t in place of ℓ~t\tilde{\ell}_t, holding Wt,j−1W_{t,j-1} and πt,j\pi_{t,j} fixed in line 8 of Alg 1. However, relative to the ideal learner, exploration costs some throughput in rounds drafting KK, and the factor 1/πt,j≤1/ε1/\pi_{t,j}\le1/\varepsilon makes gradients noisier: we quantify both in § 5.

From Prediction Error to Decoding Efficiency

We now ask how much decoding efficiency AMTP loses by acting on predicted rather than true hazards. First, we show that, for any online learner, the throughput regret against the best horizon at each visited history is controlled by the learner’s excess prediction loss. We then bound that loss for OGD, first for the ideal full-feedback learner and then for AMTP’s partial-feedback learner, and then we bound the price of partial feedback. Finally, we show how to convert the throughput regret into bounds on expected completion time and speedup. We give complete proofs in Appendix B.

Prediction error to throughput regret

We allow the controller to maximize predicted throughput only approximately, with a selection error ξt≥0\xi_t \ge0 that accommodates exploration:

R^t(k)=G^t(k)Ct(k),R^t(kt)≥max⁡1≤k≤KR^t(k)−ξt.(12)\widehat{R}_t(k)=\frac{\widehat{G}_t(k)}{C_t(k)},\qquad\widehat{R}_t(k_t)\ge\max_{1\leq k\leq K}\widehat{R}_t(k)-\xi_t. \tag*{(12)}

For a comparator sequence θ1:T∗\theta^*_{1:T}, define

RT=∑t=1T(ℓt(θt)−ℓt(θt∗)),AT=∑t=1T(ℓt(θt∗)−ℓtB),DT=∑t=1T(Rt(kt∗)−Rt(kt)).\mathcal{R}_T=\sum_{t=1}^{T}\left(\ell_t(\theta_t)-\ell_t(\theta_t^*)\right),\qquad\mathcal{A}_T=\sum_{t=1}^{T}\left(\ell_t(\theta_t^*)-\ell_t^B\right),\qquad\mathcal{D}_T=\sum_{t=1}^{T}\left(R_t(k_t^*)-R_t(k_t)\right).

Here RT\mathcal{R}_T is the learner’s regression regret against the comparator, AT≥0\mathcal{A}_T\geq0 is the comparator’s approximation error, and DT\mathcal{D}_T is the throughput regret against the best horizon at each history the learner visits. This comparator is stronger than the best fixed horizon: it may change from round to round with the context. By Lemma 1, RT+AT=∑t=1TEt(θt)≥0\mathcal{R}_T+\mathcal{A}_T=\sum_{t=1}^{T}\mathcal{E}_t(\theta_t)\geq0. Write ΛK=cmin⁡−1K(K+1)(2K+1)6\Lambda_K=c_{\min}^{-1}\sqrt{\frac{K(K+1)(2K+1)}{6}}.

Theorem 1 (Dynamic regret transfer). Under the preceding assumptions, for every comparator sequence and every realization of the pre-round histories and selected horizons, we have

DT≤2ΛKT(RT+AT)+∑t=1Tξt.(13)\mathcal{D}_T\leq2\Lambda_K\sqrt{T\left(\mathcal{R}_T+\mathcal{A}_T\right)}+\sum_{t=1}^{T}\xi_t. \tag*{(13)}

The key idea is to connect calibration to throughput prediction, and then to horizon selection. Telescoping the survival products and applying Lemma 1 bounds the error in predicted throughput uniformly over horizons. Combining this with Equation (12) bounds the per-round regret:

max⁡1≤k≤K∣R^t(k)−Rt(k)∣≤ΛKEt(θt),Rt(kt∗)−Rt(kt)≤2ΛKEt(θt)+ξt.\max_{1\leq k\leq K}\left|\widehat{R}_t(k)-R_t(k)\right|\leq\Lambda_K\sqrt{\mathcal{E}_t(\theta_t)},\qquad R_t(k_t^*)-R_t(k_t)\leq2\Lambda_K\sqrt{\mathcal{E}_t(\theta_t)}+\xi_t.

Summing over rounds and applying Cauchy–Schwarz gives Equation (13). A regression guarantee therefore becomes a throughput guarantee through the learner’s total excess prediction loss, including the comparator’s approximation error. Importantly, this does not depend on how θt\theta_t is produced, which allows us to use any online learning algorithm and transfer their guarantees to our setting.

Remark 1 (Sharpness). The square-root dependence in Eq. (13) cannot be improved uniformly. Prop. 2 with independent proposals and known costs incurs one-round throughput regret 23Et(θt)\frac{2}{3}\sqrt{\mathcal{E}_t(\theta_t)}.

Remark 2 (Estimated costs). Suppose instead that the controller uses C^t(k)≥cmin⁡\widehat{C}_t(k)\geq c_{\min}, and let δtC=max⁡1≤k≤K∣C^t(k)−Ct(k)∣\delta_t^C=\max_{1\leq k\leq K}|\widehat{C}_t(k)-C_t(k)|. Then, measuring ξt\xi_t relative to G^t(k)/C^t(k)\widehat{G}_t(k)/\widehat{C}_t(k) gives

DT≤2ΛKT(RT+AT)+∑t=1Tξt+2(K+1)cmin⁡2∑t=1TδtC.(14)\mathcal{D}_T\leq2\Lambda_K\sqrt{T\left(\mathcal{R}_T+\mathcal{A}_T\right)}+\sum_{t=1}^{T}\xi_t+\frac{2(K+1)}{c_{\min}^2}\sum_{t=1}^{T}\delta_t^C. \tag*{(14)}

Learning the hazards with OGD

We now bound RT\mathcal{R}_T for the two learners of § 4. Both use an affine forecaster h^θ,t,j=⟨θ,xt,j⟩\widehat{h}_{\theta,t,j}=\langle\theta,x_{t,j}\rangle on a nonempty closed convex set Θ\Theta of diameter at most DD. The features are Ft\mathcal{F}_t-measurable with ∥xt,j∥2≤F\lVert x_{t,j}\rVert_2\leq F, and forecasts lie in [0,1][0,1] for all θ∈Θ\theta\in\Theta. Initialize θ1∈Θ\theta_1\in\Theta. The comparator θt∗∈Θ\theta_t^*\in\Theta is Ft\mathcal{F}_t-measurable, and its path length is bounded almost surely by a deterministic quantity, ∑t=1T−1∥θt+1∗−θt∗∥2≤PT\sum_{t=1}^{T-1}\lVert\theta_{t+1}^*-\theta_t^*\rVert_2\leq P_T, as is standard for dynamic regret ([40, 6, 36]). We assume known costs throughout this subsection.

Ideal full feedback. The ideal learner of § 4 observes all KK positions and always acts greedily, so ξt=0\xi_t=0. Its gradients ∇ℓ^t(θt)\nabla\widehat{\ell}_t(\theta_t) are unbiased for ∇ℓt(θt)\nabla\ell_t(\theta_t) and satisfy ∥∇ℓ^t(θt)∥2≤2FK\lVert\nabla\widehat{\ell}_t(\theta_t)\rVert_2\leq2FK.

Corollary 1 (OGD with full feedback). Under these conditions, projected OGD (Equation (10)) on the full-feedback loss with constant step size η>0\eta>0 satisfies

ERT≤D2+2DPT2η+2ηF2K2T.(15)\mathbb{E}\mathcal{R}_T\leq\frac{D^2+2DP_T}{2\eta}+2\eta F^2K^2T. \tag*{(15)}

Under realizability, optimizing η\eta, for fixed KK, cmin⁡c_{\min}, DD, FF, gives EDT=O(T3/4(1+PT)1/4)\mathbb{E}\mathcal{D}_T=O\left(T^{3/4}(1+P_T)^{1/4}\right).

Equation 10 is the standard projected-OGD argument with a moving comparator. Theorem 1 and Jensen’s inequality then give the final rate. We give the result for any unbiased gradient with bounded second moment in Equation (10). As § 4 explains, this learner needs the target distribution at all KK positions in every round, so this is only our benchmark for an implementable controller.

Partial feedback. AMTP replaces ℓ~t\tilde{\ell}_t with the observed loss. Here, the gradients remain unbiased, but each observed term is scaled by 1πt,j≤1ε\frac{1}{\pi_{t,j}} \le\frac{1}{\varepsilon}, so for gt=∇ℓ^t(θt)g_t = \nabla\hat{\ell}_t(\theta_t) we have E[∥gt∥2∣Ft]≤4F2K2ε2\mathbb{E}[\lVert g_t\rVert^2 \mid\mathcal{F}_t] \le\frac{4F^2K^2}{\varepsilon^2}, where exploration rounds contribute E∑t=1Tξt≤εTK+1cmin⁡\mathbb{E}\sum_{t=1}^{T}\xi_t \le\frac{\varepsilon T K+1}{c_{\min}} to the selection error.

Corollary 2 (OGD with partial feedback). Under these conditions, Algorithm 1 with known costs, exploration rate ε∈(0,1]\varepsilon\in(0,1] and constant step size η>0\eta> 0 satisfies

E RT≤D2+2DPT2η+2ηF2K2Tε.(16)\mathbb{E}\,R_T \le\frac{D^2+2DP_T}{2\eta}+\frac{2\eta F^2K^2T}{\varepsilon}. \tag*{(16)}

Under realizability, optimizing η\eta, for fixed KK, cmin⁡c_{\min}, DD, FF, gives E DT=O(T4/5(1+PT)1/5)\mathbb{E}\,D_T = O\left(T^{4/5}(1+P_T)^{1/5}\right).

The projected-OGD bound with the second-moment estimate above gives equation (16), and Theorem 1 with Jensen’s inequality and a balancing argument gives the final rate. This tuning uses the number of rounds TT and a known bound PTP_T on comparator variation.

The price of partial feedback. Equations 15 and 16 differ only by the factor 1ε\frac{1}{\varepsilon} in the gradient-noise term, and the rates differ only via the selection-error term εT\varepsilon T. Here, exploration must be frequent enough to keep gradient noise in check, but it also drafts the full window when a shorter one may be better. Balancing these effects moves the rate from T3/4(1+PT)1/4T^{3/4}(1+P_T)^{1/4} to T4/5(1+PT)1/5T^{4/5}(1+P_T)^{1/5}, which are both sublinear when PT=o(T)P_T=o(T). So, the average throughput approaches that of the best horizon at each history, and AMTP pays a vanishing gap for learning from the feedback of its horizon choices.

From throughput regret to speedup

We measure the throughput regret per round, as the goal is to minimize the time to produce an output. We fix an integer output budget N≥1N \ge1, and compare AMTP with a baseline under matched prompts, the same target output law and the same timing scope. Let JNbaseJ_N^{\mathrm{base}} denote the baseline’s completion time and define its effective rate rbase(N)=N/EJNbaser_{\mathrm{base}}(N)=N/\mathbb{E}J_N^{\mathrm{base}}, assuming 0<EJNbase<∞0<\mathbb{E}J_N^{\mathrm{base}}<\infty.

Corollary 3 (Completion time and speedup). Given max⁡1≤k≤KRt(k)≥ρ>0\max_{1\le k\le K}R_t(k)\ge\rho>0 at each visited history, for some constant ρ\rho, let the realized round cost ct≥0c_t\ge0 satisfy E[ct∣Ft,kt]=Ct(kt)\mathbb{E}[c_t\mid\mathcal{F}_t,k_t]=C_t(k_t), and let

σN=inf⁡{m≥1:∑t=1mLt(kt)≥N},JN=∑t=1σNct.(17)\sigma_N=\inf\left\{m\ge1:\sum_{t=1}^{m}L_t(k_t)\ge N\right\},\qquad J_N=\sum_{t=1}^{\sigma_N}c_t. \tag*{(17)}

Extend the same policy to NN rounds and suppose that EDN≤BN\mathbb{E}D_N\le B_N. Then, the expected completion time and the speedup, defined as the ratio of expected completion times, satisfy

EJN≤N+K+cmax⁡BNρ,SN:=EJNbaseEJN≥ρ/rbase(N)1+K/N+cmax⁡BN/N.(18)\mathbb{E}J_N\le\frac{N+K+c_{\max}B_N}{\rho},\qquad S_N:=\frac{\mathbb{E}J_N^{\mathrm{base}}}{\mathbb{E}J_N}\ge\frac{\rho/r_{\mathrm{base}}(N)}{1+K/N+c_{\max}B_N/N}. \tag*{(18)}

In particular, SN>1S_N>1 whenever ρ/rbase(N)>1+K/N+cmax⁡BN/N\rho/r_{\mathrm{base}}(N)>1+K/N+c_{\max}B_N/N.

To see why, let Δt=Rt(kt∗)−Rt(kt)≥0\Delta_t=R_t(k_t^*)-R_t(k_t)\ge0. The assumption on ρ\rho gives Gt(kt)≥ρCt(kt)−cmax⁡ΔtG_t(k_t)\ge\rho C_t(k_t)-c_{\max}\Delta_t. Each round costs at least one token, so σN≤N\sigma_N\le N, and the final round overshoots the budget by at most KK tokens. Since {σN≥t}\{\sigma_N\ge t\} is determined before round tt, conditional expectations gives

ρ EJN≤E∑t=1σNLt(kt)+cmax⁡E∑t=1σNΔt≤N+K+cmax⁡BN,\rho\,\mathbb{E}J_N\le\mathbb{E}\sum_{t=1}^{\sigma_N}L_t(k_t)+c_{\max}\mathbb{E}\sum_{t=1}^{\sigma_N}\Delta_t\le N+K+c_{\max}B_N,

which is the bound in (18). Dividing the baseline’s completion time by this gives the claim.

Speedup guarantee of AMTP. Corollary 2 with T=NT=N gives BN=O(N4/5(1+PN)1/5)B_N=O(N^{4/5}(1+P_N)^{1/5}), so the penalty in Equation (18) is O(K/N+((1+PN)/N)1/5)O(K/N+((1+P_N)/N)^{1/5}). If PN=o(N)P_N=o(N) and rbase(N)→r0>0r_{\mathrm{base}}(N)\to r_0>0, the penalty vanishes and lim inf⁡N→∞SN≥ρ/r0\liminf_{N\to\infty}S_N\ge\rho/r_0. Acceptance and round cost thus set the achievable speedup ρ/r0\rho/r_0, and learning the horizon costs only a vanishing fraction of it.

Experiments

We evaluate AMTP on three self-speculative multi-token-prediction families (self-distilled Qwen3-4B, Meta’s facebook/multi-token-prediction 7B, and Medusa heads on Llama-3.1-8B-Instruct) and two cross-model pairings with a separate, larger target (self-distilled 4B → Qwen3-14B; Meta MTP 7B → Llama-2-13B), on AIME 2025 and GSM8K (full setup in Table 4, Appendix § 13). All runs disable KV caching, so verification recomputes the full context each round; each condition is a single unseeded run, and we compare conditions only within a model since hardware differs across runs. The fixed-window baseline uses the largest window each draft supports (k=16k=16, 44, 66); the adaptive controller is the affine hazard predictor and cost model of § 4 with ε\varepsilon-bounded exploration, updated by one gradient step per round (hyperparameters in Table 5, Appendix § 13).

#FamilyPairingDraftTargetPlain baselineMax kk
1Self-distilledSelf-speculativeQwen3-4B-Inst-2507-MTPSame checkpointSame checkpoint16
2Meta MTPSelf-speculativemulti-token-prediction 7BSame checkpointLlama-2-7B4
3MedusaSelf-speculativeLlama-3.1-8B-Instruct + Medusa headsSame checkpointLlama-3.1-8B-Instruct6
4Self-distilledCross-modelQwen3-4B-Inst-2507-MTPQwen3-14BQwen3-14B16
5Meta MTPCross-modelmulti-token-prediction 7BLlama-2-13BLlama-2-13B4

Table 4. MTP draft/target experiment matrix, run without KV-caches. Rows 1-3 are the core self-speculative pairings; rows 4-5 are the cross-model scaling pairings. Each row is evaluated on GSM8K and AIME 2025 with a fixed window, AMTP, and plain (next-token) decoding of the target.

QuantityValue
Maximum window KK4 / 6 / 16 (Meta / Medusa / self-dist.)
Hazard modelaffine (linear, no sigmoid link), 5 inputs
Hazard optimiser, learning rateProjected OGD, 0.01
Hazard projection radius DD10.0
Exploration rate ε\varepsilon0.1
Cost optimiser, learning rateAdam, 0.01
Start-up updates umin⁡u_{\min}20
Context scale ℓ\ell, cost scale γ\gamma100, 1000
Checkpoint intervalevery 50 updates

Table 5. AMTP configuration used in all experiments. No value was tuned per model or per task.

ModelDecodingAIME 2025 tok/sAIME 2025 Speed-upGSM8K tok/sGSM8K Speed-up
Self-distilled Qwen3-4BPlain (next-token)18.81.00×16.21.00×
Fixed k=16k=1634.01.81×38.62.39×
Adaptive (ours)34.51.83×38.32.37×
Meta MTP 7BPlain (next-token)12.51.00×4.7b1.00×
Fixed k=4k=437.73.01×19.2b4.09×
Adaptive (ours)31.92.55×19.4b4.13×
Meta MTP 7B → Llama-2-13BPlain (next-token)6.21.00×2.7b1.00×
Fixed k=4k=47.61.23×4.7b1.75×
Adaptive (ours)28.24.55×11.6b4.30×
Medusa, Llama-3.1-8BPlain (next-token)10.71.00×13.01.00×
Fixed k=6k=623.62.20×20.01.54×
Adaptive (ours)25.32.37×19.41.50×
Self-dist. 4B → Qwen3-14BPlain (next-token)10.41.00×6.4a1.00×
Fixed k=16k=1622.52.17×21.33.33×
Adaptive (ours)24.72.38×21.53.36×

Table 1. Decoding throughput (tokens/s) and speed-up over plain decoding for each draft/target pairing on AIME 2025 and GSM8K, with AMTP in bold if it exceeds the best fixed window by more than 1%. aPlain decoding run reached 1,166 of 1,319 GSM8K problems before its timeout: speed-up computed over that subset. bMeta MTP’s base checkpoints do not emit an end-of-sequence token after answering, so GSM8K runs for this pairing are capped at 100 problems, 100 rounds each.

Discussion. AMTP helps most when drafting and verification differ in cost and when reasoning traces are long and variable in length. The cross-model pairings, where draft and target are separate models, show the largest gains over the fixed window: Meta MTP 7B →Llama-2-13B improves throughput by 268% on AIME and 147% on GSM8K (over its best fixed window), and self-distilled 4B →Qwen3-14B by 10% on AIME while staying within 1% of the best fixed window on GSM8K. In the self-speculative pairings, draft and target share one forward pass, so a longer horizon costs little extra and there is less to gain: self-distilled 4B and Medusa improve by 2–7% on AIME and stay within 3% of the fixed window on GSM8K. The one regression is Meta MTP 7B on AIME (−15%). Meta’s base checkpoint does not reliably stop after answering, and every round of a longer generation costs more. We note, however, that its acceptance rate was higher under adaptive control throughout. Across all pairings, AMTP drafts fewer tokens per round while committing a similar number, allowing it to accept a higher fraction of what it drafts than any fixed window, converting wasted draft computation into completed tokens even where the net throughput effect is small.

Conclusion and Future Work

In this work, we study how far MTP should speculate. Since all MTP heads fire in a single forward pass, the horizon must be chosen before drafting, and the right choice changes with context. We showed that acceptance survival determines the expected number of committed tokens at every horizon for any causal proposal, and built AMTP, an online controller that learns survival from verification feedback and picks the horizon with the highest predicted throughput, without retraining any model or changing the exact verifier. We show that any online learner’s prediction error translates into throughput regret against the best horizon for each context, and in turn into a bound on wall-clock completion time. Empirically, AMTP decodes up to 4.1×4.1 \times faster than standard decoding and matches or outperforms the fixed window in 8 of 10 settings.

ModelEvalAccept. (%) FixedAccept. (%) Adapt.Tokens/round FixedTokens/round Adapt.Accuracy (%) PlainAccuracy (%) FixedAccuracy (%) Adapt.
Self-distilled 4BGSM8K23324.674.6389.485.085.7
Medusa 8BGSM8K33482.992.9083.279.679.2
Self-dist. 4B → 14BGSM8K21294.334.3392.8ᵃ92.993.5
Self-distilled 4BAIME18343.843.8320.030.026.7
Meta MTP 7BAIME50573.003.030.00.00.0
Meta MTP 13BAIME44522.762.510.00.00.0
Medusa 8BAIME22462.342.280.00.00.0
Self-dist. 4B → 14BAIME14283.233.2020.020.023.3

Table 2. Draft acceptance rate, tokens committed per verification round, and accuracy for plain decoding, the best fixed window and AMTP on AIME 2025 and GSM8K. ᵃPlain decoding run reached 1,166 of 1,319 GSM8K problems before its time limit; accuracy computed over that subset.

ModelEvalMean ktk_tStd.RangeDistinct kk
Self-distilled 4BGSM8K11.212.731–1616
Meta MTP 7BAIME3.540.691–44
Meta MTP 13BAIME2.930.991–44
Medusa 8BGSM8K3.951.021–66

Table 3. Distribution of the draft window ktk_t chosen by AMTP over all verification rounds of a run. We remark here that the window is not constant: it varies across rounds within a single generation and across generations.

Draft window chosen by AMTP for four models and evaluation settings

Figure 3. Draft window chosen by AMTP, averaged over generations in bins of 10 verification rounds (points; bars show one standard deviation across rounds in the bin). The window adapts as generation proceeds instead of staying at a single value.

Several limitations point to future work. Our experiments decode one sequence at a time without a KV-cache: batched serving with caching changes the cost of each horizon and is a natural direction. Comparing hazard-based and direct survival prediction, and extending horizon control to tree-structured drafts, are promising directions. Finally, it would be interesting to extend our work to adaptive diffusion-based speculative methods.

AI Use Statement

Generative AI tools assisted with editing the manuscript, generating code for the experiments, identifying and summarizing related literature, and proof-checking the mathematical formulations and proofs. The authors are responsible for checking the final claims, proofs, and citations.

Acknowledgements

We thank Adam Wierman, Jacob Abernethy, Matthew Fahrbach, and Sarah Liaw for helpful comments. EA’s research is supported by NSF Grant CCF 2338816.

Outline of the Appendices.

  • Section A provides some motivation for adaptive horizon selection;

  • Section B presents the proof of our main results;

  • Section C shows how to estimate the costs and throughput measurements;

  • Section D explains our experimental setup and provides further results.

Why Longer Drafts Degrade

Draft qualities can deteriorate with the horizon even if every head is accurate on its own. For independent heads, the block mismatch has two sources: marginal fitting error, and dependence among future target tokens that the heads cannot represent, neither of which individually determines the throughput-optimal horizon, which depends on the verifier’s acceptance profile and the round cost.

Fix a round, condition on its committed context, and suppress the round index. Let P(k)P^{(k)} and Q(k)Q^{(k)} be the target and proposal laws over the next kk tokens, assumed to be prefix marginals of common laws PP and QQ, and let PjP_j be the position-jj target marginal. The vocabulary is finite and logarithms are natural; KL identities use the usual extended-value convention.

Proposition 1 (Dependence and marginal fit). For independent heads Q(k)=∏j=1kqjQ^{(k)} = \prod_{j=1}^{k} q_j, let TC⁡P(Y1:k):=DKL(P(k)∥∏j=1kPj)\operatorname{TC}_P(Y_{1:k}) := D_{\mathrm{KL}}\left(P^{(k)} \middle\| \prod_{j=1}^{k} P_j\right) be the total correlation of the target block. Then,

DKL(P(k)∥Q(k))=TC⁡P(Y1:k)+∑j=1kDKL(Pj∥qj),(19)D_{\mathrm{KL}}\left(P^{(k)} \middle\| Q^{(k)}\right) = \operatorname{TC}_P(Y_{1:k}) + \sum_{j=1}^{k} D_{\mathrm{KL}}(P_j\|q_j), \tag*{(19)}

and, at each position jj,

EY<j∼P(j−1)[DKL(pj(⋅∣Y<j)∥qj)]=IP(Yj;Y<j)+DKL(Pj∥qj).(20)\mathbb{E}_{Y_{<j}\sim P^{(j-1)}}\left[D_{\mathrm{KL}}\left(p_j(\cdot\mid Y_{<j})\middle\|q_j\right)\right] = I_P(Y_j;Y_{<j}) + D_{\mathrm{KL}}(P_j\|q_j). \tag*{(20)}

Proof. Insert ∏jPj(yj)\prod_j P_j(y_j) into the likelihood ratio:

log⁡P(k)(y1:k)∏jqj(yj)=log⁡P(k)(y1:k)∏jPj(yj)+∑jlog⁡Pj(yj)qj(yj).\log\frac{P^{(k)}(y_{1:k})}{\prod_j q_j(y_j)} = \log\frac{P^{(k)}(y_{1:k})}{\prod_j P_j(y_j)} + \sum_j \log\frac{P_j(y_j)}{q_j(y_j)}.

and take expectations under P(k)P^{(k)}. Inserting it in the conditional ratio pj(Yj∣Y<j)qj(Yj)\frac{p_j(Y_j\mid Y_{<j})}{q_j(Y_j)} gives Eq. (20).

Even exact marginal heads, qj=Pjq_j=P_j, therefore maintain the total correlation as their block KL divergence. The term IP(Yj;Y<j)I_P(Y_j;Y_{<j}) is the information about earlier target tokens that an independent head cannot use, and heads that condition on earlier proposed tokens can reduce it.

We now explain how the block mismatch grows with the horizon. Let δ(k):=TV⁡(P(k),Q(k))\delta(k):=\operatorname{TV}(P^{(k)},Q^{(k)}). Because marginalization contracts total variation, we have

2δ(k)=∑y1:k∣∑v(P(k+1)(y1:k,v)−Q(k+1)(y1:k,v))∣≤∑y1:k,v∣P(k+1)(y1:k,v)−Q(k+1)(y1:k,v)∣=2δ(k+1).\begin{aligned} 2\delta(k) = \sum_{y_{1:k}}\left|\sum_v\left(P^{(k+1)}(y_{1:k},v)-Q^{(k+1)}(y_{1:k},v)\right)\right| \\ &\le\sum_{y_{1:k},v}\left|P^{(k+1)}(y_{1:k},v)-Q^{(k+1)}(y_{1:k},v)\right| = 2\delta(k+1). \end{aligned}

Similarly, block mismatch caps survival: with the conditional kernels defined along a path, the probability that all kk sequential checks accept is

sk=∑y1:k∏j=1kmin⁡{pj(yj∣y<j),qj(yj∣y<j)}≤1−δ(k),(21)s_k = \sum_{y_{1:k}}\prod_{j=1}^{k}\min\{p_j(y_j\mid y_{<j}),q_j(y_j\mid y_{<j})\}\le1-\delta(k), \tag*{(21)}

since each product of minima is at most the minimum of the two products.

Example 1 (Perfect marginals, bounded gain). Let the target draw one fair bit BB and repeat it. Yj=BY_j=B for all jj, so P(k)(0k)=P(k)(1k)=1/2P^{(k)}(0^k)=P^{(k)}(1^k)=1/2. Independent heads with exact marginals draw a fresh fair bit at each position, so Q(k)(y1:k)=2−kQ^{(k)}(y_{1:k})=2^{-k}. Then

δ(k)=1−21−k,DKL(P(k)∥Q(k))=(k−1)log⁡2.\delta(k)=1-2^{1-k},\qquad D_{\mathrm{KL}}(P^{(k)}\mathbin\Vert Q^{(k)})=(k-1)\log2.

The first proposal is always accepted. Given that the prefixes have been accepted, each later target conditional is a point mass at the first bit while the proposal is uniform, so each later position is accepted with probability 1/21/2. Therefore, we have that sj=21−js_j=2^{1-j}, and G(k)=1+∑j=1k21−j=3−21−k<3G(k)=1+\sum_{j=1}^{k}2^{1-j}=3-2^{1-k}<3, showing that exact marginals can coexist with block mismatch approaching 11 and an expected gain that never reaches 33 tokens, no matter how long the draft.

Proofs of the Efficiency Guarantees

This section proves the results stated in the main text, in the order they appear. Throughout, write Et=ℓt(θt)−ℓtBE_t=\ell_t(\theta_t)-\ell_t^{B} and b^t,r=b^θt,t,r\widehat{b}_{t,r}=\widehat{b}_{\theta_t,t,r}. Then, by Lemma 1, we have ∑t=1TEt=RT+AT\sum_{t=1}^{T}E_t=R_T+A_T.

Predictor class. We use an affine forecaster b^θ,t,j=⟨θ,xt,j⟩\widehat{b}_{\theta,t,j}=\langle\theta,x_{t,j}\rangle. For instance, consider simplex weights θ\theta and features xt,j∈[0,1]dx_{t,j}\in[0,1]^d: here, the loss is convex in θ\theta and the forecasts stay in [0,1][0,1].

Proof of Lemma 1. Write et,j(Y<j)−b^θ,t,j=(et,j(Y<j)−ht,j)+(ht,j−b^θ,t,j)e_{t,j}(Y_{<j})-\widehat{b}_{\theta,t,j}=(e_{t,j}(Y_{<j})-h_{t,j})+(h_{t,j}-\widehat{b}_{\theta,t,j}) and expand each square. By the definition of the hazard equation 4, the cross term vanishes:

EQt[Wt,j−1(et,j(Y<j)−ht,j)]=0.\mathbb{E}_{Q_t}\left[W_{t,j-1}\left(e_{t,j}(Y_{<j})-h_{t,j}\right)\right]=0.

The first square summed over jj is ℓtB\ell_t^B, and the second is multiplied by EQt[Wt,j−1]=st,j−1\mathbb{E}_{Q_t}[W_{t,j-1}]=s_{t,j-1}.

Proof of Theorem 1. First, telescoping the survival products gives

s^t,j−st,j=∑r=1jst,r−1(ht,r−h^t,r)∏u=r+1j(1−h^t,u).\widehat{s}_{t,j}-s_{t,j}=\sum_{r=1}^{j}s_{t,r-1}\left(h_{t,r}-\widehat{h}_{t,r}\right)\prod_{u=r+1}^{j}\left(1-\widehat{h}_{t,u}\right).

Every factor in the product lies in [0,1][0,1], so summing over j≤kj\le k, applying Cauchy–Schwarz, and using st,r−1≤1s_{t,r-1}\le1 and Lemma 1,

∣G^t(k)−Gt(k)∣≤∑r=1k(k−r+1)st,r−1∣h^t,r−ht,r∣≤(∑r=1k(k−r+1)2st,r−1)1/2(∑r=1kst,r−1(h^t,r−ht,r)2)1/2≤k(k+1)(2k+1)6Et.(22)\begin{aligned} \left|\widehat{G}_t(k)-G_t(k)\right| &\le\sum_{r=1}^{k}(k-r+1)s_{t,r-1}\left|\widehat{h}_{t,r}-h_{t,r}\right|\\ &\le\left(\sum_{r=1}^{k}(k-r+1)^2s_{t,r-1}\right)^{1/2}\left(\sum_{r=1}^{k}s_{t,r-1}\left(\widehat{h}_{t,r}-h_{t,r}\right)^2\right)^{1/2}\\ &\le\sqrt{\frac{k(k+1)(2k+1)}{6}}\sqrt{E_t}. \tag*{(22)} \end{aligned}

Dividing by Ct(k)≥cmin⁡C_t(k)\ge c_{\min} and using k≤Kk\le K gives max⁡k∣R^t(k)−Rt(k)∣≤ΛKEt\max_k|\widehat{R}_t(k)-R_t(k)|\le\Lambda_K\sqrt{E_t}. Combining this with the selection rule in equation 12 gives

Rt(kt∗)−Rt(kt)≤[Rt(kt∗)−R^t(kt∗)]+[R^t(kt∗)−R^t(kt)]+[R^t(kt)−Rt(kt)]≤2ΛKEt+ξt.R_t(k_t^*)-R_t(k_t)\le[R_t(k_t^*)-\widehat{R}_t(k_t^*)]+[\widehat{R}_t(k_t^*)-\widehat{R}_t(k_t)]+[\widehat{R}_t(k_t)-R_t(k_t)]\le2\Lambda_K\sqrt{E_t}+\xi_t.

Then, by Cauchy–Schwarz, we have ∑t=1TEt≤T∑tEt=T(RT+AT)\sum_{t=1}^{T}\sqrt{E_t}\le\sqrt{T\sum_t E_t}=\sqrt{T(R_T+A_T)}.

A general projected-OGD bound. Both learning corollaries follow from the standard projected-OGD argument ([40]) with a moving comparator and stochastic gradients.

Lemma 2 (Projected OGD with a moving comparator). Let Θ\Theta be a nonempty closed convex set of diameter at most DD, let θ1∈Θ\theta_1\in\Theta, and let each ℓt\ell_t be convex and differentiable on Θ\Theta. Suppose θt+1=ΠΘ(θt−ηgt)\theta_{t+1}=\Pi_\Theta(\theta_t-\eta g_t) with E[gt∣Ft]=∇ℓt(θt)\mathbb{E}[g_t\mid\mathcal{F}_t]=\nabla\ell_t(\theta_t) and E[∥gt∥22∣Ft]≤M2\mathbb{E}[\lVert g_t\rVert_2^2\mid\mathcal{F}_t]\le M^2. Let θt∗∈Θ\theta_t^*\in\Theta be Ft\mathcal{F}_t-measurable with ∑t<T∥θt+1∗−θt∗∥2≤PT\sum_{t<T}\lVert\theta_{t+1}^*-\theta_t^*\rVert_2\le P_T almost surely, for a deterministic PTP_T. Then

ERT≤D2+2DPT2η+ηM2T2.(23)\mathbb{E}R_T\le\frac{D^2+2DP_T}{2\eta}+\frac{\eta M^2T}{2}. \tag*{(23)}

With η=D2+2DPTM2T\eta= \sqrt{\frac{D^2+2DP_T}{M^2T}} in the nondegenerate case, Theorem 1 and Jensen’s inequality give

EDT≤2ΛKT(MT(D2+2DPT)+EAT)+E∑t=1Tξt.(24)\mathbb{E}D_T \le2\Lambda_K\sqrt{T\left(M\sqrt{T(D^2+2DP_T)}+\mathbb{E}A_T\right)}+\mathbb{E}\sum_{t=1}^{T}\xi_t. \tag*{(24)}

Proof. Nonexpansiveness of the projection gives

⟨gt,θt−θt⋆⟩≤∥θt−θt⋆∥22−∥θt+1−θt⋆∥222η+η2∥gt∥22.\langle g_t,\theta_t-\theta_t^\star\rangle\le\frac{\lVert\theta_t-\theta_t^\star\rVert_2^2-\lVert\theta_{t+1}-\theta_t^\star\rVert_2^2}{2\eta}+\frac{\eta}{2}\lVert g_t\rVert_2^2.

By convexity and conditional unbiasedness, the expectation of the left-hand side is at least E[ℓt(θt)−ℓt(θt⋆)]\mathbb{E}[\ell_t(\theta_t)-\ell_t(\theta_t^\star)]. To telescope against a moving comparator, we use

∥θt+1−θt+1⋆∥22−∥θt+1−θt⋆∥22≤2D∥θt+1⋆−θt⋆∥2.\lVert\theta_{t+1}-\theta_{t+1}^\star\rVert_2^2-\lVert\theta_{t+1}-\theta_t^\star\rVert_2^2\le2D\lVert\theta_{t+1}^\star-\theta_t^\star\rVert_2.

Summing over tt proves equation (23). Substituting the chosen η\eta gives ERT≤MT(D2+2DPT)\mathbb{E}R_T\le M\sqrt{T(D^2+2DP_T)}, and equation (24) follows from Theorem 1 and Jensen’s inequality. □\square

Proof of Corollary 1 (full feedback). Here, gt=−2∑j=1KWt,j−1(et,jobs−⟨θt,xt,j⟩)xt,jg_t=-2\sum_{j=1}^{K}W_{t,j-1}(e_{t,j}^{\mathrm{obs}}-\langle\theta_t,x_{t,j}\rangle)x_{t,j} is unbiased for ∇ℓt(θt)\nabla\ell_t(\theta_t), and since Wt,j−1≤1W_{t,j-1}\le1, ∣et,jobs−h^t,j∣≤1\lvert e_{t,j}^{\mathrm{obs}}-\hat{h}_{t,j}\rvert\le1 and ∥xt,j∥2≤F\lVert x_{t,j}\rVert_2\le F, we have ∥gt∥2≤2FK\lVert g_t\rVert_2\le2FK. Apply Lemma 2 with M=2FKM=2FK and ξt=0\xi_t=0. Under realizability, EDT=O(T3/4(1+PT)1/4)\mathbb{E}D_T=O(T^{3/4}(1+P_T)^{1/4}) for fixed KK, cmin⁡c_{\min}, DD, FF. □\square

Proof of Corollary 2 (partial feedback). Unbiased loss and gradient. Fix θ\theta. Because the exploration coin is independent of the draft given Ft\mathcal{F}_t, for each position

E[1{kt≥j}πt,jWt,j−1(et,jobs−h^θ,t,j)2∣Ft]=EQt[Wt,j−1(et,j(Y<j)−h^θ,t,j)2].\mathbb{E}\left[\left.\frac{\mathbf{1}\{k_t\ge j\}}{\pi_{t,j}}W_{t,j-1}(e_{t,j}^{\mathrm{obs}}-\hat{h}_{\theta,t,j})^2\right|\mathcal{F}_t\right]=\mathbb{E}_{Q_t}\left[W_{t,j-1}(e_{t,j}(Y_{<j})-\hat{h}_{\theta,t,j})^2\right].

This discrepancy is needed only when the indicator is one. Summing over jj shows that the observed loss is conditionally unbiased, and differentiating shows this for the gradient of the affine predictor.

Second moment. Using ∥∑j=1Kvj∥22≤K∑j=1K∥vj∥22\left\lVert\sum_{j=1}^{K}v_j\right\rVert_2^2\le K\sum_{j=1}^{K}\lVert v_j\rVert_2^2, Wt,j−1≤1W_{t,j-1}\le1 and E[1{kt≥j}∣Ft]=πt,j\mathbb{E}[\mathbf{1}\{k_t\ge j\}\mid\mathcal{F}_t]=\pi_{t,j},

E[∥gt∥22∣Ft]≤4F2K∑j=1K1πt,j≤4F2K2ε.\mathbb{E}[\lVert g_t\rVert_2^2\mid\mathcal{F}_t]\le4F^2K\sum_{j=1}^{K}\frac{1}{\pi_{t,j}}\le\frac{4F^2K^2}{\varepsilon}.

Substituting M2=4F2K2/εM^2=4F^2K^2/\varepsilon into equation (23) gives the regression bound.

Selection error. On a greedy round ξt=0\xi_t=0. On an exploration round, ξt=max⁡kR^t(k)−R^t(K)≤(K+1)/cmin⁡\xi_t=\max_k\widehat{R}_t(k)-\widehat{R}_t(K)\le(K+1)/c_{\min}, so E∑tξt≤εT(K+1)/cmin⁡\mathbb{E}\sum_t\xi_t\le\varepsilon T(K+1)/c_{\min}. Combining these bounds gives the final rates. □\square

Proof of Corollary 3. Let Δt=Rt(kt⋆)−Rt(kt)≥0\Delta_t=R_t(k_t^\star)-R_t(k_t)\ge0. Since Rt(kt⋆)≥ρR_t(k_t^\star)\ge\rho and Ct(kt)≤cmax⁡C_t(k_t)\le c_{\max},

Gt(kt)=Ct(kt)(Rt(kt⋆)−Δt)≥ρCt(kt)−cmax⁡Δt.G_t(k_t)=C_t(k_t)(R_t(k_t^\star)-\Delta_t)\ge\rho C_t(k_t)-c_{\max}\Delta_t.

Every round commits at least one token, so σN≤N\sigma_N\le N, and the last round overshoots the budget by at most KK tokens: N≤∑t=1σNLt≤N+KN\le\sum_{t=1}^{\sigma_N}L_t\le N+K. The event {σN≥t}\{\sigma_N\ge t\} is determined before round tt, so taking conditional expectations round by round and summing gives

ρEJN≤E∑t=1σNLt+cmax⁡E∑t=1σNΔt≤N+K+cmax⁡EDN.\rho\mathbb{E}J_N\le\mathbb{E}\sum_{t=1}^{\sigma_N}L_t+c_{\max}\mathbb{E}\sum_{t=1}^{\sigma_N}\Delta_t\le N+K+c_{\max}\mathbb{E}D_N.

where the last step uses σN≤N\sigma_N\le N and Δt≥0\Delta_t\ge0. Dividing by ρ\rho gives the completion-time bound, and dividing the baseline’s expected completion time by it gives the speedup bound. □\square

The square-root dependence is tight. The transfer in Theorem 1 scales with the square root of the excess loss. The next result shows that this cannot be improved for the forecast-greedy controller, even with independent heads, known costs and K=2K=2.

Proposition 2. (Square-root dependence is unavoidable.) For every δ∈(0,1/2)\delta\in(0,1/2) there is an exact speculative-decoding instance with K=2K=2, costs C(1)=1C(1)=1 and C(2)=5/4C(2)=5/4, and a pre-draft hazard forecast with excess loss E=4δ2E=4\delta^2, such that forecast-greedy selection incurs

R(k⋆)−R(k^)=25E.(25)R(k^\star)-R(\widehat{k})=\frac{2}{5}\sqrt{E}. \tag*{(25)}

Repeating the construction over TT rounds gives

DT=25T∑t=1TEt.(26)D_T=\frac{2}{5}\sqrt{T\sum_{t=1}^{T}E_t}. \tag*{(26)}

Hence no uniform o(E)o(\sqrt{E}) one-round bound holds under the assumptions of the transfer theorem.

Proof. Instance. Take the vocabulary {0,1}\{0,1\} and a target that emits 0 with probability one after every prefix. The independent proposal heads are q1(0)=1q_1(0)=1 and q2(0)=1/2+δq_2(0)=1/2+\delta. The first token is always accepted, so W1=1W_1=1 and e1=h1=0e_1=h_1=0. At the second position e2=TV⁡(p2,q2)=1/2−δe_2=\operatorname{TV}(p_2,q_2)=1/2-\delta: a proposed 0 is always accepted and a proposed 1 always rejected, and both the correction and the bonus token are 0. Hence h2=1/2−δh_2=1/2-\delta, s1=1s_1=1 and s2=1/2+δs_2=1/2+\delta.

Forecast and excess loss. Take h^1=0\widehat{h}_1=0 and h^2=1/2+δ\widehat{h}_2=1/2+\delta. The discrepancies are deterministic and W0=W1=1W_0=W_1=1, so ℓ(h^)=(2δ)2=4δ2\ell(\widehat{h})=(2\delta)^2=4\delta^2 and ℓB=0\ell^B=0, giving E=4δ2E=4\delta^2. Both the forecast and the true hazards lie in the affine class h^θ,j=θj\widehat{h}_{\theta,j}=\theta_j on Θ=[0,1]2\Theta=[0,1]^2.

Regret. Counting the correction or bonus token, G(1)=G^(1)=2G(1)=\widehat{G}(1)=2, G(2)=5/2+δG(2)=5/2+\delta and G^(2)=5/2−δ\widehat{G}(2)=5/2-\delta. With the stated costs, R(1)=R^(1)=2R(1)=\widehat{R}(1)=2, R(2)=2+4δ/5R(2)=2+4\delta/5 and R^(2)=2−4δ/5\widehat{R}(2)=2-4\delta/5. So k⋆=2k^\star=2 and k^=1\widehat{k}=1 are unique, and the regret is 4δ/5=(2/5)E4\delta/5=(2/5)\sqrt{E}. Since KK and the costs stay fixed as δ↓0\delta\downarrow0, no bound of the form o(E)o(\sqrt{E}), and in particular none of the form cEcE, can hold uniformly.

Many rounds. Use the same models, costs and forecasts at every round. All committed tokens are 0 and the models ignore the history, so these are consistent rounds of one decoding process, with Et=4δ2E_t=4\delta^2 and DT=4Tδ/5=(2/5)T∑EtD_T=4T\delta/5=(2/5)\sqrt{T\sum E_t}.

The construction above places the two horizons arbitrarily close to a decision boundary. When every suboptimal horizon is separated from the best one, the transfer becomes linear in the excess loss.

Proposition 3. (Transfer under a throughput gap.) Under the known-cost assumptions of Theorem 1, suppose ∃γ>0\exists\gamma>0 such that Rt(kt⋆)−Rt(k)∈{0}∪[γ,∞)R_t(k_t^\star)-R_t(k)\in\{0\}\cup[\gamma,\infty) for every round tt and horizon kk. Then

DT≤4ΛK2γ(RT+AT)+2∑t=1Tξt.D_T\leq\frac{4\Lambda_K^2}{\gamma}(\mathcal{R}_T+\mathcal{A}_T)+2\sum_{t=1}^{T}\xi_t.

Proof. Let Δt=Rt(kt⋆)−Rt(kt)\Delta_t=R_t(k_t^\star)-R_t(k_t) and dt=ΛKEtd_t=\Lambda_K\sqrt{E_t}. Step 2 of the proof of Theorem 1 gives Δt≤2dt+ξt\Delta_t\leq2d_t+\xi_t. If Δt=0\Delta_t=0 there is nothing to prove. Otherwise Δt≥γ\Delta_t\geq\gamma, and Young’s inequality 2dt≤Δt/2+2dt2/Δt2d_t\leq\Delta_t/2+2d_t^2/\Delta_t gives, after rearranging,

Δt≤4dt2Δt+2ξt≤4ΛK2γEt+2ξt.\Delta_t\leq\frac{4d_t^2}{\Delta_t}+2\xi_t\leq\frac{4\Lambda_K^2}{\gamma}E_t+2\xi_t.

Summing over tt completes the proof.

Predicting survival directly. Hazards are one way to parameterize acceptance survival. The same verification feedback also supports predicting st,js_{t,j} directly, using either of the labels

Zt,j=Wt,j,Zt,jRB=Wt,j−1(1−et,jobs).(27)Z_{t,j}=W_{t,j},\qquad Z^{\mathrm{RB}}_{t,j}=W_{t,j-1}(1-e^{\mathrm{obs}}_{t,j}). \tag*{(27)}

Both have conditional mean st,js_{t,j} given Ft\mathcal{F}_t. The second equals E[Wt,j∣Ft,Y≤j]\mathbb{E}[W_{t,j}\mid\mathcal{F}_t,Y_{\leq j}]: it integrates out the current proposed token, so it is a Rao–Blackwellization of the first and has no larger conditional variance. Both are available at every drafted position under the feedback assumptions of § 4.

Let s^ψ,t,j\widehat{s}_{\psi,t,j} be a pre-draft survival forecast, let ζt,j\zeta_{t,j} be either label, and define ℓtS(ψ)=EQ[∑j=1K(ζt,j−s^ψ,t,j)2]\ell_t^S(\psi)=\mathbb{E}_Q\left[\sum_{j=1}^{K}(\zeta_{t,j}-\widehat{s}_{\psi,t,j})^2\right]. As in Lemma 1, its excess loss is

EtS(ψ):=ℓtS(ψ)−ℓtS,B=∑j=1K(s^ψ,t,j−st,j)2.(28)E_t^S(\psi):=\ell_t^S(\psi)-\ell_t^{S,B}=\sum_{j=1}^{K}(\widehat{s}_{\psi,t,j}-s_{t,j})^2. \tag*{(28)}

With the same exploration scheme, the observed loss ℓ^tS(ψ)=∑j=1kt(ζt,j−s^ψ,t,j)2/πt,j\widehat{\ell}_t^S(\psi)=\sum_{j=1}^{k_t}(\zeta_{t,j}-\widehat{s}_{\psi,t,j})^2/\pi_{t,j} is conditionally unbiased. With G^tS(k)=1+∑j=1ks^ψt,t,j\widehat{G}_t^S(k)=1+\sum_{j=1}^{k}\widehat{s}_{\psi_t,t,j}, Cauchy–Schwarz gives

∣G^tS(k)−Gt(k)∣≤kEtS(ψt),(29)\left|\widehat{G}_t^S(k)-G_t(k)\right|\le\sqrt{k}\sqrt{E_t^S(\psi_t)}, \tag*{(29)}

so with known costs the one-round throughput regret is at most 2KEtS(ψt)/cmin⁡+ξt2\sqrt{K E_t^S(\psi_t)}/c_{\min}+\xi_t.

Round Costs and Measured Throughput

The marginal value of an extra position makes the tradeoff explicit. If ΔCt(k)=Ct(k+1)−Ct(k)≥0\Delta C_t(k)=C_t(k+1)-C_t(k)\ge0, then

Rt(k+1)≥Rt(k)⟺st,k+1≥Rt(k)ΔCt(k).(30)R_t(k+1)\ge R_t(k)\quad\Longleftrightarrow\quad s_{t,k+1}\ge R_t(k)\Delta C_t(k). \tag*{(30)}

The gain in expected committed tokens must cover the extra round cost. This comparison is local; the controller scores every candidate and does not assume that Rt(k)R_t(k) is unimodal.

Estimated latency costs. Write Et=Et(θt)E_t=E_t(\theta_t) as in equation (9). If the controller instead uses R^t(k)=G^t(k)/C^t(k)\widehat{R}_t(k)=\widehat{G}_t(k)/\widehat{C}_t(k), assume C^t(k)≥cmin⁡\widehat{C}_t(k)\ge c_{\min} and define

δtC=max⁡1≤k≤K∣C^t(k)−Ct(k)∣.\delta_t^C=\max_{1\le k\le K}\left|\widehat{C}_t(k)-C_t(k)\right|.

Then

max⁡k∣R^t(k)−Rt(k)∣≤ΛKEt+K+1cmin⁡2δtC.\max_k\left|\widehat{R}_t(k)-R_t(k)\right|\le\Lambda_K\sqrt{E_t}+\frac{K+1}{c_{\min}^2}\delta_t^C.

Thus Theorem 1 becomes

DT≤2ΛKT(RT+AT)+2(K+1)cmin⁡2∑t=1TδtC+∑t=1Tξt,D_T\le2\Lambda_K\sqrt{T(R_T+A_T)}+\frac{2(K+1)}{c_{\min}^2}\sum_{t=1}^{T}\delta_t^C+\sum_{t=1}^{T}\xi_t,

where ξt\xi_t is now defined relative to the estimated-cost objective.

Connection to measured acceptance. Over TT complete rounds, define the pooled draft acceptance rate, average window length, and average realized round cost by

a^T=∑t=1TAt(kt)∑t=1Tkt,k‾T=1T∑t=1Tkt,c‾T=1T∑t=1Tct.\widehat{a}_T=\frac{\sum_{t=1}^{T}A_t(k_t)}{\sum_{t=1}^{T}k_t},\qquad\overline{k}_T=\frac{1}{T}\sum_{t=1}^{T}k_t,\qquad\overline{c}_T=\frac{1}{T}\sum_{t=1}^{T}c_t.

Since Lt=1+At(kt)L_t=1+A_t(k_t), the measured throughput satisfies the exact identity

∑t=1TLt∑t=1Tct=1+a^Tk‾Tc‾T.(31)\frac{\sum_{t=1}^{T}L_t}{\sum_{t=1}^{T}c_t}=\frac{1+\widehat{a}_T\overline{k}_T}{\overline{c}_T}. \tag*{(31)}

Consequently, acceptance improvements translate into throughput improvements through both the average window length and the round cost. Acceptance alone is insufficient: for a fixed context and draft law,

E[At(k)∣Ft]k=1k∑j=1kst,j\frac{\mathbb{E}[A_t(k)\mid\mathcal{F}_t]}{k}=\frac{1}{k}\sum_{j=1}^{k}s_{t,j}

is nonincreasing in kk, so shortening the window increases acceptance without increasing throughput.

The identity in equation (31) applies to complete rounds under the one-correction-or-bonus convention. An output cutoff or early end-of-sequence token requires recording the actual committed count; the pooled identity should not be applied blindly to such truncated rounds.

Experimental Setup and Further Results

This section describes our experimental setup and provides further results. We use the following checkpoints that can be found on HuggingFace:

  1. jwkirchenbauer/Qwen3-4B-Inst-2507-MTP,

  2. facebook/multi-token-prediction (7B_1T_4),

  3. meta-llama/Llama-3.1-8B-Instruct with Medusa heads,

  4. Qwen/Qwen3-14B,

  5. meta-llama/Llama-2-\{7b, 13b\}-hf.

Hardware and Software. Self-distilled Qwen3-4B, its Qwen3-14B cross-model pairing and Medusa runs use a NVIDIA H100 on a university SLURM cluster; Meta MTP runs use a single NVIDIA H100 SXM on a rented cloud pod. Every run occupies one GPU exclusively and processes one sample at a time, so measured wall time is not distorted by co-located jobs. Throughput is therefore comparable between conditions on the same hardware but not across the two hardware groups. Models are loaded in the checkpoint’s native precision through Hugging Face transformers; evaluations are driven by Inspect AI, using a custom model provider that wraps our speculative-decoding engine. The exact package versions are pinned in the released code’s lock file.

Tasks and Caps. AIME 2025 uses all 30 problems with a limit of 1,000 verification rounds and 3,000 generated tokens per problem. GSM8K uses the standard ten-shot prompt (fixed few-shot seed) with a limit of 300 rounds per problem for the speculative conditions. The self-distilled runs (self-speculative and paired with the Qwen3-14B target) use all 1,319 test problems; the Medusa runs use the first 250. The Meta MTP checkpoints are base models that do not emit an end-of-sequence token after answering, so they generate until the round cap; for the Meta 13B pair on GSM8K we therefore cap each of the first 100 problems at 100 rounds (300 tokens for plain decoding) and use identical caps across conditions, and we re-analyze the earlier 300-round Meta 7B fixed run on the same prefix. These runs measure throughput and acceptance only, since a 7–13B base model’s GSM8K accuracy is not a meaningful check of lossless decoding. The Qwen3-14B plain-decoding baseline for the self-distilled cross-model pairing reached 1,166 of 1,319 GSM8K problems before its time limit; its throughput and accuracy are computed over that completed subset, and the fixed and adaptive conditions for this pairing still cover all 1,319. Sampling draws from the unmodified softmax of each model (no temperature scaling), without a fixed random seed, so runs are not bit-for-bit repeatable.

Metrics. For a run with rounds t=1,…,Tt = 1, \ldots, T, let ctc_t be the number of tokens committed in round tt (accepted drafts plus the one token sampled from the target), ktk_t the window used, and τt\tau_t the measured wall time of the round, including drafting, verification and synchronization.

tokens/round=1T∑tct,acceptance rate=∑t(ct−1)∑tkt,throughput (tok/s)=∑tct∑tτt,speed-up=throughputthroughput of plain decoding.\begin{aligned} \text{tokens/round} &= \frac{1}{T}\sum_t c_t, &\qquad\text{acceptance rate} &= \frac{\sum_t(c_t-1)}{\sum_t k_t}, \\ \text{throughput (tok/s)} &= \frac{\sum_t c_t}{\sum_t \tau_t}, &\qquad\text{speed-up} &= \frac{\text{throughput}}{\text{throughput of plain decoding}}. \end{aligned}

For plain next-token decoding, a round produces exactly one token (ct=1c_t=1, no drafting). Sums run over all problems of an evaluation, so throughput is a token-weighted, not a per-problem, average. We report accuracy from the task’s own scorer.

Baselines. Plain decoding uses the same target model and prompt with the standard autoregressive loop, also without a KV-cache, so speed-ups isolate the effect of speculation. For the self-speculative pairings (self-distilled Qwen3-4B, Medusa on Llama-3.1-8B-Instruct) the plain-decoding baseline is the same checkpoint decoding without drafting. Meta’s 7B multi-token-prediction checkpoint has no separately released plain next-token model, so its plain-decoding baseline is Llama-2-7B, the base architecture it was fine-tuned from; for the 13B pairing, the target itself, Llama-2-13B, is the baseline. For the self-distilled cross-model pairing, the baseline is the target alone, Qwen3-14B.

Draft-Model Implementations

All draft models implement one interface: given the current context, return kk sampled tokens together with the kk distributions they were sampled from. The engine is agnostic to how the draft produces them, so AMTP and the verification step are shared across families.

Self-speculative and cross-model pairings. In a self-speculative pairing the same weights draft and verify and are loaded once. In a cross-model pairing a small multi-token-prediction draft proposes tokens for a larger target of the same vocabulary: self-distilled Qwen3-4B for Qwen3-14B, and Meta’s 7B multi-token-prediction model for Llama-2-13B. The engine checks that the draft and target share a tokenizer and vocabulary; the self-distilled model declares extra mask tokens.

Self-distilled Qwen3-4B (mask-token drafting). The checkpoint drafts kk tokens in one forward pass by appending k−1k-1 reserved mask tokens (ids 151669–151700) to the context and reading the logits at the last real position and at each mask position. It supports k≤16k \le16. It ships without its own verification scheme, so verification is performed by our engine with the standard accept/reject rule.

Meta MTP (independent parallel heads). The 7B checkpoint has four output heads that read the trunk’s final hidden state and predict tokens t+1,…,t+4t+1,\ldots,t+4 independently. The checkpoint is not in Hugging Face format, so we load it with a self-contained implementation (transformer trunk, four heads, SentencePiece tokenizer). A single trunk forward produces all 4 distributions.

Medusa on Llama-3.1-8B-Instruct. Six residual-block heads, each with its own output projection, predict from the last hidden state of the base model. The base model’s own next-token distribution supplies position one; head ii then predicts position i+2i+2. Head weights are loaded from a separate repository, and the base model is the unmodified instruct checkpoint.

No KV-cache. All runs recompute the full context on every forward pass. This makes per-round cost depend visibly on context length, which AMTP’s cost model represents (Appendix D.2), and it removes cache-rollback logic that differs between attention variants and would confound the comparison across draft families. Absolute throughput is consequently lower than with an optimised cached implementation; the relative comparisons between conditions are what we report.

Adaptive Multi-Token Prediction Details

Hazard targets. The hazard label at drafted position jj is TV⁡(pj,qj)=1−∑vmin⁡(pj(v),qj(v))\operatorname{TV}(p_j,q_j)=1-\sum_v\min(p_j(v),q_j(v)), the probability that a token drawn from pjp_j is rejected. It is computed for every drafted position, including those after the first rejection, via the target distributions already produced by the verification.

Cost target. The cost model is fitted to the whole round’s measured wall time, as AMTP’s decision only needs the total. Since every run disables the KV-cache (Appendix § 13.§ 1), the cost model includes context length as a feature alongside the window kk; a model fit with context length excluded explains almost none of the round-to-round cost variance under this setting.

Checkpoint lineage. Control-block state is saved every 50 updates under a key made of the draft checkpoint, target checkpoint and an implementation tag. The tag changes whenever the cost regime changes, and the current tag identifies runs without a key–value cache and with the rescaled cost model, so weights fitted under a different regime are never loaded.

Start-up. For the first 20 updates the window is drawn with probability proportional to 1/(nk+1)1/(n_k+1), so the cost model observes several window sizes. All conditions labelled “adaptive” begin with this phase; the numbers we report include it.

Complete Results

Tables 7 and 8 list our final results behind the main-text tables, and Table 6 gives the distribution of windows chosen by AMTP. Tables 1–3 in the main text are derived from the same records.

Model / evalk=1k=12345–6≥7\ge7
Meta MTP 7B, AIME1.47.327.064.30.00.0
Meta MTP 13B, AIME9.524.629.536.50.00.0
Meta MTP 7B, GSM8K*0.31.419.079.20.00.0
Meta MTP 13B, GSM8K*0.52.916.779.90.00.0
Medusa 8B, GSM8K0.14.729.243.522.50.0
Self-dist. 4B, GSM8K0.00.00.00.22.996.9
Self-dist. 4B → 14B, AIME0.31.14.710.429.753.8
Self-dist. 4B → 14B, GSM8K0.00.00.20.64.095.1

Table 6. Share of verification rounds (%) in which the control block chose each window size, over the full round population. The distribution is wide for every model, and the mode differs by model and by task. *Capped runs (first 100 problems, first 100 rounds).

Draft → targetConditionRoundsTok./roundAccept. (%)Tok./sGen. (h)Acc. (%)
Self-dist. Qwen3-4BPlain81,7911.00–18.81.2120.0
Self-dist. Qwen3-4BFixed k=16k=1625,5493.8417.734.00.8030.0
Self-dist. Qwen3-4BAdaptive25,9273.8333.934.50.8026.7
Self-dist. 4B → Qwen3-14BQwen3-14B60,0911.00–10.41.6120.0
Self-dist. 4B → Qwen3-14BFixed k=16k=1618,2443.2314.022.50.7320.0
Self-dist. 4B → Qwen3-14BAdaptive16,5253.2028.224.70.6023.3
Meta MTP 7BLlama-2-7B13,1901.00–12.50.290.0
Meta MTP 7BFixed k=4k=47,0093.0050.037.70.160.0
Meta MTP 7BAdaptive11,2683.0357.231.90.300.0
Meta MTP 7B → Llama-2-13BLlama-2-13B14,3091.00–6.20.640.0
Meta MTP 7B → Llama-2-13BFixed k=4k=45,3702.7643.97.60.540.0
Meta MTP 7B → Llama-2-13BAdaptive2,7722.5151.628.20.070.0
Medusa Llama-3.1-8BPlain53,2941.00–7.51.970.0
Medusa Llama-3.1-8BFixed k=6k=619,7602.3422.423.60.550.0
Medusa Llama-3.1-8BAdaptive18,3952.2846.225.30.460.0

Table 7. AIME 2025 evaluations (n=30n=30 problems in each row). Rounds: total verification rounds over all problems (one round is one token for plain decoding). Tok./s: total committed tokens per total measured round wall time. Gen. (h): summed round wall time. Acc.: fraction of problems answered correctly; it is 0 for every 7–13B model (Meta and Llama), so it carries no signal there.

Worked Examples. We provide real unedited excerpts from logged telemetry of a self-distilled Qwen3-4B adaptive run on AIME 2025: *Let A be the set of positive integer divisors of 2025. Let B be a randomly selected subset of A. The probability that B is a nonempty set with the property that the least common multiple of its elements is 2025 is mn\frac{m}{n}, where mm and nn are relatively prime positive integers. Find m+nm+n.

Draft → targetConditionProblemsRoundsTok./roundAccept. (%)Tok./sGen. (h)Acc. (%)
Self-dist. Qwen3-4BPlain1319279,0501.00–16.24.8089.4
Fixed k=16k=16131964,0084.6723.038.62.1585.0
Adaptive131965,1834.6332.438.32.1985.7
Self-dist. 4B → Qwen3-14B†Qwen3-14B†1166179,7201.00–6.47.8092.8
Fixed k=16k=16131947,6434.3320.821.32.6992.9
Adaptive131947,5294.3328.521.52.6693.5
Meta MTP 7B*Llama-2-7B10024,4401.00–4.71.44–
Fixed k=4k=41008,9133.1854.519.20.41–
Adaptive1009,0653.2158.619.40.42–
Meta MTP 7B → Llama-2-13B*Llama-2-13B10023,6601.00–2.72.46–
Fixed k=4k=41008,1082.7242.94.71.31–
Adaptive1008,2062.7546.611.60.54–
Medusa Llama-3.1-8BPlain25044,8771.00–13.00.9683.2
Fixed k=6k=625015,6192.9933.120.00.6579.6
Adaptive25016,7392.9048.219.40.6979.2

Table 8. Complete GSM8K results. Self-distilled 4B and Qwen3-14B target rows use all 1,319 problems where finished; Medusa uses the first 250 problems; *Meta MTP runs are capped (first 100 problems, first 100 rounds; ∼300 tokens for plain decoding) because the Meta base models do not terminate after answering, so their scored accuracy (1–4%, driven almost entirely by truncation) is not meaningful and is omitted. †The Qwen3-14B plain run reached 1,166 of 1,319 problems before its time limit; its accuracy is over those completed problems.

Example 1: a difficult stretch, seven consecutive rounds. Roughly 650 verification rounds into its own generated solution, the model is deriving the number of qualifying subsets. Table 9 lists seven consecutive rounds verbatim. In each round the control block first chooses a window ktk_t from its own hazard forecast, then drafts exactly ktk_t tokens; the accepted column gives how many of those were accepted before the first rejection (or all ktk_t, if none were rejected), and correction gives the resampled token that replaced the first rejected draft token. Draft tokens past the rejection point are never verified and contribute nothing to the committed output.

The committed text across these seven rounds, concatenated, reads: “2768 - 4864 = 27904\n\nYes,\n\nSo, the number of nonempty subsets$ such that LCM” with those visible self-corrections (Yes, So) where the model’s own verification caught a drafted continuation it would not have produced itself. The chosen window swings from k_t=7totok_t=16$ round to round, and every round in this stretch needed at least one correction; this is a difficult patch of the derivation, not representative of the easier, longer-window stretches that dominate most of a generation.

Decoding throughput for AIME 2025 and GSM8K

(a) (a) Decoding throughput (tokens/second) for plain decoding, the best fixed window, and AMTP, across all five pairings and both evaluation tasks. Every multi-token-prediction condition beats plain decoding; the Meta MTP cross-model pairing (facebook/multi-token-prediction draft to Llama-2-13B target) shows the largest absolute gap between fixed and adaptive.

Throughput of AMTP relative to the best fixed window

(b) (b) Throughput of AMTP, relative to the best fixed window, self-speculative pairings and the modest-effect cross-model pairing (self-distilled 4B→14B).

Cross-model Meta MTP pairing

(c) (c) The cross-model Meta MTP pairing (draft/target cost asymmetry), shown on its own axis given the scale of the effect relative to every other condition.

Figure 4. Top: decoding throughput of plain decoding, the best fixed window and AMTP. Every multi-token-prediction condition is faster than plain decoding. Middle: throughput of AMTP relative to the best fixed window, for self-speculative pairings and the self-distilled cross-model pairing — effects are modest in both directions, within about 15% either way. Bottom: the Meta MTP cross-model pairing, shown separately because its gain (+268% AIME, +147% GSM8K) is an order of magnitude larger than every other condition — draft/target cost asymmetry combined with long, variable-length reasoning produces the largest effect in this validation.

Decoding trace — AIME 2025

Figure 5. Four consecutive real verification rounds (648–651) from one adaptive-control-block run on AIME 2025 (self-distilled Qwen3-4B). Green tokens were accepted, the red token was rejected and replaced by the correction shown on the right (resampled from the residual), and grey tokens were drafted but never verified because the round already stopped at the rejection. The control block re-selects the window ktk_t every round (shown on the left). All tokens, windows, and corrections are taken directly from logged telemetry.

Example 2: full acceptance with a bonus token. Later in the same run, round 101 is more typical of an easy stretch. The context ends “. . . we want to count”, following directly from the probability setup. The control block forecasts rejection hazards h^t,1=0.40\hat{h}_{t,1}=0.40, h^t,2=0.48\hat{h}_{t,2}=0.48, h^t,3=0.55\hat{h}_{t,3}=0.55 for the next three positions, giving a predicted gain G^t(3)≈1+0.60+0.31+0.14≈2.05\hat{G}_t(3) \approx1 + 0.60 + 0.31 + 0.14 \approx2.05 expected committed tokens, and the controller selects kt=3k_t=3. Table 10 lists the single round. Since the draft is verified in full with no rejection, the engine draws one additional bonus token directly from the target’s own distribution rather than discarding the round.

Roundktk_tDraftAcceptedBonus
1013▁the ▁number ▁of3/3 (all)▁non

Table 10. One real verification round (101) with full acceptance, from the same adaptive-control-block run as Table 9. The bonus token is sampled from the target’s distribution at the position immediately after the draft, since no rejection occurred.

Roundktk_tDraftAcceptedCorrection
648132 7 6 8 – _ 4 8 6 4 = _ 213/13 (all)—
649129 0 4 $ $ Yes But _ _ of _of4/12Yes
65014. _So , _$ _number _of 1 _subsets _subsets _with _is _** $ _elements1/14So
65114, _the _number $ _of _≤ $ _the 4 0 4 _with _^ \3/14_of
65216_non _with B B _have _B (S _are _2 0 ^ $ = 2 2 | 1/16 | empty
6538_subsets $ $ _⊂ CM _= _ 23/8$
6547_such _that _⊂ _⊂ _S $ | 3/7 | CM

Table 9. Seven consecutive real verification rounds (648–654) from one adaptive-control-block run. _ marks a leading space in a token; $ and \ are literal draft tokens (the model was mid-LaTeX). All data is taken directly from logged round telemetry.

The committed text for the round is therefore “ the number of non”, four tokens from a single target forward pass, with no correction needed.

References

  1. [1]Sudhanshu Agrawal, Wonseok Jeon, and Mingu Lee. AdaEDL: Early draft stopping for speculative decoding of large language models via an entropy-based lower bound on token acceptance probability. In Proceedings of the 4th NeurIPS Efficient Natural Language and Speech Processing Workshop, volume 262 of Proceedings of Machine Learning Research, 2024. URL https://proceedings.mlr.press/v262/agrawal24a.html.arxiv.org/abs/2410.18351
  2. [2]Kwangjun Ahn, Alex Lamb, and John Langford. Efficient joint prediction of multiple future tokens. arXiv preprint arXiv:2503.21801, 2025. URL https://arxiv.org/abs/2503.21801.
  3. [3]Emile Anand and Sarah Liaw. Feel-good Thompson sampling for contextual bandits: a Markov chain Monte Carlo showdown. In Advances in Neural Information Processing Systems, volume 38, 2025.arxiv.org/abs/2507.15290
  4. [4]Emile Anand, Abdullah Ateyeh, Archer Wang, and Marin Soljačić. Smat-attention: Structured long-context sequence modeling, 2026. URL https://arxiv.org/abs/2609.36062.
  5. [5]Zachary Ankner, Rishab Parthasarathy, Aniruddha Nrusimha, Christopher Rinard, Jonathan Ragan-Kelley, and William Brandon. Hydra: Sequentially-dependent draft heads for medusa decoding, 2024. URL https://arxiv.org/abs/2402.05109.
  6. [6]Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
  7. [7]Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, and Tri Dao. Medusa: Simple LLM inference acceleration framework with multiple decoding heads. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 5209–5235. PMLR, 2024. URL https://proceedings.mlr.press/v235/cai24i8.html.arxiv.org/abs/2401.10774
  8. [8]Carrie Chen. EntMTP: Accelerating LLM inference with entropy guided multi token prediction. arXiv preprint arXiv:2606.27550, 2026.arxiv.org/abs/2606.27550
  9. [9]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.01318, 2023. URL https://arxiv.org/abs/2302.01318.
  10. [10]Xin Cheng, Xingkai Yu, Chenze Shao, Jiashi Li, Yunfan Xiong, Yi Qian, Jiaqì Zhu, Shirong Ma, Xi-aokang Zhang, Jiasheng Ye, Qinyu Chen, Chengqi Deng, Jiping Yu, Damai Dai, Zhengyan Zhang, Yixuan Wei, Yixuan Tan, Wenkai Yang, Runxin Xu, Yu Wu, Zhean Xu, Xuanyu Wang, Muyang Chen, Rui Tian, Xiao Bi, Zhewen Hao, Shaoyuan Chen, Huangqi Cao, Wentao Zhang, Anyi Xu, Huishuai Zhang, Dongyan Zhao, and Wenfeng Liang. DSpark: Confidence-scheduled speculative decoding with semi-autoregressive generation. arXiv preprint arXiv:2607.05147, 2026. URL https://arxiv.org/abs/2607.05147.
  11. [11]Sai Sreenivas Chintha, Chidera Biringa, Rishab Sharma, Anusha Agrawal, Prachi Badarayani, Gemma Zhang, Nigel Boachie Kunkamunah, Marco Ayala, and Sulaiman Vesal. Next token or vector? learning how far to decode. arXiv preprint arXiv:2610.22788, 2026.arxiv.org/abs/2610.22788
  12. [12]DeepSeek-AI. DeepSeek-V3 technical report. arXiv preprint arXiv:2412.19437, 2024.arxiv.org/abs/2412.19437
  13. [14]Fabian Gloeckle, Badr Youbi Idrissi, Baptiste Rozière, David Lopez-Paz, and Gabriel Synnaeve. Better & faster large language models via multi-token prediction. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 15706–15734. PMLR, 2024. URL https://proceedings.mlr.press/v235/gloeckle24a.html.arxiv.org/abs/2404.19737
  14. [15]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3–4):157–325, 2016.
  15. [16]Yunlong Hou, Fengzhuo Zhang, Cunxiao Du, Xuan Zhang, Jiachun Pan, Tianyu Pang, Chao Du, Vincent Y. F. Tan, and Zhuoran Yang. BanditSpec: Adaptive speculative decoding via bandit algorithms. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, 2025. URL https://proceedings.mlr.press/v267/hou25h.html.
  16. [17]Kaixuan Huang, Xudong Guo, and Mengdi Wang. SpecDec++: Boosting speculative decoding via adaptive candidate lengths. arXiv preprint arXiv:2405.19715, 2024. URL https://arxiv.org/abs/2405.19715.
  17. [18]John Kirchenbauer, Abhimanyu Hans, Brian Bartoldson, Micah Goldblum, Ashwinee Panda, and Tom Goldstein. Multi-token prediction via self-distillation. arXiv preprint arXiv:2602.06019, 2026. URL https://arxiv.org/abs/2602.06019.
  18. [19]John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems, volume 20, 2007.
  19. [20]Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 19274–19286. PMLR, 2023. URL https://proceedings.mlr.press/v202/leviathan23a.html.
  20. [21]Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. EAGLE: Speculative sampling requires rethinking feature uncertainty. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 28528–28948. PMLR, 2024a. URL https://proceedings.mlr.press/v235/li24bt.html.
  21. [22]Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. EAGLE-2: Faster inference of language models with dynamic draft trees. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 7421–7432. Association for Computational Linguistics, 2024b. doi: 10.18653/v1/2024.emnlp-main.422. URL https://aclanthology.org/2024.emnlp-main.422/.
  22. [23]Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. EAGLE-3: Scaling up inference acceleration of large language models via training-time test. In Advances in Neural Information Processing Systems, 2025.
  23. [24]Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret MPC via perturbation analysis: Prediction error, constraints, and nonlinearity. In Advances in Neural Information Processing Systems, volume 35, 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/hash/eadeef7c51ad86989cc3b311cb49ec89-Abstract-Conference.html.
  24. [25]Yiheng Lin, James A. Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive policy selection in time-varying systems: No-regret via contractive perturbations. In Advances in Neural Information Processing Systems, volume 36, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/a7a7180fe7f82ff98eee0827c5e9c141-Abstract-Conference.html.
  25. [26]Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online policy optimization in unknown nonlinear systems. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 3475–3522. PMLR, 30 Jun–03 Jul 2024. URL https://proceedings.mlr.press/v247/lin24a.html.arxiv.org/abs/2404.13009
  26. [27]Hongyi Liu, Jiaji Huang, Zhen Jia, Youngsuk Park, and Yu-Xiang Wang. Not-a-bandit: Probably no-regret drafter selection in speculative decoding for LLMs. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/2510.20064.
  27. [28]Tianyu Liu, Yun Li, Qitan Lv, Kai Liu, Jianchen Zhu, Winston Hu, and Xiao Sun. Pearl: Parallel speculative decoding with adaptive draft length, 2025. URL https://arxiv.org/abs/2408.11850.
  28. [29]Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Alvin Cheung, Zhijie Deng, Ion Stoica, and Hao Zhang. Online speculative decoding. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 2024.arxiv.org/abs/2310.07177
  29. [30]Jonathan Mamou, Oren Pereg, Daniel Korat, Moshe Berchansky, Nadav Timor, Moshe Wasserblat, and Roy Schwartz. Dynamic speculation lookahead accelerates speculative decoding of large language models. In Proceedings of the 4th NeurIPS Efficient Natural Language and Speech Processing Workshop, volume 262 of Proceedings of Machine Learning Research, pages 456–467. PMLR, 2024. URL https://proceedings.mlr.press/v262/mamou24a.html.arxiv.org/abs/2405.04304
  30. [31]Yu-Yang Qian, Hao-Cong Wu, Yichao Fu, Hao Zhang, and Peng Zhao. When drafts evolve: Speculative decoding meets online learning. arXiv preprint arXiv:2603.12617, 2026. URL https://arxiv.org/abs/2603.12617.
  31. [32]Mohammad Samragh, Arnav Kundu, David Harrison, Kumari Nishu, Devang Naik, Minsik Cho, and Mehrdad Farajtabar. Your llm knows the future: Uncovering its multi-token prediction potential, 2025. URL https://arxiv.org/abs/2507.11851.
  32. [33]Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. In Advances in Neural Information Processing Systems, volume 31, 2018.arxiv.org/abs/1811.03115
  33. [34]Heming Xia, Zhe Yang, Qingxiu Dong, Peiyi Wang, Yongqi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding, 2024. URL https://arxiv.org/abs/2401.07851.
  34. [35]Jiebin Zhang, Zhenghan Yu, Liang Wang, Nan Yang, Eugene J. Yu, Zheng Li, Yifan Song, Dawei Zhu, Xingxing Zhang, Furu Wei, and Sujian Li. Learning to draft: Adaptive speculative decoding with reinforcement learning. arXiv preprint arXiv:2603.01639, 2026. URL https://arxiv.org/abs/2603.01639.
  35. [36]Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems, volume 31, 2018.
  36. [37]Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning, 2021. URL https://arxiv.org/abs/2110.00871.
  37. [38]Ziyin Zhang, Jiahao Xu, Tian Liang, Xingyu Chen, Zhiwei He, Rui Wang, and Zhaopeng Tu. Draft model knows when to stop: Self-verification speculative decoding for long-form generation. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 16685–16697. Association for Computational Linguistics, 2025. doi: 10.18653/v1/2025.emnlp-main.844. URL https://aclanthology.org/2025.emnlp-main.844/.
  38. [39]Guoliang Zhao, Ruobing Xie, An Wang, Shuaipeng Li, Huaibing Xie, and Xingwu Sun. Self-distillation for multi-token prediction. arXiv preprint arXiv:2603.23911, 2026.arxiv.org/abs/2603.23911
  39. [40]Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, 2003. URL https://www.martin.zinkevich.org/publications/ICML03.pdf.

Paper details

vlnc:W_6kgkhy9g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Generative AI tools

View statement
Looking for related papers…
Contents