llguidance HATES This One Weird Grammar

Consider this grammar:

%llguidance {"no_forcing": true}
start: STEM SUFFIX

STEM: "list" | "listen"
SUFFIX: "ed"

The grammar has two terminals. STEM matches either list or listen, and SUFFIX matches ed. The shortest accepted input splits like this:

listSTEMedSUFFIX

Together, those lexemes form listed. The longer stem gives us listened.

llguidance rejects even the shorter one:

>>> b"listed" in next_token_mask
False
>>> validate_tokens([b"listed"])
0
>>> consume_token(b"listed")
False

How llguidance builds a mask

llguidance generates a token mask by walking a trie containing the byte strings in the model vocabulary. As it descends through the trie, it speculatively feeds bytes to a recognizer. A failed byte prunes the trie branch. Reaching a terminal node while the recognizer is still viable adds that vocabulary token to the mask.

Inside that recognizer is a lexer that feeds into an Earley parser. The lexer consumes bytes until it has a completed lexeme. The parser then consumes that lexeme and advances to a new state.

Sounds simple so far, right? And it is. But unfortunately it won’t be.

Greedy lexing

Suppose the lexer is reading STEM = "list" | "listen". And suppose the full input string is:

listened

The lexer reads this as:

listenSTEMedSUFFIX

Which parses. And lo, all is well. Or is it?

But remember, llguidance traverses a trie, not a full input string.

Be llguidance for a moment. Traverse the trie. First l. Then i. Then s. Then t.

We’ve seen four bytes: list.

You check the lexer. A match!

But wait. It’s not that simple.

The match is conditional.

This trie node represents the complete LLM token "list". But it also represents "liste...", "lists...", and whatever other LLM tokens happen to begin with "list".

The condition this match is predicated on is that there is not a longer match of the same terminal, STEM. If the next bytes are en, the greedy match is listen, not list.

So, uh, that’s a problem.

We can’t just look ahead. There are multiple possible aheads. This is a trie, which branches out into multiple possibilities.

What about backtracking within the same LLM token? In principle, llguidance could retain earlier accepting lexer and parser states, then try a different lexing if the longer greedy match later fails. Doing that while walking the token trie may add substantial overhead.

The other option is to accept conditionally: let the parser consume the terminal, but tag that parser state with a condition saying that it is valid only if we don’t later find a longer match for the same terminal. But that… uh, oh, actually, I guess that does work. In fact, that’s exactly what GLRMask’s dynamic mode does, directly inspired by this insight. But let’s stick to llguidance.

llguidance takes a simpler path. It effectively looks ahead, but only by one byte. And it turns out that for virtually every grammar that matters, this is not a problem. In fact, it’s hard to come up with a real counterexample. So naturally, the English word listed is one.

For listened, greediness makes the right choice. For listed, it does not. After list, the next byte e might begin the suffix ed, or it might continue the stem towards listen. llguidance keeps reading the stem:

list      accepting
liste     live, non-accepting
listed    dead

The d proves that the correct split was list | ed. But by then the accepting boundary after list is two bytes behind.

Easy fix

In the rare case where this is a problem - and there are some - it can be pretty easily resolved by moving the choice into the parser. For our grammar, lowercase stem is a parser rule rather than a terminal:

%llguidance {"no_forcing": true}
start: stem SUFFIX

stem: "list" | "listen"
SUFFIX: "ed"

BEHOLD:

>>> b"listed" in next_token_mask
True
>>> validate_tokens([b"listed"])
1
>>> consume_token(b"listed")
True

JSON is usually safe

Even this repair is rarely necessary. For the largest category of real-life grammar constraints used in generation - of which 99.9% is almost certainly JSON Schema - the issue barely arises.

JSON is unusually friendly to one-byte lookahead. Strings are the clearest case: the closing quote marks the boundary explicitly, so there is no ambiguity about where the string ends.

The other JSON lexemes are similarly well behaved in context. Numbers, true, false, and null are followed by punctuation, whitespace, or the end of input, none of which can continue the preceding lexeme. Even the awkward number path 1 → 1e → 1e2 is harmless: e can continue a number after 1, but it cannot begin anything legal after a completed number. Regex constraints inside strings still end at the closing quote. Any genuinely awkward custom boundary can usually be fixed by splitting the terminal there.

