Google DeepMind's LLM System Unlocks Novel Combinatorial Solutions
This represents the first discoveries made for established open problems using LLMs.
The system finds a computer program that outputs a new lower bound on the cap set problem, an open problem in combinatorics of genuine interest to the mathematical community. The system uses a code-generation LLM (not even fine-tuned) together with a genetic algorithm to iteratively generate and refine a lot of programs (on the order of 1 million) that output solutions. Each solutions is evaluated and scored. If a program passes (in the sense of producing an output that satisfies the constraints of the combinatorial problem) and scores well, it's saved and can be sampled and iterated upon in the future. This is significant scientifically, and the bin-packing problem actually has real-life applications, e.g., in logistics. But the approach is limited to a problems where solutions can be:
evaluated (binary pass/ fail) quickly
meaningfully scored (not just binary)
This is a really cool technique for exploring solution spaces at scale, but it's not for proving theorems. I could imagine pure mathematicians using this sort of thing to empirically test hypotheses on certain kinds of problems. Maybe copilot for mathematicians?