GLRMask

Suppose you want to guarantee that an LLM’s output follows a grammar. How do we do this?

The dumb way is to sample repeatedly until we get a token the parser no longer rejects:

while generating:
    logits = model()
    token = sample(logits)
    while not constraint.allows(token):
        token = sample(logits)
    constraint.commit(token)
    model.commit(token)

The problem with rejection sampling is that it blocks the whole decoding pipeline. Nothing can continue until we’ve decided on a token that’s valid, and in the worst case could end up working through almost the entire vocabulary while the GPU sits idle.¹

The alternative is to work out which tokens are legal up front, as a mask over the vocabulary, while the model is busy:

while generating:
    parallel:
        logits = model()
        mask = constraint.get_mask()

    logits[~mask] = -np.inf
    token = sample(logits)

    constraint.commit(token)
    model.commit(token)

get_mask() runs in parallel with the forward pass to determine which model tokens are legal from the current state. The sampler picks one of the legal tokens, then commit(token) advances the lexer and parser using the token that was actually chosen.

If the mask is ready by the time the forward pass finishes, its cost is hidden. If not, it stalls generation. So get_mask has to be fast.

So masked generation works by restricting the sampler to grammatically valid tokens. It literally can’t go wrong²! But what does the mask actually compute?

Suppose the bytes generated so far are $u$ , the language we want to generate is $L$ (a language is just a set of strings; here, $L$ is the set allowed by the grammar), and model token $v$ corresponds to the byte string $\beta(v)$ . The next-token mask is

\mathrm{Mask}_L(u) = \{v\in\mathcal V:\exists w,\;u\beta(v)w\in L\}.

Let’s think about what this means. A token is legal if appending its bytes still leaves some way to complete the output into a grammatically valid string. And we need to check that for every token in the vocabulary, at every generation step.

A bruteforce approach might look something like this:

Build a mask over the entire LLM vocabulary.
For each LLM token $t$ , check whether appending $\beta(t)$ keeps the parse valid.
If so, set its bit.

With a vocabulary of 100k+ tokens, this probably won’t go too well.

A straightforward way to generate the mask is to explore candidate token bytes online. In practice you put the vocabulary in a byte trie, share work between tokens with common prefixes, cut off branches as soon as they become impossible, and use further shortcuts to settle whole groups of tokens at once. This can already make mask generation very fast, particularly for JSON. llguidance is a strong implementation of this kind of approach.

But how much work remains depends on the grammar and the current parse state, and this can show up most clearly in tail latency (e.g. p99.9).

GLRMask tries to move as much of this work ahead of time as possible. Compilation is heavier, sometimes substantially so, but it only has to happen once, and the compiled constraint can then be reused for every subsequent request.

Weighted automata

To see where we’re headed, it might be useful to understand what we’re trying to build and why it should be possible, at least vaguely.

The central object in GLRMask is the Parser DWA. It eats the current parser stack from the top down, one symbol at a time, and returns the mask directly.

Okay, great: a magical automaton! But why should such a thing exist?

Here’s one way to think about it.

Fix a lexer state $q$ and a model token $v$ . Depending on how $v$ ‘s bytes are lexed, it may produce one or more terminal sequences. Each of those sequences, in turn, makes the parser perform some actions on the stack. For an LR parser, those actions are shifts, reduces, and gotos. But regardless of how the particular parsing paradigm formulates those actions, they must boil down to a sequence of reads and writes on the parser stack.

The lexer, parser, and vocabulary are known ahead of time. So for a given lexer state, by combining the terminal sequences that we know the lexer emits with the stack reads and writes we know the parser performs for them, we should be able to characterise ahead of time exactly how an LLM token acts on the parse state.

Viewed from before the token is consumed, when we just want to know whether or not this token will be accepted, this gives us a set of requirements on the old stack: which parser states need to be sitting at the top of the stack, and in what order. So for each $(q,v)$ , there is a set of parser-stack prefixes from which $v$ can be consumed legally.

For reasons we’ll come back to later, it is possible to ensure that an LR parser can produce only a bounded amount of parser activity while processing any one terminal. Furthermore, as long as each terminal consumes at least one byte, we know that each model token can produce only a bounded amount of lexer activity. Putting these together, a model token can induce only a bounded amount of parser activity, and therefore its acceptance depends on only a bounded prefix of the existing parser stack. Thus each $(q,v)$ induces a regular language over stack prefixes, recognizable by a finite automaton.

Now imagine one of these automata for every $(q,v)$ pair. An LLM vocabulary may contain a hundred thousand or more tokens, and a lexer can easily have tens of thousands of states, so there are a lot of them. But there is also a lot of shared structure among them.

GLRMask exploits this shared structure by storing the whole family in one weighted automaton. Common stack-prefix paths are represented only once, while the weights record which $(q,v)$ pairs use each part of the graph.

A weighted automaton is just an automaton whose transitions carry weights, with rules for how those weights combine. In GLRMask, a weight is a Boolean array