Context matters

It would be nice if we could inspect each terminal definition independently and say: this terminal obeys some rule, therefore the lexer will behave well around it. We cannot. A terminal’s behaviour also depends on the other terminals that the parser permits beside it.

That is not peculiar to llguidance. Lark’s contextual lexer also uses parser state to decide which terminals are active. Here NAME and VALUE have identical definitions:

start: "name:" NAME
     | "value:" VALUE

NAME: /[a-z]+/
VALUE: /[a-z]+/

%ignore /[ \t]+/

Yet the same bytes become different tokens in different parser contexts:

>>> parser.parse("name: abc").children[0]
Token('NAME', 'abc')
>>> parser.parse("value: abc").children[0]
Token('VALUE', 'abc')

Lark depends on parser context too, but it does not have llguidance’s one-byte lookahead limitation. The opening grammar parses normally:

>>> Lark(grammar, parser="lalr").parse("listed")
Tree(Token('RULE', 'start'), [Token('STEM', 'list'), Token('SUFFIX', 'ed')])

Parser context can nevertheless make llguidance’s behaviour stranger still:

start: "ping " ipv6
     | "connect " (ipv6 | HOST_PORT)

ipv6: HEX "::" HEX

HEX: /[0-9a-f]+/
HOST_PORT: /[a-z0-9]+:[0-9]+/

The grammar accepts an IPv6 address after either command, while connect additionally accepts an ordinary host:port pair. llguidance 1.7.6 behaves like this:

ping fe80::1       accepted
connect fe80::1    rejected
connect server:80  accepted

After ping , only HEX can begin. After connect , both HEX and HOST_PORT are active:

fe80     HEX accepting; HOST_PORT alive
fe80:    HOST_PORT alive, non-accepting
fe80::   HOST_PORT dead

HOST_PORT never matches the address. Merely allowing it in this parser context is enough to erase the valid boundary after fe80.

Lark’s contextual lexer accepts connect fe80::1. It applies each eligible regex to the remaining input, so HOST_PORT fails outright while HEX matches fe80. llguidance discovers that failure incrementally while traversing the vocabulary trie. At fe80:, HOST_PORT is still alive; by the time the second colon kills it, the useful boundary has been lost.

So there is no useful rule for terminals in isolation.

A simple lexer rule

There is, however, a simple sufficient condition for the combined lexer:

Once the lexer is accepting, every continuation that keeps it alive must also leave it accepting.

Equivalently, every live successor of an accepting state in the combined lexer must also be accepting.

Our opening lexer fails:

list      accepting
liste     live, non-accepting
listen    accepting

A conventional identifier lexer passes. Once [A-Za-z_][A-Za-z0-9_]* has matched, every further byte that keeps it alive also leaves it matching.

The combined-lexer qualification matters. Suppose the grammar has both:

IDENT       = [A-Za-z_][A-Za-z0-9_]*
KEYWORD_DEF = def

After reading d, the keyword terminal has not matched yet, but the combined lexer is already accepting because d is a valid identifier.

The rule is simple, but stronger than necessary. Ordinary JSON numbers fail it:

1       accepting
1e      live, non-accepting
1e2     accepting

JSON still works because parser context rules out the dangerous handoff.

The one-byte handoff rule

If you really want a rule that admits cases like JSON numbers, you have to include the parser context:

At a valid lexeme boundary, no byte may both continue the current lexeme and begin a legal next lexeme.

For a terminal $T$ in some reachable parser context, a rough version is:

Here, $\operatorname{continue}(T)$ contains bytes that can keep the lexer alive after $T$ has already matched. $\operatorname{FIRST}(\text{after } T)$ contains bytes that can begin a legal following lexeme in the current parser context.

Our weird grammar fails immediately.

After STEM has matched list, the byte e can keep STEM alive:

list + e = liste

The same byte can begin SUFFIX:

ed

The boundary is invisible when the first byte of SUFFIX arrives. It only becomes clear after the later d, by which time the earlier accepting position has been lost.

