FunSearch: LLM in Math
Google DeepMind has used a large language model to crack a famous unsolved problem in pure mathematics.
DeepMind’s FunSearch, a novel AI framework, has successfully solved the cap set problem in mathematics and enhanced bin-packing algorithms, using a unique pairing of a pre-trained Large Language Model with an automated evaluator for iterative solution development.
FunSearch is built on a modified version of Google’s PaLM 2, termed Codey, optimized for code generation. It fills in missing solution components in a Python-sketched problem.
Problem
The cap set problem, an open challenge in mathematics, involves finding the largest set of points in a high-dimensional grid where no three points align linearly. It’s a complex issue representing a broader class of problems in extremal combinatorics.
Solution
The approach involved pairing a pre-trained LLM with an evaluator for program generation and refinement. FunSearch first generates a range of potential solutions. The evaluator then rigorously filters these solutions, retaining only the most accurate and viable ones. This process iteratively refines the solutions, enhancing their reliability and applicability.
“To be very honest with you, we have hypotheses, but we don’t know exactly why this works” says Alhussein Fawzi, a research scientist at Google DeepMind.
FunSearch discovered the largest cap sets known in 20 years, outperforming existing computational methods. In bin-packing, it improved upon human-devised heuristics, demonstrating its efficacy in practical algorithm optimization.
