(archived) The 112-hyphen token

Did you know that this is perfectly valid Python?

-----------------------1

So is this:

-+-+-+-+-+-+-+-+-+-+-+-+1

Did you know, also, that this is a single GPT-5 token?

----------------------------------------------------------------------------------------------------------------ID: 182513

Wow. Stunning. A real chonker.

A Python lexer may turn those bytes into 112 MINUS terminals. An LR parser may reduce before each shift. A GLR parser may branch and merge through a graph-structured stack.

A grammar-constrained decoder may perform all of that merely to decide whether the model is allowed to choose one vocabulary token.

I’ve spent the past few years working on GLRMask, a grammar-constrained decoding library. Chonkers like this have consumed a frankly unreasonable amount of that time.

Mask and commit

At each decoding step, the model produces logits over its vocabulary. A constraint computes a Boolean mask of legal tokens, the sampler applies it, and one token is chosen.

mask = constraint.get_mask()
token = sample(logits, mask)
constraint.commit(token)

commit advances the actual lexer and parser with the sampled token. get_mask asks which vocabulary tokens could be committed safely.

The GPU can compute logits while the CPU computes the mask, but sampling waits for both. A slow mask call delays the entire decoding step.

commit processes one token. get_mask considers roughly 200,000 candidates.

Programmatic tool calling is the obvious application: turn a tool’s JSON Schema into a grammar and prevent the model from producing a syntactically malformed call. The model can still request the weather on the Sun, but it cannot forget the closing brace.

Model tokens and grammar terminals

A parser does not consume model tokens. It consumes grammar terminals emitted by a lexer. The two tokenisations split the same bytes for unrelated reasons.

One model token may:

• complete several grammar terminals, such as "}\n" becoming RBRACE NEWLINE;
• stop halfway through a string, number or keyword;
• add bytes without completing any terminal;
• admit several possible terminal sequences.

Testing one model token therefore means continuing the current lexer with its bytes, considering every terminal sequence those bytes can produce, and asking whether the parser can consume each sequence from its current stack.

The sixteen-hyphen case is easier to inspect than the 112-hyphen token:

The hyphens may be one model token:

The grammar lexer sees sixteen terminals:

An LR shift may first require several reductions: pop parser states, follow a goto transition, then shift the terminal. Under GLR, conflicts may produce several legal stacks represented compactly in a GSS. A candidate model token can therefore hide a whole sequence of reductions, shifts, branches and merges.

During commit, those sixteen terminals are simply the input that happened. During get_mask, they are parser work hidden inside one candidate token.

Walking the vocabulary online

Brute force copies the constraint state, commits every vocabulary token and keeps the successful ones. A vocabulary trie shares byte prefixes and prunes a whole subtree when its prefix becomes invalid.

llguidance is the best online trie-and-parser system I know. It walks the trie from an Earley row and lexer state. Most bytes stay in cached lexer machinery; the parser wakes when lexemes finish. JSON Schema suits this design unusually well: most bytes continue a string or number, parser events are sparse, compilation is tiny and the resulting masks are already fast enough for many systems.

My first GLRMask implementations put an incremental GLR parser inside a similar trie traversal. I removed unit and nullable reductions, simplified GSS nodes aggressively, memoised parser actions and added early exits. Common calls became fast. The slowest calls still followed the parser work embedded in candidate-token lexes.

A trie can share the bytes of the 112-hyphen token with shorter hyphen tokens. It cannot erase 112 terminal completions along the path. After the grammar transformations, GSS simplifications, memoisation and early exits, the tail still varied with the amount of lexer and parser execution packed into candidate tokens. I no longer expected another online optimisation to make that dependence predictable across difficult CFGs.

I wanted the slowest masks down in the tens of microseconds on grammars and vocabularies much less friendly than JSON. The vocabulary, lexer, grammar and LR tables are fixed before generation. A model token’s bytes determine its possible terminal sequences, and the grammar and LR tables determine the possible stack effects of each sequence. GLRMask flattens this fixed token–lexer–parser computation into a family of stack recognisers, one for each lexer state and model token.

A recogniser for the stacks that admit one token

Fix lexer state $q$ and model token $v$, with byte string $\beta(v)$. Define

