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 also beat the target quality-wise. Our paper formally proves how such a feat is possible with a formal approach to lossy speculative decoding called mentored decoding. To get there, we connect inference to a celebrated ML training theory, 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 divergence independentO(n) space and O(sort(n)) time data structure built on drafter and target outputs, which allows to query the optimal parameters of the dual problem in O(logn) time and constructing optimal mentored distributions in O(n) time for any f-divergence.
Figures & tables
Figure 1: Example of optimal solutions for the TV-MD problem with n=3 tokens in Δ3 , as intersection (thick segment) between the two L1 balls centered in p and 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 [min{p,q},max{p,q}]∩Δ3 (see text).
Figure 2: Illustration of the definition of clampset(z,A,B) ( 10 ) (in red ) when A<B are intervals (figured by rectangles) and z (thick vertical bar) moves along the real line (see text).
Figure 3: Plots of logt (left) and expt (right), for t=0,1/4,1/2,3/4,1 in black curves where thickness increases with t (see text).
Figure 4: In the Δ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 \textscc(p,q) . We display the couple (a,b) corresponding to the mentored distribution π . Finally, for a set of four f -divergences (rKL = reverse KL), we display that π is also the optimal solution in all \textscmdf(p,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.
Table 1: f -divergences used in our toy simulations; we recall fTV(z)=.∣z−1∣/2 (see text).
Table 2: Left: curve of points (a~,b~) in C(p,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\mboxacc(MD) , for several f -divergences. Remark that for all except TV2 , the right derivative at P\mboxacc(SD) is indeed zero and the divergence stays close to 0 even past >10% increase acceptance probability P\mboxacc(MD) (see text).
Table 3: For each of the f -divergence plots in Table 2 (Right), we plot the divergence as a function of P\mboxacc(MD) , and in filled green the interval of min and max values corresponding to ( 42 ) in Theorem 3.12 , over a range of P\mboxacc(MD) which covers P\mboxacc(SD) ( red dot) to P\mboxacc(SD) increased by 25 % (see text).
Table 4: Top: plots of the f -divergence bound D in \textscmdf(p,q;D) as a function of a ( Left ) and b ( Right ), exemplifying Theorem 3.12 . Bottom: plots of the optimal acceptance probability P\mboxacc(MD) as a function of a ( Left ) and b ( Right ), exemplifying Theorem 3.12 (see text).
Table 5: Left: curve giving the boosting bound coefficient k=.(1+a)/(1−b) (Theorem 4.8 ) as a function of the acceptance probability P\mboxacc(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).
Table 6: Mentored distribution (thick purple curve) and acceptance probability ( purple area) when p (thin blue curve) and q (thin red curve) are discretized from Beta distributions. The values under each plot are b and P\mboxacc(MD) (in parentheses, see text).
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.
Ziyi Wang, Siva Rajesh Kasa, Ankith M S +6
Purdue University · Amazon Inc. · University of Illinois Urbana-Champaign +1
Autoregressive decoding is bottlenecked by its sequential nature. Speculative decoding has become a standard way to accelerate inference by using a fast draft model to predict upcoming tokens from a slower target model, and then verifying them in parallel with a single target model forward pass. However, speculative decoding itself relies on a sequential dependence between speculation and verification. We introduce speculative speculative decoding (SSD) to parallelize these operations. While a verification is ongoing, the draft model predicts likely verification outcomes and prepares speculations pre-emptively for them. If the actual verification outcome is then in the predicted set, a speculation can be returned immediately, eliminating drafting overhead entirely. We identify three key challenges presented by speculative speculative decoding, and suggest principled methods to solve each. The result is Saguaro, an optimized SSD algorithm. Our implementation is on average 30% faster than optimized speculative decoding baselines and up to 5x faster than autoregressive decoding with open source inference engines.
Tanishq Kumar, Tri Dao, Avner May
Department of Computer Science, Stanford University · Department of Computer Science, Princeton University · Together AI
Speculative decoding (SD) accelerates language model inference by drafting tokens from a cheap proposal model and verifying them against an expensive target model via rejection sampling. Because rejection truncates the draft block at the first error, throughput degrades when draft and target diverge. Rather than rejecting draft tokens outright, we propose to reweight them. To this end, we introduce sequential Monte Carlo speculative decoding (SMC-SD), which replaces token-level rejection with importance-weighted resampling over a population of draft particles. SMC-SD is a principled approximate inference scheme that trades exactness for additional speed, while preserving theoretical bounds on its per-step approximation error. Because LLM inference is memory bandwidth-bound, the arithmetic needed to draft particles and to score them in parallel comes nearly for free -- SMC-SD uses idle compute to turn verification into a vectorized, fixed-size operation with no rollback. Empirically, SMC-SD achieves 2.36x speed-up over speculative decoding and a 5.2x speed-up over autoregressive decoding, while remaining within 3% of the target model's accuracy on reasoning, instruction-following, and coding benchmarks.
Yahya Emara, Mauricio Barba da Costa, Chi-Chih Chang +4