Structured and constrained decoding

You ask a model for a tool call. The schema is trivial:

{"type": "object",
 "properties": {"name": {"type": "string"},
                "id":   {"type": "integer"}},
 "required": ["name", "id"]}

Prompt-only formatting can fail through a trailing comma, a quoted integer, or extra prose. A retry increases that request's latency and can worsen the population's tail latency. A single request has a latency, not a p99; the illustrative failure rate is not an empirical guarantee.

This cannot be prompted away, for a structural reason. Sampling draws from a distribution over all 128,256 Llama-3 tokens at every step, and no prompt assigns zero probability to any of them. A logit of $-\infty$ does. That is constrained decoding: at every step, compute the set of tokens the grammar permits next and drive every other logit to negative infinity before the sampler sees it.

That turns a modelling problem into a systems problem, and the systems problem is the hard one — the grammar is defined over characters, the sampler operates over tokens. Get the bridge wrong and you get errors like this, raised when a schema uses a keyword the compiler cannot lower:

        if has_xgrammar_unsupported_json_features(schema):
            raise VLLMValidationError(
                "The provided JSON schema contains features not supported by xgrammar."
            )

Think of it as a second, non-differentiable model running alongside the first. The network proposes a distribution; an automaton vetoes. The automaton has no opinion about which legal token is best — the sampler picks among the survivors with its usual temperature, top-p and penalties (§6.1).

The veto is a bitmask: one bit per vocabulary entry. For 128,256 entries, 4,008 32-bit words occupy 16,032 bytes per row. Requests with identical grammar/tokenizer state may share a mask, but arbitrary heterogeneous requests require distinct mutable matcher states.

A regular expression in a supported regular subset can use a finite-state automaton. JSON Schema is not universally finite-state: recursive schemas and unbounded JSON nesting require stack-like state; other validation keywords may not be enforced by the decoder. Backends compile the supported subset to an appropriate recognizer. The interface is:

Only the third of those runs on the GPU. Hold that thought — it is the punchline of the cost section.

Two things in Figure 1 matter more than the shapes. The edges are labelled with characters while the masks are indexed by tokens, and one token can cross several edges at once. And the two masks differ wildly in density — tens of bits at S0, thousands at S5 — yet both are 16,032 bytes on the wire. Mask cost does not shrink when the constraint tightens.

