Raw BNF grammars instead of Guidance grammar DSL

[a3lem]

Context:

I'm slowly wrapping my head around guidance's way of working and evaluating whether it's worth the added layer of abstraction.

One thing that strikes me as odd in the examples – although this might just say something about my current level of understanding – is that CFG grammars are consistently defined using Guidance operators, whereas BNF notation already exists. By contrast, regex patterns are defined using the familiar regex DSL.

I suppose there are advantages to using a custom grammar DSL in terms of getting values from the generated output. I'm concerned, though, that I may at some point encounter a use case that is easier/only possible to define in BNF notation, which obviously factors into how I evaluate Guidance.

Questions:

1. In case I missed something, is it in fact already possible to provide BNF grammars directly?
2. If not, what was the reasoning for not including this?
3. Does the Guidance grammar DSL provably cover all possible expressions that BNF notation could define?
4. If not, would it be an idea to add direct support for BNF notation?

There's a good chance my questions simply reveal I haven't fully understood the power of Guidance yet. Anyway, thanks in advance for any extra info!

[riedgar-ms]

We are looking into EBNF support within guidance right now. Tag @hudson-ai who is experimenting with this.

As to 'why not the default?' the reason is that guidance tries to make the on-ramp for novice users as gentle as possible, and EBNF grammars are not well known outside of the field of computer science.

[hudson-ai]

@lemontheme if you're curious or want to play around with it a bit, here is my draft (really a draft -- the API and implementation are subject to change) of EBNF support for guidance, using lark as the EBNF parser:

https://github.com/hudson-ai/guidance/blob/ebnf/guidance/library/_ebnf.py

To add to Richard's comment on 'why not the default', I feel that guidance is doing a bit more than just constraining LLMs with CFGs. In my opinion, it's a pythonic interface that makes working with LLMs 'feel like programming' again, if that makes any sense. For loops, branches/if statements, function calling, etc. are all part of this interface.

That being said, I agree that some subsets of this functionality are most easily described with (E)BNF, hence this draft implementation. There are a few bumps in the road I want to smooth out before opening a PR, but I hope to get there soon :)

[hudson-ai]

See the tests here for an example of usage:

https://github.com/hudson-ai/guidance/blob/ebnf/tests/library/test_ebnf.py

[a3lem]

Interesting! Glad to see others have been thinking about this too.