w\in\mathbb B^{Q_{\mathrm{lex}}\times\mathcal V},

indexed by lexer states and model tokens. Concretely, $w_{q,v}=1$ means that the transition applies to the pair $(q,v)$ .

To build the Parser DWA, we handle the lexer and parser separately:

On the lexer side, the Terminal DWA records which terminal sequences a model token can produce.
On the parser side, the stack-effect automata describe what each terminal can do to the parser stack.

Terminal DWA

The Terminal DWA records, for every lexer state and model token, the terminal sequences that token can produce.

Fix a lexer state $q$ and a model token $v$ , and let $\beta(v)$ be the bytes of that token.

A single LLM token might:

expand into multiple terminals ("}\n" could lex as RBRACE NEWLINE),
end partway through a terminal (halfway through a string literal, halfway through a number, halfway through true),
be lexically ambiguous,
or produce no terminals yet (e.g. it adds bytes inside a string, but doesn’t close it).

So even for a fixed lexer state and model token, there may be more than one terminal sequence we need to consider.

We store these sequences in a deterministic weighted automaton, or DWA.

A path through the Terminal DWA represents a terminal sequence, and its weights record which lexer-state/model-token pairs can produce it.

Conceptually, for each pair $(q,v)$ , run $\beta(v)$ through the lexer from $q$ , and add the terminal sequences it can produce as paths from the root, marking those paths with $(q,v)$ . If the token ends partway through a lexeme, we also need to account for its possible completions. The model token is only legal if at least one such completion can eventually be accepted by the parser. So branch the path once for each terminal that lexeme could still become, and end each branch with that terminal.

In practice, of course, we traverse a vocabulary trie rather than iterating through each full token individually. But you get the idea. Lots of tries! Just assume, from now on, that any time I mention iterating over the vocabulary, I really mean traversing it as a trie.

Stack effects

PLUS stack-effect automaton — One stack-effect automaton per terminal. Neutral edges read or pop parser states; crimson edges push them.

For an LR parser, consuming one terminal means performing zero or more reductions followed by a shift.

A shift pushes a state to the stack. Reductions are a bit more involved. But what matters really is that ultimately everything an LR parser does is a sequence of operations that read from (and consume) and write to the top of a stack.

GLRMask abstracts away parser behaviour as sequences of stack effects: $p^-$ for “read and remove parser state $p$ ,” and $p^+$ for “write parser state $p$ .”

A stack effect sequence such as

p^-r^+s^+

therefore says: the old stack must begin with $p$ ; consume it; then write $r$ and $s$ .

Different terminals can have different stack effects, and a terminal may have more than one possible effect. For each terminal $t$ , let $E_t$ denote the set of its possible stack-effect sequences.

Stack effects also compose nicely. Suppose one terminal has the effect

p^-r^+s^+

and the next has

s^-r^-u^+.

Composing them gives

p^-r^+s^+s^-r^-u^+.

Let’s think about what this means. One terminal pushes states $r \, s$ onto the stack, and the next terminal immediately reads $s \, r$ back off. As far as the stack is concerned, those operations cancel:

p^-r^+s^+s^-r^-u^+ \;\longrightarrow\; p^-r^+r^-u^+ \;\longrightarrow\; p^-u^+.

The two-terminal sequence therefore only requires the original stack to begin with $p$ . And if it does, it simply replaces that $p$ with $u$ . Everything involving $r$ and $s$ happens internally between the two terminals.

So, the cancellation rule is simply

p^+p^-\to\epsilon

A mismatched write/read pair, on the other hand, makes the path invalid:

p^+q^-\longrightarrow\bot \qquad(p\ne q).

For any set of stack effects, repeatedly applying these cancellations takes every surviving effect to a normal form consisting of some reads from the original stack followed by some writes describing the new stack:

p_1^-p_2^-\cdots p_m^-q_1^+q_2^+\cdots q_n^+.

Finally, for each terminal $t$ , let $E_t$ be the set of stack effects by which $t$ can be consumed.

Rather than enumerate $E_t$ explicitly, we represent it with a small automaton over stack operations. Each path through the automaton corresponds to one stack effect in $E_t$ .

Parser DWA

Let’s recap. We’ve built two kinds of automata.

The Terminal DWA compactly represents the terminal sequences that model tokens can produce, with each path weighted by the lexer states and model tokens for which it applies.

Then for each terminal, we have a small automaton describing its effect on the parser stack.

So the Terminal DWA connects model tokens to terminals, while the stack-effect automata connect terminals to stack effects.

\begin{array}{rcl} \text{model tokens} & \xrightarrow{\text{Terminal DWA}} \text{terminals} \xrightarrow{\text{stack-effect automata}} & \text{stack effects} \end{array}

It’s time to cut out the middleman.

\begin{array}{rcl} \text{model tokens} & \xrightarrow{\hspace{7em}\text{Parser DWA}\hspace{7em}} & \text{stack effects} \end{array}

