Speculative Decoding Math: Algorithms & Speedup Limits › Optimal Draft Length

Choosing the draft length $k$ involves balancing the cost of generating more drafts against the diminishing probability of accepting them all. This optimization problem has both theoretical and practical importance. In theory, it determines the maximum achievable speedup for a given model pair and hardware configuration. In practice, it guides the single most important configuration choice when deploying speculative decoding.

The optimal draft length is not fixed. It depends on the acceptance probability $\alpha$ (which varies by task and context), the cost ratio $c$ (which depends on hardware and model sizes), and potentially on dynamic factors like recent acceptance rate history. Understanding these dependencies allows you to make good static choices and design adaptive strategies that respond to changing conditions.

We want to find $k^*$ that maximizes speedup. Substituting our formula for $\mathbb{E}[N]$, the optimization problem is:

$$\begin{aligned} k^* &= \arg\max_k \frac{\mathbb{E}[N_k]}{1 + k/c} && \text{(maximize speedup)} \\ &= \arg\max_k \frac{(1 - \alpha^{k+1})/(1 - \alpha)}{1 + k/c} && \text{(substitute } \mathbb{E}[N_k] \text{)} \end{aligned}$$

where:

• $k^*$: optimal draft length
• $\mathbb{E}[N_k]$: expected tokens generated with draft length $k$
• $c$: cost ratio

Taking the derivative with respect to $k$ and setting to zero is analytically intractable because $k$ is an integer, but we can analyze the continuous relaxation and then round to find the optimal integer value. The continuous analysis reveals the structure of the problem and shows why an interior optimum always exists for finite $c$.

The expected tokens $\mathbb{E}[N_k]$ grows sublinearly in $k$. This can be seen from the geometric series formula:

$$\mathbb{E}[N_k] = \frac{1 - \alpha^{k+1}}{1 - \alpha} \approx \frac{1}{1-\alpha} \text{ as } k \to \infty$$

where:

• $\mathbb{E}[N_k]$: expected tokens for draft length $k$
• $\frac{1}{1-\alpha}$: asymptotic limit of expected tokens as $k$ grows without bound
• $\alpha < 1$: acceptance probability

The growth rate decreases exponentially because $\alpha^k$ decays exponentially. Meanwhile, the cost $1 + k/c$ grows linearly in $k$. This tension creates an interior optimum. Intuitively, each additional draft token has a diminishing marginal benefit (it is only useful if all previous tokens were accepted, which becomes increasingly unlikely) but a constant marginal cost (one more draft model forward pass). At some point, the marginal cost exceeds the marginal benefit, and we should stop drafting.

Think of it as a classic diminishing returns problem. The first draft token you add is very valuable because there is a high probability it gets accepted ($\alpha$). The second draft token is somewhat less valuable because it only contributes when the first was also accepted ($\alpha^2$ probability of usefulness). The tenth draft token only contributes when all nine preceding tokens were accepted ($\alpha^{10}$ probability), which for $\alpha = 0.8$ is only about 10.7%. At some point, the additional draft tokens contribute so rarely that running the draft model to generate them costs more than it saves.

For large $c$ (fast draft model), we can derive an approximate optimal draft length. When $c \to \infty$, the optimal $k$ is infinite since there's no cost to drafting more tokens. For finite $c$, the optimal $k$ satisfies the first-order condition from setting the derivative of the speedup function to zero. Treating $k$ as continuous and applying the quotient rule:

$$\begin{aligned} \frac{d}{dk} \left( \frac{1 - \alpha^{k+1}}{1 + k/c} \right) &= \frac{-\alpha^{k+1} \ln(\alpha) \cdot (1 + k/c) - (1 - \alpha^{k+1}) \cdot (1/c)}{(1 + k/c)^2} && \text{(quotient rule)} \\ &= 0 && \text{(set derivative to zero)} \end{aligned}$$

where:

• $\alpha$: acceptance probability
• $k$: draft length
• $c$: cost ratio
• $-\alpha^{k+1} \ln(\alpha)$: derivative of the numerator term $(1 - \alpha^{k+1})$ (positive since $\ln(\alpha) < 0$ for $\alpha < 1$)
• $1/c$: derivative of the denominator term $(1 + k/c)$
• $(1 + k/c)^2$: squared denominator from the quotient rule

Setting the numerator to zero gives:

$$-\alpha^{k+1} \ln(\alpha) = \frac{1 - \alpha^{k+1}}{c(1 + k/c)}$$

where:

• $\alpha$: acceptance probability
• $k$: draft length
• $c$: cost ratio
• $-\alpha^{k+1} \ln(\alpha)$: marginal gain from extending the draft by one position
• Right side: normalized marginal cost of extension

This equation balances marginal benefit against marginal cost. The left side represents the expected additional tokens from extending the draft by one position (how often does the $(k+1)$th token get accepted, and how much does that help). The right side represents the cost of that extension in terms of reduced speedup per existing token. While this equation cannot be solved in closed form, it can be solved numerically for any specific values of $\alpha$ and $c$.

For typical values ($\alpha \approx 0.7$, $c \approx 10$), optimal $k$ ranges from 4 to 8 tokens. This explains why practical systems typically use draft lengths in this range. The formula predicts that using $k=5$ is close to optimal for many common configurations, which is why it has become a common default setting in speculative decoding implementations.

In practice, the optimal $k$ varies based on context. Different parts of a response have different acceptance rates: the beginning of a sentence is often more predictable than the middle, and common phrases have much higher acceptance rates than rare ones. Systems that use a fixed $k$ throughout generation leave performance on the table because they cannot adjust to these variations.

Practical adaptive strategies include:

• Fixed $k$: Simple to implement, works well when acceptance rates are stable. A good default for production systems where simplicity matters.
• Adaptive $k$: Adjust based on recent acceptance rates. If the last several iterations had high acceptance rates, increase $k$; if rates were low, decrease $k$. This can improve average throughput by 10-20% over fixed $k$ in practice.
• Tree-based drafting: Generate multiple candidate continuations as a tree rather than a single sequence, increasing effective acceptance probability. When the draft model is uncertain about the best next token, it can propose several alternatives, and the target model accepts the best match. This approach trades increased memory usage for higher effective acceptance rates.

The adaptive approach monitors acceptance rates during generation and increases $k$ when rates are high (showing the draft model is performing well on the current content) or decreases $k$ when rates are low (showing more challenging content where longer drafts would be wasteful). Implementing this correctly requires careful bookkeeping to avoid introducing biases from the adaptation process itself, but when done correctly, it maintains the exact-sampling guarantee while improving average throughput.