[Working Paper] AlphaEvolve: Breaking Decades-Old Ramsey Lower Bounds via LLM-Driven Code Evolution

TL;DR

Ramsey theory—the study of order within chaos—just received a significant update from an AI agent. Using AlphaEvolve, an LLM-based code mutation framework, researchers have discovered new lower bounds for five classical Ramsey numbers, including $R(3,13)\ge 61$ and $R(4,15)\ge 159$. Unlike previous efforts that relied on "bespoke" human-coded algorithms, AlphaEvolve evolved its own search strategies, proving that AI can automate the discovery of sophisticated mathematical heuristics.

The Ramsey Challenge: Searching for Needles in an Exponential Haystack

The Ramsey number $R(r,s)$ is the smallest number of vertices $n$ such that any graph of size $n$ must contain either a clique of size $r$ or an independent set of size $s$. Finding the exact value is notoriously difficult—Paul Erdős famously joked that if aliens demanded the value of $R(5,5)$, humanity should marshal all its resources, but if they asked for $R(6,6)$, we should just hope to strike first.

The current strategy for lower bounds is computational construction: if you can build a graph of size $n$ that lacks these structures, you've proven $R(r,s)>n$. However, the search space is $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$, and existing SOTA results often come from "personal communications" featuring undocumented, specialized algorithms optimized for a single $(r,s)$ pair.

Methodology: Evolving the Search, Not Just the Solution

The core innovation is AlphaEvolve, a meta-algorithm that doesn't just look for graphs—it looks for programs that find graphs.

The AlphaEvolve Loop

1. Evolution: A population of search algorithms is maintained. An LLM (like Gemini) is prompted to mutate a high-performing parent program to create a new variant.
2. Execution: The new program runs and generates two graphs: $G_1$ (the primary candidate) and $G_2$ (a larger "prospect" graph).
3. Scoring: Programs are rewarded based on the size of $G_1$ and a "near-miss" bonus for $G_2$. If $G_2$ has fewer violations than a random baseline, the program is deemed "promising" for further evolution.

Note: The system initializes with an empty graph and forces the LLM to learn how to grow valid structures from scratch.

Evolved Insights: Four Families of Discovery

Crucially, the LLM discovered that different Ramsey numbers require different "starting points." These strategies were categorized into four families:

• Stochastic Initialization: Best for smaller cases like $R(3,5)$.
• Algebraic Seeding: Using Paley/Cubic residue graphs as a foundation for $R(4,13)$.
• Cyclic/Circulant Bootstrap: Utilizing symmetries to reduce search space for $R(3,18)$ and $R(4,14)$.
• Hybrid/Spectral Seeding: Using complex "fractal" or spectral properties for $R(3,11)$.

Case Study: $R(4,13)$

In Algorithm 4, AlphaEvolve abandoned simple random flips. Instead, it initialized with a Cubic Residue Cayley graph over $F_{127}$, implemented incremental violation tracking (avoiding full rescans), and utilized a "Strategic Kick" (forced random flips) to escape local minima in the Tabu search.

Experimental Results: Moving the Needle

The results are clear. AlphaEvolve successfully incremented the lower bounds for five classical cases:

Beyond new results, AlphaEvolve matched the SOTA for 28 other cells, often discovering "novel" search strategies that are absent from existing human literature, such as the Tabu-enhanced Local Search for R(4, 10).

Critical Analysis & Future Outlook

Why does this work? Unlike a human researcher who might stick to a familiar technique (like Simulated Annealing), AlphaEvolve explores the space of heuristics itself. It can combine "Strategic Kicking," "Harmonic Memory," and "Algebraic Seeding" in ways that are non-intuitive but computationally efficient.

Limitations: This approach is primarily for lower bounds. Establishing upper bounds (proving a graph cannot exist) requires formal methods and exhaustive verification (e.g., SAT solvers), which AlphaEvolve is not yet designed to handle.

Conclusion: This paper marks a shift from "AI helping humans" to "AI discovering algorithms." For pure mathematicians, it provides new targets. For AI researchers, it provides a blueprint for using LLMs to solve hard, objective-driven problems in the sciences.