🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

Este artigo melhora o limite superior do expoente de multiplicação de matrizes $\omega$ para menos de 2,371177 ao reformular o problema de otimização subjacente e aprimorar o processo de solução com técnicas modernas de aprendizado de máquina e AlphaEvolve.

Autores originais: 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 leitura🧠 Leitura aprofundada

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No vasto cenário da ciência da computação, poucas operações são tão fundamentais quanto a multiplicação de duas grandes grades de números, um processo conhecido como multiplicação de matrizes. Esta tarefa matemática sustenta tudo, desde o treinamento de modelos de inteligência artificial até a renderização de imagens realistas em videogames. Por décadas, cientistas sabem que esta operação pode ser realizada mais rapidamente do que o método padrão e direto, mas o limite preciso de quão rápida ela pode possivelmente ser permaneceu como um dos mistérios mais persistentes do campo. Este limite é descrito por um único número, um expoente matemático que dita como o tempo necessário para o cálculo cresce à medida que o tamanho das grades aumenta. Quanto menor este número, mais eficiente o computador pode ser. Embora o mínimo teórico seja conhecido por ser pelo menos dois, o melhor limite superior comprovado pairou pouco acima de 2,37 por anos, uma barreira que os pesquisadores têm vindo a desgastar com ferramentas matemáticas cada vez mais sofisticadas.

Uma equipe de pesquisadores do Google DeepMind, juntamente com colaboradores de várias universidades, conseguiu agora empurrar este limite um pouco mais longe. Ao combinar técnicas modernas de otimização com uma nova forma de inteligência artificial, eles estabeleceram um novo recorde, provando que o expoente pode ser reduzido para menos de 2,371177. Este é um pequeno deslocamento numérico, mas, no contexto deste problema específico, representa um passo significativo à frente. O resultado anterior, alcançado em 2025, situava-se em 2,371339. A nova descoberta não resolve o mistério definitivo do limite exato, nem altera imediatamente a forma como os computadores multiplicam matrizes na prática, mas estreita as restrições teóricas do problema, mostrando que o teto é mais baixo do que se pensava anteriormente ser possível.

O caminho para este novo recorde começou com uma estrutura matemática conhecida como o método do laser, uma técnica desenvolvida há quarenta anos para projetar algoritmos de multiplicação de matrizes mais rápidos indiretamente. O refinamento mais recente deste método, chamado análise de perda de combinação, baseia-se na resolução de um problema de otimização massivo e complexo. Este problema envolve encontrar a melhor maneira de decompor uma grande estrutura matemática em partes menores. Os pesquisadores descobriram que a dificuldade deste problema depende de um parâmetro que representa a profundidade da decomposição. As tentativas anteriores tinham parado numa profundidade de três, o que limitava o número de variáveis que podiam ser ajustadas. A nova equipe percebeu que, ao aumentar esta profundidade para quatro, poderiam explorar um espaço muito maior de possibilidades, mas fazer isso exigiria a resolução de um problema com milhões de variáveis, uma tarefa demasiado grande para os algoritmos tradicionais usados no passado.

Para enfrentar esta escala, os pesquisadores recorreram a técnicas emprestadas do aprendizado de máquina. Em vez de usar resolvedores matemáticos padrão, eles reformularam o problema para que pudesse ser tratado pelo gradiente descendente, um método comumente usado para treinar redes neurais. Esta abordagem permitiu-lhes utilizar hardware de computação poderoso para processar os dados em paralelo, lidando com a explosão de complexidade que acompanhou a decomposição mais profunda. Eles trataram as variáveis matemáticas como se fossem os pesos ajustáveis num modelo de aprendizagem, refinando-os iterativamente para encontrar uma solução melhor. Esta mudança de estratégia, por si só, melhorou o limite por um valor mensurável, demonstrando que as ferramentas computacionais modernas poderiam desbloquear um potencial que os métodos mais antigos tinham perdido.

No entanto, a equipe não parou por aí. Eles empregaram um sistema chamado AlphaEvolve, uma inteligência artificial desenhada para escrever e melhorar o seu próprio código. Em vez de apenas executar o algoritmo de otimização, eles deixaram a IA modificar o próprio algoritmo. O sistema gerava uma nova versão do código, executava-a para ver que limite produzia e, em seguida, evoluía o código para minimizar esse limite. Este processo de autoaperfeiçoamento permitiu aos pesquisadores encontrar refinamentos subtis na estratégia de otimização que uma equipe humana poderia ter negligenciado. O resultado desta evolução automatizada foi um novo melhoria, empurrando o limite para o novo recorde de 2,371177.

Para garantir que este resultado não fosse um artefato de erros de arredondamento de computador ou imprecisões de ponto flutuante, a equipe realizou uma etapa de verificação rigorosa. Eles pegaram na solução encontrada pelos seus algoritmos e converteram todos os números em frações exatas, realizando os cálculos finais com precisão perfeita. Eles também substituíram cada logaritmo nas equações por um limite racional seguro que garantia que as restrições fossem cumpridas. Este processo de certificação cuidadoso confirmou que o novo limite é matematicamente válido e livre do ruído numérico que frequentemente assola tais computações complexas.

Os pesquisadores observam que, embora a sua abordagem tenha rendido um melhor limite, as melhorias estão a tornar-se cada vez mais difíceis de alcançar. Os ganhos que fizeram são comparáveis em magnitude ao progresso incremental visto nos últimos quarenta anos. Eles sugerem que, embora mais melhorias modestas possam ser possíveis através do contínuo refinamento destas técnicas de otimização, alcançar um salto muito maior na compreensão do verdadeiro limite exigirá provavelmente ideias matemáticas inteiramente novas. Por agora, o trabalho permanece como um testemunho do poder de combinar a matemática teórica profunda com o músculo computacional do aprendizado de máquina moderno, provando que, mesmo num campo com uma longa história, ainda há espaço para a descoberta.

