AI Search: The Bitter-Er Lesson

The effectiveness of search goes hand-in-hand with quality of the value function. But today, value functions are incredibly domain-specific, and there is weak or no current evidence (as far as I know) that we can make value functions that generalize well to new domains. This article effectively makes a conceptual leap from "chess has good value functions" to "we can make good value functions that enable search for AI research". I mean yes, that'd be wonderful - a holy grail - but can we really?

In the meantime, 1000x or 10000x inference time cost for running an LLM gets you into pretty ridiculous cost territory.

I feel like this is a really hard problem to solve generally and there are smart researchers like Yann LeCun trying to figure out the role of search in creating AGI. Yann's current bet seems to be on Joint Embedding Predictive Architectures (JEPA) for representation learning to eventually build a solid world model where the agent can test theories by trying different actions (aka search). I think this paper [0] does a good job in laying out his potential vision, but it is all ofc harder than just search + transformers.

There is an assumption that language is good enough at representing our world for these agents to effectively search over and come up with novel & useful ideas. Feels like an open question but: What do these LLMs know? Do they know things? Researchers need to find out! If current LLMs' can simulate a rich enough world model, search can actually be useful but if they're faking it, then we're just searching over unreliable beliefs. This is why video is so important since humans are proof we can extract a useful world model from a sequence of images. The thing about language and chess is that the action space is effectively discrete so training generative models that reconstruct the entire input for the loss calculation is tractable. As soon as we move to video, we need transformers to scale over continuous distributions making it much harder to build a useful predictive world model.

[0]: https://arxiv.org/abs/2306.02572

Anything that allows AI to scale to superinteligence quicker is going to run into AI alignment issues, since we don’t really know a foolproof way of controlling AI. With the AI of today, this isn’t too bad (the worst you get is stuff like AI confidently making up fake facts), but with a superintelligence this could be disastrous.

It’s very irresponsible for this article to advocate and provide a pathway to immediate superintelligence (regardless of whether or not it actually works) without even discussing the question of how you figure out what you’re searching for, and how you’ll prevent that superintelligence from being evil.

Before an LLM discovers a cure for cancer, I propose we first let it solve the more tractable problem of discovering the “God Cheesecake” - the cheesecake do delicious that a panel of 100 impartial chefs judges to be the most delicious they have ever tasted. All the LLM has to do is intelligently search through the much more combinatorially bounded “cheesecake space” until it finds this maximally delicious cheesecake recipe.

But wait… An LLM can’t bake cheesecakes, nor if it could would it be able to evaluate their deliciousness.

Until AI can solve the “God Cheesecake” problem, I propose we all just calm down a bit about AGI

I believe in search, but it only works if you have an appropriate search space. Chess has a well-defined space but the everyday world does not. The trick is enabling an algorithm to learn its own search space through active exploration and reading about our world. I'm working on that.

I didn’t understand this piece.

What do they mean by using LLMs with search? Is this simply RAG?

The problem with adding "search" to a model is that the model has already seen everything to be "search"ed in its training data. There is nothing left.

Imagine if Leela (author's example) had been trained on every chess board position out there (I know it's mathematically impossible, but bear with me for a second). If Leela had been trained on every board position, it may have whupped Stockfish. So, adding "search" to Leela would have been pointless, since it would have seen every board position out there.

Today's LLMs are trained on every word ever written on the 'net, every word ever put down in a book, every word uttered in a video on Youtube or a podcast.

This is a fascinating idea - although I wish the definition of search in the LLM context was expanded a bit more. What kind of search capability strapped onto current-gen LLMs would give them superpowers?

It seems there is a fundamental information theory aspect to this that would probably save us all a lot of trouble if we would just embrace it.

The #1 canary for me: Why does training an LLM require so much data that we are concerned we might run out of it?

