[October 2026 edition]

Indexes and the Art of Searching, Part 7: Evaluation Functions That Drive Search

Published: Oct 2, 2026
Reading time: ~12 min

Part 6 broke search algorithms down into their components. Part 7 looks at one of those components: the evaluation function, which decides where the search heads.

1. Evaluation Functions: The Other Component of Search

A search runs on two parts: something that generates candidates and a function that returns how good each candidate is. The second part goes by a different name in each field. In A* it is the heuristic function h, in two-player games the evaluation function, in evolutionary computation the fitness function, in optimization the objective function, and in reinforcement learning the reward. When an LLM generates proposals inside a search, a verifier that judges whether each proposal is correct plays the same role.

There are four ways to build such a function: simplify the problem and solve the simplified version exactly, have people design features and tune their weights, use a verifier directly as the function, or learn a surrogate.

2. Evaluation Functions from Relaxation

Relaxation is the standard way to build the h for A*. The overview by Holte and colleagues summarizes the core of Chapter 4 of Pearl’s Heuristics as using exact distances in a simplified version of the state space as estimates of distances in the original space. Relaxing means weakening or removing the conditions that restrict transitions between states. Drop the constraint that you must drive on roads, and the distance between cities becomes the straight-line distance. Drop the 15-puzzle rule that a tile can move only when it is next to the blank, and you get the Manhattan distance. Because you can move more freely in the relaxed space than in the original, every distance there is less than or equal to the corresponding distance in the original space. In car-navigation terms, the straight-line distance to the destination always comes out equal to or shorter than the route you actually drive. As we saw in Part 5, A* is guaranteed to find the shortest path when h always estimates the remaining distance at or below the true value in this way, and textbooks call that property admissible. An h built by relaxation is admissible by construction. The other property, consistency, requires that when you advance one segment to the next intersection, the estimate drops by no more than the length of that segment. With straight-line distance, driving one segment brings you closer to the destination by at most that segment’s length, so this condition holds too, and the estimate rarely shrinks abruptly mid-search and throws the ordering off. According to the same chapter, a group at the Politecnico di Milano showed before Pearl that using exact distances in a relaxed space as h yields a heuristic that is both admissible and consistent.

Relaxation has a weakness. Gaschnig pointed out that computing h by searching the relaxed space can take longer than solving the problem directly with breadth-first search and no h at all, and Valtorta later proved this formally. The result applies only to schemes that search the relaxed space every time h is needed. It does not cover schemes that precompute values and store them in a table, or relaxations such as the Manhattan distance that have a closed-form expression.

Pattern databases are the precompute-and-store approach. In Culberson and Schaeffer’s 1998 paper, on the standard set of 100 instances of the 15-puzzle, the total number of nodes searched fell from 36,302,808,031 with the Manhattan distance alone to 34,987,894 with two databases, fringe and corner, a 1038-fold reduction. Each database held 518,918,400 positions and took 520MB, and each took less than 1 hour of wall-clock time to build. Because each node costs more to evaluate, the wall-clock speedup was only about 6 times, rising to about 12 times when lookups were kept to a minimum. Korf used this method to find the first optimal solutions to random states of Rubik’s Cube.

Relaxation also supplies lower bounds for the traveling salesman problem. The problem asks for the shortest route that visits every city exactly once and returns to the start, so every city has exactly one road in and one road out, two roads in all. A lower bound is a value that every route is guaranteed to be at least as long as, and branch and bound uses it to discard unpromising branches early. The Held–Karp lower bound starts by setting one city (point p) aside and connecting the remaining cities into a tree using the cheapest combination of roads. That is the minimum spanning tree, and adding the two cheapest roads from p to it gives what is called a 1-tree. Removing p’s two roads from a tour leaves a single path, which is a tree, so a tour is a special 1-tree in which every city has exactly two roads, and the cheapest 1-tree costs no more than the shortest tour. Built naively, though, the cheapest 1-tree contains cities where three or more roads meet and cities with only one road. So the costs are adjusted: roads attached to cities with too many roads are made to look more expensive, and roads at cities with too few are made to look cheaper, which pulls the 1-tree toward the shape of a tour. Dropping a constraint you want enforced and instead adding a penalty to the cost for each violation is what textbooks call Lagrangian relaxation, and here it folds the constraint “every city has degree exactly 2” into the cost. This is regarded as giving very strong lower bounds for a limited amount of computation, and it is used in solvers such as Concorde.

3. Feature Design and Weight Tuning

A different way to build the function, used for a long time, is to have people design features and tune their weights. The chess evaluation function Shannon wrote in 1950 is the following formula.

f(P) = 200(K−K') + 9(Q−Q') + 5(R−R') + 3(B−B'+N−N') + (P−P')
       − 0.5(D−D'+S−S'+I−I') + 0.1(M−M')

K, Q, R, B, N, and P are the numbers of White’s pieces, and the primed letters are Black’s. D, S, and I are doubled, backward, and isolated pawns, and M is the number of legal moves (mobility). Shannon wrote that the coefficients 0.5 and 0.1 were merely his own rough estimates. In a position where pieces are in the middle of being exchanged, the material balance flips with the next move, so an evaluation that counts material is usable only in quiescent positions, where the exchanges have settled. Shannon therefore argued that the search should read ahead to a quiescent position before evaluating.

Samuel’s 1959 checkers program learned these weights. The evaluation was a linear polynomial. In the generalization experiments, it used 16 of 38 terms at a time, kept the rest in reserve, and swapped the least important terms for reserve ones. Two programs, Alpha and Beta, played against each other. A value obtained by looking ahead is more accurate than a static evaluation assigned from the board alone, so after each move Alpha used the difference between the two as the training signal and adjusted the polynomial’s coefficients to bring the static evaluation closer to the look-ahead value.

