Speculative Decoding Is Per-Token, Not Path
Abstract
We prove that the speedup of exact speculative decoding is governed by a per-token rate, not by the path-level prefix-overlap capacity that folklore suggests, and that the gap between the two can be unbounded. The two candidates are the per-token Leviathan rate σ_L(P, Q) and the path-level coupling capacity Ω_L(P, Q) = Σ_t=1^L ov(P_≤t, Q_≤t). We show σ_L ≤ Ω_L always, the inequality is strict already on i.i.d. products, and there exists an explicit fixed-precision binary trajectory-exact rejection-style protocol on L = 2 with E[τ] = 19/16 > 9/8 = σ_L, ruling out σ_L as a universal upper bound across all trajectory-exact rounds. Inside the deployable admissible Leviathan-style clipped-ratio class, σ_L is the tight rate, and the speculation decoding complexity satisfies SDC_B,L^Q(M; u, T) = Θ(T / (σ_L,B(P_M^u,T, Q) + 1)), achieved by iterated Leviathan and matched up to constants by Wald. On the path side, Ω_L exhibits a sharp two-sided dichotomy in the prefix-KL profile η_t: Σ_t √(η_t / 2) = o(L) forces Ω_L = L − o(L), while geometrically bounded overlap o_t ≤ ρ^t forces Ω_L ≤ 1/(1−ρ) uniformly in L, with no unconditional KL converse. Two explicit fixed-precision Transformer families of size O(log L) realize the two extremes under the same three-element proposal family Q = Q_flat, Q_const_0, Q_const_1: a constant-readout family F⁺ has SDC ≤ T / ((1−ε)L + 1), while an alternating-parity family F⁻ has SDC ≥ T/5, an unconditional Θ(L) architecture separation. Speculative decoding is not path coupling; it is per-token clipped-ratio acceptance, and the architecture of the target controls the rate.
Related papers
See more related submissions when the market opens.