Wherever the Terminal DWA has an edge labelled $t$ , splice in the stack-effect automaton for $t$ . A path that previously represented a terminal sequence now expands into paths describing the corresponding parser-stack operations.

Writes from one terminal can run into reads from the next. Adjacent write/read symbols cancel when they match, and kill the path when they don’t. We keep cancelling until all of these internal write/read pairs are gone.

Any remaining writes sit at the end of the path, describing the net additions to the stack after the required stack prefix has been read.

For mask generation, the trailing writes aren’t needed. We could keep them and use the same automaton to update the parser state during commit, but that adds more complexity than it is worth. So instead we just drop them.

What we are left with is a weighted automaton over parser-stack symbols, whose paths read prefixes of the parser stack directly.

And that’s it: the Parser DWA!

I think it’s helpful to see the Parser DWA as basically a compressed representation of the family $L_{q,v}$ . For any particular $(q,v)$ , the corresponding read-only automaton for $L_{q,v}$ can in principle be recovered from the Parser DWA by keeping only transitions whose weights contain $(q,v)$ . So, effectively, slapping Boolean-array weights onto transitions lets us pack a whole family of automata into one, with the weights encoding the distinctions among them.

Finally, one nice property of the Parser DWA is that it only ever needs to read a bounded prefix of the parser stack. First, it should be fairly clear that each terminal sequence emitted by the lexer for a model token has bounded length. Every terminal emitted during the scan consumes at least one byte, and a model token contains only finitely many bytes. And because the vocabulary is finite, there is a fixed maximum token length. For each terminal, the stack effect is bounded too. After grammar normalization, the number of consecutive reductions between shifts is bounded by a constant depending only on the grammar [Aycock et al., 2001]. The Parser DWA is just the composition of these bounded terminal sequences and bounded stack effects. So it too must be bounded. Nice!

Mask generation

Let’s suppose for the moment that each parser state is simply a stack of LR state IDs (i.e. there’s no lexical or grammatical ambiguity).

Mask generation runs the Parser DWA on the current parser stack, one symbol at a time. Each transition’s Boolean weight narrows a running set of allowed tokens as it is taken. When the Parser DWA hits an accepting state, the tokens accepted there are added to the mask.

...  # <fold>

@dataclass
class DWA[T, W: Semiring]:
    ...  # <fold>
    def run(self, input: list[T], wi: W) -> W:
        state = self.start
        active_weight = wi
        out = active_weight * self.final_weights[state]

        for x in input:
            state, edge_weight = self.transitions[state][x]
            active_weight *= edge_weight
            out += active_weight * self.final_weights[state]

        return out

...  # <fold>
@dataclass
class Constraint:
    ...  # <fold>
    def get_mask(self) -> TokenMask:
        return self.parser_dwa.run(self.stack, np.ones(self.token_count, dtype=bool))

from __future__ import annotations

from dataclasses import dataclass
from typing import Protocol, Self

import numpy as np
from jaxtyping import Bool


class Semiring(Protocol):
    def __add__(self, other: Self) -> Self: ...
    def __mul__(self, other: Self) -> Self: ...


type State = int
type LRState = int
type TokenMask = Bool[np.ndarray, "token"]
type ParserDWA = DWA[LRState, TokenMask]


@dataclass
class DWA[T, W: Semiring]:
    start: State
    transitions: dict[State, dict[T, tuple[State, W]]]
    final_weights: dict[State, W]

    def run(self, input: list[T], wi: W) -> W:
        state = self.start
        active_weight = wi
        out = active_weight * self.final_weights[state]

        for x in input:
            state, edge_weight = self.transitions[state][x]
            active_weight *= edge_weight
            out += active_weight * self.final_weights[state]

        return out
@dataclass
class Constraint:
    parser_dwa: ParserDWA
    stack: list[LRState]
    token_count: int

    def get_mask(self) -> TokenMask:
        return self.parser_dwa.run(self.stack, np.ones(self.token_count, dtype=bool))

Relaxing our no-parser-or-lexer-ambiguity assumption, we give the weights back their lexer-state dimension, and represent the parser stacks as graph-structured stacks GSS[LRState] rather than simple list[LRState]s. Then run becomes a simultaneous traversal of two graphs: the parser DWA on one hand, and a GSS on the other:

...  # <fold>

type GSS[T] = dict[T, GSS[T]]

@dataclass
class DWA[T, W: Semiring]:
    ...  # <fold>
    def run_gss(self, input: GSS[T], wi: W) -> W:
        def visit(gss: GSS[T], state: State, active_weight: W) -> W:
            out = active_weight * self.final_weights[state]

            for x, tail in gss.items():
                next_state, edge_weight = self.transitions[state][x]
                out += visit(tail, next_state, active_weight * edge_weight)

            return out

        return visit(input, self.start, wi)

