语法约束Grammar (GBNF)

By now the model can chat (L20-L22). But many real scenarios want more than "talks fine" - they want strictly correct format: calling an API needs valid JSON, filling a form needs the required fields, extracting info needs a fixed structure. A model generates by probability and inevitably wanders off sometimes - this lesson's GBNF grammar constraint puts a "guardrail" on generation, making it impossible to produce format-invalid output.

Its idea is clever: not generate-then-check-and-retry-if-bad (slow and unreliable), but at each sampling step strike out every "token the grammar disallows right now", so the model can only move forward on the legal path. So however much the model wants to wander, it cannot step past the grammar's boundary - the result is always valid, right the first time.

Why a grammar is needed

First see where it sits in the sampling pipeline. L21 covered that sampling prunes and shapes a row of logits and finally picks one token. The grammar inserts a mask stage into this pipeline: before picking, slam to negative infinity the logit of every candidate "the grammar disallows right now", so their probability becomes 0, impossible to be chosen.

After a legal token is picked, one more step: advance the grammar state. The grammar is like a state machine; the token just allowed moved it one notch forward, and which tokens are legal next updates accordingly. Mask then advance, token by token, locks the whole output firmly onto the grammar's track.

There is a subtle bonus too: because illegal tokens are set to negative infinity with probability zeroed, the remaining legal tokens re-normalize their probabilities. That is, the constraint not only "forbids the illegal" but lets the model pick within the legal range by its own preference - keeping the rules while preserving the model's judgment as much as possible. Strong constraint and model intelligence do not conflict here.

Feel its value from another angle. Without a grammar constraint, to get JSON out of the model you can only beg in the prompt "please return only valid JSON, no extra text" and pray it obeys - a large model mostly does, but occasionally gilds the lily with an explanation, drops a quote, or writes a number as words. This "mostly right, occasionally derailed" is precisely the most lethal in production, because you must write a pile of error-handling for that 1% derailment.

You might worry: with such a rigid constraint, does it "frame the model into stupidity"? No. A grammar dictates only structure (what can go where), not content (the actual values). At a legal position, the model still fills by its own understanding - a username where a username goes, a sensible number where an age goes. You fix the structure, the model's intelligence still decides the content, each to its job.

What GBNF is

