# Structured output and sampling

> From the AI Infrastructure Engineer Handbook, part "Serving engines". Web page: https://system.tangentbyte.com/learn/structured-output

The forward pass ends with a vector of logits, one score for every token in the vocabulary, and the engine still has to turn that vector into one token. Two pieces of an engine do that. The sampler applies the request's settings, temperature, penalties, top-k, top-p and min-p, and draws a token. Structured output, when a request asks for it, runs before the sampler: a grammar compiled from a JSON schema or a regular expression decides which tokens may come next, and every other token is removed. A request that asks for JSON then gets JSON that parses, matches the schema and can be handed to a program, every time the answer finishes.

Neither piece is expensive in the arithmetic sense, and both can still cost a service a lot. Top-p as written in the papers sorts the whole vocabulary, which on an H100 takes longer than the rest of the sampler together at large batches. A grammar check done naively walks 128,000 tokens through an automaton on the CPU for every sequence at every step. Engines have answers to both, and this chapter takes them apart and measures them.

After this chapter you can apply the sampler's steps in vLLM's order and say what each one costs, explain why top-p needs a sort and how engines avoid it, build a token mask from a grammar and explain why an index or a pushdown automaton makes it cheap, say where vLLM compiles grammars and computes masks and what that costs under load, recognize the tokenization traps of constrained decoding, and answer the interview question "will JSON mode slow down or hurt my model?" with measurements. The system design handbook covers the basics in [Sampling](https://system.tangentbyte.com/learn/llm-inference#sampling) and [Structured output](https://system.tangentbyte.com/learn/inference-engines#structured-output), and this chapter assumes both, along with [Build a mini inference engine](https://system.tangentbyte.com/learn/mini-inference-engine) and [Inside vLLM](https://system.tangentbyte.com/learn/inside-vllm). Everything about vLLM refers to **vLLM 0.32.0**, whose default model runner (Model Runner V2) keeps its sampler in `vllm/v1/worker/gpu/sample/`.

### From logits to a token

A step of the engine produces one row of logits for each sequence that is due a token, so the sampler works on a batch: a matrix of `[sequences, vocabulary]`, 128,256 columns wide for Llama 3. Every request in the batch can have different settings, so each setting is held as a column of per-request values and every operation is written for the whole matrix at once. A step that no request in the batch uses is skipped.

vLLM 0.32.0 applies the steps in this order, in `Sampler.apply_sampling_params` in `sample/sampler.py`, after copying the logits into a new float32 tensor.

_Diagram: From logits to a token in vLLM 0.32.0, for each sequence in the batch_ Logits from the forward pass -> Grammar mask (if constrained); Grammar mask (if constrained) -> Bias, penalties, bad words; Bias, penalties, bad words -> Temperature, min-p, top-k/p; Temperature, min-p, top-k/p -> One token per sequence (random draw)

| Step                                   | What it does to the logits                                                                                                                                            | Applies to                      |
| -------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------- |
| Grammar mask                           | Sets every token the grammar forbids to −∞. vLLM applies it in the model runner before the sampler is called.                                                         | Requests with structured output |
| Allowed tokens, logit bias, min tokens | Keeps only the listed tokens; adds the request's bias to chosen tokens; forbids stop tokens until `min_tokens` have been generated. One Triton kernel does all three. | Requests that set them          |
| Penalties                              | Repetition, frequency and presence penalties, described below.                                                                                                        | Requests that set them          |
| Bad words                              | Forbids token sequences the request listed.                                                                                                                           | Requests that set them          |
| Temperature                            | Divides the logits by T.                                                                                                                                              | All sampled requests            |
| min-p                                  | Removes tokens whose probability is below min_p times the top token's.                                                                                                | Requests that set it            |
| top-k, then top-p                      | Keeps the k most likely tokens, then the smallest set of the rest whose probability reaches p.                                                                        | Requests that set them          |
| Draw                                   | Picks one token at random from what is left, or the most likely one at temperature 0.                                                                                 | All                             |

The order matters wherever two steps do not commute. A logit bias adds and a repetition penalty divides, so the comment in vLLM's source notes that the two give different results in the other order. Temperature comes before the truncation steps, so a high temperature flattens the distribution first and min-p, top-k and top-p then cut what the flattening let into the tail. Logprobs, when a request asks for them, are taken by default from the logits before any of the sampler's steps (`logprobs_mode` is `raw_logprobs`), but after the grammar mask, which the model runner applied before calling the sampler.

#### Penalties

The **repetition penalty** comes from the CTRL paper (Keskar et al., 2019), which divided the logits of tokens already generated by θ and found θ ≈ 1.2 with greedy decoding "yields a good balance between truthful generation and lack of repetition". Dividing a negative logit by θ would raise it, so Hugging Face and vLLM both divide positive logits and multiply negative ones. Both also count the prompt's tokens as well as the output's: vLLM keeps a bitmask of each request's prompt tokens, 32 tokens to an int32 word, and combines it with a mask of the tokens generated so far (`sample/penalties.py`).

The **frequency and presence penalties** are OpenAI's. Its documentation defines them as `mu[j] -> mu[j] - c[j] * alpha_frequency - float(c[j] > 0) * alpha_presence`, where mu\[j] is token j's logit and c\[j] is how often the token has been sampled so far, and allows values from −2 to 2. The frequency penalty grows with each repetition, and the presence penalty is charged once. Neither counts the prompt.

Penalties need per-request state that the other steps do not: a count of every token in each request's output, kept on the GPU and updated each step. The nano_engine version in [sampler.py](https://system.tangentbyte.com/labs/infra/nano_engine/sampler.py) rebuilds those counts from Python lists every step, which is fine for a lab and would not be for a server.

#### Temperature and the truncation filters

Temperature divides the logits before the softmax, so T below 1 sharpens the distribution and T above 1 flattens it. vLLM treats a temperature of 0 as greedy decoding, and then also turns off top-p, top-k and min-p, which cannot change the argmax anyway. It raises any temperature above 0 and below 0.01 to 0.01, with a warning, because dividing by smaller numbers can overflow to infinity (`sampling_params.py`).

The three truncation filters remove the unlikely tail, which matters because the tail is long. For SmolLM2-135M after "My favourite food is", the 20 most likely tokens hold 25% of the probability, and the other 49,132 tokens hold the remaining 75%. Holtzman et al. showed that sampling from the full distribution produces incoherent text, because some draw eventually lands in that tail, and that greedy and beam search, which never sample, produce text that is "bland, incoherent, or gets stuck in repetitive loops".

- **Top-k** keeps the k most likely tokens. Fan, Lewis and Dauphin sampled from the 10 most likely when generating stories in 2018.
- **Top-p**, or nucleus sampling (Holtzman et al., ICLR 2020), keeps "the smallest set such that" the probabilities add up to at least p. Its argument against top-k is that a fixed k is wrong both ways: after "The Eiffel Tower is in the city of", SmolLM2 puts 79% on " Paris" and 23 tokens reach 90%, while after "My favourite food is" it takes 1,550 tokens to reach 90%. A k of 50 keeps, in the first case, 27 more tokens than the 23 that reach 90%, none above 0.21%, and in the second throws away 64% of the probability, much of it reasonable foods. Top-p adapts to the shape.
- **Min-p** (Nguyen et al., ICLR 2025) keeps tokens whose probability is at least min_p times the top token's. It adapts to the shape like top-p, but needs only the maximum of each row and no sort. Its authors recommend values of 0.05 to 0.1 and claim it keeps text coherent at temperatures of 2 to 3. A 2025 reanalysis by Schaeffer, Kazdan and Denisov-Blanch found that the paper's human evaluation had omitted data and that min-p did not beat the other methods once the number of tuned settings was controlled for, so treat its advantage as unproven and its low cost as certain.

After the filters, the surviving tokens' probabilities are rescaled to add up to 1. The widget in the Simulation section shows all three filters on real SmolLM2 distributions.

#### The draw

The last step picks a token. The textbook way, `torch.multinomial`, computes the cumulative sum of each row and searches it, and PyTorch's implementation synchronizes the GPU with the CPU. vLLM avoids it. Its older V1 sampler draws one exponential random number E per token and takes the argmax of p ÷ E, and its V2 sampler adds Gumbel noise to the logits and takes the argmax, which is the same trick in log space because a Gumbel variable is the negative logarithm of an exponential one (Maddison, Mnih and Teh, 2017, Section 3.1). Either way, token i wins with probability p_i, and the whole draw is one elementwise pass and one argmax.

The V2 kernel generates its noise without a random-number generator object. It hashes the request's seed, the token's position in the sequence and the vocabulary index with MurmurHash3 (`sample/gumbel.py`), and a request without a seed gets a random one. The noise a request sees therefore depends only on its own seed and position, not on which other requests share its batch.

#### The default you did not set

A request that sets no sampling parameters is not necessarily greedy, and is not necessarily sampled at temperature 1. vLLM's `--generation-config` defaults to `auto`, which reads the model's `generation_config.json` and uses its temperature, top-p, top-k, min-p, penalties and maximum length as the server's defaults, and logs a warning that it did so. Llama 3.1 8B Instruct's file sets temperature 0.6 and top-p 0.9, so a request to a stock vLLM server with no `temperature` field is sampled at 0.6 with top-p 0.9. Pass `--generation-config vllm` to get vLLM's own defaults (temperature 1.0, no truncation), which is what the lab's server does so that every request states its settings.

### What sampling costs

On the CPU, the cost of the sampler is easy to see. [structured_bench.py](https://system.tangentbyte.com/labs/infra/structured_bench.py) times each step of the nano_engine sampler on random logits on an M2, with PyTorch using 4 threads.

```
Sampling steps on the CPU (4 threads), median ms per call
   vocab  batch   argmax     draw    min-p  top-k 50  top-p 0.9  penalties
   49152      1    0.040    0.644    0.150     0.184      3.024      0.281
   49152     32    0.336   17.544    1.854     1.802     27.460      6.260
   49152    256    2.563  141.345   13.378    13.727    216.299     47.536
  128256      1    0.098    1.629    0.324     0.606      8.586      0.732
  128256     32    0.833   46.228    4.422     4.708     77.277     13.855
  128256    256    6.613  366.388   34.233    33.057    608.973    109.539
```

Top-p is the most expensive step by far, 0.6 s for 256 sequences of Llama 3's vocabulary, because finding "the smallest set whose probability reaches p" means sorting each row. The draw is second, because it generates one random number per token. At the batch sizes a server runs, the sort or the draw alone would take longer on a CPU than a whole decode step takes on a GPU.

On a GPU the same steps take microseconds, and the sort still stands out. [gpu/sampling_bench.py](https://system.tangentbyte.com/labs/infra/gpu/sampling_bench.py) times them with CUDA events on an H100, on float32 logits of Llama 3's vocabulary.

```
Microseconds per call on an H100, vocabulary 128,256          batch   1      8     64    256    512
argmax (greedy)                                                    34.6   34.8   35.2   60.5   97.8
softmax + torch.multinomial                                       123.1  121.2  223.4  559.9 1034.8
softmax + exponential race                                         73.9   78.6  159.8  431.3  823.2
Gumbel-max                                                         53.6   52.1  125.0  350.4  655.9
min-p 0.1 mask                                                     77.5   81.1  182.3  521.4 1001.4
top-k 50 mask (torch.topk)                                         95.8  107.2  252.2  778.6 1433.5
top-p 0.9 mask (full sort)                                        134.6  394.0 1262.5 4293.2 8443.7
top-p 0.9 mask (vLLM Triton)                                      176.6  176.2  581.9  672.1 1279.9
top-k 50 + top-p 0.9 mask (vLLM Triton)                           201.2  211.9  211.3  391.4  753.7
top-p 0.9 sample (FlashInfer)                                      66.3   84.5  136.0  310.0  554.9
top-k 50 + top-p 0.9 sample (FlashInfer)                          127.1  143.7  249.0  585.2 1089.4
clone of the logits (for scale)                                    12.7   12.7   30.3   94.7  180.8
grammar bitmask applied (xgrammar)                                 40.2   40.2   62.9  218.3  415.3
```

At 256 sequences, top-p by a full sort takes 4.3 ms, which is about a third of a decode step of Llama 3.1 8B at that batch size (13.7 ms, measured below). Engines have two ways around the sort, and vLLM uses both.

- **Find the threshold without sorting.** vLLM's default top-k and top-p masking is a Triton kernel (`ops/topk_topp_triton.py`, citing the Qrita paper's pivot-based truncation), which searches for the logit value that separates the kept tokens from the rest instead of ordering them all. It takes 0.67 ms at 256 sequences, a sixth of the sort.
- **Sample without finding the threshold at all.** FlashInfer's sampling kernels draw a token by rejection sampling: draw from the full distribution, and if the token falls outside the top-p set, raise a pivot and draw again from the tokens above it, until a draw is accepted. The FlashInfer team's 2025 post explains the dual-pivot version, which at least halves the candidate range each round, and reports that it cut vLLM's sampling time by more than half on an H100. Here it takes 0.31 ms at 256 sequences, a fourteenth of the sort. vLLM's V2 sampler uses it when some request sets top-k or top-p, no request in the batch is greedy or seeded, and logprobs are not requested in a processed mode (`VLLM_USE_FLASHINFER_SAMPLER` defaults to on); otherwise it masks with the Triton kernel and draws with its Gumbel kernel.

The cheapest steps are the ones the batch does not need, which is why every step checks whether any request in the batch uses it.

Does any of this show at the level of a server? The same script runs `vllm serve` with Llama 3.1 8B on the H100 and sends the same chat workload with seven settings, every answer 256 tokens long, with 1, 64 and 256 requests in flight.

| Setting                                                | Tokens/s, 1 in flight | 64 in flight | 256 in flight | Time per output token at 256 |
| ------------------------------------------------------ | --------------------- | ------------ | ------------- | ---------------------------- |
| Greedy                                                 | 160                   | 8,287        | 16,319        | 13.7 ms                      |
| Temperature 1                                          | 159                   | 8,342        | 15,732        | 14.2 ms                      |
| Top-p 0.9                                              | 159                   | 8,282        | 15,097        | 13.9 ms                      |
| Top-k 50                                               | 158                   | 8,304        | 16,314        | 13.5 ms                      |
| Top-k 50 and top-p 0.9                                 | 157                   | 8,197        | 15,755        | 13.6 ms                      |
| Min-p 0.1                                              | 151                   | 8,175        | 15,276        | 14.1 ms                      |
| Penalties (repetition 1.1, frequency and presence 0.5) | 159                   | 8,304        | 17,430        | 12.8 ms                      |

Every setting is within 7% of greedy at 256 requests in flight, and that is inside the run-to-run spread: each run takes 8 seconds, the penalties row came out fastest of all, and greedy itself, run again on a fresh server for the follow-up below, reached 18,729 tokens per second, 15% more than in this table. The sampler's few hundred microseconds are hidden inside a step of 13 ms, and the fused kernels keep them that way. The sort is what would have shown, and vLLM does not sort on a GPU.

One setting behaved differently. Requests with a seed of their own reached only 3,721 tokens per second at 64 in flight, against about 8,300 for every other setting, with the same time per output token; the difference was all in the wait for the first token, a median of 1.7 s against 0.1 s. vLLM's log says why: "Triton kernel JIT compilation during inference: \_gumbel_sample_kernel", with the advice to extend the warm-up to cover "this shape/config". Seeded requests needed a configuration of that kernel which the server's warm-up had not compiled, and the first of them waited while Triton compiled it. A follow-up run that sent the seeded requests twice on the same server confirms it: the second time, seeded requests at 64 in flight got 7,801 tokens per second and a median first token of 93 ms. The lesson is general to engines that compile kernels on demand: warm up with the settings production traffic uses, or the first users pay for the compile.

### Constraining the output to a grammar

Structured output adds one step before the sampler. The engine keeps, for each constrained sequence, the state of an automaton built from the grammar, and before sampling it sets the logit of every token the automaton would reject to −∞. Whatever the temperature, top-p or penalties, a forbidden token has probability 0, so every token drawn keeps the output a valid prefix of something the grammar accepts. When the grammar reaches its end, the only token allowed is the end-of-sequence token.

The hard part is that the grammar is written over characters and the model chooses tokens. A token can hold several characters, part of one grammar element and part of the next: SmolLM2's vocabulary has `{"`, `":`, `",` and `"",` as single tokens, so the token after `"name` can close the key and start the separator at once. To decide whether a token is allowed, the engine has to run each of its characters through the automaton, starting from the sequence's current state. Doing that for every token of the vocabulary at every step is the naive mask.

#### The naive mask

[constrained_decoding.py](https://system.tangentbyte.com/labs/infra/constrained_decoding.py) builds it from scratch. Its `compile_schema` turns a small JSON schema (a name, an age, a city from a list of six, and a boolean) into a deterministic finite automaton over characters, with the layout fixed to one line, and `mask_naive` walks every token of SmolLM2's 49,152 through it.

```
Automaton: 86 states. Vocabulary: 49,152 tokens, 48,835 usable

Walking the whole vocabulary in one state (no index), along {"name": "Kwame Holm", "age": 26, "city": "London", "member": true}
  after ''                                2 tokens allowed,    7.2 ms
  after '{"name": '                      45 tokens allowed,    7.1 ms
  after '{"name": "Ma'               48,557 tokens allowed,   82.8 ms
  after '": "Kwame Holm", "age": '       11 tokens allowed,    9.9 ms
  after 'm", "age": 26, "city": "'       14 tokens allowed,    7.4 ms
```

The 317 tokens the script calls unusable are special tokens and tokens that hold only part of a multi-byte character, which a character-level automaton cannot judge. Real engines run their automata over bytes for this reason.

Two things stand out. Most states allow very few tokens, and one state, inside a string, allows almost all of them. And even the narrow states cost 7 ms, because finding out that a token is not allowed still means looking at it. In Python that is 7 to 83 ms per sequence per step, more than a whole decode step of the 8B model on an H100. Compiled code would be much faster, but the work would still grow with the size of the vocabulary and the number of sequences, at every step, which is why engines move it to compile time.

#### An index per state: Outlines

Willard and Louf (2023), the authors of Outlines, observed that the walk depends only on the automaton's state and the token, not on anything the model has done. So it can be done once for every state, before decoding starts, and kept: for each state, the mask of allowed tokens and the state each allowed token leads to. Decoding then costs one lookup per step, O(1) where the naive mask is O(vocabulary). Outlines turns a JSON schema into a regular expression and the expression into an automaton like the lab's, then builds this index.

```
Index: built in 0.7 s for 86 states; allowed tokens per state: median 2, max 48,557; 50,926 (state, token) entries in the tables
Masking with the index took 0.099 ms per step (median); without it, the walk above takes tens of milliseconds per step
```

The price is paid at compile time, once per schema, and it grows with the number of states. The lab's schema has 86 states because it is tiny and its layout is fixed. A schema with optional fields, free whitespace, nested objects, numbers with ranges or strings with length limits multiplies them, because a regular expression can only remember where it is by having a separate state for every situation. A recursive schema, such as a tree whose nodes contain nodes, cannot be written as a regular expression at all, and has to be cut off at some depth. JSONSchemaBench (Geng et al., 2025) measured a median compile time of 3.5 to 8 seconds for Outlines on its real-world schema collections, and some features took from 40 seconds to 10 minutes.

#### A pushdown automaton and a split vocabulary: XGrammar

JSON is not a regular language, because brackets nest, and the natural automaton for it is a pushdown automaton: a finite automaton with a stack, which pushes when it enters an object or array and pops when it leaves. XGrammar (Dong et al., MLSys 2025) runs grammars as byte-level pushdown automata, and its main idea is about which work can be done ahead of time.

For most tokens, whether they are allowed depends only on the top of the stack, the rule the automaton is inside right now. Inside a string, any token made of string characters is allowed, whatever the string is nested in. XGrammar calls these tokens context-independent and precomputes their status for every grammar position, in what it calls the adaptive token mask cache. Only the tokens that would finish the current rule and pop back into the parent need the whole stack to judge, and the paper calls them context-dependent. For Llama 3.1's vocabulary and the JSON grammar, the paper counts "less than 1% (1134 out of 128k)" context-dependent tokens. At each step, XGrammar takes the precomputed mask for the current position and checks only those few tokens against the real stack.

The paper describes three more pieces. The cache stores, for each position, whichever of the accepted or rejected sets is smaller, which it reports shrinks the cache from 160 MB to 0.46 MB. The stacks of all the paths the automaton might be in share one tree, so a rollback is a pointer change. And the vocabulary is checked in sorted order, so tokens with a common prefix share the work of matching it. Its measured mask time is 36 µs per token for a JSON schema with Llama 3.1's vocabulary on a desktop CPU (Figure 9), up to 3 times faster than the best earlier engine on JSON schemas and over 100 times faster on context-free grammars.

On the M2, with the order schema of the next sections, xgrammar 0.2.8 compiles the schema in 2 ms for SmolLM2's vocabulary and 5 ms for Llama 3's, and fills one sequence's mask in a median of 3 to 4 µs, at most 23 µs, over a whole answer. That schema is simpler than the paper's benchmark, and the numbers show how small the per-step cost becomes once the precomputation has been done.

llguidance, from the Guidance project, takes the other route: no precomputation, and a fast check at every step. It parses with an Earley parser over a lexer built from regular-expression derivatives, walks a trie of the vocabulary so that a rejected prefix rules out every token that starts with it, and its README reports about 50 µs of one CPU core per mask for a 128,000-token vocabulary with "no significant startup cost". The README also records that llguidance shipped in OpenAI's API for JSON schemas in May 2025.

The mask itself is a bitmask: one bit per token, 32 tokens to an int32 word, so a row for Llama 3 is 4,008 words, 16 KB. Applying it to the logits is one elementwise kernel, which took 40 µs for one sequence and 218 µs for 256 in the H100 table above.

### Structured output inside vLLM

A request asks for structured output in one of two ways. OpenAI's `response_format` takes `{"type": "json_schema", "json_schema": {"schema": ...}}` or `{"type": "json_object"}`, which vLLM compiles as the schema `{"type": "object"}`. vLLM's own `structured_outputs` field also takes `regex`, `choice` (a list of strings, which the xgrammar backend turns into a grammar), `grammar` (EBNF or Lark) and `structural_tag`. Only one kind is allowed per request.

The backend is chosen per server, with `--structured-outputs-config '{"backend": ...}'`: `xgrammar`, `guidance` (llguidance), `outlines` (its Rust core) or `lm-format-enforcer`. The default, `auto`, uses xgrammar when it supports the request and falls back to guidance, or to outlines in some cases, for schemas with features xgrammar lacks, such as `multipleOf`, `uniqueItems` or most string formats (`backend_xgrammar.py`). The structured-output manager creates one backend for the whole server, and a request cannot choose its own.

_Diagram: Structured output in vLLM 0.32.0. The grammar is compiled off the scheduler's path, and the mask is filled while the GPU runs the step_ Request with a JSON schema -> Compile pool (threads) (schema); Compile pool (threads) -> Scheduler (engine core) (grammar); Scheduler (engine core) -> GPU worker forward pass (launch step); Scheduler (engine core) -> Mask kernel, then sampler (bitmask); GPU worker forward pass -> Mask kernel, then sampler (logits)

Follow one request through the source.

1. **Compile.** When the engine core receives the request, its structured-output manager submits the grammar to a thread pool of half the machine's cores (`structured_output/__init__.py`), and the request waits with the status `WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR`. The scheduler skips it on every step until the compile finishes and schedules everyone else, so a slow compile delays only its own request. xgrammar keeps compiled grammars in a cache of up to 512 MB (`VLLM_XGRAMMAR_CACHE_MB`), keyed by the schema's text, so a second request with the same schema does not compile again. A grammar that fails to compile finishes the request with an error.
2. **Fill the mask while the GPU works.** The engine core's step launches the forward pass without waiting for it (`execute_model(..., non_block=True)`), then calls the scheduler's `get_grammar_bitmask`, which fills one row per constrained sequence on the CPU, and only then asks the worker to sample with that bitmask. As long as filling the masks takes less time than the forward pass, it costs nothing. With more than 128 constrained requests in a batch and no speculative decoding, the rows are filled by a second thread pool, in groups of 16.
3. **Apply.** The worker copies the bitmask to the GPU on a side stream and applies it with a Triton kernel adapted from xgrammar's, before the sampler runs.
4. **Accept.** After the step, the scheduler advances each matcher by the token it produced. A token the matcher rejects, which would be a bug, finishes the request with an error. The request finishes normally through the usual stop check: the grammar allows the end-of-sequence token only once the output is complete.

Two interactions are worth knowing. With asynchronous scheduling, which is on by default, the engine prepares step n + 1 before step n's tokens are known, and a constrained request's mask for n + 1 depends on its token from step n; vLLM therefore holds back the sampling of a step that contains such a request until the previous step's output has been processed. With speculative decoding, the mask has one row per draft position: the scheduler advances the matcher through the draft tokens to fill the rows, then rolls it back, and the matcher is created able to roll back as many tokens as the draft is long. For reasoning models with a reasoning parser configured, the grammar starts only after the end-of-thinking token, so the model can reason freely and then answer in the required format.

vLLM has no jump-forward decoding, described below. Its xgrammar and guidance backends carry comments that it could be added. SGLang 0.5.23 still has jump-forward code in its grammar backends, but nothing in its scheduler calls it.

#### What it costs on an H100

The order workload of the lab asks Llama 3.1 8B to read a short paragraph, such as "Hello, this is Hiro Adeyemi (<hiro.adeyemi@example.com>). Please send me 2 folders at $25.30 each and 1 ruler at $37.72 each. Standard shipping is fine.", and return it as JSON with a customer, an email, a list of items with a product, quantity and unit price, and an express flag. [gpu/sampling_bench.py](https://system.tangentbyte.com/labs/infra/gpu/sampling_bench.py) runs it with no constraint, with any JSON object, with one schema shared by every request, and with a schema of its own for every request, which forces a compile per request, all greedy, at 1, 64 and 256 requests in flight.

| Backend, mode                      | Time per output token, 1 / 64 / 256 in flight | Median first token at 256 | Schema-valid / values right |
| ---------------------------------- | --------------------------------------------- | ------------------------- | --------------------------- |
| No constraint                      | 6.20 / 7.39 / 14.07 ms                        | 659 ms                    | 100% / 100%                 |
| xgrammar, any JSON object          | 6.22 / 7.58 / 13.73 ms                        | 381 ms                    | 100% / 100%                 |
| xgrammar, one schema               | 6.23 / 7.50 / 13.38 ms                        | 398 ms                    | 100% / 100%                 |
| xgrammar, a new schema per request | 6.22 / 7.50 / 13.06 ms                        | 503 ms                    | 100% / 100%                 |
| guidance, one schema               | 6.23 / 7.92 / 17.71 ms                        | 462 ms                    | 100% / 100%                 |
| outlines, one schema               | 6.23 / 36.05 / 128.86 ms                      | 705 ms                    | 100% / 94%                  |

Time per output token is the reliable column. The runs at 256 in flight last under two seconds each, too short for steady throughput or first-token figures. The unconstrained row's 659 ms is not a cost of having no grammar: it was the first run at that concurrency on that server, and the constrained runs after it were faster. With xgrammar, the constraint costs nothing measurable at any concurrency, even when every request brings a schema that has to be compiled. Guidance costs nothing at one request in flight and about 30% per token at 256. Guidance computes every mask at run time, so the likely reason is that filling 256 of them on the 4 CPU cores the container reserves no longer fits inside a 13 ms step. The outlines backend is in another class: 36 ms per token at 64 in flight and 129 ms at 256, five and nine times the unconstrained step, while it costs nothing at one request. A cost that is absent for one request and grows with the number in flight is a per-request CPU cost paid on every step, and here it was far larger than the step itself.

The outlines rows also got 6% of values wrong where every other row got none. Its answers came out on one line, `{"customer": "Priya Moreau", ...}`, where Llama by itself writes indented JSON, and in the two wrong answers among those the run saved, the model went on after the last real item and added one more, `{"product": "express shipping", "quantity": 1, "unit_price": 0}` and `{"product": "shipping", ...}`. A layout the model does not use pushed it off course, the effect the next section measures in a small model.

Compiling costs little once a backend is running. At one request in flight, a schema the server had never seen raised the median time to the first token from 15.5 ms to 18.3 ms with xgrammar, and from 17.7 to 17.9 ms with guidance. The very first structured request after the server starts is different, because the manager builds the backend then, including its view of all 128,256 tokens of the vocabulary: it waited 0.64 s for its first token with xgrammar, 3.0 s with guidance and 0.9 s with outlines, against 18 to 20 ms for the same request repeated. A warm-up request with a schema belongs in a server's start-up for that reason.

The last column says the constraint did not change a single answer's correctness here: Llama 3.1 8B already writes this JSON correctly without it, with its own indentation. At this scale structured output is insurance against the rare malformed answer and a contract for the program reading the output. The model in the next section is the case it is built for.

### Tokens and text do not line up

A constraint guarantees that the text is valid. It does not guarantee that the tokens are the ones the model would have chosen for that text, and the gap causes most of the surprises of constrained decoding.

#### Non-canonical tokens

A tokenizer splits a given text one way, and a model is trained on text split that way. The model does not always reproduce that split when it writes: unconstrained, SmolLM2 writes `[` and then `{"` where the tokenizer writes `[{` and then `"`, and only 9 of its 48 free answers in the nano_engine run below match the tokenizer's split token for token. A constraint adds splits the model would not have chosen either, and then it is reading a token sequence it would not have produced itself. In the lab's from-scratch run, every one of the 12 constrained answers of SmolLM2-135M differed from the tokenizer's own split of the same text, and all 12 at the same place: the tokenizer writes the opening `{"` as one token, and the model wrote `{` and then `"`. In 11 answers that was the only difference; the twelfth also spelled a name as `Am` `ara` where the tokenizer writes `A` `mar` `a`, a choice the model made by itself inside a free string.

The reason is visible in the step-by-step record that the second widget shows. At the first step the model's favourite is `{`, at 47%, and the grammar allows it, since `{` is a valid start. At the second step the model's favourite is a newline, at 65%: unconstrained, it lays JSON out over several lines. The lab's grammar fixes the layout to one line, so the only allowed token is `"`, to which the model gave 0.05%. The token is forced, the text is valid, and the split is one the tokenizer never produces. The effect here is harmless, but the general point stands: a grammar that disagrees with the model's habits forces tokens the model gave almost no probability, and everything the model writes afterwards is conditioned on a sequence it would not have written.

This is one argument for letting a JSON grammar allow whitespace, which vLLM's xgrammar and guidance backends do unless `disable_any_whitespace` is set: Llama 3.1 8B's constrained answers on the H100 came out indented, as it writes them unconstrained. The argument against is that a small model can then emit whitespace until it runs out of tokens. Guidance's token healing addresses the same mismatch at the prompt boundary: it backs up one token before the end of the prompt and constrains the first generated token to start with the removed text, because a prompt that ends in "http:" was split before ":" where the model would have chosen "://".

#### Jump-forward decoding

Much of a JSON answer is fixed by the schema. After `"Kwame Holm"`, the next text must be `, "age": `, and there is nothing for the model to decide. Jump-forward decoding, introduced with SGLang's compressed finite-state machine in 2024, appends such forced text without sampling it: the tokens still run through the model so that their keys and values are in the KV cache, but all in one step, like a chunk of a prompt, instead of one step each. The SGLang post reported latency cut by up to 2 times and throughput raised by up to 2.5 times on its JSON benchmark.

The forced text has to be turned into tokens, and the tokenizer's split of it in isolation may not be how the model would have split it in context. The dangerous token is the last one: forced text ending in `": "` might be followed by a word the tokenizer would merge with the quote. SGLang's fix was to append the text and retokenize the whole output. nano_engine's implementation in [structured.py](https://system.tangentbyte.com/labs/infra/nano_engine/structured.py) uses the simplest safe rule: tokenize the forced text and leave off its last token, so that the model chooses the boundary.

#### Measured in nano_engine

[structured_bench.py](https://system.tangentbyte.com/labs/infra/structured_bench.py) runs 48 orders through nano_engine with SmolLM2-135M-Instruct on the M2's CPU, seven ways, with at most 160 output tokens each. "Canonical" counts the answers whose tokens are exactly the tokenizer's split of their text; "fill" and "apply" are microseconds per constrained sequence per step.

```
48 orders, SmolLM2-135M-Instruct on the CPU, max_tokens 160
mode                       parses  schema  fields right  at max  tokens  steps  tok/s  fill us  apply us  canonical
free, greedy                   29       0          0.0%      16    5095    163    351                             9
free, T=0.8                     5       0          0.0%      31    6212    163    309                            31
any JSON object, greedy        31       0          0.0%      17    5072    163    353        6        54          9
schema, greedy                 29      29         31.2%      19    5778    163    354        5       157          0
schema, T=0.8                  34      34         18.8%      15    5884    163    294        5       159          1
schema, any whitespace         30      30         32.3%      18    5853    163    361        5       155          6
schema, jump-forward           42      42         46.4%       6    4823    139    352        6       106          9

schema, jump-forward: 1822 of 4823 output tokens were forced by the grammar and appended without sampling
jump-forward and plain constrained decoding gave identical text for 20 of 48 orders
```

Read the table from the top. Without a constraint, a 135-million-parameter model produces JSON that parses 29 times in 48 and matches the schema never: it invents keys, puts the email in the customer field and turns the items into strings. Asking for any JSON object changes almost nothing, because the answers that failed were mostly cut off, not malformed. With the schema, every answer that finished matches it, and 29 of 48 finished. The other 19 hit the limit of 160 tokens inside the items array, where the model kept adding items, and an answer cut off mid-array is not valid JSON however it was constrained. The guarantee holds only for answers that end. Of the values, 31% are right: the constraint fixes the shape and does nothing for the content, and a model this small still puts the email in the customer field or turns the product into the whole sentence it came from.

Masking costs 5 µs per sequence per step to fill with xgrammar and about 155 µs to apply to the logits on the CPU. Neither is visible in the throughput, which is set by the model.

Jump-forward forced 38% of the output tokens, and those tokens did not need a step each, so the longest request finished in 139 steps instead of 163. It also changed the text of 28 of the 48 answers, which it would not do if forced tokens were the tokens the model would have chosen. The canonical column shows why: plain constrained decoding produced the tokenizer's own split in 0 of 48 answers, and jump-forward, which tokenizes the forced text with the tokenizer, in 9. In all 48 answers the tokens first differ at the start of the items array, where the model by itself writes `[` and `{"` and jump-forward appends the tokenizer's `[{` and `"`; in 20 of them the text came out the same anyway. In this run the changed answers were better, 42 valid instead of 29, mostly because fewer of them looped in the items array, but that is a property of this model and workload. Jump-forward changes the model's input, and has to be evaluated like any other change to it.

### Does a constraint hurt quality?

The guarantee is about format, and the obvious worry is that forcing a format makes the content worse. Tam et al. (2024), "Let Me Speak Freely?", reported large drops on reasoning tasks under format restrictions; for example gpt-4o-mini scored 94.6% on GSM8K answering in natural language and 87.0% in JSON mode. The team behind Outlines replied in "Say What You Mean" that the comparison used different prompts for different formats and counted JSON mode, which guarantees nothing, as structured generation; rerunning with matched prompts on Llama 3 8B Instruct, they measured 0.78 on GSM8K with structured generation against 0.77 without. JSONSchemaBench found constrained decoding slightly better on GSM8K for every framework it tested, 83.8% for guidance and 83.7% for xgrammar against 80.1% unconstrained.

Three points survive the argument. A schema that puts the answer before the reasoning forces the model to answer before it has reasoned, so put any reasoning or explanation field first. A layout the model would not write by itself pushes it off its training distribution, as the non-canonical tokens above show, so prefer schemas close to how the model already formats JSON. And measure on your own task with and without the constraint, as the H100 runs above did, rather than trusting either side's benchmark.

### Simulation

The first widget applies the sampler's filters to real next-token distributions of SmolLM2-135M for three prompts, from a peaked one to a flat one, in vLLM's order: temperature, then min-p, then top-k, then top-p.

Try these, in order.

1. On the peaked prompt, with no filter at temperature 1, read how much probability lies outside the 20 tokens shown. Switch to the flat prompt and read it again.
2. Set top-k to 50 and switch between the two prompts. On the peaked one, read under the bars how little probability the 30 kept tokens beyond the 20 shown hold between them; on the flat one, read how much probability top-k 50 throws away. This is Holtzman's argument against a fixed k.
3. Turn top-k off and set top-p to 0.9. Compare the number of kept tokens on the two prompts, and press "Draw 12 tokens" a few times on each.
4. Set temperature to 2 with no filter on the flat prompt, and draw. Then add min-p 0.1 and draw again. Raise the temperature to 3 and watch how many tokens min-p keeps.
5. With top-p 0.9 on the peaked prompt, lower the temperature to 0.5. The kept set shrinks, because temperature comes first and sharpens the distribution that top-p then measures.

The second widget replays one constrained answer of SmolLM2-135M-Instruct step by step, with the lab's automaton: at each step the model's six favourite tokens, which of them the grammar allows, how many tokens it allows in all, and the text it forces from that point.

1. Step through the first two tokens and find the step where the grammar overrules the model.
2. Step into the name and read how many tokens are allowed inside a string. Compare with the steps between fields.
3. Find the step where the model wanted to open a string for `member`, as its unconstrained answer at the bottom does, and see what the grammar left it.
4. Count the steps that only copy forced text, shown dimmed once passed. These are what jump-forward decoding would skip.

### Lab: a constrained decoder from scratch, then nano_engine and vLLM

**Tier: \[Mac] for Parts A and B, \[1 GPU] for Part C.**

**Part A, from scratch.** [constrained_decoding.py](https://system.tangentbyte.com/labs/infra/constrained_decoding.py) needs PyTorch and Transformers, and downloads SmolLM2-135M-Instruct on first use.

```
python constrained_decoding.py          # about 20 seconds on an M2
python constrained_decoding.py --test   # only the self-checks
```

Read `compile_schema`, `mask_naive` and `Index`, then do four things. First, before running, predict how many tokens are allowed right after `"age": `and right after the opening quote of the name, and explain the difference. Second, write `mask_trie`: build a character trie of the vocabulary once, then walk it together with the automaton, so that a character the automaton rejects rules out every token below that point of the trie. Check that it returns the same mask as `mask_naive` in every state, and time both in the five states the script prints and over all 86. Third, add `maxLength` for strings to `compile_schema` and count the states for the person schema with a name of at most 30 characters; explain what that does to the index. Fourth, explain why the script's automaton could not represent a schema in which an item can contain a list of items, and what XGrammar does instead.

**Part B, nano_engine.** This chapter adds two files to nano_engine and extends three others. [sampler.py](https://system.tangentbyte.com/labs/infra/nano_engine/sampler.py) implements penalties, temperature, min-p, top-k, top-p and the exponential-race draw. [structured.py](https://system.tangentbyte.com/labs/infra/nano_engine/structured.py) compiles a request's `json_schema`, `regex` or `grammar` with xgrammar, fills and applies the masks, and implements jump-forward decoding behind `EngineConfig(jump_forward=True)`. `SamplingParams` and the server accept the new fields, including OpenAI's `response_format`. The engine's tests check the sampler's arithmetic and that constrained answers always parse.

```
pip install -r requirements.txt                     # now includes xgrammar 0.2.8, the version vLLM 0.32.0 pins
python -m nano_engine.test_nano_engine              # 13 tests, about a minute
python structured_bench.py engine                   # about 2 minutes on an M2
python structured_bench.py sampler                  # about 30 seconds
python -m nano_engine.server --jump-forward         # then send response_format requests with curl
```

From your run, reproduce the table of "Measured in nano_engine", then answer three questions. Why do 19 constrained answers still fail to parse, and what one change to the schema fixes most of them? Measure it. Why does jump-forward change the text of answers that are greedy and deterministic? Find one answer where it did, and the first token at which the two versions differ. And in `structured.py`, the mask is filled after the forward pass; what would it take to fill it during the forward pass, as vLLM does, and what does the GIL have to do with whether that helps?

**Part C, the GPU.** The script is [gpu/sampling_bench.py](https://system.tangentbyte.com/labs/infra/gpu/sampling_bench.py), with three parts: the sampling kernels, the sampling settings on a server, and the structured-output backends on a server.

```
cd gpu
modal run modal_run.py --script sampling_bench.py --gpu 'H100!' --vllm                    # 11 min, $0.72
modal run modal_run.py --script sampling_bench.py --gpu 'H100!' --vllm --args "--parts sampling --settings 'greedy;T=1, top-p 0.9, seeded;T=1, top-p 0.9, seeded, again' --tag h100_seeded"   # 4 min, $0.29
modal run modal_run.py --script sampling_bench.py --gpu A10 --vllm --args "--quick"          # not run for this chapter
python gcp_run.py --script sampling_bench.py --gpu L4 --vllm --args "--quick" --max-hours 2   # building the image takes about 20 min; an L4 hour is about $0.55 of GCP credit
```

From your runs, fill in the kernel table, the sampling-settings table and the structured-output table, then answer four questions. At what batch size does a sorting top-p cost more than 10% of a decode step of the 8B model on your GPU? Why does FlashInfer's sampler stop being used when one request in the batch is greedy? On your hardware, at what concurrency does the guidance backend start to cost time per token, and what in the machine would you change to push that point higher? And what would you measure in production to know whether structured output is costing your service anything?

Reference solution

_Part A._ After `"age": `the automaton is at the start of an integer, so the allowed tokens are those made only of digits, possibly after a minus sign, and possibly ending in the `,` that follows the value. Inside a string, any token made of string characters is allowed, and so is any token that closes the string and continues correctly. The script prints 11 and 48,557.

A trie-walking `mask_trie`, written as a stack of (trie node, automaton state) pairs that skips a child as soon as the automaton rejects its character, gives the same mask in every state. Its times on the M2, against `mask_naive`:

```
trie built in 0.13 s
''                           naive    7.6 ms  trie   0.17 ms  trie edges visited 456 of 330,856 chars
'{"name": '                  naive    7.2 ms  trie   0.24 ms  trie edges visited 498 of 330,856 chars
'{"name": "Ma'               naive   82.9 ms  trie 137.01 ms  trie edges visited 99,601 of 330,856 chars
'": "Kwame Holm", "age": '   naive    9.8 ms  trie   0.15 ms  trie edges visited 461 of 330,856 chars
'm", "age": 26, "city": "'   naive    7.2 ms  trie   0.15 ms  trie edges visited 635 of 330,856 chars
all 86 states via trie: 0.14 s
```

In a narrow state the trie looks at about 500 edges instead of 330,856 characters and is 40 to 60 times faster, because one rejected first character rules out thousands of tokens. Inside the string almost nothing is rejected, the trie visits a third of all characters, and its per-edge overhead in Python makes it slower than the plain loop. Building the whole index takes 0.14 s instead of 0.7 s. The two kinds of state are exactly XGrammar's split: positions where few tokens survive, which are cheap to check at run time with a trie, and positions where nearly every token survives, whose answer depends only on the position and is worth precomputing.

A string with a `maxLength` of 30 needs a separate state for each length so far, since the automaton must know when to forbid another character, so the name alone becomes about 31 states, each allowing nearly the whole vocabulary, and the index grows by about 30 copies of the largest mask. Limits on lengths and numeric ranges are what make regular-expression indexes large.

A list of items in which an item can contain a list is recursive, and a finite automaton has no memory of how deep it is, so it can only represent a fixed number of levels, each with its own copy of the states. XGrammar keeps the nesting on a stack, as a parser does, and precomputes everything that depends only on the top of the stack.

_Part B._ Adding `"maxItems": 3` to the items array is the change. With it, 45 of 48 answers match the schema and 48.4% of fields are right, against 29 and 31.2% without it, and only 3 answers hit the 160-token limit; with jump-forward as well, 45 and 49.0%. The model kept appending items because the grammar always allowed another one, and a limit in the schema becomes a limit in the grammar.

Jump-forward changes greedy answers because it changes the tokens the model reads. Plain constrained decoding lets the model choose how to split forced text, and SmolLM2 opens the items array with `[` and `{"`, a split the tokenizer does not produce; jump-forward appends the tokenizer's split, `[{` and `"`. That is where the tokens of the two versions first differ, in all 48 answers. From there on, the model is conditioned on different input, and greedy decoding follows.

Filling the mask during the forward pass needs the forward pass to run without holding up the Python thread that fills masks. On a GPU the forward pass is asynchronous: the CPU launches kernels and continues, so the fill can run between the launch and the synchronization before sampling, which is what vLLM's `execute_model(non_block=True)` arranges. On the CPU, the forward pass runs in the same thread, so the fill would need a second thread, and it helps only if both PyTorch's kernels and xgrammar's fill release the GIL while they work, as their C++ code does.

_Part C._ The reference results are [sampling_bench_h100.json](https://system.tangentbyte.com/labs/infra/gpu/sampling_bench_h100.json) and [sampling_bench_h100_seeded.json](https://system.tangentbyte.com/labs/infra/gpu/sampling_bench_h100_seeded.json), the seeded settings repeated on a warm server, and the sections above explain them. On the H100, a sorting top-p crosses 10% of a decode step of the 8B model between 8 and 64 sequences: 0.39 ms against a step of about 6.3 ms at 8 (the step measured at one request in flight, which 8 barely lengthens), and 1.3 ms against 7.4 ms at 64. That is why vLLM does not sort. FlashInfer's sampler draws the token itself, while greedy rows need a plain argmax and vLLM's V2 sampler runs one path for the whole batch, so a single greedy or seeded request sends the batch down the Triton mask and Gumbel kernel instead. Guidance's per-token cost appeared at 256 requests in flight on 4 reserved cores; more cores, fewer constrained requests per server, or xgrammar raise that point. In production, watch time per output token for constrained against unconstrained requests at the same load, the time requests spend waiting for a grammar (the gap between arrival and first schedule for constrained requests), and the compile cache's hit rate, which is the share of requests whose schema the server had already seen.

### Interview angle

"Walk me through what happens between the logits and the next token" is a warm-up that separates people who have read a sampler from people who have used one. Give the steps in order: grammar mask, logit bias and allowed tokens, penalties, temperature, then the truncation filters and the draw. Say why the order matters: temperature before truncation, penalties before temperature, and the grammar before everything, so that no setting can resurrect a forbidden token. Then name the cost: everything is elementwise except top-p, which needs a sort unless the engine uses a pivot search or rejection sampling, and the draw is an exponential race or Gumbel-max rather than `torch.multinomial`. On an H100 a sorting top-p took 4.3 ms for 256 sequences of Llama 3's vocabulary and FlashInfer's sampler 0.3 ms.

"How does constrained decoding work, and why isn't it slow?" is the main question. The mechanism is a mask of −∞ over forbidden tokens before sampling. The difficulty is that tokens and grammar symbols do not align, so a naive mask walks the whole vocabulary through the automaton at every step. The answers are precomputation: Outlines indexes every state of a finite automaton ahead of time; XGrammar runs a pushdown automaton and precomputes the context-independent tokens, which are more than 99% of Llama 3's vocabulary for JSON, leaving about a thousand to check per step; llguidance skips precomputation and makes the per-step check fast with a token trie. Then the engine part: vLLM compiles grammars in a thread pool while the request waits, caches them by schema text, and fills masks on the CPU while the GPU runs the forward pass.

"Will turning on JSON mode slow us down?" deserves numbers and a condition. With xgrammar on an H100, time per output token for Llama 3.1 8B was unchanged up to 256 requests in flight, even with a new schema on every request. Guidance cost 30% per token at 256 in flight on 4 CPU cores. The condition is CPU: masks are filled on the CPU during the forward pass, and the cost appears when the CPU work no longer fits inside a step. Mention compile latency for unseen schemas and that schemas are cached.

"Does it hurt quality?" A good answer has three parts: the published disagreement, Tam et al. against the Outlines team's rebuttal, with the rebuttal's point that the original compared different prompts; the practical rules of reasoning fields first and schemas close to the model's own habits; and the tokenization point, that constrained output can be valid text in token sequences the model has never seen. Add that a constraint guarantees format only for answers that finish, and that values can still be wrong.

### Check yourself

A request sets temperature 0.7, top-p 0.9 and a repetition penalty of 1.2, and asks for a JSON schema. In what order does vLLM apply these, and why is the grammar mask first?

The grammar mask is applied in the model runner before the sampler, then the penalties, then temperature, then top-p, then the draw. The mask goes first so that nothing later can make a forbidden token possible: penalties and temperature change the logits of allowed tokens, and the truncation filters only remove tokens, so a token at −∞ stays there. It also means that top-p's nucleus is computed over the allowed tokens only.

Why does top-p need a sort when top-k and min-p do not, and how do vLLM and FlashInfer avoid it?

Top-p keeps the smallest set of most likely tokens whose probabilities reach p, which depends on the cumulative sum of the probabilities in descending order, so in its direct form it orders the whole vocabulary. Top-k needs only the k largest values, which `torch.topk` finds without ordering the rest, and min-p needs only each row's maximum. vLLM's default Triton kernel searches for the threshold logit with pivots instead of sorting. FlashInfer samples by rejection: it draws a token and, if the token falls outside the set, raises a pivot and draws again among the tokens above it, never computing the set explicitly. On an H100, at 256 sequences, those took 0.67 ms and 0.31 ms against 4.3 ms for the sort.

vLLM's V2 sampler adds Gumbel noise to the logits and takes the argmax. Why is that a correct way to sample, and why does it beat torch.multinomial?

If G_i are independent Gumbel variables, argmax_i (log p_i + G_i) is i with probability p_i, the Gumbel-max trick; a Gumbel variable is −log of an exponential one, so this is the same as argmax p_i ÷ E_i with E_i exponential. It needs one random number per token, an elementwise add and an argmax, all of which run as one GPU kernel, while `torch.multinomial` computes a cumulative sum, searches it and synchronizes with the CPU. vLLM's version also derives each random number from a hash of the seed, the position and the token index, so a request's noise does not depend on the rest of the batch.

Llama 3.1 8B Instruct is served with a stock \`vllm serve\` and a client sends a request with no sampling parameters. Is the answer greedy?

No. vLLM's `--generation-config` defaults to `auto`, which applies the model's `generation_config.json`, and Llama 3.1 8B Instruct's sets temperature 0.6 and top-p 0.9. The request is sampled with those settings, and the server logs a warning saying so. `--generation-config vllm` restores vLLM's own defaults, and a client that needs greedy output should send temperature 0.

The naive mask walks every token through the automaton at every step. What does Outlines precompute, and why can it not do the same for every JSON schema?

Outlines turns the schema into a regular expression and the expression into a finite automaton, and for every state of the automaton it precomputes the set of allowed tokens and the state each one leads to, so each step is one lookup. The cost moves to compile time and grows with the number of states. Regular expressions cannot count nesting, so a recursive schema can only be represented to a fixed depth, and features such as length limits, numeric ranges and optional fields multiply the states; JSONSchemaBench found median compile times of several seconds and some schemas taking minutes.

What are XGrammar's context-independent tokens, and why does the split make masks cheap?

XGrammar runs the grammar as a pushdown automaton. A token is context-independent at a grammar position if whether it is allowed depends only on that position, the top of the stack, and not on what is below; most tokens are, for example every token of plain string characters inside a string. Their status is precomputed for every position. Only the context-dependent tokens, which could finish the current rule and return to the parent, are checked against the real stack at run time, and for Llama 3.1's vocabulary and JSON they are under 1%, 1,134 of 128,000. Measured on an M2, filling a mask took 3 to 4 µs for the order schema.

On the H100, xgrammar cost nothing measurable per output token at 256 requests in flight, and guidance cost 30%. Where does that difference come from?

vLLM fills the bitmask rows on the CPU, in the engine core, while the GPU runs the forward pass, so the masks cost nothing as long as filling all of them takes less than a step. A step at 256 requests takes about 13 ms. xgrammar's precomputed masks need a few microseconds per row, far inside that. Guidance computes each mask at run time, which is cheap for one request; for 256 rows on the 4 CPU cores the container reserved, the masks most likely no longer fit inside the step, so the step waited for them.

SmolLM2-135M under a schema produced answers that matched it 29 times in 48, although the grammar allows only valid output. What happened to the other 19, and what is the lesson?

They hit the limit of 160 output tokens inside the items array, where the model kept adding items because the grammar always allowed another. An answer cut off mid-array is not valid JSON. The guarantee of structured output holds only for answers that finish, so set `max_tokens` with room to spare and bound repetition in the schema itself: with `"maxItems": 3`, 45 of 48 answers matched.

Jump-forward decoding appends the text a grammar forces without sampling it. Why did it change the text of greedy answers in nano_engine, and what is the risk at the token boundary?

It changes the tokens the model reads. Without it, the model chooses how to split forced text, and SmolLM2 chose splits the tokenizer does not make, such as `[` and `{"` where the tokenizer writes `[{` and `"`; with it, the forced text is split by the tokenizer. Different input tokens give different logits, so even greedy decoding diverges. At the boundary, the last forced token might be one the tokenizer would merge with what the model writes next, such as a quote and the start of a word, so the engine must either leave the last token for the model to choose, as nano_engine does, or retokenize the whole output, as SGLang did.

### Further reading

- Holtzman et al., [The Curious Case of Neural Text Degeneration](https://arxiv.org/abs/1904.09751) (ICLR 2020), which defines nucleus sampling in Section 3.1 and argues against a fixed k in Section 3.2 and Figure 5. Fan, Lewis and Dauphin, [Hierarchical Neural Story Generation](https://arxiv.org/abs/1805.04833) (2018), Section 5.4, for top-k sampling with k = 10.
- Nguyen et al., [Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs](https://arxiv.org/abs/2407.01082) (ICLR 2025), and the reanalysis by Schaeffer, Kazdan and Denisov-Blanch, [Min-p, Max Exaggeration](https://arxiv.org/abs/2506.13681) (2025).
- Keskar et al., [CTRL](https://arxiv.org/abs/1909.05858) (2019), Section 4.1, for the repetition penalty, and OpenAI's [frequency and presence penalties](https://developers.openai.com/api/docs/guides/advanced-usage).
- The FlashInfer team, [Sorting-Free GPU Kernels for LLM Sampling](https://flashinfer.ai/2025/03/10/sampling.html) (2025), on rejection sampling with pivots.
- Willard and Louf, [Efficient Guided Generation for Large Language Models](https://arxiv.org/abs/2307.09702) (2023), the Outlines index.
- Dong et al., [XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models](https://arxiv.org/abs/2411.15100) (MLSys 2025). Section 3.1 has the context-independent tokens and the mask cache, Section 3.5 the overlap with the GPU, and Figure 9 the mask times.
- [llguidance](https://github.com/guidance-ai/llguidance), its README for the design and timings, and Guidance's notebook on [token healing](https://github.com/guidance-ai/guidance/blob/main/notebooks/art_of_prompt_design/prompt_boundaries_and_token_healing.ipynb).
- The LMSYS team, [Fast JSON Decoding for Local LLMs with Compressed Finite State Machine](https://lmsys.org/blog/2024-02-05-compressed-fsm/) (2024), the origin of jump-forward decoding and its tokenization problem.
- Geng et al., [JSONSchemaBench](https://arxiv.org/abs/2501.10868) (2025), which compares six frameworks on coverage, speed and quality. Several of its authors work on Guidance, one of the frameworks compared.
- Tam et al., [Let Me Speak Freely?](https://arxiv.org/abs/2408.02442) (2024), and the reply from the Outlines team, [Say What You Mean](https://blog.dottxt.ai/say-what-you-mean.html) (2024).
- vLLM documentation on [structured outputs](https://docs.vllm.ai/en/latest/features/structured_outputs.html), and the source at v0.32.0: [the V2 sampler](https://github.com/vllm-project/vllm/blob/v0.32.0/vllm/v1/worker/gpu/sample/sampler.py), [the Gumbel kernel](https://github.com/vllm-project/vllm/blob/v0.32.0/vllm/v1/worker/gpu/sample/gumbel.py), [the structured-output manager](https://github.com/vllm-project/vllm/blob/v0.32.0/vllm/v1/structured_output/__init__.py) and [its xgrammar backend](https://github.com/vllm-project/vllm/blob/v0.32.0/vllm/v1/structured_output/backend_xgrammar.py).
