Hillclimbing on verifiable rewards

Originally posted at sebaheg.com on 2026-09-19

History

There is a surprisingly general way to solve hard 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 celestial orbits. 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:

candidate → evaluate ─────────→ done
                │   ↑
                ↓   │
          generate candidate
                └───┘
               repeat

Hillclimbing through search

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

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

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. This is what's done in techniques like Bayesian optimisation, Monte-Carlo tree search, evolutionary algorithms and simulated annealing. That's hillclimbing¹, but without the gradients.

And the candidate $x$ doesn't even need to be a number or a vector. It could be almost anything — even a program.

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

where $\mathcal{P}$ 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 follow a few properties:

1. Verifiable reward — We can measure whether one candidate is better than another, and the measurement represents what we actually care about. Given two programs p₁ and p₂, we can reliably determine which performed better.

2. Searchable landscape — Evaluating previous candidates gives us information that helps us generate better candidates. Otherwise, the search just degenerates into blind enumeration.

3. Abundant evaluation — We can obtain trustworthy evaluations quickly enough to sustain the search. This might come from data, simulation, formal verification, or interaction with the real environment.

Verifiability tells us how good the current candidate is. Searchability tells us whether that information helps us find the next step uphill. Abundant evaluation lets us keep climbing without simply overfitting the evaluator.

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, proofs with a verifier, 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?

So the progression from our friend Cauchy finding the parameters for his planetary orbits, would be something like:

optimise parameters → optimise programs → optimise the optimiser

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