# simplified from grammars/json.gbnf
root   ::= object
object ::= "{" ws ( string ":" ws value )? "}"
value  ::= object | string | number | "true" | "false"
string ::= "\"" [^"]* "\""

So how is "the grammar" itself written? In GBNF (GGML BNF), a BNF-like grammar description. Its core is rules: ::= defines "what a name can expand into", | means "one of several", [...] describes a class of characters, plus repetition, grouping and other notations.

The snippet above (simplified from the repo's grammars/json.gbnf) describes a minimal JSON: the entry is root, expanding into an object; an object is key-value pairs inside braces; a value can be an object, string, number or literal. Rules can be recursive (an object can nest a value, a value can be an object), so a handful of rules describe infinitely nested structures.

This table lists GBNF's most common notations. Combined, they can describe almost any "structured" output format: JSON, code in a particular syntax, fixed-template answers... The repo's grammars/ directory ships ready examples like JSON and chess moves, to use directly or adapt.

BNF as a notation is in fact long-standing, a classic tool for describing programming-language grammars; GBNF is a lightweight dialect of it, trimmed and tailored for "constraining generation". If you have seen a programming language's grammar definition, you will take to these ::= rules at first sight; if not, no matter - just treat it as "a set of blocks describing what a legal string looks like".

There is a practical knack to writing GBNF: top-down, decompose layer by layer. First think out the outermost structure (say "an object"), written as root; then write a rule for each part it depends on (key, value, whitespace); use | for "one of several", */+ for "repeat some times". Decompose down to the bottom character classes and a grammar is done. The ready examples in the repo are the best templates.

How the grammar constrains sampling

# pseudocode: mask + advance
# before sampling: mask out illegal candidates (llama_grammar_apply_impl)
for cand in cur_p:
    if not grammar_allows(stacks, cand.id):
        cand.logit = -INFINITY        # illegal -> can never be chosen
# after a token is chosen: advance the grammar state (llama_grammar_accept_impl)
grammar.accept(chosen_token)          # step forward along the rule stacks

Turning a GBNF grammar into "a mask at sampling time" relies on two internal functions: llama_grammar_apply_impl (mask) and llama_grammar_accept_impl (advance).

The apply step: holding the grammar's current state (a set of rule stacks, the stacks field, recording "where the expansion is now, what is legal next"), it checks each candidate token - keep those that fit, set those that do not to negative infinity. EOG (the terminator) is also masked while the grammar is not yet complete, lest the model quit halfway.

The accept step: once sampling actually picks a token, feed it back to the grammar so the rule stacks advance to a new state. The next apply then recomputes the legal set from this new state. The two alternate, like walking along the grammar's track, each step stepping only on a legal sleeper.

It is worth pausing here to savor the "state machine" metaphor. Once a grammar is loaded, what the runtime maintains is not "the whole text" but "where in the grammar it is now, which characters are allowed next". Each accepted token nudges this position forward; it is like a cursor moving over the grammar graph, and where the cursor sits decides the legal set for the next step.

Walk the smallest example, generating {"a":1}, step by step: at each step the grammar lets through only the legal next character, slams every other candidate to -inf, then advances the state machine - locking the output onto the legal track character by character.

One might ask: scanning tens of thousands of candidates each step to judge legality, is that not slow? The implementation does plenty of optimization - precompiling the grammar into efficient structures, quickly filtering candidates by the rule stacks, caching intermediate results, and so on. In most cases this cost is nearly negligible against the model's one forward pass (L17). So use grammar constraints freely; the reliability they buy far outweighs the small price.

A concrete grounded example: many "let the large model be a backend" applications rely on grammar constraints to guarantee it returns JSON a program can consume directly. Define the grammar for the return structure, attach the grammar sampler, and the model end becomes a reliable component that "always outputs a legal structure". Without it, you must stuff a layer of parse, correct, and retry glue between the model and the program; with it, that glue layer can largely be dropped. This is the concrete engineering value a constraint brings.

Element types and being a sampler

A grammar is compiled at load time into a string of low-level elements, whose types are defined by enum llama_gretype. Every ::= rule you write is ultimately translated into such a string of elements for the runtime to match efficiently.

These types are GBNF notation's "machine code": CHAR is a literal character, CHAR_RNG_UPPER pairs up to express a range (like a-z), CHAR_NOT is a negated class, RULE_REF is "reference another rule", ALT is an alternation separator, END closes. Lowering the human-written grammar to this level lets the runtime quickly decide "is the next character legal".

But it usually does not mix into the main sampler chain; it is a separate object applied before or after the chain per a grammar_first flag. This is because constraint differs in nature from shaping ops like "tune temperature / prune candidates", needing flexible ordering.

Why compile the human-written grammar into this string of low-level elements first, rather than matching the raw text directly? Because the runtime judges legality once per generated token and must be fast. Pre-splitting the grammar into tidy elements like CHAR/RULE_REF lets the runtime advance and match in a simple, efficient way, without re-parsing the raw grammar text. This is the classic "spend a bit at compile time, save the bulk at run time" trade-off.

Savor again the elegance of the grammar "being a sampler". L21 designed sampling as a string of pluggable small transforms; at the time you may not have foreseen that "grammar constraint", something that sounds utterly different, could slot unchanged into the same apply/accept interface. That is the value of a good interface: the extension point it reserves can hold new tricks never imagined at design time.

Finally, put this lesson back into the whole picture: from L20's vocab, L21's sampling, L22's chat templates, to this lesson's grammar constraint, you have now gathered the full toolkit for "controlling the model's output" - controlling how to tokenize, how to pick words, how to organize the conversation, how to constrain the structure. Next lesson L24 covers LoRA, adding even "how to fine-tune the model's behavior". Only the last piece of Part 4's puzzle remains.