Your take on what Guidance aims to be got me thinking. Since posting, I've come to realize it's likely that Guidance, with its operators and imperative approach, is strictly more expressive than CFGs (although I don't know enough formal language theory to actually prove this). In other words, everything that can be generated from a CFG can be expressed in Guidance.

Still, when all one cares about is capturing a string generated from a complex grammar, then BNF is a whole lot more compact than defining tens of Guidance functions. Presumably, these are the subsets of functionality you refer to?

I'm still figuring out how your implementation works. It's forcing me to dig into the internal API. My high-level understanding is that convert a Lark grammar (+1 for Lark by the way) into internal Guidance concepts, which are then evaluated as usual. (There's a few steps in between that I'm still wrapping my head around. The Guidance codebase takes some time to understand, it seems.) Anyway, is that more or less what's happening?

[hudson-ai]

I also suspect that guidance is strictly more expressive than CFGs (although I also haven't seen nor produced a proof of this yet).

Still, when all one cares about is capturing a string generated from a complex grammar, then BNF is a whole lot more compact than defining tens of Guidance functions. Presumably, these are the subsets of functionality you refer to?

Yes, exactly!

I want to make one more comment on this part of the discussion that is more-or-less orthogonal to the formal "expressiveness" of the grammar, and it is related to my use of the phrase "pythonic interface" above. Even if guidance were "only" as expressive as BNF, I believe that its design comes with several valuable affordances (both implicit and explicit) that will impact what kinds of systems people will be able to dream up and build.

Some examples to illustrate what I mean (heavily quoting a conversation I had with @notarealdeveloper earlier -- tagging you in case you are interested in weighing in):

1. You may choose to use one programming language over another not because it is more powerful (they are both probably Turing complete...) but because it makes it (cognitively) easier to implement the kind of functionality you are designing.
2. Choice of mathematical notation matters even when competing notations describe "the same thing". A good notation (where "good" is context dependent!) "tells" you what kinds of operations you can or should apply. See Terence Tao's excellent mathoverflow post about this.
3. Plenty of mathematical theorems are "equivalent" to each other (e.g. Bolzano-Weierstrass and the statement that "every countable commutative ring has a maximal ideal"), but they feel different. This "feeling different" goes beyond "vibes" and has real-world consequences. If "mathematical equivalence" and "cognitive equivalence" were the same, then nearly all mathematical theorems would be provable with zero work.

It's my hope that the language/interface that guidance provides is more suitable and approachable than BNF for programmers to design the kinds of grammars that will be truly useful to them when applying LLMs to real-world problems. The only way to get there is via community feedback though, so thank you so much for engaging here!

Anyway, back to your questions/comments about the implementation. Guidance essentially has two primitives: "select" and "join", where select is equivalent to the "or" (|) operator in EBNF and join is just concatenation/juxtaposition. To make a guidance grammar from an EBNF specification, I'm just taking advantage of this equivalence. So in other words, yes -- you hit the nail on the head about how this works.

I'll admit that my implementation is pretty opaque at the moment... I believe this is because of some subtleties around how guidance handles recursive calls of guidance-decorated functions as well as the difficulties that present themselves when programmatically generating code. I'm hoping to simplify the implementation a bit, but hopefully it should be usable without you having to understand all of the internals anyway 😄

Btw thanks for the +1 for Lark -- that's a valuable signal! Do you know if there are other competing or complimentary libraries that may be worth considering here?

[a3lem]

Thanks for introducing me to several new concepts! That's a fascinating way of looking at it. Things got philosophical there in the middle, but I'm here for it!

While some of Guidance's more advanced functionality has taken me a while to wrap my head around, I think it's a fact that, out of many LLM prompting libraries, Guidance offers the most direct route to just having an actionable 'conversation' with an LLM – 'actionable' in the sense that a minimum of new abstractions is needed to get output from one generation step, make a decision, and pass it to the next generation step.

I'm still on the fence about where the future is headed. I'd love to see a DSL that can be compiled to something that can be run hyper-efficiently in an LLM runtime. But then, tack on enough features to a DSL and soon enough it becomes Turing complete, at which point you might as well have just used an existing programming language – which can similarly be compiled for efficient execution, except without the extra step in the middle. =p

Your implementation isn't necessarily opaque, to be clear. It's the whole codebase. A question I find particularly hard to answer is Where does the generation call happen? – because something I find essential to check when reviewing any of the hundreds of emerging LLM prompting libraries is that the library is not modifying my prompts/messages. I'm still learning how everything fits together. (Something I'm looking to implement/add is a way to use a Guidance program both for prompting/inference (i.e. answer is unknown) and for generating training examples (answer is known, but the format should resemble what will be used at inference time).)

As for Lark, there are a few libraries like it, obviously. Once upon a time, I reviewed all of them, settling on Lark in the end. I can't remember why. I think I liked the notation flavor and the ability to import grammars; found the docs clear; the speed, adequate; oh, and that it didn't bring any extra dependencies.

[hudson-ai]

Things got philosophical there in the middle, but I'm here for it!

I tend to get a bit rambly at times, so it's nice to hear that it's appreciated 😆

Guidance offers the most direct route to just having an actionable 'conversation' with an LLM – 'actionable' in the sense that a minimum of new abstractions is needed to get output from one generation step, make a decision, and pass it to the next generation step.

❤️

I'd love to see a DSL that can be compiled to something that can be run hyper-efficiently in an LLM runtime. But then, tack on enough features to a DSL and soon enough it becomes Turing complete, at which point you might as well have just used an existing programming language – which can similarly be compiled for efficient execution, except without the extra step in the middle. =p

That is essentially the goal here! You write python, we turn that into something that can be used to 🤞 efficiently guide an LLM.

Where does the generation call happen?

Great question. Hopefully I can help address it a bit...

When you call a guidance function, nothing really happens. That's imprecise, but what I mean is that all that really goes on under the hood is that the python code inside the function is used to generate a grammar (sort of like a compilation step). Functions that require dynamic python control-flow are a little more complicated than that, but that's the general idea (this is the distinction between "stateless" and "stateful" grammars that you can find in the readme).

Adding strings and/or the grammars returned by guidance functions (and strings) together simply concatenates the strings/grammars. Still no LLM calls.

Generation only happens when one of these grammars is added to the right of a Model object. You can see this in the __add__ method on the Model class. Most of the actual work is being done in the _run_stateless method, which accepts one of these "compiled" grammars and runs the LLM forward on it. The implementation is a bit opaque, but hopefully just knowing where it happens provides some insight.

Your prompts should never really be "modified" by this library (beyond possibly some chat/role blocks, which I believe are more or less "opt-in"). Adding a string to an LLM is quite literally appending that string to the "prompt" used for further generation. Adding a grammar just runs the LLM forward on that grammar, furthermore appending the output of that generation to the downstream "prompt". I'm putting quotes on "prompt" because I think a nice insight of this library is that there really isn't a distinction between prompts and deterministic generation constraints.

[ibehnam]

Just as as follow-up, I wanted to see if there's been any update on this? It's so cool to be able to use (E)BNF grammars directly in guidance. @hudson-ai

[hudson-ai]

Hi @ibehnam sorry for the long delay! I have an open PR on this at the moment. DEFINITELY not going to be a stable/public part of the guidance API for a little while, but if you want to play around with it, I would love to get some feedback. See the PR here: #1017

See guidance/library/_rfc3986.py for an example usage