$$L_{q,v}=\{\Gamma : \beta(v)\text{ can be lexed and parsed from }(q,\Gamma)\},$$

where $\Gamma$ is an LR stack written as parser-state IDs from top to bottom.

For fixed $q$ and $v$, $L_{q,v}$ is a regular language over parser-state IDs, closely related to the classical regularity of LR viable prefixes but narrowed to the stacks from which one fixed model token can be consumed. GLRMask has to build these recognisers before the runtime stacks exist.

Lexing $\beta(v)$ may produce several terminal sequences. Consider one:

$$r=t_1t_2\dots t_k.$$

For each grammar terminal $t$, GLRMask builds a template automaton. Its paths describe legal LR reduction chains followed by a shift of $t$.

A path records stack reads and writes. Write $p^-$ for requiring and removing parser state $p$, and $p^+$ for writing it. Two adjacent terminal paths may have effects

$$(p^-r^+s^+)\qquad(s^-r^-u^+).$$

The first terminal creates intermediate states $r,s$; the second consumes them. Composition cancels that internal work:

$$(p^-r^+s^+)\,(s^-r^-u^+)\rightarrow p^-u^+.$$

A write followed by a different read rejects the path:

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

After composing every terminal in $r$, each surviving path has the form

$$x^-y^+.$$

The old stack must provide $x$. Committing the token would leave $y$ on the new stack.

get_mask only needs the precondition $x$. The path already represents successful consumption of the complete token; the actual parser will construct $y$ if the token is sampled. The compiler projects away the final writes.

The projected paths recognise a regular language $L_r$ of old stacks. If the token has several possible lexes,

$$L_{q,v}=\bigcup_{r\in\operatorname{Lex}(q,\beta(v))}L_r.$$

For the 112-hyphen token, parser states created and consumed among the 112 MINUS terminals cancel during compilation. The recogniser retains only the old-stack prefix on which the complete token depends. Runtime does not perform 112 shifts; it tests the current stack against that recogniser.

From the Terminal DWA to the Parser DWA

GLRMask constructs the lexical side for the whole vocabulary at once. It builds a trie over model-token byte strings and simulates the grammar lexer from every relevant lexer state. When a grammar terminal completes, the compiler records a terminal-labelled edge, the continuation lexer state and the model tokens that reached it.

Paths through this acyclic Terminal DWA are the possible terminal sequences produced by model tokens.

The compiler replaces each terminal-labelled edge with the corresponding parser template. Token weights follow the inserted paths. Stack effects cancel across terminal boundaries, mismatches disappear and final writes are projected away.

This produces the family of old-stack recognisers, with a great deal of shared graph structure. GLRMask stores the shared graph as a weighted automaton. Conceptually, a weight is a set of (lexer state, model token) pairs. The implementation stores it as a map from compiled tokenizer-state IDs to token sets.

Following a transition intersects the live weight with the transition weight. Alternative paths combine by union. Final weights record which pairs accept after the stack prefix read so far.

Filter every weight to one pair $(q,v)$ and the graph becomes the ordinary recogniser for $L_{q,v}$. Keep the whole weight and one traversal evaluates the entire family. After simplification and determinisation, the graph is the Parser DWA.

The construction needs a bound on parser work between terminals. GLRMask’s table-build normal form rejects reachable nullable and zero-length productions, right-recursive cycles that would create unbounded reduction chains, and indirect left-recursive cycles that can create unbounded GSS growth. Long productions are lowered before this stage. Aycock et al. study the same bounded-reduction problem in Even Faster Generalized LR Parsing.

The terminal templates are then acyclic and bounded in depth. Model-token byte paths are finite. The Parser DWA reads only a bounded prefix of an LR stack, although the stack itself may be arbitrarily deep.

Reading an LR stack or GSS

For one LR stack, the runtime has this shape:

def get_mask(stack_top_to_bottom, active_lexer_states):
    state = parser_dwa.start
    alive = weight_for(active_lexer_states)
    result = alive & parser_dwa.final_weight(state)

    for parser_state in stack_top_to_bottom:
        edge = parser_dwa.step(state, parser_state)
        if edge is None:
            break

        state, weight = edge
        alive &= weight
        if not alive:
            break

        result |= alive & parser_dwa.final_weight(state)

    return project_to_tokens(result)

