Mentored Decoding: Faster Inference meets Boosting

Vivien Tran-Thien; Richard Nock

cs.LGSep 24, 2026

Mentored Decoding: Faster Inference meets Boosting

Authors: Vivien Tran-Thien, Richard Nock

Organizations: Google

Abstract

Speculative decoding is a successful technique speeding up inference of a target autoregressive language model via a fast drafter model. Lossy speculative decoding allows a drift with respect to the target to further improve speed. Interestingly, it has been observed experimentally that the resulting model can $\textit{also}$ beat the target $\textit{quality-wise}$ . Our paper formally proves how such a feat is possible with a formal approach to lossy speculative decoding called $\textit{mentored decoding}$ . To get there, we connect inference to a celebrated ML training theory, $\textit{boosting}$ , and proceed via the generalization of mentored decoding to the whole set of $f$ -divergences. We uncover key properties of mentored decoding, among which (i) the particularly appealing geometric nature of the total variation case, (ii) simple approximations for any $f$ -divergence in direct relation with boosting compliance, and (iii) a $\textit{divergence independent}$ $O(n)$ space and $O(\mathrm{sort}(n))$ time data structure built on drafter and target outputs, which allows to query the optimal parameters of the dual problem in $O(\log n)$ time and constructing optimal mentored distributions in $O(n)$ time for any $f$ -divergence.

Figures & tables

Panel of Figure 1 — Figure 1: Example of optimal solutions for the TV-MD problem with $n=3$ tokens in $\Delta_{3}$ , as intersection (thick segment) between the two $L_{1}$ balls centered in $\bm{p}$ and $\bm{q}$ (in color red and blue ) whose radii define $D$ and the optimal objective value for the total variation divergences in ( f -MD-1 ). The shaded area is set $\left[\min\{\bm{p},\bm{q}\},\max\{\bm{p},\bm{q}\}\right]\cap\Delta_{3}$ (see text).

Figure 2: Illustration of the definition of $\mathrm{clampset}(z,\mathbb{A},\mathbb{B})$ ( 10 ) (in red ) when $\mathbb{A}<\mathbb{B}$ are intervals (figured by rectangles) and $z$ (thick vertical bar) moves along the real line (see text).

Panel of Figure 3 — Figure 3: Plots of $\log_{t}$ (left) and $\exp_{t}$ (right), for $t=0,1/4,1/2,3/4,1$ in black curves where thickness increases with $t$ (see text).

\displaystyle\tau_{a}\leftarrow\left(r_{i0}-1-a\right)\cdot q_{A}

;

\displaystyle\tau_{b}\leftarrow\left(1-b-r_{j0}\right)\cdot q_{B};

Algorithm 1 UpdateCBreakpoints

(\textsc{r},\textsc{c},a,b,i,j,q_{A},q_{B},a_{\max},b_{\max})

Figure 4: In the $\Delta_{3}$ simplex (same setting as Figure 1 ), we illustrate Theorem 3.13 and Lemma 5.2 . The thick dark line is the set of mentored distributions built from querying QueryCBreakpoints in Algorithm 3 . The bend represents a mentored distribution corresponding to a breakpoint in $\textsc{c}(\bm{p},\bm{q})$ . We display the couple $(a,b)$ corresponding to the mentored distribution $\bm{\pi}$ . Finally, for a set of four $f$ -divergences (rKL = reverse KL), we display that $\bm{\pi}$ is also the optimal solution in all $\textsc{md}_{f}(\bm{p},\bm{q};.)$ because it is the intersection between the TV-ball defining the optimal objective and the $f$ -divergence ball defining the constraint activated in $f$ -MD.

\displaystyle\tilde{b}

\displaystyle\leftarrow

\displaystyle b+\frac{(\tilde{a}-a)\cdot q(\mathbb{A}_{i})}{q(\mathbb{B}_{i})};\quad\mbox{//

\mathbb{A}{i},\mathbb{B}{i}

are as in \eqref{defAbis}, \eqref{defBbis} for breakpoint

(a_{i},b_{i})

}

(66)

Algorithm 3 QueryCBreakpoints

(\textsc{c},\tilde{a})

Name	Generator $f(z)$	Comments
Kullback-Leibler (KL)	$z\log z$
reverse Kullback-Leibler (rKL)	$-\log z$
Hellinger	$1-\sqrt{z}$
Neyman	$(z-1)^{2}$	reverse $\chi^{2}$
Pearson	$(z-1)^{2}/z$	$\chi^{2}$
$TV_{2}$	$2\cdot\max\left\{f_{\mathrm{TV}}(z),2\cdot\|z-1\|-1\right\}$

Table 1:

f

-divergences used in our toy simulations; we recall