Here is the crux. Suppose the vocabulary contains a token whose surface string is {" — two characters. Standing at S0 in Figure 1, is it legal? You cannot tell from S0's outgoing edges, because an edge consumes one character. You must simulate: run {, land in S1, run ", land in S2. The token is legal only if no character in it hits a dead end, and the state you arrive in is S2, not S1.

So the compiler's job is: for every state $q$ and every token $t$, decide whether running $t$'s byte string from $q$ stays inside the language, and if so record the destination $\delta(q, t)$. Define

where $V$ is the token vocabulary, $q$ ranges over the states, and $M(q)$ is the legal-token set encoded as the bitmask. The naive construction is $O(|Q| \cdot |V| \cdot L)$ for $|Q|$ states and average token length $L$ bytes: a thousand states over 128,256 four-byte tokens is half a billion byte-steps for one schema. That is why both engines push compilation off the request path — and it is why their guards are sized the way they are: vLLM aborts a regex compile after 5 seconds (VLLM_REGEX_COMPILATION_TIMEOUT_S, vllm/envs.py:L1642-L1643) and SGLang polls a pending compile for up to 10,000 iterations of 5 ms before declaring it timed out (python/sglang/srt/environ.py:L374-L375). Those bounds are the engines' own statement of the scale of work they expect; neither is a measurement of any particular schema, and this book has none.

Storage is the other half. Fully materialising $M(q)$ for every state costs

Fully materializing every possible state can be prohibitive. Production backends mix precomputation, shared caches and runtime checking: XGrammar precomputes context-independent token decisions while handling context-dependent stack state at runtime. A compiled-grammar cache is not evidence that no masks or mask fragments are cached. vLLM sets a cache budget:

        self.compiler = xgr.GrammarCompiler(
            tokenizer_info,
            max_threads=8,
            cache_enabled=True,
            cache_limit_bytes=vllm.envs.VLLM_XGRAMMAR_CACHE_MB * 1024 * 1024,
        )

VLLM_XGRAMMAR_CACHE_MB defaults to 512 (vllm/envs.py:L1637), and note max_threads=8 — grammar compilation is multi-threaded because it is the expensive step.

The per-step cost, priced against the decode budget

Measure three components separately; their relative cost depends on shape, backend and overlap.

Mask application on device. The shown kernel reads the packed mask and writes negative infinity to forbidden logits. It does not load the old logit values:

        packed_bitmask = tl.load(
            bitmask_ptr + batch_id * bitmask_strides + bitmask_offsets,
            packed_bitmask_mask,
        )
        bitmask = ((packed_bitmask[:, None] >> (tl.arange(0, 32)[None, :])) & 1) == 0
        bitmask = bitmask.reshape(BLOCK_SIZE)

        tl.store(
            logits_ptr + batch_id * logits_strides + offsets,
            -float("inf"),
            vocab_mask & bitmask,
        )

A worst-case logical payload is 513,024 bytes of logit stores plus 16,032 bytes of mask per row, or 529,056 bytes. At peak 3.35 TB/s the ideal payload lower bound is 0.158 microseconds per row (40.4 microseconds for 256 rows), not a measured kernel time. Masked stores, transaction granularity, cache/write policies, launch latency and achieved bandwidth determine real traffic.

Host-to-device transfer. 16,032 bytes per row, so 4.10 MB every step at batch 256 — 64 µs over PCIe Gen5 x16 at its nominal 64 GB/s. Both engines pin the buffer so the copy can genuinely be non_blocking; SGLang says so at the allocation site:

def _allocate_token_bitmask(vocab_size: int, batch_size: int) -> torch.Tensor:
    # Pin where pinning exists, so the later H2D can be a genuine non_blocking
    # copy (a pageable source silently downgrades it).  MPS torch has no
    # pin-memory kernel and asserts on pin_memory=True.
    return torch.full(
        get_bitmask_shape(batch_size, vocab_size),
        -1,
        dtype=bitmask_dtype,
        pin_memory=is_pin_memory_available(),
    )

Mask computation and automaton advance. This is single-threaded host work, per request, and it is where the real cost lives.

The quoted paths advance matchers on the host. Serial work can scale with request count; independent requests can also be threaded or otherwise batched by the implementation. Neither GPU batch time nor amortized per-request GPU time is guaranteed flat when batch size doubles. Compare the exposed host critical path with device work after accounting for overlap.

vLLM's answer is twofold. First, hide the work behind the forward pass: dispatch the model asynchronously, compute the bitmask while the GPU is busy, apply it in a separate sampling call:

        scheduler_output = self.scheduler.schedule(self._should_throttle_prefills())
        future = self.model_executor.execute_model(scheduler_output, non_block=True)
        grammar_output = self.scheduler.get_grammar_bitmask(scheduler_output)
        with (
            self.capture_iteration_details(scheduler_output) as iteration_details,
            self.log_error_detail(scheduler_output),
        ):
            model_output = future.result()
            if model_output is None:
                model_output = self.model_executor.sample_tokens(grammar_output)

That is why the model runner splits execute_model from sample_tokens at all — and the fill is only free if it finishes before the forward does. Hence the second answer: when it might not, shard the fill across a thread pool.

        max_batch_size = self.vllm_config.scheduler_config.max_num_seqs
        self.fill_bitmask_parallel_threshold = 128
        if self.fill_bitmask_parallel_threshold < max_batch_size:
            self.fill_bitmask_parallel_batch_size = 16
            # Use:
            # - at least 1 CPU
            # - at most half the number of CPUs or 8, whichever is less
            max_workers = max(1, min(multiprocessing.cpu_count() // 2, 8))
            self.executor_for_fillmask = ThreadPoolExecutor(max_workers=max_workers)

The quoted path chunks filling into groups of 16 above its threshold, with speculation disabled, and waits for futures. The constants establish a policy, not its measured provenance or optimality. Benchmark the CPU count, grammar mix and scheduler before retuning.

SGLang hides the same cost differently. Its mask is built inside the worker, immediately before sampling:

    def update_regex_vocab_mask(self):
        if not self.grammars:
            self.grammar_mask = None
            return

        # Find a grammar from the list
        first_grammar = next(grammar for grammar in self.grammars if grammar)

        vocab_mask = first_grammar.allocate_vocab_mask(
            vocab_size=self.vocab_size,
            batch_size=len(self.temperatures),
            device=self.device,
        )
# ...
        entries = [
            GrammarRow(row=row, grammar=grammar)
            for row, grammar in enumerate(self.grammars)
            if grammar and not grammar.finished and not grammar.is_terminated()
        ]
        first_grammar.fill_vocab_mask_batched(entries, vocab_mask)

fill_vocab_mask_batched is the interesting indirection: the default is a Python for loop over rows (python/sglang/srt/constrained/base_grammar_backend.py:L88-L94), but the llguidance backend overrides it with a native parallel filler (python/sglang/srt/constrained/llguidance_backend.py:L151-L159) — a real capability difference between backends, not a wrapper detail.

SGLang's harder problem is its overlap scheduler: the FSM advance for step $N$ needs the token sampled at step $N$, which is not on the host yet when step $N{+}1$ is prepared. Its answer is a grammar barrier, a callback handed into the worker that resolves the previous batch's tokens and advances the FSM during the current forward:

        # Sync so the FSM advance lands before the next batch's bitmask. Permanent
        # path for host-draft algorithms, not a pending migration.
        need_grammar_sync = (
            batch
            and not batch.spec_algorithm.is_none()
            and batch.grammar_needs_sync()
            and batch.forward_mode.is_decode()
            and len(self.result_queue) > 0
        )
# ...
        return disable_overlap_for_batch or need_grammar_sync

    def _advance_pending_grammar(self):
        """Grammar barrier (spec-v2 overlap): advance the FSM over any not-yet
        -processed decode result still in the queue, so a following verify()'s
        bitmask sees the previous batch's committed tokens. Invoked mid-worker
        (before generate_token_bitmask) so the CPU advance overlaps the target
        verify forward. Idempotent; no-op when the queue is empty or has no grammar.
        """
        for prev_batch, prev_result in self.result_queue:
            self.batch_result_processor.advance_grammar_fsm(prev_result, prev_batch)

Read need_grammar_sync carefully: for speculative algorithms whose worker does not support the barrier, a grammar in the batch disables overlap scheduling for that step. That is the most expensive thing in this chapter — not microseconds of masking, but losing the CPU/GPU overlap the scheduler is built around. The test is has_grammar and not self.spec_algorithm.supports_grammar_overlap() (python/sglang/srt/managers/schedule_batch.py:L2247-L2251).

Both engines abstract the grammar library behind an interface. vLLM has two abstract classes — StructuredOutputBackend (compile, allocate bitmask, destroy) and StructuredOutputGrammar (accept, validate, rollback, fill, is_terminated, reset) in vllm/v1/structured_output/backend_types.py:L31-L142. SGLang has BaseGrammarBackend with four dispatch methods — dispatch_json, dispatch_regex, dispatch_ebnf, dispatch_structural_tag — each defaulting to _not_supported (python/sglang/srt/constrained/base_grammar_backend.py:L241-L282). A backend supports a constraint type exactly when it overrides that method.

xgrammar covers all six of vLLM's StructuredOutputOptions, though its compile_grammar only ever sees five of them (backend_xgrammar.py:L79-L131 branches on JSON, JSON_OBJECT, GRAMMAR, REGEX, STRUCTURAL_TAG): choice is rewritten into an EBNF alternation during validation — so_params.choice = None; so_params.grammar = choice_grammar — so it arrives at the compiler as a grammar (backend_xgrammar.py:L329-L339). Outlines refuses grammars outright:

    elif so_params.grammar:
        raise VLLMValidationError(
            "Outlines structured outputs backend "
            "does not support grammar specifications"
        )

The same is true of lm-format-enforcer (backend_lm_format_enforcer.py:L191-L195). SGLang's outlines backend inherits the base dispatch_ebnf and dispatch_structural_tag, which log Skip unsupported key_type=... and hand back an InvalidGrammarObject (python/sglang/srt/constrained/outlines_backend.py:L160-L164).

Defaults differ. SGLang picks xgrammar unconditionally:

    def _handle_grammar_backend(self):
        if self.grammar_backend is None:
            self.grammar_backend = "xgrammar"

Choices are ["xgrammar", "outlines", "llguidance", "none"] (server_args.py:L245) plus anything registered via register_grammar_backend. vLLM defaults to "auto" (vllm/config/structured_outputs.py:L21), which is a per-request fallback chain, not a fixed choice: validate under xgrammar; on failure fall back to guidance; if the tokenizer is a non-tekken Mistral or the schema uses patternProperties, fall back to outlines instead (vllm/sampling_params.py:L1156-L1193). Switching engines per request is a real operational hazard — two schemas can take paths with different whitespace semantics — which is why the resolved backend is stamped into _backend and a later mismatch raises.

The API surface over these knobs — response_format, guided_json, SGLang's json_schema/regex/ebnf/structural_tag — belongs to §9.1. All of it funnels into the same six-way enum at backend_types.py:L19-L25.

After {, a restricted grammar may force the five characters "id":. Five characters are not necessarily five model tokens. Jump-forward emits a forced text run, retokenizes consistently, and updates/recomputes the model states needed for later branching. It avoids sampling decisions at forced positions, not all computation required to incorporate those tokens into the KV cache.

Read this section as mechanism, not as a flag you can set. At the pinned SHAs neither engine runs jump-forward on the request path: SGLang removed the scheduler-side driver in #4032 and vLLM never landed one. The interface below still exists in SGLang's grammar backends, and the retokenisation hazard it exposes is the reason the feature is hard — which is why it is worth understanding even though nothing calls it. The status callout at the end of the section has the exact evidence.

Detecting the forced run is the automaton's job, exposed through the same interface in every backend:

    def try_jump_forward(self, tokenizer) -> Optional[Tuple[List[int], str]]:
        """
        Try to jump forward in the grammar.

        Returns:
            A jump forward helper which may be used in `jump_forward_str_state`.
            None if the jump forward is not possible.
        """
        raise NotImplementedError()
# ...
    def jump_and_retokenize(
        self, old_output_ids: List[int], new_output_ids: List[int], next_state: int
    ) -> None:
        """
        Jump forward occurs, and update the grammar state if needed.
        """
        raise NotImplementedError()

The outlines implementation builds the map at compile time. init_state_to_jump_forward walks the FSM's transition table and records, for each state, the single outgoing edge — deleting the entry the moment a second outgoing edge appears:

            outgoings_ct[state] += 1
            if outgoings_ct[state] > 1:
                if state in state_to_jump_forward:
                    del state_to_jump_forward[state]
                break

            state_to_jump_forward[state] = JumpEdge(
                symbol=c,
                symbol_next_state=next_state,
            )

Note lines 82–84 of that file: final states are seeded with outgoings_ct[s] = 1 before the walk, because a final state can always terminate — terminating counts as a second option, so an accepting state is never jump-forwardable. That is a subtle correctness detail that is easy to get wrong.

Now the hazard. Jumping produces text, and the KV cache is indexed by tokens. You cannot just tokenise the forced string and append it, because BPE is not compositional across a boundary: the last token already in the cache and the first characters of the forced string may merge into one different token. Append naively and the KV state corresponds to a token sequence no tokeniser would ever produce — off-distribution in a way that is invisible until the output degrades.

The correct procedure is to re-tokenise the whole string and repair. SGLang's historical implementation did exactly that, and its comments name the failure mode:

        all_text = self.origin_input_text + self.decoded_text + jump_forward_str
        all_ids = self.tokenizer.encode(all_text)
        if not all_ids:
            logger.warning("Encoded all_text resulted in empty all_ids")
            return False

        prompt_tokens = len(self.origin_input_ids_unpadded)
        if prompt_tokens > len(all_ids):
            logger.warning("prompt_tokens is larger than encoded all_ids")
            return False

        if all_ids[prompt_tokens - 1] != self.origin_input_ids_unpadded[-1]:
            # TODO(lsyin): fix token fusion
            logger.warning(
                "Token fusion between input and output, try to avoid this by removing the space at the end of the input."
            )
            return False

Three guards, one abort each. The last is the token-fusion check: if re-tokenising the full string changes the prompt's last token, the boundary has moved into territory the KV cache already committed, so the jump is refused rather than corrupting state. The warning's advice — remove the trailing space from the input — is a real workaround for a real bug class.

The grammar needs repairing too, since it was advanced over the old token sequence. xgrammar's jump_and_retokenize finds the longest common prefix, rolls the matcher back over the divergent suffix, and re-accepts:

    def jump_and_retokenize(
        self, old_output_ids: List[int], new_output_ids: List[int], next_state: int
    ):
        k = 0
        for i, old_id in enumerate(old_output_ids):
            if old_id == new_output_ids[i]:
                k = i + 1
            else:
                break

        # rollback to the last token that is the same
        if k < len(old_output_ids):
            self.matcher.rollback(len(old_output_ids) - k)

        for i in range(k, len(new_output_ids)):
            if not self.matcher.accept_token(new_output_ids[i]):
                raise ValueError(
                    f"Token not accepted during retokenization: {new_output_ids[i]} "

The last box is the cost nobody advertises: a jump invalidates KV for every position at or after the divergence index, so the saved forward passes are partly repaid by a small re-prefill. The win is still large when the forced run is long — {"name": " is ten characters, perhaps four tokens, four forward passes at 4.48 ms each on Llama-3-8B — but it is not free, which is why the feature was fiddly enough to remove rather than maintain.

Speculative decoding (§6.2) proposes $k$ tokens and verifies them in one forward pass. A drafter knows nothing about your grammar, so drafts are routinely illegal — and verification needs a bitmask per draft position, each computed from the state reached by accepting the drafts before it. Both engines handle this; they differ in where.

vLLM allocates the bitmask with a row for every position that could be sampled:

        if self._grammar_bitmask is None:
            assert self.backend is not None
            max_batch_size = self.vllm_config.scheduler_config.max_num_seqs

            # Allocate a bitmask for each token needing to be checked:
            # one for each speculative position, and one more for the
            # bonus token / non-speculative token.
            self._grammar_bitmask = self.backend.allocate_token_bitmask(
                max_batch_size * (1 + max_num_spec_tokens)
            )

At max_num_seqs=256 and $k=3$ that buffer is $256 \times 4 \times 16{,}032 = 16.4$ MB of pinned host memory, and the per-step H2D grows fourfold with it. Filling it walks the drafts, emitting a mask, accepting the token, emitting the next mask, and finally rolling the FSM back by the number of advances so the true state is untouched (vllm/v1/structured_output/__init__.py:L298-L359). Separately, drafts that the grammar rejects are filtered out before they are even scheduled and replaced with -1 sentinels:

            # Filter out spec tokens which do not adhere to the grammar.
            if self.structured_output_manager.should_advance(request):
                metadata = request.structured_output_request
                spec_token_ids = metadata.grammar.validate_tokens(spec_token_ids)  # type: ignore[union-attr]
            # Pad to original number of spec tokens.
            num_invalid_tokens = orig_num_spec_tokens - len(spec_token_ids)
            if num_invalid_tokens:
                spec_token_ids.extend([-1] * num_invalid_tokens)
                num_invalid_spec_tokens[req_id] = num_invalid_tokens

validate_tokens is why the interface has both an advancing and a non-advancing accept: it returns the accepted prefix and rewinds (backend_xgrammar.py:L181-L201). Sentinel drafts are excluded from acceptance-rate statistics, so your reported acceptance length is not silently depressed by the grammar (vllm/v1/core/sched/scheduler.py:L1867-L1876). max_rollback_tokens is sized to num_speculative_tokens at matcher construction (backend_xgrammar.py:L124-L128), and lm-format-enforcer refuses speculation outright — "LM Format Enforcer backend does not support speculative tokens" (backend_lm_format_enforcer.py:L134-L137).

SGLang verifies a tree, not a chain, so its mask construction is a DFS over the draft tree where each node's legality is read out of its parent's bitmask:

            parent_bitmask = allocate_token_bitmask[parent_pos]
            current_token = draft_tokens[curr]
            if vocab_size and current_token >= vocab_size:
                is_accepted = False
            else:
                # 32 boolean bitmask values are packed into 32-bit integers
                is_accepted = (
                    parent_bitmask[current_token // 32] & (1 << (current_token % 32))
                ) != 0

        if is_accepted:
            if curr != 0:
                # Accept the current token
                grammar.accept_token(int(draft_tokens[curr]))
            if not grammar.is_terminated():
                # Generate the bitmask for the current token
                grammar.fill_vocab_mask(allocate_token_bitmask, curr)
                if retrieve_next_token[curr] != -1:
                    # Visit the child node
                    dfs(
# ...
            if curr != 0:
                # Rollback the current token
                grammar.rollback(1)

Accept on the way down, roll back on the way up — a depth-first walk that leaves the matcher where it started. That is why SGLang's matcher gets MAX_ROLLBACK_TOKENS = 200 (python/sglang/srt/constrained/xgrammar_backend.py:L58) rather than a spec-width bound. The traversal is host work deliberately issued after the target verify launch so it overlaps that forward (python/sglang/srt/speculative/spec_utils.py:L617-L646), with a tripwire on it: exceed TREE_TRAVERSE_TIME_THRESHOLD = 1 second and it logs "Bit mask generation took ... seconds with grammar: ..." (spec_utils.py:L549-L554).

Follow a single request from arrival to its second sampled token.

1. Admission. SamplingParams._validate_structured_output resolves the backend. Under "auto" it dry-runs xgr.Grammar.from_json_schema(schema) and falls through to guidance or outlines on failure (vllm/sampling_params.py:L1156-L1193), stamping the winner into structured_outputs._backend.
2. Blocking state. The request is constructed non-schedulable: self.status = RequestStatus.WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR (vllm/v1/request.py:L114-L115), so it lands in the skipped-waiting queue, not the runnable one — see §1.4.
3. Async compile, then promotion. grammar_init submits _create_grammar to a pool sized at half the CPUs and stores the Future (vllm/v1/structured_output/__init__.py:L167-L176); each scheduling pass polls it with a 100 µs timeout (vllm/v1/structured_output/request.py:L50-L59). Ready and valid, the request goes to WAITING; ready and an Exception, it joins grammar_compile_error_reqs and fails alone rather than taking the engine down (vllm/v1/core/sched/scheduler.py:L2817-L2825).
4. Prefill. While it is still a prefill chunk the request is excluded from the bitmask — req.use_structured_output and not req.is_prefill_chunk (scheduler.py:L1731-L1733). Masking starts at the first sampled token.
5. Step N, dispatch and fill. execute_model(non_block=True) launches the forward; get_grammar_bitmask collects the structured request ids in scheduling order (scheduler.py:L1720-L1742) and calls grammar.fill_bitmask(...) → matcher.fill_next_token_bitmask(bitmask, idx) per row (backend_xgrammar.py:L208-L209). The tensor is handed to the worker as a .numpy() array, because ndarray serialisation is cheaper across the process boundary (__init__.py:L361-L368).
6. Step N, apply. apply_grammar_bitmask reorders rows from scheduling order into batch order — they differ, and offsets shift by each request's speculative token count — stages them pinned, copies non_blocking, and calls xgr.apply_token_bitmask_inplace(logits, grammar_bitmask, indices=index_tensor) (vllm/v1/structured_output/utils.py:L114-L162).
7. Step N, advance. update_from_output calls grammar.accept_tokens(...). Rejection should be impossible, since the mask made illegal tokens unsampleable; if it happens the request is killed with "Unexpected: grammar rejected tokens %s for request %s. Terminating request." (scheduler.py:L1918-L1943). That line in production means the mask and the FSM disagreed — a bug, not a user error.

SGLang's shape is the same with different names: GrammarManager.process_req_with_grammar keys the cache on (type, spec) and returns either a copy() of a cached grammar or a compile future (python/sglang/srt/constrained/grammar_manager.py:L131-L182, base_grammar_backend.py:L284-L293); get_ready_grammar_requests polls at SGLANG_GRAMMAR_POLL_INTERVAL (0.005 s) and gives up after SGLANG_GRAMMAR_MAX_POLL_ITERATIONS (10,000) with "Grammar preprocessing timed out" (grammar_manager.py:L203-L303).

Compilation latency is a TTFT cliff on first use

The first request carrying a new schema pays the full compile. Both engines make that asynchronous, but asynchronous is not free — the request waits. Caching is keyed on the (type, spec) string, so a schema differing only in property order is a miss: if your gateway serialises schemas non-deterministically you will recompile the same grammar forever. Warm the cache at startup with one dummy request per schema.

Adversarial regexes hang the worker

Compilation state explosion and catastrophic regex backtracking are different hazards. (a+)+b can be expensive for a backtracking matcher, but denotes the same simple regular language as a+b; it is not an exponential-DFA example. Some regex families do have exponential determinization growth. Bound pattern size, compilation time and memory, and isolate compilation workers; a timed-out future may still require cancellation/termination.

    try:
        result = future.result(timeout=timeout)
    except TimeoutError:
        future.cancel()
        executor.shutdown(wait=False, cancel_futures=True)
        raise ValueError(
            f"Regex compilation timed out after {timeout}s. "
            "The pattern may be too complex or contain constructs that "
            "cause exponential state-space explosion (e.g. nested "
            f"quantifiers). Pattern: {pattern[:200]}"
        ) from None

VLLM_REGEX_COMPILATION_TIMEOUT_S defaults to 5 (vllm/envs.py:L1642-L1643). Note that the cancelled thread keeps burning a core until the C extension returns — the timeout bounds your latency, not your CPU.

Constraints the tokeniser cannot express

Some patterns are fine at the character level and unusable at the token level. Outlines rejects regexes without a universal start state, and the error is unusually explanatory:

    if _prefix_needs_context(parsed):
        raise VLLMValidationError(
            "Regex does not have a anchored universal start state"
            "This means that the Regex uses anchors (^) or look-arounds "
            "in a way which requires context before any token is matched."
            "structured outputs needs regexes that can match without needing "
            "that context. Try rewriting the pattern without using these "
            f"constructs. Pattern:\n{pattern}"
        )

The cited backend rejects backreferences, lookarounds and Unicode word boundaries. Backreferences can express nonregular languages; bounded/contextual assertions and boundaries are not all inherently nonregular. Some rejections reflect the library's supported syntax or streaming-context contract rather than a mathematical impossibility of finite-state recognition.

Silently dropped schema constraints

The nastiest failure is the one that does not raise. vLLM's deny-list check carries a comment worth reading in full:

        # A string mixing a generative constraint (pattern or format) with
        # explicit length bounds. xgrammar compiles the pattern/format side
        # and silently drops minLength/maxLength from the grammar, so output
        # can violate the bound without any error surfacing. Verified against
        # the compiled EBNF: pattern/format grammars come out byte-identical
        # with and without the length keywords, while maxLength alone lowers
        # to {0, N} correctly.
        if (
            obj.get("type") == "string"
            and ("pattern" in obj or "format" in obj)
            and ("minLength" in obj or "maxLength" in obj)
        ):
            return True

{"type": "string", "pattern": "[a-z]+", "maxLength": 8} would have produced unbounded strings with no warning. Constrained decoding guarantees conformance to the compiled grammar, which may be strictly weaker than the schema you wrote. Validate the output anyway.

Unbounded repetition, and grammars that ruin the model

A grammar can be legal and still be a trap. {"type": "array", "items": {"type": "string"}} with no maxItems permits an infinite array, and EOS is not grammar-legal until the array closes, so the model loops until max_tokens. Masking stop tokens until termination is deliberate — vLLM passes SamplingParams.all_stop_token_ids into the matcher as override_stop_tokens precisely so they stay masked (vllm/v1/structured_output/backend_types.py:L111-L123). Bound your repetitions.

The subtler problem is quality. Masking renormalises, and if the grammar forces the model somewhere it did not want to go, what is left can be close to noise. A schema whose field ordering contradicts the training distribution — forcing "reasoning" after "answer" — yields syntactically perfect, semantically worse output. Whitespace is the classic case: disable_any_whitespace (vllm/config/structured_outputs.py:L26-L30) forces compact JSON on a model trained on pretty-printed JSON. Neither engine can warn you; only an eval can.

Suppose two first-token choices A and B are currently legal and equally likely. Only 0.1 of A's next-token probability reaches a valid ending, compared with 0.9 for B. Local masking leaves the first decision 50/50, then forces a valid ending. Sampling the original model conditioned on eventual validity would instead choose A with probability 0.1. This distinction does not undermine structural validity; it clarifies which distribution is sampled. Validate grammar acceptance, EOS/length completion, full schema semantics and task correctness separately. An empty legal set requires an explicit error/fallback policy, never an all-negative-infinity softmax.

import numpy as np

first = np.array([0.5, 0.5])
valid_completion_mass = np.array([0.1, 0.9])
locally_masked_first = first / first.sum()
conditioned_on_validity = first * valid_completion_mass
conditioned_on_validity /= conditioned_on_validity.sum()
np.testing.assert_allclose(locally_masked_first, [0.5, 0.5])
np.testing.assert_allclose(conditioned_on_validity, [0.1, 0.9])
assert not np.allclose(locally_masked_first, conditioned_on_validity)
allowed = np.array([False, False])
assert not allowed.any()  # report a dead-end; do not call softmax
print("Local masking and globally conditioned generation differ.")

vLLM ships a structured-output benchmark harness. It sweeps QPS with a configurable fraction of requests carrying a schema, which is exactly the knob that isolates grammar overhead from everything else:

# serve with an explicit backend so "auto" cannot silently switch engines
vllm serve meta-llama/Meta-Llama-3-8B-Instruct \
  --structured-outputs-config.backend xgrammar \
  --max-num-seqs 256

# sweep QPS 25..1 at 100% structured, then at 0%, and diff
MODEL=meta-llama/Meta-Llama-3-8B-Instruct STRUCTURED_OUTPUT_RATIO=1 \
  bash benchmarks/run_structured_output_benchmark.sh
MODEL=meta-llama/Meta-Llama-3-8B-Instruct STRUCTURED_OUTPUT_RATIO=0 \
  bash benchmarks/run_structured_output_benchmark.sh

Three things to vary, in order. Batch size — set --max-num-seqs to 64 then 129, crossing fill_bitmask_parallel_threshold = 128; the parallel fill only engages above it. Backend — rerun with guidance and outlines on the identical schema. Schema complexity — compare benchmarks/structured_schemas/structured_schema_1.json against one with a long enum and a regex-constrained string.

On SGLang the equivalent is --grammar-backend {xgrammar,llguidance,outlines,none} plus --constrained-json-disable-any-whitespace, and the thing to watch is not mask cost but whether overlap scheduling stays on: under speculative decoding, if your algorithm's supports_grammar_overlap() is false, adding a grammar silently serialises the step loop.

The full measurement is 09-structured-decoding-overhead in the labs. Every number here is derived arithmetic or read out of source; none is measured, and what you actually see will be dominated by host CPU speed, which none of the arithmetic above captures.

• Fast JSON Decoding for Local LLMs with Compressed Finite State Machine — the original jump-forward writeup, linked from the SGLang source itself (python/sglang/srt/constrained/outlines_jump_forward.py:L16): https://lmsys.org/blog/2024-02-05-compressed-fsm/
• SGLang #4032, "Misc clean up; Remove the support of jump forward" (commit 935cda944b, 2025-03-03). Read its diff against python/sglang/srt/managers/schedule_batch.py for the full historical implementation.
• xgrammar's GrammarMatcher.find_jump_forward_string, the API vLLM's source points at: https://xgrammar.mlc.ai/docs/api/python/index.html#xgrammar.GrammarMatcher.find_jump_forward_string (cited at vllm/v1/structured_output/backend_xgrammar.py:L146).
• llguidance fast-forward docs — the compute_ff_bytes / compute_ff_tokens distinction, which is exactly the retokenisation problem: https://github.com/guidance-ai/llguidance/blob/main/docs/fast_forward.md (cited at vllm/v1/structured_output/backend_guidance.py:L177-L182).
• regex-automata's universal start state: https://docs.rs/regex-automata/latest/regex_automata/dfa/trait.Automaton.html#method.universal_start_state (cited at vllm/v1/structured_output/backend_outlines.py:L316-L318).
• vLLM issues cited inside the structured-output code: #31901 (CPU bitmask dtype), #42452 and #44006 (reasoning-end boundaries), #43388 (async scheduling + spec decode placeholder drift), #45436 (diffusion LLMs), plus xgrammar #850 (the NUL-byte segfault both engines work around by hand). The best documentation of this subsystem's sharp edges.