@dataclass
class Constraint:
    ...  # <fold>
    def get_mask(self) -> TokenMask:
        mask = np.zeros(self.token_count, dtype=bool)

        for lexer_state, gss in self.state.items():
            wi = np.zeros((self.lexer_state_count, self.token_count), dtype=bool)
            wi[lexer_state, :] = True
            mask |= self.parser_dwa.run_gss(gss, wi)[lexer_state]

        return mask

from __future__ import annotations

from dataclasses import dataclass
from typing import Protocol, Self

import numpy as np
from jaxtyping import Bool


class Semiring(Protocol):
    def __add__(self, other: Self) -> Self: ...
    def __mul__(self, other: Self) -> Self: ...


type LexerState = int
type LRState = int
type State = int
type TokenMask = Bool[np.ndarray, "token"]
type Weight = Bool[np.ndarray, "lexer_state token"]
type ParserDWA = DWA[LRState, Weight]


type GSS[T] = dict[T, GSS[T]]


@dataclass
class DWA[T, W: Semiring]:
    start: State
    transitions: dict[State, dict[T, tuple[State, W]]]
    final_weights: dict[State, W]

    def run_gss(self, input: GSS[T], wi: W) -> W:
        def visit(gss: GSS[T], state: State, active_weight: W) -> W:
            out = active_weight * self.final_weights[state]

            for x, tail in gss.items():
                next_state, edge_weight = self.transitions[state][x]
                out += visit(tail, next_state, active_weight * edge_weight)

            return out

        return visit(input, self.start, wi)


@dataclass
class Constraint:
    parser_dwa: ParserDWA
    state: dict[LexerState, GSS[LRState]]
    lexer_state_count: int
    token_count: int

    def get_mask(self) -> TokenMask:
        mask = np.zeros(self.token_count, dtype=bool)

        for lexer_state, gss in self.state.items():
            wi = np.zeros((self.lexer_state_count, self.token_count), dtype=bool)
            wi[lexer_state, :] = True
            mask |= self.parser_dwa.run_gss(gss, wi)[lexer_state]

        return mask

Notice what kind of work this is. The runtime is mostly table lookups and bitset operations. This feels very fast. Maybe as fast as mask generation can be.

Could some other approach be faster still? A highly ambiguous grammar can still make the GSS large, and GLR’s worst cases do not disappear. In practice, though, GLR remains hard to beat for incremental parsing under ambiguity, and ordinary JSON and code-like grammars keep the GSS small. And therein lies why the runtime feels near optimal. It reads only the stack prefix it needs, using table lookups and bulk token-set operations, without traversing the vocabulary trie or running the parser for candidate tokens.

Longest match: Tying up loose ends with Weighted GSS

We’ve ignored one lexer detail so far: longest match. Suppose the terminal PLUS accepts both + and ++. After the first +, PLUS matches, but the lexer cannot yet know that this is the match it should emit; another + would make it longer.

GLRMask keeps both possibilities:

keep scanning, in case PLUS extends;
emit the short PLUS, but attach a condition that PLUS must not later match from the saved continuation state.

If another + extends the match, the short branch is removed. If the longer match becomes impossible, the open branch dies and the condition on the short branch can be dropped.

These conditions are cheap to check because GLRMask precomputes the relevant token sets over the vocabulary. For each lexer state $q$ and terminal $t$ , it stores a bitset $M(q,t)$ of model tokens for which $t$ would match from $q$ . If a branch says that $t$ must not match from $q$ , those tokens are removed from its mask. With several conditions, a token is removed if it violates any of them.

The conditions above have to be stored separately for different GLR stack paths. GLRMask does this with a weighted graph-structured stack.

An ordinary GSS represents a set of stacks,

S \subseteq \Gamma^*.

A weighted GSS represents a value attached to each of those stacks,

w:S\to K.

For GLRMask, that value is initially the set of longest-match conditions carried by the stack.

Why put the value inside the GSS? Suppose two runtime branches have the same parser stacks but different conditions. If the conditions live outside the GSS, either the GSS update runs twice, or the implementation has to discover afterwards that the resulting GSSs are equal and merge them. Pointer equality misses structurally equal copies; structural equality can require walking a large graph.

Even exact GSS equality is not enough. Two GSSs can differ in one place while sharing almost everything else. They cannot be merged as whole objects, so the shared subgraphs still get duplicate attached-value work.

The separate weighted-gss library stores the value in the shared graph itself. GLR states live on edges and weights live on nodes, arranged so that each represented stack has one weight. When stack paths merge, their weights merge too. Long straight runs are stored as segments, and the library can lift weights towards the root when possible.

During mask generation, the attached value changes from longest-match conditions to token masks:

\operatorname{WeightedGSS}\langle S,\mathrm{Conditions}\rangle \longrightarrow \operatorname{WeightedGSS}\langle S,\mathrm{Mask}\rangle.

The stack structure stays shared throughout.

This changes the pseudocode in one important place. Before, every stack path in one GSS began with the same wi. Now each path begins with the mask implied by its own longest-match conditions. We transform those conditions into Boolean weights first, then run the same Parser-DWA walk over the weighted GSS:

...  # <fold>

