5 ms·

> 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 man

> 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
- contravariant 3y ago
  I mean you're going to need to include a probability to backtrack one way or another, but simply having a backtrack character seems more like a trick to make fitting the model easier than a way to make constraining it more accurate. Simply having the probability to backtrack does turn the whole generation process into a ergodic Markov chain though, so you might be able to use something like MCMC to make it work. Technically those only start sampling the distribution eventually but picking the first or nth full output might be good enough for all practical purposes. Especially at low temperatures where there aren't many reasonable options in the first place.
jiggawatts 3y ago
This is what Google Mind is working on: treating the output of LLMs as tree to be searched instead of just linearly outputting tokens in a "greedy" manner and hoping for the best. Apparently GPT-4 gets a lot of its quality from generating many alternatives (16?) and then picking the best one, but this is 16x as much computer power. A clever tree search (which itself could be a neural net!) could improve the efficiency of this many-fold while simultaneously improving the quality by a huge factor as well.
- contravariant 3y ago
  Arguably a '1 token at a time' model is itself a tree search, so it's more of a perspective than anything. It's really when you start pruning this tree that this distinction becomes interesting. And of course treating the tree as an explicit object may allow the model to do interesting stuff like jumping to a different branch entirely (deletions insertions etc.). Generating 16 alternatives and picking the best one only makes sense to me if your standard for picking one is orthogonal to the model itself, if you just pick the one that your model deems the most likely you've just figure out a very crude and expensive way to lower the temperature.
  - Vetch 3y ago
    That is stretching arguably too far. If you are taking 1 sample path, you are not in any meaningful sense searching a tree. In the context of sampling a probability distribution, which is what LLMs do in effect, there is extra depth to this. Any random response need not be representative of what the model "thinks". And maybe counter-intuitive to some but the most likely generation might actually be unrepresentative as well. Drawing lots of samples and then marginalizing (as a kind of vote) is methodologically more principled where appropriate. Constraining generation according to some gating function, continually redrawing samples, can be used to significantly reduce error rates at the cost of longer generation times. LLMs are not being used to their full potential because it is too costly to do so.
  - joaogui1 3y ago
    When we talk about tree search we allow for backtracking, so if a node has 3 children all 3 will be explored generally, or at least a subsample of the children will be, in LLM sampling you generally pick a single token/child and then just go on with that until the end of the generation. If DeepMind is indeed doing something similar to AlphaZero to language modelling one would expect they would generate multiple "rollouts" from the current context and then use some kind of function/network to predict which next token will lead you to the best final generation and then output that token. How to do all of that using a sensible amount of compute is what remains to be seen
newhouseb 3y ago
The way LLMs work is they output probabilities for every _token_, so you don't really need to backtrack you can just always pick a token that matches the provided grammar. That said, you might want to do something like (backtracking) beam-search which uses various heuristics to simultaneously explore multiple different paths because the semantic information may not be front-loaded, i.e. let's say we had a grammar that had a key "healthy" with values "very_unhealthy" or "moderately_healthy." For broccoli, the LLM might intend to say "very_healthy" and choose "very" but then be pigeonholed into saying "very_unhealthy" because it's the only valid completion according to the grammar. That said, there are a lot of shortcuts you can take to make this fairly efficient thanks to the autoregressive nature of (most modern) LLMs. You only need to regenerate / recompute from where you want to backtrack from.
- Vetch 3y ago
  Whether or not backtracking is needed is really down to the grammar's ambiguity. The auto-regressive nature of LLMs is actually something that counts against them, at least as some tell it. Although, really, the root problem is generating autoregressively from LLMs precludes planning ahead while also lacking any iterative refinement stage. Backtracking, look-ahead, early failure pruning and staged generation are all very useful for fitting both concepts (refinement and planning ahead) in an auto-regressive generation framework.

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

contravariant 3y ago
I mean you're going to need to include a probability to backtrack one way or another, but simply having a backtrack character seems more like a trick to make fitting the model easier than a way to make constraining it more accurate. Simply having the probability to backtrack does turn the whole generation process into a ergodic Markov chain though, so you might be able to use something like MCMC to make it work. Technically those only start sampling the distribution eventually but picking the first or nth full output might be good enough for all practical purposes. Especially at low temperatures where there aren't many reasonable options in the first place.

jiggawatts 3y ago

This is what Google Mind is working on: treating the output of LLMs as tree to be searched instead of just linearly outputting tokens in a "greedy" manner and hoping for the best. Apparently GPT-4 gets a lot of its quality from generating many alternatives (16?) and then picking the best one, but this is 16x as much computer power. A clever tree search (which itself could be a neural net!) could improve the efficiency of this many-fold while simultaneously improving the quality by a huge factor as well.

contravariant 3y ago
Arguably a '1 token at a time' model is itself a tree search, so it's more of a perspective than anything. It's really when you start pruning this tree that this distinction becomes interesting. And of course treating the tree as an explicit object may allow the model to do interesting stuff like jumping to a different branch entirely (deletions insertions etc.). Generating 16 alternatives and picking the best one only makes sense to me if your standard for picking one is orthogonal to the model itself, if you just pick the one that your model deems the most likely you've just figure out a very crude and expensive way to lower the temperature.
- Vetch 3y ago
  That is stretching arguably too far. If you are taking 1 sample path, you are not in any meaningful sense searching a tree. In the context of sampling a probability distribution, which is what LLMs do in effect, there is extra depth to this. Any random response need not be representative of what the model "thinks". And maybe counter-intuitive to some but the most likely generation might actually be unrepresentative as well. Drawing lots of samples and then marginalizing (as a kind of vote) is methodologically more principled where appropriate. Constraining generation according to some gating function, continually redrawing samples, can be used to significantly reduce error rates at the cost of longer generation times. LLMs are not being used to their full potential because it is too costly to do so.
- joaogui1 3y ago
  When we talk about tree search we allow for backtracking, so if a node has 3 children all 3 will be explored generally, or at least a subsample of the children will be, in LLM sampling you generally pick a single token/child and then just go on with that until the end of the generation. If DeepMind is indeed doing something similar to AlphaZero to language modelling one would expect they would generate multiple "rollouts" from the current context and then use some kind of function/network to predict which next token will lead you to the best final generation and then output that token. How to do all of that using a sensible amount of compute is what remains to be seen

newhouseb 3y ago

The way LLMs work is they output probabilities for every _token_, so you don't really need to backtrack you can just always pick a token that matches the provided grammar. That said, you might want to do something like (backtracking) beam-search which uses various heuristics to simultaneously explore multiple different paths because the semantic information may not be front-loaded, i.e. let's say we had a grammar that had a key "healthy" with values "very_unhealthy" or "moderately_healthy." For broccoli, the LLM might intend to say "very_healthy" and choose "very" but then be pigeonholed into saying "very_unhealthy" because it's the only valid completion according to the grammar. That said, there are a lot of shortcuts you can take to make this fairly efficient thanks to the autoregressive nature of (most modern) LLMs. You only need to regenerate / recompute from where you want to backtrack from.

Vetch 3y ago
Whether or not backtracking is needed is really down to the grammar's ambiguity. The auto-regressive nature of LLMs is actually something that counts against them, at least as some tell it. Although, really, the root problem is generating autoregressively from LLMs precludes planning ahead while also lacking any iterative refinement stage. Backtracking, look-ahead, early failure pruning and staged generation are all very useful for fitting both concepts (refinement and planning ahead) in an auto-regressive generation framework.