10 ms·

Llama: Add grammar-based sampling

417 points by davepeck 3y ago

spion 3y ago
Specifically for multi-choice string enums (essentially dropdowns), I wonder if this would work better if the full (joint/product) probability given the logits is considered when picking the final choice, rather than using a greedy algorithm. This will favor the right choice, as opposed to e.g. one of the choices that contain the most common start token - if a start token are shared among many items in the list. Of course the probability needs to be adjusted once a subset of the logits goes to zero so it actually makes sense...
version_five 3y ago
I'm interested in this and I'm going to try incorporating it into something I'm doing. That said, I feel like this could be one of those Bitter Lesson situations where it's not the most effective approach in anything but the very short term: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html
- woah 3y ago
  Not an expert at all, but I believe that OpenAI uses this in some of their GPT apis which are meant for programmatic use. I've seen it theorized that offloading the rote grammar stuff to a simple process that is meant for it lets the LLM use it's "brainpower" on the complicated stuff more effectively. No idea if this is true.
  - TechBro8615 3y ago
    It makes sense to my uninformed intuition, which is that a strict grammar reduces the search space for the token generation and so the AI can eliminate possibilities that would otherwise be ambiguous.
- Der_Einzige 3y ago
  It may be a stop-gap, but its an important one as it is not obvious that LLMs in the next few years will "organically" solve their issues with generating text with constraints.
painted-now 3y ago
Can anyone recommend some paper or overview on how "sampling" / "decoding" is done in the e2e neural network age? I know how decoding was done for machine translation and speech recognition back in the HMM times (i.e. https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm and https://en.wikipedia.org/wiki/Beam_search https://en.wikipedia.org/wiki/Beam_search). These days I get the impression people just do "greedy" - but I don't really know. Any recommendations for info on that topic? Edit: Forgot Viterbi
- spion 3y ago
  Its greedy and random :) Instead of a paper, I would recommend the algorithms of most LMM implementations (rwkv.cpp has a relatively clean implementation in python https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/sampling.py https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...)
  - painted-now 3y ago
    I guess I need to sit down and study this stuff in more detail, but do I understand correctly that the code you shared makes the decisions for each position independently? I am just astonished that this produces any coherent output. Also it is not clear to me how the length of the output sequence is determined.
    - pizza 3y ago
      Once the stop token is likeliest
- janalsncm 3y ago
  Just reading through the GPT4 documentation it doesn’t seem like there’s a ton of difference with what you’ve mentioned. https://platform.openai.com/docs/api-reference/completions/create https://platform.openai.com/docs/api-reference/completions/c... Of course we now know that GPT4 is a Mixture of Experts, so under the hood they’re parallelizing computation. They also include a way to modify the logits with presence/frequency penalty terms.
moffkalast 3y ago
Ah finally, this was discussed a lot and is well overdue. Remains to be seen how well the models will adapt to this new constraint, though the demo seems promising.
- ec109685 3y ago
  Isn’t this approach forcing the LLM to adapt? E.g. it is throwing tokens away that don’t match the grammar.
  - moffkalast 3y ago
    Well the grammar will be correct as enforced by the sampler, but the content it's filled with could be anything at all. Sort of how when you change the prompt template the output can be garbage for some models. I haven't tried it out yet myself, but apparently even OpenAI's implementation of this exact principle on their API still has function hallucination issues even with GPT 4.
meepmorp 3y ago
Does anyone know Japanese well enough to comment on the output from the Japanese example?
- vore 3y ago
  It is vaguely Japanese, I guess, but pretty incoherent: 1. What is the purpose? 2. Remember the customer 3. About the customer [incomplete sentence?]
- brucethemoose2 3y ago
  Note that there are actual Japanese llama finetunes that would be much more coherent with these grammar constraints
1024core 3y ago
Can someone ELI5 what's going on here? I'm reasonably familiar with LLMs, but I can't quite grok what Georgi is doing here and why it's so exciting for some.
- simonw 3y ago
  See my comment here https://news.ycombinator.com/item?id=36820884 https://news.ycombinator.com/item?id=36820884
