Speculative Decoding Math: Algorithms & Speedup Limits › Expected Speedup Analysis

Understanding the expected speedup from speculative decoding requires analyzing how many tokens we expect to accept from each draft sequence and how this translates to wall-clock improvements. This analysis provides both theoretical insights and practical guidance for deploying speculative decoding systems.

The speedup analysis connects the abstract acceptance probability to concrete performance numbers. You might wonder why we need a full mathematical treatment rather than just running experiments. The answer is that experiments can only test specific configurations, while the mathematical framework reveals the basic tradeoffs. It tells us how speedup depends on draft model quality, draft length, and the relative speed of the two models. Armed with this formula, you can predict performance for new model pairs without running extensive benchmarks, and you can optimize configuration choices analytically.

Think of the speedup formula as a budget analysis. Each speculative decoding iteration has a cost (running the draft model multiple times and the target model once) and a benefit (generating multiple tokens in one iteration). The ratio of benefit to cost is the speedup. The mathematical framework makes this ratio precise and reveals how each parameter affects the balance.

Let $\alpha$ denote the average acceptance probability for a single token. Under simplifying assumptions where each position has the same acceptance rate, we can derive a clean expression for this probability. While real-world acceptance rates vary by position and context, this i.i.d. assumption provides valuable analytical insights and gives formulas that match empirical measurements reasonably well when using the observed acceptance rate as the input.

The expected acceptance probability $\alpha$ is computed by averaging over all tokens that the draft model might propose, weighting each token's acceptance probability by how often the draft model proposes it:

$$\begin{aligned} \alpha &= \mathbb{E}_{x \sim q}\left[\min\left(1, \frac{p(x)}{q(x)}\right)\right] && \text{(definition of expectation)} \\ &= \sum_x q(x) \cdot \min\left(1, \frac{p(x)}{q(x)}\right) && \text{(expand expectation)} \\ &= \sum_x \min\left(q(x), q(x) \cdot \frac{p(x)}{q(x)}\right) && \text{(distribute } q(x) \text{)} \\ &= \sum_x \min(q(x), p(x)) && \text{(simplify)} \end{aligned}$$

where:

• $\alpha$: expected acceptance probability
• $\mathbb{E}_{x \sim q}$: expectation over tokens proposed by the draft model
• $q(x)$: draft model probability of token $x$
• $p(x)$: target model probability of token $x$
• $\sum_x \min(q(x), p(x))$: total probability mass overlap between the two distributions

This quantity measures the overlap between the draft and target distributions. When the distributions are identical, $\alpha = 1$. When they are completely disjoint, $\alpha = 0$. In practice, $\alpha$ typically falls between 0.6 and 0.9 for well-matched draft and target model pairs. Because $\alpha$ equals the distribution overlap, it directly measures draft model quality from first principles and connects acceptance rates to the statistical notion of distributional similarity.

Given a draft of length $k$, the number of accepted tokens follows a truncated geometric distribution. This distribution arises because we accept tokens sequentially until the first rejection, but we stop at position $k$ even if no rejection has occurred. Under the i.i.d. assumption with uniform acceptance probability $\alpha$, the probability that the first $j$ tokens are all accepted is $\alpha^j$, and the probability of a rejection at position $j+1$ is $\alpha^j(1-\alpha)$.

Let $N$ be the number of tokens we generate (accepted drafts plus one from rejection sampling or the $(k+1)$th position). The expected value is:

$$\mathbb{E}[N] = \sum_{i=1}^{k} i \cdot \alpha^{i-1}(1-\alpha) + (k+1) \cdot \alpha^k$$

where:

• $\mathbb{E}[N]$: expected number of accepted tokens (plus one verification)
• $k$: draft sequence length
• $\alpha$: probability of accepting a single token
• $i$: position of the first rejection
• $\alpha^{i-1}(1-\alpha)$: probability that the first rejection occurs at position $i$
• $(k+1) \cdot \alpha^k$: contribution from the case where all $k$ tokens are accepted

The first term accounts for rejecting at position $i$ (we keep $i$ tokens including the resampled one). The second term accounts for accepting all $k$ drafts (we get $k+1$ tokens including the bonus verification token).

We can simplify this sum by observing that $N$ is 1 plus the count of accepted draft tokens. Since the probability of accepting the first $j$ tokens is $\alpha^j$ for all $j \le k$ (under the simplified i.i.d. assumption), we can use the linearity of expectation:

$$\begin{aligned} \mathbb{E}[N] &= 1 + \sum_{j=1}^{k} P(\text{token } j \text{ is accepted}) && \text{(linearity of expectation)} \\ &= 1 + \sum_{j=1}^{k} \alpha^j && \text{(i.i.d. assumption)} \\ &= \sum_{j=0}^{k} \alpha^j && \text{(include } j=0 \text{ term)} \\ &= \frac{1 - \alpha^{k+1}}{1 - \alpha} && \text{(geometric series sum)} \end{aligned}$$

