Advanced

Grammar-Constrained Decoding

Constrained decoding masks every token the grammar cannot accept before sampling, using an automaton compiled from a regex, JSON schema or context-free grammar. This page covers how the mask is computed fast enough to hide under a 5 ms decode step, why per-step masking does not sample from the model conditioned on the grammar, and how it interacts with speculation.

Get full Premium access · ₹2,000 / $25

Every worked answer and derivation in all 12 topics, every concept page, and the full practice-test bank.

6 months · One payment · No auto-renewal

RELATED CONCEPTS

Sampling: Temperature, Top-k and Top-p Speculative Decoding: The Algebra and the Proof The vLLM V1 Engine Architecture SGLang's Radix Cache and Overlap Scheduler Latency Decomposition: Queue, Prefill, Decode

PRACTICE THIS IN REAL QUESTIONS

Speculative & Constrained DecodingDerive the expected speedup of speculative decoding, prove it does not change the output distribution, and tell me when it stops paying.→Speculative & Constrained DecodingWhat do temperature, top-k and top-p each do to the next-token distribution, and in what order does a serving engine apply them?→Implement-from-Scratch CodingImplement batched top-p sampling with temperature. It must handle ties at the cutoff, p = 1, temperature 0 and masked tokens.→Implement-from-Scratch CodingImplement the lossless speculative sampling verifier for a batch with ragged draft lengths, and prove it matches the target.→KV Cache & GPU MemoryWith parallel sampling at n=8, a 2K-token prompt and 500 output tokens each, how many KV blocks does copy-on-write save?→Speculative & Constrained DecodingHow does grammar-constrained decoding build the allowed-token mask at every step, and what does that cost per step at batch 128?→