- modeless 3y ago
  If you ask an LLM to generate JSON or another language that has a grammar, it will sometimes produce invalid syntax. This pull request constrains the LLM so that it can only output valid syntax according to whatever grammar you supply. It's a modification to the sampling procedure. What is the sampling procedure? Well, the way an LLM generates text is one token (short sequence of characters) at a time. First the giant neural net assigns a probability to every possible token (this is the hard part). Then a sampling procedure uses the probabilities to pick one of the tokens, and the process repeats. The sampling procedure is not a neural net and can be modified in many different ways. You might think that the sampling procedure should always simply pick the token with the highest probability (greedy sampling). You can do that, but it's usually better to pick at random weighted by the probabilities. This gives more diversity and is less likely to get stuck in loops. But this means that literally any token with nonzero probability might get picked, so you can see how this might lead to invalid JSON being generated sometimes. This pull request zeros out the probabilities of all the tokens that wouldn't be valid according to your grammar, so they can't be picked. BTW there are lots of other interesting modifications to the sampling process you could consider. For example, maybe you can see that in the process of sampling tokens one after the other you might paint yourself into a corner and end up with no good options to choose from. So maybe it makes sense to allow backtracking. In fact, maybe at each sampling step we can consider multiple options, making a tree of possible outputs, and at the end we can pick the path through the tree with the highest overall probability. Of course we can't consider every option; it would be a complete tree with a branching factor of the number of possible tokens, which would grow exponentially. Let's prune the tree at each step and only consider the top, say, five paths we've seen so far. This is called "beam search". It's not normally used for LLMs because the neural net that generates the probabilities is very expensive to run and multiplying that cost by a factor of e.g. five is unpalatable. But it can be done, and produces somewhat better results. You could also consider using MCTS like chess engines do.
simonw 3y ago
Here's my understanding of how this works (please someone correct me if I'm getting this wrong). Language models emit tokens one at a time, starting with the prompt that you give them. If you have a conversation with an LLM, effectively you can think of that as you giving it a sequence of tokens, then it generates some, then you generate more and so-on. This grammar trick effectively takes advantage of this by giving you much more finely grained control over the tokens. So you can do things like this: Give me the address of the White House as JSON: {"street": " Then the LLM can return: 1600 Pennsylvania Ave NW" The moment you see that closing double quote, you take over again and inject: ", "City": " It fills in: Washington, DC" And so on. But because this is all based on a grammar, you can do way more with it than just JSON. I saw a brilliant suggestion relating to this on Twitter a while ago: > @OpenAI should add an API argument allowing passing up a deterministic context free grammar. > [...] > While I think DCFL is what you want here in the short term, the really best thing is passing up a small WASM binary that simply is the sampler. > Allow a user to pass up a few KB of WASM binary and give it a few megabytes of RAM to run. Would enable next level LLM superpowers. https://twitter.com/grantslatton/status/1637692033115762688 https://twitter.com/grantslatton/status/1637692033115762688
- anothernewdude 3y ago
  So does this mean I can detect "Sorry" at the start of a response and prevent it?
- pshc 3y ago
  I don't think this is correct; previously you could already control output by reading tokens one at a time from the LLM until you hit a stop character. My take from the grammar-based sampling PR is that you ask llama.cpp to constrain the next output token, to a restricted set of possible tokens, using the grammar.
  - simonw 3y ago
    Right, which is the same idea - it's just that the code in llama.cpp is running your grammar as part of its token generation decisions as opposed to pausing and waiting for your other code to pick the next token. (I'm trying for a very high level explanation here.)
bavarianbob 3y ago
Could someone help me with context? I'm OOTL and don't understand what is going on here.
- brucethemoose2 3y ago
  This can constrain an LLM's output to an arbitrary grammar/format as it is generated, rather than asking the model to output a specific format and hoping it outputs something valid.
  - Tostino 3y ago
    This is important for "smaller" models, because you don't have to waste some of the potential "intelligence" (parameter space) on training it how to generate valid JSON or YAML or anything like that.
    - brucethemoose2 3y ago
      You still do... The model has to know JSON and YAML, its just more reliable when the generation is enforced by grammar
      - Tostino 3y ago
        Right, but there is a big difference between ”generally knows what JSON looks like and gets it right most of the time" and "generates perfect JSON every time".
