기술 요약: 몫 트리 산술 (Quotient Tree Arithmetic, QTA)

문제 정의

수십 년간 과학 계산 및 머신러닝의 표준이었던 부동 소수점 산술(IEEE 754)은 다음과 같은 근본적인 한계를 가집니다:

1. 부정확한 표현: 흔히 쓰이는 십진수(예: 0.1)를 정확하게 표현할 수 없어, $0.1 + 0.2 \neq 0.3$과 같은 오류가 발생합니다.
2. 언더플로우 및 기울기 소실(Vanishing Gradients): 매우 작은 값들이 0으로 반올림되어, 기울기 곱이 0으로 붕괴되는 딥 뉴럴 네트워크의 기울기 소실 문제를 야기합니다.
3. 비결정성(Non-Determinism): 반올림 모드와 융합 곱셈-누산(FMA) 가용성, 피연산자 순서로 인해 하드웨어, 컴파일러 버전, 연산 순서에 따라 결과가 달라집니다.
4. 비교 휴리스틱: 등가성(Equality) 확인을 위해 임의의 $\epsilon$-허용 오차(tolerance)가 필요하며, 이는 신뢰하기 어렵습니다.

GMP, Decimal과 같은 기존의 임의 정밀도 라이브러리는 심각한 성능 비용을 초래하는 반면, 양자화(INT8, FP8)는 정밀도를 희생하고 체계적인 오류를 도입합니다.

방법론

본 논문은 정확하고 근사적인 계산을 위한 통합 프레임워크로서 **유리수 쌍 산술(Rational Pair Arithmetic, RPA)**과 그 확장형인 **몫 트리 산술(Quotient Tree Arithmetic, QTA)**을 제안합니다.

1. 유리수 쌍 산술 (RPA)

핵심 통찰은 **IEEE 754 정수 정확성 윈도우(Integer Exactness Window)**에 기반합니다. IEEE 754 배정밀도 부동 소수점은 $(-2^{53}, 2^{53})$ 범위 내의 모든 정수를 정확하게 표현합니다.

• 표현: 실수 형태의 양은 IEEE 더블(double) 타입의 정렬된 쌍 $(n, d)$로 저장되며, 엄격하게 정수로 취급됩니다. 값은 $n/d$이며, 지연 평가(lazily evaluated)됩니다.
• 산술 연산: 정수 구성 요소에 대해 연산이 수행됩니다:
  • $(a, b) + (c, d) = (ad + bc, bd)$
  • $(a, b) \times (c, d) = (ac, bd)$
  • 비교는 교차 곱셈($ad < bc$)을 통해 수행됩니다.
• 정확성: $|n|, |d| < 2^{53}$인 한, 모든 산술은 다중 정밀도 라이브러리 없이도 정확합니다. 이는 실용적인 도메인(예: 약 900억 달러 규모의 센트 단위 화폐) 및 과학적 측정값을 충분히 커버합니다.

2. 클린업(Cleanup) 연산

분자와 분모의 크기가 무한히 커지는 것(즉, $2^{53}$ 윈도우를 초과하는 것)을 방기하기 위해, 시스템은 클린업(Cleanup) 연산을 사용합니다.

• 메커니즘: $n$과 $d$를 $\gcd(|n|, |d|)$로 나눕니다.
• 하드웨어 제안: 본 논문은 벡터화된 GCD 축소를 수행하여 RPA가 단정밀도 부동 소수점과 유사한 처리량을 갖도록 하는 새로운 SIMD 명령인 **RatCleanup**을 제안합니다.
• 추적된 상쇄(Tracked Cancellation): 구조화된 계산(예: 고정된 분모를 가진 화폐 계산)의 경우, 컴파일러는 전체 GCD 알고리즘 없이 요소를 상쇄하여 오버헤드를 $O(1)$로 줄일 수 있습니다.

3. 몫 트리 산술 (중첩된 RPA)

이 프레임워크는 분자나 분모가 다시 유리수 쌍이 되어 기호적 표현 트리(symbolic expression tree)를 형성하는 **중첩된 유리수 쌍(Nested Rational Pairs)**으로 확장됩니다.

• 지연 평가(Deferred Evaluation): 표현식은 트리 형태로 유지됩니다. 평가(단일 쌍으로의 평탄화)는 구체적인 부동 소수점 결과가 명시적으로 요청될 때까지 지연됩니다.
• 제한된 깊이: 정리 4.2는 트리 깊이가 연산당 최대 1씩 증가함($m$번의 연산에 대해 총 크기 $O(m)$)을 증명하여, 일반적인 기호 대수 시스템에서 나타나는 조합 폭발($O(2^m)$)을 방지함을 보여줍니다.
• 교차 상쇄(Cross-Cancellation): 정리 4.3은 어떠한 나눗셈이 일어나기 전이라도 분자와 분모 서브트리에 공통으로 나타나는 인수를 기호적으로 상쇄할 수 있음을 확립합니다. 이는 초월수(예: $e^x$)에 대해서도 해당 값이 참조 동일(reference-equal)하다면 적용됩니다.

