5 ms·

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.
- astrange 3y ago
  This is a sort of modern version of https://wiki.c2.com/?AlternateHardAndSoftLayers https://wiki.c2.com/?AlternateHardAndSoftLayers, one of the most useful software patterns.
  - turnsout 3y ago
    Say more… I read the link, and it seems to be advocating for replacing specific business logic with a generic code interpreter?
    - astrange 3y ago
      I swear the content of that page was a lot more helpful the last time I looked at it. Anyway, the idea is that if you can architecture your program into layers (rather than spaghetti) it can get a lot more powerful if some of your layers are "soft" (dynamic typing/scripting/etc) and some are "hard" (static typing/lower level code/etc). Because some things like UI are too inconvenient to do in static languages so are better as a soft layer, but you want that resting on top of something more proven and type-checked so it still catches bugs easily. In this case, LLMs are a big blob of unproven data that we don't know why they work, i.e. they're not tested. But that's also the reason they can do everything they do.
6gvONxR4sf7o 3y ago
LLMs are happy to generate arbitrary strings. You might want it to spit out something along the lines of "Alice: 42" and then it spits out "hi, i'm helpful and Alice is exactly forty two, as far as I can tell, but I'm just a language model." So you give it a grammar that says the response has to be an uppercase letter followed by lowercase letters, then a colon, then a space, then digits, then it's done. Now, when it looks for that first token, it will only consider tokens that are compatible with that pattern. Then it'll continue with only next tokens that are compatible with the next parts of the pattern. These grammars do that with a flexible and useful kind of pattern.
tylerhou 3y ago
An LLM does not generate "the next token" - from an input text, it generates a vector of probabilities where each slot in the vector corresponds to a token. The value in a token's slot is (approximately) the probability that that particular token might appear next in the text. Programs like ChatGPT "interpret" that vector of probabilities to generate text by selecting (sampling) one of the top tokens. But sometimes this is too flexible -- for example, ChatGPT might generate invalid JSON when you want JSON output because it chose a token that does not conform to the JSON grammar. A way to "force" an LLM to generate e.g. JSON is to change the sampling process. Instead of choosing any top token, we first filter the tokens to just those that conform to the JSON grammar. Then, we sample one of the top tokens from that subset.
- ttul 3y ago
  And given that the inference code has access to the entire vector, it's the logical place to put this filtering... OpenAI and other LLM APIs probably don't want to return the entire token probability vector to the user because it's a lot of data. That being said, it wouldn't surprise me if Microsoft has such access as part of their deal because of the obviously superior position this puts them in vs. regular API customers.
- bryan0 3y ago
  And to build on this, take a look at the code change. Currently in llama.cpp there are many techniques for sampling the next token: llama_sample_token_greedy - just take the top probability llama_sample_top_k - sample only from the top k probabilities etc ... this code change adds a new sample: llama_sample_grammar - sample only from tokens which match the grammar
  - dave1010uk 3y ago
    If the performance was ok, is there any reason why a sampler couldn't call an API or use a separate fine tuned model?
- machiaweliczny 3y ago
  Damn, I thought that making DiffuserAST is smart but sampler based on typescript closures might be much easier to implement. Gotta try this.

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.

astrange 3y ago
This is a sort of modern version of https://wiki.c2.com/?AlternateHardAndSoftLayers https://wiki.c2.com/?AlternateHardAndSoftLayers, one of the most useful software patterns.
- turnsout 3y ago
  Say more… I read the link, and it seems to be advocating for replacing specific business logic with a generic code interpreter?
  - astrange 3y ago
    I swear the content of that page was a lot more helpful the last time I looked at it. Anyway, the idea is that if you can architecture your program into layers (rather than spaghetti) it can get a lot more powerful if some of your layers are "soft" (dynamic typing/scripting/etc) and some are "hard" (static typing/lower level code/etc). Because some things like UI are too inconvenient to do in static languages so are better as a soft layer, but you want that resting on top of something more proven and type-checked so it still catches bugs easily. In this case, LLMs are a big blob of unproven data that we don't know why they work, i.e. they're not tested. But that's also the reason they can do everything they do.

6gvONxR4sf7o 3y ago

LLMs are happy to generate arbitrary strings. You might want it to spit out something along the lines of "Alice: 42" and then it spits out "hi, i'm helpful and Alice is exactly forty two, as far as I can tell, but I'm just a language model." So you give it a grammar that says the response has to be an uppercase letter followed by lowercase letters, then a colon, then a space, then digits, then it's done. Now, when it looks for that first token, it will only consider tokens that are compatible with that pattern. Then it'll continue with only next tokens that are compatible with the next parts of the pattern. These grammars do that with a flexible and useful kind of pattern.

tylerhou 3y ago

An LLM does not generate "the next token" - from an input text, it generates a vector of probabilities where each slot in the vector corresponds to a token. The value in a token's slot is (approximately) the probability that that particular token might appear next in the text. Programs like ChatGPT "interpret" that vector of probabilities to generate text by selecting (sampling) one of the top tokens. But sometimes this is too flexible -- for example, ChatGPT might generate invalid JSON when you want JSON output because it chose a token that does not conform to the JSON grammar. A way to "force" an LLM to generate e.g. JSON is to change the sampling process. Instead of choosing any top token, we first filter the tokens to just those that conform to the JSON grammar. Then, we sample one of the top tokens from that subset.

ttul 3y ago
And given that the inference code has access to the entire vector, it's the logical place to put this filtering... OpenAI and other LLM APIs probably don't want to return the entire token probability vector to the user because it's a lot of data. That being said, it wouldn't surprise me if Microsoft has such access as part of their deal because of the obviously superior position this puts them in vs. regular API customers.
bryan0 3y ago
And to build on this, take a look at the code change. Currently in llama.cpp there are many techniques for sampling the next token: llama_sample_token_greedy - just take the top probability llama_sample_top_k - sample only from the top k probabilities etc ... this code change adds a new sample: llama_sample_grammar - sample only from tokens which match the grammar
- dave1010uk 3y ago
  If the performance was ok, is there any reason why a sampler couldn't call an API or use a separate fine tuned model?
machiaweliczny 3y ago
Damn, I thought that making DiffuserAST is smart but sampler based on typescript closures might be much easier to implement. Gotta try this.