Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

Overview§

This paper targets the fundamental problem of bounding the matrix multiplication exponent $\omega$, which is the infimum over constants $c$ such that $n \times n$ matrix multiplication can be performed in $O(n^{c+o(1)})$ field operations. The current-best bounds arise from an advanced refinement of the laser method known as combination loss analysis (Duan et al., 2022; Williams et al., 2024; Alman et al., 2025). The authors make three key contributions: (1) a reformulation of the core optimization problem that expands the search space, (2) a novel optimizer designed using modern machine learning techniques, and (3) a refinement of this optimizer using AlphaEvolve, a genetic/evolutionary algorithm from Google DeepMind. This combined approach yields the new state-of-the-art upper bound $\omega < 2.371177$, improving on the previous best of $2.371339$.

Background: The Laser Method and Combination Loss§

The laser method begins with a base tensor (e.g., a tensor power of a matrix multiplication tensor) and applies a sequence of transformations, including zeroing and combination steps. In the combination step, multiple "pieces" of a decomposed tensor are combined after applying a random permutation. The combination loss quantifies how much the combined tensor's rank (or border rank) is degraded due to non-perfect cancellation. Duan et al. (2022) showed this loss can be minimized by solving a non-convex optimization problem over a probability simplex. The objective is a complex function that reflects the final bound on $\omega$ obtained via the recursive inequality.

New Optimization Formulation§

The authors first reformulate the optimization problem to allow a larger set of candidate solutions. Specifically, instead of optimizing over a fixed simplex of piece probabilities, they introduce auxiliary variables that capture correlations between pieces and allow the optimization to search over a convex hull of possible combination strategies. This reformulation admits more degrees of freedom, potentially leading to better local optima. Mathematically, the optimization problem can be written as

$$ \max_{\theta \in \Theta} \; f(\theta) \qquad \text{where} \quad f(\theta) = 2\,\log_{d}\|T\|_{\mathrm{str}} + \text{loss terms} $$

where $\theta$ parameterizes the probability distribution over the tensor pieces and the combination loss appears via a quadratic form $Q(\theta)$ that must satisfy certain spectral conditions.

The key insight is that the previous fixed-point iteration used to solve this problem was trapped in narrow basins. By enlarging the domain, the authors obtain smoother objective geometry.

Machine-Learned Optimizer and AlphaEvolve§

To optimize the reformulated objective, the authors train a policy network that proposes update steps in the parameter space. This is reminiscent of learned optimizers in deep learning: the policy is trained offline on a distribution of similar objective landscapes (generated from random tensor decompositions) using evolutionary strategies or reinforcement learning. The learned optimizer produces updates that are more robust to the rugged, high-dimensional terrain of the combination-loss objective.

After the learned optimizer converges to a candidate solution, AlphaEvolve is applied as a refinement step. AlphaEvolve is a population-based evolutionary algorithm that maintains a set of candidate solutions and iteratively applies mutation, crossover, and selection. The key difference from standard genetic algorithms is that AlphaEvolve uses a learned mutation operator (inheriting the policy network) and a surrogate fitness model to reduce expensive evaluations. The combination of a strong local optimizer (the ML one) and a global evolutionary search (AlphaEvolve) allows the authors to escape poor local minima and find better bounds.

Results and Impact§

The resulting bound $\omega < 2.371177$ improves the previous record by about $1.6 \times 10^{-4}$. While numerically modest, every improvement in $\omega$ is significant for complexity theory and could potentially be amplified by further tensor-powering. The methodology also demonstrates that modern machine learning techniques can be fruitfully applied to pure combinatorial optimization problems in theoretical computer science.

Code Sketch§

The following is a simplified Python/PyTorch illustration of the learned optimizer plus AlphaEvolve loop. Actual implementation details are not public.

import torch
import torch.nn as nn
import numpy as np

# Policy network for proposing mutation directions
class PolicyNet(nn.Module):
    def __init__(self, dim):
        super().__init__()
        self.fc = nn.Sequential(
            nn.Linear(dim, 128),
            nn.ReLU(),
            nn.Linear(128, dim)
        )
    def forward(self, x):
        return self.fc(x)  # output mutation direction

# Objective: combination loss (simplified)
def objective(theta):
    # Placeholder for the actual combination loss function
    Q = compute_quadratic_form(theta)  # from tensor decomposition
    return torch.min(torch.linalg.eigvalsh(Q))  # spectral condition

policy = PolicyNet(dim=theta_dim)
alpha_optim = torch.optim.Adam(policy.parameters(), lr=1e-3)

# AlphaEvolve-style population loop
population = torch.randn(pop_size, theta_dim, requires_grad=True)
for gen in range(num_generations):
    scores = torch.stack([objective(theta) for theta in population])
    # Selection pressure: keep top half and mutate via policy
    _, idx = torch.topk(scores, pop_size // 2)
    elite = population[idx]
    mutations = policy(elite)  # learned mutation direction
    offspring = elite + 0.1 * torch.randn_like(elite) + 0.05 * mutations
    population = torch.cat([elite, offspring], dim=0)
    # Optionally fine-tune policy using RL to maximize offspring fitness
    loss = -objective(mutations)
    alpha_optim.zero_grad(); loss.mean().backward(); alpha_optim.step()

The actual implementation leverages large-scale distributed evolution and a carefully designed surrogate objective, but this captures the essential interplay between the learned policy and evolutionary refinement.