🔢 mathematics

Efficient approximations of matrix multiplication using truncated decompositions

이 논문은 대규모 밀집 행렬 곱셈을 효율적으로 근사하기 위해 절단된 특이값 분해(truncated SVD)와 순환 분해(circulant decomposition)를 활용하며, 이를 통해 LLM(대규모 언어 모델)의 연산 속도를 크게 향상시킬 수 있는 $\mathcal{O}(n^2 \log n)$ 복잡도의 알고리즘을 제안합니다.

원저자: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

게시일 2026-04-27

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

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

1. 문제 상황: "거대한 도서관의 책 정리하기"

행렬 곱셈은 마치 수만 권의 책이 쌓인 거대한 도서관에서 두 종류의 방대한 목록을 대조하여 새로운 목록을 만드는 작업과 같습니다.

기존 방식 (Exact Multiplication): 모든 책의 제목, 저자, 출판일, 페이지 수를 하나하나 완벽하게 대조합니다. 결과는 완벽하지만, 시간이 너무 오래 걸려서 도서관 전체를 정리하는 데 몇 년이 걸릴 수도 있습니다. (컴퓨터로 치면 엄청난 계산량과 전력이 소모됩니다.)
기존의 근사 방식 (Randomized Algorithms): 책 몇 권만 무작위로 골라 대조합니다. 빠르긴 하지만, 너무 대충 해서 결과물이 엉망진창이 될 때가 많습니다.

2. 이 논문의 핵심 아이디어: "중요한 것부터 먼저, 나머지는 덤으로"

연구진은 **"모든 데이터를 똑같은 비중으로 다룰 필요가 있을까?"**라는 질문을 던졌습니다. 이들은 행렬을 세 가지 방식으로 '해체'해서 접근합니다.

① SVD (특이값 분해): "도서관의 베스트셀러 찾기"

도서관의 모든 책을 다 보는 대신, 가장 영향력 있는 '베스트셀러' 100권만 먼저 완벽하게 분석합니다. 그리고 나머지 '비주류 도서'들은 아주 가볍게 훑어봅니다. 베스트셀러만 잘 파악해도 도서관의 전체적인 흐름(행렬의 핵심 정보)은 거의 다 알 수 있기 때문입니다.

② Circulant Decomposition (순환 분해): "패턴 찾기"

어떤 데이터들은 일정한 **'리듬'이나 '패턴'**을 가지고 있습니다. 예를 들어, 매일 아침 9시에 들어오는 택배처럼 규칙적인 패턴이 있다면, 그 패턴 하나만 제대로 파악해도 수만 개의 데이터를 일일이 계산할 필요가 없습니다. 이 논문은 수학적인 '회전(Cycle)' 개념을 이용해 이 패턴을 찾아내어 계산 속도를 획기적으로 높였습니다.

③ Fourier-based Sparsification (푸리에 기반 희소화): "핵심 멜로디 추출"

음악에서 수많은 악기 소리가 섞여 있어도 우리는 '메인 멜로디'만 들으면 노래를 이해할 수 있죠? 이 방식은 데이터에서 **가장 강렬한 '멜로디(주요 주파수)'**만 남기고 나머지 잔잔한 소음(Noise)은 지워버리는 방식입니다. 데이터가 가벼워지니 계산이 엄청나게 빨라집니다.

3. 이 논문의 필살기: "1차 근사 (First-order Approximation)"

이 논문이 진짜 똑똑한 점은 여기서 나옵니다. 보통은 "중요한 것만 계산하고 끝!"이라고 하지만, 이들은 **"중요한 것들끼리 곱하고, + 중요한 것과 나머지(찌꺼기)를 곱하고 + 나머지와 중요한 것을 곱하자!"**라는 전략을 씁니다.

이것을 **'1차 근사'**라고 부르는데, 마치 요리를 할 때 메인 재료(고기)만 먹는 게 아니라, 고기와 소스, 소스와 채소의 조화까지 살짝 맛을 봐주는 것과 같습니다. 이렇게 하면 계산량은 크게 늘리지 않으면서도, 결과물의 정확도는 거의 완벽(오차 1% 미만)에 가깝게 끌어올릴 수 있습니다.

4. 왜 이게 중요한가요? (실제 적용: ChatGPT 같은 AI)

이 기술이 가장 빛을 발하는 곳은 바로 **거대언어모델(LLM, 예: ChatGPT)**입니다.

AI가 우리가 입력한 긴 문장을 읽고 이해할 때(Prefilling 단계), 내부적으로는 상상할 수 없을 만큼 거대한 행렬 곱셈이 일어납니다. 이 논문의 방식을 적용하면:

속도: AI의 답변 속도가 훨씬 빨라집니다.
효율: 똑같은 성능의 AI를 훨씬 적은 전력과 비용으로 돌릴 수 있습니다.
정확도: 대충 계산하는 게 아니라 '똑똑하게' 계산하기 때문에, AI가 헛소리(Perplexity 저하)를 할 확률을 최소화합니다.

요약하자면:

이 논문은 **"모든 데이터를 똑같이 힘들게 계산하지 말고, 데이터 속에 숨겨진 '핵심 패턴'과 '중요한 주인공'을 찾아내어 효율적으로 계산하자! 그러면 속도는 엄청나게 빨라지면서도 결과는 거의 완벽하다!"**라는 것을 수학적으로 증명하고 실험으로 보여준 연구입니다.

[기술 요약] 절단 분해를 이용한 행렬 곱셈의 효율적 근사

