14  Speculative and constrained decoding

The scheduling chapter decided when requests run and when compatible KV state can be reused. The decoder still has to choose each next token. Two changes answer different questions: speculative decoding lets a cheaper draft method propose tokens for target-model verification, while constrained decoding limits which tokens are allowed so output can follow a schema or grammar. Speculation needs acceptance and correction rules to preserve the intended distribution when exact sampling is required. Constraints serve a validity requirement and may add work. Neither method inherits the other’s correctness check or performance evidence.

A three-token draft suffix enters parallel target verification. Accept, first-rejection correction and all-pass extra-token branches lead to committed output. A schematic probability example rejects mat and corrects with dog. A separate parser tests age from the opening key prefix, masks invalid tokens and commits state only after selection. Timing, constraint cost and completion checks remain separate.
Figure 14.1: Speculation commits a verified prefix and uses residual correction to preserve the target distribution. The probability bars and whole-run timing record are illustrative. Constraints mask illegal continuations and update request state only after selection; their validity and total cost require separate checks.

14.1 Speculative decoding

Speculative decoding uses a cheaper draft method to propose several tokens and the target model to verify them. The method follows Fast Inference from Transformers via Speculative Decoding1, which proposes candidates with an approximation model and verifies them in parallel with the target model without changing the output distribution. The draft method accelerates proposal, but the output is exact only when the acceptance and residual rules preserve the target distribution.

The problem is serial target-model decoding. A normal autoregressive loop asks the large target model for one token at a time. Speculative decoding tries to advance several tokens per target-model verification pass by first generating a candidate suffix with a cheaper draft model.

14.1.1 Draft and verify mechanism

The mechanism has four ordered stages: draft a candidate suffix, run the target model over its prefixes in parallel, accept the longest prefix that passes the tests, and sample one more token. For γ draft tokens, the algorithm needs γ + 1 target next-token distributions: one at each draft position and one after the whole suffix. A target verification can produce them in parallel; a serving engine may already have the first distribution from its preceding target step. A rejection uses target p and draft q at that position for the corrected residual token. If all proposals pass, the last target distribution supplies the extra token without another target pass. The equations and worked example below explain these steps before implementation choices are considered.

Let p(x) and q(x) be normalized target and draft next-token distributions over the same vocabulary, conditioned on the same token prefix and incorporating the chosen sampling settings. The draft model samples a short candidate suffix cheaply. The target model evaluates that suffix in a larger verification pass. Each proposed token is accepted with a rule based on how much the draft distribution overstated or understated that token relative to the target distribution. If a token is rejected, the algorithm samples a replacement from a fallback distribution derived from the target and draft distributions, then discards the unaccepted suffix.

One word, two meanings: residual

Residual connection: the addition that carries a sub-layer’s input forward alongside its output, so the sub-layer only has to produce the difference (the model behind the workload, Section 1.1). It is part of the model’s architecture.

Residual distribution: what is left of the target distribution p after the draft distribution q is subtracted, with negative values set to zero and the result renormalized. It is the distribution a rejected token is resampled from, and it is what keeps the output exact.

The shared word means the remaining part in both cases, but the two refer to different objects: one is a tensor addition inside the model, and the other is a probability correction in the sampling algorithm.

The standard acceptance and residual rules preserve the target distribution:2

\[ \text{Acceptance Probability} = \min\left(1, \frac{p(x)}{q(x)}\right) \tag{14.1}\]

When a draft token x is rejected, a corrected token is sampled from the residual distribution:

\[ p'(x) = \frac{\max(0, p(x) - q(x))}{\sum_{y} \max(0, p(y) - q(y))} \tag{14.2}\]

For one position, a token x is proposed with probability q(x). Multiplying by its acceptance probability gives accepted output mass min(p(x), q(x)). Tokens with q(x) = 0 cannot be proposed. Let R be the rejection probability, 1 minus the sum of those accepted masses over the vocabulary. Since p sums to one, R is also the sum of max(p(x) - q(x), 0). When R > 0, rejection followed by residual sampling contributes R times p’(x) = max(p(x) - q(x), 0). Adding accepted and corrected mass gives p(x) for each token. If R = 0, p and q coincide and rejection cannot occur in exact arithmetic, so residual normalization is unnecessary.

Example: Where rejected probability goes

For an illustrative vocabulary (A, B, C), take p = (0.6, 0.3, 0.1) and q = (0.2, 0.5, 0.3) at one fixed prefix. The acceptance probabilities are (1, 0.6, 1/3). Multiplying each by its proposal probability gives accepted masses (0.2, 0.3, 0.1), totaling 0.6. Thus rejection occurs with probability 0.4.

The missing target mass is max(p - q, 0) = (0.4, 0, 0). Dividing by 0.4 gives residual probabilities (1, 0, 0): every rejection supplies A. The final output masses are (0.2, 0.3, 0.1) + 0.4 times (1, 0, 0) = (0.6, 0.3, 0.1), exactly p. Sampling ordinary p after rejection would instead produce (0.44, 0.42, 0.14), changing the target distribution.

This calculation explains the correction rule across repeated samples, not a requirement that a particular draft token equal the target’s most likely token. Applying the same rule at each retained prefix preserves the next-token distribution at every step. After the first rejection, later proposals have the wrong conditioning prefix and are discarded. If all proposals survive, the extra token is sampled directly from the target after that suffix.

A simple sequential cost model relates expected progress to the draft acceptance rate alpha, candidate length gamma, and draft-to-target cost ratio c. It assumes a constant independent acceptance probability, gamma sequential draft steps, and one target verification whose cost is approximated by one ordinary target step.

Every verification commits one correction token after a rejection or one extra target token after all proposals survive. Retaining at least i draft tokens requires the first i proposals to be accepted, with probability alpha^i under the model’s assumptions. Each retained position adds one token when reached. Averaging these contributions gives 1 + alpha + alpha^2 + … + alpha^gamma, the geometric sum written below:

\[ \text{Expected Tokens} = \frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} \tag{14.3}\]

Here c = time(M_q) / time(M_p) is the execution-time ratio of one draft step to one target step. In units of one ordinary target step, the draft costs gamma times c and verification costs one more. Dividing expected advance by this cost, gamma c + 1, gives the estimated speedup for long enough generations. Near the generation limit, there may be too few remaining tokens to obtain that average gain.

\[ \text{Speedup} = \frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(\gamma c + 1)} \tag{14.4}\]

As alpha approaches 1, the expected advance approaches gamma + 1 tokens. Real systems can deviate from this estimate because target verification cost changes with batch shape, removing KV entries computed for a rejected suffix (cache rollback) costs work, and requests do not share one constant acceptance probability.

Example: Estimating speculative speedup

Illustrative assumptions: Take gamma = 4 draft tokens, theoretical alpha = 0.8, and c = 0.2 draft-to-target cost ratio. These are assumed inputs to the cost model, not benchmark measurements.

Expected advance: 1 + 0.8 + 0.64 + 0.512 + 0.4096 = 3.3616, or 3.36 tokens per target verification. This is also (1 - 0.8^5) / (1 - 0.8). It includes the final target or residual-sampled token, not only accepted draft tokens.

Estimated speedup: 3.36 / (4 x 0.2 + 1) = 1.87x before rollback, scheduler overhead, cache maintenance, and batch-shape effects.

Validation: Compare the estimate with wall-clock target verification, draft work, rollback, and serving-scheduler time on the same prompt distribution.

The exact acceptance rule preserves the target distribution, but speed depends on accepted progress relative to draft, verification, rollback, and cache-maintenance cost. The next question is which draft design and candidate length minimize measured end-to-end latency for the actual prompt classes.

14.1.2 Implementation choices and measurement

The theoretical alpha is the mean conditional probability that a draft proposal is accepted at a prefix, under the independence assumptions used in the cost model. A mean retained-prefix length, even divided by gamma, is not that parameter: positions after the first rejection do not belong to the committed continuation.

The acceptance rule, the residual correction, and the exactness guarantee are defined in speculative decoding (Section 14.1). Three implementation choices remain:

  • Parallel verification: The target model evaluates the drafted suffix in one larger forward pass instead of one target pass per drafted token.
  • Lenience: A relaxation that can improve speed by accepting more tokens, but it no longer has the same exact-distribution guarantee and must be evaluated as a quality/speed trade-off.
  • N-gram or context-copy draft: A near-zero-cost approximator that proposes tokens from repeated recent context rather than a separate neural draft model. It is attractive when text has strong repetition and model loading a second draft is too expensive.