@dataclass
class Constraint:
    ...  # <fold>
    def get_mask(self) -> TokenMask:
        ...  # <fold>
        for lexer_state, gss in self.state.items():
            gss = self.initialize_weights(lexer_state, gss)
            mask |= self.parser_dwa.run_weighted_gss(gss)[lexer_state]

        return mask

from __future__ import annotations

from collections.abc import Callable
from dataclasses import dataclass
from typing import Protocol, Self
from typing import TypeVar

import numpy as np
from jaxtyping import Bool
from weighted_gss import WeightedGSS


V = TypeVar("V")


class Semiring(Protocol):
    def __add__(self, other: Self) -> Self: ...
    def __mul__(self, other: Self) -> Self: ...


type LexerState = int
type LRState = int
type Terminal = int
type State = int
type TokenMask = Bool[np.ndarray, "token"]
type Weight = Bool[np.ndarray, "lexer_state token"]
type Condition = tuple[LexerState, Terminal]
type Conditions = frozenset[Condition]
type ParserDWA = DWA[LRState, Weight]


@dataclass
class GSS[T, W]:
    # Internals omitted (not trivial).
    def joined_weight(self) -> W: ...
    def pop_branches(self) -> list[tuple[T, GSS[T, W]]]: ...
    def map_weights(self, f: Callable[[W], V]) -> GSS[T, V]: ...


@dataclass
class DWA[T, W: Semiring]:
    start: State
    transitions: dict[State, dict[T, tuple[State, W]]]
    final_weights: dict[State, W]

    def run_weighted_gss(self, input: WeightedGSS[T, W]) -> W:
        def visit(gss: WeightedGSS[T, W], state: State) -> W:
            out = gss.joined_weight() * self.final_weights[state]

            for x, tail in gss.pop_branches():
                next_state, edge_weight = self.transitions[state][x]
                tail = tail.map_weights(lambda active_weight: active_weight * edge_weight)
                out += visit(tail, next_state)

            return out

        return visit(input, self.start)


@dataclass
class Constraint:
    parser_dwa: ParserDWA
    state: dict[LexerState, WeightedGSS[LRState, Conditions]]
    possible_matches: dict[tuple[LexerState, Terminal], TokenMask]
    lexer_state_count: int
    token_count: int

    def initialize_weights(
        self,
        lexer_state: LexerState,
        gss: WeightedGSS[LRState, Conditions],
    ) -> WeightedGSS[LRState, Weight]:
        """WeightedGSS[LRState, Conditions] -> WeightedGSS[LRState, Weight]"""
        def initial_weight(conditions: Conditions) -> Weight:
            w = np.zeros((self.lexer_state_count, self.token_count), dtype=bool)
            w[lexer_state, :] = True

            for q, t in conditions:
                w[lexer_state] &= ~self.possible_matches[q, t]

            return w

        return gss.map_weights(initial_weight)

    def get_mask(self) -> TokenMask:
        mask = np.zeros(self.token_count, dtype=bool)

        for lexer_state, gss in self.state.items():
            gss = self.initialize_weights(lexer_state, gss)
            mask |= self.parser_dwa.run_weighted_gss(gss)[lexer_state]

        return mask

The abstraction is simple enough that its performance impact is easy to underestimate. In GLRMask it has been essential for single-digit-microsecond incremental GLR operations.

More generally, it may be useful when a persistent GSS is updated repeatedly and each represented stack carries some extra value. If keeping that value outside the GSS causes duplicate updates or expensive whole-GSS deduplication, especially when the graphs are often almost equal, putting the value into the shared structure can avoid that work.

Putting it all together

from __future__ import annotations

from dataclasses import dataclass
from typing import Protocol, Self

import numpy as np
from jaxtyping import Bool
from weighted_gss import WeightedGSS


class Semiring(Protocol):
    def __add__(self, other: Self) -> Self: ...
    def __mul__(self, other: Self) -> Self: ...


type LexerState = int
type LRState = int
type Terminal = int
type State = int
type TokenMask = Bool[np.ndarray, "token"]
type Weight = Bool[np.ndarray, "lexer_state token"]
type Condition = tuple[LexerState, Terminal]
type Conditions = frozenset[Condition]
type ParserDWA = DWA[LRState, Weight]


@dataclass
class DWA[T, W: Semiring]:
    start: State
    transitions: dict[State, dict[T, tuple[State, W]]]
    final_weights: dict[State, W]

    def run_weighted_gss(self, input: WeightedGSS[T, W]) -> W:
        def visit(gss: WeightedGSS[T, W], state: State) -> W:
            out = gss.joined_weight() * self.final_weights[state]

            for x, tail in gss.pop_branches():
                next_state, edge_weight = self.transitions[state][x]
                tail = tail.map_weights(lambda active_weight: active_weight * edge_weight)
                out += visit(tail, next_state)

            return out

        return visit(input, self.start)


