How to use lazy grammars?

[leon-herbrik]

Could you give me a hint at how to use this feature?
I want the model to think freely, but after reaching "</think>", it should only output valid JSON.
My grammar looks like this:

root ::= thought any endthought "Final JSON:\n" json

thought ::= "<think>"
endthought ::= "</think>"
any ::= .*

Where json is a valid json grammar (I left it out for space reasons).
I'm sending this grammar via JSON to the server and use grammar_lazy: true, grammar_triggers: [{word: "</think>", at_start: false}]. However I get the error 'terminate called after throwing an instance of 'std::runtime_error'
what(): Unexpected empty grammar stack after accepting piece:
Aborted (core dumped)'
The same happens when at_start is set to true.
I'm using DeepSeek-R1-Distill-Qwen-14B-Q4_K_M.gguf.

Any help would be appreciated.

[leon-herbrik]

@ochafik would you be able to help here? 🙏

[ochafik]

Hi @leon-herbrik, the grammar gets anything from the trigger, please try:

root ::= "</think>" "Final JSON:\n" json

(alsoo, .* will match anything eagerly and defeat the rest of the grammar, this is what lazy grammers are working around :-))

[leon-herbrik]

Thanks a lot @ochafik, that worked :)

I suppose currently there is no way in a single request to first sample a "<think>", then sample unconstrained until "</think>" and then sample only valid JSON? So, switching between constrained and unconstrained sampling?

[ochafik]

No there isn’t any anti-trigger unfortunately. I wish we could add some non-backtracking reluctant match .* but both semantics and implementations are nightmares)

I think we may want to support thinking + json output natively, do you know what deepseek’s api behaviour is when setting a JSON schema in response_format?

(My understanding re streaming is they don’t extract reasoning_content as deltas, which seems a bit unfortunate)

[leon-herbrik]

I see. I'll try and wrap my head around the technical details of grammar based sampling to understand why these implemenations are a nightmare.

From what I can see on the website, they don't extract the reasoning_content, as you said. However I don't currently have access to the API to test it.

[ochafik]

I see. I'll try and wrap my head around the technical details of grammar based sampling to understand why these implemenations are a nightmare.

Unlike a recursive descent backtracking parser, the grammar sampler keeps the entire set of possibly valid parsing stacks (almost like the superposed states of a quantum computer haha), so as to be able to say which of the next possible tokens to be sampled are valid (no backtracking, we don't "ungenerate" any tokens). The format of these stacks is kind of a stack of continuation pointers, pointing to the next literal terminal.

On the semantic front, you either need to express what constitutes a repetition breaker / untrigger (what is allowing to break out of your hyper-reluctant .*??) or pick a possibly dubious rule (e.g. unbreak upon the next matching literal (e.g. .*?? "foo" "bar" would break out of the .*?? upon foo). We couldn't keep the same notation .*? as reluctant matches in regexes as the semantics is different (reluctant matches will still backtrack, but we won't)

And on the implementation front, you'd need to keep more metadata in the stacks (are we in a reluctant context, where do we break out to, which other parallel stacks do we cancel out, etc), which is very tricky as performance is in the essence (current grammar sampling has performance issues, I'm toying with a few improvements).