🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

Este artículo mejora el límite superior del exponente de la multiplicación de matrices $\omega$ a menos de 2.371177 mediante la reformulación del problema de optimización subyacente y la mejora del proceso de solución con técnicas modernas de aprendizaje automático y AlphaEvolve.

Autores originales: Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

Publicado 2026-08-18

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el vasto paisaje de la informática, pocas operaciones son tan fundamentales como multiplicar dos grandes cuadrículas de números, un proceso conocido como multiplicación de matrices. Esta tarea matemática sustenta desde el entrenamiento de modelos de inteligencia artificial hasta la renderización de imágenes realistas en videojuegos. Durante décadas, los científicos han sabido que esta operación puede realizarse más rápido que con el método estándar y directo, pero el límite preciso de qué tan rápido puede llegar a ser ha seguido siendo uno de los misterios más obstinados del campo. Este límite se describe mediante un único número, un exponente matemático que dicta cómo crece el tiempo requerido para el cálculo a medida que aumenta el tamaño de las cuadrículas. Cuanto menor sea este número, más eficiente podrá ser la computadora. Aunque se sabe que el mínimo teórico es al menos dos, el mejor límite superior probado ha rondado ligeramente por encima de 2.37 durante años, una barrera que los investigadores han ido erosionando con herramientas matemáticas cada vez más sofisticadas.

Un equipo de investigadores de Google DeepMind, junto con colaboradores de varias universidades, ha logrado empujar este límite un poco más allá. Al combinar técnicas de optimización modernas con una nueva forma de inteligencia artificial, han establecido un nuevo récord, demostrando que el exponente puede reducirse a menos de 2.371177. Este es un cambio numérico pequeño, pero en el contexto de este problema específico, representa un paso significativo hacia adelante. El resultado anterior, alcanzado en 2025, se situaba en 2.371339. El nuevo hallazgo no resuelve el misterio definitivo del límite exacto, ni cambia inmediatamente la forma en que las computadoras multiplican matrices en la práctica, pero estrecha las restricciones teóricas del problema, mostrando que el techo es más bajo de lo que se pensaba posible.

El camino hacia este nuevo récord comenzó con un marco matemático conocido como el método láser, una técnica desarrollada hace más de cuarenta años para diseñar algoritmos de multiplicación de matrices de forma indirecta. El refinamiento más reciente de este método, llamado análisis de pérdida de combinación, depende de la resolución de un problema de optimización masivo y complejo. Este problema consiste en encontrar la mejor manera de descomponer una gran estructura matemática en piezas más pequeñas. Los investigadores descubrieron que la dificultad de este problema depende de un parámetro que representa la profundidad de la descomposición. Los intentos anteriores se habían detenido en una profundidad de tres, lo que limitaba el número de variables que podían ajustarse. El nuevo equipo se dio cuenta de que, al aumentar esta profundidad a cuatro, podrían explorar un espacio de posibilidades mucho mayor, pero hacerlo requeriría resolver un problema con millones de variables, una tarea demasiado grande para los algoritos tradicionales utilizados en el pasado.

Para abordar esta escala, los investigadores recurrieron a técnicas tomadas del aprendizaje automático. En lugar de utilizar solvers matemáticos estándar, reformularon el problema para que pudiera ser manejado por el descenso de gradiente, un método comúnmente utilizado para entrenar redes neuronales. Este enfoque les permitió utilizar potentes hardware de computación para procesar los datos en paralelo, manejando la explosión de complejidad que trajo consigo la descomposición más profunda. Trataron las variables matemáticas como si fueran los pesos ajustables en un modelo de aprendizaje, refinándolos iterativamente para encontrar una mejor solución. Este cambio de estrategia por sí solo mejoró el límite en una cantidad mensurable, demostrando que las herramientas computacionales modernas podían desbloquear un potencial que los métodos más antiguos habían pasado por alto.

Sin embargo, el equipo no se detuvo ahí. Emplearon un sistema llamado AlphaEvolve, una inteligencia artificial diseñada para escribir y mejorar su propio código. En lugar de simplemente ejecutar el algoritmo de optimización, dejaron que la IA modificara el algoritmo mismo. El sistema generaba una nueva versión del código, la ejecutaba para ver qué límite producía y luego evolucionaba el código aún más para minimizar ese límite. Este proceso de automejoramiento permitió a los investigadores encontrar refinamientos sutiles en la estrategia de optimización que un equipo humano podría haber pasado por alto. El resultado de esta evolución automatizada fue una mejora adicional, empujando el límite hacia el nuevo récord de 2.371177.

Para asegurar que este resultado no fuera un artefacto de errores de redondeo de la computadora o imprecisiones de punto flotante, el equipo realizó un paso de verificación riguroso. Tomaron la solución encontrada por sus algoritmos y convirtieron todos los números en fracciones exactas, realizando los cálculos finales con precisión perfecta. También reemplazaron cada logaritmo en las ecuaciones con un límite racional seguro que garantizara que se cumplieran las restricciones. Este proceso de certificación cuidadosa confirmó que el nuevo límite es matemáticamente válido y está libre de la contaminación numérica que suele afectar a tales computaciones complejas.

Los investigadores señalan que, si bien su enfoque ha producido un mejor límite, las mejoras son cada vez más difíciles de lograr. Las ganancias que obtuvieron son comparables en magnitud al progreso incremental visto en los últimos cuarenta años. Sugieren que, aunque es posible lograr más mejoras modestas continuando con el refinamiento de estas técnicas de optimización, alcanzar un salto mucho mayor en la comprensión del límite real probablemente requerirá ideas matemáticas completamente nuevas. Por ahora, el trabajo se erige como un testimonio del poder de combinar la matemática teórica profunda con la fuerza computacional del aprendizaje automático moderno, demostrando que incluso en un campo con una larga historia, todavía hay espacio para el descubrimiento.