An identifier followed by ( passes:

IDENT = [A-Za-z_][A-Za-z0-9_]*

The opening parenthesis cannot continue IDENT. It kills the identifier immediately and can be handed to the next parser row.

This rule is conservative. Shared bytes do not prove that llguidance will reject anything. Parser state, terminal priority, the combined lexer, and other implementation details can settle some cases. The overlap shows where the cheap one-byte handoff has stopped being an adequate explanation.

Not a fundamental tradeoff

An obvious explanation is that this lexer behaviour is simply the tradeoff behind llguidance’s speed. It starts almost instantly, generates masks extremely quickly, and avoids building an LR table or a large recognizer up front. The lexer weirdness looks like the price paid for that performance.

It is not free to fix, but it is not required by llguidance’s architecture either. I implemented an opt-in version that remembers earlier accepting positions in the existing lexer stack. If the attempted longer match dies, it returns to the latest one and replays the bytes that came after it. If that gap becomes long, it keeps a synchronized fallback parser snapshot instead.

That adds state, rollback machinery, and some conservative slow paths while a fallback is pending. What it does not require is replacing the lazy lexer, the Earley parser, or the vocabulary-trie walk. The original path remains intact when the feature is disabled.

How llguidance really works

It took me a while to understand what is going on here. Before getting to the vocabulary trie, it helps to isolate one lexing attempt and put it back in its parser-level context.

def recognize(text, parser):
    position = 0

    while position < len(text):
        state = lexer_for(parser)
        match = next_match(text[position:], state)

        if match is None:
            return False

        parser = parser.consume(match.state.matches())
        position += match.length

    return parser.is_accepting()

The parser repeatedly asks the lexer for one match, consumes the resulting terminal, and continues from the end of that match:

find one lexeme
→ give it to the parser
→ continue

The disagreement is entirely inside next_match.

Consider the scan of listed:

Input prefix    Lexer state
------------    -------------------
l               live, not accepting
li              live, not accepting
lis             live, not accepting
list            live, accepting
liste           live, not accepting
listed          dead

Both approaches visit the same live prefixes. They differ only in which prefix they retain as the match.

We can separate that shared walk from the decision:

@dataclass(frozen=True)
class Prefix:
    state: LexerState
    length: int

    @property
    def accepting(self):
        return self.state.is_accepting()

def live_prefixes(text, state):
    for length, char in enumerate(text, start=1):
        next_state = state.step(char)

        if next_state.is_dead():
            break

        state = next_state
        yield Prefix(state, length)

live_prefixes yields every prefix for which the lexer remains live. It stops before the first character that would kill the lexer. For listed, it yields:

l → li → lis → list → liste

Only list is accepting.

def next_match(text, state):
    candidate = None

    for prefix in live_prefixes(text, state):
        if prefix.accepting:
            candidate = prefix

    return candidate

def next_match(text, state):
    candidate = None

    for prefix in live_prefixes(text, state):
        candidate = prefix

    if candidate is not None and candidate.accepting:
        return candidate

    return None

After scanning listed, the decisive state is already visible:

normal:       prefix = liste    candidate = list
llguidance:   prefix = liste    candidate = liste

Normal maximal munch remembers list, so the parser can consume STEM and continue with ed. The llguidance-style version retains only liste. Because liste is not accepting, it returns None.

The entire difference is:

normal:
    keep the last accepting prefix

llguidance-style:
    keep the last live prefix, then test it

Put another way, the two operations occur in a different order:

normal      = last(accepting(prefixes))
llguidance  = accepting_or_none(last(prefixes))

This is conceptual pseudocode isolating the greedy-boundary decision, not literal llguidance source. The real implementation also handles multiple active terminals, priorities, lazy lexemes, skipped terminals, parser transitions, and traversal of the tokenizer trie. None of those details changes the distinction shown here.

The normalized live_prefixes version makes the difference easy to see, but neither side would usually be written that way. In their more recognizable forms, the same two policies look like this:

def next_match(text, lexer):
    candidate = None

    for length, byte in enumerate(text, start=1):
        lexer = lexer.step(byte)

        if lexer.is_dead():
            break

        if lexer.is_accepting():
            candidate = Prefix(lexer, length)

    return candidate

class Recognizer:
    def advance(self, byte):
        next_lexer = self.lexer_state.step(byte)

        if next_lexer.is_live():
            return Recognizer(self.parser_state, next_lexer)

        if not self.lexer_state.is_accepting():
            return None

        next_parser = self.parser_state.consume(self.lexer_state.matches())
        next_lexer = lexer_for(next_parser).step(byte)

        if next_lexer.is_dead():
            return None

        return Recognizer(next_parser, next_lexer)

The left side is the usual maximal-munch loop: keep scanning, and remember each accepting position in case a longer attempt later fails.

The right side has a different shape because llguidance is an incremental recognizer. It receives one byte at a time. While that byte can continue the current lexer state, it simply advances. Only when continuation fails does it ask whether the current state can be emitted, give that match to the parser, and reuse the killing byte as the beginning of the next lexeme.

That is the same policy as the simpler live_prefixes version. On listed, the ordinary lexer saved list before reaching liste. The llguidance recognizer reaches liste, then sees that d kills it. At that moment its current state is not accepting, so there is nothing to hand to the parser.

In constrained decoding, there is no complete next string. llguidance walks the vocabulary trie, carrying this recognizer state along each possible token prefix. Tokens with the same prefix share the same work:

This is my understanding of the relevant algorithm, not llguidance’s literal implementation. The real code mutates a speculative state stack and pops bytes while walking a flattened vocabulary trie. I return a new recognizer state for each byte because it is easier to follow.

def walk(vocab_node, recognizer):
    if vocab_node.token_id is not None:
        mask.add(vocab_node.token_id)

    for byte, child in vocab_node.children.items():
        next_recognizer = recognizer.advance(byte)

        if next_recognizer is not None:
            walk(child, next_recognizer)

The advance method is the llguidance-shaped function shown above. The parser state determines which terminals are active; the lexer state tracks how far the current terminal has progressed. The vocabulary walk supplies the bytes.

A full vocabulary walk like this takes about a millisecond in the cases I have been testing. llguidance usually does less. Its most important shortcut is subsumption: prove that the current lexer state accepts an entire precomputed slice of the vocabulary, then add that slice to the mask without walking every token in it.

How I changed it

I eventually implemented an opt-in greedy fallback in redesign/greedy-lexeme-fallback-integrated-v3. It lets llguidance continue exactly as before, but remembers where the current greedy lexeme could have ended.

class GreedyReplay:
    accepting_stack_indices = []
    shadow = None

Every byte llguidance pushes already leaves a state in its lexer stack. The new state records which committed stack positions were accepting. During a speculative vocabulary-trie walk, it only scans the part of the lexer stack added by that trie branch. It does not emit the lexeme. It does not fork the parser. The longer interpretation remains the only active interpretation.

For listed, the primary path still looks like this:

list      accepting; remember this position
liste     live, non-accepting
listed    dead

The difference comes when d kills the lexer. Instead of giving up because liste is not accepting, the parser can return to the saved position after list.

Conceptually, the recovery is:

def recover(byte):
    checkpoint = latest_accepting_position()

    restore_lexer_to(checkpoint)
    emit_lexeme_at(checkpoint)
    replay(bytes_after(checkpoint))
    return advance(byte)

The real code is more careful, but that is the operation. It truncates the lexer history to the checkpoint, gives the saved STEM = list match to the Earley parser, then replays the bytes after it—e, followed by the d that exposed the failed longer match. Those bytes are now interpreted in the parser context after STEM, where they form SUFFIX = ed.

So this is not a second recognizer being carried through every byte. Most of the time there is still one recognizer. The fallback interpretation is reconstructed only when the primary interpretation fails.

That matters during the vocabulary walk. llguidance speculatively pushes bytes while descending the token trie, then pops them on the way back out. A recovered fallback must obey the same protocol. The implementation saves an undo snapshot before speculative recovery, so a later pop_bytes() can restore the exact primary state. Definitive token consumption has a corresponding undo record so token rollback can cross a fallback promotion and later take the long match instead.

Replay is not enough

A checkpoint can remain unresolved for an arbitrarily long time. Consider a terminal matching either a or ab{10000}c. If the input is really a followed by another lexeme beginning with ten thousand bs, waiting for the final failure and then replaying all ten thousand bytes would produce a fairly spectacular latency spike.

The implementation therefore changes strategy after 64 bytes. It materializes the fallback interpretation as a complete parser snapshot—a shadow—and keeps it synchronized as tokens or forced bytes are committed.

short gap:
    remember checkpoint
    replay only if the primary path fails

long gap:
    materialize fallback parser snapshot
    advance it with committed input
    promote it if the primary path fails

The shadow is not another member of a general recognizer bundle. There is at most one synchronized fallback snapshot for the current greedy checkpoint. During a speculative trie walk, if the primary path fails, llguidance swaps to that snapshot and replays only the bytes added by the current trie branch. Deferred replay is therefore bounded by the 64-byte threshold plus the current token-trie path, rather than by the total length of the unresolved lexeme.

The newest accepting position is tried first. If the longer candidate reaches another accepting state, that becomes the active checkpoint and any materialized shadow for the older one is discarded. Older checkpoints can still reappear during nested recovery, but they do not compete with a later successful greedy match. This preserves llguidance’s combined-lexer maximal-munch semantics. It does not implement per-terminal maximal munch, and it does not preserve every possible lexical segmentation.

That distinction is tested directly. With:

start: A B | AB C
A: "a"
B: "b"
AB: "ab"
C: "c"

abc is accepted, but ab is still rejected at end of input: once AB = ab has arrived, the earlier A = a boundary has lost. The fallback only rescues an earlier accepting boundary when the attempted longer match fails before producing a later greedy match.

A pending checkpoint also means lexer history now matters. Two recognizers can have the same current DFA state but different saved boundaries. The branch therefore avoids mask-cache reuse keyed only by the current lexer state, declines the quick forced-byte answer, and disables tokenizer-slice subsumption while a fallback is pending. These are conservative choices; they keep the ordinary machinery untouched when no checkpoint is alive.

The feature is opt-in:

%llguidance {"greedy_lexeme_fallback": true}

With it disabled, llguidance uses its original state and hot path. With it enabled, the branch passes focused tests for listed, the contextual IPv6 example, f-string chunks, end of input, long and nested checkpoint chains, captures, cloning, validation, forcing, stop and suffix lexemes, token rollback, and repeated mask generation.

So the eventual answer was not to keep both recognizers running and kill one later. It was to keep the greedy recognizer running, remember the last place it could have stopped, and make returning there cheap enough to work inside llguidance’s speculative token-trie traversal.

STEM = [a-z]+(\.[a-z]+)*

QUALIFIED_VALUE ::= STEM COLON VALUE

COLON = :

FILE ::= STEM EXT

STEM = [a-z]+(\.[a-z]+)*
EXT  = .json | .txt

FILE ::= NAME (DOT NAME)* DOT EXT_NAME

NAME     = [a-z]+
DOT      = .
EXT_NAME = json | txt

accepted prefix:      list
ambiguous next byte:  e
following byte:       d
candidate:            listed

START ::= STEM COLON SUFFIX

STEM   = list | listen
COLON  = :
SUFFIX = ed

START  ::= STEM SUFFIX
STEM   ::= LIST | LISTEN

LIST    = list
LISTEN  = listen
SUFFIX  = ed

message = f"User {user.name} completed {task.name} in {duration} seconds with status {status}."

statement: "message = f\"" FCHUNK? ("{" expr "}" FCHUNK?)* "\"\n"
expr: NAME ("." NAME)*

FCHUNK: /(?:[^{}"\\]|\\.|\{\{|\}\})+/
NAME: /[A-Za-z_][A-Za-z0-9_]*/

statement: "message = f\"" piece* "\"\n"

?piece: TEXT | ESCAPE | "{{" | "}}" | "{" expr "}"
expr: NAME ("." NAME)*

TEXT: /[^{}"\\]+/
ESCAPE: /\\./
NAME: /[A-Za-z_][A-Za-z0-9_]*/

f<A<int>>();

>>();\n

?relational: shift (("<" | ">" | "<=" | ">" "=") shift)*
?shift: additive ((LSHIFT | ">" ">") additive)*
template_suffix: "<" template_argument_list ">"

f<A<A<A<A<A<A<A<int>>>>>>>>();

>>>>>>>>

list

liste

listen

listed