Der_Einzige 3y ago
I am in love with this, I tried my hand at building a Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Generation-Studio https://github.com/Hellisotherpeople/Constrained-Text-Genera...), and got published at COLING 2022 for my paper on it (https://paperswithcode.com/paper/most-language-models-can-be-poets-too-an-ai-1 https://paperswithcode.com/paper/most-language-models-can-be...), but I always knew that something like this or the related idea enumerated in this paper: https://arxiv.org/abs/2306.03081 https://arxiv.org/abs/2306.03081 was the way to go. I will have to think about how I can build grammars that force things like syllable counts or syntactic rules. Current LLMs do very poorly on those kinds of tasks due to the tokenization schemes...
- sp332 3y ago
  I was surprised, but Nous Hermes does a half decent job at writing haikus.
svc0 3y ago
I think it should be noted that this enforces grammatical constraints on the model's generated text, but it doesn't do anything to properly align the content. This would be useful if you needed to ensure a server delivered well-formatted JSON, but it I suspect it wont solve a lot of alignment issues with current language generation. For example current iterations of Llama and GPT often do not label markdown code-blocks correctly. Using grammar-based sampling, you could enforce that it labels code blocks but you couldn't enforce correct labeling since this is context-dependent. You also couldn't invent a novel domain-specific language without aligning against that language and expect good output.
- brucethemoose2 3y ago
  But since its llama, some examples could be trained into a lora. I can imagine a system where, for instance, a markdown lora and a markdown grammar file can be hotswapped in and out.
- newhouseb 3y ago
  Also important to call out that anytime you have a freeform string it's pretty much an open invitation for the LLM to go completely haywire and run off into all sorts of weird tangents. So these methods are best used with other heuristics to bias sampling once you get to free-form text territory (i.e. a repetition penalty etc)
ilaksh 3y ago
Has anyone tested FreeWilly2 (the new Llama2 fine-tune released today by Stable Foundation) on code generation?
brucethemoose2 3y ago
This grammar "library" was cited as an example of what the format could look like:. https://github.com/antlr/grammars-v4 https://github.com/antlr/grammars-v4 There is everything from assembly and C++ to glsl and scripting languages, arithmetic, games, and other weird formats like freedesktop shortcuts, llvm ir or verilog.
- ttul 3y ago
  A convenience feature in any inference API would be to specify a shortcut to a standardized grammar such as HTML, JSON, Python, etc. It is frankly strange to me that OpenAI have not already done this, considering the obvious effort they undertook to fine-tune the Code Interpreter model.
- RossBencina 3y ago
  It would be awesome if they supported ANLTR4 grammar syntax. Such a great tool.
Icko 3y ago
How is this different from Guidance and LMQL?
- jameshart 3y ago
  Looks like a tool Guidance could use to make better use of the sampling from a local llama model.
QuantumG 3y ago
So, umm, if you want to walk BNF and emit likely tokens you can do that without any "machine learning" or whatever you want to call it. So what is being added here? Training to tie the prompt to the output?
- sp332 3y ago
  The difference is in the word “likely”. You can put unstructured data in the prompt and get structured data out. You could put in the beginning of a list and ask for a continuation.
  - QuantumG 3y ago
    I get that
sandkoan 3y ago
Also using a similar method: https://github.com/automorphic-ai/trex https://github.com/automorphic-ai/trex Playground: https://automorphic.ai/playground https://automorphic.ai/playground
burke 3y ago
I implemented this for PyTorch too at https://github.com/Shopify/torch-grammar https://github.com/Shopify/torch-grammar. I have a hacked version of text-generation-inference that uses it—happy to share that if it’s useful to anyone.
- Scene_Cast2 3y ago
  Yes, please share. I've been meaning to play around with dumping the token probability vectors inside one of the LLM UIs. Having a diff starting point would help a bunch.
  - burke 3y ago
    Sure, here it is. It's extremely rough but it works as a starting point: https://gist.github.com/burke/6d035758f7492612e2ad86bb7de2d5fb https://gist.github.com/burke/6d035758f7492612e2ad86bb7de2d5...
