Hillclimbing on verifiable rewards

Guess, measure, improve

There is a surprisingly general way to solve difficult problems in mathematics: make a guess, measure how good it is, and use what you learned to make the next guess. You don’t need to know the answer in advance. You just need a way to tell whether you’re getting better or not.

This idea is called hillclimbing - you're climbing the objective landscape towards its (hopefully global) optimum. In 1847, Augustin-Louis Cauchy gave an early mathematical formulation while working on determining the parameters of celestial orbit equations. His move was to turn solving into improving: start with a candidate answer, measure its error, change it in a direction that reduces the error, and repeat until you have a satisfactory result:

guess → evaluate → improve → repeat

Hillclimbing through search

Classical optimisation is about finding the optimal input value (or vector) to an objective function:

x^* = \operatorname*{arg\,max}_{x \in \mathcal{X}} f(x)

Which optimisation technique works best depends on what we know about the objective function $f$ and the search space $\mathcal{X}$ . If the search space is discrete and small, we can just enumerate all solutions and compare. If the problem has useful mathematical structure, we may be able to exploit it directly. For instance, the Simplex algorithm in linear optimisation exploits the fact that, when a finite optimum exists, one can be found at a vertex of the feasible polytope. It moves between neighbouring vertices that improve the objective until none do. I remember iteratively solving linear optimisation problems with the Simplex algorithm by pen and paper - fun times!

If $f$ is differentiable and we have access to its derivatives, we can use gradient descent to tell us which direction locally improves the objective (which is what Cauchy did). If we don't have access to the gradient but can cheaply evaluate $f$ at small perturbations of $x$ , we may be able to approximate it numerically. If all we can do is evaluate $f(x)$ (black-box optimisation), we can instead treat optimisation as a search problem: generate candidates, evaluate them, and use the results to decide where to search next. I remember a Google Research project where they optimised a chocolate chip cookie recipe based on human taste ratings, that's pretty "gradient-free". For these situations, people use techniques like Bayesian optimisation, Monte-Carlo tree search, evolutionary algorithms and simulated annealing. That's hillclimbing¹, but without the gradients.

Search-based optimisation also lets us move beyond numerical search spaces. The candidate $x$ could be a Chinese character, a chess move, a prompt or even a program. As long as we can generate candidates and evaluate them with $f(x)$ , we have something to optimise.

Searching over programs

Searching over programs isn't new. Fields like program synthesis and genetic programming have been doing this for decades: define an objective, search over programs, and evaluate how well they achieve it.

But historically, this has been difficult because generating useful program modifications has been hard. We now have a tool that is remarkably good at generating programs: the large language model (LLM). Instead of generating programs from a fixed grammar or predefined mutation operators, an LLM can read a program, understand its context, inspect how previous attempts performed, and propose a new program that it expects to do better.

We can therefore think of optimisation as searching directly over a space of programs:

x^* = \operatorname*{arg\,max}_{x \in \mathcal{X}} \operatorname{evaluate}(\operatorname{run}(x))

where $\mathcal{X}$ now is the space of possible programs.

But being able to search over programs doesn't mean we can search them effectively. Some problems are much more hillclimbable than others.

Suitable problems

For hillclimbing programs through search to work well, the problem needs to have a few properties:

Verifiability — We can measure whether one candidate is better than another, and the measurement represents what we actually care about. We're able to sample the verifier quickly enough and a lot of times so to gather a lot of data about what good looks like.
Searchable landscape — Evaluating previous candidates gives us information that helps us generate better candidates. Otherwise, the search would just degenerate into blind enumeration.

Verifiability tells us how good the current candidate is. Searchability tells us whether that information helps us find the next step uphill.

This makes for a good solution method when solutions are hard to generate but easy to verify. Code can be checked with tests and benchmarks, math proofs with a formal verifier like Lean, games by their score, and optimisation algorithms by the solutions they produce.

The LLM doesn't need to know whether its proposed program is better. It only needs to propose promising candidates. The environment tells us which ones actually worked.

Hillclimb the hillclimbing

Here, we've treated the program generating new candidates as fixed. But that generator is, of course, itself just another program. If we can hillclimb programs, why not hillclimb the program doing the hillclimbing? The progression from our friend Cauchy fitting his planetary orbits would then be something like:

optimise parameters → optimise programs → optimise the optimiser

Such a system is no longer just searching for better solutions. It is searching for better ways to search for better solutions.

We use hillclimbing in the broad sense here, meaning using reward feedback to generate new candidate solutions. Not every step has to be strictly uphill. ↩