An example experiment pairs a larger target model with a smaller draft model and tokenizes the same fixed prompt sample from the intended text domain in both comparison arms. Keep the stopping rule, output-token count and timing interval the same for the target-only comparison. Record retained draft-prefix lengths separately from committed output-token counts and elapsed time, and report mean accepted-prefix length plus committed tokens per measured wall time. Coloring proposed tokens by accepted or rejected status shows whether progress comes from long accepted runs or occasional accepted proposals; measured time and committed tokens determine whether either pattern improves speed.

Speculative decoding helps when the draft is cheap, aligned with the target, and verification batches efficiently. It is weak when the target model is already saturated by a large batch, when the draft is inaccurate for the domain, when gamma is too large for the acceptance rate, or when KV-cache rollback and CPU sampling overhead dominate.

Accepted-prefix lengths show how far verification advances through each proposal. The table describes qualitative acceptance regimes, not an estimator of alpha from those lengths. Any engine-reported acceptance rate needs its own numerator, denominator, and treatment of positions after the first rejection. Draft cost, target batch efficiency, rollback cost, and serving-scheduler pressure determine whether that progress saves time.

Table 14.1: How speculative-decoding acceptance rate affects expected speed.
Acceptance-rate range What it means Likely speed result What to do
High Most drafted tokens survive target verification Speculation can reduce target-model passes if the draft is cheap and verification is batched well Increase candidate length carefully until rollback or verification cost grows
Medium Some runs are accepted but rejections are frequent Speedup is workload-dependent and may vary by prompt domain Measure by prompt class; tune candidate length, draft model, and batching policy
Low Draft proposals rarely match the target distribution Extra draft work and rollback can make decoding slower Use a better draft, reduce candidate length, or disable speculation for that traffic class
High acceptance but no speedup The target path is already saturated or overhead moved elsewhere Wall time stays flat despite good token acceptance Inspect GPU timeline, scheduler gaps, KV rollback, and CPU sampling work

For a speculative-decoding comparison, record proposed tokens, target verification, retained-prefix lengths, committed token counts, gamma, and measured wall time together. Theoretical alpha and c belong to the separate cost-model estimate. Acceptance alone is not evidence of faster service.

14.2 Constrained decoding

Constrained decoding restricts output to a structured language, such as a JSON schema, grammar, regular expression, or finite set of choices. It belongs to the serving-engine or decoder layer between model logits and token selection. The reliability benefit is valid structured output. The performance cost is maintaining one constraint state and valid-token mask per active request.

In a finite-state design, a state records progress through the permitted character sequence. A transition consumes a character along a labeled edge to another state. The current state determines which continuations remain possible. Some states also permit completion of the whole constrained output.

One implementation path from JSON schema to regular expression, finite-state machine, and logit mask represents one compiled-constraint design, following Efficient Guided Generation for Large Language Models3. A regular expression or finite choice set can use finite-state machinery directly with a vocabulary index over valid continuations. Nested JSON or general grammar constraints may instead need parser or grammar-stack state beyond finite-state scope. In each case, a constraint compiler produces runtime state that identifies which next-token byte sequences remain valid.

At every decode step, the constraint runtime keeps the current parser state, derives legal next terminals or byte prefixes, maps those possibilities to tokenizer IDs, constructs a vocabulary-sized valid-token mask, masks invalid logits, samples or selects one remaining token, and advances the parser state with that token. Tokenization matters because one vocabulary token can contain several characters or a partial structural sequence. Validity cannot be implemented as a simple one-character lookup.

Compiling the constraint, matching token strings to grammar continuations, constructing masks, and updating parser state add CPU or scheduler work. Requests with different constraint states may also fragment a batch. A validity gain does not imply a speed gain.

Checking a candidate token does not advance the request’s constraint state; only the selected token commits that change. The end-of-sequence token (EOS) is allowed only when the full constraint permits termination. An output-length limit can stop generation before that point and leave incomplete output.

Example: The age-field token walk

