🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

이 논문은 기저의 최적화 문제를 재구성하고 현대적인 머신러닝 기술과 AlphaEvolve을 통해 솔루션 프로세스를 강화함으로써 행렬 곱셈 지수 $\omega$ 에 대한 상한을 2.371177 미만으로 개선한다.

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

게시일 2026-08-18

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

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

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터 과학의 광활한 풍경 속에서, 두 개의 거대한 숫자 격자를 곱하는 작업만큼 근본적인 연산은 드뭅니다. 이 과정은 행렬 곱셈(matrix multiplication)으로 알려져 있습니다. 이 수학적 과업은 인공지능 모델을 훈련시키는 것부터 비디오 게임에서 사실적인 이미지를 렌더링하는 것에 이르기까지 모든 것의 기초가 됩니다. 수십 년 동안 과학자들은 이 연산이 표준적이고 직관적인 방법보다 더 빠르게 수행될 수 있다는 사실을 알고 있었지만, 얼마나 빨리 갈 수 있는지에 대한 정확한 한계는 이 분야의 가장 완고한 미스터리 중 하나로 남아 있었습니다. 이 한계는 격자의 크기가 커짐에 따라 계산에 소요되는 시간이 어떻게 증가하는지를 결정하는 단일 숫자, 즉 수학적 지수로 설명됩니다. 이 숫자가 작을수록 컴퓨터는 더 효율적일 수 있습니다. 이론적 최솟값은 최소 2라는 것이 알려져 있지만, 입증된 최선의 상한선은 수년간 2.37을 약간 상회하는 수준에 머물러 왔으며, 연구자들은 점점 더 정교해지는 수학적 도구들을 사용하여 이 장벽을 깎아 나가고 있습니다.

Google DeepMind의 연구진과 여러 대학의 협력 연구진은 이제 이 경계를 조금 더 밀어냈습니다. 현대적인 최적화 기법과 새로운 형태의 인공지능을 결합함으로써, 그들은 지수가 2.371177 미만으로 낮아질 수 있음을 증명하며 새로운 기록을 세웠습니다. 이는 작은 수치적 변화이지만, 이 특정 문제의 맥락에서는 중요한 진전을 의미합니다. 2025년에 달성된 이전의 최고 결과는 2.371339였습니다. 이번의 새로운 발견이 정확한 한계라는 궁극적인 미스터리를 해결하거나 컴퓨터가 실제로 행렬을 곱하는 방식을 즉각적으로 바꾸지는 않지만, 문제에 대한 이론적 제약을 강화하여 천장이 이전에 생각했던 것보다 더 낮다는 것을 보여줍니다.

이 새로운 기록을 향한 길은 40년 전 더 빠른 행렬 곱셈 알고리즘을 간접적으로 설계하기 위해 개발된 레이저 방법(laser method)이라는 수학적 프레임워크에서 시작되었습니다. 이 방법의 가장 최근의 정교화 방식인 조합 손실 분석(combination loss analysis)은 거대하고 복형적인 최적화 문제를 해결하는 것에 의존합니다. 이 문제는 커다란 수학적 구조를 더 작은 조각들로 나누는 최선의 방법을 찾는 것을 포함합니다. 연구진은 이 문제의 난이도가 분해의 깊이를 나타내는 매개변수에 달려 있다는 것을 발견했습니다. 이전의 시도들은 깊이 3에서 멈추었으며, 이는 조정할 수 있는 변수의 수를 제한했습니다. 새로운 팀은 이 깊이를 4로 늘림으로써 훨씬 더 넓은 가능성의 공간을 탐색할 수 있다는 것을 깨달았지만, 그렇게 하는 것은 수백만 개의 변수를 가진 문제를 풀어야 함을 의미했으며, 이는 과거에 사용되던 전통적인 알고리즘으로는 너무 거대한 작업이었습니다.

이러한 규모를 다루기 위해 연구진은 머신러닝에서 빌려온 기술들을 활용했습니다. 표준적인 수학적 솔버를 사용하는 대신, 그들은 문제를 신경망을 훈련할 때 흔히 사용되는 경사 하강법(gradient descent)으로 처리할 수 있도록 재구성했습니다. 이 접근 방식은 강력한 컴퓨터 하드웨어를 사용하여 데이터를 병렬로 처리할 수 있게 해주었으며, 더 깊은 분해와 함께 찾아온 복잡성의 폭발을 감당할 수 있게 했습니다. 그들은 수학적 변수들을 마치 학습 모델의 조정 가능한 가중치처럼 취급하여, 더 나은 솔루션을 찾기 위해 반복적으로 정제했습니다. 이러한 전략의 전환만으로도 경계값을 측정 가능한 수준으로 개선했으며, 이는 현대의 계산 도구가 과거의 방법들이 놓쳤던 잠재력을 끌어낼 수 있음을 입증했습니다.

