Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

행렬 곱셈 코드를 바로 빠르게 만든 것이 아니라, 이론상 필요한 연산 수의 최선 상한을 최적화와 AlphaEvolve로 조금 낮춘 결과다.

이 논문은 한마디로 큰 정사각 행렬 두 개를 곱할 때 필요한 산술 연산 수의 이론적 상한을 개선한다. 행렬 곱셈 지수의 알려진 상한을 2.371339에서 2.371177로 낮췄다. 차이는 0.000162이며 실제 프로그램 속도가 그만큼 빨라졌다는 뜻은 아니다. 연구진은 재귀 깊이를 3에서 4로 늘리고 약 2만 5천 개였던 최적화 변수를 약 700만 개로 확장한 뒤 기울기 기반 최적화와 AlphaEvolve를 적용했다. 마지막에는 모든 값을 유리수로 다시 계산해 부동소수점 오차가 증명을 깨지 않는지 확인했다.

핵심 요약

• 새 결과는 행렬 곱셈의 연산 수가 이론상 입력 크기의 2.371177제곱보다 조금 작은 수준 안에 든다는 상한이다. 실사용 행렬 곱셈 시간을 측정한 결과는 아니다.
• 기존 조합 손실 분석은 최대 재귀 깊이 3에서 약 2만 5천 변수를 썼다. 새 방식은 깊이 4에서 약 700만 변수를 다뤘다.
• 확률 분포는 소프트맥스로 표현하고 최대 엔트로피 분포는 Sinkhorn-Knopp 계산으로 구했다. 자동 미분과 Adam을 쓰고 JAX 텐서 계산으로 병렬화했다.
• 기울기 방식만으로 이전 상한을 약 0.000097 낮췄다. AlphaEvolve가 최적화 코드를 바꾼 뒤 전체 개선 폭은 약 0.000162가 됐으며 후보 한 번은 단일 GPU에서 약 5시간 걸렸다.
• 최종 해를 유리수로 반올림하고 로그에도 안전한 방향의 유리수 경계를 적용해 검증했다. 저자들은 큰 추가 개선에는 새로운 수학 아이디어가 필요하다고 밝혔다.

논문 링크

외부 연구를 정리한 자료입니다. HDATF가 발표한 논문이나 제품 성능을 측정한 결과는 아닙니다.