ahupp 3y ago
Interesting that the second commentor is Tobias Lütke, CEO of Shopify.
- 0xDEF 3y ago
  Also interesting how Shopify is making a lot of moves in this space using both the OpenAI APIs and using self-hosted models.
lachlan_gray 3y ago
Something I’m wondering lately is if you are generating tokens fast enough, is restricting the logits actually worth it computationally? If tokens are cheap enough it might be more efficient to validate/discard them as they come rather than place constraints on how they come out. I don’t know how this one works, but the sampling or renormalizing scheme would cost something too right?
- mmoskal 3y ago
  There is at least 6 orders of magnitude difference in computation cost of computing a token (pass through a multi-B model) and doing a single step of a program. Even if your validation is really naive, it's hard to beat 6 orders of magnitude. So no, you're not generating tokens fast enough.
karmasimida 3y ago
This is great and all. But LLM's are usually very good at following grammars. I rarely see LLM generating code that is OOD. Ofc, this is only true for popular language (JSON/Python/Java, etc), I can see how this is handy for more niche and in house DSL. You still need quite a lot of prompt engineering to get desired outputs, this just add another layer of output verification IMO. But does it really save much as comparing to get the output then parse and reject the output that doesn't follow the grammar? Might be debateable. But great work regardless.
- mpalmer 3y ago
  > this just add another layer of output verification IMO. It's not verifying the output after it's done, it's constraining the output as it's generated. > But does it really save much as comparing to get the output then parse and reject the output that doesn't follow the grammar? Might be debateable. I don't think it's debatable at all. Forcing the model to conform to a grammar during generation means there is never a need to discard and regenerate because it got the grammar wrong. Think of the compute involved in generating the whole output and then re-generating if it's non-conformant. There is no comparison.
  - karmasimida 3y ago
    > It's not verifying the output after it's done, it's constraining the output as it's generated. It is verifying, by filtering only tokens that allowed by the grammar. I think we are talking about the same thing.

417 points by davepeck 3y ago

Specifically for multi-choice string enums (essentially dropdowns), I wonder if this would work better if the full (joint/product) probability given the logits is considered when picking the final choice, rather than using a greedy algorithm. This will favor the right choice, as opposed to e.g. one of the choices that contain the most common start token - if a start token are shared among many items in the list. Of course the probability needs to be adjusted once a subset of the logits goes to zero so it actually makes sense...

version_five 3y ago

I'm interested in this and I'm going to try incorporating it into something I'm doing. That said, I feel like this could be one of those Bitter Lesson situations where it's not the most effective approach in anything but the very short term: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html

woah 3y ago
Not an expert at all, but I believe that OpenAI uses this in some of their GPT apis which are meant for programmatic use. I've seen it theorized that offloading the rote grammar stuff to a simple process that is meant for it lets the LLM use it's "brainpower" on the complicated stuff more effectively. No idea if this is true.
- TechBro8615 3y ago
  It makes sense to my uninformed intuition, which is that a strict grammar reduces the search space for the token generation and so the AI can eliminate possibilities that would otherwise be ambiguous.
Der_Einzige 3y ago
It may be a stop-gap, but its an important one as it is not obvious that LLMs in the next few years will "organically" solve their issues with generating text with constraints.

painted-now 3y ago

Can anyone recommend some paper or overview on how "sampling" / "decoding" is done in the e2e neural network age? I know how decoding was done for machine translation and speech recognition back in the HMM times (i.e. https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm and https://en.wikipedia.org/wiki/Beam_search https://en.wikipedia.org/wiki/Beam_search). These days I get the impression people just do "greedy" - but I don't really know. Any recommendations for info on that topic? Edit: Forgot Viterbi

spion 3y ago
Its greedy and random :) Instead of a paper, I would recommend the algorithms of most LMM implementations (rwkv.cpp has a relatively clean implementation in python https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/sampling.py https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...)
- painted-now 3y ago
  I guess I need to sit down and study this stuff in more detail, but do I understand correctly that the code you shared makes the decisions for each position independently? I am just astonished that this produces any coherent output. Also it is not clear to me how the length of the output sequence is determined.
  - pizza 3y ago
    Once the stop token is likeliest
