Cheng Tan

Everything Is a Search Problem

Second in the series — Nothing New Under the Sun — on the handful of ideas computer science keeps rediscovering under new names

· systemsaiphilosophy ·中文

The first entry in this series was about never paying full price for the same work twice. This one is about the idea hiding inside more papers than any other, usually without being named. Strip a systems contribution down to its skeleton and, more often than not, you find the same two-part object: a space of candidate answers, and a procedure for walking that space. Search.

The two parts are worth holding apart, because they are the two places a contribution can live. The space is what answers are expressible at all—every schedule you could emit, every plan you could execute, every order you could impose. The walker is how you move through it: greedily, exhaustively, randomly, cleverly. AlphaGo is the cleanest calibration of the distinction I know. The space of Go is fixed by the rules—roughly 250 legal moves per position, games about 150 moves deep, some 2×10^170 legal board positions. What got built was a better walker: a tree search whose breadth is narrowed by a policy network and whose depth is cut short by a value network. Against Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue had against Kasparov. The triumph was not searching more. It was searching less, better.

Hold “space” and “walker” apart like that, and a remarkable amount of systems research sorts itself into contributions to one, the other, or both.

Scheduling: the search problem that never dies

Start with the field’s perennial. Scheduling and resource allocation have been officially hopeless since 1975, when the general problem was proved NP-complete—and they are completely unavoidable, which is why every generation of systems researchers meets them again in new clothes. Look at what “new clothes” actually means, and it is always the same thing: the space changed. A new workload mints a new one: the cloud made candidate placements elastic, serverless made them ephemeral, LLM serving welded them to GPU memory. New hardware reshapes the space, opening trade-offs that were not there before. And a new objective re-weights it: optimize for power or carbon instead of latency alone—same machines, same jobs, a new definition of “better”—and suddenly the old walks land in different places.

One vivid example is a piece of my own work, built around NVIDIA’s Multi-Instance GPU (MIG). MIG lets one physical GPU be partitioned into instances of different sizes, which quietly breaks a founding assumption of scheduling: the machine is no longer a fixed vessel. Its shape is one of the things you choose. We called the abstract version the reconfigurable machine scheduling problem—NP-hard, naturally—and walked it with a pipeline of walkers: greedy search, a genetic algorithm, and, fittingly, Monte Carlo tree search. The follow-ups are legible the same way: a theory paper that pins down how well any walker can do in this space, and a system that searches utility-first and reconfigures the cluster. Three papers, one sentence each: here is the new space; here is the bound on what any walker can do in it; here is a walker that survives in practice.

Checking is searching too

Verification looks like the opposite of all this—no candidates, no exploration, just a verdict. Flip the quantifier and the resemblance snaps into place. My clearest example is my own: Cobra checks whether a black-box database behaved serializably, and the definition of “serializable” is existential—a history passes if there exists a serial order of its transactions consistent with every read and write you observed. Checking is searching for that witness, in a space that is NP-complete to walk. We did not hand-craft the walker; we handed the space to an SMT solver built for graph problems, and spent our own effort shrinking the space before the solver ever saw it. An earlier post argued that correctness for AI has the same existential shape: an output is correct when some legitimate run explains it. Same object again. To accept is to find one witness; to reject is to exhaust the space. Verification is search with the stakes inverted.

From insight to solver

Now watch what happened to the walkers over thirty years, because the field changed its habits and barely remarked on it.

The classic systems paper walked the space by hand: stare at the problem, find the insight, freeze the insight into a heuristic, and let evaluation bless it. The newer paper does something different: state the problem as a principled formulation—a min-cost flow for cluster scheduling, a mixed-integer program for space-time placement, a knapsack that has been running in production behind Google’s flash cache for years—and then pay a general-purpose walker to do the walking. That became possible because the walkers industrialized: SAT solvers turned practical in the late nineties, SMT solvers put entire theories behind a single interface, and “NP-hard” quietly stopped meaning “write a heuristic” and started meaning “call a solver.” The hardness never moved. What moved is that exponential-in-the- worst-case became livable-in-the-observed-case, once the walker was somebody else’s decade of engineering.

I don’t want to overstate the split—the formulation still takes insight, and plenty of excellent systems remain hand-made. But the trend is clear: we stopped carving walkers and started renting them.

The machine that searches for searchers

Which brings in AI, and the oldest claim in that field. This is not folklore: it is the hypothesis Newell and Simon put at the center of their Turing Award lecture. “A physical symbol system exercises its intelligence in problem solving by search—that is, by generating and progressively modifying symbol structures until it produces a solution structure.” Intelligence, on this view, is not decorated by search; it operates by search. Fifty years later the field’s sharpest self-criticism says the same thing from the other side: the bitter lesson of seventy years of AI is that the only methods that scale with computation are search and learning.

So when AI finally entered systems research in force, it was never going to be an alien arrival; it was search meeting search. The interesting part is where it entered. It did not join the walk through solution space. It moved one level up. FunSearch—the name is literal, “searching in the function space”—pairs a language model with an evaluator and, in its authors’ words, “searches for programs that describe how to solve a problem, rather than what the solution is.” AlphaEvolve, its industrial descendant, evolved the scheduling heuristic that has been packing Google’s fleet in production for over a year. The model does not emit a schedule. It emits a scheduler. Call the pattern a meta-solver: the search no longer returns an answer, consumed once; it returns a walker, amortized forever. Readers of the first entry will recognize the economics—an answer is spent, a solver is kept, and the second time is cheaper.

The level you dare to search at

Step back and the thirty-year arc is one motion, repeated. First we searched for answers, by hand. Then we searched for formulations, and rented the walking. Now we search for the searchers themselves. The space changes, the walker changes, the level changes—the move never does. If Newell and Simon were right that intelligence just is this move, then the history of computing has been the history of climbing one level up it at a time, handing the level below to a machine.

So the old line holds; nothing new under the sun. But let me be accurate about the slogan. “Everything is a search problem” does not mean everything is brute force—AlphaGo won by evaluating less than Deep Blue. The whole game, at every level, has always been the same: knowing where not to look.

References