For GLR, every path through the GSS is one LR stack and common suffixes are shared. GLRMask traverses the product of the GSS and Parser DWA. Work that reaches the same GSS node and DWA state is joined, so the shared suffix is read once.

get_mask does not loop over the vocabulary, walk candidate bytes, mutate the parser or execute reductions for hypothetical tokens. It reads a bounded part of the current parse representation using transition lookups, weight intersections and unions. It stops when nothing remains live or when deeper stack states cannot affect the answer.

commit still feeds the sampled token’s bytes into the real incremental lexer and GLR parser. It mutates the GSS and lexer state for the next decoding step.

The bounded Parser DWA does not give GLR as a whole pleasant adversarial bounds. A highly ambiguous grammar can still produce a large GSS, and mask time depends on the relevant part of that represented parse state. In my experience, JSON schemas and programming-language-like grammars with reasonable disambiguation usually keep the GSS modest.

GLR-like methods nevertheless remain a hard baseline to beat for incremental ambiguous parsing; Laurie Tratt’s survey, Lezer, tree-sitter and Elkhound all approach related territory.

I do not have an optimality theorem. But to me, GLRMask feels close to optimal at runtime in the same sense that llguidance feels close to optimal at compile time. GLRMask spends heavily before generation; mask time reads a bounded part of the existing parse representation, performs predictable set operations, stops early, avoids a vocabulary loop and does not run the parser for candidate tokens. The work follows the current parse configuration rather than the number of parser events hidden throughout the vocabulary.

A terminal boundary that may move

Longest-match lexing leaves one piece of uncertainty at runtime. Suppose a terminal accepts both + and ++. After one +, the shorter match is valid but may still grow. A conventional scanner reads ahead and can return to its last accepting position if the longer attempt fails. Generation cannot retract bytes already sampled across a model-token boundary.

GLRMask keeps one branch waiting for the longer match and another that emits the shorter terminal. The early-emission branch records that terminal as excluded while the tokenizer continuation still has the same terminal in its strict future. If the terminal later completes from that continuation, the earlier boundary was premature and the branch is invalid. If the terminal drops out of the strict future first, the exclusion can be discarded.

The persistent GSS shares immutable stack suffixes between these branches. Each path carries a small exclusion map; equivalent parser paths join their maps when they merge. Active lexer states choose the relevant rows of the Parser-DWA weights during the next mask query.

I wrote more about the awkward lexer cases in llguidance HATES This One Weird Grammar.

The compiler ate the project

The final Parser DWA can be compact while a naive construction is enormous. Template substitution creates intermediate paths. Determinisation can multiply states. Weight maps fragment into many ranges. A straightforward compiler may run out of memory before reaching a small result.

GLRMask reduces semantic cases before expansion. Tokens and lexer states with identical consequences are grouped. Interchangeable terminals compile through representatives. Terminal-DWA edges with common continuations are combined before templates are substituted. Cancellation and dead-path pruning happen during construction. Determinisation and minimisation order matters, and simple structural families use specialised builders.

Weights are conceptually maps of token sets. GLRMask stores the map keys and token sets as sorted integer ranges. IDs are remapped so values that co-occur tend to form fewer ranges; repeated outer maps and inner token sets are interned. RangeSetBlaze was a huge help. It is a very nice, underappreciated data structure.

The persistent GSS became the separate weighted-gss library. It supports joinable path-local weights such as the longest-match exclusions above, while sharing stack structure. Long deterministic runs are packed into segments so ordinary parsing does not pay for a separate graph node per stack state.

The repository began in June 2024 as grammars2024, became Sep1 and eventually GLRMask. It is now a Rust and Python library containing the compiler, runtime, tests, examples and benchmark harnesses. Most of the project is the compiler required to produce the small mask-time machine.

For a fresh JSON Schema used once, llguidance is probably the better trade. Its cold path is tiny and its masks are already fast. That compilation starts to make sense when constraints are reused, arbitrary CFG behaviour matters, model tokens trigger substantial parser work or tail mask latency justifies the machinery.