This simplified character machine checks one field fragment inside an object. The surrounding constraint has already consumed {" before state 0. The local machine then requires the key age, its closing quote, a colon, one or more digits, and a comma. It has these eight states and only these local edges:

Table 14.2: Character transitions in the age-field fragment.
State Progress so far Allowed next character and destination
0 Opening key quote consumed a -> 1
1 a consumed g -> 2
2 ag consumed e -> 3
3 age consumed " -> 4
4 Closing key quote consumed : -> 5
5 Colon consumed; no value digit yet Any digit 0 through 9 -> 6
6 At least one value digit consumed Any digit 0 through 9 -> 6; , -> 7
7 Field and following comma consumed Hand control to the surrounding object constraint

Unlisted local characters are rejected. This toy fragment has no whitespace edges. Its digit loop alone does not enforce JSON number syntax: for example, it would admit leading-zero digit strings. A full JSON or schema constraint must additionally enforce number syntax, any required value range, and the rest of the object. This machine demonstrates token matching, not a complete JSON validator.

For a vocabulary token whose decoded text is age, the runtime checks all three edges: a takes 0 to 1, g takes 1 to 2, and e takes 2 to 3. The token is allowed and its ending state is 3. Age and hou fail at their first character. A token beginning legally but containing a later illegal character must also be masked. These examples apply when the tokenizer contains the corresponding token IDs.

The runtime tests candidates from the same current state without committing their trial transitions. It sets each valid token ID’s mask entry to allowed, masks the others before selection, and updates the request’s state only for the selected token. Selecting age therefore commits state 3, where the next character must be the closing quote.

The closing quote moves 3 to 4, and the colon moves 4 to 5. For the value 27, 2 moves 5 to 6, 7 loops at 6, and the comma moves 6 to 7. The resulting prefix {"age":27, is not a completed JSON document. No local state 0 through 7 establishes whole-document completion. The end-of-sequence token (EOS) is allowed only when the full constraint permits termination, after the remaining fields and closing syntax. Ending at a length limit before that point produces incomplete output, not valid completion.

The schema can be compiled before requests arrive, and an engine may reuse token masks for repeated states. Each request still needs its own current state. The mask-build time, state-update time, constrained TPOT, and completion validity reveal the runtime cost of that work.

The practical question is whether validity is worth its decode overhead for the traffic class. Group requests with the same constraint when the engine supports it, precompile stable schemas, and measure constrained Time Per Output Token (TPOT) separately from unconstrained decode. Schema enforcement checks JSON structure. Application validation checks the business rules.

A useful cache hit, a long accepted draft prefix, or a valid structured response shows only part of the result. Their lookup, transfer, verification, and constraint costs also affect the time a user waits. Serving measurement and stack selection (Section 15.1) places those effects inside a fixed request workload and the service’s latency, quality, and cost requirements.

References


  1. Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023, Oral), preprint at Speculative decoding paper preprint (DOI), v1 submitted 2022-11-30, v2 revised 2023-05-18. Supports draft-then-verify with acceptance rule min(1, p(x)/q(x)) and residual sampling preserving the target distribution, plus the expected-token and speedup equations used in Section 14.1.1. Limit: reported 2 to 3 times acceleration on T5-XXL needs a cheap aligned draft and high acceptance; low acceptance or costly draft removes the gain.↩︎

  2. Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023, Oral), preprint at Speculative decoding paper preprint (DOI), v1 submitted 2022-11-30, v2 revised 2023-05-18. Supports draft-then-verify with acceptance rule min(1, p(x)/q(x)) and residual sampling preserving the target distribution, plus the expected-token and speedup equations used in Section 14.1.1. Limit: reported 2 to 3 times acceleration on T5-XXL needs a cheap aligned draft and high acceptance; low acceptance or costly draft removes the gain.↩︎

  3. Willard, B. T., & Louf, R. (2023). Efficient Guided Generation for Large Language Models. Preprint at Guided generation paper preprint (DOI), v1 submitted 2023-07-19, v4 revised 2023-08-19. Supports reformulating guided generation as finite-state transitions with an index over the model vocabulary and valid-token masking. Limit: finite-state scope covers regular expressions and finite choices directly; nested JSON or general grammars need additional parser or grammar-stack state, and overhead depends on schema and batching.↩︎