Structured decoding and fairness

Callers increasingly want output that is not just plausible text but valid JSON, a function call, or a string in some grammar. Constrained decoding methods enforce such formal language constraints during generation. Doing this naively is costly in two ways: Beurer-Kellner et al. show that many existing methods not only add performance overhead at generation time but also significantly impair task accuracy, because the constraint is defined over text while the model emits subword tokens, and misaligning the two distorts what the model is allowed to say. Their DOMINO algorithm enforces constraints in a fully subword-aligned fashion, and by leaning on pre-computation and speculative decoding it runs with virtually no overhead, in some cases almost 2 times faster than unconstrained decoding.

Making that mask cheap is its own engineering problem, because the naive version does work proportional to the vocabulary at every step. Dong et al. put the cost precisely: each decoding step has to interpret the grammar for every possible token in a vocabulary that can be as large as 128k in Llama 3.1, and because interpreting a context-free grammar requires a stack state tracking which recursive rules have matched so far, it is impossible to precompute and cache all combinations of stack patterns ahead of time. Their XGrammar engine splits the vocabulary into context-independent tokens, which can be prechecked, and context-dependent tokens, which must be interpreted at runtime, then adds a persistent stack to speed up the context-dependent checks and overlaps grammar computation with GPU execution by co-designing the engine with the inference engine. They report up to 100 times speedup over existing solutions, and near-zero overhead structured generation end to end.

XGrammar makes each step cheaper. SGLang attacks the number of steps instead, starting from the observation that the token-by-token discipline is sometimes pure waste. Existing systems compile a regular expression into a finite state machine, hold the current state, read the allowed tokens off the next states, zero the probability of the rest, and advance one token per forward pass, even across stretches where exactly one token is ever valid. The paper’s example is the constant prefix {"summary": ", which spans several tokens without a single choice anywhere in it: the model is run once per token to emit output that was determined before decoding began. SGLang’s compressed finite state machine analyzes the machine and collapses adjacent singular-transition edges into single edges, so every token along a compressed edge comes out of one forward pass. The obstacle it removes is plumbing rather than theory, and the paper says so: it is the lack of integration between the state machine and the model runner that prevents existing systems from processing multiple tokens at once. On a JSON decoding benchmark the compression raises throughput 1.6 times, with one condition that an implementation can quietly get wrong. The machine has to be preprocessed once and reused across a batch of requests; redoing that preprocessing per request makes throughput 2.4 times lower, which is a larger loss than the optimization was worth in the first place.

All three systems assume something has told them what the output must look like, and in an engine that something is a request parameter. vLLM’s documentation defines a small SQL-like language and hands it over with the request:

simplified_sql_grammar = """
    root ::= select_statement

    select_statement ::= "SELECT " column " from " table " where " condition

    column ::= "col_1 " | "col_2 "

    table ::= "table_1 " | "table_2 "

    condition ::= column "= " number

    number ::= "1 " | "2 "
"""

completion = client.chat.completions.create(
    model=model,
    messages=[
        {
            "role": "user",
            "content": "Generate an SQL query to show the 'username' and 'email' from the 'users' table.",
        }
    ],
    extra_body={"structured_outputs": {"grammar": simplified_sql_grammar}},
)

Six production rules define a language containing exactly the strings the model is permitted to produce, and every decode step for this request masks the vocabulary down to the tokens that keep the output on some path through them. Read the prompt against the grammar and the tension is obvious: it asks for username and email from a users table, and the grammar admits only col_1, col_2, table_1 and table_2. The constraint is what decides, which is the sharp edge of the technique. A grammar that does not match the task still yields output that parses, and a caller who checks only whether parsing succeeded never finds out.

A grammar is one of five constraint shapes vLLM accepts. choice restricts the output to exactly one of a list, regex to a pattern, json to a JSON Schema, grammar to a context-free grammar in EBNF, and structural_tag applies a schema only inside specified tags within the generated text. Offline the same options arrive as a StructuredOutputsParams object nested inside SamplingParams, which is the detail that connects this section to the earlier ones: a constraint is per-request state travelling with the sampling parameters, so two requests sharing a continuously batched iteration can be masked against different grammars in the same step. Which engine compiles the mask is configurable too, with xgrammar and guidance as backends and a default that picks one from the details of the request.