The clear lack of generalization and/or internal world modeling is what is really in the way of a self-bootstrapping AGI/ASI. You can certainly try to emulate a world model with clever prompting (here's what you did last, heres your objective, etc.), but this seems seriously deficient to me based upon my testing so far.

The article seems rather hand-wavy and over-confident about predicting the future, but it seems worth trying.

"Search" is a generalization of "generate and test" and rejection sampling. It's classic AI. Back before the dot-com era, I took an intro to AI course and we learned about writing programs to do searches in Prolog.

The speed depends on how long it takes to generate a candidate, how long it takes to test it, and how many candidates you need to try. If they are slow, it will be slow.

An example of "human in the loop" rejection sampling is when you use an image generator and keep trying different prompts until you get an image you like. But the loop is slow due to how long it takes to generate a new image. If image generation were so fast that it worked like Google Image search, then we'd really have something.

Theorem proving and program fuzzing seem like good candidates for combining search with LLM's, due to automated, fast, good evaluation functions.

And it looks like Google has released a fuzzer [1] that can be connected to whichever LLM's you like. Has anyone tried it?

[1] https://github.com/google/oss-fuzz-gen

Search is almost certainly necessary, and I think the trillion dollar cluster maximalists probably need to talk to people who created superhuman chess engines that now can run on smartphones. Because one possibility is that someone figures out how to beat your trillion dollar cluster with a million dollar cluster, or 500k million dollar clusters.

On chess specifically, my takeaway is that the branching factor in chess never gets so high that a breadth-first approach is unworkable. The median branching factor (i.e. the number of legal moves) maxes out at around 40 but generally stays near 30. The most moves I have ever found in any position from a real game was 147, but at that point almost every move is checkmate anyways.

Creating superhuman go engines was a challenge for a long time because the branching factor is so much larger than chess.

Since MCTS is less thorough, it makes sense that a full search could find a weakness and exploit it. To me, the question is whether we can apply breadth-first approaches to larger games and situations, and I think the answer is clearly no. Unlike chess, the branching factor of real-world situations is orders of magnitude larger.

But also unlike chess, which is highly chaotic (small decisions matter a lot for future state), most small decisions don't matter. If you're flying from NYC to LA, it matters a lot if you drive or fly or walk. It mostly doesn't matter if you walk out the door starting with your left foot or your right. It mostly doesn't matter if you blink now or in two seconds.

The post starts with a fascinating premise, but then falls short as it does not define search in the context of LLMs, nor does it explain how “Pfizer can access GPT-8 capabilities today with more inference compute”.

I found it hard to follow and I am an AI practitioner. Could someone please explain more what could the OP mean?

To me it seems that the flavor of search in the context of chess engines (look several moves ahead) is possible precisely because there’s an objective function that can be used to rank results, i.e. which potential move is “better” and this is more often than not a unique characteristic of reinforcement learning. Is there even such a metric for LLMs?

Isn't the "search" space infinite though and impossible to qualify "success"?

You can't just give LLMs infinite compute time and expect them to find answers for like "cure cancer". Even chess moves that seem finite and success quantifiable are an also infinite problem and the best engines take "shortcuts" in their "thinking". It's impossible to do for real world problems.

While I respect the power of intuition - this may well be a great path - it's worth keeping in mind that this is currently just that. A hunch. Leela got crushed due to AI directed search, what if we can wave a wand and hand all AIs search. Somehow. Magically. Which will then somehow magically trounce current LLMs at domain-specific task.

There's a kernel of truth in there. See the papers on better results via monte carlo search trees (e.g. [1]). See mixture-of-LoRA/LoRA-swarm approaches. (I swear there's a startup using the approach of tons of domain-specific LoRAs, but my brain's not yielding the name)

Augmenting LLM capabilities via _some_ sort of cheaper and more reliable exploration is likely a valid path. It's not GPT-8 next year, though.

[1] https://arxiv.org/pdf/2309.03224

The branching factor for chess is about 35.

For token generation, the branching factor depends on the tokenizer, but 32,000 is a common number.

Will search be as effective for LLMs when there are so many more possible branches?

I wouldn’t read too much into stockfish beating Leela Chess Zero. My calculator beats GPT-4 in matrix multiplication, doesn’t mean we need to do what my calculator does in GPT-4 to make it smarter. Stockfish evaluates 70 million moves per second (or something in that ballpark). Chess is not such a complicated game that you aren’t guaranteed to find the best move when you evaluate 70 million moves. It’s why when there was an argument whether alpha zero really beat stockfish convincingly in Google’s PR Stunt, a notable chess master quipped “Even god would not be able to beat stockfish this frequently.” , similarly god with all this magical powers would not beat my calculator at multiplication. It says more about the task than about the nature of intelligence.

Charlie Steiner pointed this out 5 years ago on Less Wrong:

If you train GPT-3 on a bunch of medical textbooks and prompt it to tell you a cure for Alzheimer's, it won't tell you a cure, it will tell you what humans have said about curing Alzheimer's ... It would just tell you a plausible story about a situation related to the prompt about curing Alzheimer's, based on its training data. Rather than a logical Oracle, this image-captioning-esque scheme would be an intuitive Oracle, telling you things that make sense based on associations already present within the training set.

What am I driving at here, by pointing out that curing Alzheimer's is hard? It's that the designs above are missing something, and what they're missing is search. I'm not saying that getting a neural net to directly output your cure for Alzheimer's is impossible. But it seems like it requires there to already be a "cure for Alzheimer's" dimension in your learned model. The more realistic way to find the cure for Alzheimer's, if you don't already know it, is going to involve lots of logical steps one after another, slowly moving through a logical space, narrowing down the possibilities more and more, and eventually finding something that fits the bill. In other words, solving a search problem.

So if your AI can tell you how to cure Alzheimer's, I think either it's explicitly doing a search for how to cure Alzheimer's (or worlds that match your verbal prompt the best, or whatever), or it has some internal state that implicitly performs a search.

https://www.lesswrong.com/posts/EMZeJ7vpfeF4GrWwm/self-super...

I think I understand the game space that Leela and now Stockfish search. I don't understand whether the author envisions LLMs searching possibility spaces of

  1) written words,
  2) models of math / RL / materials science,
  3) some smaller, formalized space like the game space of chess,