@dataclass
class Constraint:
    parser_dwa: ParserDWA
    state: dict[LexerState, WeightedGSS[LRState, Conditions]]
    possible_matches: dict[tuple[LexerState, Terminal], TokenMask]
    lexer_state_count: int
    token_count: int

    def initialize_weights(
        self,
        lexer_state: LexerState,
        gss: WeightedGSS[LRState, Conditions],
    ) -> WeightedGSS[LRState, Weight]:
        """WeightedGSS[LRState, Conditions] -> WeightedGSS[LRState, Weight]"""
        def initial_weight(conditions: Conditions) -> Weight:
            w = np.zeros((self.lexer_state_count, self.token_count), dtype=bool)
            w[lexer_state, :] = True

            for q, t in conditions:
                w[lexer_state] &= ~self.possible_matches[q, t]

            return w

        return gss.map_weights(initial_weight)

    def get_mask(self) -> TokenMask:
        mask = np.zeros(self.token_count, dtype=bool)

        for lexer_state, gss in self.state.items():
            gss = self.initialize_weights(lexer_state, gss)
            mask |= self.parser_dwa.run_weighted_gss(gss)[lexer_state]

        return mask

Benchmarks

The paired JSON Schema Bench publication run covered 10,263 schemas and just over three million timed token steps per framework. Per-step mask-and-commit time (TBM):

system	median TBM	mean TBM	p99	p99.9	max	TPS ceiling
GLRMask	4.06 µs	4.52 µs	12.8 µs	20.7 µs	144 µs	221,471 tok/s
llguidance	14.7 µs	27.1 µs	259 µs	964 µs	7.80 ms	36,903 tok/s

Time to the first mask, with compilation included, went the other way. GLRMask measured 23.8 ms median, 81.5 ms mean, 780 ms p99, 3.36 s p99.9 and 5.11 s max; llguidance measured 1.08 ms median, 1.76 ms mean, 13.4 ms p99, 45.0 ms p99.9 and 205 ms max.

JavaScript leaves much more parser work on llguidance’s online path. For a direct grammar-shape comparison I used the same two JavaScript smoke inputs, 40 Llama-3 token steps in total. The first run uses each system’s optimized JS setup: GLRMask uses its native GLRM grammar, while llguidance gets the hand-tuned companion grammar, larger parser limits, and JavaScript tokenizer slices.

system	median TBM	mean TBM	p99	p99.9	max	TPS ceiling
GLRMask	50.6 µs	57.2 µs	151 µs	153 µs	154 µs	17,473 tok/s
llguidance	1.60 ms	1.62 ms	4.52 ms	4.62 ms	4.63 ms	616 tok/s

For the naive run, both systems get the exact same checked-in js.ebnf grammar. No llguidance-specific %ignore rewrite, parser-limit tuning or tokenizer slices:

system	median TBM	mean TBM	p99	p99.9	max	TPS ceiling
GLRMask	127 µs	155 µs	406 µs	419 µs	420 µs	6,438 tok/s
llguidance	21.6 ms	19.8 ms	35.9 ms	37.0 ms	37.1 ms	51 tok/s

GLRMask slows down on the generic grammar, but remains below half a millisecond even at the maximum. llguidance is much more sensitive to the grammar representation. Its median moves from 1.60 ms to 21.6 ms.

The TPS ceiling is the reciprocal of mean TBM: the rate the constraint engine alone could sustain if the GPU and model took no time at all. Real end-to-end generation is lower once model time and the rest of the decoding loop are included. With only 40 steps in the two smoke-input runs, p99.9 is necessarily very close to the observed maximum.

The larger tuned corpus contains 31 JavaScript fixtures and 4,099 token steps:

system	median TBM	mean TBM	p99	p99.9	max	TPS ceiling
GLRMask	40.9 µs	50.4 µs	192 µs	306 µs	497 µs	19,860 tok/s
llguidance	1.05 ms	1.17 ms	3.28 ms	3.83 ms	4.13 ms	854 tok/s

GLRMask compilation for these JavaScript grammars takes on the order of tens of seconds on the M1 Pro used here, while llguidance builds in milliseconds. That compilation cost is the subject of the next section.

Aggregate percentiles also hide where the time goes. I broke down one real JSON input and one real JavaScript input token by token in Where constrained decoding time goes: GLRMask vs llguidance.

Trade-off

GLRMask makes the most sense when a constraint will be reused, when very low and predictable mask latency is especially important, or when the grammar leaves substantial parser work on the online path.

GLRMask compilation is heavily parallelized, and build-time optimization has largely focused on making effective use of the available cores. That reduces build time, but it can also create sharp CPU and memory spikes. To keep those spikes away from inference, the recommended setup is to compile on a separate server:

compile constraints on a separate server, with enough CPU and memory to finish them quickly;
cache the compiled artifacts;
push those artifacts to the inference servers that need them.

If a constraint arrives dynamically, an online decoder can serve it immediately while GLRMask compiles elsewhere. Later requests can switch to the compiled artifact.