f_{\mathrm{TV}}(z)\stackrel{{\scriptstyle\mathrm{.}}}{{=}}|z-1|/2

(see text).

Panel of Table 2 — Table 2: Left: curve of points $(\tilde{a},\tilde{b})$ in $\mathcal{C}(\bm{p},\bm{q})$ from Lemma 5.3 , showing it is strictly increasing and continuous. Right: curves showing the corresponding $f$ -divergence bound $D$ in ( f -MD-2 ) ( f -MD-1 ) as a function of the optimal acceptance probability $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ , for several $f$ -divergences. Remark that for all except $TV_{2}$ , the right derivative at $P_{\hskip-2.84544pt\mbox{\tiny acc}}(SD)$ is indeed zero and the divergence stays close to 0 even past $>10\%$ increase acceptance probability $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ (see text).

Panel of Table 3 — Table 3: For each of the $f$ -divergence plots in Table 2 (Right), we plot the divergence as a function of $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ , and in filled green the interval of min and max values corresponding to ( 42 ) in Theorem 3.12 , over a range of $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ which covers $P_{\hskip-2.84544pt\mbox{\tiny acc}}(SD)$ ( red dot) to $P_{\hskip-2.84544pt\mbox{\tiny acc}}(SD)$ increased by 25 $\%$ (see text).

Panel of Table 4 — Table 4: Top: plots of the $f$ -divergence bound $D$ in $\textsc{md}_{f}(\bm{p},\bm{q};D)$ as a function of $a$ ( Left ) and $b$ ( Right ), exemplifying Theorem 3.12 . Bottom: plots of the optimal acceptance probability $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ as a function of $a$ ( Left ) and $b$ ( Right ), exemplifying Theorem 3.12 (see text).

Panel of Table 5 — Table 5: Left: curve giving the boosting bound coefficient $k\stackrel{{\scriptstyle\mathrm{.}}}{{=}}\sqrt{(1+a)/(1-b)}$ (Theorem 4.8 ) as a function of the acceptance probability $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ ; remark that $k$ remains close to $1$ even for substantial increase of the acceptance probability compared to the speculative decoding solution. Right: curve giving coefficient $k$ as a function of $a$ (see text).

Panel of Table 6 — Table 6: Mentored distribution (thick purple curve) and acceptance probability ( purple area) when $\bm{p}$ (thin blue curve) and $\bm{q}$ (thin red curve) are discretized from Beta distributions. The values under each plot are $b$ and $P_{\hskip-2.84544pt\mbox{\tiny acc}}(MD)$ (in parentheses, see text).

Speculative Decoding

Speculative decoding accelerates generation by drafting multiple tokens and verifying them in parallel with a larger target model.

See all 314 papers

DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification
Apr 8, 2026Ziyi Wang, Siva Rajesh Kasa, Ankith M S +6Speculative Decoding LLM Inference Acceleration
Purdue University · Amazon Inc. · University of Illinois Urbana-Champaign +1
Speculative Speculative Decoding
Mar 3, 2026Tanishq Kumar, Tri Dao, Avner MaySpeculative Decoding LLM Inference Acceleration
Department of Computer Science, Stanford University · Department of Computer Science, Princeton University · Together AI
Faster LLM Inference via Sequential Monte Carlo
Apr 17, 2026Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang +4Speculative Decoding LLM Inference Acceleration
Cornell University · Makora · MIT +1

Apr 8, 2026J/K move · Enter open · S save

DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification

Ziyi Wang, Siva Rajesh Kasa, Ankith M S, Santhosh Kumar Kasa+5

Purdue University · Amazon Inc. · University of Illinois Urbana-Champaign+1

Speculative Decoding LLM Inference Acceleration Parallel Speculative Decoding

Open paper AskPDF arXiv

Speculative decoding is an effective technique for accelerating large language model inference by drafting multiple tokens in parallel. In practice, its speedup is often bottlenecked by a rigid verification step that strictly enforces the accepted token distribution to exactly match the target model. This constraint leads to the rejection of many plausible tokens, lowering the acceptance rate and limiting overall time speedup. To overcome this limitation, we propose Dynamic Verification Relaxed Speculative Decoding (DIVERSED), a relaxed verification framework that improves time efficiency while preserving generation quality. DIVERSED learns an ensemble-based verifier that blends the draft and target model distributions with a task-dependent and context-dependent weight. We provide theoretical justification for our approach and demonstrate empirically that DIVERSED achieves substantially higher inference efficiency compared to standard speculative decoding methods. Code is available at: https://github.com/comeusr/diversed.

Abstract

Speculative Decoding

Explore similar work

DIVERSED: Relaxed Speculative Decoding via Dynamic Ensemble Verification

Speculative Speculative Decoding

Faster LLM Inference via Sequential Monte Carlo