llguidance HATES This One Weird Grammar (Debugger-first)

Consider this grammar:

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

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

There are two obvious strings in the language:

list + ed     = listed
listen + ed   = listened

Lark accepts both. llguidance accepts listened too. But give it the single model token listed and something odd happens:

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

This is not the usual model-token-versus-grammar-terminal problem. llguidance is perfectly capable of accepting one model token that contains several grammar lexemes. The problem is where it decides the first lexeme ends.

During mask generation, llguidance is not handed a complete candidate string and asked to lex it. It walks a trie of model-vocabulary byte strings. Prefixes shared by many tokens share recognizer work. As each byte is pushed, the lexer and parser have to remain in a state that could still lead to some valid continuation.

That is normally a very good fit for constrained decoding. It also means there is no single known “rest of the input” that a conventional lexer can inspect before choosing a boundary. At list, the trie may contain branches for list, listed, listener, listening, and thousands of unrelated longer tokens. The recognizer has to decide what state to carry into each branch incrementally.

The easiest way to see it is one byte at a time.

The important moment is after list.

At that point STEM has matched. If the input were to end there, list would be a perfectly good lexeme. But the lexer cannot commit to it yet, because the same terminal has a longer alternative: listen.

So when the next byte is e, the current STEM does not die. It becomes liste: not a complete match, but still a possible prefix of listen.

list      accepting
liste     live, non-accepting

Then comes d.

listed is not a prefix of either list or listen, so the attempted longer STEM finally dies. Unfortunately, the failure arrived too late. The correct interpretation was:

list | ed

The e should have been the first byte of SUFFIX. By the time the later d proves that, the accepting boundary after list is already behind us.

The longer string does not have this problem. For listened, continuing after list was exactly the right decision:

listen | ed

So this tiny grammar manages to make listened easy and listed impossible.

It is worth separating two questions here. First: is list currently a valid STEM? Yes. Second: do we yet know that the greedy STEM ends there? No. llguidance keeps answering the second question by trying to continue. The problem is that it does not retain enough of the answer to the first question when continuation later turns out to have been a mistake.

An ordinary maximal-munch lexer can scan past the final boundary too. The difference is that it normally remembers its last accepting position. It is free to explore liste, because if that path dies it still has list in its pocket. Here, the live-but-non-accepting liste state replaces the useful accepting state rather than merely extending beyond it.

The grammar-side fix

The simplest repair is to move the choice out of the lexer and into the parser:

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

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

Lowercase stem is now a parser rule rather than one greedy terminal. And now:

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

BEHOLD.

This is usually the right response if a custom grammar runs into the problem: put the ambiguous boundary somewhere the parser can see it.

Why you probably have not noticed

Most constrained generation is JSON, and JSON is unusually friendly here.

Strings have an explicit closing quote. true, false, and null end before punctuation, whitespace, or end of input. Those bytes cannot also continue the literal that came before them. JSON numbers have slightly stranger internal paths—1 can become 1e, which is live but incomplete—but the surrounding grammar normally prevents that continuation byte from simultaneously beginning the next lexeme.

Our grammar has exactly the dangerous shape. After list, the byte e has two jobs available to it:

continue STEM:   list + e = liste...
begin SUFFIX:           e + d = ed

llguidance chooses the first interpretation while it remains possible. The second only becomes obviously correct later.

This is why simply saying “greedy lexing” is not quite enough. Greedy lexers routinely pursue longer matches and then fall back to the last one that worked. The unusual part is combining greediness with an incremental recognizer that can move from an accepting state into a non-accepting live state without retaining the accepting boundary for later recovery.

It does not have to work this way

This behaviour is not fundamental to constrained decoding, or even to llguidance’s overall architecture. A lexer can remember an earlier accepting position while still trying the longer greedy match. If the longer attempt eventually dies, it can return to the saved boundary and reinterpret the bytes after it in the parser context that follows.

I implemented an opt-in version of that idea in redesign/greedy-lexeme-fallback-integrated-v3. The ordinary path stays greedy. The extra machinery matters only while there is an earlier accepting boundary worth returning to.

But none of that is necessary to understand the failure. The debugger contains the whole story:

list      matched
liste     still possible
listed    impossible

The lexer learns that it should have stopped at list only after it has already forgotten how to stop there.