하지만 팀은 거기서 멈추지 않았습니다. 그들은 스스로 코드를 작성하고 개선하도록 설계된 인공지능인 AlphaEvolve를 채택했습니다. 단순히 최적화 알고리즘을 실행하는 데 그치지 않고, AI가 알고리즘 자체를 수정하도록 했습니다. 시스템은 새로운 버전의 코드를 생성하고, 그것이 어떤 경계값을 산출하는지 실행해 본 뒤, 해당 경계값을 최소화하기 위해 코드를 더욱 진화시켰습니다. 이러한 자기 개선 과정 덕분에 연구진은 인간 팀이 간과했을 수도 있는 최적화 전략의 미묘한 정교함을 찾아낼 수 있었습니다. 이 자동화된 진화의 결과는 추가적인 개선을 이끌어내어, 경계값을 새로운 기록인 2.371177로 낮추었습니다.

이 결과가 컴퓨터의 반올림 오차나 부동 소수점 부정확함에 의한 결과물이 아님을 보장하기 위해, 팀은 엄격한 검증 단계를 수행했습니다. 그들은 알고리즘이 찾아낸 솔루션을 가져와 모든 숫자를 정확한 분수로 변환하고, 완벽한 정밀도로 최종 계산을 수행했습니다. 또한 방정식의 모든 로그를 제약 조건이 충족됨을 보장하는 안전한 유리수 상한으로 대체했습니다. 이러한 신중한 인증 과정은 새로운 경계값이 수학적으로 유효하며, 복잡한 계산에서 흔히 발생하는 수치적 노이즈로부터 자유롭다는 것을 확인시켜 주었습니다.

연구진은 자신들의 접근 방식이 더 나은 경계값을 산출했지만, 개선을 달성하는 것이 점점 더 어려워지고 있다고 언급합니다. 그들이 이룬 성과는 지난 40년 동안 나타난 점진적인 진보의 규모와 맞먹습니다. 그들은 이러한 최적화 기법을 계속 정교화함으로써 추가적인 완만한 개선은 가능할지 모르나, 진정한 한계에 대한 훨씬 더 큰 도약을 달성하려면 완전히 새로운 수학적 아이디어가 필요할 것이라고 시사합니다. 현재로서는, 이 연구가 심도 있는 이론 수학과 현대 머신러닝의 계산 능력을 결합하는 힘에 대한 증거로서, 긴 역사를 가진 분야에서도 여전히 발견의 여지가 남아 있음을 보여주는 사례로 남아 있습니다.

기술 요약: 현대적 최적화 및 AlphaEvolve를 통한 행렬 곱셈 지수의 개선

문제 정의
두 $n \times n$ 행렬을 $O(n^{\omega + o(1)})$ 연산으로 곱할 수 있는 행렬 곱셈의 계산 복잡도 지수 $\omega$ 는 이론 컴퓨터 과학의 근본적인 미해결 과제로 남아 있다. 1969년 스트라센(Strassen)의 돌파구가 $\omega < 2.81$ 을 확립한 이후, 현재 최선의 상한값은 $\omega < 2.371339$ (Alman 등, 2025)이다. 이 상한값은 **조합 손실 분석(combination loss analysis)**이라 알려진 "레이저 방법(laser method)"의 정교화로부터 도출되었다. 이 접근법의 핵심은 복잡한 비볼록 최적화 문제를 푸는 것이다. 난점은 최적화의 복잡성(재귀 레벨 $\ell^*$ 에 따라 이중 지수적으로 증가함)과 결과적인 상한값의 정밀도 사이의 트레이드오프에 있다. 이전의 최첨단(SOTA) 결과는 약 25,000개의 매개변수를 포함하는 재귀 레벨 $\ell^* = 3$ 에서 달성되었다.

방법론
저자들은 조합 손실 분석을 위한 최적화 과정을 개선하기 위해, 더 높은 재귀 레벨인 $\ell^* = 4$ 를 목표로 하는 2단계 접근법을 제안한다.