Tool calls, scratch work and irreversible mistakes

Young folk might not remember, but in the old days (one year ago) models were quite bad at tool calls. They were not merely bad at choosing the right tool. They were bad at calling tools period.

Ask for exactly YES or NO and receive The answer is YES. Ask for JSON and receive bare JSON, fenced JSON, a preamble followed by JSON, or three different JSON blocks with commentary between them. You could write a parser for every case you had seen. The model would eventually invent another one.

A grammar solves the syntactic part. It cannot rescue intent, and it can force a strange recovery from a decision that has already been sampled. Suppose a tool call permits a comment:

{
  "tool": "get_weather",
  "arguments": {"location": "Perth"},
  "comment": "The user said \"Perth\", so I'll check there."
}

Without the escapes around Perth, the quote after The user said ends the string. The decoder discovers the mistake only when the model tries to continue. It cannot go back and insert an escape, so the grammar may force

{"tool":"get_weather","arguments":{"location":"Perth"},"comment":"The user said "}

The output parses. It makes less sense. But hey, at least it now parses.

There is a bunch of work on this: Grammar-Aligned Decoding, Let Me Speak Freely? and The Hidden Cost of Structure.

Before the age of thinking models, I also used grammar constraints to keep <answer> out of reach until a model had generated some minimum amount of scratch work:

<thinking>
...
</thinking>
<answer>
...
</answer>

A crude grammar required at least 256 characters inside <thinking>:

start: "<thinking>" THINKING "</thinking>" "<answer>" ANSWER "</answer>"

THINKING: /[^<]{256,}/
ANSWER: /[^<]+/

Until THINKING had matched 256 characters, </thinking> and therefore <answer> were not legal next. The model could still reason badly. This was before prompt caching, mind you, so repeatedly feeding its earlier reasoning back to it was expensive. No 90% cached-input discount. Imagine that.

Anyway, that is ancient history. Programmatic tool calling is the obvious use now. Better models may make syntax constraints less important, but small and on-device models may keep them relevant for quite a while.

Life after parsing

It’s been fun, and I’m proud of the result. I think the construction is novel. Even though it is complicated to compile, there’s something satisfyingly simple about the runtime: reading the parse stack directly through a weighted automaton, computing the mask via fast weight intersections.

If I’m honest, though, it is probably overkill. Most constrained generation is done on JSON Schemas. And honestly, maybe if llguidance doesn’t like your grammar, you should fix your grammar? If its lexer semantics are causing you trouble, maybe you can fix that by splitting up your terminals.

So why bother solving the general case?

One explanation: When I started working on this, tool-using LLM agents were not really a thing. So, it was somewhat less obvious that JSON Schema was going to account for $99.\overline{9}\%$ of the useful work. Still, I think it was predictable.

A more general (and pessimistic) explanation has to do with not just grammar constrained generation, but grammars more generally: Grammars are fun! They abound with neat little problems that seem like they should be easy but aren’t. And that kind of nags at you.

But sadly, in its most general form, parsing just isn’t that useful. Very few people need a parsing framework. If you’re making a language, you only need one parser for that language. And even then, parsing is usually the least of your worries.

Write a recursive-descent parser, or use a parser generator, whatever works. And then get on with the much larger problem of implementing the language. That’s the way most language implementations go anyway. At least, the ones that survive their authors’ attempts to build the perfect parsing framework. That is more or less the subject of Semantic Designs’ old essay Life After Parsing.

Constrained decoding is a different problem, obviously. But the same temptation remains. I wanted to solve the general problem for arbitrary CFGs. I wanted the pathological tokens and lexer edge cases and ambiguous grammars to work properly. And now they mostly do.

JSON schemas don’t really apply here. They’re ‘easy’, in that sense.

This is yak shaving in the Jargon File sense—several levels of apparently pointless work that eventually reaches the original problem—or, if you prefer, Hal trying to replace a light bulb.

Anyway, I’d hardly be the first person to make a yacc shaving pun. So I’m not going to.

I’ve spent the past few years shearing this particular yak, and I’m proud of the haircut. Even if most people just wanted a short back and sides.