DeepMind AI outdoes human mathematicians on unsolved problem
nature.com
nature.com
Namely, what sort of computational resources had been dedicated to the problem before? Because DeepMind suddenly throwing their weight at a problem that was previously the focus of a handful of random math grad students would make it hard to benchmark the ML advance that was made here -- like would it be possible to find a similar solution with a ton of compute and more traditional genetic algorithms?
I wouldn't be surprised if the answer were no. Protein folding competition was a pretty big space in biology before getting absolutely destroyed by Alpha Fold. But I also wouldn't be entirely surprised if the answer were yes. The amount of hype around LLMs right now is crazy, probably half the news I see about them turns out to be very exaggerated upon further evaluation.
ETA: the headline here is definitely exaggerated, because there was also human in the loop to refine what the LLM was generating. At a glance the technical article doesn't benchmark enough against alternatives to the LLM component in their workflow IMO. But it is entirely possible they tackled well established enough open problems, such that prior work already handled those control cases decently.
I'd love to know what someone in this space of mathematics thinks about the paper! Would it have generated much buzz if they got these same results like 3 years ago? Would it be accepted to Nature if they found they could accomplish something similar using their framework even if it was an RNN in the loop?
From the article:
"What’s most exciting to me is modelling new modes of human–machine collaboration,” Ellenberg adds. “I don’t look to use these as a replacement for human mathematicians, but as a force multiplier.”
Haven't mathematicians been using complex computer modeling to help solve unsolved math problems since computers have existed? And havent those computers basically always beat out a human alone?
So isn't this news just that the mathematicians now have a newer and better computer model to help them solve their problems?
Seems like evolution, not revolution.
Real progress is always incremental. I wouldn't be surprised if 5-10 years from now we have similar kinds of systems discovering new materials or new candidates for dark matter.
It can work by itself too but it is unclear at a glance how well since the main focus of the paper is the new mathematical benchmarks they achieved, i.e. their best results. Will have to read the paper more closely to say anything with high confidence, but based on their summary I'd guess the human in the loop part was pretty important here.
I agree with the quote. The ability of AI to augment human capabilities has way more potential than the more speculative ideas about artificial general intelligence. This is why I'm not very sympathetic to the skepticism toward deep learning and LLMs as "not intelligence", "not real AI", "stochastic parrots", etc. Who cares whether or not these systems are generally intelligent agents, if they have the potential to increase the scientific output of humanity by even 10 or 20%?
> implementation contains an implementation of the evolutionary algorithm, code manipulation routines, and a single-threaded implementation of the FunSearch pipeline. It does not contain language models for generating new programs, the sandbox for executing untrusted code, nor the infrastructure for running FunSearch on our distributed system. This directory is intended to be useful for understanding the details of our method, and for adapting it for use with any available language models, sandboxes, and distributed systems.
> Abstract: Large Language Models (LLMs) have demonstrated tremendous capabilities in solving complex tasks, from quantitative reasoning to understanding natural language. However, LLMs sometimes suffer from confabulations (or hallucinations) which can result in them making plausible but incorrect statements [1,2]. This hinders the use of current large models in scientific discovery. Here we introduce FunSearch (short for searching in the function space), an evolutionary procedure based on pairing a pre-trained LLM with a systematic evaluator. We demonstrate the effectiveness of this approach to surpass the best known results in important problems, pushing the boundary of existing LLM-based approaches [3]. Applying FunSearch to a central problem in extremal combinatorics — the cap set problem — we discover new constructions of large cap sets going beyond the best known ones, both in finite dimensional and asymptotic cases. This represents the first discoveries made for established open problems using LLMs. We showcase the generality of FunSearch by applying it to an algorithmic problem, online bin packing, finding new heuristics that improve upon widely used baselines. In contrast to most computer search approaches, FunSearch searches for programs that describe how to solve a problem, rather than what the solution is. Beyond being an effective and scalable strategy, discovered programs tend to be more interpretable than raw solutions, enabling feedback loops between domain experts and FunSearch, and the deployment of such programs in real-world applications.
"DeepMind AI outdoes human mathematicians on unsolved problem" (2023) https://www.nature.com/articles/d41586-023-04043-w :
> Large language model improves on efforts to solve combinatorics problems inspired by the card game Set.
"The effectiveness of FunSearch in discovering new knowledge for hard problems might seem intriguing. We believe that the LLM used within FunSearch does not use much context about the problem; the LLM should instead be seen as a source of diverse (syntactically correct) programs with occasionally interesting ideas. When further constrained to operate on the crucial part of the algorithm with a program skeleton, the LLM provides suggestions that marginally improve over existing ones in the population, which ultimately results in discovering new knowledge on open problems when combined with the evolutionary algorithm.
Another crucial component of the effectiveness of FunSearch is that it operates in the space of programs: rather than directly searching for constructions (which is typically an enormous list of numbers), FunSearch searches for programs generating those constructions. Because most problems we care about are structured (highly non-random), we hypothesize that solutions are described more concisely with a computer program, compared to other representations."
It is perhaps unfair to say that DeepMind has brute-forced generating programs rather than brute-forcing a single program that generates an answer - but effectively that's what they did, and it's a very cool idea! They did the same with "DeepTensor" or whatever their program for finding matrix multiplication algorithms was called. I am not denying that this is a useful direction for computational mathematics research - I have personally spent a lot of time blindly fiddling with SAGE hoping the computer will spit out a nicer answer. Having this process automated seems useful.
But saying that this tech "outdoes human mathematicians" is pure dishonesty, very much like saying MATLAB "outdoes human physicists" at understanding fluid mechanics. FunSearch doesn't understand what a set is (or even what a number is), any more than MATLAB understands what viscosity is. LLMs are still much worse at actual quantitative reasoning than pigeons or mice, let alone humans.
I’d like to see how novel the program it generated was, rather than just being a brute force random search or a standard genetic algorithm. I have a suspicion that the bug result here is simply that it saved them coding time.