Matej Balog

Matej Balog

Auto-generated profile, based on publicly available information

Matej Balog

Google DeepMind, London, UK

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 December 2023 in Nature
Verified
Journal Article
Open access
PDF file
BRBernardino Romera-Paredes
Bernardino Romera-Paredes
MBMohammadamin Barekatain
Mohammadamin Barekatain
ANAlexander Novikov
Alexander Novikov
MBMatej Balog
Matej Balog
MKM. Pawan Kumar
M. Pawan Kumar
AFAlhussein Fawzi
Alhussein Fawzi
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 statements1,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 pretrained 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 approaches3. 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 shows that it is possible to make discoveries 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 on 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.

8 October 2026 in Science
Verified
Journal Article
Closed access
GTGeorge Tsoukalas
George Tsoukalas
AKAnton Kovsharov
Anton Kovsharov
SSSergey Shirobokov
Sergey Shirobokov
ASAnja Surina
Anja Surina
MFMoritz Firsching
Moritz Firsching
SCSwarat Chaudhuri
Swarat Chaudhuri
Large language models (LLMs) increasingly excel at mathematics tasks, but their unreliability limits their utility in mathematics research. A mitigation is to use LLMs to generate formal proofs in languages such as Lean, in which the compiler verifies every proof step. We present the first demonstration of this method’s value in solving open problems at scale. We built an artificial intelligence agent for formal proof search that autonomously resolved nine of 353 open Erdős problems, proved 44/492 On-Line Encyclopedia of Integer Sequences conjectures, and is being deployed in combinatorics, optimization, graph theory, algebraic geometry, and quantum optics research. Even a basic agent alternating LLM-based generation with Lean-based verification replicated the Erdős successes. These findings demonstrate the power of formal proof search as an enabler of autonomous mathematical discovery.