Inside FunSearch: Google DeepMind’s New LLM that is Able to Discover New Math and Computer Science Algorithms

Author(s): Jesus Rodriguez

Originally published on Towards AI.

I recently started an AI-focused educational newsletter, that already has over 160,000 subscribers. TheSequence is a no-BS (meaning no hype, no news, etc) ML-oriented newsletter that takes 5 minutes to read. The goal is to keep you up to date with machine learning projects, research papers, and concepts. Please give it a try by subscribing below:

Discovering new science might be most complete Turing Test for the AI models. New scientific methods require complex reasoning skills, combining knowledge from many fields, constant experimentation and evaluation, and many other complex cognitive skills. Google DeepMind has been one of the AI labs pushing the frontiers of using AI to streamline our path to new scientific discoveries. Models such as AlphaGo has enabled the discovery of new proteins while AlphaTensor was able to improve classic matrix multiplication algorithms. Google DeepMind’s newest iteration in this area is FunSearch, a model that was able to create new mathematics and computer science algorithms.

FunSearch provides a clever approach to discover new algorithms by “thinking in code”. Essentially, FunSearch uses an LLM to generate computer programs based on a set of functions for a given problem and then uses an evaluator to prove the different solutions. The FunSearch named is derived from the fact that the model iteratively searches the function space.

Inside FunSearch

FunSearch is based on a combination of evolutionary methods and Language Models (LLMs) to refine and enhance the best programming ideas. This process starts with a user-defined problem, presented in the form of code, which includes an evaluation procedure and a seed program. This seed program kickstarts a collection of programs for further development.

FunSearch is based some a series of key components:

1. Problem Specification: Users provide a problem in the form of an ‘evaluate’ function, which rates potential solutions. An initial, often simple, program is also included to begin the evolution process.

2. Pre-Trained LLM: FunSearch relies on Codey, built on the PaLM2 model family. Codey, which has undergone extensive training on a vast array of code, is pivotal in suggesting enhancements to functions. Remarkably, Codey operates without any specific training tailored to the problems at hand.

3. Evaluation: This component of FunSearch involves scoring programs generated by the LLM based on certain inputs. For instance, in dimensional or combinatorial optimization problems, these inputs vary according to the specific requirements of the task.

4. Programs Database: This database maintains a diverse collection of accurate programs, which are crucial for generating new prompts and avoiding local optima in the evolutionary process.

5. Prompt: FunSearch uses a method called ‘best-shot prompting,’ which involves selecting and ranking programs from the database based on their performance. Each program is assigned a version number based on its score.

6. Distributed System: This component of FunSEarch comprises three main components: a program database, samplers, and evaluators, all working asynchronously. The database stores and dispenses programs, samplers use the pre-trained LLM to create new functions, and evaluators judge the efficacy of these programs. This intricate system, illustrated in their supplementary information, showcases the comprehensive and dynamic approach of Google DeepMind in advancing the field of program evolution.

FunSearch in Action

To evaluate FunSearch, Google DeepMind decided to tackle some iconic problems in both math and computer science.

Problem 1: Cap Set Problem

The first challenge was the cap set problem, a long-standing puzzle in the mathematical community. This problem involves identifying the largest group of points in a high-dimensional grid such that no three points form a straight line. Collaborating with mathematics professor Jordan Ellenberg from the University of Wisconsin–Madison, who made a significant breakthrough in this area, Google DeepMind tackled this problem, which has implications in extremal combinatorics. Traditional computing methods falter here due to the astronomical number of possibilities, surpassing even the total number of atoms in the universe.

FunSearch’s achievement in this area was remarkable. It generated programs that discovered the largest cap sets known to date, marking the most substantial progress in this field in over two decades. Not only did it achieve this feat, but it also surpassed the capabilities of the most advanced computational solvers available, demonstrating its superior efficiency in handling complex mathematical challenges.

Problem 2: Bin Packing

The second problem Google DeepMind addressed with FunSearch was the practical and widely relevant bin packing problem. This problem involves efficiently packing items of varying sizes into the least number of bins possible, a task central to numerous real-world applications, from logistics to data center management. Typically, this problem is approached with heuristic rules based on human experience, which can vary greatly depending on the specific requirements of each case.

FunSearch proved its adaptability once again. Setting it up for the bin packing problem was straightforward despite its significant difference from the cap set challenge. The tool excelled by creating a custom program tailored to the specific details of the task at hand. This program outperformed traditional heuristics, achieving more efficient packing with the use of fewer bins. This success highlighted FunSearch’s flexibility and potential to revolutionize problem-solving in various domains.

FunSearch represents one of the most interesting papers published this year and one that highlights the potential of LLMs applied to the discovery of new science. The discovery of new algorithms in math and computer science is, in and out itself, a remarkable achievement, but the principles of FunSearch apply to many other areas of science.

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI