Constraining LLM output using a Lark grammar

[nchammas]

I am just starting to experiment with LLMs for the first time and need to constrain the model's output using a Lark grammar.

I noticed that @erezsh recently starred parserLLM, but that project seems unmaintained.

I then stumbled on llama.cpp's GBNF, which seems like an actively supported and developed method for accomplishing my goal. However, I assume GBNF is not exactly the same thing as Lark's flavor of EBNF. Would it be worthwhile to add some kind of export method that converts a Lark grammar into GBNF?

Finally, while looking through the Lark README I noticed Outlines, which has its own support for generating structured output, this time built directly using Lark. This seems like the ideal solution.

Should I just use Outlines? Asking here in case I am missing something obvious, as it is my first rodeo with LLMs.

[erezsh]

Hi @nchammas !

Personally I didn't use Outlines yet, but I've heard good things, so it's probably a good place to start.

[nchammas]

Just a general FYI: Looks like supporting indentation-significant grammars is particularly tricky for LLMs.

[erezsh]

I spent some time thinking about how to generate indentation a few months ago. I don't know how helpful it would be, but I'll put it here:

The gist of the idea is to have multiple lexers, one for each indentation level, and use parser callbacks to move between these lexers. (similar to how the contextual-lexer in Lark moves between states)
That shifts the handling of indentation from column-counting into regular lexing (i.e. a state-machine), with only having to move between states.
While that might suggest a huge amount of lexers, in practice most real-world code has less than 16 levels of indentation. Furthermore, those lexers would all be identical to each other, except for the regexps of the INDENT and DEDENT terminals. For indentation, changing between lexers actually only requires changing the values of these 2 terminals.

(the explanation assumes it uses Lark, but maybe it can apply to other parsers as well)

[nchammas]

Interesting! This comment would be better appreciated by @mmoskal (the author of the LLGuidance PR I linked to just above).

(Apologies to Michał if the ping is not appropriate. Just thought you might find this interesting.)

[mmoskal]

Thanks @nchammas for bringing this up!

The lexer in LLGuidance uses a custom derivative-based regex library where lexer automaton states are built dynamically from the set of currently allowed lexemes (terminals) (derived from Earley parser state). Thus, depending on the current indent level I can indicate that say lexeme "\n " is NEWLINE, "\n " is INDENT, and "\n" is DEDENT.

The problem is that multiple DEDENT lexemes can be generated from a single byte of input and I'm generally not set up for that (the price you pay for hyper-optimizing everything).

As for conversions, we have https://github.com/guidance-ai/llguidance/blob/main/python/llguidance/gbnf_to_lark.py and there is an inverse in vLLM https://github.com/vllm-project/vllm/blob/main/vllm/v1/structured_output/utils.py#L105

Note that gBNF will def. not handle indent/dedent (they don't even have %ignore; or for that matter a concept of a separate lexer). The Lark syntax is more expressive.

[nchammas]

Thank you for that explanation @mmoskal.

Just wanted to add another note here for @erezsh about yet another project I found in this space: SynCode.

It looks like they too use Lark's syntax to support constraining LLM generation to an EBNF grammar, even claiming to handle indentation-sensitive output like Python well. They support LALR(1) and LR(1) grammars.