행렬곱 지수 \(\omega\)의 상한을 낮추는 일은 새 행렬곱 코드를 몇 줄 고치는 일이 아니다. 지난 40년의 개선은 Coppersmith-Winograd 계열의 laser method를 정교화하며, 거대한 비볼록 최적화 문제에서 더 좋은 feasible point를 찾는 방향으로 진화했다. 이 논문은 바로 그 계산 부분을 현대적인 최적화 시스템으로 다시 설계한다.
연구진은 combination loss analysis의 재귀 수준을 기존 \(\ell^*=3\)에서 \(\ell^*=4\)로 올린다. 최적화 변수는 약 2만5천 개에서 약 700만 개로 불어난다. 이를 감당하기 위해 확률분포를 logit과 softmax로 재매개변수화하고, 최대 엔트로피 문제를 Sinkhorn-Knopp로 계산하며, implicit differentiation과 Adam을 사용한다. JAX에서 비균일한 graph computation을 tensor program으로 바꿔 GPU 병렬화를 가능하게 한 뒤, AlphaEvolve가 그 optimizer code 자체를 진화시킨다.
행렬곱의 ‘조금 더 작은 지수’는 수십 년짜리 이론 경쟁의 단위이다
핵심 응용은 행렬곱 자체를 빠르게 실행하는 즉시 효과보다, 계산복잡도 이론의 가장 오래된 경계를 조금씩 밀어내는 데 있다.
\(n\times n\) 행렬 두 개를 몇 번의 산술연산으로 곱할 수 있는가
행렬곱은 기계학습 계산부터 현실적인 컴퓨터 그래픽까지 컴퓨터과학 전반의 핵심 연산이다. 그러나 큰 정방행렬을 곱하는 데 필요한 산술연산의 최적 asymptotic complexity는 아직 알려져 있지 않다. 지수 \(\omega\)는 대략 다음과 같은 의미를 갖는다.
Strassen은 1969년 \(\omega<2.81\)을 보여 cubic \(O(n^3)\) 장벽을 처음 깼다. 이후 Pan, Bini 등, Schönhage, Romani, Coppersmith-Winograd, Strassen, Stothers, Williams, Le Gall, Alman-Williams, Duan, Williams-Xu-Xu-Zhou, Alman 등으로 개선이 이어졌다. 논문은 지난 40년의 모든 개선이 laser method에 의존한다고 정리한다.
최근 네 개의 상한
| Work | Upper bound on \(\omega\) | Role in this note |
|---|---|---|
| Duan et al. (2023) | 2.371866 | combination loss analysis를 도입한 계열 |
| Williams et al. (2024) | 2.371552 | laser-method refinement의 후속 개선 |
| Alman et al. (2025) | 2.371339 | 이 논문의 직접적인 이전 SOTA, \(\ell^*=3\) |
| This note (2026) | 2.371177 | gradient optimization + AlphaEvolve, \(\ell^*=4\) |
gradient 기반 접근만으로 이전 SOTA 대비 약 \(0.97\times10^{-4}\)를 낮췄고, AlphaEvolve까지 적용하면 총 개선폭은 약 \(1.62\times10^{-4}\)가 된다. 절댓값만 보면 작다. 하지만 논문은 Coppersmith-Winograd가 \(\omega<2.376\)에 도달한 이후 40년 동안의 개별 개선폭 대부분과 비교할 만한 규모라고 평가한다.
새 상한은 새 정리만이 아니라 비볼록 최적화의 더 좋은 해에서 나온다
현재 최고 상한은 laser method의 refinement인 combination loss analysis를 통해 얻는다. 이 framework에서는 특정 수학적 조건을 만족하는 parameter 설정 하나가 곧 \(\omega\)의 상한 certificate가 된다. 따라서 이론이 허용하는 거대한 공간에서 더 좋은 feasible solution을 찾는 numerical optimization이 computer-assisted proof의 중심 단계가 된다.
이전 SOTA는 최대 recursion level \(\ell^*=3\)에서 얻었다. 그런데 \(\ell^*\)를 올리면 attainable bound는 좋아질 여지가 생기는 반면, optimization complexity는 \(\ell^*\)에 대해 doubly exponential하게 커진다. 이번 연구는 이 계산 장벽을 정면으로 공격한다.
복잡한 증명 계산을 ‘shape와 region을 가진 트리’로 펼친다
각 node는 probability distribution과 분해 규칙을 들고 있고, leaf까지 내려가며 tensor decomposition의 질량·엔트로피·matrix size를 누적한다.
고정 hyperparameter \(q\)와 \(\ell^*\), 그리고 shape space
high-level 구조는 rooted tree이다. 정수 \(q\ge1\), \(\ell^*\ge2\)를 고정한다. 이 트리는 Coppersmith-Winograd tensor \(CW_q\)의 거듭제곱을 더 작은 tensor들로 재귀적으로 분해하는 방식을 encoding한다.
level-\(\ell\) shape는 세 좌표가 \(2^\ell\)로 합쳐지는 비음수 정수 triple이다.
좌표는 \(X,Y,Z\) 세 dimension으로 부른다. region은 6개이며, 각 region \(r\in[6]\)은 \(\{X,Y,Z\}\)의 \(r\)번째 사전식 permutation \(\pi_r\)에 대응한다. shape의 모든 좌표가 양수면 positive-shape node, 하나라도 0이면 zero-shape node이다.
root에서 가능한 모든 top-level shape·region을 열고, positive node를 계속 쪼갠다
root \(G\)는 level, shape, region 속성을 갖지 않는다. 대신 모든 \(s\in\mathcal S_{\ell^*}\), \(r\in[6]\)에 대해 child \(G[s,r]\)를 갖는다.
positive-shape \(s=(s_X,s_Y,s_Z)\)를 한 단계 낮게 분할할 수 있는 후보는
level \(\ell\ge3\)의 positive node \(T\)는 모든 \(u\in\operatorname{Split}(s_T)\)와 모든 region \(r\)에 대해 child \(T[u,r]\)를 갖는다. 부모의 region과 child의 region이 같을 필요는 없다. zero-shape node와 level-2 positive-shape node는 더 쪼개지지 않는 leaf이다.
node 종류에 따라 최적화할 확률분포가 달라진다
유한집합 \(D\)에 대한 확률 simplex를 \(\Delta(D)\)라 쓰면, free variable은 네 부류로 나뉜다.
complete split set은 길이 \(2^{\ell-1}\)인 \(\{0,1,2\}\) 값 vector 중 합이 \(a\)인 것들의 집합이다.
엔트로피, mass, retained exponent, local matrix size가 하나의 부등식으로 조립된다
최적화의 수학적 핵심은 각 확률분포가 얼마나 많은 조합을 ‘보존’하는지와 leaf가 얼마나 큰 행렬곱을 제공하는지를 균형시키는 데 있다.
같은 marginal을 가진 분포 중 최대 엔트로피와의 차이를 penalty로 쓴다
모든 logarithm과 entropy는 base 2이다. 유한 support를 가진 분포 \(\rho\)의 entropy는
shape distribution \(\rho\)의 좌표별 marginal \(\rho_W\)를 고정한 채 얻을 수 있는 최대 entropy를 다음처럼 정의한다.
\(P_D\)가 바로 combination loss의 penalty 개념이다. joint distribution이 같은 marginals 아래 가능한 최대 엔트로피에서 얼마나 떨어져 있는지를 수치화한다.
확률 선택을 따라 tree의 질량을 top-down으로 전달한다
root mass는 \(m_G=1\)이다. root child의 mass는 region probability와 shape probability의 곱이다.
level \(\ell\ge3\) positive node에서는 complement split \(s_T-u\)까지 함께 반영한다.
zero-shape leaf와 positive node를 서로 다른 방식으로 구성한다
zero-shape node에서는 첫 zero coordinate의 distribution은 all-zero vector에 놓인 point mass이다. 첫 nonzero coordinate의 \(\beta\)는 free variable이고, 남은 coordinate는 \(L\mapsto\mathbf 2-L\) 변환으로 대응시킨다. 여기서 \(\mathbf2\)는 길이 \(2^{\ell-1}\)인 all-two vector이다.
positive node \(T\)에서는 child의 complete split distribution을 Cartesian product로 이어 붙인 뒤 \(\alpha_T^{(r)}\)로 mixture하고, 다시 region weight \(A_T^{(r)}\)로 합친다.
level-2 shape \((1,1,2)\)에서는 \(\mu_T\)로 다음 distribution을 만든다. 다른 두 shape는 \(X,Y,Z\) 역할만 순환시킨다.
각 level에서 가장 약한 좌표 방향을 기준으로 보존량을 계산한다
root retained exponent는 각 region의 contribution \(E_G^{(r)}\)를 region weight로 평균한 값이다. 논문은 먼저 identity permutation인 \(r=1\)을 정의하고 나머지 5개 region은 \(X,Y,Z\)를 \(\pi_r\)로 relabeling해 얻는다.
원문 식 (3)–(5): root retained exponent
기호 \(*,+,<\)는 각각 해당 좌표가 unconstrained, strictly positive, parent coordinate보다 strictly smaller임을 나타내는 mnemonic이다.
여기서 \(\bar\beta\)들은 해당 조건 아래 \(\alpha\)로 가중한 child complete-split distribution의 mixture이다. 분모가 0이면 논문은 \(0\cdot\mathrm{undefined}:=0\)으로 정의해 식을 well-defined하게 만든다. 최종적으로 \(E_G=\sum_{r=1}^{6}A_G^{(r)}E_G^{(r)}\)이다.
원문 식 (6)–(8): level \(\ell\ge3\) positive node
각 positive node \(T\)에 대해 region과 coordinate별 intermediate retained exponent를 계산한다. \(r=1\)에서
나머지 region도 coordinate permutation으로 얻는다. level \(\ell\in[3,\ell^*]\)의 retained exponent는 각 region마다 \(X,Y,Z\) 누적값 중 최소를 취해 합한다.
원문 식 (9)–(10): level 2와 local matrix size
shape \((1,1,2)\)인 positive level-2 node의 retained exponent vector는
이고 다른 두 shape는 entropy component의 좌표만 바뀐다. 전체 \(E_2\)는 \(X,Y,Z\) 방향의 합 중 최소값이다.
zero-shape leaf의 local matrix size는 첫 zero coordinate \(W_0\) 방향에만 값이 있고, 첫 nonzero coordinate \(W_1\)의 complete split entropy와 값 1이 나타나는 position 수의 기대값으로 정한다.
shape \((1,1,2)\)의 local matrix size는
shape \((2,1,1)\), \((1,2,1)\)은 \(2\mu_T\log q\) 항의 위치를 각각 \(X\), \(Y\)로 옮긴다.
수치해가 ‘좋아 보인다’에서 끝나지 않도록, 최종 상한을 증명 가능한 부등식으로 봉인한다
optimization output은 proof candidate이다. theorem이 요구하는 것은 exact feasibility이고, floating point 값은 마지막에 별도의 certificate로 검증한다.
모든 retained exponent와 leaf matrix size를 하나로 합친다
total retained exponent와 total matrix size는 다음과 같다.
여기서 \(\mathcal L\)은 leaf 집합이다. 최종 optimization problem은 매우 짧게 쓸 수 있다.
Theorem 1은 Alman et al. (2025)의 결과이다. 식 (11)의 feasible solution 하나를 찾으면 asymptotic matrix multiplication exponent에 대해 \(\omega\le\Omega\)가 성립한다. 즉 optimizer가 하는 일은 단순히 score를 내리는 것이 아니라, theorem의 가정 안에 남으면서 더 작은 \(\Omega\)를 인증할 parameter set을 찾는 것이다.
\(H_D^{\max}\)를 정확히 닫힌식으로 계산할 수 없다는 문제가 남는다
앞의 derived quantity 중 \(H_D^{\max}(\rho)\)만 analytic하게 계산할 수 없다. 다행히 \(E_{\mathrm{total}}\) 안의 모든 \(H_D^{\max}\)를 upper bound로 대체하면 \(E_{\mathrm{total}}\)은 감소할 뿐이다. 따라서 더 보수적인 값으로도 식 (11)을 만족하면 원래 문제에도 여전히 feasible이고 \(\omega\le\Omega\)가 유지된다.
같은 marginal을 가진 분포와 Lagrange multiplier residual로 최대 엔트로피를 끼운다
valid certificate는 세 요소를 요구한다. 첫째, \(D\)의 모든 원소에 양의 확률을 주면서 \(\rho\)와 같은 \(X,Y,Z\) marginal을 가진 \(y\in\Delta(D)\). 둘째, scalar \(\lambda_0\)와 각 좌표·marginal value별 multiplier \(\lambda_W(w)\). 셋째, 모든 \(a=(a_X,a_Y,a_Z)\in D\)에 대해 다음 residual을 만족하는 \(\varepsilon\ge0\)이다.
Lemma 1은 이 certificate가 있으면
임을 보인다. 왼쪽은 \(y\)가 같은 marginals를 가지므로 최대화 문제의 feasible point라는 사실에서 바로 나온다. 오른쪽은 entropy의 concavity를 이용해 임의의 같은-marginal 분포 \(\rho'\)를 \(y\)에서 1차 upper bound한 뒤, multiplier 조합이 marginal equality 때문에 소거되고, residual vector의 \(\ell_\infty\) bound \(\varepsilon\)와 두 확률분포 사이의 \(\ell_1\)-distance가 최대 2라는 사실을 사용한다.
SQP 대신 softmax·Sinkhorn·implicit differentiation·Adam·JAX를 넣는다
핵심은 더 ‘AI다운’ 알고리즘을 쓴다는 수사가 아니라, 700만 변수짜리 구조를 differentiable tensor computation으로 바꿔 실제로 \(\ell^*=4\)를 풀 수 있게 만든 데 있다.
simplex constraint를 softmax 안으로 밀어 넣는다
수치 최적화에서는 \(q=5\), \(\ell^*=4\)를 사용한다. Alman et al. (2025)은 \(\ell^*=3\)에서 SNOPT의 sequential quadratic programming(SQP)을 썼다. 이번 연구는 non-convex minimization을 gradient 기반으로 바꾼다.
대부분의 free variable이 확률분포이므로 원래 변수에는 non-negativity와 sum-to-one 제약이 붙는다. 연구진은 distribution 자체를 직접 최적화하지 않고 unconstrained logit를 parameter로 두고 softmax를 적용한다. 초기 logit는 random하게 시작한다.
최대 엔트로피 분포를 free variable로 같이 최적화하지 않고 내부 solver로 계산한다
같은 marginal을 유지하는 maximum-entropy distribution 문제는 optimal transport에서 반복되는 구조와 닮아 있다. 논문은 Sinkhorn-Knopp algorithm을 이용해 stable하고 differentiable한 objective를 얻는다. 이전 연구처럼 maximum-entropy distribution과 corresponding Lagrange multiplier까지 전체 optimization의 free variable로 넣지 않고, 현재 input distribution이 주어질 때 Sinkhorn-Knopp로 직접 계산한다.
gradient는 automatic differentiation으로 구한다. Sinkhorn iteration을 통과해 backpropagate할 때의 안정성을 높이기 위해 implicit differentiation을 사용하고, outer parameter update에는 Adam을 적용한다.
비균일 graph message passing을 multi-dimensional tensor program으로 바꾼다
\(\ell^*=4\)에서 약 700만 변수를 GPU로 처리하려면 optimizer 선택만 바꿔서는 부족하다. Alman et al. 구현은 graph node에 free parameter를 저장하고 child→parent와 parent→child message passing을 수행한다. 문제는 node마다 child 수와 type이 달라 graph가 너무 비균일해 병렬화가 어렵다는 점이다.
연구진은 두 가지 engineering trick을 쓴다. 첫째, phantom node를 추가하고 masking해 irregular shape를 regular tensor shape로 맞춘다. 대가로 optimization parameter 수가 최대 3배까지 늘 수 있다. 둘째, node를 소수의 highly specialized group, 즉 stage로 cluster한다. 그 결과 전체 graph를 multi-dimensional tensor로 표현할 수 있고, 최대 10개 axis에 걸친 병렬 처리가 가능해진다.
AlphaEvolve는 증명 명제를 바꾸지 않고, 더 좋은 optimizer program을 진화시킨다
AI가 ‘정리를 증명했다’고 뭉뚱그리기보다, 어디를 자동화했고 어디에서 엄밀성이 확보됐는지를 분리해 보는 것이 중요하다.
수학적 feasible region이 아니라 optimization code를 변형한다
AlphaEvolve는 연구진이 만든 optimization program을 수정한다. 수정된 program은 single GPU에서 약 5시간 실행되어 하나의 \(\omega\) bound를 출력하고, AlphaEvolve는 그 결과를 fitness처럼 사용해 code를 계속 진화시킨다.
특히 성능이 좋아진 설정은 AlphaEvolve의 evolving constructions 기능이다. 각 generation의 optimizer가 parent algorithm이 발견한 best solution point에서 시작한다. 즉 optimizer code의 변이와 state warm-start를 결합해 search를 이어 간다.
floating point 최적점은 마지막에 exact rational arithmetic으로 다시 계산한다
optimizer가 출력한 작은 \(\Omega\)가 곧바로 정리의 결론은 아니다. floating point error가 부등식의 방향을 미세하게 뒤집을 수 있기 때문이다. 연구진은 최적화가 끝난 뒤 별도의 verification step을 수행한다.
논문 작성 시점에는 verification code와 발견한 solution을 공개할 repository를 준비 중이라고 밝힌다. 따라서 이 note 자체는 검증 방법을 설명하지만, 해당 repository가 이미 공개됐다고 말하지는 않는다.
modern optimization과 code evolution이 기존 수학 틀 안의 더 좋은 certificate를 찾았다
이 결과는 combination loss analysis라는 기존 수학적 proof framework를 폐기한 것이 아니다. 그 안의 non-convex optimization을 더 크게, 더 빠르게, 더 differentiable하게 풀고, 그 optimizer 자체를 AlphaEvolve로 개선한 뒤, 최종 candidate를 rational arithmetic으로 다시 증명 가능한 객체로 바꿨다.
AI가 새 수학을 ‘발견했다’는 한 문장보다, 수학과 최적화가 역할을 어떻게 나눴는지가 더 중요하다
이번 개선은 강하지만 제한적이다. 같은 방법으로 조금 더 내릴 가능성은 있어도, 큰 폭의 진전에는 새로운 수학적 아이디어가 필요하다는 것이 저자들의 결론이다.
계산 최적화의 한계와 새 수학의 필요를 동시에 인정한다
논문은 이번 개선이 \(\omega<2.376\) 이후 지난 40년의 많은 개선과 비슷한 magnitude라고 평가한다. 동시에 같은 접근으로 further modest improvements를 얻을 가능성은 있지만, \(\omega\)를 크게 더 낮추려면 새로운 mathematical idea가 필요할 가능성이 높다고 말한다.
이 균형이 중요하다. optimizer가 더 강해졌다고 해서 underlying proof technique의 structural ceiling이 사라지는 것은 아니다. 계산은 현재 이론이 열어 둔 feasible region을 더 잘 탐색할 수 있지만, feasible region 자체를 넓히는 일은 여전히 수학의 몫이다.
수학, 수치최적화, program evolution을 분리해서 읽는다
Mathematical layer
combination loss analysis와 Theorem 1이 무엇이 valid upper bound인지 정의한다.
Optimization layer
softmax, Sinkhorn, implicit differentiation, Adam, JAX tensorization이 더 큰 \(\ell^*\) 문제를 실제로 푼다.
AI-code layer
AlphaEvolve가 optimizer program을 진화시켜 같은 formal objective에서 더 좋은 solution을 찾는다.
이 결과로 바로 말할 수 없는 것들
첫째, \(\omega<2.371177\)은 asymptotic upper bound이다. 특정 크기의 실제 dense matrix multiply가 곧바로 이 지수대로 빠르게 실행된다는 뜻은 아니다. 둘째, 이번 성과는 combination loss analysis라는 특정 proof framework의 optimization을 개선한 결과이며, 일반적인 모든 수학적 최적화 문제에서 AlphaEvolve가 같은 효과를 낸다는 증거는 아니다.
셋째, source note는 AlphaEvolve 탐색의 총 세대 수, 총 GPU-hour, 전체 candidate count 같은 비용 세부를 제공하지 않는다. 약 5시간은 수정된 optimization program 하나를 single GPU에서 실행해 bound를 얻는 시간으로 설명된다. 넷째, verification repository는 “preparing”이라고만 되어 있으므로 본문만으로 공개 상태를 단정해서는 안 된다.
가장 실용적인 패턴은 ‘AI가 증명을 써 준다’가 아니라 search와 certification의 분리일 수 있다
이번 사례에서 search는 유연하고 공격적이다. gradient descent는 local geometry를 이용하고, GPU tensorization은 계산 규모를 키우며, AlphaEvolve는 optimizer code의 설계 공간까지 탐색한다. 반대로 certification은 보수적이다. theorem이 요구하는 constraint를 exact rational arithmetic과 방향이 안전한 log bound로 확인한다.
이 조합은 AI-for-mathematics의 한 가지 중요한 설계 원리를 보여 준다. 발견 단계에서는 휴리스틱과 학습을 최대한 활용하고, 최종 주장 단계에서는 별도의 검증 경로로 epistemic debt를 청산한다. 이 문장은 논문의 theorem이 직접 증명한 명제는 아니지만, 전체 workflow가 보여 주는 공학적 함의라고 볼 수 있다.
연구의 출발점
저자들은 이 note의 작업이 2025년 가을 Simons Institute for the Theory of Computing의 Complexity and Linear Algebra program에서 나눈 초기 대화에서 동기를 얻었다고 밝힌다.