Reading Notes on PEARL

When I previously read EAGLE, I saw the author link this paper below it. I recently needed to study PD disaggregation, so this was a good opportunity to read and take notes on PEARL.

Core Idea

Traditional speculative decoding verifies only after producing a complete sequence of draft tokens. Verification and drafting therefore have a logical ordering: no drafting occurs during verification, and no verification occurs during drafting.

To run the two processes in parallel, PEARL proposes two verification strategies.

---

Core Concept

The two strategies are pre-verify and post-verify:

• pre: This strategy breaks the restriction that verification must wait for a complete draft. It verifies the prefix as soon as the first draft token appears. If the first token is rejected, every later token will be rejected as well. The approach still respects logical ordering and seems like a generally applicable way to use otherwise idle resources.
• post: This strategy breaks the vanilla requirement that the next draft generation wait for verification to supply a prefix, merging the gaps between consecutive draft generations. If an entire draft is accepted, the draft model can continue generating because its current trajectory remains healthy; there is no need for the verified prefix to interrupt it. When verification fails, the system returns to pre-verification.

In the vanilla implementation, the draft model generates $N$ tokens and the target then verifies them. Alternating the two leaves two idle periods:

1. The target model is idle while candidates are generated.
2. The draft model is idle during verification.

PEARL fills these gaps by having the target perform an extra “verification” while drafting. Since no candidates yet exist, this is not truly verification: pre-verify is a target-model decoding step that generates a new token. As long as that step is slower than generating $N$ candidates, it can perform useful pruning before the real verification, or post-verify.

During post-verify, the draft model continues generating. In the worst case verification fails and those candidates are discarded, but latency is not lost—ignoring wasted compute outside a serving scenario. Any successful verification produces some benefit.

---

Thinking

The method feels natural, but like branch prediction in a pipeline it depends on the probability of choosing the right direction—in this case, the draft acceptance rate.

We can derive an expression by defining:

• $t_g$: generation time
• $t_v$: verification time
• $\gamma$: maximum length of one draft
• $\alpha$: per-token acceptance rate
• $t_1$: duration of one section

Starting from one inference cycle—and therefore one pre-verify—verification can either succeed or fail.

On failure:

$t_f = max(\gamma t_g , t_v)$

$n_t = 1$

On success, several consecutive post-verification stages may occur, with probability:

$P(accept = a\gamma + b) = \alpha^{a\gamma +b} (1-\alpha)$

$t_s=(a+1)t_f$

Weighting the cases gives:

$$\begin{aligned} E[n] &= (1-\alpha)\cdot 1 + \alpha \sum_{k=1}^{\infty} k \cdot \alpha^k (1-\alpha) = 1 - \alpha + \frac{\alpha^2}{1-\alpha}, \\ E[t] &= (1-\alpha)t_s + \alpha \sum_{a=0}^{\infty} (a+1)t_s \cdot \alpha^{a\gamma} (1-\alpha) = (1-\alpha)t_s + \frac{\alpha(1-\alpha)t_s}{(1-\alpha^\gamma)^2}, \\ E\left[\frac{\text{token}}{\text{s}}\right] &= \frac{E[n]}{E[t]} = \frac{1 - \alpha + \dfrac{\alpha^2}{1-\alpha}} {(1-\alpha)t_s + \dfrac{\alpha(1-\alpha)t_s}{(1-\alpha^\gamma)^2}}, \end{aligned}$$

For comparison, the average utility of vanilla speculative decoding is:

$U=\frac{\alpha k}{k t_g + t_v}$

Taking $t_v = 10t_g$ and $\gamma=4$ produces the following plot. The gain is significant when the acceptance rate is high.

The acceptance rate also declines as the accepted sequence grows. Real behavior therefore does not follow a geometric sequence and will be slightly worse than this estimate.