AlphaEvolve, 행렬 곱셈 지수 상한을 2.371177로 개선

들어가며

행렬 곱셈은 선형대수의 기본 연산이지만, 그 계산 복잡도를 이론적으로 얼마나 낮출 수 있는지는 오랫동안 연구된 문제입니다. 행렬 곱셈 지수 ω는 크기가 대략 n인 정방행렬 두 개를 곱할 때 필요한 계산량을 대략 n^ω로 나타내는 값입니다. 지수가 낮을수록 점근적 관점에서 더 효율적인 알고리즘을 뜻합니다. 다만 이 값은 특정 GPU나 소프트웨어 라이브러리의 실제 실행 속도를 직접 의미하지는 않습니다.

DeepMind 연구진을 포함한 연구팀은 행렬 곱셈 지수의 최신 상한을 다시 개선했다고 발표했습니다. 새 상한은 ω < 2.371177이며, 이전의 2.371339보다 낮습니다. 이번 성과는 일반적인 행렬 연산 구현을 최적화한 결과가 아니라, 레이저 방법의 현대적 개선 기법에 포함된 핵심 최적화 문제를 다룬 연구입니다.

핵심 내용

• 조합 손실 분석을 개선했다. 최근 행렬 곱셈 지수의 좋은 상한은 레이저 방법을 발전시킨 조합 손실 분석에서 나옵니다. 이 방법은 대수적 구성뿐 아니라 결과의 성능을 결정하는 어려운 최적화 문제를 함께 해결해야 합니다.
• 문제를 더 넓은 형태로 재구성했다. 연구팀은 핵심 최적화 문제를 재정식화해 기존보다 넓은 설정에서 풀 수 있도록 했습니다. 이를 통해 탐색 가능한 후보 구조의 범위를 확장했습니다.
• 머신러닝의 최적화 아이디어를 적용했다. 연구진은 최근 머신러닝 분야의 발전을 활용해 이 수학적 문제에 맞는 새로운 최적화 알고리즘을 설계했습니다. 이는 행렬 곱셈용 AI 모델을 학습했다는 뜻이 아니라, 알고리즘 탐색에 현대적인 최적화 기법을 활용했다는 의미입니다.
• AlphaEvolve로 결과를 추가 개선했다. 새 알고리즘이 찾은 결과를 AlphaEvolve로 다시 정제했습니다. 문제 재구성, 자동 탐색, 후속 개선을 연결한 파이프라인입니다.

의미와 한계

2.371339에서 2.371177로의 변화는 숫자만 보면 작아 보입니다. 그러나 행렬 곱셈 지수 연구는 이미 정교하게 다듬어진 이론적 경계를 조금씩 밀어내는 분야입니다. 더 낮은 상한을 얻으려면 복잡한 구성물을 찾고, 그 구성이 엄격한 조건을 만족한다는 점을 입증해야 합니다. 따라서 이번 결과의 중요성은 일상적인 행렬 연산이 즉시 같은 비율로 빨라진다는 데 있지 않고, 자동화된 최적화가 고난도 알고리즘 이론 연구를 지원할 수 있음을 보여준다는 데 있습니다.

또한 이 결과는 현재의 행렬 라이브러리가 n^2.371177의 속도로 실행된다는 뜻이 아닙니다. 이는 행렬 곱셈의 점근적 이론 상한에 관한 주장입니다. 고전적인 대수 기법과 머신러닝 기반 최적화, 자동 진화 탐색을 결합하는 방식이 다른 문제에도 적용될지는 제공된 자료만으로 판단할 수 없습니다. 그럼에도 이번 논문은 AI 보조 알고리즘 발견의 구체적인 사례로 볼 수 있습니다.

출처: Hugging Face Daily Papers