Where constrained decoding time goes

Percentiles are useful, but they hide what constrained decoding actually feels like from one token to the next. A decoder can spend almost nothing at one position and milliseconds at the next, even though the model is generating one continuous piece of text.

The examples below are taken directly from the benchmark suite used for GLRMask’s weighted-automata article. Each coloured region is one Llama-3 token. The colour is TBM, the time to build the token mask and then commit the chosen token. Green is 5 µs or less. 1 ms is red. Slower tokens stay red and become progressively stronger rather than changing to another hue. The scale is shared by every map.

On desktop the two systems are shown side by side. On mobile, toggle between them. Hover a token to compare the two measured times.

JSON

JSON is also where llguidance is often extremely fast. The first example is a valid JSON Schema Bench input with fixed object fields and ordinary string values.

Fixed fields

Both systems stay comfortably in the microsecond range. Punctuation and pieces of the ISO timestamps get down to a few microseconds. The larger llguidance steps are around property names and transitions into constrained values, but its median TBM is still only 5.8 µs and its p99 is 102 µs. GLRMask is 3.5 µs and 7.1 µs.

llguidance has a much wider spread across token positions. GLRMask has already compiled the lexer/parser interaction into the automata used at runtime, leaving less position-dependent work online.

URI field

The next schema is still small and conventional: fixed fields for an ingest/publish request, with an enum for action, an integer version, and a location string constrained to an https:// or file:// URI.

Most llguidance positions are again cheap: the median is 12.3 µs. Three tokens in the URI are different. example takes 1.12 ms, .com 513 µs, and the closing ", 532 µs. The p99 is 889 µs. GLRMask’s p99 on the same input is 4.4 µs and its maximum is 4.5 µs.

This is a useful middle case: the aggregate median says llguidance is doing very well, but a few token boundaries are two orders of magnitude slower than the rest of the sequence.

Arbitrary property names

The next schema is tiny. It is an object whose only substantive rule is patternProperties: { "^.{1,255}$": {} }. The valid input is just three empty objects under three keys.

The first key token costs llguidance 3.37 ms. At that position its mask contains 123,440 of the 128,256 Llama-3 tokens, so the online vocabulary traversal has an unusually broad set of possibilities to account for. The median over the whole 16-token input is still only 43.6 µs. GLRMask’s maximum is 11.7 µs.

Patterned email fields

This one is a normal-looking six-field object. from and to are strings with email patterns; the other fields are strings and an integer with ordinary length limits.

Here the slow work is spread over the email value rather than concentrated in one token. Six llguidance steps exceed 1 ms. In the first address, test reaches 4.04 ms, .gov 2.36 ms, .uk 1.36 ms, @example 1.25 ms, and the following ", 3.18 ms. The second address has another 1.10 ms test step. GLRMask’s maximum over the whole input is 12.1 µs.

All four JSON inputs above are existing valid JSON Schema Bench examples. They range from the kind of fixed-field object where llguidance is excellent to small schemas where a handful of ordinary token positions become millisecond-scale.

JavaScript

For a less artificial JavaScript example, this is an actual file from this site: the complete scripts/release.mjs production-release script. It is 4.6 KB of ordinary project glue: Node imports, subprocess calls, option objects, error handling, git commands, template strings, environment variables, and an interactive async confirmation.

A real project file

The file is 1,174 Llama-3 tokens. llguidance’s median TBM is 610 µs and its p99 is 2.70 ms; 529 token positions exceed 1 ms and 232 exceed 2 ms. The expensive positions are spread through ordinary syntax rather than one special construct: function, semicolon-newline boundaries, .platform, .trim, comparison operators, call openings and indentation all appear near the slow end. GLRMask’s median is 17.7 µs, its p99 is 112 µs, and its maximum is 157 µs.

The viewer shows the first 50 lines of the 137-line file. The timing statistics above still cover all 1,174 tokens in the complete file.

The next fixture exercises more of the language: template literals, substitutions, a tagged template, a regular expression and division.

Templates and regex

llguidance still has 4–5 µs positions where its lexer can settle a large part of the vocabulary cheaply. Other positions require much more of the online machinery. In this short input, tokens such as [ in the function body, const, the start of division, a backtick and the regex flags reach roughly 2.5–3.2 ms.

GLRMask varies on a smaller scale. Its median is 14.3 µs and its p99 is 59.8 µs for this input. llguidance’s median is 925 µs and its p99 is 2.83 ms. The expensive llguidance positions line up with particular lexer/parser situations; GLRMask resolved most of that structure during compilation.

The JavaScript benchmark in the main article gives llguidance a companion grammar written specifically for it, with %ignore-based trivia handling, larger parser limits and JavaScript-specific tokenizer slices. On the two inputs used for the direct grammar-shape comparison, llguidance’s median is 1.60 ms with that tuning and 21.6 ms when both systems are instead given the same generic EBNF grammar. GLRMask moves from 50.6 µs to 127 µs. On the full 4,099-token tuned corpus, the medians are 1.05 ms for llguidance and 40.9 µs for GLRMask.

Later profiling narrowed down the slow JavaScript positions. In a trace of all 4,099 token steps, 3,466 had lexer_cost == 0. Millisecond masks still occurred. CPU time tracked vocabulary-trie traversal and aggregate speculative Earley work much more closely, and slow states commonly visited around 180,000 to 207,000 trie nodes.

Tokenizer slices account for part of the difference between JSON and JavaScript. A slice is checked against one active lexeme continuation. Llama-3 often includes the space before a word in the model token: 43,044 of the 128,256 vocabulary entries are one ASCII space followed by letters. A token such as value therefore crosses from skipped whitespace into an identifier. I tested a JavaScript grammar that moved spaces and newlines into every following terminal while leaving comments skipped. It preserved every post-first-token mask across the 31 fixtures and reduced stabilized p50, p90 and p95 mask times by about 16%, 15% and 13%. The remaining millisecond tail still involved large trie walks. The cross-lexeme slicer experiment has the minimal grammar and trie-node counts.

Measurement

These token maps were measured on an Apple M1 Pro with the 128,256-token Llama-3 vocabulary. Each displayed token value is the minimum of 10 measured runs after one warm-up run, using thread CPU time. The JSON examples are Github_easy---o32480, Github_easy---o44051, Github_trivial---o9908, and Github_easy---o21456 from JSON Schema Bench. The larger JavaScript example is this site’s complete scripts/release.mjs; the smaller syntax-focused example is fixture 23 from CFA’s 31-file JavaScript capability corpus.

The JavaScript grammars are performance-oriented counterparts rather than a claim of byte-for-byte mask equivalence. GLRMask uses its native GLRM grammar; llguidance uses the tuned Lark companion. They intentionally differ at some trivia and automatic-semicolon-insertion boundaries. The expected token in both displayed fixtures is accepted throughout by both systems.

For the aggregate results, including the untuned JavaScript comparison and compilation times, see the benchmark section of the GLRMask article.