janalsncm 3y ago
Just reading through the GPT4 documentation it doesn’t seem like there’s a ton of difference with what you’ve mentioned. https://platform.openai.com/docs/api-reference/completions/create https://platform.openai.com/docs/api-reference/completions/c... Of course we now know that GPT4 is a Mixture of Experts, so under the hood they’re parallelizing computation. They also include a way to modify the logits with presence/frequency penalty terms.

moffkalast 3y ago

Ah finally, this was discussed a lot and is well overdue. Remains to be seen how well the models will adapt to this new constraint, though the demo seems promising.

ec109685 3y ago
Isn’t this approach forcing the LLM to adapt? E.g. it is throwing tokens away that don’t match the grammar.
- moffkalast 3y ago
  Well the grammar will be correct as enforced by the sampler, but the content it's filled with could be anything at all. Sort of how when you change the prompt template the output can be garbage for some models. I haven't tried it out yet myself, but apparently even OpenAI's implementation of this exact principle on their API still has function hallucination issues even with GPT 4.

meepmorp 3y ago

Does anyone know Japanese well enough to comment on the output from the Japanese example?

vore 3y ago
It is vaguely Japanese, I guess, but pretty incoherent: 1. What is the purpose? 2. Remember the customer 3. About the customer [incomplete sentence?]
brucethemoose2 3y ago
Note that there are actual Japanese llama finetunes that would be much more coherent with these grammar constraints

1024core 3y ago

Can someone ELI5 what's going on here? I'm reasonably familiar with LLMs, but I can't quite grok what Georgi is doing here and why it's so exciting for some.

simonw 3y ago
See my comment here https://news.ycombinator.com/item?id=36820884 https://news.ycombinator.com/item?id=36820884
modeless 3y ago
If you ask an LLM to generate JSON or another language that has a grammar, it will sometimes produce invalid syntax. This pull request constrains the LLM so that it can only output valid syntax according to whatever grammar you supply. It's a modification to the sampling procedure. What is the sampling procedure? Well, the way an LLM generates text is one token (short sequence of characters) at a time. First the giant neural net assigns a probability to every possible token (this is the hard part). Then a sampling procedure uses the probabilities to pick one of the tokens, and the process repeats. The sampling procedure is not a neural net and can be modified in many different ways. You might think that the sampling procedure should always simply pick the token with the highest probability (greedy sampling). You can do that, but it's usually better to pick at random weighted by the probabilities. This gives more diversity and is less likely to get stuck in loops. But this means that literally any token with nonzero probability might get picked, so you can see how this might lead to invalid JSON being generated sometimes. This pull request zeros out the probabilities of all the tokens that wouldn't be valid according to your grammar, so they can't be picked. BTW there are lots of other interesting modifications to the sampling process you could consider. For example, maybe you can see that in the process of sampling tokens one after the other you might paint yourself into a corner and end up with no good options to choose from. So maybe it makes sense to allow backtracking. In fact, maybe at each sampling step we can consider multiple options, making a tree of possible outputs, and at the end we can pick the path through the tree with the highest overall probability. Of course we can't consider every option; it would be a complete tree with a branching factor of the number of possible tokens, which would grow exponentially. Let's prune the tree at each step and only consider the top, say, five paths we've seen so far. This is called "beam search". It's not normally used for LLMs because the neural net that generates the probabilities is very expensive to run and multiplying that cost by a factor of e.g. five is unpalatable. But it can be done, and produces somewhat better results. You could also consider using MCTS like chess engines do.

simonw 3y ago