For a new JSON Schema used once, llguidance may well cost less in total. Its start-up cost is tiny, and it is very good at avoiding work until that work is actually needed. JSON gives it two useful fast paths. Inside strings, many tokens consist entirely of bytes that stay inside the current string lexeme, so llguidance can accept precomputed slices of the vocabulary without walking those parts of the trie or touching the parser. Property names and other exact literals go the other way: the allowed byte sequence is narrow, so a wrong prefix rejects a whole trie subtree almost immediately. The slice check applies to one active lexeme at a time. In the Llama-3 vocabulary used here, 43,044 of 128,256 tokens are one ASCII space followed by letters, so ordinary code tokens often cross from skipped whitespace into the next lexeme and stay in the trie walk. Walking a large part of the trie while repeatedly crossing lexer boundaries and advancing the parser comes up less often in JSON. For one-off constraints, that can make more sense than compiling a GLRMask artifact.

Appendix: Compilation

You might reasonably object at this point. Stack effects? A Parser DWA? This is a lot of effort just to get the parser off the online path. There isn’t that much parser work to do during mask generation (which is true). Why not keep the Terminal DWA and traverse over that at runtime instead, feeding each edge’s terminal into the parser as we walk? We would still be spared the vocabulary trie.

Well, yes, you could, and it might even be fast. But building the Parser DWA once you have the Terminal DWA is kind of easy, conceptually and in a lot of cases computationally as well (a full JavaScript grammar being a notable exception). The actual hard part is building the Terminal DWA quickly and without exhausting memory. The finished Terminal DWA can be tiny while the intermediate NWAs built on the way there are huge. A direct build over the full vocabulary and lexer state set can blow well past any reasonable memory or time budget, so a big part of the compiler’s job is to shrink the problem before doing it.

Within a partition, the compiler can use properties that do not hold over the full vocabulary. Tokens are grouped roughly by byte shape and length into word-like, numeric, punctuation and non-ASCII partitions; long tokens and tokens that cross structural boundaries are handled separately.

Consider a partition whose LLM tokens contain no alphabetical bytes. Property-key literals such as "name": , "title": and "enabled": differ mainly in the letters between the quotes. Those letters cannot occur in this partition. In the restricted view used for this build, the alphabetic transitions disappear and the literals are left with the same punctuation around them: the opening quote, the closing quote, the colon after it, and the following space. The terminals can therefore be treated as equivalent for this partition and represented by one member of the class through most of the build.

Now take a partition containing only alphabetical bytes. The same property-key literals do differ here, because a token may consume letters from inside "name": or "enabled": . But such a token cannot also contain the closing quote, the colon, or the following space. It therefore cannot finish the property-key terminal and continue into another terminal. For most literal terminals in this partition, every possible path has length one. GLRMask calls these terminals L1 and puts the remainder in L2P. Each partition gets one Terminal DWA for L1 and another for L2P, and the L1 build can use algorithms that assume there will never be a two-terminal path.

Terminal synthesis and terminal equivalence also run per partition. Terminal synthesis rebuilds terminal expressions using only the bytes that occur in the partition and its token-length limit. Terminal equivalence groups terminals whose observable behaviour in the partition is identical. The compiler carries one representative from each class through the expensive work, then restores the class members afterwards. When every partition has finished, the per-partition L1 and L2P Terminal DWAs are merged layer by layer and passed separately into the Parser-DWA build.

There are plenty of smaller compile-time optimizations as well, mostly aimed at avoiding repeated work or keeping intermediate automata small. They matter, but they are less interesting than the partition-local reductions above.

RangeSetBlaze deserves a special mention. Weights contain large sets of token IDs, and those IDs often occur in long contiguous runs. RangeSetBlaze stores the sets directly as sorted integer ranges and supports the set operations GLRMask needs without expanding them into individual token IDs. It ended up being useful all over the compiler, but especially for representing and manipulating weights.

Appendix: The construction in equations

A model token may produce one or more terminal sequences. Each sequence induces a stack effect. The Parser DWA keeps only the read prefix of that effect: the part that must be present on the parser stack.

The weights are Boolean masks indexed by lexer state and model token:

K=\mathbb B^{Q_{\mathrm{lex}}\times\mathcal V}, \qquad W_{qv}\in\mathbb B.

Weights combine pointwise by union and intersection:

