6 ms·
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 p
by 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 agoSo does this mean I can detect "Sorry" at the start of a response and prevent it?
- pshc 3y agoI 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 agoRight, 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.)
- swyx 3y agoyou could also always specify the logit bias parameter in openai apis
- pshc 3y agoThat's true, and one can bias logits in llama.cpp and friends too, but those are global biases that affect the entire output rather than being specified per-token. Uploading a grammar or a wasm binary to the inference engine does seem more expressive.
- jiggawatts 3y agoNot just that: the LLM outputs not individual tokens, but a weighted recommendation. The most probable (“best”) token has the highest weight, but there may be many alternatives including JSON symbols like quote characters. The “temperature” setting adjusts how likely it is that an output token is chosen that is not the top-rated option. That prevents repetitive output. Forcing an LLM to obey a grammar is mostly about filtering the list before the token choice is made. There may still be a random element controlled by the temperature! A more advanced feature not commonly used is to also enable back-tracking if the AI gets stuck and can’t produce a valid output.
- contravariant 3y ago> A more advanced feature not commonly used is to also enable back-tracking if the AI gets stuck and can’t produce a valid output. Technically that part is mandatory if you don't just want it to produce an output but to make it produce an output that correctly matches the temperature (i.e. one that you could have gotten by randomly sampling the LLM until you got a correct one). Randomly picking the next tokens that isn't grammatically incorrect works but oversamples paths where most of the options are invalid. The ultimate example of this is that it can get stuck at a branch with probability 0. From a probabilistic standpoint what you'd need to do is not just make it backtrack but make it keep generating until it generates a grammatically correct output in one go. Maybe there is something clever that can be done to avoid regenerating from the start? What you'd need to achieve is that a token that has a x% probability of leading to an incorrect output also has x% probability to be erased.
- brucethemoose2 3y ago> Maybe there is something clever that can be done to avoid regenerating from the start? What you'd need to achieve is that a token that has a x% probability of leading to an incorrect output also has x% probability to be erased. Like giving the llm a backspace token? There is a paper related to this: https://news.ycombinator.com/item?id=36425375 https://news.ycombinator.com/item?id=36425375
- 3y ago
- IAmNotACellist 3y agoI'm struggling to understand what he's talking about. Starting with "passing up," did he invent this terminology? The only input you have to an LLM is the prompt, which gets tokenized. And if you were to send DCFG rules or a compiled version of it as part of the request, how would that fundamentally alter the way that the tokens are predicted? If the model predicts something that doesn't conform to the grammar you require, is he proposing re-prompting until it gets it right?
- baobabKoodaa 3y agoYou have more inputs to an LLM than just the prompt. For example, people commonly pass parameters which control the sampling of tokens. Implementing grammar based sampling does NOT require "re-prompting until it gets it right". Imagine a point in time when the LLM is generating some particular token. Which token will it produce? To decide that, it evaluates and assigns a score to each potential token. Then it chooses one of these options based on some rules. Rules could be as simple as "pick the token with the highest score". That is called a greedy strategy. Usually more complex strategies are used and they typically have some randomness. That is called sampling. You can imagine a grammar based sampling strategy to force specific tokens at specific positions in the output, for example, to close a bracket in json.
- lyjackal 3y agoThe model returns probabilities across the full set of tokens. This restricts the tokens to those that conform to the grammar, and samples from those
- radarsat1 3y agoThis reminds me of something i did once using a 1d CRF at the output of a sequence model. I set "impossible" transitions to -inf so that transitions between certain state pairs were simply never predicted. I could imagine executing something like this that is conditional on the current grammatical context. On fact it's a bit surprising to me how little I see CRFs mentioned in the context of language models. They are useful whenever you want to model or learn transition probabilities.
- eightysixfour 3y agoIsn’t this what Microsoft Guidance does? https://github.com/microsoft/guidance https://github.com/microsoft/guidance
- ttul 3y agoI read the code. Guidance seems designed to work well with OpenAI's chat completion API. When you ask Guidance to choose from a set of options, it breaks the list into a tree of tokens and then walks this tree, providing the next set of possible tokens in the logit_bias parameter with value set to +100. For example, suppose that you specify this as your Guidance "program" and suppose (for sake of simplicity) that the token for "lea" is 1300, the token for "ther" is 1500, and the token for "ves" is 5300: "armor": "{{#select 'armor'}}leather{{or}}leaves{{/select}}", Guidance will send OpenAI a chat completion starting with "armor": " ... providing a logit_bias map {"1300": "100"}. This bias forces the model to choose "lea" as the next token. Following this call, we have the prefix "armor": "lea ... and now Guidance calls chat completion again setting the logit_bias map to {"1500": "100", "5300": "100"} to indicate that the tokens for "ther" or "ves" are equally probable and really the only tokens the model is allowed to select between, unless some other token is maximally probable given the context. OpenAI now replies with token "1500" (let's say) and Guidance completes the string as follows: "armor": "leather ... because "ther" is represented by token number 1500. Guidance then tacks on the closing quote and other stuff specified by the user: "armor": "leather", ... and it sets the value of "armor" to "leather" so that you can use that value later in your code if you wish to. Guidance is pretty powerful, but I find the grammar hard to work with. I think the idea of being able to upload a bit of code or a context-free grammar to guide the model is super smart. https://github.com/microsoft/guidance/blob/d2c5e3cbb730e337b9bee20520eb694bd43e5f38/guidance/library/_select.py#L67 https://github.com/microsoft/guidance/blob/d2c5e3cbb730e337b...
- ricopags 3y agoJust to +1 mmoskal, while Guidance does somewhat work with OpenAI APIs, AFAIK it was first designed around having direct access to the logits, thus is superior when using local models.
- 3y ago
- SCHiM 3y agoNo, the way it works is that the current output + potential next tokens to be sampled are checked with the grammar. All potential tokens that don't match are removed. Then, with the list of valid tokens left, normal sampling strategies are used.
- barbazoo 3y agoThank you for laying it out like that.
- thomasahle 3y agoAnother detailed description of how to do this: https://github.com/normal-computing/outlines/pull/131 https://github.com/normal-computing/outlines/pull/131 That's one of the developers of the Outlines library, another cool LLM workflow library.
- farissbahi 3y agoThere's a paper as well. :) https://arxiv.org/pdf/2307.09702.pdf https://arxiv.org/pdf/2307.09702.pdf
- nojvek 3y agoI’m sure ggml would accept that as a PR if the wasm vm had a tiny surface area.