Resumen Técnico: Mejora del exponente de la multiplicación de matrices con optimización moderna y AlphaEvolve

Planteamiento del problema
La complejidad computacional de la multiplicación de matrices, caracterizada por el exponente $\omega$ donde dos matrices de $n \times n$ pueden multiplicarse en $O(n^{\omega + o(1)})$ operaciones, sigue siendo una cuestión abierta fundamental en la informática teórica. Si bien el avance de Strassen en 1969 estableció que $\omega < 2.81$ , el límite superior actual más ajustado es $\omega < 2.371339$ (Alman et al., 2025). Este límite se deriva de un refinamiento del "método láser" conocido como análisis de pérdida de combinación (combination loss analysis). El núcleo de este enfoque consiste en resolver un problema de optimización no convexo complejo. La dificultad radica en el compromiso entre la complejidad de la optimización (que crece de forma doble exponencial con el nivel de recursión $\ell^*$ ) y la precisión del límite resultante. Los resultados previos del estado del arte (SOTA) se lograron con un nivel de recursión de $\ell^* = 3$ , involucrando aproximadamente 25,000 parámetros.

Metodología
Los autores proponen un enfoque de dos pasos para mejorar el proceso de optimización del análisis de pérdida de combinación, apuntando a un nivel de recursión superior de $\ell^* = 4$ .

Reformulación y optimización basada en gradientes:
- Expansión del problema: Los autores reformulan el problema de optimización para manejar $\ell^* = 4$ . Esto aumenta el número de parámetros optimizables de ~25k a aproximadamente 7 millones.
- Objetivo diferenciable: Para resolver este problema no convexo de alta dimensión, se alejan de la Programación Cuadrática Secuencial (SQP) utilizada en trabajos previos. En su lugar, emplean un enfoque basado en gradientes.
- Parametrización: Para manejar las restricciones de que las probabilidades deben ser no negativas y sumar uno, las distribuciones se parametrizan mediante logits y se convierten usando la función softmax, permitiendo una optimización sin restricciones.
- Manección de la entropía máxima: El problema implica calcular distribuciones de entropía máxima ( $H_{max}$ ) sujetas a restricciones marginales. En lugar de optimizar estas distribuciones directamente, los autores utilizan el algoritmo de Sinkhorn-Knopp (del transporte óptimo) para calcularlas. Emplean la diferenciación implícita para realizar la retropropagación a través de este algoritmo, asegurando que la función objetivo sea diferenciable y estable.
- Implementación: El algoritmo está implementado en Jax para aprovechar la paralelización por hardware (GPUs). Para gestionar la estructura de grafo no uniforme del árbol de optimización, introducen "nodos fantasma" mediante enmascaramiento y agrupan nodos en "etapas" especializadas, lo que permite representar el problema como tensores multidimensionales para un procesamiento paralelo eficiente.
Integración de AlphaEvolve:
- Los autores aplican AlphaEvolve (Novikov et al., 2025) para refinar aún más el algoritmo de optimización.
- AlphaEvolve modifica el programa de optimización mismo. Utilizando una característica de "evolución de construcciones", el algoritmo en cada generación parte del mejor punto de solución encontrado por el algoritmo padre, evolucionando iterativamente el código para minimizar el límite $\omega$ resultante.
Verificación rigurosa:
- Para asegurar que el resultado esté libre de errores de punto flotante, los autores realizan un paso de verificación separado. Redondean la solución de punto flotante a números racionales y reevalúan todas las cantidades derivadas utilizando aritmética racional exacta.
- Los logaritmos se reemplazan con límites racionales redondeados en la dirección que garantice que todas las restricciones del problema de optimización sigan cumpliéndose, proporcionando un certificado matemáticamente riguroso para el límite.

Contribuciones clave y resultados

Nuevo límite superior: El enfoque combinado produce un nuevo límite superior de $\omega < 2.371177$ .
Magnitud de la mejora: Esto mejora el SOTA anterior de $\omega < 2.371339$ en aproximadamente $1.62 \times 10^{-4}$ . La optimización inicial basada en gradientes por sí sola mejoró el límite en $\approx 0.97 \times 10^{-4}$ , atribuyéndose el resto de la ganancia al refinamiento de AlphaEvolve.
Escalabilidad: El trabajo demuestra la viabilidad de resolver problemas de análisis de pérdida de combinación en $\ell^* = 4$ , una escala previamente intratable con los métodos SQP estándar debido a la explosión en el conteo de parámetros.

Significancia y afirmaciones
El artículo afirma que esta mejora es comparable en magnitud a la mayoría de los avances realizados en los últimos 40 años desde que se estableció el límite de Coppersmith-Winograd ( $\omega < 2.376$ ). Los autores enfatizan que su contribución reside en aprovechar las técnicas modernas de aprendizaje automático (descenso de gradiente, transporte óptimo y generación de código evolutivo) para resolver el marco matemático existente de manera más efectiva.

Los autores se mantienen modestos respecto a las perspectivas futuras, señalando que, si bien es posible lograr otras mejoras modestas a través de esta metodología centrada en la optimización, alcanzar reducciones significativamente mayores en $\omega$ probablemente requerirá nuevas ideas matemáticas más allá del marco actual del método láser. Este trabajo fue motivado por discusiones en el Instituto Simons para la Teoría de la Computación en el otoño de 2025.

Más como este