where:

• $\mathbb{E}[N]$: closed-form expected number of tokens generated per iteration
• $\alpha$: acceptance probability
• $k$: draft length
• $\frac{1 - \alpha^{k+1}}{1 - \alpha}$: sum of the geometric series $1 + \alpha + \alpha^2 + \cdots + \alpha^k$

This closed-form expression shows that expected tokens per iteration grow as a geometric series in the acceptance probability. When $\alpha$ is close to 1, almost all draft tokens are accepted, and $\mathbb{E}[N]$ approaches $k+1$. When $\alpha$ is close to 0, most drafts are rejected immediately, and $\mathbb{E}[N]$ approaches 1 (we generate just one token from the residual distribution). The geometric series structure is key: each additional draft token contributes $\alpha^j$ to the expected yield, which decays exponentially with position, creating natural diminishing returns at longer draft lengths.

Let $c$ be the cost ratio, defined as the time for one target model forward pass divided by the time for one draft model forward pass. Typically $c \gg 1$ since the target model is much larger. For example, if the target model has 70 billion parameters and the draft model has 7 billion parameters, we might expect $c$ to be roughly 10, depending on hardware and batching configurations. In memory-bandwidth-limited regimes (which describes most autoregressive inference), $c$ scales roughly with the ratio of model parameter counts.

Without speculative decoding, generating $n$ tokens requires $n$ target model passes, taking time $n \cdot T_{\text{target}}$. This is the baseline we are trying to beat. Each token requires a full forward pass through the large model, with no opportunity for parallelism across tokens in standard autoregressive generation.

With speculative decoding, each iteration requires:

• One draft model pass generating $k$ tokens, taking time $k \cdot T_{\text{draft}}$
• One target model pass verifying all $k$ positions, taking time $T_{\text{target}}$

The iteration produces $\mathbb{E}[N] = \frac{1 - \alpha^{k+1}}{1 - \alpha}$ tokens on average and takes time $T_{\text{target}} + k \cdot T_{\text{draft}} = T_{\text{target}}(1 + k/c)$.

The speedup ratio $S$ compares how fast we generate tokens with speculative decoding versus standard autoregressive generation. We derive this by computing the time per token under both approaches and taking their ratio. Standard generation takes $T_{\text{target}}$ per token. Speculative decoding takes $T_{\text{target}}(1 + k/c) / \mathbb{E}[N]$ per token. The speedup is:

$$\begin{aligned} S &= \frac{T_{\text{target}}}{\frac{T_{\text{target}}(1 + k/c)}{\mathbb{E}[N]}} && \text{(ratio of time per token)} \\ &= \frac{\mathbb{E}[N]}{1 + k/c} && \text{(cancel } T_{\text{target}} \text{)} \\ &= \frac{(1 - \alpha^{k+1})/(1 - \alpha)}{1 + k/c} && \text{(substitute } \mathbb{E}[N] \text{)} \end{aligned}$$

where:

• $S$: speedup ratio (values above 1 mean speculative decoding is faster)
• $T_{\text{target}}$: time for standard autoregressive generation per token
• $k$: draft length
• $c$: cost ratio ($T_{\text{target}} / T_{\text{draft}}$)
• $\alpha$: acceptance probability (used in $\mathbb{E}[N]$)
• $1 + k/c$: cost of one speculative iteration in units of target model passes
• $\mathbb{E}[N]$: average tokens produced per iteration

This formula captures the needed tradeoff in speculative decoding. The numerator measures benefit, specifically how many tokens we expect to generate per iteration. The denominator measures cost, specifically how much computation that iteration requires. Speedup greater than 1 means speculative decoding is faster than standard generation. The formula also shows that speedup depends on all three of $\alpha$, $k$, and $c$ in ways that interact: high $\alpha$ is more valuable when $k$ is large, and large $k$ is only worth it when $c$ is large enough.

When the draft model is very fast ($c \to \infty$), this simplifies to:

$$S \approx \frac{1 - \alpha^{k+1}}{1 - \alpha}$$

where:

• $S$: theoretical maximum speedup with a zero-cost draft model
• $\alpha$: acceptance probability
• $k$: draft length

This limiting case represents the best possible speedup when the draft model adds negligible overhead. In practice, draft models incur costs, so the actual speedup is lower than this bound. However, this formula provides a useful upper limit for what speculative decoding can achieve. When $\alpha = 0.8$ and $k = 5$, the theoretical maximum speedup is $(1 - 0.8^6) / (1 - 0.8) \approx 3.7\times$, meaning even with a free draft model, we cannot exceed 3.7 times the speed of standard generation in this configuration.