slight step aside - do people at notion realize, their own custom keyboard shortcuts break the habits built on the web.

cmd + p -- bring up their own custom dialog. instead of printing the page as one would expect

This feels a lot like generation 3 AI throwing out all the insights from gens 1 and 2 and then rediscovering them from first principles, but it’s difficult to tell what this text is really about because it lumps together a lot of things into “search” without fully describing what that means more formally.

> She was called Leela Chess Zero — ’zero’ because she started knowing only the rules.

That's a common framing but it's wrong. Leela -and all its friends- have another piece of chess-specific knowledge that is indispensable to their performance: they have a representation of the game of chess -a game-world model- as a game tree, divided in plys: one ply for each player's turn. That game tree is what is searched by adversarial search algorithms, such as minimax or Monte Carlo Tree Search (MCTS; the choice of Leela, IIUC).

More precisely modelling a game as a game tree applies to many games, not just chess, but the specific brand of game tree used in chess engines applies to chess and similar, two-person, zero-sum, complete information board games. I do like my jargon! For other kinds of games, different models, and different search algorithms are needed, e.g. see Poker and Libratus [1].

The need for such a game tree, such a model of a game world, is currently impossible to go without, if the target is superior performance. The article mentions no-search algorithms and briefly touches upon their main limitation (i.e. "why?").

All that btw is my problem with the Bitter Lesson: it is conveniently selective with what it considers domain knowledge (i.e. a "model" in the sense of a theory). As others have noted, e.g. Rodney Brooks [2], Convolutional Neural Nets have dominated image classification thanks to the use of convolutional layers to establish positional invariance. That's a model of machine vision invented by a human, alright, just as a game-tree is a model of a game invented by a human, and everything else anyone has ever done in AI and machine learning is the same: a human comes up with a model, of a world, of an environment, of a domain, of a process, then a computer calculates using that model, and sometimes even outperforms humans (as in chess, Go, and friends) or at the very least achieves results that humans cannot match with hand-crafted solutions.

That is a lesson to learn (with all due respect to Rich Sutton). Human model + machine computation has solved every hard problem in AI in the last 80 years. And we have no idea how to do anything even slightly different.

____________________

[1] https://en.wikipedia.org/wiki/Libratus

[2] https://rodneybrooks.com/a-better-lesson/

The whole premise of this article is to compare the chess state of the art of 2019 with today, and then they start to talk about llms. But chess is a board with 64 squares and 32 pieces, it's literally nothing compared to the real physical world. So I don't get how this is relevant

If I had to bet money on it, researchers at top labs have already tried applying search to existing models. The idea to do so is pretty obvious. I don't think it's the one key insight to achieve AGI as the author claims.

The author is making a few leap of faith in this article.

First, his example of the efficiency of ML+search for playing Chess is interesting but not a proof that this strategy would be applicable or efficient in the general domain.

Second, he is implying that some next iteration of ChatGPT will reach AGI level, given enough scale and money. This should be considered hypothetical until proven.

Overall, he should be more scientific and prudent.

I don't run javascript by default using NoScript, and something amusing happened on this website because of it.

The link for the site points to a notion.site address, but attempting to go to this address without javascript enabled (for that domain) forces a redirect to a notion.so domain. Attempting to visit just the basic notion.site address also does this same redirection.

What this ends up causing is that I don't have an easy way to use NoScript to temporarily turn on javascript for the notion.site domain, because it never loads. So much for reading this article.

This is one of my favorite reads in a while

What happened to all the chatter about Q*? I remember reading about this train/test time trade-off back then, does anyone have good list of recent papers/blogs about this? What is holding back this or openai is just running some model 10x longer to estimate what they would get if they trained with 10x?

