4 ms·

Yeah, Stockfish is probably evaluating many millions of positions when looking 40-ply ahead, even with the limited number of legal chess moves in a given positi

Yeah, Stockfish is probably evaluating many millions of positions when looking 40-ply ahead, even with the limited number of legal chess moves in a given position, and with an easy criteria for heavy early pruning (once a branch becomes losing, not much point continuing it). I can't imagine the cost of evaluating millions of LLM continuations, just to select the optimal one! Where tree search might make more sense applied to LLMs is for more coarser grained reasoning where the branching isn't based on alternate word continuations but on alternate what-if lines of thought, but even then it seems costs could easily become prohibitive, both for generation and evaluation/pruning, and using such a biased approach seems as much to fly in the face of the bitter lesson as be suggested by it.

mxwsn 2y ago
Yes absolutely and well put - a strong property of chess is that next states are fast and easy to enumerate, which makes search particularly easy and strong, while next states are much slower, harder to define, and more expensive to enumerate with an LLM
- typon 2y ago
  The cost of the LLM isn't the only or even the most important cost that matters. Take the example of automating AI research: evaluating moves effectively means inventing a new architecture or modifying an existing one, launching a training run and evaluating the new model on some suite of benchmarks. The ASI has to do this in a loop, gather feedback and update its priors - what people refer to as "Grad student descent". The cost of running each train-eval iteration during your search is going to be significantly more than generating the code for the next model.
  - HarHarVeryFunny 2y ago
    You're talking about applying tree search as a form of network architecture search (NAS), which is different from applying it to LLM output sampling. Automated NAS has been tried for (highly constrained) image classifier design, before simpler designs like ResNets won the day. Doing this for billion parameter sized models would certainly seem to be prohibitively expensive.
    - typon 2y ago
      I'm not following. How do you propose search is performed by the ASI designed for "AI Research"? (as proposed by the article)
      - HarHarVeryFunny 2y ago
        Fair enough - he discusses GPT-4 search halfway down the article, but by the end is discussing self-improving AI. Certainly compute to test ideas (at scale) is the limiting factor for LLM developments (says Sholto @ Google), but if we're talking moving beyond LLMs, not just tweaking them, then it seems we need more than architecture search anyways.
  - therobots927 2y ago
    Well people certainly are good at finding new ways to consume compute power. Whether it’s mining bitcoins or training a million AI models at once to generate a “meta model” that we think could achieve escape velocity. What happens when it doesn’t? And Sam Altman and the author want to get the government to pay for this? Am I reading this right?
byteknight 2y ago
Isn't evaluating against different effective "experts" within the model effectively what MoE [1] does? > Mixture of experts (MoE) is a machine learning technique where multiple expert networks (learners) are used to divide a problem space into homogeneous regions.[1] It differs from ensemble techniques in that for MoE, typically only one or a few expert models are run for each input, whereas in ensemble techniques, all models are run on every input. [1] https://en.wikipedia.org/wiki/Mixture_of_experts https://en.wikipedia.org/wiki/Mixture_of_experts
- HarHarVeryFunny 2y ago
  No - MoE is just a way to add more parameters to a model without increasing the cost (number of FLOPs) of running it. The way MoE does this is by having multiple alternate parallel paths through some parts of the model, together with a routing component that decides which path (one only) to send each token through. These paths are the "experts", but the name doesn't really correspond to any intuitive notion of expert. So, rather than having 1 path with N parameters, you have M paths (experts) each with N parameters, but each token only goes through one of them, so number of FLOPs is unchanged. With tree search, whether for a game like Chess or potentially LLMs, you are growing a "tree" of all possible alternate branching continuations of the game (sentence), and keeping the number of these branches under control by evaluating each branch (= sequence of moves) to see if it is worth continuing to grow, and if not discarding it ("pruning" it off the tree). With Chess, pruning is easy since you just need to look at the board position at the tip of the branch and decide if it's a good enough position to continue playing from (extending the branch). With an LLM each branch would represent an alternate continuation of the input prompt, and to decide whether to prune it or not you'd have to pass the input + branch to another LLM and have it decide if it looked promising or not (easier said than done!). So, MoE is just a way to cap the cost of running a model, while tree search is a way to explore alternate continuations and decide which ones to discard, and which ones to explore (evaluate) further.
  - PartiallyTyped 2y ago
    How does MoE choose an expert? From the outside and if we squint a bit; this looks a lot like an inverted attention mechanism where the token attends to the experts.