Here's my understanding of how this works (please someone correct me if I'm getting this wrong). Language models emit tokens one at a time, starting with the prompt that you give them. If you have a conversation with an LLM, effectively you can think of that as you giving it a sequence of tokens, then it generates some, then you generate more and so-on. This grammar trick effectively takes advantage of this by giving you much more finely grained control over the tokens. So you can do things like this: Give me the address of the White House as JSON: {"street": " Then the LLM can return: 1600 Pennsylvania Ave NW" The moment you see that closing double quote, you take over again and inject: ", "City": " It fills in: Washington, DC" And so on. But because this is all based on a grammar, you can do way more with it than just JSON. I saw a brilliant suggestion relating to this on Twitter a while ago: > @OpenAI should add an API argument allowing passing up a deterministic context free grammar. > [...] > While I think DCFL is what you want here in the short term, the really best thing is passing up a small WASM binary that simply is the sampler. > Allow a user to pass up a few KB of WASM binary and give it a few megabytes of RAM to run. Would enable next level LLM superpowers. https://twitter.com/grantslatton/status/1637692033115762688 https://twitter.com/grantslatton/status/1637692033115762688

anothernewdude 3y ago
So does this mean I can detect "Sorry" at the start of a response and prevent it?
pshc 3y ago
I don't think this is correct; previously you could already control output by reading tokens one at a time from the LLM until you hit a stop character. My take from the grammar-based sampling PR is that you ask llama.cpp to constrain the next output token, to a restricted set of possible tokens, using the grammar.
- simonw 3y ago
  Right, which is the same idea - it's just that the code in llama.cpp is running your grammar as part of its token generation decisions as opposed to pausing and waiting for your other code to pick the next token. (I'm trying for a very high level explanation here.)

bavarianbob 3y ago

Could someone help me with context? I'm OOTL and don't understand what is going on here.

brucethemoose2 3y ago
This can constrain an LLM's output to an arbitrary grammar/format as it is generated, rather than asking the model to output a specific format and hoping it outputs something valid.
- Tostino 3y ago
  This is important for "smaller" models, because you don't have to waste some of the potential "intelligence" (parameter space) on training it how to generate valid JSON or YAML or anything like that.
  - brucethemoose2 3y ago
    You still do... The model has to know JSON and YAML, its just more reliable when the generation is enforced by grammar
    - Tostino 3y ago
      Right, but there is a big difference between ”generally knows what JSON looks like and gets it right most of the time" and "generates perfect JSON every time".

Der_Einzige 3y ago

I am in love with this, I tried my hand at building a Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Generation-Studio https://github.com/Hellisotherpeople/Constrained-Text-Genera...), and got published at COLING 2022 for my paper on it (https://paperswithcode.com/paper/most-language-models-can-be-poets-too-an-ai-1 https://paperswithcode.com/paper/most-language-models-can-be...), but I always knew that something like this or the related idea enumerated in this paper: https://arxiv.org/abs/2306.03081 https://arxiv.org/abs/2306.03081 was the way to go. I will have to think about how I can build grammars that force things like syllable counts or syntactic rules. Current LLMs do very poorly on those kinds of tasks due to the tokenization schemes...

sp332 3y ago
I was surprised, but Nous Hermes does a half decent job at writing haikus.

svc0 3y ago

I think it should be noted that this enforces grammatical constraints on the model's generated text, but it doesn't do anything to properly align the content. This would be useful if you needed to ensure a server delivered well-formatted JSON, but it I suspect it wont solve a lot of alignment issues with current language generation. For example current iterations of Llama and GPT often do not label markdown code-blocks correctly. Using grammar-based sampling, you could enforce that it labels code blocks but you couldn't enforce correct labeling since this is context-dependent. You also couldn't invent a novel domain-specific language without aligning against that language and expect good output.

brucethemoose2 3y ago
But since its llama, some examples could be trained into a lora. I can imagine a system where, for instance, a markdown lora and a markdown grammar file can be hotswapped in and out.
newhouseb 3y ago
Also important to call out that anytime you have a freeform string it's pretty much an open invitation for the LLM to go completely haywire and run off into all sorts of weird tangents. So these methods are best used with other heuristics to bias sampling once you get to free-form text territory (i.e. a repetition penalty etc)

ilaksh 3y ago

Has anyone tested FreeWilly2 (the new Llama2 fine-tune released today by Stable Foundation) on code generation?

