Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing
Rasul Tutunov, Alexandre Maraval, Antoine Grosnit, Xihan Li, Jun Wang, Haitham Bou-Ammar
2025-12-05
Summary
This paper tackles the incredibly difficult problem of figuring out how to pack spheres together in the most efficient way in different dimensions, a question known as Hilbert's eighteenth problem.
What's the problem?
The core issue is that finding the densest way to arrange spheres isn't solved for most dimensions. Even when researchers make progress, like in 8 dimensions, it's extremely challenging. A common method for finding limits on how dense the packing can be involves complex computer calculations called semidefinite programs, but these calculations take a very long time – sometimes days for just one attempt – making it impossible to use typical 'brute force' AI methods that require tons of data and calculations.
What's the solution?
The researchers approached this problem by framing the creation of these complex calculations as a game. They used a smart AI strategy that learns from its previous attempts, combining Bayesian optimization and Monte Carlo Tree Search. This allowed the AI to efficiently explore different ways to build the calculations, ultimately finding better upper bounds for sphere packing density in dimensions 4 through 16.
Why it matters?
This work shows that AI doesn't always need massive amounts of data to make breakthroughs in difficult math problems. Instead, a more thoughtful, learning-based approach can be effective even when each calculation is slow and expensive. This suggests a new direction for using AI to assist in mathematical discovery, complementing the current focus on large language models.
Abstract
Sphere packing, Hilbert's eighteenth problem, asks for the densest arrangement of congruent spheres in n-dimensional Euclidean space. Although relevant to areas such as cryptography, crystallography, and medical imaging, the problem remains unresolved: beyond a few special dimensions, neither optimal packings nor tight upper bounds are known. Even a major breakthrough in dimension n=8, later recognised with a Fields Medal, underscores its difficulty. A leading technique for upper bounds, the three-point method, reduces the problem to solving large, high-precision semidefinite programs (SDPs). Because each candidate SDP may take days to evaluate, standard data-intensive AI approaches are infeasible. We address this challenge by formulating SDP construction as a sequential decision process, the SDP game, in which a policy assembles SDP formulations from a set of admissible components. Using a sample-efficient model-based framework that combines Bayesian optimisation with Monte Carlo Tree Search, we obtain new state-of-the-art upper bounds in dimensions 4-16, showing that model-based search can advance computational progress in longstanding geometric problems. Together, these results demonstrate that sample-efficient, model-based search can make tangible progress on mathematically rigid, evaluation limited problems, pointing towards a complementary direction for AI-assisted discovery beyond large-scale LLM-driven exploration.