Great post! Two thoughts that came to mind while reading it:
the post mostly discussed search happening directly within the network, e.g. within a single forward pass; but what can also happen e.g. in the case of LLMs is that search happens across token-generation rather than within. E.g. you could give ChatGPT a chess constellation and then ask it to list all the valid moves, and then check which move would lead to which state, and if that state looks better than the last one. This would be search depth 1 of course, but still a form of search. In practice it may be difficult because ChatGPT likes to give messages only of a certain length, so it probably stops prematurely if the search space gets too big, but still, search most definitely takes place in this case.
somewhat of a project proposal, ignoring my previous point and getting back to “search within a single forward pass of the network”: let’s assume we can “intelligent design” our way to a neural network that actually does implement some kind of small search to solve a problem. So we know the NN is on some pretty optimal solution for the problem it solves. What does (S)GD look like at or very near to this point? Would it stay close to this optimum, or maybe instantly diverge away, e.g. because the optimum’s attractor basin is so unimaginably tiny in weight space that it’s just numerically highly unstable? If the latter (and if this finding indeed generalizes meaningfully), then one could assume that even though search “exists” in parameter space, it’s impractical to ever be reached via SGD due to the unfriendly shape of the search space.
Aren’t LLMs already capable of two very different kinds of search? Firstly, their whole deal is predicting the next token—which is a kind of search. They’re evaluation all the tokens at every step, and in the end choose the most probable seeming one. Secondly, across-token search when prompted accordingly. Say “Please come up with 10 options for X, then rate them all according to Y, and select the best option” is something that current LLMs can perform very reliably—whether or not “within token search” exists as well. But then again, one might of course argue that search happening within a single forward pass, and maybe even a type of search that “emerged ” via SGD rather than being hard baked into the architecture, would be particularly interesting/important/dangerous. We just shouldn’t make the mistake of assuming that this would be the only type of search that’s relevant.
I think across-token search via prompting already has the potential to lead to the AGI like problems that we associate with mesa optimizers. Evidently the technology is not quite there yet because PoCs like AutoGPT basically don’t quite work, so far. But conditional on AGI being developed in the next few years, it would seem very likely to me that this kind of search would be the one that enables it, rather than some hidden “O(1)” search deeply within the network itself.
Edit: I should of course add a “thanks for the post” and mention that I enjoyed reading it, and it made some very useful points!