LLMs with search

In the early days of the field, the A.I. pioneer Allen Newell posited that much of human cognitive activity involves searching through a problem space to find a solution. This quickly became a foundation underlying what we now often refer to as “classical A.I.” Modern search techniques have led to many amazing A.I. advances, from Deep Blue to AlphaFold.

Today, deep learning networks have captured much of the attention of A.I. onlookers. GPT-4 and other LLMs are giant deep networks that respond to your prompts without any explicitly encoded search. Although these are capable of some reasoning capabilities, at least as of today, their multistep reasoning capabilities are limited.

A common approach has been appearing lately in many A.I. research papers that combines LLMs with search in order to produce more general and powerful cognitive reasoning capabilities. The common theme has been to use LLMs to propose the set of plausible actions to consider at each search node. In this capacity, the LLM acts as a subroutine to the search algorithm. Another component models the state resulting from an action choice, and a third component provides some quality feedback such as a score. These state and scoring components are sometimes built on top of an LLM, but sometimes utilize a different system. The flexibility and creativity provided by LLMs opens up many application areas previously not possible. Notable examples include ART, ORCA 2, AlphaCodium, LLM planning, Eureka, etc.

Last week, Google DeepMind published a paper in Nature on their system AlphaGeometry that illustrates this methodology. AlphaGeometry set a new state-of-the-art milestone for a computer solving hard geometry problems, solving 83% of the problems on the International Mathematical Olympiad test, compared to an average of 86% among human gold medalists and 76% among human silver medalists. A language model proposes (draws) diagrams for a problem, addressing the creative formulation stage. Once a formulation is specified, a theorem prover takes over to find the solution. GPT-4 alone is unable to solve any of the problems, and the need to figure out how to geometrically formulate a problem before mechanically finding the solution has limited the ability for computers to previously succeed at this level.