This tweet is relevant: https://x.com/polynoamial/status/1676971503261454340

The problem is the transitive closure of chess move is a chess move. The transitive closure of human knowledge and theories to do X is new theories never seen before and no Value function can do that, unless you are also implying theorem proving is included for correctness verification which is also a very difficult search and computationally expensive problem on its own.

Also, I think this is instead time to sit back and think what exactly is the thing we value in society as well: Personal(Human) self-sufficiency(I also like to compare this AI to UBI) and thus achievement, which only means Human-in-Loop AI that can help us achieve that and that is specific to each individual, i.e. multi-atttribute value functions whose weights are learned and they change over time.

Writing about AGI and defining it to do the "best" search while not talking about what we want it to do *for us* is exactly wrong-headed for these reasons.

How would search + LLMs work together in practice?

How about using search to derive facts from ontological models, and then writing out the discovered facts in English. Then train the LLM on those English statements. Currently LLMs are trained on texts found on the internet mostly (only?). But information on the internet is often false and unreliable.

If instead we would have logically sound statements by the billions derived from ontological world-models then that might improve the performance of LLMs significantly.

Is something like this what the article or others are proposing? Give the LLM the facts, and the derived facts. Prioritize texts and statements we know and trust to be true. And even though we can't write out too many true statements ourselves, a system that generated them by the billions by inference could.

This strikes me as Lesswrong style pontificating.

The biggest issue the author does not seem aware of is how much compute is required for this. This article is the equivalent of saying that a monkey given time will write Shakespeare. Of course it's correct, but the search space is intractable. And you would never find your answer in that mess even if it did solve it.

I've been building branching and evolving type llm systems for well over a year now full time.

I have built multiple "search" or "exploring" algorithms. The issue is that after multiple steps, your original agent, who was tasked with researching or doing biology, is now talking about battleships (an actual example from my previous work).

Single step is the only real situation search functions work. Mutli step agents explode to infinite possibilities very very quickly.

Single step has its own issues, though. While a zero shot question run 1000 times (eg, solve this code problem), may help find a better solution it's a limited search space (which is a good thing)

I recently ran a test of 10k inferences of a single input prompt on multiple llm models varying the input configurations. What you find is that an individual prompt does not have infinite response possibilities. It's limited. This is why they can actually function as llms now.

Agents not working is an example of this problem. While a single step search space is massive, it's exponential every step the agent takes.

I'm building tools and systems around solving this problem, and to me, a massive search is as far off as saying all we need 100x AI model sizes to solve it.

Autonomy =/ (Intelligence or reasoning)

just came here to upvote the alphago / MCTS comments

OT but this website completely breaks arrow and page up/down scrolling, as well as alt=arrow navigation. Only mouse scrolling works for me (I'm using Firefox). Can't websites stop messing with basic browser functionality for no valid reason at all ?

A big problem with the conclusions of this article is the assumptions around possible extrapolations.

We don't know if a meaningfully superintelligent entity can exist. We don't understand the ingredients of intelligence that well, and it's hard to say how far the quality of these ingredients can be improved, to improve intelligence. For example, an entity with perfect pattern recognition ability, might be superintelligent, or just a little smarter than Terrance Tao. We don't know how useful it is to be better at pattern recognition to an arbitrary degree.

A common theory is that the ability modeling processes, like the behavior of the external world is indicative of intelligence. I think it's true. We also don't know the limitations of this modeling. We can simulate the world in our minds to a degree. The abstractions we use make the simulation more efficient, but less accurate. By this theory, to be superintelligent, an entity would have to simulate the world faster with similar accuracy, and/or use more accurate abstractions.

We don't know how much more accurate they can be per unit of computation. Maybe you have to quadruple the complexity of the abstraction, to double the accuracy of the computation, and human minds use a decent compromise that is infeasible to improve by a large margin. Maybe generating human level ideas faster isn't going to help because we are limited by experimental data, not by the ideas we can generate from it. We can't safely assume that any of this can be improved to an arbitrary degree.

We also don't know if AI research would benefit much from smarter AI researchers. Compute has seemed to be the limiting factor at almost all points up to now. So the superintelligence would have to help us improve compute faster than we can. It might, but it also might not.

This article reminds me of the ideas around the singularity, by placing too much weight on the belief that any trendline can be extended forever.

It is otherwise pretty interesting, and I'm excitedly watching the 'LLM + search' space.

I've recently matured to the point where all applications are made of 2 things, search and security. The rest is just things added on top. If you cant find it it isn't worth having.