Hacker News Reader

Comment by HarHarVeryFunny | Hacker News Reader

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.

View on HN

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

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

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.

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.

I'm not following. How do you propose search is performed by the ASI designed for "AI Research"? (as proposed by the article)

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.

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?

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

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.

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.

Usually there’s a small neural network that makes the choice for each token in an LLM.

I don't know the details, but there are a variety of routing mechanisms that have been tried. One goal is to load balance tokens among the experts so that each expert's parameters are equally utilized, which it seems must sometimes conflict with wanting to route to an expert based on the token itself.

From what I can gather it depends, but could be a simple Softmax-based layer[1] or just argmax[2].

There was also a recent post[3] about a model where they used a cross-attention layer to let the expert selection be more context aware.

[1]: https://arxiv.org/abs/1701.06538

[2]: https://arxiv.org/abs/2208.02813

[3]: https://news.ycombinator.com/item?id=40675577

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

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.

> [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?

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

Hence my weasel wording of 'typically'.

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

> Would a well constructed chess engine always resign as black?

Depends on what you mean by well-constructed?

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

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.

Reply on news.ycombinator.com