FunSearch

FunSearch is a fascinating technique that merges the creative abilities of large language models (LLMs) with traditional computational search methods. Think of it as having an endlessly imaginative assistant (the LLM) that suggests new ways to solve a problem, and then a super-fast grader (the computational search) that checks how good those suggestions actually are.

The core idea behind FunSearch is to use an LLM not just to generate text, but to generate actual computer code, specifically algorithms. An algorithm is a step-by-step procedure for solving a problem, like a recipe for a computer. FunSearch first describes a problem to the LLM, asking it to come up with potential solutions as code. These generated code snippets are then run and evaluated by a separate process. The best performing codes are fed back to the LLM, acting as examples to guide it to produce even better solutions in subsequent attempts.

This process is called an _iterative search_ because it involves repeated cycles of generation, evaluation, and refinement. The LLM gets smarter at creating algorithms based on the feedback it receives, much like a student learns by seeing examples of good work. This feedback loop is what allows FunSearch to explore a vast number of possibilities and converge on highly optimized solutions.

For example, FunSearch has been used successfully to discover more efficient algorithms for problems like finding caps, which is a mathematical search problem in number theory. It starts with simpler, known algorithms, and through its iterative process, the LLM proposes variations and improvements. These improvements are then tested, and the most successful ones become the starting point for the next round of generation.

A common misconception might be that the LLM itself is doing all the problem-solving and evaluation. In reality, the LLM is more like a creative brainstormer. The critical part is the external evaluation and the feedback loop, where the actual performance of the generated code is measured. This combination of creative AI and rigorous computational testing is what makes FunSearch such a powerful tool for discovering new algorithms.