Life after ~~parsing~~ grammar constrained generation

I have spent the past few years working on GLRMask, a grammar-constrained decoding library.

The technical result is described in Constrained decoding with weighted automata. This article is about why I kept building it.

Why grammar constraints seemed useful

Models used to be bad at tool calls. Not just bad at choosing the right tool. Bad at producing the call at all.

Ask for JSON and you might get bare JSON, fenced JSON, an explanation before the JSON, or several JSON blocks with commentary between them. Ask for exactly YES or NO and get The answer is YES.

Tool schemas gave grammar constraints an obvious job. Turn a JSON Schema into a grammar. Block any next token that would make the output syntactically invalid. The model could still ask for the weather on the Sun, but it could not forget the closing brace.

This only solves syntax. It does not repair a bad decision already sampled.

Suppose a tool call allows a comment:

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

Now suppose the model forgets the escapes around Perth. The quote after The user said ends the string. The mistake becomes visible only when the model tries to continue. The decoder cannot go back and add an escape. The grammar may force this instead:

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

The result parses. It makes less sense.

Grammar constraints can also change the model’s distribution and force awkward continuations. This is not a complete correctness mechanism. It is one guardrail.

Scratch work

Before thinking models, I also used grammar constraints to keep <answer> unavailable until a model had produced 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 reached the minimum length, </thinking> and <answer> were illegal.

The model could still reason badly. This was also before prompt caching, so repeatedly feeding old reasoning back into the model was expensive.

That use now feels historical. Tool calls are the clearer application. Better models may also make syntax constraints less important over time. Small and on-device models may keep them useful longer.

The project changed underneath me

The repository began in June 2024 as grammars2024. It later became Sep1, then GLRMask.

When I started, tool-using agents were not yet the obvious centre of LLM application design. It was less clear that JSON Schema would account for almost all practical grammar-constrained generation.

Still, it was predictable that most users would want a narrow, reliable structured-output system rather than a general parser framework.

I built the general system anyway.

I wanted arbitrary context-free grammars. I wanted ambiguous grammars. I wanted regex terminals, longest-match lexing, model tokens that crossed lexeme boundaries, and pathological tokens that hid long parser executions. I wanted the slow masks to stay small and predictable.

Most JSON schemas do not need all of this. Their delimiters keep lexer and parser work simple. An online system such as llguidance is usually the better cold-start trade for a schema used once.

GLRMask pays much more before generation. That cost makes sense when constraints are reused, tail latency matters, or grammar and lexer behaviour cannot be simplified without changing the problem.

The compiler ate the project

The runtime idea is small. Read the current parser stack through a weighted automaton. Intersect token sets. Return the mask.

Building that automaton became most of the project.

The compiler needed grammar normalization, lexer-state and token equivalence, vocabulary partitioning, terminal interchangeability, stack-effect cancellation, pruning, determinisation, minimisation, range-based weights, interning, and many specialised builders.

The persistent graph-structured stack became a separate library, weighted-gss.

This is the familiar failure mode of parser projects. The infrastructure becomes more interesting than the thing it was meant to support.

Life after parsing

Semantic Designs’ old essay Life After Parsing tells language implementers to get past the parser and implement the language.

Parsing is usually not the hard part of a language. Use recursive descent. Use a parser generator. Use whatever works. Then build the type system, runtime, tools, libraries, debugger, package manager, documentation, and everything else people actually need.

Very few people need a general parsing framework. A language implementation usually needs one parser for one language.

Constrained decoding is different, but the temptation is the same. Instead of building the perfect parser before implementing the language, you build the perfect constraint engine before shipping the model feature.

Grammars make this easy to do. They contain many problems that look small and turn out not to be small. Lexer boundaries. Ambiguity. Empty productions. Reduction cycles. Incremental updates. Shared stacks. Every local fix exposes another general case.

That kind of problem nags at me.

GLRMask is probably overkill for most users. I am still proud of it. I think the construction is novel. The compiled runtime is fast and clean. The pathological cases mostly work.

This is yak shaving in the original sense: several levels of apparently unrelated work that eventually reaches the first task. Or Hal trying to replace a light bulb.

I would hardly be the first person to make a yacc shaving pun. So I will not.

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