1. 문제 정의 (Problem Statement)

대규모 밀집 행렬(Large Dense Matrices)의 곱셈은 딥러닝(LLM, CNN), 물리 시뮬레이션(DFT) 등 현대 컴퓨팅의 핵심적인 병목 구간입니다.

기존 방식의 한계: Strassen이나 Coppersmith-Winograd와 같은 알고리즘은 이론적 복잡도( $O(n^{2.37})$ )는 낮지만 실제 구현이 매우 어렵습니다. 반면, 기존의 무작위 근사(Randomized Approximation) 알고리즘들은 계산량은 줄일 수 있으나, 실용적인 수준의 정밀도(Precision)를 확보하기 어렵다는 단점이 있습니다.
핵심 과제: 계산 복잡도를 $O(n^2 \log n)$ 수준으로 낮추면서도, 상대 오차(Relative Error)를 1% 이내로 유지할 수 있는 실용적인 근사 행렬 곱셈 방법론이 필요합니다.

2. 방법론 (Methodology)

본 논문은 행렬을 **'지배적인 성분(Dominant components)'**과 **'잔차(Residue)'**로 분해한 후, 이를 이용한 1차 근사(First-order approximation) 방식을 제안합니다.

2.1. 핵심 근사 원리

행렬 $A$ 와 $B$ 를 각각 $A = A_i + \Delta A$ , $B = B_k + \Delta B$ 로 분해했을 때, 곱셈 $AB$를 다음과 같이 근사합니다:
$M \approx \sum A_i B + \sum \Delta A B_k$
이는 단순한 0차 근사(지배적 성분끼리의 곱)보다 훨씬 정밀하며, 계산 복잡도를 크게 높이지 않으면서 오차를 획기적으로 줄입니다.

2.2. 세 가지 주요 분해 방식

SVD(특이값 분해) 기반: 행렬을 상위 $k$ 개의 특이값 성분으로 분해합니다. 무작위 알고리즘(Randomized SVD)을 사용하여 $O(kn^2)$ 의 비용으로 효율적인 계산이 가능합니다.
Circulant(순환) 분해 기반: 행렬을 순환 행렬들의 합으로 분해합니다. FFT(고속 푸리에 변환)를 활용하여 $O(n^2 \log n)$ 의 복잡도로 계산할 수 있으며, 행렬에 주기적 구조가 있을 때 매우 강력합니다.
Fourier-domain Sparsification(푸리에 도메인 희소화) 기반: 행렬을 푸리에 변환하여 주파수 영역에서 지배적인 성분만 남기고 나머지를 제거(Sparsification)하여 계산합니다.

3. 주요 기여 (Key Contributions)

새로운 근사 프레임워크 제안: 단순한 저계수(Low-rank) 근사를 넘어, 잔차 항을 포함하는 1차 근사법을 통해 정밀도와 효율성의 균형을 맞췄습니다.
오차 분석 및 추정 이론: 행렬의 성분이 독립적이거나 특정 분포(Haar distribution 등)를 따를 때, 곱셈 결과의 Frobenius norm 오차를 사전에 예측할 수 있는 수학적 경계(Error bounds)를 유도했습니다.
적응형 분해 선택: 행렬의 특성(주기성, 특이값 분포 등)에 따라 SVD, Circulant, Fourier 중 가장 적합한 분해 방식을 선택할 수 있는 이론적 근거를 제시했습니다.

4. 실험 결과 (Results)

4.1. 수치적 성능

정밀도: 다양한 유형의 행렬(Toeplitz, Hankel, Symmetric 등)에 대해 1% 이내의 상대 오차를 달성했습니다.
효율성: 기존의 무작위 외적(Randomized outer product) 방식보다 훨씬 적은 연산량으로 동일한 정밀도를 구현했습니다. 특히 SVD 기반 1차 근사는 기존 방식보다 수십 배 빠른 속도를 보였습니다.

4.2. LLM(대규모 언어 모델) 적용 사례

실제 적용: OPT-125M 및 OPT-1.3B 모델의 Prompt Prefilling(프롬프트 프리필링) 단계에 적용했습니다.
성능 향상:
- OPT-1.3B 모델에서 약 **3.07배의 실시간 속도 향상(Wall-clock speed-up)**을 달성했습니다.
- Perplexity(혼란도): 모델의 예측 정확도를 나타내는 Perplexity 값은 기본 모델(Baseline)과 거의 차이가 없는 수준(Near-lossless)을 유지했습니다. 이는 근사 계산이 모델의 지능을 저하시키지 않으면서도 연산 속도만 획기적으로 높일 수 있음을 증명합니다.

5. 의의 (Significance)

본 논문은 이론적인 행렬 계산 복잡도 개선에 그치지 않고, 실제 LLM 추론 가속화라는 매우 실용적인 응용 분야를 제시했습니다.

하드웨어 친화적: FFT 및 행렬-벡터 곱셈 위주의 연산으로 구성되어 현대의 GPU 및 가속기 구조에서 효율적으로 동작합니다.
확장성: 모델의 파라미터 수가 증가할수록(예: 1조 개 규모), 제안된 방식의 계산 이득은 기하급수적으로 커질 수 있음을 시사합니다.
실용적 가이드라인: 어떤 행렬에 어떤 분해법을 써야 하는지, 그리고 계산 전후에 오차를 어떻게 관리해야 하는지에 대한 명확한 수학적 가이드를 제공합니다.