stevage 2y ago
Pruning isn't quite as easy as you make it sound. There are lots of famous examples where chess engines misevaluate a position because they prune out apparently losing moves that are actually winning. Eg https://youtu.be/TtJeE0Th7rk?si=KVAZufm8QnSW8zQo https://youtu.be/TtJeE0Th7rk?si=KVAZufm8QnSW8zQo
vlovich123 2y ago
> and with an easy criteria for heavy early pruning (once a branch becomes losing, not much point continuing it) This confuses me. Positions that seem like they could be losing (but haven’t lost yet) could become winning if you search deep enough.
- HarHarVeryFunny 2y ago
  Yes, and even a genuinely (with perfect play) losing position can win if it sharp enough and causes your opponent to make a mistake! There's also just the relative strength of one branch vs another - have to prune some if there are too many. I was just trying to give the flavor of it.
  - eru 2y ago
    > [E]ven a genuinely (with perfect play) losing position can win if it sharp enough and causes your opponent to make a mistake! Chess engines typically assume that the opponent plays to the best of their abilities, don't they?
    - nullc 2y ago
      Imagine that there was some non-constructive proof that white would always win in perfect play. Would a well constructed chess engine always resign as black? :P
      - eru 2y ago
        > Would a well constructed chess engine always resign as black? Depends on what you mean by well-constructed?
    - slyall 2y ago
      The Contempt Factor is used by engines sometimes. "The Contempt Factor reflects the estimated superiority/inferiority of the program over its opponent. The Contempt factor is assigned as draw score to avoid (early) draws against apparently weaker opponents, or to prefer draws versus stronger opponents otherwise." https://www.chessprogramming.org/Contempt_Factor https://www.chessprogramming.org/Contempt_Factor
AnimalMuppet 2y ago
> Where tree search might make more sense applied to LLMs is for more coarser grained reasoning where the branching isn't based on alternate word continuations but on alternate what-if lines of thought... To do that, the LLM would have to have some notion of "lines of thought". They don't. That is completely foreign to the design of LLMs.
- HarHarVeryFunny 2y ago
  Right - this isn't something that LLMs currently do. Adding search would be a way to add reasoning. Think of it as part of a reasoning agent - external scaffolding similar to tree of thoughts.

mxwsn 2y ago

Yes absolutely and well put - a strong property of chess is that next states are fast and easy to enumerate, which makes search particularly easy and strong, while next states are much slower, harder to define, and more expensive to enumerate with an LLM

typon 2y ago
The cost of the LLM isn't the only or even the most important cost that matters. Take the example of automating AI research: evaluating moves effectively means inventing a new architecture or modifying an existing one, launching a training run and evaluating the new model on some suite of benchmarks. The ASI has to do this in a loop, gather feedback and update its priors - what people refer to as "Grad student descent". The cost of running each train-eval iteration during your search is going to be significantly more than generating the code for the next model.
- HarHarVeryFunny 2y ago
  You're talking about applying tree search as a form of network architecture search (NAS), which is different from applying it to LLM output sampling. Automated NAS has been tried for (highly constrained) image classifier design, before simpler designs like ResNets won the day. Doing this for billion parameter sized models would certainly seem to be prohibitively expensive.
  - typon 2y ago
    I'm not following. How do you propose search is performed by the ASI designed for "AI Research"? (as proposed by the article)
    - HarHarVeryFunny 2y ago
      Fair enough - he discusses GPT-4 search halfway down the article, but by the end is discussing self-improving AI. Certainly compute to test ideas (at scale) is the limiting factor for LLM developments (says Sholto @ Google), but if we're talking moving beyond LLMs, not just tweaking them, then it seems we need more than architecture search anyways.
- therobots927 2y ago
  Well people certainly are good at finding new ways to consume compute power. Whether it’s mining bitcoins or training a million AI models at once to generate a “meta model” that we think could achieve escape velocity. What happens when it doesn’t? And Sam Altman and the author want to get the government to pay for this? Am I reading this right?