(W\oplus W')_{qv}=W_{qv}\lor W'_{qv}, \qquad (W\otimes W')_{qv}=W_{qv}\land W'_{qv}.

A deterministic weighted automaton is

\mathcal A=(S,s_0,\tau,\varphi), \qquad \tau:S\times\Sigma\rightharpoonup S\times K.

If its run on $a_1\cdots a_m$ is

s_0\xrightarrow{a_1/W_1}s_1 \xrightarrow{a_2/W_2}\cdots \xrightarrow{a_m/W_m}s_m,

its value is the intersection of the transition weights and the final weight:

\big[\!\big[\mathcal A\big]\!\big](a_1\cdots a_m) =W_1\otimes\cdots\otimes W_m\otimes\varphi(s_m).

The Terminal DWA stores which lexer-state/token pairs produce each grammar terminal sequence. If $\beta(v)$ is the byte string of model token $v$ , then

\big[\!\big[\mathcal T_{\mathrm{DWA}}\big]\!\big](r)_{qv}=1 \quad\Longleftrightarrow\quad r\in\mathrm{Lex}(q,\beta(v)).

Here $r=t_1\cdots t_k$ is a sequence of grammar terminals.

Each terminal $t$ has a language $E_t$ of parser-stack effects. For parser stack alphabet $\Gamma$ , introduce a read and a write symbol for every parser state:

\Gamma^\pm=\{p^-,p^+:p\in\Gamma\}.

An effect $u^-z^+\in E_t$ means that consuming $t$ can replace the top prefix $u$ with $z$ :

u\alpha\overset{t}{\mapsto}z\alpha \qquad(\alpha\in\Gamma^*).

Adjacent writes and reads cancel when their parser states agree. A disagreement kills the path:

p^+p^-\to\epsilon, \qquad p^+q^-\to\bot\quad(p\ne q).

Writing $\preceq$ for prefix order, composition of two stack effects is

(u^-x^+)\odot(y^-z^+) := \begin{cases} u^-a^+z^+, & x=ya,\\ u^-a^-z^+, & y=xa,\\ \bot, & x\not\preceq y\ \land\ y\not\preceq x. \end{cases}

Composition extends from individual effects to their languages:

E\odot F =\{x\odot y:x\in E,\ y\in F,\ x\odot y\ne\bot\}.

So the net effects of a terminal sequence $r=t_1\cdots t_k$ are

E_r=E_{t_1}\odot\cdots\odot E_{t_k}, \qquad E_\epsilon=\{\epsilon\}.

For mask generation, only the read prefix matters: the part that had to exist before the token began. Project each net effect onto that prefix:

\widehat E_r = \{u\in\Gamma^*: \exists z\in\Gamma^*,\ u^-z^+\in E_r\}.

A terminal sequence is parseable from stack $\sigma$ exactly when one of these read prefixes occurs at the top of $\sigma$ :

\mathrm{Parseable}(r,\sigma) \quad\Longleftrightarrow\quad \exists u\in\widehat E_r,\ \exists\alpha:\ \sigma=u\alpha.

A model token may produce several terminal sequences, so its read-prefix language is their union:

\widehat E_{q,v} = \bigcup_{r\in\mathrm{Lex}(q,\beta(v))}\widehat E_r.

The Parser DWA stores all of these languages in one weighted automaton:

\big[\!\big[\mathcal P_{\mathrm{DWA}}\big]\!\big](\rho)_{qv}=1 \quad\Longleftrightarrow\quad \rho\in\widehat E_{q,v}.

The Parser DWA therefore satisfies:

\begin{aligned} \big[\!\big[\mathcal P_{\mathrm{DWA}}\big]\!\big](\rho)_{qv}=1 &\quad\Longleftrightarrow\quad \rho\in\widehat E_{q,v}\\ &\quad\Longleftrightarrow\quad \exists r:\ \big[\!\big[\mathcal T_{\mathrm{DWA}}\big]\!\big](r)_{qv}=1 \ \land\ \rho\in\widehat E_r. \end{aligned}

Ignoring longest-match exclusions for now, $\mathrm{ParserOK}(q,\sigma,v)$ holds exactly when some top prefix $\rho$ of $\sigma$ has Parser-DWA value containing $(q,v)$ :

\mathrm{ParserOK}(q,\sigma,v) \quad\Longleftrightarrow\quad \exists\rho,\alpha:\ \sigma=\rho\alpha \ \land\ \big[\!\big[\mathcal P_{\mathrm{DWA}}\big]\!\big](\rho)_{qv}=1.

Suppose one token emits the two terminals x and ], with effects

b^-b^+p^+\in E_{\texttt{x}}, \qquad p^-b^-c^+\in E_{\texttt{]}}.

Their internal parser work disappears:

(b^-b^+p^+)(p^-b^-c^+) \longrightarrow b^-b^+b^-c^+ \longrightarrow b^-c^+.

The token may perform several reductions and shifts internally, but the mask query only has to check that the old stack begins with $b$ .

In one line:

\big[\!\big[\mathcal P_{\mathrm{DWA}}\big]\!\big](\rho)_{qv} = \bigvee_{r\in\mathcal T^*} \left( \big[\!\big[\mathcal T_{\mathrm{DWA}}\big]\!\big](r)_{qv} \land [\rho\in\widehat E_r] \right).

Assuming sampling without replacement. ↩
Constrained decoding can hurt task performance even when it guarantees syntactic validity. Greedily masking and renormalizing over the tokens that are legal at the current step can distort the model’s original distribution, while token/grammar misalignment can force unnatural tokenizations and reduce accuracy. See Grammar-Aligned Decoding and DOMINO. ↩