Constrained Decoding and Structured Output

A program that calls a language model usually needs the answer in a fixed shape, for example a JSON object with a file name and a line number. A model that is asked for JSON usually writes JSON, and sometimes writes a sentence before it, a Markdown fence around it, a trailing comma, or half an object because it ran out of tokens. A program cannot guess which of these it will get, so it has to defend against all of them.

Constrained decoding removes the "sometimes". The model picks its answer one token at a time (a token is a small piece of text). Before each pick, the engine looks at the text written so far, works out which tokens could still lead to valid output, and sets the probability of every other token to zero. The model can then only choose among tokens that keep the text valid, so the finished text always follows the format.

This lesson builds the mechanism in Java, starting from a block over 8 tokens and growing to a recognizer for JSON. It measures what the check costs, runs it in llama.cpp with the course's random-weight model, reads how vLLM implements it, and lists the pitfalls. It ends with Project 14: a constrained sampler, and an extractor that turns free text into Java records through llama-server. Afterwards you can force any model to produce a given format, choose between the available tools, and know where the guarantee ends.

The sampling lessons built the chain that turns the model's scores into one chosen token. Constrained decoding adds one more filter to that chain. llama-server: Endpoints, Slots, and Prompt Cache showed the request fields. This lesson explains what happens behind them.

Example 1: free-text JSON that fails to parse

Before adding any machinery, look at what goes wrong without it. The program takes seven answers that models commonly give to the prompt "Reply with JSON: {file: string, line: integer}" and feeds each to Jackson's JSON parser (Jackson is the most common JSON library in Java). Look at which answers parse and what kind of error each failure gives.

import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.LinkedHashMap;
import java.util.Map;

public class FreeTextJson {
    public static void main(String[] args) {
        // Typical answers to "Reply with JSON: {\"file\": string, \"line\": integer}".
        Map<String, String> answers = new LinkedHashMap<>();
        answers.put("clean", "{\"file\": \"Main.java\", \"line\": 42}");
        answers.put("markdown fence", "```json\n{\"file\": \"Main.java\", \"line\": 42}\n```");
        answers.put("prose first", "Sure! Here is the JSON: {\"file\": \"Main.java\", \"line\": 42}");
        answers.put("trailing comma", "{\"file\": \"Main.java\", \"line\": 42,}");
        answers.put("single quotes", "{'file': 'Main.java', 'line': 42}");
        answers.put("truncated", "{\"file\": \"Main.java\", \"li");
        answers.put("wrong type", "{\"file\": \"Main.java\", \"line\": \"forty-two\"}");

        ObjectMapper mapper = new ObjectMapper();
        for (var e : answers.entrySet()) {
            String verdict;
            try {
                var node = mapper.readTree(e.getValue());
                verdict = node.path("line").isInt() ? "ok, line=" + node.get("line").asInt()
                        : "parsed, but line is " + node.path("line").getNodeType();
            } catch (Exception ex) {
                verdict = "FAIL: " + ex.getClass().getSimpleName();
            }
            System.out.printf("%-15s %s%n", e.getKey(), verdict);
        }
    }
}

clean           ok, line=42
markdown fence  FAIL: JsonParseException
prose first     FAIL: JsonParseException
trailing comma  FAIL: JsonParseException
single quotes   FAIL: JsonParseException
truncated       FAIL: JsonEOFException
wrong type      parsed, but line is STRING

Only the first answer parses into what the program needs. The others fail for different reasons:

• markdown fence: chat models are trained on a lot of Markdown, so they often wrap code in a fence. The parser stops at the first backtick.
• prose first: a polite sentence before the object. A program can search for the first {, but then it must also find where the object ends.
• trailing comma and single quotes: valid in JavaScript or Python literals, but invalid in JSON. Jackson can be configured to accept some of these, which moves the problem and does not solve it.
• truncated: generation stopped at max_tokens, the limit on how many tokens the model may write. JsonEOFException means the input ended in the middle of a value.
• wrong type: the text parses, but line is a string and the program wanted an integer. The syntax is fine and the schema is not. A schema is a description of the allowed fields and their types.

The usual remedy is to retry until the output parses. Each retry costs a full generation, and there is no bound on the number of attempts. Constrained decoding makes the first five failures impossible, and with a schema it makes the sixth impossible as well. Truncation remains possible, and Example 12 covers it.

Example 2: logit masking on a toy vocabulary

This example shows what "forbidding a token" means in numbers. When a model decides the next token, it first computes a score for every token in its vocabulary (the list of all tokens it knows). These raw scores are called logits. A function called softmax turns the scores into probabilities that add up to 1: higher score, higher probability. The engine then picks a token according to those probabilities.

A logit mask sets the logit of every forbidden token to negative infinity. Softmax computes exp(logit), and exp(-infinity) is exactly 0, so a forbidden token gets probability 0 and the remaining probabilities are scaled up to add to 1 again. In the program, the vocabulary has 8 tokens, and a JSON object must start with { or { (a brace with a leading space). Look at the model's probabilities before and after the mask.

import java.util.Locale;
import java.util.Set;

public class LogitMask {
    static double[] softmax(double[] logits) {
        double max = Double.NEGATIVE_INFINITY, sum = 0;
        for (double l : logits) max = Math.max(max, l);
        double[] p = new double[logits.length];
        for (int i = 0; i < p.length; i++) { p[i] = Math.exp(logits[i] - max); sum += p[i]; }
        for (int i = 0; i < p.length; i++) p[i] /= sum;
        return p;
    }

    public static void main(String[] args) {
        String[] vocab = {"Sure", "{", " {", "\"", "Here", "[", "```", "\n"};
        double[] logits = {3.0, 1.5, 0.5, -1.0, 2.5, 0.0, 2.0, 1.0};
        Set<String> allowed = Set.of("{", " {");                  // a JSON object must start here

        double[] masked = logits.clone();
        for (int i = 0; i < vocab.length; i++)
            if (!allowed.contains(vocab[i])) masked[i] = Double.NEGATIVE_INFINITY;

        double[] before = softmax(logits), after = softmax(masked);
        double keptMass = 0;
        System.out.println("token    logit   p(before)  masked logit  p(after)");
        for (int i = 0; i < vocab.length; i++) {
            if (allowed.contains(vocab[i])) keptMass += before[i];
            System.out.printf(Locale.ROOT, "%-7s  %5.1f   %8.4f  %12s  %8.4f%n", "'" + vocab[i].replace("\n", "\\n") + "'",
                    logits[i], before[i], Double.isInfinite(masked[i]) ? "-inf" : String.format(Locale.ROOT, "%.1f", masked[i]), after[i]);
        }
        System.out.printf(Locale.ROOT, "probability mass the model gave to allowed tokens: %.4f%n", keptMass);
        System.out.printf(Locale.ROOT, "p('{') after = %.4f / %.4f = %.4f%n", before[1], keptMass, before[1] / keptMass);
    }
}

token    logit   p(before)  masked logit  p(after)
'Sure'     3.0     0.4027          -inf    0.0000
'{'        1.5     0.0899           1.5    0.7311
' {'       0.5     0.0331           0.5    0.2689
'"'       -1.0     0.0074          -inf    0.0000
'Here'     2.5     0.2443          -inf    0.0000
'['        0.0     0.0201          -inf    0.0000
'```'      2.0     0.1482          -inf    0.0000
'\n'       1.0     0.0545          -inf    0.0000
probability mass the model gave to allowed tokens: 0.1229
p('{') after = 0.0899 / 0.1229 = 0.7311

Before masking, the model prefers Sure (0.4027), Here (0.2443), and a Markdown fence (0.1482). It wants to start with prose. The two allowed tokens together hold only 0.1229 of the probability.

After masking, six logits are -inf, and exp(-inf) is 0, so those tokens have probability 0.0000 and cannot be picked at any temperature (the setting that makes sampling more or less random). The two survivors keep their relative weights. { had 0.0899 and { had 0.0331, a ratio of 2.7 to 1. After scaling they have 0.7311 and 0.2689, which is the same ratio. The last output line shows the scaling directly: 0.0899 / 0.1229 = 0.7311. Masking does not change the model's preferences among the allowed tokens. It only removes the rest.

The kept mass, 0.1229, measures how much the constraint disagrees with the model at this step. A small kept mass at one step is normal here, because the model wanted a preamble. A small kept mass at many steps means the grammar forces text that the model considers unlikely, which Example 13 shows can lower the quality of the output.

Example 3: a finite automaton constraining sampling

The mask in Example 2 was written by hand. An engine needs a rule that computes the allowed tokens at every step. For simple formats such as a fixed list of words, a finite automaton does this. It is a machine with a finite set of states and a rule for moving from one state to another on each character. A format that such a machine can check is called a regular language. Fixed strings, enums, and patterns without nesting are all regular.

The program constrains the output to one of red, green, grey, or blue. The state is the text written so far, and it is valid as long as it is a prefix of one of the four words. A token is allowed if adding its characters keeps the state valid. The end token <eos> is allowed only when the text is already a complete word. The "model" is random scores from a seeded generator, because the point is the mask, not the model. The program runs three times and prints, at every step, which tokens were allowed and which one was picked.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class AutomatonSampling {
    static final List<String> WORDS = List.of("red", "green", "grey", "blue");
    static final String[] VOCAB = {"r", "e", "d", "re", "red", "g", "gr", "green", "ee", "en", "ey",
                                   "n", "y", "b", "l", "u", "bl", "ue", "yellow", "<eos>"};

    // The automaton state is the text so far; it is valid while it is a prefix of an allowed word.
    static boolean livePrefix(String s) { return WORDS.stream().anyMatch(w -> w.startsWith(s)); }
    static boolean accepting(String s) { return WORDS.contains(s); }

    static boolean allowed(String state, String token) {
        if (token.equals("<eos>")) return accepting(state);
        return livePrefix(state + token);
    }

    public static void main(String[] args) {
        Random rnd = new Random(3);
        for (int run = 1; run <= 3; run++) {
            String state = "";
            StringBuilder trace = new StringBuilder();
            while (true) {
                double[] logits = new double[VOCAB.length];
                for (int i = 0; i < logits.length; i++) logits[i] = rnd.nextGaussian() * 2;  // a "model"
                List<Integer> ok = new ArrayList<>();
                for (int i = 0; i < VOCAB.length; i++) if (allowed(state, VOCAB[i])) ok.add(i);
                double max = Double.NEGATIVE_INFINITY;              // sample from the masked softmax
                for (int i : ok) max = Math.max(max, logits[i]);
                double sum = 0;
                for (int i : ok) sum += Math.exp(logits[i] - max);
                double u = rnd.nextDouble() * sum, cum = 0;
                int pick = ok.get(ok.size() - 1);
                for (int i : ok) { cum += Math.exp(logits[i] - max); if (u < cum) { pick = i; break; } }
                List<String> okText = ok.stream().map(i -> VOCAB[i]).toList();
                trace.append(String.format("  state %-8s allowed %-34s -> %s%n", "'" + state + "'", okText, VOCAB[pick]));
                if (VOCAB[pick].equals("<eos>")) break;
                state += VOCAB[pick];
            }
            System.out.printf("run %d: '%s'%n%s", run, state, trace);
        }
    }
}

run 1: 'red'
  state ''       allowed [r, re, red, g, gr, green, b, bl]  -> re
  state 're'     allowed [d]                                -> d
  state 'red'    allowed [<eos>]                            -> <eos>
run 2: 'grey'
  state ''       allowed [r, re, red, g, gr, green, b, bl]  -> gr
  state 'gr'     allowed [e, ee, ey]                        -> e
  state 'gre'    allowed [e, en, y]                         -> y
  state 'grey'   allowed [<eos>]                            -> <eos>
run 3: 'green'
  state ''       allowed [r, re, red, g, gr, green, b, bl]  -> gr
  state 'gr'     allowed [e, ee, ey]                        -> ee
  state 'gree'   allowed [n]                                -> n
  state 'green'  allowed [<eos>]                            -> <eos>

In each run, the first step allows 8 of the 20 tokens: the ones that start an allowed word (r, re, red, g, gr, green, b, bl). The tokens yellow, ee, and <eos> are masked because no allowed word starts with them.

Run 1 picked re. From state re, the only token that keeps a valid prefix is d, because red is the only word that starts with re. In state red, the only allowed token is <eos>, so generation stops. Run 2 went gr, e, y. In state gr, the allowed tokens were e, ee, and ey, which all lead to green or grey. Run 3 reached green through gr, ee, n. The same word can be spelled by different token sequences, and the automaton accepts all of them because it checks characters, not tokens.

The vocabulary includes single letters for a reason. A first draft of this program had no e token, and a run that picked r reached a state where every token was masked. This is called a dead end, because the sampler has no legal move. Real vocabularies contain every single byte as a token, so a grammar over characters always has at least one way forward. Project 14 (Example 14) meets the same problem with a missing space token.

Example 4: a pushdown recognizer for a JSON subset

Real formats such as JSON nest: every { needs a matching }, and objects can sit inside arrays inside objects. A finite automaton cannot track unbounded nesting, because it has no memory of how many brackets are still open. A pushdown recognizer is an automaton with a stack, which is a list where you add and remove items only at one end. It pushes a marker on { or [ and removes it on } or ]. The marker on top of the stack always says which bracket must close next.

For the text {"a": [1, 2 the stack grows like this:

text so far     stack after reading it (right end = top)
{               [object]
{"a": [         [object, array]
{"a": [1, 2     [object, array]    (still open, so a "]" and then a "}" must follow)

The program recognizes objects, arrays, strings, integers, and true, false, null, one character at a time. For each test text it reports one of three answers: complete, a valid prefix (so far nothing is wrong, and more characters could finish it), or invalid at a given character.

import java.util.ArrayDeque;
import java.util.Deque;

public class JsonPrefixCheck {
    // A pushdown recognizer for a JSON subset: objects, arrays, strings, integers, true/false/null.
    static final class JsonPrefix {
        enum S { VALUE, VALUE_OR_CLOSE, KEY_OR_CLOSE, KEY, COLON, STRING, ESCAPE, NUMBER, LITERAL, AFTER_VALUE, DONE }
        final Deque<Character> stack = new ArrayDeque<>();      // 'O' = inside object, 'A' = inside array
        S state = S.VALUE;
        boolean stringIsKey, numberHasDigit;
        String literalRest = "";

        JsonPrefix copy() {
            JsonPrefix c = new JsonPrefix();
            c.stack.addAll(stack);
            c.state = state; c.stringIsKey = stringIsKey; c.numberHasDigit = numberHasDigit; c.literalRest = literalRest;
            return c;
        }

        private void endValue() { state = stack.isEmpty() ? S.DONE : S.AFTER_VALUE; }

        boolean feed(char ch) {
            boolean ws = ch == ' ' || ch == '\n';
            switch (state) {
                case VALUE, VALUE_OR_CLOSE -> {
                    if (ws) return true;
                    if (ch == ']' && state == S.VALUE_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    if (ch == '{') { stack.push('O'); state = S.KEY_OR_CLOSE; return true; }
                    if (ch == '[') { stack.push('A'); state = S.VALUE_OR_CLOSE; return true; }
                    if (ch == '"') { state = S.STRING; stringIsKey = false; return true; }
                    if (ch == '-' || Character.isDigit(ch)) { state = S.NUMBER; numberHasDigit = ch != '-'; return true; }
                    for (String lit : new String[] {"true", "false", "null"})
                        if (lit.charAt(0) == ch) { state = S.LITERAL; literalRest = lit.substring(1); return true; }
                    return false;
                }
                case KEY_OR_CLOSE, KEY -> {
                    if (ws) return true;
                    if (ch == '"') { state = S.STRING; stringIsKey = true; return true; }
                    if (ch == '}' && state == S.KEY_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    return false;
                }
                case COLON -> {
                    if (ws) return true;
                    if (ch == ':') { state = S.VALUE; return true; }
                    return false;
                }
                case STRING -> {
                    if (ch == '\\') { state = S.ESCAPE; return true; }
                    if (ch == '"') { if (stringIsKey) state = S.COLON; else endValue(); return true; }
                    return ch >= 0x20;
                }
                case ESCAPE -> { state = S.STRING; return "\"\\/bfnrt".indexOf(ch) >= 0; }
                case NUMBER -> {
                    if (Character.isDigit(ch)) { numberHasDigit = true; return true; }
                    if (!numberHasDigit) return false;
                    endValue();
                    return feed(ch);                               // the character after a number
                }
                case LITERAL -> {
                    if (literalRest.isEmpty() || literalRest.charAt(0) != ch) return false;
                    literalRest = literalRest.substring(1);
                    if (literalRest.isEmpty()) endValue();
                    return true;
                }
                case AFTER_VALUE -> {
                    if (ws) return true;
                    if (ch == ',') { state = stack.peek() == 'O' ? S.KEY : S.VALUE; return true; }
                    if (ch == '}' && stack.peek() == 'O') { stack.pop(); endValue(); return true; }
                    if (ch == ']' && stack.peek() == 'A') { stack.pop(); endValue(); return true; }
                    return false;
                }
                default -> { return ws; }                         // DONE: only trailing whitespace
            }
        }

        boolean complete() { return state == S.DONE || (state == S.NUMBER && numberHasDigit && stack.isEmpty()); }
    }

    static String check(String text) {
        JsonPrefix p = new JsonPrefix();
        for (int i = 0; i < text.length(); i++)
            if (!p.feed(text.charAt(i))) return "INVALID at index " + i + " ('" + text.charAt(i) + "')";
        return p.complete() ? "COMPLETE" : "VALID PREFIX, stack depth " + p.stack.size() + ", state " + p.state;
    }

    public static void main(String[] args) {
        String[] inputs = {
            "{\"a\": [1, 2], \"b\": \"x\"}", "{\"a\": [1, 2", "[tru", "[true]", "\"unterminated",
            "{\"a\" 1}", "{\"a\": 1,}", "{\"a\": -}", "{} extra", "[[[[[[1]]]]]]"};
        for (String s : inputs) System.out.printf("%-26s %s%n", s, check(s));
    }
}

{"a": [1, 2], "b": "x"}    COMPLETE
{"a": [1, 2                VALID PREFIX, stack depth 2, state NUMBER
[tru                       VALID PREFIX, stack depth 1, state LITERAL
[true]                     COMPLETE
"unterminated              VALID PREFIX, stack depth 0, state STRING
{"a" 1}                    INVALID at index 5 ('1')
{"a": 1,}                  INVALID at index 8 ('}')
{"a": -}                   INVALID at index 7 ('}')
{} extra                   INVALID at index 3 ('e')
[[[[[[1]]]]]]              COMPLETE

The three answers mean different things to a sampler:

• COMPLETE: the text is one full JSON value. {"a": [1, 2], "b": "x"} and [true] end with an empty stack. [[[[[[1]]]]]] shows that the depth is limited only by the stack, which is the part an automaton cannot do.
• VALID PREFIX: more characters can still make the text valid. {"a": [1, 2 has a stack depth of 2 (one object and one array) and is in state NUMBER, since another digit may follow. [tru is in the middle of the literal true. "unterminated is inside a string at depth 0.
• INVALID at index i: no continuation can fix the text. {"a" 1} fails at index 5 because a key must be followed by :. {"a": 1,} fails at the } after a comma, because a comma inside an object promises another key. {"a": -} fails because - must be followed by a digit. {} extra fails at e, because the top-level value is complete and only whitespace may follow.

A constrained sampler needs only the second and third answers during generation. A token is allowed if the text stays a valid prefix (or becomes complete), and <eos> is allowed only when the text is complete. The copy() method lets the sampler test a token on a copy of the recognizer without changing the real state. The next example uses it.

Example 5: token boundaries, one token spanning several grammar symbols

A grammar like the one in Example 4 is written over characters, but the model picks whole tokens, and one token can hold several characters. A token such as "]} closes a string, an array, and an object in one step. The sampler therefore feeds every character of a candidate token through the recognizer, one after another, and allows the token only if all of the characters pass.

The program repeats the recognizer from Example 4 and tests eleven tokens after a prefix that ends inside a string. For each token, it prints whether it is allowed, and if it is rejected, at which of its characters.

import java.util.ArrayDeque;
import java.util.Deque;

public class TokenBoundaries {
    // A pushdown recognizer for a JSON subset: objects, arrays, strings, integers, true/false/null.
    static final class JsonPrefix {
        enum S { VALUE, VALUE_OR_CLOSE, KEY_OR_CLOSE, KEY, COLON, STRING, ESCAPE, NUMBER, LITERAL, AFTER_VALUE, DONE }
        final Deque<Character> stack = new ArrayDeque<>();      // 'O' = inside object, 'A' = inside array
        S state = S.VALUE;
        boolean stringIsKey, numberHasDigit;
        String literalRest = "";

        JsonPrefix copy() {
            JsonPrefix c = new JsonPrefix();
            c.stack.addAll(stack);
            c.state = state; c.stringIsKey = stringIsKey; c.numberHasDigit = numberHasDigit; c.literalRest = literalRest;
            return c;
        }

        private void endValue() { state = stack.isEmpty() ? S.DONE : S.AFTER_VALUE; }

        boolean feed(char ch) {
            boolean ws = ch == ' ' || ch == '\n';
            switch (state) {
                case VALUE, VALUE_OR_CLOSE -> {
                    if (ws) return true;
                    if (ch == ']' && state == S.VALUE_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    if (ch == '{') { stack.push('O'); state = S.KEY_OR_CLOSE; return true; }
                    if (ch == '[') { stack.push('A'); state = S.VALUE_OR_CLOSE; return true; }
                    if (ch == '"') { state = S.STRING; stringIsKey = false; return true; }
                    if (ch == '-' || Character.isDigit(ch)) { state = S.NUMBER; numberHasDigit = ch != '-'; return true; }
                    for (String lit : new String[] {"true", "false", "null"})
                        if (lit.charAt(0) == ch) { state = S.LITERAL; literalRest = lit.substring(1); return true; }
                    return false;
                }
                case KEY_OR_CLOSE, KEY -> {
                    if (ws) return true;
                    if (ch == '"') { state = S.STRING; stringIsKey = true; return true; }
                    if (ch == '}' && state == S.KEY_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    return false;
                }
                case COLON -> {
                    if (ws) return true;
                    if (ch == ':') { state = S.VALUE; return true; }
                    return false;
                }
                case STRING -> {
                    if (ch == '\\') { state = S.ESCAPE; return true; }
                    if (ch == '"') { if (stringIsKey) state = S.COLON; else endValue(); return true; }
                    return ch >= 0x20;
                }
                case ESCAPE -> { state = S.STRING; return "\"\\/bfnrt".indexOf(ch) >= 0; }
                case NUMBER -> {
                    if (Character.isDigit(ch)) { numberHasDigit = true; return true; }
                    if (!numberHasDigit) return false;
                    endValue();
                    return feed(ch);                               // the character after a number
                }
                case LITERAL -> {
                    if (literalRest.isEmpty() || literalRest.charAt(0) != ch) return false;
                    literalRest = literalRest.substring(1);
                    if (literalRest.isEmpty()) endValue();
                    return true;
                }
                case AFTER_VALUE -> {
                    if (ws) return true;
                    if (ch == ',') { state = stack.peek() == 'O' ? S.KEY : S.VALUE; return true; }
                    if (ch == '}' && stack.peek() == 'O') { stack.pop(); endValue(); return true; }
                    if (ch == ']' && stack.peek() == 'A') { stack.pop(); endValue(); return true; }
                    return false;
                }
                default -> { return ws; }                         // DONE: only trailing whitespace
            }
        }

        boolean complete() { return state == S.DONE || (state == S.NUMBER && numberHasDigit && stack.isEmpty()); }
    }

    static String verdict(String prefix, String token) {
        JsonPrefix p = new JsonPrefix();
        for (char c : prefix.toCharArray()) p.feed(c);
        for (int i = 0; i < token.length(); i++)
            if (!p.feed(token.charAt(i))) return i == 0 ? "rejected at its first char" : "rejected at char " + i;
        return p.complete() ? "allowed, JSON complete" : "allowed, state " + p.state;
    }

    public static void main(String[] args) {
        String prefix = "{\"name\": \"Ada\", \"tags\": [\"x";       // ends inside a string
        System.out.println("prefix: " + prefix);
        String[] tokens = {"y", "\"", "\"]", "\"]}", "\", \"", "\"],", "\"]}\n", "\"]},", "\"}", "\n", "\\n"};
        for (String t : tokens)
            System.out.printf("%-8s %s%n", "'" + t.replace("\\", "\\\\").replace("\n", "\\n") + "'", verdict(prefix, t));
    }
}

prefix: {"name": "Ada", "tags": ["x
'y'      allowed, state STRING
'"'      allowed, state AFTER_VALUE
'"]'     allowed, state AFTER_VALUE
'"]}'    allowed, JSON complete
'", "'   allowed, state STRING
'"],'    allowed, state KEY
'"]}\n'  allowed, JSON complete
'"]},'   rejected at char 3
'"}'     rejected at char 1
'\n'     rejected at its first char
'\\n'    allowed, state STRING

The prefix {"name": "Ada", "tags": ["x is inside the string "x, which is inside an array, which is inside an object. Here is what each candidate token does:

• y continues the string, so the state stays STRING.
• " closes the string, so the recognizer is after a value inside the array (AFTER_VALUE).
• "] closes the string and the array. That is two grammar symbols in one token, and the state is again AFTER_VALUE, now inside the object.
• "]} closes all three, and the JSON is complete. After this token, <eos> becomes allowed.
• ", " closes the string, adds a comma, and opens the next string. That is four symbols, ending in STRING.
• "], closes the string and the array and promises another key, so the state is KEY.
• "]}\n is complete plus a trailing newline, which the recognizer allows after a complete value.
• "]}, is rejected at character 3, because after the top-level object closes, a comma has nothing to separate.
• "} is rejected at character 1, because the innermost open bracket is [, so } cannot close it. The stack is what catches this.
• A raw newline is rejected at its first character, because JSON strings cannot contain control characters. The two-character token \n (a backslash followed by the letter n) is allowed, because it is an escape sequence.

The rejection position matters for speed. A token that fails at its first character costs one step to reject, and many tokens share their first characters. The next example uses that observation.

Example 6: mask cost per step for a large vocabulary

The mask must be computed before every token, and real vocabularies are large. The naive method replays every vocabulary token through a copy of the recognizer at every step. The program tests this on a vocabulary of 20,000 distinct tokens (all 49 single characters plus seeded random strings). It stops after {"name": "Ada", "age": and computes the mask twice.

1. Naively: try every token from the start.
2. With a trie, a prefix tree in which tokens that share a prefix share a path. When a prefix is rejected, the walk skips the whole subtree below it at once. If no token may start with a, then no token starting with a needs to be looked at.

The program counts how many characters each method feeds to the recognizer. It also computes the size of a mask for a real vocabulary.

import java.util.ArrayDeque;
import java.util.LinkedHashSet;
import java.util.Deque;
import java.util.Set;
import java.util.Locale;
import java.util.Random;
import java.util.TreeMap;

public class MaskCost {
    // A pushdown recognizer for a JSON subset: objects, arrays, strings, integers, true/false/null.
    static final class JsonPrefix {
        enum S { VALUE, VALUE_OR_CLOSE, KEY_OR_CLOSE, KEY, COLON, STRING, ESCAPE, NUMBER, LITERAL, AFTER_VALUE, DONE }
        final Deque<Character> stack = new ArrayDeque<>();      // 'O' = inside object, 'A' = inside array
        S state = S.VALUE;
        boolean stringIsKey, numberHasDigit;
        String literalRest = "";

        JsonPrefix copy() {
            JsonPrefix c = new JsonPrefix();
            c.stack.addAll(stack);
            c.state = state; c.stringIsKey = stringIsKey; c.numberHasDigit = numberHasDigit; c.literalRest = literalRest;
            return c;
        }

        private void endValue() { state = stack.isEmpty() ? S.DONE : S.AFTER_VALUE; }

        boolean feed(char ch) {
            boolean ws = ch == ' ' || ch == '\n';
            switch (state) {
                case VALUE, VALUE_OR_CLOSE -> {
                    if (ws) return true;
                    if (ch == ']' && state == S.VALUE_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    if (ch == '{') { stack.push('O'); state = S.KEY_OR_CLOSE; return true; }
                    if (ch == '[') { stack.push('A'); state = S.VALUE_OR_CLOSE; return true; }
                    if (ch == '"') { state = S.STRING; stringIsKey = false; return true; }
                    if (ch == '-' || Character.isDigit(ch)) { state = S.NUMBER; numberHasDigit = ch != '-'; return true; }
                    for (String lit : new String[] {"true", "false", "null"})
                        if (lit.charAt(0) == ch) { state = S.LITERAL; literalRest = lit.substring(1); return true; }
                    return false;
                }
                case KEY_OR_CLOSE, KEY -> {
                    if (ws) return true;
                    if (ch == '"') { state = S.STRING; stringIsKey = true; return true; }
                    if (ch == '}' && state == S.KEY_OR_CLOSE) { stack.pop(); endValue(); return true; }
                    return false;
                }
                case COLON -> {
                    if (ws) return true;
                    if (ch == ':') { state = S.VALUE; return true; }
                    return false;
                }
                case STRING -> {
                    if (ch == '\\') { state = S.ESCAPE; return true; }
                    if (ch == '"') { if (stringIsKey) state = S.COLON; else endValue(); return true; }
                    return ch >= 0x20;
                }
                case ESCAPE -> { state = S.STRING; return "\"\\/bfnrt".indexOf(ch) >= 0; }
                case NUMBER -> {
                    if (Character.isDigit(ch)) { numberHasDigit = true; return true; }
                    if (!numberHasDigit) return false;
                    endValue();
                    return feed(ch);                               // the character after a number
                }
                case LITERAL -> {
                    if (literalRest.isEmpty() || literalRest.charAt(0) != ch) return false;
                    literalRest = literalRest.substring(1);
                    if (literalRest.isEmpty()) endValue();
                    return true;
                }
                case AFTER_VALUE -> {
                    if (ws) return true;
                    if (ch == ',') { state = stack.peek() == 'O' ? S.KEY : S.VALUE; return true; }
                    if (ch == '}' && stack.peek() == 'O') { stack.pop(); endValue(); return true; }
                    if (ch == ']' && stack.peek() == 'A') { stack.pop(); endValue(); return true; }
                    return false;
                }
                default -> { return ws; }                         // DONE: only trailing whitespace
            }
        }

        boolean complete() { return state == S.DONE || (state == S.NUMBER && numberHasDigit && stack.isEmpty()); }
    }

    static final class Trie { final TreeMap<Character, Trie> kids = new TreeMap<>(); boolean isToken; }
    static long trieFeeds;

    static int walk(Trie node, JsonPrefix state) {               // counts allowed tokens below this node
        int allowed = node.isToken ? 1 : 0;
        for (var e : node.kids.entrySet()) {
            JsonPrefix next = state.copy();
            trieFeeds++;
            if (next.feed(e.getKey())) allowed += walk(e.getValue(), next);  // invalid prefix: skip subtree
        }
        return allowed;
    }

    public static void main(String[] args) {
        String alphabet = "abcdefghijklmnopqrstuvwxyz0123456789 \"{}[]:,-_.\n";
        Random rnd = new Random(11);
        Set<String> vocab = new LinkedHashSet<>();                // distinct tokens, insertion order
        for (char c : alphabet.toCharArray()) vocab.add(String.valueOf(c));
        while (vocab.size() < 20_000) {
            StringBuilder t = new StringBuilder();
            int len = 2 + rnd.nextInt(7);
            for (int i = 0; i < len; i++) t.append(alphabet.charAt(rnd.nextInt(alphabet.length())));
            vocab.add(t.toString());
        }
        JsonPrefix state = new JsonPrefix();
        for (char c : "{\"name\": \"Ada\", \"age\": ".toCharArray()) state.feed(c);

        long naiveFeeds = 0;
        int naiveAllowed = 0;
        for (String tok : vocab) {                                // naive: replay every token
            JsonPrefix p = state.copy();
            boolean ok = true;
            for (char c : tok.toCharArray()) { naiveFeeds++; if (!p.feed(c)) { ok = false; break; } }
            if (ok) naiveAllowed++;
        }
        Trie root = new Trie();
        for (String tok : vocab) {
            Trie n = root;
            for (char c : tok.toCharArray()) n = n.kids.computeIfAbsent(c, k -> new Trie());
            n.isToken = true;
        }
        int trieAllowed = walk(root, state);
        System.out.printf("vocabulary %d tokens, allowed after the prefix: naive %d, trie %d%n",
                vocab.size(), naiveAllowed, trieAllowed);
        System.out.printf("character steps: naive %d, trie %d%n", naiveFeeds, trieFeeds);

        int v = 151_936, tokensPerSecond = 50;
        System.out.printf(Locale.ROOT, "bitmask for %d tokens: %d int32 words = %d bytes per row%n",
                v, (v + 31) / 32, (v + 31) / 32 * 4);
        System.out.printf(Locale.ROOT, "naive checks per second at %d tokens/s: %,d tokens%n",
                tokensPerSecond, (long) v * tokensPerSecond);
    }
}

vocabulary 20000 tokens, allowed after the prefix: naive 656, trie 656
character steps: naive 31226, trie 4162
bitmask for 151936 tokens: 4748 int32 words = 18992 bytes per row
naive checks per second at 50 tokens/s: 7,596,800 tokens

Both methods find the same 656 allowed tokens. After "age": a value must start, so tokens that begin with a digit, -, ", {, [, t, f, n, a space, or a newline can pass, and only if their remaining characters also fit.

The naive method fed 31,226 characters through the recognizer. Every token was tried, and most were rejected at their first or second character. The trie walk fed 4,162 characters: when the character a fails at the root, the walk skips every token that starts with a without looking at them. That is 7.5 times fewer steps for this vocabulary and state.

The last two lines scale up. A real vocabulary such as Qwen2's has 151,936 tokens. Engines store the mask as a bitmask, one bit per token packed into 32-bit integers. The size is (151,936 + 31) / 32 = 4,748 words, which is 18,992 bytes per sequence per step. At 50 tokens per second, a naive mask checks 7,596,800 tokens per second for one sequence, which would cost more than the model's own forward pass on a CPU. Engines use three techniques to avoid that:

• Precomputation: llguidance and xgrammar split the grammar into a lexer (which groups characters into units such as numbers and strings) and a parser (which checks how the units fit together). They precompute which tokens each lexer state allows. llama.cpp's docs/llguidance.md reports an average of 50 μs of single-core CPU time per mask for a 128K-token Llama 3 vocabulary on the JSON Schema Bench, with p99 (the slowest 1 in 100) at 0.5 ms.
• Check the sample first: llama.cpp's common_sampler_sample (common/sampling.cpp) samples without the grammar, checks only the chosen token against the grammar, and builds the full mask only if that token is rejected. A model that already writes valid JSON pays for one token check per step. The source calls this "grammar-based rejection sampling".
• Overlap with the GPU: vLLM fills the bitmasks on CPU threads while the GPU runs the forward pass (vllm/v1/structured_output/__init__.py).

Example 7: GBNF syntax and the grammars shipped with llama.cpp

Engines accept a grammar as text, so the next step is to write one. GBNF (GGML BNF, described in grammars/README.md) is llama.cpp's grammar format. A grammar is a set of rules of the form name ::= sequence. A sequence is made of:

• Terminals: quoted strings such as "edit ", or character classes such as [a-z].
• | to separate alternatives.
• *, +, ?, {m}, and {m,n} to repeat the item before them (zero or more, one or more, optional, exactly m, between m and n).
• Rule names, which are lowercase words with dashes.

The rule named root is the start rule. The grammar below accepts one line of a coding agent's command language, such as edit src/app.java line 12. The command writes the grammar to a file and runs llama-completion with --grammar-file.

cat > cmd.gbnf <<'GBNF'
root ::= "edit " path " line " num "\n"
path ::= [a-z]{1,8} ("/" [a-z]{1,8}){0,2} ".java"
num  ::= [1-9] [0-9]{0,3}
GBNF
llama-completion -m tiny-random-qwen2vocab-f32.gguf --grammar-file cmd.gbnf -p "Command:" \
  -n 60 --temp 0 -t 2 -c 256 --no-warmup -no-cnv

The next block shows the real output from the pinned build with the random-weight model: the standard output, then two lines of the log.

Command:edit errmsg/loader/loaderyy.java line 8888
 [end of text]
I common_perf_print: prompt eval time =      13.64 ms /     2 tokens (    6.82 ms per token,   146.67 tokens per second)
I common_perf_print:        eval time =     232.74 ms /    18 runs   (   12.93 ms per token,    77.34 tokens per second)

The output after the prompt matches the grammar exactly: edit , a path of three lowercase segments (errmsg, loader, loaderyy, each 1 to 8 letters, the last exactly 8), .java, line, a number that starts with a nonzero digit and has at most 4 digits (8888), and a newline. After the newline the grammar is complete, so the only token left is end-of-generation, printed as [end of text]. The program stopped after 18 generated tokens, although -n allowed 60. The random model chose the letters, and the grammar chose the structure.

The bounds in the grammar are deliberate. A first version used [a-z]+ for each path segment. The random model kept choosing letters and never chose / or .java, so generation ended at the 60-token limit in the middle of a path. An unbounded repetition lets a weak model wander forever, and {1,8} forces the grammar forward. grammars/README.md also warns about the opposite construction: x? x? x? ... repeated N times can make sampling slow, and x{0,N} should be used instead.

The flag -no-cnv turns off conversation mode, which llama-completion enables automatically when the model has a chat template. Without it, the prompt would be wrapped in the template. The grammars/ directory at the pinned commit ships arithmetic.gbnf, c.gbnf, chess.gbnf, english.gbnf, japanese.gbnf, json.gbnf, json_arr.gbnf, and list.gbnf. The file json.gbnf accepts any JSON object, and its first lines are below.

root   ::= object
value  ::= object | array | string | number | ("true" | "false" | "null") ws

object ::=
  "{" ws (
            string ":" ws value
    ("," ws string ":" ws value)*
  )? "}" ws

The structure mirrors the recognizer of Example 4: object refers to value, which refers to object again. That recursion is what needs a stack. GBNF can also match special tokens directly, with <[1000]> by id or <think> by text, and negate them with !.

Example 8: JSON schema to grammar in llama.cpp, valid JSON from random weights

Writing a grammar by hand for every JSON shape is tedious, so llama.cpp can build the grammar from a JSON Schema. llama-server's native /completion endpoint accepts a json_schema field, converts it with common/json-schema-to-grammar.cpp, and returns the grammar it used in generation_settings.grammar. The request below asks for an object with a file name of at most 16 characters, a line number from 1 to 9999, and a severity that is one of two words. The test is whether the result stays valid even with a model that has random weights.

curl -s "127.0.0.1:$PORT/completion" -d '{"prompt": "Report the bug location:", "n_predict": 120, "temperature": 0,
  "json_schema": {"type": "object",
    "properties": {"file": {"type": "string", "maxLength": 16},
                   "line": {"type": "integer", "minimum": 1, "maximum": 9999},
                   "severity": {"enum": ["low", "high"]}},
    "required": ["file", "line", "severity"]}}'

The next block shows the real output with the random-weight model. It has the content, the stop type and token count, the content parsed by Python's json module, and then the grammar.

'{"file":"\'多少钱EnergyEST多少钱", "line":\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t5555, "severity"\n\t\t\t\t            \t \t\t:\n\t               \t\t\t\t"high"\n              \t \t\t \t}'
eos 51
{'file': "'多少钱EnergyEST多少钱", 'line': 5555, 'severity': 'high'}
char ::= [^"\\\x7F\x00-\x1F] | [\\] (["\\bfnrt] | "u" [0-9a-fA-F]{4})
file ::= "\"" char{0,16} "\""
file-kv ::= "\"file\"" space ":" space file
line ::= ([1-9] | ([1-8] [0-9] | [9] [0-9]) | ([1-8] [0-9]{2} | [9] ([0-8] [0-9] | [9] [0-9])) | ([1-8] [0-9]{3} | [9] ([0-8] [0-9]{2} | [9] ([0-8] [0-9] | [9] [0-9]))))
line-kv ::= "\"line\"" space ":" space line
root ::= "{" space file-kv "," space line-kv "," space severity-kv space "}"
severity ::= ("\"low\"" | "\"high\"")
severity-kv ::= "\"severity\"" space ":" space severity
space ::= | " " | "\n"{1,2} [ \t]{0,20}

The output parses, and every value satisfies the schema: file is 16 characters (an apostrophe, 3 Chinese characters, EnergyEST, and 3 more Chinese characters), line is 5555, and severity is high. Generation ended with eos after 51 tokens, because once the closing } was produced the grammar allowed nothing else. The random model contributed only choices among the allowed tokens.

The printed grammar shows how the converter works:

• root lists the three key-value rules in a fixed order, separated by ",". All three properties are required, so none is optional.
• file ::= "\"" char{0,16} "\"" turns maxLength: 16 into a bounded repetition of char. The rule char excludes quotes, backslashes, and control characters unless they are escaped.
• line is the most interesting rule. GBNF has no numeric comparison, so the converter writes the range 1 to 9999 as alternatives by digit count: one digit [1-9], two digits [1-8] [0-9] | [9] [0-9], and so on up to four digits. grammars/README.md lists minimum and maximum as supported only for "type": "integer".
• severity is an alternation of the two quoted strings.
• space allows nothing, one space, or one or two newlines followed by up to 20 spaces or tabs, between every pair of tokens. The random model used that freedom heavily, which Example 12 measures.

grammars/README.md lists the converter's limits at this commit:

• additionalProperties defaults to false (unlike the JSON Schema specification).
• Unsupported keywords are skipped silently.
• pattern must start with ^ and end with $.
• Remote $ref is not fetched.
• uniqueItems, contains, not, and if/then/else are not supported.

The note in the same file states that the schema is not added to the prompt. The model sees only what the prompt says, so a prompt should describe the expected fields.

Example 9: response_format with llama-server

Most client libraries talk to servers through the OpenAI-style /v1/chat/completions endpoint, so the same constraint has to work there. That endpoint reads a response_format field. In tools/server/server-common.cpp, {"type": "json_schema", "json_schema": {"schema": ...}} becomes a schema, {"type": "json_object"} becomes "any object" (or the optional schema it carries), and {"type": "text"} means no constraint. The example sends three requests: one with a schema, one with json_object, and one with an unknown type, to see how the server answers each.

curl -s "127.0.0.1:$PORT/v1/chat/completions" -d '{"messages": [{"role": "user", "content": "Which file has the bug?"}],
  "temperature": 0, "max_tokens": 200,
  "response_format": {"type": "json_schema", "json_schema": {"name": "bug", "strict": true, "schema": {
    "type": "object", "properties": {"file": {"type": "string", "maxLength": 12}, "fixed": {"type": "boolean"}},
    "required": ["file", "fixed"], "additionalProperties": false}}}}'
curl -s "127.0.0.1:$PORT/v1/chat/completions" -d '{"messages": [{"role": "user", "content": "Any object"}],
  "temperature": 0, "max_tokens": 60, "response_format": {"type": "json_object"}}'
curl -s "127.0.0.1:$PORT/v1/chat/completions" -d '{"messages": [{"role": "user", "content": "x"}],
  "response_format": {"type": "xml"}}'

The next block shows the real output: the content, finish_reason (why generation stopped), and usage for the first two requests, and the error body for the third.

'{\n\n\t\t\t            \t \t\t\t"file":\n\n "",\n\t\t    \t\t\t    \t \t\t\t \t"fixed":\n\n \t\t\t\t            \t\ttrue }' stop {'completion_tokens': 28, 'prompt_tokens': 24, 'total_tokens': 52, 'prompt_tokens_details': {'cached_tokens': 0}}
'{\n\n"AllайайайContentAlignment kleine了几 kleine了几 optical㉰总裁ContentAlignmentContentAlignmentContentAlignmentContentAlignment kleine早晨 optical㉰尕 optical㉰ optical㉰尕 optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰ optical㉰钪NG钪NG' length
{"error":{"code":400,"message":"response_format type must be one of \"text\" or \"json_object\", but got: xml","type":"invalid_request_error"}}

The schema request returned {"file": "", "fixed": true} wrapped in whitespace, with finish_reason stop after 28 tokens. An empty string satisfies maxLength: 12, because the schema has no minLength, so the grammar allowed the model to close the string at once.

The json_object request shows the most common failure that grammars do not prevent. "Any object" allows a key of any length, the random model kept producing key characters, and max_tokens: 60 stopped generation inside the first key. The finish_reason is length, and the content is a valid prefix but not valid JSON. A client must check finish_reason before parsing.

The third request uses an unknown type and gets HTTP 400 with invalid_request_error. The message names only text and json_object, but the code before it also accepts json_schema, as the first request shows. The server also rejects a request that sets both json_schema and grammar ("Cannot use both json_schema and grammar"). The field strict: true is accepted and has no further effect here, because the grammar is always strict.

Example 10: grammar engines in vLLM

vLLM is a serving engine for GPUs, and it implements the same feature with different tools. In vLLM 0.30.0, its StructuredOutputsConfig (vllm/config/structured_outputs.py) selects a backend, which is the library that does the grammar work, with --structured-outputs-config '{"backend": "..."}'. The choices are auto (the default), xgrammar, guidance (llguidance), outlines, and lm-format-enforcer.

A request carries its constraint in a structured_outputs field with exactly one of these keys:

• json: a JSON Schema.
• regex: a regular expression.
• choice: a list of allowed strings.
• grammar: a grammar string.
• json_object: any JSON object.
• structural_tag: constrain only parts of the text, similar to the lazy grammar in Example 11.

StructuredOutputsParams in vllm/sampling_params.py raises an error for zero keys or for several. The constraint can also arrive in the OpenAI response_format field. The program builds one request body for each kind and computes the size of vLLM's bitmask buffer.

import com.fasterxml.jackson.databind.ObjectMapper;
import com.fasterxml.jackson.databind.node.ObjectNode;
import java.util.Locale;

public class VllmStructured {
    public static void main(String[] args) throws Exception {
        ObjectMapper json = new ObjectMapper();
        String[][] constraints = {
            {"choice", "[\"positive\", \"negative\"]"},
            {"regex", "\"[A-Z][a-z]+\\\\.java:[0-9]{1,5}\""},
            {"json", "{\"type\": \"object\", \"properties\": {\"line\": {\"type\": \"integer\"}}, \"required\": [\"line\"]}"},
            {"grammar", "\"root ::= (\\\"yes\\\" | \\\"no\\\")\""}};
        for (String[] c : constraints) {
            ObjectNode body = json.createObjectNode().put("model", "qwen");
            body.putArray("messages").addObject().put("role", "user").put("content", "...");
            body.putObject("structured_outputs").set(c[0], json.readTree(c[1]));
            System.out.println(json.writeValueAsString(body));
        }
        ObjectNode openai = json.createObjectNode().put("model", "qwen");
        openai.putObject("response_format").put("type", "json_schema").putObject("json_schema")
                .put("name", "loc").set("schema", json.readTree("{\"type\": \"object\"}"));
        System.out.println(json.writeValueAsString(openai));

        // Bitmask rows: one per request in the batch and per speculative position (+1).
        int vocab = 151_936, maxNumSeqs = 256, specTokens = 3;
        int words = (vocab + 31) / 32, rows = maxNumSeqs * (1 + specTokens);
        System.out.printf(Locale.ROOT, "bitmask: %d rows x %d int32 = %.2f MiB%n",
                rows, words, rows * (double) words * 4 / (1024 * 1024));
    }
}

{"model":"qwen","messages":[{"role":"user","content":"..."}],"structured_outputs":{"choice":["positive","negative"]}}
{"model":"qwen","messages":[{"role":"user","content":"..."}],"structured_outputs":{"regex":"[A-Z][a-z]+\\.java:[0-9]{1,5}"}}
{"model":"qwen","messages":[{"role":"user","content":"..."}],"structured_outputs":{"json":{"type":"object","properties":{"line":{"type":"integer"}},"required":["line"]}}}
{"model":"qwen","messages":[{"role":"user","content":"..."}],"structured_outputs":{"grammar":"root ::= (\"yes\" | \"no\")"}}
{"model":"qwen","response_format":{"type":"json_schema","json_schema":{"name":"loc","schema":{"type":"object"}}}}
bitmask: 1024 rows x 4748 int32 = 18.55 MiB

The first four bodies use vLLM's own field:

• choice restricts the answer to a list of strings, which is the enum case of Example 3.
• regex takes a regular expression. The JSON escaping turns \\. in the Java source into \. in the regex.
• json takes a schema object.
• grammar takes a grammar string. For xgrammar, vLLM checks whether the string looks like Lark syntax (grammar_is_likely_lark in vllm/v1/structured_output/utils.py) and converts it to EBNF. Otherwise it parses the string as EBNF in the GBNF style used in this lesson.

The fifth body is the OpenAI form, which vLLM converts to the same parameters.

With auto, the source tries xgrammar first. If xgrammar rejects the request (an unsupported schema feature, for example), it falls back to guidance, and then to outlines when guidance cannot handle the tokenizer or the schema. The comment in the source calls these "opinionated defaults" that may change between releases. A specific backend never falls back. The option disable_any_whitespace: true (xgrammar and guidance only) removes optional whitespace from JSON output, which is the whitespace that Example 9 shows the random model filling.

The last output line is the GPU-side buffer. vLLM allocates one bitmask row per sequence, multiplied by 1 + num_speculative_tokens when speculative decoding is on, because each speculative position needs its own mask (grammar_bitmask in vllm/v1/structured_output/__init__.py). For 256 sequences, 3 speculative tokens, and a 151,936-token vocabulary, that is 1,024 rows of 4,748 32-bit words, which is 18.55 MiB. The xgrammar backend also creates its matcher with max_rollback_tokens equal to the number of speculative tokens, so it can undo the grammar state for rejected guesses. The speculative decoding lesson explains why guesses get rejected: a cheap helper guesses several tokens ahead and the large model discards the ones it disagrees with.

Example 11: lazy grammars for tool calls

An agent's answer often mixes free text with a structured part. A model may write a sentence of reasoning, then a tool call, and only the call must follow a grammar. A grammar applied from the first token would force the reasoning text into the call format as well. A lazy grammar stays inactive until a trigger appears in the output. The trigger can be a word, a token, or a pattern. After the trigger, the grammar constrains everything that follows.

The program simulates a model that offers candidate continuations in order of preference. It uses a Java regular expression as the grammar and checks valid prefixes with Matcher.hitEnd(), which reports whether the matcher reached the end of the input while a longer input could still match. Before the trigger <tool_call>, the first candidate is always taken. After it, the first candidate that keeps the text a valid prefix is taken.

import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class LazyGrammar {
    static final String TRIGGER = "<tool_call>";
    static final Pattern CALL = Pattern.compile(
            "<tool_call>\\{\"name\": \"(read_file|run_tests)\", \"args\": \\{\"path\": \"[a-zA-Z/._]+\"\\}\\}</tool_call>");

    // A string is a valid prefix if the matcher either matches it or ran out of input while matching.
    static boolean validPrefix(String s) {
        Matcher m = CALL.matcher(s);
        return m.matches() || m.hitEnd();
    }

    public static void main(String[] args) {
        // At each step the "model" offers candidates in order of preference.
        List<List<String>> steps = List.of(
                List.of("I will ", "Let me "), List.of("read the file.\n"), List.of("<tool_call>"),
                List.of("{\"name\": \"", "{'name': '"), List.of("readFile", "read_file"),
                List.of("\", \"args\": {\"path\": \"", "\", \"path\": \""), List.of("src/Main.java"),
                List.of("\"}}", "\"}"), List.of("</tool_call>", "\n"));
        StringBuilder text = new StringBuilder();
        int triggerAt = -1;
        for (List<String> candidates : steps) {
            String chosen = null;
            for (String c : candidates) {
                if (triggerAt < 0) { chosen = c; break; }         // before the trigger: unconstrained
                if (validPrefix(text.substring(triggerAt) + c)) { chosen = c; break; }
            }
            String mode = triggerAt < 0 ? "free" : "grammar";
            text.append(chosen);
            if (triggerAt < 0 && text.indexOf(TRIGGER) >= 0) triggerAt = text.indexOf(TRIGGER);
            List<String> shown = candidates.stream().map(c -> "'" + c.replace("\n", "\\n") + "'").toList();
            System.out.printf("%-7s %-48s -> '%s'%n", mode, String.join(" ", shown), chosen.replace("\n", "\\n"));
        }
        System.out.println("tool call complete: " + CALL.matcher(text.substring(triggerAt)).matches());
        System.out.println(text);
    }
}

free    'I will ' 'Let me '                              -> 'I will '
free    'read the file.\n'                               -> 'read the file.\n'
free    '<tool_call>'                                    -> '<tool_call>'
grammar '{"name": "' '{'name': ''                        -> '{"name": "'
grammar 'readFile' 'read_file'                           -> 'read_file'
grammar '", "args": {"path": "' '", "path": "'           -> '", "args": {"path": "'
grammar 'src/Main.java'                                  -> 'src/Main.java'
grammar '"}}' '"}'                                       -> '"}}'
grammar '</tool_call>' '\n'                              -> '</tool_call>'
tool call complete: true
I will read the file.
<tool_call>{"name": "read_file", "args": {"path": "src/Main.java"}}</tool_call>

The first three steps are free: the model's first choice is taken each time, including <tool_call>. Once the trigger appears, the remaining steps are checked against the grammar, starting at the trigger. Here is what happens next:

• At step 4, the model's first choice, {"name": ", is valid.
• At step 5, the model prefers readFile, which is not a tool name in the grammar's alternation (read_file|run_tests), so the second choice read_file is taken.
• At step 6, the model's first choice gives the arguments in the expected shape.
• At the last step, </tool_call> is chosen over a newline, and the complete text matches the pattern.

llama-server implements this with the request fields grammar_lazy and grammar_triggers. When --jinja is on and a request has tools, the server builds the grammar and the triggers from the chat template's tool-call format (common/chat.cpp) and sets them itself. The same fields can also be sent by hand. The next request does that with the random-weight model, whose greedy output for this prompt is 嫄elve嫄路口嫄路口路口.... It uses the word 路口 (a single token in the Qwen2 vocabulary) as the trigger.

curl -s "127.0.0.1:$PORT/completion" -d '{"prompt": "def add(a, b):", "n_predict": 24, "temperature": 0,
  "grammar": "root ::= \"路口\" \" = \" [0-9]{1,3} \"\\n\"",
  "grammar_lazy": true, "grammar_triggers": [{"type": 1, "value": "路口"}], "preserved_tokens": ["路口"]}'

The next block shows the real output: the content, stop_type, and tokens predicted.

'嫄elve嫄路口 = 2\n' eos 9

Before the trigger, the model wrote its usual 嫄elve嫄 freely. When it produced 路口, the grammar took over: =, one digit, a newline, and the end. Without the lazy grammar, the same prompt continues with 嫄路口路口路口... for all 24 tokens. The trigger type is a number from the enum in common/common.h: 0 is a token, 1 is a word, 2 is a pattern, and 3 is a full pattern. A word trigger that is a single token must also appear in preserved_tokens, or the server rejects the request with "Grammar trigger word should be marked as preserved token".

Example 12: pitfalls, whitespace and truncation

A grammar guarantees that every output is grammatical, but two things can still go wrong. The first comes from the grammar's freedom to add whitespace. The second comes from the token limit. The program measures the whitespace in the real output of Example 9 and then parses a JSON object that is cut at several lengths, to show when a cut object becomes valid.

import com.fasterxml.jackson.databind.ObjectMapper;

public class WhitespaceTruncation {
    public static void main(String[] args) throws Exception {
        ObjectMapper json = new ObjectMapper();
        // Real content from llama-server with the random-weight model and a schema (Example 9).
        String real = "{\n\n\t\t\t            \t \t\t\t\"file\":\n\n \"\",\n\t\t    \t\t\t    \t \t\t\t \t\"fixed\":"
                + "\n\n \t\t\t\t            \t\ttrue }";
        long ws = real.chars().filter(Character::isWhitespace).count();
        String compact = json.writeValueAsString(json.readTree(real));
        System.out.printf("grammar output: %d chars, %d whitespace (%d%%)%n", real.length(), ws, 100 * ws / real.length());
        System.out.println("compact form  : " + compact + " (" + compact.length() + " chars)");

        // Truncation: a valid prefix is not valid JSON.
        String full = "{\"file\":\"Main.java\",\"line\":42,\"severity\":\"high\"}";
        for (int cut : new int[] {10, 25, 40, full.length() - 1, full.length()}) {
            String part = full.substring(0, cut);
            String result;
            try {
                json.readTree(part);
                result = "parses";
            } catch (Exception e) {
                result = "fails: " + e.getClass().getSimpleName();
            }
            System.out.printf("%2d chars %-52s %s%n", cut, part, result);
        }
    }
}

grammar output: 92 chars, 68 whitespace (73%)
compact form  : {"file":"","fixed":true} (24 chars)
10 chars {"file":"M                                           fails: JsonEOFException
25 chars {"file":"Main.java","line                            fails: JsonEOFException
40 chars {"file":"Main.java","line":42,"severity"             fails: JsonEOFException
47 chars {"file":"Main.java","line":42,"severity":"high"      fails: JsonEOFException
48 chars {"file":"Main.java","line":42,"severity":"high"}     parses

The schema-constrained output of Example 9 is 92 characters, and 68 of them (73%) are whitespace. The compact form is 24 characters. The grammar's space rule permits up to two newlines and 20 tabs or spaces at every gap, and a model that gives some probability to whitespace tokens can spend most of its budget there. Trained models mostly write compact or conventionally indented JSON because their training data does. A quantized or confused model can still loop on whitespace until max_tokens. There are three remedies: vLLM's disable_any_whitespace, a hand-written GBNF grammar whose space rule allows at most one space, or a sampling penalty.

The truncation lines show that every cut of a valid JSON text fails to parse until the last character arrives, even at 47 of 48 characters. A grammar guarantees that the text is a valid prefix at every step. It cannot guarantee that the text is finished when max_tokens runs out. The client has to check finish_reason (length against stop) and do one of two things. It can raise the limit and retry, as Project 14 does. Or it can bound the grammar so that its longest valid text fits in the budget, using maxLength, maxItems, and bounded repetitions.

Example 13: pitfalls, quality under heavy constraints and key order

A grammar can also lower the quality of the content it guarantees. The program has two parts. The first computes the probability a constraint keeps when the model wants to say something that the schema forbids. The second reproduces the order in which llama.cpp's schema converter writes keys, which matters when a schema asks a model to reason before it answers.

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;

public class HeavyConstraints {
    public static void main(String[] args) {
        // 1. Mass kept by the mask: the model wants to say it does not know, the schema demands an integer.
        Map<String, Double> next = new LinkedHashMap<>();
        next.put("\"unknown\"", 0.55); next.put("null", 0.20); next.put("42", 0.10);
        next.put("7", 0.08); next.put("1", 0.07);
        Set<String> integers = Set.of("42", "7", "1");
        double kept = 0;
        for (var e : next.entrySet()) if (integers.contains(e.getKey())) kept += e.getValue();
        System.out.printf(Locale.ROOT, "mass on allowed tokens: %.2f%n", kept);
        for (var e : next.entrySet())
            if (integers.contains(e.getKey()))
                System.out.printf(Locale.ROOT, "  %-3s %.2f -> %.3f after renormalizing%n", e.getKey(), e.getValue(), e.getValue() / kept);

        // 2. Key order: llama.cpp's converter emits required properties first, then optional ones.
        List<String> schemaOrder = List.of("reasoning", "answer");   // as listed under "properties"
        Set<String> required = Set.of("answer");
        List<String> grammarOrder = new ArrayList<>();
        for (String p : schemaOrder) if (required.contains(p)) grammarOrder.add(p);
        for (String p : schemaOrder) if (!required.contains(p)) grammarOrder.add(p);
        System.out.println("schema order : " + schemaOrder);
        System.out.println("grammar order: " + grammarOrder + " (required first)");
        System.out.println("with both required: " + schemaOrder + " (schema order kept)");
    }
}

mass on allowed tokens: 0.25
  42  0.10 -> 0.400 after renormalizing
  7   0.08 -> 0.320 after renormalizing
  1   0.07 -> 0.280 after renormalizing
schema order : [reasoning, answer]
grammar order: [answer, reasoning] (required first)
with both required: [reasoning, answer] (schema order kept)

The model's distribution puts 0.55 on "unknown" and 0.20 on null, which are the honest answers. The schema demands an integer, so only 0.25 of the probability is allowed. Scaling the remaining numbers up to add to 1 turns the model's weak guesses into confident ones: 42 goes from 0.10 to 0.400 (0.10 / 0.25). The output is a well-formed integer that the model itself rated as unlikely. A schema that leaves no room for "not found" (a nullable field, or an enum value such as unknown) forces the model to invent values. Low kept mass over many steps is a sign that the schema or the prompt is fighting the model. Logging the kept mass, or the log probabilities of the output, makes this visible.

The second part concerns key order. llama.cpp's _build_object_rule (common/json-schema-to-grammar.cpp) writes the required properties first, in schema order, and then the optional ones. With reasoning optional and answer required, the grammar forces answer before reasoning. A model that was meant to reason first must now answer first and justify afterwards, so the reasoning cannot influence the answer. Making both properties required keeps the schema order. docs/llguidance.md states that llguidance keeps the definition order regardless of required, so the same schema can produce different key orders on different backends. A schema that is meant to make the model think before answering must list the reasoning field first and mark it required.

Other pitfalls, as a table:

Example 14: Project 14, part 1, a constrained sampler over a toy vocabulary

Project 14 puts the pieces into working code. Part 1 is a reusable class, ConstrainedSampler. It takes a grammar (a Java regex standing in for a compiled schema) and a vocabulary. At every step it masks each token that would leave the grammar's set of valid prefixes, allows <eos> only on a complete match, samples from the masked scores, and reports why it stopped. The finish reason is stop (the sampler chose <eos>), length (the token budget ran out), or dead end (no token was allowed).

The schema is a person record: a capitalized name of 2 to 9 letters and an age from 1 to 99. Jackson then parses each result into a Java record. The program runs four seeds and then repeats seed 1 with a budget of only 6 tokens.

import com.fasterxml.jackson.databind.ObjectMapper;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class ConstrainedSampler {
    record Person(String name, int age) {}
    record Result(String text, int steps, int maskedOut, String finish) {}

    static final String EOS = "<eos>";
    final Pattern grammar;
    final List<String> vocab;

    ConstrainedSampler(Pattern grammar, List<String> vocab) { this.grammar = grammar; this.vocab = vocab; }

    boolean allowed(String text, String token) {
        Matcher m = grammar.matcher(token.equals(EOS) ? text : text + token);
        return token.equals(EOS) ? m.matches() : (m.matches() || m.hitEnd());
    }

    Result generate(Random model, int maxTokens) {
        StringBuilder text = new StringBuilder();
        int maskedOut = 0;
        for (int step = 0; step < maxTokens; step++) {
            List<Integer> ok = new ArrayList<>();
            double[] logits = new double[vocab.size()];
            for (int i = 0; i < logits.length; i++) {
                logits[i] = model.nextGaussian();                // stand-in for the model's logits
                if (allowed(text.toString(), vocab.get(i))) ok.add(i); else maskedOut++;
            }
            if (ok.isEmpty()) return new Result(text.toString(), step, maskedOut, "dead end");
            double max = Double.NEGATIVE_INFINITY, sum = 0;
            for (int i : ok) max = Math.max(max, logits[i]);
            for (int i : ok) sum += Math.exp(logits[i] - max);
            double u = model.nextDouble() * sum;
            int pick = ok.get(ok.size() - 1);
            for (int i : ok) { u -= Math.exp(logits[i] - max); if (u < 0) { pick = i; break; } }
            if (vocab.get(pick).equals(EOS)) return new Result(text.toString(), step + 1, maskedOut, "stop");
            text.append(vocab.get(pick));
        }
        return new Result(text.toString(), maxTokens, maskedOut, "length");
    }

    public static void main(String[] args) throws Exception {
        Pattern schema = Pattern.compile("\\{\"name\": \"[A-Z][a-z]{1,8}\", \"age\": [1-9][0-9]?\\}");
        List<String> vocab = List.of("{", "{\"", "name", "\":", " \"", "\", \"", "age", ": ", "\"name\": \"",
                "A", "Ada", "Al", "an", "Bo", "b", "ice", "ob", "o", "x", "1", "4", "42", "7", "0", "}", "\"}",
                ", ", " ", "[", "null", "Sure", EOS);
        ConstrainedSampler sampler = new ConstrainedSampler(schema, vocab);
        ObjectMapper json = new ObjectMapper();
        for (int seed = 1; seed <= 4; seed++) {
            Result r = sampler.generate(new Random(seed), 40);
            String parsed;
            try {
                parsed = json.readValue(r.text(), Person.class).toString();
            } catch (Exception e) {
                parsed = "not parsed: " + e.getClass().getSimpleName();
            }
            System.out.printf("seed %d: %-34s %2d tokens, %3d masked, %-6s %s%n",
                    seed, r.text(), r.steps(), r.maskedOut(), r.finish(), parsed);
        }
        Result cut = sampler.generate(new Random(1), 6);
        System.out.println("max 6 tokens: " + cut.text() + " finish=" + cut.finish());
    }
}

seed 1: {"name": "Sureanob", "age": 41}    13 tokens, 372 masked, stop   Person[name=Sureanob, age=41]
seed 2: {"name": "Axobnullb", "age": 42}   16 tokens, 458 masked, stop   Person[name=Axobnullb, age=42]
seed 3: {"name": "Aicexnull", "age": 10}   16 tokens, 457 masked, stop   Person[name=Aicexnull, age=10]
seed 4: {"name": "Surean", "age": 42}      13 tokens, 378 masked, stop   Person[name=Surean, age=42]
max 6 tokens: {"name": "Sureanob", " finish=length

Every seed produced text that Jackson parsed into a Person record. The grammar plus the parser give a typed value. The names are nonsense (Sureanob, Axobnullb) because the "model" is random noise. Sure and null appear inside names because those tokens consist of letters that fit [A-Z][a-z]{1,8}. The grammar decides structure and character classes, not meaning.

The masked column counts how many token candidates were removed over the whole run. With 32 tokens and 13 steps, seed 1 removed 372 of 416 candidates, which means that on most steps only a few tokens fit. The stop finish means the sampler chose <eos> at a point where the regex matched completely.

The last output line reruns seed 1 with a budget of 6 tokens. The text is a valid prefix with finish=length, and Jackson would fail on it. This is the truncation case of Example 12.

The first version of this program also showed a dead end. The vocabulary had ": " but no single space. A path through "\":" led to "age": with no token able to add the required space, and the sampler returned dead end. Adding " " to the vocabulary fixed it. Real vocabularies contain all single bytes, but grammars over special tokens can still reach states with no allowed token. A sampler must report that situation and not loop.

Example 15: Project 14, part 2, an extractor against llama-server

Part 2 uses a real server to turn free text into records. The extractor does four things:

1. It sends a chat request with a response_format schema.
2. It checks finish_reason before it parses anything.
3. After a truncation, it retries with four times the token budget (up to 3 attempts).
4. It maps the JSON into a Java record.

It needs a running llama-server, so the block is marked ignore for the checker (which skips it). The base URL comes from the first argument.

import com.fasterxml.jackson.databind.JsonNode;
import com.fasterxml.jackson.databind.ObjectMapper;
import com.fasterxml.jackson.databind.node.ObjectNode;
import java.net.URI;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.util.List;

public class Extractor {
    record Finding(String file, int line, String severity) {}

    static final ObjectMapper JSON = new ObjectMapper();
    static final String SCHEMA = """
        {"type": "object",
         "properties": {"file": {"type": "string", "maxLength": 24},
                        "line": {"type": "integer", "minimum": 1, "maximum": 99999},
                        "severity": {"enum": ["low", "medium", "high"]}},
         "required": ["file", "line", "severity"], "additionalProperties": false}""";

    static Finding extract(HttpClient http, String baseUrl, String text) throws Exception {
        int maxTokens = 64;
        for (int attempt = 1; attempt <= 3; attempt++, maxTokens *= 4) {
            ObjectNode body = JSON.createObjectNode();
            body.putArray("messages").addObject().put("role", "user")
                    .put("content", "Extract file, line, and severity as JSON from: " + text);
            body.put("temperature", 0).put("max_tokens", maxTokens);
            ObjectNode format = body.putObject("response_format").put("type", "json_schema");
            format.putObject("json_schema").put("name", "finding").set("schema", JSON.readTree(SCHEMA));

            HttpRequest req = HttpRequest.newBuilder(URI.create(baseUrl + "/v1/chat/completions"))
                    .header("Content-Type", "application/json")
                    .POST(HttpRequest.BodyPublishers.ofString(JSON.writeValueAsString(body))).build();
            JsonNode resp = JSON.readTree(http.send(req, HttpResponse.BodyHandlers.ofString()).body());
            JsonNode choice = resp.path("choices").path(0);
            String finish = choice.path("finish_reason").asText();
            String content = choice.path("message").path("content").asText();
            System.out.printf("attempt %d: max_tokens=%d finish_reason=%s completion_tokens=%d%n",
                    attempt, maxTokens, finish, resp.path("usage").path("completion_tokens").asInt());
            if (!finish.equals("stop")) continue;                // truncated: valid prefix, not valid JSON
            JsonNode obj = JSON.readTree(content);
            return new Finding(obj.get("file").asText(), obj.get("line").asInt(), obj.get("severity").asText());
        }
        throw new IllegalStateException("no complete JSON after 3 attempts");
    }

    public static void main(String[] args) throws Exception {
        String baseUrl = args.length > 0 ? args[0] : "http://127.0.0.1:8080";
        HttpClient http = HttpClient.newHttpClient();
        for (String text : List.of("NullPointerException in Parser.java at line 88, crashes the build",
                                   "Typo in README.md line 3")) {
            Finding f = extract(http, baseUrl, text);
            System.out.println("-> " + f);
        }
    }
}

The next block shows the real output against llama-server running the random-weight model. The server was started as in Example 8, and Java ran with -Dstdout.encoding=UTF-8.

attempt 1: max_tokens=64 finish_reason=length completion_tokens=64
attempt 2: max_tokens=256 finish_reason=stop completion_tokens=79
-> Finding[file=<<尕']->acher хорошо玩法瓤瓤瓤, line=33333, severity=high]
attempt 1: max_tokens=64 finish_reason=stop completion_tokens=54
-> Finding[file=, line=33333, severity=high]

The first text needed two attempts. With 64 tokens the model was still inside the JSON (finish_reason=length, all 64 tokens used), so the extractor did not try to parse. It retried with 256 tokens, and the second attempt finished after 79 tokens. The second text fit in the first budget, at 54 tokens.

Both records are type-correct: file is a string of at most 24 characters, line is an integer in range, and severity is one of the enum values. Both are wrong in content, because the model has random weights. With a trained model, the same program returns Parser.java, 88, high for the first text. The program does not change, only the model file does.

Three properties make the extractor usable in an agent. It never parses truncated text, its retries are bounded, and its output is a typed record and not a string. A production version would also validate values that the schema cannot express (a file that exists, a line within the file) and log the attempt count, which shows when a budget or a prompt needs tuning.

Interview points

• Constrained decoding masks the tokens that would make the output an invalid prefix of a grammar. Masked logits become -inf, and the remaining probabilities keep their ratios.
• Regular languages (enums, regexes) need a finite automaton. Nested JSON needs a pushdown recognizer with a stack.
• Grammars are defined over characters, but tokens span several characters. Each candidate token is fed through the recognizer character by character, and <eos> is allowed only in an accepting state.
• Naive masking costs the vocabulary size times the token length at every step. Tries, precomputed lexer states (xgrammar, llguidance), checking the sampled token first (llama.cpp), and CPU-GPU overlap (vLLM) reduce the cost.
• In llama.cpp, GBNF is passed with --grammar or --grammar-file, a JSON Schema with -j or json_schema, and response_format works on the OpenAI endpoint. The converter puts required keys first and skips unsupported keywords.
• In vLLM, structured_outputs takes exactly one of json, regex, choice, grammar, json_object, or structural_tag. The backends are xgrammar, guidance, outlines, and lm-format-enforcer, and auto falls back from xgrammar to guidance to outlines.
• Lazy grammars activate on a trigger. Tool calling with --jinja uses them, so free text before the call stays unconstrained.
• A grammar does not prevent truncation, so a client must check finish_reason before parsing.
• Heavy constraints can force values that the model rated as unlikely. Schemas need a way to express "unknown", and key order affects reasoning.
• The grammar does not show the schema to the model, so the prompt must describe it.

Summary

• A logit mask sets forbidden tokens to -inf. In the toy example the two allowed tokens kept their 2.7 to 1 ratio after scaling.
• An automaton over characters accepted red, grey, and green through different token sequences, and a vocabulary without single letters reached a dead end.
• The pushdown recognizer classified ten inputs as complete, valid prefix, or invalid at a specific character.
• After a prefix inside a string, "]} was allowed and completed the JSON, and "]}, failed at its fourth character.
• For 20,000 tokens, a trie needed 4,162 character steps against 31,226 for naive replay. A 151,936-token bitmask is 4,748 words, which is 18,992 bytes.
• GBNF with bounded repetitions produced edit errmsg/loader/loaderyy.java line 8888 from random weights and stopped after 18 tokens.
• llama-server's JSON schema grammar writes integer ranges as digit-count alternatives and allows up to two newlines and 20 tabs or spaces between tokens.
• response_format accepts text, json_object, and json_schema. Other types return HTTP 400.
• A json_object request with 60 tokens ended with finish_reason length inside a key.
• vLLM allocates max_num_seqs × (1 + num_speculative_tokens) bitmask rows of (vocab + 31) / 32 int32 words.
• A lazy grammar on llama-server let the model write freely until 路口, then forced = 2\n and stopped.
• 73% of a schema-constrained output from the random model was whitespace.
• Project 14 generated typed records with a regex-constrained sampler and extracted records from llama-server with bounded retries on truncation.