brucethemoose2 3y ago

This grammar "library" was cited as an example of what the format could look like:. https://github.com/antlr/grammars-v4 https://github.com/antlr/grammars-v4 There is everything from assembly and C++ to glsl and scripting languages, arithmetic, games, and other weird formats like freedesktop shortcuts, llvm ir or verilog.

ttul 3y ago
A convenience feature in any inference API would be to specify a shortcut to a standardized grammar such as HTML, JSON, Python, etc. It is frankly strange to me that OpenAI have not already done this, considering the obvious effort they undertook to fine-tune the Code Interpreter model.
RossBencina 3y ago
It would be awesome if they supported ANLTR4 grammar syntax. Such a great tool.

Icko 3y ago

How is this different from Guidance and LMQL?

jameshart 3y ago
Looks like a tool Guidance could use to make better use of the sampling from a local llama model.

QuantumG 3y ago

So, umm, if you want to walk BNF and emit likely tokens you can do that without any "machine learning" or whatever you want to call it. So what is being added here? Training to tie the prompt to the output?

sp332 3y ago
The difference is in the word “likely”. You can put unstructured data in the prompt and get structured data out. You could put in the beginning of a list and ask for a continuation.
- QuantumG 3y ago
  I get that

sandkoan 3y ago

Also using a similar method: https://github.com/automorphic-ai/trex https://github.com/automorphic-ai/trex Playground: https://automorphic.ai/playground https://automorphic.ai/playground

burke 3y ago

I implemented this for PyTorch too at https://github.com/Shopify/torch-grammar https://github.com/Shopify/torch-grammar. I have a hacked version of text-generation-inference that uses it—happy to share that if it’s useful to anyone.

Scene_Cast2 3y ago
Yes, please share. I've been meaning to play around with dumping the token probability vectors inside one of the LLM UIs. Having a diff starting point would help a bunch.
- burke 3y ago
  Sure, here it is. It's extremely rough but it works as a starting point: https://gist.github.com/burke/6d035758f7492612e2ad86bb7de2d5fb https://gist.github.com/burke/6d035758f7492612e2ad86bb7de2d5...

ahupp 3y ago

Interesting that the second commentor is Tobias Lütke, CEO of Shopify.

0xDEF 3y ago
Also interesting how Shopify is making a lot of moves in this space using both the OpenAI APIs and using self-hosted models.

lachlan_gray 3y ago

Something I’m wondering lately is if you are generating tokens fast enough, is restricting the logits actually worth it computationally? If tokens are cheap enough it might be more efficient to validate/discard them as they come rather than place constraints on how they come out. I don’t know how this one works, but the sampling or renormalizing scheme would cost something too right?

mmoskal 3y ago
There is at least 6 orders of magnitude difference in computation cost of computing a token (pass through a multi-B model) and doing a single step of a program. Even if your validation is really naive, it's hard to beat 6 orders of magnitude. So no, you're not generating tokens fast enough.

karmasimida 3y ago

This is great and all. But LLM's are usually very good at following grammars. I rarely see LLM generating code that is OOD. Ofc, this is only true for popular language (JSON/Python/Java, etc), I can see how this is handy for more niche and in house DSL. You still need quite a lot of prompt engineering to get desired outputs, this just add another layer of output verification IMO. But does it really save much as comparing to get the output then parse and reject the output that doesn't follow the grammar? Might be debateable. But great work regardless.

mpalmer 3y ago
> this just add another layer of output verification IMO. It's not verifying the output after it's done, it's constraining the output as it's generated. > But does it really save much as comparing to get the output then parse and reject the output that doesn't follow the grammar? Might be debateable. I don't think it's debatable at all. Forcing the model to conform to a grammar during generation means there is never a need to discard and regenerate because it got the grammar wrong. Think of the compute involved in generating the whole output and then re-generating if it's non-conformant. There is no comparison.
- karmasimida 3y ago
  > It's not verifying the output after it's done, it's constraining the output as it's generated. It is verifying, by filtering only tokens that allowed by the grammar. I think we are talking about the same thing.