Why llguidance is fast

Also allows skipping work for entire subtrees:

• Prefix has no live lexer or parser path: reject whole subtree.
• All suffixes stay in current lexeme until token ends: accept whole subtree.

In practice, ‘all suffixes stay in current lexeme until token ends’ can be computed by storing at each vocab trie node set of bytes that occur in the suffixes it represents. Then for the lexer state, we ask which bytes this state can keep consuming indefinitely. Then if former contained in latter (subset) we accept whole subtree.

e.g. For arbitrary " terminated string [^"]*" it can consume [^"], i.e. anything except ", indefinitely, i.e. set is [^"]. So if at vocab node who’s suffixes are all alphabetical [a-zA-Z], then [a-zA-Z] is subset of [^"], and we accept subtree.

This very helpful for JSON where arbitrary string and numbers keep subtrees inside one lexeme, allowing whole subtree accept, and exact literals (e.g. property names) follow a narrow path, allowing immediate bulk rejection/termination when traversal deviates from that path.

Net effect is JSON skips huge amount of work.

llguidance

llguidance uses this to great effect. They check subsumption of predefined expressions rather than per-vocab-trie-node byte looping containment. e.g. Might have slice for [a-zA-Z]+. At build time they create bitmask of all LLM tokens whose full bytes match [a-zA-Z]+. They also build filtered vocab tries for slices and tokens left after nested slices are removed. They check at beginning of masking (not during trie traversal) whether slice language is contained in prefixes of active lexeme continuation language. Yes? Then OR bitmask for slice into output mask without traversing its trie.

In other words:

• Define slice language $S$, e.g. [a-zA-Z]+.
• At build time, precompute bitmask of LLM tokens whose full bytes belong to $S$.
• Build filtered vocab tries for each slice and for tokens left after nested slices are removed.
• At mask generation time, let $A$ = active lexeme continuation language.
• Check slice regexes recursively for whether $S$ is contained in prefixes of $A$.
• Yes? OR bitmask for $S$ into output without traversing its trie.
• Otherwise traverse relevant filtered leftover trie.

Proof:

• LLM token $j$ is in slice bitmask iff its full bytes $\beta(j)$ belong to $S$.
• Runtime check proves $S \subseteq \operatorname{Prefixes}(A)$.
• Therefore $\beta(j) \in S$ implies $\beta(j) \in \operatorname{Prefixes}(A)$.
• QED

Core idea same: settle many tokens with one containment check and one bitmask OR.

Slices

llguidance defines these JSON slices:

[\x20\x0A\x0D\x09]+
[^"\\\x00-\x1F\x7F]{1,10}
[^"\\\x00-\x1F\x7F]{1,30}
[^"\\\x00-\x1F\x7F]+

First = JSON whitespace.

Other three = runs of JSON-string-safe bytes.

The regexes overlap. Tokens are claimed in order. Effective token groups are:

C{1,10}
C{11,30}
C{31,}
everything else

$C$ = one JSON-string-safe byte.

Each group gets precomputed token mask and vocab trie.

At mask time, llguidance checks whether whole slice fits current lexer continuation.

If yes, it ORs slice mask and skips that trie.

If no, it walks that slice trie normally.

Why bounded repetitions {1,10} and {1,30}?

Suppose bounded string has 20 bytes left.

Unbounded slice C+ does not fit. It includes strings longer than 20 bytes.

Without bounded slices, any bounded repetition would force normal trie traversal.

But C{1,10} fits. llguidance accepts that whole slice at once.

Normal traversal is needed only near end, when fewer than ten bytes remain.

llguidance says full mask computation for typical JSON Schema takes about 1.5 ms when slicer does not apply.

Crossing lexeme boundaries

I ran into a limitation while tuning the JavaScript grammar. The first of these grammars puts the spaces and the following word in separate lexemes:

start: WS IDENTIFIER
WS: / +/
IDENTIFIER: /[A-Za-z]+/

The second puts the same bytes in one lexeme:

start: SPACED_IDENTIFIER
SPACED_IDENTIFIER: / +[A-Za-z]+/

Both accept one or more spaces followed by one or more letters. With the 128,256-token Llama-3 vocabulary used in my benchmarks, their complete next-token masks at the empty input are bit-for-bit identical.

With slicing disabled, both grammars visit 93,978 vocabulary-trie nodes. For the first grammar I used separate + and [A-Za-z]+ slices. For the second I used one +[A-Za-z]+ slice.

Grammar	Trie nodes without slices	Trie nodes with slices
WS IDENTIFIER	93,978	93,898
SPACED_IDENTIFIER	93,978	2,817

The slicer checks a slice against the continuation language of one active lexeme. In the first grammar, a model token such as value starts in WS and finishes in IDENTIFIER. Accepting the complete model token requires finishing WS, advancing the parser, and entering IDENTIFIER. The slice check does not compose those operations, so the token remains in the trie walk.

Leading-space words occupy a large part of the Llama-3 vocabulary. Of the 128,256 tokens used here, 43,044 (33.6%) are exactly one ASCII space followed by letters. There are 28,158 (22.0%) letters-only tokens. With the characters admitted by the JavaScript identifier grammar, 44,231 tokens (34.5%) consist of whitespace followed by identifier-like text.

I then moved spaces and newlines into the following JavaScript terminal instead of treating them as skipped lexemes. Comments stayed as skipped trivia because folding comments into every terminal changed many masks. The whitespace/newline version accepted all 4,099 tokens in the 31-file JavaScript corpus. Every mask after the first token of each file was bit-for-bit identical to the original grammar. The first mask differs because llguidance normally disables skipped lexemes before the first real lexeme.

In six alternating runs, taking the elementwise minimum at each token position, p50 mask time fell from 779 to 654 µs, p90 from 2.03 to 1.73 ms, and p95 from 2.23 to 1.95 ms. Most of the JavaScript cost remained. The containment check also failed to apply useful slices to the real identifier language, [A-Za-z_$][A-Za-z0-9_$]*, particularly once reserved-word exclusion was included. Tokens crossing punctuation and other grammar-terminal boundaries still left large parts of the vocabulary trie on the online path.