Skip to content

Program Search via Tree Search

Summary

Program search via tree search is an AI-driven methodology that frames software engineering and algorithm design as a search problem over a space of programs. Unlike traditional genetic programming which relies on syntactic mutations (e.g., syntax tree adjustments), this approach uses large language models (LLMs) to generate semantic code mutations. The exploration of these code candidates is guided by search algorithms such as predictor-based Upper Confidence Bounds (PUCT) to balance exploitation of successful programs with exploration of new code structures.

Methodology

In a tree-search guided program search framework, the search space is structured as a tree where: - Nodes represent individual programs or code candidate solutions. - Edges represent code mutations or rewrites generated by an LLM in response to a prompt. - Scores represent the evaluation of a candidate program on a validation dataset.

The selection of which code node to expand next is typically governed by a PUCT (polynomial upper confidence trees) acquisition score: $$\text{PUCT}i = r_i + c$$ where: - $r_i$ is the rank-scaled score of node $i$. - $c_{\text{puct}}$ is a tuning parameter controlling the exploration constant. - $P(i)$ is a prior probability assigned to the candidate node. - $N_{\text{total}}$ is the total number of visits across all nodes in the search tree. - $V(i)$ is the visit count of node $i$.}} \times P(i) \frac{\sqrt{N_{\text{total}}}}{1 + V(i)

When a node is selected, the LLM is prompted with the corresponding code, execution feedback (such as error logs or performance metrics), and optional research guidance to write a mutated child version. The child is executed in a secure sandbox, assigned a validation score, and appended to the tree, and the visit count is backpropagated to its ancestor nodes.

Applications

This methodology has been implemented in several AI systems for scientific discovery: - Empirical Research Assistance (ERA): Uses a modified PUCT tree search to write expert-level empirical software across genomics, epidemiology, and time-series forecasting. - FunSearch: Pairs a language model with an evolutionary algorithm to find new mathematical discoveries by writing and evaluating programs. - AlphaEvolve: An evolutionary coding loop designed for scientific and algorithmic discovery.

Citations

  • Aygün, E., et al. (2026). An AI system to help scientists write expert-level empirical software. Nature, 654, 909–915. DOI: 10.1038/s41586-026-10658-6. Source paper: s41586-026-10658-6.pdf
  • Silver, D., et al. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529, 484–489. DOI: 10.1038/nature16961