재정의 및 경사 하강 기반 최적화:
- 문제 확장: 저자들은 $\ell^* = 4$ 를 처리할 수 있도록 최적화 문제를 재정의한다. 이는 최적화 가능한 매개변수의 수를 약 2만 5천 개에서 약 7백만 개로 증가시킨다.
- 미분 가능한 목적 함수: 이 고차원 비볼록 문제를 해결하기 위해, 기존 연구에서 사용된 순차 이차 계획법(SQP)에서 벗어나 경사 하강 기반 접근법을 채택한다.
- 매개변수화: 확률이 비음수이며 합이 1이어야 한다는 제약 조건을 처리하기 위해, 분포를 로짓(logits)으로 매개변수화한 후 소프트맥스(softmax) 함수를 사용하여 변환함으로써 무제약 최적화를 가능하게 한다.
- 최대 엔트로피 처리: 이 문제는 주변부 제약 조건(marginal constraints)을 가진 최대 엔트로피 분포( $H_{max}$ )를 계산하는 과정을 포함한다. 저자들은 이러한 분포를 직접 최적화하는 대신, 싱크혼-크노프(Sinkhorn-Knopp) 알고리즘(최적 운송 이론에서 유래)을 사용하여 이를 계산한다. 또한, 목적 함수가 미분 가능하고 안정적으로 유지되도록 암시적 미분(implicit differentiation)을 사용하여 이 알고리즘을 통해 역전파를 수행한다.
- 구현: 하드웨어 병렬화를 활용하기 위해 알고리즘을 Jax로 구현하였다. 최적화 트리의 비균일한 그래프 구조를 관리하기 위해, 마스킹을 사용하는 "팬텀 노드(phantom nodes)"를 도입하고 노드들을 특화된 "스테이지(stages)"로 클러스터링하여, 문제를 효율적인 병렬 처리가 가능한 다차원 텐서로 표현할 수 있도록 하였다.
AlphaEvolve 통합:
- 저자들은 최적화 알고리즘을 더욱 정교하게 만들기 위해 AlphaEvolve (Novikov 등, 2025)를 적용한다.
- AlphaEvolve는 최적화 프로그램 자체를 수정한다. "진화하는 구성(evolving constructions)" 기능을 사용하여, 각 세대의 알고리즘은 부모 알고리즘이 찾은 최적의 솔루션 지점에서 시작하여, 결과적인 $\omega$ 상한을 최소화하도록 코드를 반복적으로 진화시킨다.
엄격한 검증:
- 부동 소수점 오류로부터 결과를 보장하기 위해, 저자들은 별도의 검증 단계를 수행한다. 부동 소수점 솔루션을 유리수로 반올림한 후, 모든 유도된 양들을 유리스 산술(exact rational arithmetic)을 사용하여 재평가한다.
- 로그(logarithm)는 최적화 문제의 모든 제약 조건이 유지되도록 방향을 정해 반올림된 유리수 범위로 대체되어, 최적화 문제의 수학적 엄밀성을 보장하는 인증서를 제공한다.

주요 기여 및 결과

새로운 상한값: 결합된 접근법은 $\omega < 2.371177$ 이라는 새로운 상한값을 산출한다.
개선 폭: 이는 이전 SOTA인 $\omega < 2.371339$ 를 약 $1.62 \times 10^{-4}$ 만큼 개선한 것이다. 초기 경사 하강 기반 최적화만으로도 $\approx 0.97 \times 10^{-4}$ 의 개선이 이루어졌으며, 나머지 이득은 AlphaEvolve 정교화에 의한 것이다.
확장성: 본 연구는 표준 SQP 방법으로는 매개변수 수의 폭발로 인해 다루기 힘들었던 규모인 $\ell^* = 4$ 수준의 조합 손실 분석 문제를 해결할 수 있음을 입증하였다.

의의 및 주장
본 논문은 이 개선이 코퍼스미스-위노그라드(Coppersmith-Winograd) 상한 $\omega < 2.376$ 이 확립된 이후 지난 40년 동안 이루어진 대부분의 발전과 맞먹는 규모라고 주장한다. 저자들은 자신들의 기여가 기존의 수학적 프레임워크를 더 효과적으로 해결하기 위해 현대적인 머신러닝 기술(경사 하강법, 최적 운송, 진화적 코드 생성)을 활용하는 데 있음을 강조한다.

저자들은 향후 전망에 대해 겸허한 태도를 유지하며, 이러한 최적화 중심의 방법론을 통해 추가적인 완만한 개선은 가능할 수 있으나, $\omega$ 의 유의미하게 큰 감소를 달기 위해서는 현재의 레이저 방법 프레임워크를 넘어서는 새로운 수학적 아이디어가 필요할 것이라고 언급하였다. 본 연구는 2025년 가을 사이먼스 이론 컴퓨터 과학 연구소(Simons Institute for the Theory of Computing)에서의 논의를 바탕으로 수행되었다.

유사한 논문