byteknight 2y ago

Isn't evaluating against different effective "experts" within the model effectively what MoE [1] does? > Mixture of experts (MoE) is a machine learning technique where multiple expert networks (learners) are used to divide a problem space into homogeneous regions.[1] It differs from ensemble techniques in that for MoE, typically only one or a few expert models are run for each input, whereas in ensemble techniques, all models are run on every input. [1] https://en.wikipedia.org/wiki/Mixture_of_experts https://en.wikipedia.org/wiki/Mixture_of_experts

HarHarVeryFunny 2y ago
No - MoE is just a way to add more parameters to a model without increasing the cost (number of FLOPs) of running it. The way MoE does this is by having multiple alternate parallel paths through some parts of the model, together with a routing component that decides which path (one only) to send each token through. These paths are the "experts", but the name doesn't really correspond to any intuitive notion of expert. So, rather than having 1 path with N parameters, you have M paths (experts) each with N parameters, but each token only goes through one of them, so number of FLOPs is unchanged. With tree search, whether for a game like Chess or potentially LLMs, you are growing a "tree" of all possible alternate branching continuations of the game (sentence), and keeping the number of these branches under control by evaluating each branch (= sequence of moves) to see if it is worth continuing to grow, and if not discarding it ("pruning" it off the tree). With Chess, pruning is easy since you just need to look at the board position at the tip of the branch and decide if it's a good enough position to continue playing from (extending the branch). With an LLM each branch would represent an alternate continuation of the input prompt, and to decide whether to prune it or not you'd have to pass the input + branch to another LLM and have it decide if it looked promising or not (easier said than done!). So, MoE is just a way to cap the cost of running a model, while tree search is a way to explore alternate continuations and decide which ones to discard, and which ones to explore (evaluate) further.
- PartiallyTyped 2y ago
  How does MoE choose an expert? From the outside and if we squint a bit; this looks a lot like an inverted attention mechanism where the token attends to the experts.

stevage 2y ago

Pruning isn't quite as easy as you make it sound. There are lots of famous examples where chess engines misevaluate a position because they prune out apparently losing moves that are actually winning. Eg https://youtu.be/TtJeE0Th7rk?si=KVAZufm8QnSW8zQo https://youtu.be/TtJeE0Th7rk?si=KVAZufm8QnSW8zQo

vlovich123 2y ago

> and with an easy criteria for heavy early pruning (once a branch becomes losing, not much point continuing it) This confuses me. Positions that seem like they could be losing (but haven’t lost yet) could become winning if you search deep enough.

HarHarVeryFunny 2y ago
Yes, and even a genuinely (with perfect play) losing position can win if it sharp enough and causes your opponent to make a mistake! There's also just the relative strength of one branch vs another - have to prune some if there are too many. I was just trying to give the flavor of it.
- eru 2y ago
  > [E]ven a genuinely (with perfect play) losing position can win if it sharp enough and causes your opponent to make a mistake! Chess engines typically assume that the opponent plays to the best of their abilities, don't they?
  - nullc 2y ago
    Imagine that there was some non-constructive proof that white would always win in perfect play. Would a well constructed chess engine always resign as black? :P
    - eru 2y ago
      > Would a well constructed chess engine always resign as black? Depends on what you mean by well-constructed?
  - slyall 2y ago
    The Contempt Factor is used by engines sometimes. "The Contempt Factor reflects the estimated superiority/inferiority of the program over its opponent. The Contempt factor is assigned as draw score to avoid (early) draws against apparently weaker opponents, or to prefer draws versus stronger opponents otherwise." https://www.chessprogramming.org/Contempt_Factor https://www.chessprogramming.org/Contempt_Factor

AnimalMuppet 2y ago

> Where tree search might make more sense applied to LLMs is for more coarser grained reasoning where the branching isn't based on alternate word continuations but on alternate what-if lines of thought... To do that, the LLM would have to have some notion of "lines of thought". They don't. That is completely foreign to the design of LLMs.

HarHarVeryFunny 2y ago
Right - this isn't something that LLMs currently do. Adding search would be a way to add reasoning. Think of it as part of a reasoning agent - external scaffolding similar to tree of thoughts.