Handcrafted evaluation functions stayed in use for a long time. With Stockfish 12 in 2020, Stockfish added NNUE, trained on evaluations of millions of positions, to the evaluation that experts had handcrafted and tuned on fishtest, and game pairs it won outnumbered game pairs it lost by more than 10 to one. NNUE was originally devised by Yu Nasu for shogi (Japanese chess); it was merged into YaneuraOu in May 2018 and ported to Stockfish in June 2019. According to the official documentation, the training targets mix the search’s evaluation scores with actual game results. The handcrafted evaluation was removed in Stockfish 16.

Shannon’s point comes back when choosing which positions to train on. A study of an engine for xiangqi (Chinese chess) uses only quiescent positions as training data. In TD-Gammon, a network with 40 hidden units, given only the raw board as input, reached intermediate-player strength after 200,000 games of self-play. Adding Neurogammon’s handcrafted features improved its results further.

4. Verifiers as Evaluation Functions

For problems where correctness can be checked cheaply and exactly, the checking procedure itself becomes the evaluation function. FunSearch checks the proposals an LLM produces with an automated evaluator. The evaluator rejects hallucinated and incorrect proposals, and the user supplies the procedure for evaluating programs as part of the problem specification. AlphaEvolve applies the same idea to evolving programs and found an algorithm that multiplies two 4×4 complex-valued matrices using 48 multiplications.

A verifier has to meet three requirements: few false positives, meaning it rarely accepts a wrong proposal as correct; low cost, so that the search can run many generations; and partial credit, so that it gives the search something to follow. The requirement most easily broken is the first, a low false-positive rate, and the next section covers examples.

5. Holes in Evaluation Functions and Countermeasures

The stronger the search, the more easily it finds holes in the evaluation function. The 2016 paper by Amodei and colleagues organized accidents caused by a wrong objective function into the problems of side effects and reward hacking. DeepMind’s collection of examples includes an agent in a lap-based racing game that, instead of going around the track, scored points by repeatedly hitting the same green blocks, and an agent rewarded for the height of the bottom face of a red block that flipped the block over instead of lifting it and stacking it.

Adding reward terms to speed up learning works only under certain conditions. Take the example of heading for a destination on a map. Adding points for moving closer and subtracting points for moving away gives the learner more to go on. But if you only add points for moving closer, a path that goes back and forth and collects the bonus again and again comes out ahead, and you get the same kind of shortcut as in the racing game. The fix is to assign each point on the map a “height” Φ that grows as you get closer to the destination, and to add to the reward, at each step, the difference between the height of the new location and the height of the old one. Then, when you go around a loop and return to where you started, what was added and what was subtracted cancel out, so detours cannot earn points, and the best way to choose actions (the optimal policy) stays the same as under the original reward. A theorem in the 1999 paper by Ng and colleagues shows that this form, in which the added shaping reward is the height difference with the discount factor γ applied, γΦ(s′) − Φ(s), is a necessary and sufficient condition for preserving the optimal policy. The paper calls Φ a potential function. The necessity direction means that the only way of adding reward that preserves the optimal policy for every map and every original reward is this height-difference form. The paper also notes that shaping potentials can be built from distance-based heuristics, so the same kind of function as A*‘s h shows up here as well.

An evaluation function learned as a surrogate has a limit on how far you can safely optimize against it. The 2022 paper by Gao and colleagues used a fixed reward model as the stand-in for ground truth, trained a separate proxy reward model, and optimized against the proxy with reinforcement learning or best-of-n. Best-of-n generates n proposals and picks the one the proxy scores highest. The more you optimize, the further the model’s outputs drift from those of the initial model, so the paper measured the amount of optimization as d, the square root of the KL divergence that quantifies this drift. The ground-truth reward then followed d(α − βd) for best-of-n and d(α − β log d) for reinforcement learning. Both rise with d at first, but as d grows the subtracted term inside the parentheses takes over, so if you keep optimizing the proxy, past some point the ground-truth reward starts to fall.

Even verifiers get broken. In 2025, Tao and colleagues, drawing on their experience applying AlphaEvolve to 67 mathematical problems, described cases where holes in the verifier were exploited. When approximation tolerance was allowed, the holes were used by placing many points at almost the same location to blur distance checks, by abusing floating-point behavior, and by exploiting the way a linear programming solver fails. The countermeasures they list are interval arithmetic and exact computation, conservative bounds that assume the worst case, and checks that inputs lie within the permitted range. In 2026, a study of models trained with verifiable rewards exploiting their verifiers appeared. On inductive reasoning tasks, GPT-5 and Olmo3 stopped inducing the rule and instead earned reward by enumerating individual labels that passed the verifier. This behavior did not appear in GPT-4o or GPT-4.5, and it increased with task complexity and with more test-time compute. Replacing verification that checks only individual examples with verification that also applies isomorphic transformations made the shortcut disappear.

Shannon’s restriction that the evaluation is usable only in quiescent positions is the same kind of problem: an evaluation function must be used only within its domain. Building an evaluation function is not the end of the job. Deciding which inputs it is valid for, and checking that the inputs you actually pass fall within that range, remains ongoing work after the function is built.

Part 8 turns to how to choose among the methods covered so far, from the way published settings are tuned to their evaluation data, through the budget that algorithm selection itself consumes, to a decision tree for large-scale data.