주요 기여

1. RPA의 공식적 정의: 하드웨어 가속이 가능한 유리수 타입을 만들기 위해 IEEE 정수 정확성 윈도우를 활용했습니다.
2. 클린업 프리미티브: 벡터화된 GCD 축소를 수행하는 제안된 하드웨어 명령어(RatCleanup)와, 이 명령어가 값을 정확성 윈도우 내로 유지하여 무한히 정확성을 보장한다는 이론적 증명을 제공합니다.
3. 중첩된 유리수 쌍 대수: 제한된 깊이 성장, $O(k)$ 단계의 평탄화, 그리고 교차 상쇄 정리를 포함한 기호적 중첩에 대한 공식적 처리를 제공합니다.
4. 안정성 정리:
   • 지연 안정성(Deferred Stability): 지연 평가는 반올림 오차를 성급한 평가(eager evaluation) 시의 $O(m)$ ULP에서 $O(1)$ ULP로 줄입니다.
   • 기울기 소실 불가능성(정리 8.1): RPA와 클린업 환경에서, 0이 아닌 유리수 쌍의 곱이 구조적으로 0이 되는 것은 불가능합니다. 이는 딥 네트워크의 기울기 언더플로우를 제거합니다.
5. 교차 하드웨어 결정성: 고정된 계산 순서가 주어지면, RPA 결과는 하드웨어의 반올림 모드, FMA 가용성 또는 드라이버 버전에 독립적입니다.

결과 및 주장

본 논문은 벤치마크보다는 이론적 증명과 분석적 추정치를 제공합니다:

• 처리량: 분석적 추정에 따르면, 플랫(flat) RPA는 FP32보다 약 $5\text{--}18\times$ 느리지만(연산 및 클린업 비용에 따라 다름), FP64와는 유사한 수준입니다. 제안된 RatCleanup 명령어를 사용하면 오버헤드를 관리 가능한 수준으로 유지할 수 있습니다.
• 기울기 안정성: 기울기 소실의 구조적 불가능성은 스킵 연결(skip connection)이나 게이팅 메커니즘 없이도 매우 깊은 "순수(plain)" 네트워크(수백 개의 레이어)의 이론적 타당성을 부여합니다.
• 정확한 수렴: 수렴 기준을 휴리스틱 임계값($|L_t - L_{t-1}| < \epsilon$)이 아닌 정확한 등가성($L_t = L_{t-1}$)으로 정의할 수 있습니다.
• 대역폭 효율성: 계산을 기호 단계(트리 구축 및 상쇄)와 수치 단계(구체화)로 분리함으로써 QTA는 메모리 트래픽을 줄입니다. 공유된 서브트리(예: 가중치)는 한 번만 로드되며, 기호적 상쇄는 중간 메모리 쓰기를 제거합니다.

의의

본 논문은 QTA를 단순한 숫자 형식이 아니라, 기호 조작과 수치 평가를 분리하는 **계산 기질(computational substrate)**로 위치시킵니다.

• 구조적 지능: 현대 AI 시스템은 모든 쿼리에 대해 "최악의 경우 비용"을 지불합니다. QTA는 대수적 특성(상쇄, 지연된 나눗셈)을 활용하여 실제 필요한 계산을 줄이는 구조적 지능 계층을 도입하며, 이는 캐싱이나 희소 주의집중(sparse attention)과 유사하지만 정확한 보증을 제공합니다.
• 안전 및 인증: 자율 주행 차량, 의료 AI와 같은 안전 필수 영역에서, 확률적 휴리스틱으로부터 벗어나 인증된 미분(정상 상태의 정확한 증명)과 재현 가능한 훈련을 제공할 수 있는 능력은 패러다임의 전환을 의미합니다.
• 하드웨어 독립성: 이는 결과의 "비트 부패(bit-rot)"를 제거하여 결정론적인 과학 계산을 위한 경로를 제시하며, 서로 다른 GPU 세대나 CUDA 버전 간의 차이를 없앱니다.

저자들은 QTA가 원시적인 처리량을 희생하는 대신 정확성을 취하지만, 계산 비용보다 오류의 비용이 더 높은 과학 계산 및 안전 필수 머신러닝에서는 이 트레이드오프가 필수적이라고 결론짓습니다. 제안된 RatCleanup 명령어는 이 프레임워크를 기존 하드웨어 아키텍처에서 실용적으로 만드는 핵심 동력으로 식별되었습니다.