Resumo Técnico: Melhorando o Expoente da Multiplicação de Matrizes com Otimização Moderna e AlphaEvolve

Enunciado do Problema
A complexidade computacional da multiplicação de matrizes, caracterizada pelo expoente $\omega$ , onde duas matrizes $n \times n$ podem ser multiplicadas em $O(n^{\omega + o(1)})$ operações, permanece uma questão fundamental em ciência da computação teórica. Embora o avanço de Strassen em 1969 tenha estabelecido $\omega < 2,81$ , o limite superior atual mais refinado é $\omega < 2,371339$ (Alman et al., 2025). Este limite é derivado de um refinamento do "método do laser" conhecido como análise de perda de combinação (combination loss analysis). O cerne desta abordagem envolve a resolução de um problema de otimização não convexo complexo. A dificuldade reside no compromisso entre a complexidade da otimização (que cresce duplamente exponencialmente com o nível de recursão $\ell^*$ ) e a precisão do limite resultante. Os resultados anteriores de estado da arte (SOTA) foram alcançados com um nível de recursão de $\ell^* = 3$ , envolvendo aproximadamente 25.000 parâmetros.

Metodologia
Os autores propõem uma abordagem de duas etapas para melhorar o processo de otimização para a análise de perda de combinação, visando um nível de recursão mais alto de $\ell^* = 4$ .

Reformulação e Otimização Baseada em Gradiente:
- Expansão do Problema: Os autores reformulam o problema de otimização para lidar com $\ell^* = 4$ . Isso aumenta o número de parâmetros otimizáveis de ~25k para aproximadamente 7 milhões.
- Objetivo Diferenciável: Para resolver este problema não convexo de alta dimensão, eles se afastam da Programação Quadrática Sequencial (SQP) utilizada em trabalhos anteriores. Em vez disso, empregam uma abordagem baseada em gradiente.
- Parametrização: Para lidar com as restrições de que as probabilidades devem ser não negativas e somar um, as distribuições são parametrizadas via logits e convertidas usando a função softmax, permitindo a otimização sem restrições.
- Tratamento de Entropia Máxima: O problema envolve o cálculo de distribuições de entropia máxima ( $H_{max}$ ) sujeitas a restrições marginais. Em vez de otimizar essas distribuições diretamente, os autores utilizam o algoritmo Sinkhorn-Knopp (de transporte ótimo) para computá-las. Eles empregam diferenciação implícita para realizar o backpropagation através deste algoritmo, garantindo que a função objetivo permaneça diferenciável e estável.
- Implementação: O algoritmo é implementado em Jax para aproveitar o paralelismo de hardware (GPUs). Para gerenciar a estrutura de grafo não uniforme da árvore de otimização, eles introduzem "nós fantasmas" (phantom nodes) com mascaramento e agrupam nós em "estágios" especializados, permitindo que o problema seja representado como tensores multidimensionais para processamento paralelo eficiente.
Integração com AlphaEvolve:
- Os autores aplicam o AlphaEvolve (Novikov et al., 2025) para refinar ainda mais o algoritmo de otimização.
- O AlphaEvolve modifica o próprio programa de otimização. Usando um recurso de "evolução de construções" (evolving constructions), o algoritmo em cada geração parte do melhor ponto de solução encontrado pelo algoritmo pai, evoluindo iterativamente o código para minimizar o limite $\omega$ resultante.
Verificação Rigorosa:
- Para garantir que o resultado esteja livre de erros de ponto flutuante, os autores realizam uma etapa de verificação separada. Eles arredondam a solução de ponto flutuante para números racionais e reavaliam todas as quantidades derivadas usando aritmética racional exata.
- Os logaritmos são substituídos por limites racionais arredondados na direção que garante que todas as restrições do problema de otimização permaneçam satisfeitas, fornecendo um certificado matematicamente rigoroso para o limite.

Contribuições Principais e Resultados

Novo Limite Superior: A abordagem combinada produz um novo limite superior de $\omega < 2,371177$ .
Magnitude da Melhoria: Isso melhora o SOTA anterior de $\omega < 2,371339$ em aproximadamente $1,62 \times 10^{-4}$ . A otimização baseada em gradiente inicial melhorou o limite em $\approx 0,97 \times 10^{-4}$ , sendo que o ganho restante é atribuído ao refinamento do AlphaEvolve.
Escalabilidade: O trabalho demonstra a viabilidade de resolver problemas de análise de perda de combinação em $\ell^* = 4$ , uma escala anteriormente intratável com métodos SQP padrão devido à explosão na contagem de parâmetros.

Significância e Alegações
O artigo afirma que esta melhoria é comparável em magnitude à maioria dos avanços feitos nos últimos 40 anos desde que o limite de Coppersmith-Winograd ( $\omega < 2,376$ ) foi estabelecido. Os autores enfatizam que sua contribuição reside em alavancar técnicas modernas de aprendizado de máquina (gradiente descendente, transporte ótimo e geração de código evolutivo) para resolver o quadro matemático existente de forma mais eficaz.

Os autores permanecem modestos quanto às perspectivas futuras, observando que, embora melhorias modestas adicionais possam ser alcançáveis através desta metodologia focada em otimização, alcançar reduções significativamente maiores em $\omega$ provavelmente exigirá novas ideias matemáticas além do atual quadro do método do laser. O trabalho foi motivado por discussões no Simons Institute for the Theory of Computing no outono de 2025.

Mais como este