TL;DR

1984년에 발견된 랜덤 프로젝션의 거리 보존 성질(JL Lemma)이, 40년 후 LLM의 KV Cache를 극한까지 압축하는 핵심 도구가 됩니다. QJL(2024) → PolarQuant(2025) → TurboQuant(2025)로 이어지는 연구 흐름을 따라가며, “랜덤 회전 한 번이면 최적 양자화가 가능하다”는 이론적 결론에 도달합니다. 다만 실전에서는 이론의 핵심 요소인 QJL 잔차 보정이 오히려 해로울 수 있고, 선행 연구(RaBitQ)와의 관계에 대한 학술적 논쟁도 진행 중입니다.

그림 1. JL Lemma(1984)에서 TurboQuant(2025)까지, 40년의 연구 여정.

KV Cache 문제

LLM 서빙을 해본 분이라면 알겠지만, long-context 추론에서 진짜 병목은 모델 가중치가 아니라 KV Cache입니다. Transformer가 토큰을 생성할 때마다 이전 모든 토큰의 Key-Value 임베딩을 메모리에 들고 있어야 하기 때문입니다.

Attention score [25]를 보면 왜 그런지 바로 알 수 있습니다 (여기서는 \(1/\sqrt{d_{k}}\) 스케일링을 생략한 간략화된 형태입니다):

\[\text{Score}=\text{softmax} \big( [\langle q_{n},k_{1}\rangle ,\langle q_{n},k_{2}\rangle ,\ldots ,\langle q_{n},k_{n}\rangle ] \big)\]

여기서 \(q_{n}\)은 현재 쿼리이고, \(k_{1},\ldots ,k_{n}\)은 캐시된 키 임베딩입니다. 내적 \(\langle q_{n},k_{i}\rangle\)는 “\(i\)번째 과거 토큰이 지금 질문에 얼마나 관련 있는가?”를 측정합니다. 대화가 길어질수록 참조해야 할 키의 수가 늘어나고, KV Cache는 선형적으로 커집니다.

구체적인 숫자로 보면 그 규모가 명확합니다.

그림 2. 컨텍스트가 길어질수록 KV Cache가 모델 가중치를 압도합니다. 128K에서는 4배 차이.

Llama-3-8B의 가중치를 INT4로 양자화하면 약 4GB. 그런데 128K 컨텍스트를 처리하면 KV Cache가 16GB 이상. 모델 가중치의 4배입니다. (단일 시퀀스, FP16 KV, 32레이어 × 8 KV헤드 × 128 head_dim × 2(K+V) × 2바이트 × 128K 토큰 기준의 대략적 추정입니다.) GPTQ니 AWQ니 해서 가중치를 아무리 줄여봤자, KV Cache를 방치하면 의미가 없습니다.

양자화 오버헤드 문제

당연히 KV Cache도 양자화하려는 시도가 있었습니다. KIVI [23]는 키와 밸류에 비대칭 비트를 할당하여(키 2비트 per-channel, 밸류 2비트 per-token) 튜닝 없이 2비트까지 압축합니다. KVQuant [24]는 여기에 outlier 분리, 비균일 코드북, dense-and-sparse 분해 등을 결합하여 10M 토큰 수준의 초장문 컨텍스트를 목표로 합니다. 두 방법 모두 공통적으로, 데이터를 블록 단위로 나누고 각 블록마다 scale(스케일)과 zero-point(영점)라는 보조 상수를 저장합니다.

문제는 이 보조 상수의 오버헤드가 생각보다 크다는 것입니다. FP16으로 저장하는 경우를 예로 들면:

• 그룹 크기 128 + 4비트 양자화: 128 × 4비트 + 16비트(scale) + 16비트(zero) = 544비트, 실질 4.25비트/값

• 그룹 크기 32 + 4비트 양자화: 32 × 4비트 + 32비트 = 160비트, 실질 5비트/값

FP32로 저장하면 오버헤드는 더 커져서, 그룹 크기 32에서 실질 6비트/값까지 올라갑니다.

그룹을 작게 나눌수록 품질은 좋아지지만, 오버헤드가 점점 커져서 “4비트 양자화”라고 해놓고 실제로는 6비트를 쓰게 됩니다. 이 글에서 다루는 QJL, PolarQuant, TurboQuant는 모두 이 오버헤드 문제를 근본적으로 없애려는 시도이고, 그 출발점이 1984년의 순수 수학이라는 게 좀 의외입니다.

랜덤 프로젝션의 거리 보존 성질

Johnson-Lindenstrauss Lemma

1984년에 Johnson과 Lindenstrauss [20]가 발견한 사실은, 처음 들으면 직관에 반합니다: 고차원 벡터를 랜덤하게 저차원으로 사영하면, 점들 사이의 거리가 거의 그대로 보존됩니다.

JL Lemma의 핵심 (Lemma 1.1 [1])

\(\mathbb{R}^{d}\)의 점들을 \(\mathbb{R}^{m}\)으로 랜덤 사영하면, 모든 쌍 간의 거리가 \((1\pm \epsilon )\)로 보존됩니다. 여기서 중요한 건, 필요한 목표 차원 \(m=O(\epsilon ^{-2}\log n)\)이 원래 차원 \(d\)에 전혀 의존하지 않는다는 점입니다.

그림 3. JL Lemma의 직관: 랜덤 프로젝션은 점들 사이의 거리를 거의 보존합니다.

100만 차원의 벡터든 10억 차원의 벡터든, \(n\)개 점의 쌍별 거리를 10% 오차로 보존하려면 \(m\approx 100\cdot \log n\)차원이면 됩니다. 구체적으로, JL 변환을 \(f(x)=\frac{1}{\sqrt{m}}Sx\)로 정의하면 (여기서 \(S\in \mathbb{R}^{m\times d}\)의 각 원소는 \(N(0,1)\)에서 i.i.d. [1][21]), 분포적 JL Lemma (Lemma 1.2 [1])는 다음을 보장합니다:

\[\Pr \big[ | \|f(x)\|_{2}^{2}-\|x\|_{2}^{2} | >\epsilon \|x\|_{2}^{2} \big] \le \delta \text{when }m=O(\epsilon ^{-2}\log (1/\delta ))\]

\(\frac{1}{\sqrt{m}}\) 정규화가 핵심입니다: \(S_{ij}\sim N(0,1)\)이면 \(\mathbb{E}[\|Sx\|^{2}]=m\|x\|^{2}\)이므로, \(\frac{1}{\sqrt{m}}\)을 곱해야 \(\mathbb{E}[\|f(x)\|^{2}]=\|x\|^{2}\)이 됩니다. (QJL [2]에서는 이 정규화를 \(S\) 자체가 아닌 추정기의 \(1/m\) 팩터로 흡수합니다.)

“길이가 보존된다”는 성질에서 곧바로 내적 보존 (Corollary 1.5 [1])이 따라 나옵니다:

\[| \langle f(x),f(y)\rangle -\langle x,y\rangle | \le \epsilon \|x\|_{2}\|y\|_{2}\]

Attention 자체가 내적 연산이라는 걸 생각하면, 이 성질이 왜 중요한지 바로 감이 옵니다. (증명은 편극 항등식 \(4\langle u,v\rangle =\|u+v\|^{2}-\|u-v\|^{2}\)에서 나옵니다 [1].)

코드로 확인: JL 프로젝션이 거리를 보존하는가?

import numpy as np
d, m, n = 1000, 50, 200  # 1000차원 → 50차원, 200개 벡터
X = np.random.randn(n, d)
S = np.random.randn(m, d) / np.sqrt(m)  # 1/√m 정규화
X_proj = (S @ X.T).T

# 원래 공간 vs 프로젝션 공간의 쌍별 거리 비교
i, j = 0, 1
dist_orig = np.linalg.norm(X[i] - X[j])
dist_proj = np.linalg.norm(X_proj[i] - X_proj[j])
print(f"원본 거리: {dist_orig:.3f}, 프로젝션 거리: {dist_proj:.3f}, 비율: {dist_proj/dist_orig:.3f}")
# → 비율이 1에 가까움 (1000차원을 50차원으로 줄여도!)

import numpy as np
d, m, n = 1000, 50, 200  # 1000차원 → 50차원, 200개 벡터
X = np.random.randn(n, d)
S = np.random.randn(m, d) / np.sqrt(m)  # 1/√m 정규화
X_proj = (S @ X.T).T

# 원래 공간 vs 프로젝션 공간의 쌍별 거리 비교
i, j = 0, 1
dist_orig = np.linalg.norm(X[i] - X[j])
dist_proj = np.linalg.norm(X_proj[i] - X_proj[j])
print(f"원본 거리: {dist_orig:.3f}, 프로젝션 거리: {dist_proj:.3f}, 비율: {dist_proj/dist_orig:.3f}")
# → 비율이 1에 가까움 (1000차원을 50차원으로 줄여도!)

import numpy as np
d, m, n = 1000, 50, 200  # 1000차원 → 50차원, 200개 벡터
X = np.random.randn(n, d)
S = np.random.randn(m, d) / np.sqrt(m)  # 1/√m 정규화
X_proj = (S @ X.T).T

# 원래 공간 vs 프로젝션 공간의 쌍별 거리 비교
i, j = 0, 1
dist_orig = np.linalg.norm(X[i] - X[j])
dist_proj = np.linalg.norm(X_proj[i] - X_proj[j])
print(f"원본 거리: {dist_orig:.3f}, 프로젝션 거리: {dist_proj:.3f}, 비율: {dist_proj/dist_orig:.3f}")
# → 비율이 1에 가까움 (1000차원을 50차원으로 줄여도!)

JL 행렬은 어떻게 발전해왔나

JL 변환을 실현하는 랜덤 행렬(JL Distribution)은 40년간 꾸준히 발전해왔습니다 [1]. 처음에는 행렬 전체를 가우시안(\(N(0,1)\)) [21]이나 Rademacher(\(\pm 1\))로 채운 Dense 구성(\(O(md)\) 시간)에서 시작하여, Achlioptas [22]가 원소의 2/3를 0으로 만드는 Sparse 구성을 제안했습니다. Sparse 구성이 가능한 이유는 흥미롭습니다: 벡터의 \(\ell _{\infty }/\ell _{2}\) 비율이 작으면, 즉 에너지가 특정 좌표에 집중되지 않고 고르게 퍼져 있으면, 행렬의 대부분을 0으로 채워도 거리 보존이 가능합니다 (Theorem 1.8 [1]). 최종적으로 Ailon과 Chazelle [17]는 이 관찰을 구조적으로 활용하는 FFT(Fast Fourier Transform) 기반 구성(FJLT)을 제안했습니다: 먼저 Hadamard 변환으로 \(\ell _{\infty }/\ell _{2}\) 비율을 강제로 줄인 뒤, sparse 행렬로 프로젝션합니다.

특히 중요한 것이 Ailon과 Chazelle가 제안한 Fast JL Transform(FJLT) [17]입니다:

\[f(x)=P\cdot H\cdot D\cdot x\]

세 행렬 각각의 역할을 보면:

\(D\): 대각 Rademacher 행렬 — 대각선에 \(+1\) 또는 \(-1\)이 동일 확률로 놓인 행렬입니다. 벡터에 곱하면 각 좌표의 부호를 랜덤하게 뒤집는 효과가 있습니다. 예를 들어 \(d=4\)일 때:

\[D= \Big( \begin{array}{cccc}+1&0&0&0\\ 0&-1&0&0\\ 0&0&+1&0\\ 0&0&0&-1\end{array} \Big) ,D \Big( \begin{array}{c}3\\ 7\\ 2\\ 5\end{array} \Big) = \Big( \begin{array}{c}3\\ -7\\ 2\\ -5\end{array} \Big)\]

이 단계의 목적은 입력 벡터의 에너지가 특정 좌표에 집중되어 있더라도, 부호를 섞어서 다음 단계(Hadamard)가 에너지를 고르게 분산시킬 수 있도록 준비하는 것입니다.

\(H\): Walsh-Hadamard 행렬 — \(\pm 1\)로만 구성된 직교 행렬로, 재귀적으로 정의됩니다:

\[H_{1}=(1),H_{2}=\frac{1}{\sqrt{2}} \bigg( \begin{array}{cc}1&1\\ 1&-1\end{array} \bigg) ,H_{4}=\frac{1}{2} \Big( \begin{array}{cccc}1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\end{array} \Big)\]

벡터에 \(H\)를 곱하면 모든 좌표 간의 덧셈/뺄셈 조합이 일어나, 에너지가 한 좌표에 집중된 벡터도 모든 좌표에 고르게 분산됩니다. 핵심은 FFT와 같은 butterfly 구조 덕분에 \(O(d\log d)\)에 계산 가능하고, \(\pm 1\)만 사용하므로 곱셈이 전혀 필요 없다는 점입니다—NPU 같은 하드웨어 가속기에 특히 유리합니다.

\(P\): Sparse 사영 행렬 — 대부분의 원소가 0인 \(m\times d\) 행렬로, \(d\)차원을 \(m\)차원으로 축소합니다. \(HD\) 단계 후 벡터의 에너지가 이미 고르게 퍼져 있으므로, sparse한 행렬로도 충분히 좋은 프로젝션이 가능합니다 [1]. 예를 들어 \(d=4,m=2\)일 때:

\[P= \bigg( \begin{array}{cccc}0&1.2&0&0\\ 0&0&0&-0.8\end{array} \bigg)\]

이 세 단계를 결합하면: \(D\)가 부호를 섞고, \(H\)가 에너지를 분산시키고, \(P\)가 차원을 줄입니다. 전체 시간 복잡도는 \(H\) 단계의 \(O(d\log d)\)가 지배하며, 이는 Dense 구성의 \(O(md)\)보다 훨씬 빠릅니다. 뒤에서 살펴볼 QJL, PolarQuant, TurboQuant는 모두 이 FJLT의 \(HD\) 단계—랜덤 부호 뒤집기 + Hadamard 변환—를 핵심 전처리로 활용합니다. 차이는 \(P\)(차원 축소) 대신 양자화를 적용한다는 점입니다.

코드로 확인: Hadamard가 에너지를 분산시키는가?

import numpy as np
from scipy.linalg import hadamard
d = 128
H = hadamard(d) / np.sqrt(d)       # 정규화된 Hadamard (d는 2의 거듭제곱)
D = np.diag(np.random.choice([-1, 1], d))  # 랜덤 부호

x = np.zeros(d); x[0] = 1.0      # 에너지가 한 좌표에 집중
y = H @ D @ x                      # HD 변환
print(f"변환 전 max/norm: {np.max(np.abs(x)):.3f}")   # → 1.000
print(f"변환 후 max/norm: {np.max(np.abs(y)):.3f}")   # → 0.088 (에너지 분산!)

import numpy as np
from scipy.linalg import hadamard
d = 128
H = hadamard(d) / np.sqrt(d)       # 정규화된 Hadamard (d는 2의 거듭제곱)
D = np.diag(np.random.choice([-1, 1], d))  # 랜덤 부호

x = np.zeros(d); x[0] = 1.0      # 에너지가 한 좌표에 집중
y = H @ D @ x                      # HD 변환
print(f"변환 전 max/norm: {np.max(np.abs(x)):.3f}")   # → 1.000
print(f"변환 후 max/norm: {np.max(np.abs(y)):.3f}")   # → 0.088 (에너지 분산!)

import numpy as np
from scipy.linalg import hadamard
d = 128
H = hadamard(d) / np.sqrt(d)       # 정규화된 Hadamard (d는 2의 거듭제곱)
D = np.diag(np.random.choice([-1, 1], d))  # 랜덤 부호

x = np.zeros(d); x[0] = 1.0      # 에너지가 한 좌표에 집중
y = H @ D @ x                      # HD 변환
print(f"변환 전 max/norm: {np.max(np.abs(x)):.3f}")   # → 1.000
print(f"변환 후 max/norm: {np.max(np.abs(y)):.3f}")   # → 0.088 (에너지 분산!)

딥러닝 양자화와의 연결점

40년 된 수학 이론이 KV Cache 압축과 연결되는 지점은 세 가지입니다.

첫째, 에너지 분산이라는 동기가 동일합니다. SmoothQuant [6]은 대각 스케일링으로 outlier를 분산시키고, QuIP [18]과 QuIP# [19]은 Hadamard 회전을 직접 사용합니다. 방법은 다르지만(SmoothQuant는 데이터 의존적 대각 행렬, FJLT는 랜덤 Rademacher + Hadamard), 목적은 같습니다: 일부 채널에 집중된 에너지를 모든 차원으로 분산시켜 균일 양자화의 효율을 높이는 것.

둘째, 내적 보존은 정확도 유지의 중요한 전제입니다. 신경망 추론은 행렬 곱(\(y=Wx\))의 연쇄이고, 양자화가 내적을 잘 보존하면(JL Corollary 1.5 [1]) 개별 선형 연산의 출력이 보존됩니다. 다만, softmax나 layernorm 같은 비선형 연산을 거치면 내적 보존만으로 최종 정확도가 보장되지는 않습니다—이 한계는 섹션 7에서 다시 다룹니다.

셋째, \(\ell _{\infty }/\ell _{2}\) 비율은 양자화 효율의 척도입니다. 이 비율은 “벡터의 에너지가 얼마나 한 좌표에 집중되어 있는가”를 측정합니다 (Theorem 1.8 [1]). 비율이 작을수록—에너지가 고르게 퍼져 있을수록—균일 양자화 그리드가 효율적으로 작동하여 더 적은 비트로 충분합니다. 이 관찰이 기존 양자화 기법들의 핵심 전략을 설명합니다:

• SmoothQuant [6]은 대각 스케일링으로 활성화의 outlier를 가중치 쪽으로 이전하여, 활성화의 \(\ell _{\infty }/\ell _{2}\) 비율을 줄입니다. 데이터 의존적(캘리브레이션 필요)이고, 변환 후에도 표준 균일 양자화(scale + zero-point)를 사용합니다.

• SpinQuant [7]은 직교 회전을 학습하여 분포를 균일화합니다. 회전 후에도 여전히 표준 균일 양자화를 적용하므로, per-group scale/zero-point 오버헤드가 남습니다.

• 뒤에서 살펴볼 TurboQuant 계열 [2][3][4]은 한 걸음 더 나아갑니다: 랜덤 회전으로 \(\ell _{\infty }/\ell _{2}\) 비율을 줄이는 데 그치지 않고, 회전 후 분포가 해석적으로 예측 가능하다는 사실을 이용하여 양자화기 자체를 데이터 없이 최적 설계합니다. 오버헤드가 전혀 없습니다.

이제 이 도구들이 실제 KV Cache 압축에 어떻게 쓰이는지 봅시다.

QJL: 부호 비트 하나로 내적 복원

비대칭 양자화 — 키만 1비트로

KV Cache에서 키는 대화가 끝날 때까지 메모리에 상주하지만, 쿼리는 현재 토큰 생성에만 쓰이고 사라집니다. QJL [2]은 이 비대칭성을 활용합니다: 키와 쿼리 모두 같은 랜덤 행렬 \(S\)로 프로젝션하되, 키는 프로젝션 결과의 부호 비트(sign bit)만 저장하고, 쿼리는 프로젝션 결과를 full precision으로 유지합니다. 메모리에 캐시되는 것은 키뿐이니, 키만 극단적으로 압축하는 비대칭 설계입니다.

그림 4. QJL의 비대칭 파이프라인. 키는 1비트로 극단 압축하고, 쿼리는 full precision을 유지합니다.

내적 추정기는 다음과 같습니다:

\[\hat{\langle q,k\rangle }=\frac{\sqrt{\pi /2}}{m}\cdot \|k\|_{2}\cdot \langle Sq,\text{sign}(Sk)\rangle\]

왜 부호 비트만으로 내적이 복원되는가

이게 제가 이 논문에서 가장 인상 깊었던 부분인데, 비편향성 증명이 생각보다 깔끔합니다. 네 단계입니다:

분해. 쿼리 \(q\)를 키 \(k\) 방향의 평행 성분과 수직 성분으로 나눕니다: \(q=\frac{\langle q,k\rangle }{\|k\|^{2}}k+q_{k}^{\perp }\)

전개. 각 행 \(s_{i}\)에 대해, \(x\cdot \text{sign}(x)=|x|\)라는 사실을 이용하면:

\[s_{i}^{\top }q\cdot \text{sign}(s_{i}^{\top }k)=\frac{\langle q,k\rangle }{\|k\|^{2}}\cdot |s_{i}^{\top }k|+s_{i}^{\top }q_{k}^{\perp }\cdot \text{sign}(s_{i}^{\top }k)\]

기댓값. 수직 성분은 그냥 사라집니다—\(k\)와 \(q_{k}^{\perp }\)가 직교라서, 가우시안 벡터 \(s_{i}\)를 각각에 프로젝션한 \(s_{i}^{\top }k\)와 \(s_{i}^{\top }q_{k}^{\perp }\)는 독립입니다 (가우시안에서 비상관 = 독립 [2]). 그러니까 곱의 기댓값이 0이 됩니다. 평행 성분 쪽을 보면, Step 2에서 \(s_{i}^{\top }k\cdot \text{sign}(s_{i}^{\top }k)=|s_{i}^{\top }k|\)가 됐죠. \(s_{i}\)가 가우시안이라 \(s_{i}^{\top }k\sim N(0,\|k\|^{2})\)이고, 이 정규 분포 절댓값의 기댓값이 \(\mathbb{E}[|x|]=\|k\|\cdot \sqrt{2/\pi }\)입니다 (half-normal 분포의 평균이라고 부르는 값).

상쇄. 추정기의 정의로 돌아가서 기댓값을 전개합니다. Step 3에서 수직 성분은 사라졌으므로, 평행 성분만 남습니다:

\[\mathbb{E} \Bigg[ \frac{\sqrt{\pi /2}}{m}\|k\|\sum_{i=1}^{m}(s_{i}^{\top }q)\cdot \text{sign}(s_{i}^{\top }k) \Bigg] =\frac{\sqrt{\pi /2}}{m}\|k\|\sum_{i=1}^{m}\frac{\langle q,k\rangle }{\|k\|^{2}}\cdot \mathbb{E}[|s_{i}^{\top }k|]\]

Step 3에서 구한 \(\mathbb{E}[|s_{i}^{\top }k|]=\|k\|\sqrt{2/\pi }\)를 대입하고, \(m\)개 항의 합을 \(m\)으로 나누면 하나의 항이 남습니다:

\[=\sqrt{\frac{\pi }{2}}\cdot \|k\|\cdot \frac{\langle q,k\rangle }{\|k\|^{2}}\cdot \|k\|\cdot \sqrt{\frac{2}{\pi }}=\sqrt{\frac{\pi }{2}}\cdot \sqrt{\frac{2}{\pi }}\cdot \langle q,k\rangle =1\cdot \langle q,k\rangle =\langle q,k\rangle\]

결국 보정 계수 \(\sqrt{\pi /2}\)는 half-normal에서 나온 \(\sqrt{2/\pi }\)를 정확히 지우도록 일부러 그렇게 잡은 거죠.

코드로 확인: QJL 추정기 동작

import numpy as np
d, m = 128, 4096  # m이 클수록 분산↓
q = np.random.randn(d); q /= np.linalg.norm(q)  # 단위 노름
k = np.random.randn(d); k /= np.linalg.norm(k)
S = np.random.randn(m, d)

# QJL 추정기: sign(Sk)만 저장, Sq는 full precision
sign_Sk = np.sign(S @ k)
estimate = np.sqrt(np.pi/2) / m * np.linalg.norm(k) * (S @ q) @ sign_Sk

print(f"실제 내적: {q @ k:.4f}")
print(f"QJL 추정: {estimate:.4f}")  # → 한 trial 결과 (분산은 ‖q‖‖k‖/√m에 비례)
# 비편향성을 직접 확인하려면 여러 S로 평균을 내야 함

import numpy as np
d, m = 128, 4096  # m이 클수록 분산↓
q = np.random.randn(d); q /= np.linalg.norm(q)  # 단위 노름
k = np.random.randn(d); k /= np.linalg.norm(k)
S = np.random.randn(m, d)

# QJL 추정기: sign(Sk)만 저장, Sq는 full precision
sign_Sk = np.sign(S @ k)
estimate = np.sqrt(np.pi/2) / m * np.linalg.norm(k) * (S @ q) @ sign_Sk

print(f"실제 내적: {q @ k:.4f}")
print(f"QJL 추정: {estimate:.4f}")  # → 한 trial 결과 (분산은 ‖q‖‖k‖/√m에 비례)
# 비편향성을 직접 확인하려면 여러 S로 평균을 내야 함

import numpy as np
d, m = 128, 4096  # m이 클수록 분산↓
q = np.random.randn(d); q /= np.linalg.norm(q)  # 단위 노름
k = np.random.randn(d); k /= np.linalg.norm(k)
S = np.random.randn(m, d)

# QJL 추정기: sign(Sk)만 저장, Sq는 full precision
sign_Sk = np.sign(S @ k)
estimate = np.sqrt(np.pi/2) / m * np.linalg.norm(k) * (S @ q) @ sign_Sk

print(f"실제 내적: {q @ k:.4f}")
print(f"QJL 추정: {estimate:.4f}")  # → 한 trial 결과 (분산은 ‖q‖‖k‖/√m에 비례)
# 비편향성을 직접 확인하려면 여러 S로 평균을 내야 함

그림 5. 부호 비트의 기하학적 직관. 랜덤 초평면들이 공간을 분할하고, k와 q가 같은 편에 놓이는 비율이 내적을 인코딩합니다.

기하학적으로 보면, 부호 비트는 “이 벡터가 랜덤 초평면의 어느 쪽에 있는가?”를 인코딩합니다. 두 벡터가 비슷한 방향이면 대부분의 초평면에 대해 같은 편에 놓이고, 직교에 가까우면 반반으로 갈립니다. 이 “같은 편 비율”이 내적을 결정합니다.

QJL의 저장 구조도 주목할 만합니다. 토큰당 \(m\)개 부호 비트 + 16비트(norm)만 저장하면 되고, 그룹별 scale/zero-point가 전혀 필요 없습니다. 섹션 1에서 봤던 scale/zero-point 오버헤드가 0인 셈입니다.

QJL은 좋은 아이디어지만, 한 가지 근본적인 한계가 있습니다: 원래 벡터를 복원할 수 없다는 점입니다. 부호 비트만으로는 내적은 추정할 수 있어도 벡터 자체를 되살릴 수가 없는데, 그러면 밸류(Value) 캐시에 쓸 수가 없습니다. 밸류 캐시는 내적이 아니라 벡터 자체를 가중합해야 하니까요. 이 한계를 어떻게 넘을까요?

PolarQuant: 좌표계를 바꾸는 접근

극좌표로 변환하면 무엇이 좋은가

PolarQuant [3]의 접근은 좌표계를 바꾸는 것입니다. KV 임베딩을 직교좌표 대신 극좌표(반지름 + 각도)로 변환하고, 각도를 양자화합니다. 위도가 항상 \([-90°,90°]\)인 것처럼, 극좌표의 각도는 범위가 미리 고정되어 있으므로 데이터 의존적 scale/zero-point가 필요 없습니다.

재귀적 극좌표 변환

128차원 벡터를 한 번에 극좌표로 변환하면 127개의 복잡하게 얽힌 각도가 생깁니다. PolarQuant는 이를 재귀적으로 해결합니다:

그림 6. PolarQuant의 재귀적 극좌표 변환 (4차원 예시). 좌표를 쌍으로 묶어 2D 극변환을 반복합니다.

1. 좌표를 쌍으로 묶어 2D 극좌표 변환: \((x_{2j-1},x_{2j})\mapsto (r_{j},\psi _{j})\)

2. 반지름 \(r_{1},r_{2},\ldots\)을 다시 쌍으로 묶어 반복

3. \(\log_{2}d\)번 반복하면 \(d-1\)개의 각도와 1개의 최종 반지름을 얻음

코드로 확인: 재귀적 극좌표 변환의 핵심

import numpy as np

def recursive_polar(x):
    """좌표를 쌍으로 묶어 (radius, angle)로 변환, 반지름을 재귀.
    x의 길이는 2의 거듭제곱이어야 함."""
    angles, radii = [], []
    for i in range(0, len(x), 2):
        r = np.sqrt(x[i]**2 + x[i+1]**2)
        psi = np.arctan2(x[i+1], x[i])
        radii.append(r); angles.append(psi)
    if len(radii) > 1:
        deeper_angles, final_r = recursive_polar(np.array(radii))
        return angles + deeper_angles, final_r
    return angles, radii[0]

# 8차원 벡터 → 7개 각도 + 1개 반지름
x = np.random.randn(8); x /= np.linalg.norm(x)
angles, r = recursive_polar(x)
print(f"{len(angles)}개 각도 + 반지름 {r:.4f}")  # → 7개 각도 + 1.0000

import numpy as np

def recursive_polar(x):
    """좌표를 쌍으로 묶어 (radius, angle)로 변환, 반지름을 재귀.
    x의 길이는 2의 거듭제곱이어야 함."""
    angles, radii = [], []
    for i in range(0, len(x), 2):
        r = np.sqrt(x[i]**2 + x[i+1]**2)
        psi = np.arctan2(x[i+1], x[i])
        radii.append(r); angles.append(psi)
    if len(radii) > 1:
        deeper_angles, final_r = recursive_polar(np.array(radii))
        return angles + deeper_angles, final_r
    return angles, radii[0]

# 8차원 벡터 → 7개 각도 + 1개 반지름
x = np.random.randn(8); x /= np.linalg.norm(x)
angles, r = recursive_polar(x)
print(f"{len(angles)}개 각도 + 반지름 {r:.4f}")  # → 7개 각도 + 1.0000

import numpy as np

def recursive_polar(x):
    """좌표를 쌍으로 묶어 (radius, angle)로 변환, 반지름을 재귀.
    x의 길이는 2의 거듭제곱이어야 함."""
    angles, radii = [], []
    for i in range(0, len(x), 2):
        r = np.sqrt(x[i]**2 + x[i+1]**2)
        psi = np.arctan2(x[i+1], x[i])
        radii.append(r); angles.append(psi)
    if len(radii) > 1:
        deeper_angles, final_r = recursive_polar(np.array(radii))
        return angles + deeper_angles, final_r
    return angles, radii[0]

# 8차원 벡터 → 7개 각도 + 1개 반지름
x = np.random.randn(8); x /= np.linalg.norm(x)
angles, r = recursive_polar(x)
print(f"{len(angles)}개 각도 + 반지름 {r:.4f}")  # → 7개 각도 + 1.0000

회전 후 각도 분포의 형태

핵심 수학적 통찰이 여기에 있습니다. 랜덤 회전 행렬 \(S\)를 곱한 후, 각 레벨 \(\ell\)의 각도 분포는 해석적으로 알려진 형태를 따릅니다:

\[f_{\Psi ^{(\ell )}}(\psi )\propto \sin^{2^{\ell -1}-1}(2\psi )\]

그림 7. 레벨별 각도 분포. 상위 레벨일수록 \(\pi /4\) 주변에 급격히 집중되어, 더 적은 비트로 양자화할 수 있습니다.

레벨이 올라갈수록 분포가 \(\pi /4\) 주변에 날카롭게 집중됩니다. 이는 경제적인 비트 할당을 가능하게 합니다: 첫 번째 레벨에 4비트(넓게 퍼진 분포를 촘촘히 양자화), 나머지 레벨에 2비트(집중된 분포니까 적은 비트로 충분).

PolarQuant가 QJL보다 나은 점

PolarQuant가 QJL보다 나은 점은 크게 두 가지입니다.

첫째, 원래 벡터를 복원할 수 있습니다. 양자화된 각도 \(\hat{\psi }\)와 반지름 \(r\)로부터 표준 극좌표 역변환을 적용하면 직교좌표를 되찾을 수 있습니다:

\[(r,\hat{\psi })\mapsto (r\cos \hat{\psi },r\sin \hat{\psi })\]

이 역변환을 재귀적으로 모든 레벨에 적용하면 전체 \(d\)차원 벡터가 복원됩니다 [3]. 이 덕분에 키뿐만 아니라 밸류 캐시에도 동일한 방법을 적용할 수 있습니다—QJL이 풀지 못한 문제입니다.

둘째, 레벨별로 다른 비트를 할당하는 가변 비트 할당이 가능하여, QJL의 균일한 1비트/차원보다 정보 이론적으로 효율적입니다.

PolarQuant는 벡터 복원 문제를 해결했지만, 정보 이론적 한계에 얼마나 가까이 갈 수 있는지는 열린 질문으로 남아 있었습니다. 2025년에 등장한 TurboQuant가 이 질문에 답합니다.

TurboQuant: 스칼라 양자화의 이론적 최적성

회전 후 좌표 분포는 예측 가능하다

TurboQuant [4]의 출발점은 간단한 관찰입니다:

TurboQuant의 핵심 관찰

단위 벡터 \(x\in S^{d-1}\)에 랜덤 직교 행렬 \(\Pi\)를 곱하면, \(\Pi x\)의 각 좌표는 알려진 Beta 분포를 따르며, 고차원에서 거의 독립적으로 다뤄질 수 있습니다 [4]. 분포가 알려져 있으므로 데이터 없이 최적 양자화기를 설계할 수 있습니다. (엄밀히는, 단위구 위의 좌표들은 노름 제약 \(\sum x_{j}^{2}=1\)을 공유하므로 정확히 독립일 수 없지만, 차원이 높을수록 이 의존성은 무시할 수 있을 만큼 작아집니다.)

구체적으로, 회전된 단위 벡터의 각 좌표 \(x_{j}\)는 다음 분포를 따릅니다:

\[x_{j}\sim f_{X}(t)=\frac{\Gamma (d/2)}{\sqrt{\pi }\Gamma ((d-1)/2)}(1-t^{2})^{(d-3)/2},t\in [-1,1]\]

고차원에서 이 Beta 분포는 가우시안 \(N(0,1/d)\)로 수렴합니다.

그림 8. 회전 후 좌표의 Beta 분포. \(d=128\) (Llama head dimension)에서 가우시안과 거의 겹칩니다. 분포가 미리 알려져 있으므로 데이터 없이 최적 코드북을 설계할 수 있습니다.

\(d=128\)에서는 Beta 분포와 가우시안 근사가 거의 겹칩니다. 그리고 더 중요한 점은, 고차원에서 서로 다른 좌표가 거의 독립적으로 행동한다는 것입니다. 이 덕분에 각 좌표를 개별적으로 스칼라 양자화해도 전체 벡터를 한꺼번에 양자화(벡터 양자화)한 것과 거의 같은 품질이 나옵니다.

코드로 확인: 회전 후 좌표가 Beta 분포를 따르는가?

import numpy as np
from scipy.stats import beta, kstest
d = 128
X = np.random.randn(10000, d)
X /= np.linalg.norm(X, axis=1, keepdims=True)  # 단위구 위로 정규화
coords = X[:, 0]  # 첫 번째 좌표만 추출

# 이론: (coord+1)/2 ~ Beta((d-1)/2, (d-1)/2)
a = (d - 1) / 2
_, p_value = kstest((coords + 1) / 2, beta(a, a).cdf)
print(f"KS test p-value: {p_value:.3f}")  # > 0.05면 Beta와 일치

# 분위수도 직접 비교
for q in [0.05, 0.5, 0.95]:
    emp = np.quantile(coords, q)
    theo = 2 * beta(a, a).ppf(q) - 1
    print(f"q={q}: 실측 {emp:+.4f}  Beta {theo:+.4f}")

import numpy as np
from scipy.stats import beta, kstest
d = 128
X = np.random.randn(10000, d)
X /= np.linalg.norm(X, axis=1, keepdims=True)  # 단위구 위로 정규화
coords = X[:, 0]  # 첫 번째 좌표만 추출

# 이론: (coord+1)/2 ~ Beta((d-1)/2, (d-1)/2)
a = (d - 1) / 2
_, p_value = kstest((coords + 1) / 2, beta(a, a).cdf)
print(f"KS test p-value: {p_value:.3f}")  # > 0.05면 Beta와 일치

# 분위수도 직접 비교
for q in [0.05, 0.5, 0.95]:
    emp = np.quantile(coords, q)
    theo = 2 * beta(a, a).ppf(q) - 1
    print(f"q={q}: 실측 {emp:+.4f}  Beta {theo:+.4f}")

import numpy as np
from scipy.stats import beta, kstest
d = 128
X = np.random.randn(10000, d)
X /= np.linalg.norm(X, axis=1, keepdims=True)  # 단위구 위로 정규화
coords = X[:, 0]  # 첫 번째 좌표만 추출

# 이론: (coord+1)/2 ~ Beta((d-1)/2, (d-1)/2)
a = (d - 1) / 2
_, p_value = kstest((coords + 1) / 2, beta(a, a).cdf)
print(f"KS test p-value: {p_value:.3f}")  # > 0.05면 Beta와 일치

# 분위수도 직접 비교
for q in [0.05, 0.5, 0.95]:
    emp = np.quantile(coords, q)
    theo = 2 * beta(a, a).ppf(q) - 1
    print(f"q={q}: 실측 {emp:+.4f}  Beta {theo:+.4f}")

최적 코드북을 데이터 없이 설계하기

분포 \(f_{X}(t)\)가 해석적으로 알려져 있으므로, 최적 스칼라 양자화기를 1차원 k-means 문제로 풀 수 있습니다:

\[C(f_{X},b):=\min_{-1\le c_{1}\le \cdots \le c_{2^{b}}\le 1}\sum_{i=1}^{2^{b}}\int |x-c_{i}|^{2}\cdot f_{X}(x)dx\]

이 문제는 Lloyd-Max 알고리즘으로 풀립니다. 1차원 k-means라고 보면 되고, 차원이 하나라 굉장히 빠르게 수렴합니다:

1. 경계 갱신: 현재 중심점 \(c_{1},\ldots ,c_{2^{b}}\)이 주어졌을 때, 인접한 두 중심점의 중간값 \((c_{i}+c_{i+1})/2\)을 각 영역의 경계로 설정합니다. (가장 가까운 중심점에 할당하는 것과 동일합니다.)

2. 중심점 갱신: 각 영역 안에서 분포 \(f_{X}\)에 대한 조건부 기댓값을 새 중심점으로 설정합니다: \(c_{i}\leftarrow \mathbb{E}[X|X\in \text{영역}_{i}]\). 이것이 해당 영역 내에서 MSE를 최소화하는 최적 대표값입니다.

3. 1-2를 수렴할 때까지 반복합니다.

여기서 핵심은 \(f_{X}\)가 해석적으로 알려져 있기 때문에 (앞서 본 Beta 분포), 적분을 수치적으로 정확히 계산할 수 있다는 것입니다. 데이터 샘플이 필요 없습니다. 한 번 수렴시키면 그 코드북은 모든 모델, 모든 레이어, 모든 토큰에 영원히 재사용됩니다.

코드로 확인: Lloyd-Max 알고리즘으로 2-bit 코드북 구하기

import numpy as np

def lloyd_max_gaussian(n_centroids, sigma=1.0, iters=100):
    """N(0, sigma²)에 대한 Lloyd-Max. 데이터 샘플로 근사."""
    samples = np.random.randn(100000) * sigma   # pdf 대신 큰 샘플로 근사
    centroids = np.linspace(-2*sigma, 2*sigma, n_centroids)  # 초기값
    for _ in range(iters):
        # Step 1: 각 샘플을 가장 가까운 중심점에 할당
        idx = np.argmin(np.abs(samples[:, None] - centroids), axis=1)
        # Step 2: 각 그룹의 평균으로 중심점 갱신
        for i in range(n_centroids):
            if np.any(idx == i):
                centroids[i] = samples[idx == i].mean()
    return np.sort(centroids)

# d=128에서 좌표 ~ N(0, 1/d), 2-bit (4 centroids)
d = 128
centroids = lloyd_max_gaussian(4, sigma=1/np.sqrt(d))
print(centroids * np.sqrt(d))  # ≈ [-1.51, -0.453, 0.453, 1.51]

import numpy as np

def lloyd_max_gaussian(n_centroids, sigma=1.0, iters=100):
    """N(0, sigma²)에 대한 Lloyd-Max. 데이터 샘플로 근사."""
    samples = np.random.randn(100000) * sigma   # pdf 대신 큰 샘플로 근사
    centroids = np.linspace(-2*sigma, 2*sigma, n_centroids)  # 초기값
    for _ in range(iters):
        # Step 1: 각 샘플을 가장 가까운 중심점에 할당
        idx = np.argmin(np.abs(samples[:, None] - centroids), axis=1)
        # Step 2: 각 그룹의 평균으로 중심점 갱신
        for i in range(n_centroids):
            if np.any(idx == i):
                centroids[i] = samples[idx == i].mean()
    return np.sort(centroids)

# d=128에서 좌표 ~ N(0, 1/d), 2-bit (4 centroids)
d = 128
centroids = lloyd_max_gaussian(4, sigma=1/np.sqrt(d))
print(centroids * np.sqrt(d))  # ≈ [-1.51, -0.453, 0.453, 1.51]

import numpy as np

def lloyd_max_gaussian(n_centroids, sigma=1.0, iters=100):
    """N(0, sigma²)에 대한 Lloyd-Max. 데이터 샘플로 근사."""
    samples = np.random.randn(100000) * sigma   # pdf 대신 큰 샘플로 근사
    centroids = np.linspace(-2*sigma, 2*sigma, n_centroids)  # 초기값
    for _ in range(iters):
        # Step 1: 각 샘플을 가장 가까운 중심점에 할당
        idx = np.argmin(np.abs(samples[:, None] - centroids), axis=1)
        # Step 2: 각 그룹의 평균으로 중심점 갱신
        for i in range(n_centroids):
            if np.any(idx == i):
                centroids[i] = samples[idx == i].mean()
    return np.sort(centroids)

# d=128에서 좌표 ~ N(0, 1/d), 2-bit (4 centroids)
d = 128
centroids = lloyd_max_gaussian(4, sigma=1/np.sqrt(d))
print(centroids * np.sqrt(d))  # ≈ [-1.51, -0.453, 0.453, 1.51]

위 테이블의 MSE 값(0.36, 0.117, …)이 비트 폭에 따라 어떤 속도로 줄어드는지가 중요한데, 이를 일반적으로 기술하는 것이 Panter-Dite 고해상도 공식입니다. 1951년에 Panter와 Dite가 유도한 이 공식은, 확률 분포 \(f_{X}\)가 알려져 있을 때 \(b\)비트 최적 스칼라 양자화기의 MSE 상한을 닫힌 형태로 줍니다:

\[C(f_{X},b)\le \frac{1}{12} \bigg( \int f_{X}(x)^{1/3}dx \bigg) ^{3}\cdot \frac{1}{4^{b}}\]

TurboQuant의 맥락에서 \(f_{X}\)는 회전 후 좌표의 Beta 분포이고, 적분을 계산하면 \(C(f_{X},b)\le \frac{\sqrt{3}\pi }{2d}\cdot \frac{1}{4^{b}}\)가 됩니다. 이 공식이 뒤에서 distortion bound를 유도할 때 핵심 역할을 합니다. \(b\)가 클 때(고해상도) 정확하고, \(b\)가 작을 때는 위 테이블의 실제 값이 이 근사보다 더 좋습니다.

MSE 최적 양자화기의 편향 문제

그런데 여기서 좀 까다로운 문제가 생깁니다. MSE를 최소화하는 양자화기로 내적을 추정하면, 매번 일정한 비율로 작게 나오는 현상이 발생합니다.

\(b=1\)일 때 왜 그런지 보겠습니다. 1비트 MSE 최적 코드북은 \(\{\pm c\}\)이고, \(c=\sqrt{2/(\pi d)}\)입니다. 양자화된 좌표는 \(\hat{x}_{j}=c\cdot \text{sign}(x_{j})\)이 됩니다.

내적의 기댓값을 구하려면, 섹션 3의 QJL 증명과 같은 분해를 적용합니다: \(y\)를 \(x\) 방향의 평행/수직 성분으로 나누면, 수직 성분은 기댓값이 0이 되어 사라지고, 평행 성분만 남습니다:

\[\mathbb{E}[\langle y,\hat{x}\rangle ]=c\cdot \frac{\langle y,x\rangle }{\|x\|_{2}^{2}}\cdot \mathbb{E} \Bigg[ \sum_{j}|x_{j}| \Bigg] =c\cdot \frac{\langle y,x\rangle }{\|x\|_{2}^{2}}\cdot \mathbb{E}[\|x\|_{1}]\]

(평행 성분에서 \(x_{j}\cdot \text{sign}(x_{j})=|x_{j}|\)가 되는 건 QJL 증명의 Step 2와 동일합니다.)

단위구 위의 벡터(\(\|x\|_{2}=1\))에서 각 좌표 \(x_{j}\sim N(0,1/d)\) 근사를 쓰면, \(\mathbb{E}[|x_{j}|]=\sqrt{2/(\pi d)}\)이고:

\[\mathbb{E}[\|x\|_{1}]=d\cdot \sqrt{\frac{2}{\pi d}}=\sqrt{\frac{2d}{\pi }}\]

이를 대입하면:

\[\mathbb{E}[\langle y,\hat{x}\rangle ]=\underbrace{\sqrt{\frac{2}{\pi d}}}_{c}\cdot \langle y,x\rangle \cdot \underbrace{\sqrt{\frac{2d}{\pi }}}_{\mathbb{E}[\|x\|_{1}]}=\sqrt{\frac{2}{\pi d}\cdot \frac{2d}{\pi }}\cdot \langle y,x\rangle =\sqrt{\frac{4}{\pi ^{2}}}\cdot \langle y,x\rangle =\frac{2}{\pi }\langle y,x\rangle\]

\(2/\pi \approx 0.637\), 즉 36% 과소추정입니다. \(c\)(코드북 값)와 \(\mathbb{E}[\|x\|_{1}]\)(L1 노름의 기댓값)의 곱에서 \(d\)가 약분되고 \(\sqrt{4/\pi ^{2}}=2/\pi\)만 남는 구조입니다.

여기서 자연스러운 질문: 그냥 \(\pi /2\)를 곱해서 보정하면 안 되나? \(b=1\)에서는 사실 됩니다 — \(2/\pi\)가 입력에 무관한 상수이니까, \(\pi /2\cdot (2/\pi )\cdot \langle y,x\rangle =\langle y,x\rangle\)로 bias가 사라집니다.

문제는 \(b\ge 2\)부터입니다. \(b=2\)의 코드북을 봅시다: \(\{-1.51/\sqrt{d},-0.453/\sqrt{d},+0.453/\sqrt{d},+1.51/\sqrt{d}\}\). 이제 각 좌표 \(x_{j}\)는 부호만이 아니라 크기에 따라 가까운/먼 중심점 중 하나로 할당됩니다. 예를 들어:

• \(x_{j}=0.03/\sqrt{d}\) → \(+0.453/\sqrt{d}\)로 양자화 (15배 부풀려짐)

• \(x_{j}=1.2/\sqrt{d}\) → \(+1.51/\sqrt{d}\)로 양자화 (26% 부풀려짐)

• \(x_{j}=0.9/\sqrt{d}\) → \(+0.453/\sqrt{d}\)로 양자화 (절반으로 줄어듦)

각 좌표의 양자화 오차가 \(x_{j}\)의 실제 값에 따라 방향도 크기도 다릅니다. 이 오차들이 내적 \(\sum y_{j}\hat{x}_{j}\)에 기여하는 방식은 \(y\)의 값에도 의존합니다. 결과적으로, \(b=2\)에서의 내적 bias는 특정 \((x,y)\) 쌍에 따라 달라지는 입력 의존적 양이 되어, 모든 입력에 통하는 단일 스칼라 보정 계수가 존재하지 않습니다 [4].

이것이 TurboQuant가 단순 스케일링 대신 QJL 잔차 보정을 택한 이유입니다: QJL은 잔차 \(r\)이 무엇이든 비편향이므로, \(b=1\)이든 \(b=4\)든, \((x,y)\)가 무엇이든 정확히 bias를 제거합니다. 게다가 QJL이 전체 벡터가 아닌 작은 잔차에만 적용되므로 분산도 작게 유지됩니다.

코드로 확인: b=1에서 2/π 편향

import numpy as np
d = 128; trials = 5000
c1 = np.sqrt(2 / (np.pi * d))  # b=1 코드북

# y = x로 두면 <y, x> = 1, <y, x_q> = c·||x||_1 → 정확히 2/π가 나옴
ratios = []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    x_q = c1 * np.sign(x)               # 1-bit MSE 양자화
    ratios.append(x @ x_q)               # <x, x_q> = c·||x||_1

print(f"<x, x_q> 평균: {np.mean(ratios):.4f}")  # ≈ 0.6366
print(f"이론값 2/π:    {2/np.pi:.4f}")         # 0.6366
# → b=1에서는 상수 편향이라 π/2로 보정 가능. 그런데 b≥2에서는
#   코드북이 복잡해져서 편향이 입력 의존적이 되고, 단일 스칼라 보정이 안 됨.

import numpy as np
d = 128; trials = 5000
c1 = np.sqrt(2 / (np.pi * d))  # b=1 코드북

# y = x로 두면 <y, x> = 1, <y, x_q> = c·||x||_1 → 정확히 2/π가 나옴
ratios = []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    x_q = c1 * np.sign(x)               # 1-bit MSE 양자화
    ratios.append(x @ x_q)               # <x, x_q> = c·||x||_1

print(f"<x, x_q> 평균: {np.mean(ratios):.4f}")  # ≈ 0.6366
print(f"이론값 2/π:    {2/np.pi:.4f}")         # 0.6366
# → b=1에서는 상수 편향이라 π/2로 보정 가능. 그런데 b≥2에서는
#   코드북이 복잡해져서 편향이 입력 의존적이 되고, 단일 스칼라 보정이 안 됨.

import numpy as np
d = 128; trials = 5000
c1 = np.sqrt(2 / (np.pi * d))  # b=1 코드북

# y = x로 두면 <y, x> = 1, <y, x_q> = c·||x||_1 → 정확히 2/π가 나옴
ratios = []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    x_q = c1 * np.sign(x)               # 1-bit MSE 양자화
    ratios.append(x @ x_q)               # <x, x_q> = c·||x||_1

print(f"<x, x_q> 평균: {np.mean(ratios):.4f}")  # ≈ 0.6366
print(f"이론값 2/π:    {2/np.pi:.4f}")         # 0.6366
# → b=1에서는 상수 편향이라 π/2로 보정 가능. 그런데 b≥2에서는
#   코드북이 복잡해져서 편향이 입력 의존적이 되고, 단일 스칼라 보정이 안 됨.

2단계 접근: MSE 근사 + QJL 보정

TurboQuant의 해법은 \(b\)-비트 예산을 두 단계로 쪼개는 것입니다: \((b-1)\)비트로 MSE 양자화(대략적인 근사), 나머지 1비트로 QJL 잔차 보정(정밀 교정).

그림 9. TurboQuant의 2단계 파이프라인. Stage 1(MSE)이 대략적 근사를 제공하고, Stage 2(QJL)가 잔차를 비편향적으로 보정합니다.

수식으로 표현하면:

Stage 1 — MSE 양자화 (\(b-1\) 비트):

\[\hat{x}_{\text{mse}}=\text{DeQuant}_{\text{mse}}(\text{Quant}_{\text{mse}}(x)),r=x-\hat{x}_{\text{mse}}\]

Stage 2 — QJL 잔차 보정 (1비트):

\[\hat{x}_{\text{qjl}}=\frac{\sqrt{\pi /2}}{d}\|r\|_{2}S^{\top }\cdot \text{sign}(S\cdot r)\]

최종 복원: \(\hat{x}=\hat{x}_{\text{mse}}+\hat{x}_{\text{qjl}}\)

코드로 확인: TurboQuant 2단계 파이프라인

import numpy as np
d = 128; trials = 2000
codebook = np.array([-1.51, -0.453, 0.453, 1.51]) / np.sqrt(d)  # 2-bit

mse_only, with_qjl, truth = [], [], []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    y = np.random.randn(d); y /= np.linalg.norm(y)
    Pi = np.linalg.qr(np.random.randn(d, d))[0]  # 랜덤 직교

    # Stage 1: 회전 후 2-bit MSE 양자화
    rot = Pi @ x
    idx = np.argmin(np.abs(rot[:, None] - codebook), axis=1)
    x_mse = Pi.T @ codebook[idx]

    # Stage 2: 잔차에 1-bit QJL
    r = x - x_mse
    S = np.random.randn(d, d)
    x_qjl = np.sqrt(np.pi/2) / d * np.linalg.norm(r) * S.T @ np.sign(S @ r)

    truth.append(y @ x)
    mse_only.append(y @ x_mse)
    with_qjl.append(y @ (x_mse + x_qjl))

# 회귀 기울기로 편향 측정 (1.0이면 비편향)
slope = lambda est: np.dot(est, truth) / np.dot(truth, truth)
print(f"MSE only 기울기:    {slope(mse_only):.4f}")   # < 1 (편향)
print(f"MSE + QJL 기울기:  {slope(with_qjl):.4f}")  # ≈ 1 (비편향!)

import numpy as np
d = 128; trials = 2000
codebook = np.array([-1.51, -0.453, 0.453, 1.51]) / np.sqrt(d)  # 2-bit

mse_only, with_qjl, truth = [], [], []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    y = np.random.randn(d); y /= np.linalg.norm(y)
    Pi = np.linalg.qr(np.random.randn(d, d))[0]  # 랜덤 직교

    # Stage 1: 회전 후 2-bit MSE 양자화
    rot = Pi @ x
    idx = np.argmin(np.abs(rot[:, None] - codebook), axis=1)
    x_mse = Pi.T @ codebook[idx]

    # Stage 2: 잔차에 1-bit QJL
    r = x - x_mse
    S = np.random.randn(d, d)
    x_qjl = np.sqrt(np.pi/2) / d * np.linalg.norm(r) * S.T @ np.sign(S @ r)

    truth.append(y @ x)
    mse_only.append(y @ x_mse)
    with_qjl.append(y @ (x_mse + x_qjl))

# 회귀 기울기로 편향 측정 (1.0이면 비편향)
slope = lambda est: np.dot(est, truth) / np.dot(truth, truth)
print(f"MSE only 기울기:    {slope(mse_only):.4f}")   # < 1 (편향)
print(f"MSE + QJL 기울기:  {slope(with_qjl):.4f}")  # ≈ 1 (비편향!)

import numpy as np
d = 128; trials = 2000
codebook = np.array([-1.51, -0.453, 0.453, 1.51]) / np.sqrt(d)  # 2-bit

mse_only, with_qjl, truth = [], [], []
for _ in range(trials):
    x = np.random.randn(d); x /= np.linalg.norm(x)
    y = np.random.randn(d); y /= np.linalg.norm(y)
    Pi = np.linalg.qr(np.random.randn(d, d))[0]  # 랜덤 직교

    # Stage 1: 회전 후 2-bit MSE 양자화
    rot = Pi @ x
    idx = np.argmin(np.abs(rot[:, None] - codebook), axis=1)
    x_mse = Pi.T @ codebook[idx]

    # Stage 2: 잔차에 1-bit QJL
    r = x - x_mse
    S = np.random.randn(d, d)
    x_qjl = np.sqrt(np.pi/2) / d * np.linalg.norm(r) * S.T @ np.sign(S @ r)

    truth.append(y @ x)
    mse_only.append(y @ x_mse)
    with_qjl.append(y @ (x_mse + x_qjl))

# 회귀 기울기로 편향 측정 (1.0이면 비편향)
slope = lambda est: np.dot(est, truth) / np.dot(truth, truth)
print(f"MSE only 기울기:    {slope(mse_only):.4f}")   # < 1 (편향)
print(f"MSE + QJL 기울기:  {slope(with_qjl):.4f}")  # ≈ 1 (비편향!)

주목할 점: 섹션 3에서 QJL은 내적만 추정할 수 있다고 했는데, 여기서는 \(\frac{\sqrt{\pi /2}}{d}\|r\|S^{\top }\cdot \text{sign}(S\cdot r)\)로 벡터 자체를 “복원”합니다. 이때 \(S^{\top }\)은 \(S\)의 역행렬이 아닙니다—\(S\)는 가우시안 랜덤 행렬이지 직교 행렬이 아니므로 \(S^{\top }S\not =I\)입니다. \(S^{\top }\)이 여기서 하는 역할은 선형대수적 역변환이 아니라, 무작위 투영의 부호 정보를 원래 공간으로 되돌리는 back-projection 추정기입니다. 이 추정기가 비편향인 이유는 앞서 섹션 3에서 본 것과 같은 가우시안 반접힌 분포의 성질 때문이며, \(m=d\)로 두면 \(d\)개의 독립 투표가 확보되어 분산이 충분히 줄어듭니다. 이 덕분에 TurboQuantprod는 밸류 캐시에도 적용 가능합니다.

PolarQuant의 복원과 어떻게 다른가?

두 방법 모두 “벡터 복원”이 가능하지만, 작동 원리는 완전히 다릅니다:

• PolarQuant: 극좌표 변환은 결정론적이고 정확히 가역적입니다. 양자화하지 않으면 \((x_{1},x_{2})\to (r,\psi )\to (r\cos \psi ,r\sin \psi )\)가 원본을 완벽히 복원합니다. 양자화 오차는 각도 격자 해상도에서만 발생합니다. 좌표 변환의 기하학적 가역성에 의존합니다.

• TurboQuant의 \(S^{\top }\) 단계: 결정론적으로 가역적이지 않습니다. \(S^{\top }\)을 적용해도 원본이 정확히 돌아오지 않고, \(\mathbb{E}[\hat{r}]=r\)이라는 의미에서 평균적으로만 맞습니다. 매번 노이즈가 있고, \(d\)개 행의 평균화로 분산을 줄이는 통계적 추정에 의존합니다.

비유하자면, PolarQuant는 “한국어 → 영어 → 한국어 번역”(1:1 대응)이고, TurboQuant의 QJL 단계는 “100명에게 평점을 물어 평균 내기”(개별은 부정확하지만 평균은 진실에 수렴)입니다. 둘 다 같은 결과(밸류 캐시 적용 가능)를 만들지만, TurboQuant는 PolarQuant의 복원 방식을 차용한 것이 아니라 완전히 다른 원리(통계적 평균화)로 같은 능력을 얻은 것입니다.

이 차이는 실전적으로도 중요한 trade-off를 만듭니다.

표가 보여주듯, 두 방법은 서로 다른 축에서 우위를 가집니다:

• TurboQuant의 강점 (속도와 이론): dequant 경로가 matmul + lookup으로 단순해서 GPU/NPU에서 압도적으로 빠릅니다. 특히 \(\langle q,\tilde{x}\rangle =\langle \Pi q,\tilde{y}\rangle\) 트릭으로 \(\Pi q\)를 쿼리당 한 번만 계산하면, 캐시된 각 토큰에 대해서는 \(O(d)\) 내적만 필요합니다. PolarQuant는 매 토큰마다 \(d\)개의 cos/sin을 재귀적으로 호출해야 합니다. 또한 Shannon 하한 대비 ~2.7배라는 깔끔한 이론적 보장이 있습니다.

• PolarQuant의 강점 (안정성): 결정론적 복원과 softmax 친화성. 작은 head_dim이나 까다로운 attention에서 더 robust할 수 있습니다.

대부분의 실전 시나리오(대규모 LLM 서빙, GPU 추론)에서는 속도와 하드웨어 친화성이 결정적이라 TurboQuant가 유리합니다. 그래서 Google이 주력으로 미는 것이고, 최근 커뮤니티 구현(llama.cpp, vLLM)도 TurboQuant 변형이 더 많습니다. 다만 섹션 7에서 다룰 것처럼, TurboQuant의 QJL 단계는 softmax 분산 증폭이라는 함정이 있어서 실전에서는 MSE 단계만 쓰는 경우가 많습니다. 이 경우 “TurboQuantmse”는 PolarQuant의 결정론적 안정성에 가까워지면서 속도 우위까지 유지합니다.

비편향성 증명

이 증명은 개인적으로 이 논문에서 가장 깔끔하다고 생각하는 부분입니다. QJL은 임의의 입력 벡터에 대해 비편향이므로, 잔차 \(r\)에 대해서도 비편향입니다. 전체 기대 법칙을 적용하면:

\[\mathbb{E}[\langle y,\hat{x}\rangle ]=\underbrace{\mathbb{E}[\langle y,\hat{x}_{\text{mse}}\rangle ]}_{\text{편향 있음}}+\underbrace{\langle y,x\rangle -\mathbb{E}[\langle y,\hat{x}_{\text{mse}}\rangle ]}_{\text{QJL이 잔차를 비편향 추정}}=\langle y,x\rangle\]

\(\mathbb{E}[\langle y,\hat{x}_{\text{mse}}\rangle ]\) 항이 \(+\)와 \(-\)에서 정확히 상쇄됩니다. MSE 단계가 어떤 편향을 가지든 상관없이, QJL이 잔차를 비편향 추정하면서 자동으로 보상해줍니다. 그리고 Stage 1이 잔차를 줄일수록 Stage 2의 분산도 줄어드는, 꽤 깔끔한 시너지 구조입니다.

분산 바운드와 1/4b 스케일링

비편향성은 확보했으니, 남은 질문은 오차가 얼마나 작은가입니다. 여기서 두 가지 오차 척도를 구분할 필요가 있습니다:

• \(D_{\text{mse}}\): MSE distortion = \(\mathbb{E}[\|x-\hat{x}\|_{2}^{2}]\). 원본 벡터와 복원 벡터 사이의 유클리드 거리 제곱의 기댓값입니다.

• \(D_{\text{prod}}\): 내적 distortion = \(\mathbb{E}[|\langle y,x\rangle -\langle y,\hat{x}\rangle |^{2}]\). 특정 쿼리 \(y\)에 대한 내적 추정 오차의 기댓값입니다. Attention score의 품질과 직접 관련됩니다.

TurboQuantmse는 \(D_{\text{mse}}\)를 최소화하고, TurboQuantprod는 \(D_{\text{prod}}\)를 최소화합니다. 아래에서는 \(D_{\text{prod}}\)의 상한을 유도합니다.

먼저 분산의 구조를 파악합시다. 복원된 벡터 \(\hat{x}=\hat{x}_{\text{mse}}+\hat{x}_{\text{qjl}}\)에서, \(\hat{x}_{\text{mse}}\)는 회전 행렬 \(\Pi\)가 고정되면 결정론적입니다—같은 입력에 대해 항상 같은 코드북 인덱스를 반환하니까요. 랜덤성은 오직 QJL 단계의 행렬 \(S\)에서 옵니다. 따라서 전체 법칙(law of total variance)을 적용하면:

\[\text{Var}(\langle y,\hat{x}\rangle )=\mathbb{E}_{\hat{x}_{\text{mse}}} \big[ \text{Var}(\langle y,\hat{x}_{\text{qjl}}\rangle |\hat{x}_{\text{mse}}) \big]\]

(\(\hat{x}_{\text{mse}}\)가 주어지면 \(\langle y,\hat{x}_{\text{mse}}\rangle\)는 상수이므로, \(\text{Var}(\langle y,\hat{x}_{\text{mse}}\rangle |\hat{x}_{\text{mse}})=0\)이기 때문입니다.)

이제 조건부 분산을 바운딩합니다. \(\hat{x}_{\text{mse}}\)가 주어지면, 잔차 \(r=x-\hat{x}_{\text{mse}}\)는 고정된 벡터이고, QJL은 이 \(r\)에 적용됩니다. QJL의 역양자화 벡터를 다시 보면:

\[\hat{x}_{\text{qjl}}=\frac{\sqrt{\pi /2}}{d}\|r\|_{2}S^{\top }\cdot \text{sign}(S\cdot r)\]

여기서 내적 \(\langle y,\hat{x}_{\text{qjl}}\rangle\)의 분산을 구해야 합니다. \(S\)의 각 행 \(s_{i}\)에 대해, 추정기의 \(i\)번째 “투표”는 \(\sqrt{\pi /2}\|r\|_{2}(s_{i}^{\top }y)\text{sign}(s_{i}^{\top }r)\)입니다. 이것의 분산을 바운딩하려면 2차 모멘트를 구하면 됩니다 (Var \(\le\) E[X²]).

\(\text{sign}(s_{i}^{\top }r)\in \{-1,+1\}\)이므로, 제곱하면 항상 1입니다:

\[\big[ (s_{i}^{\top }y)\text{sign}(s_{i}^{\top }r) \big] ^{2}=(s_{i}^{\top }y)^{2}\cdot \underbrace{\text{sign}(s_{i}^{\top }r)^{2}}_{=1}=(s_{i}^{\top }y)^{2}\]

따라서 sign 함수가 깔끔하게 사라지고, 2차 모멘트는 \((s_{i}^{\top }y)^{2}\)의 기댓값만 남습니다. \(s_{i}\)가 가우시안이므로 \(s_{i}^{\top }y\sim N(0,\|y\|^{2})\)이고:

\[\mathbb{E}[(s_{i}^{\top }y)^{2}]=\|y\|_{2}^{2}\]

보정 계수 \(\sqrt{\pi /2}\)와 \(\|r\|\)까지 포함하면:

\[\text{Var} \big( \sqrt{\pi /2}\|r\|_{2}(s_{i}^{\top }y)\text{sign}(s_{i}^{\top }r) \big) \le \frac{\pi }{2}\|r\|_{2}^{2}\|y\|_{2}^{2}\]

\(d\)개 행의 평균을 취하면 (독립이므로 분산이 \(1/d\)로 줄어듦):

\[\text{Var}(\langle y,\hat{x}_{\text{qjl}}\rangle |\hat{x}_{\text{mse}})\le \frac{1}{d}\cdot \frac{\pi }{2}\|y\|_{2}^{2}\|r\|_{2}^{2}=\frac{\pi }{2d}\|y\|_{2}^{2}\cdot \|r\|_{2}^{2}\]

이게 \(\pi /(2d)\)의 출처입니다: \(\pi /2\)는 QJL 보정 계수의 제곱(\((\sqrt{\pi /2})^{2}\))에서, \(1/d\)는 \(d\)개 독립 투표의 평균에서 옵니다. Stage 1이 \(r\)을 작게 만들수록 이 분산이 줄어드는 구조입니다.

\(\hat{x}_{\text{mse}}\)에 대한 기댓값을 취하면:

\[D_{\text{prod}}(b)\le \frac{\pi }{2d}\|y\|_{2}^{2}\cdot \underbrace{\mathbb{E}[\|r\|_{2}^{2}]}_{\text{Stage 1의 총 MSE}}\]

이제 \(\mathbb{E}[\|r\|_{2}^{2}]\)를 계산합니다. 이것은 \((b-1)\)비트 MSE 양자화의 총 복원 오차, 즉 \(d\)개 좌표 각각의 양자화 오차를 합한 것입니다:

\[\mathbb{E}[\|r\|_{2}^{2}]=\sum_{j=1}^{d}\mathbb{E}[(x_{j}-\hat{x}_{j})^{2}]=d\cdot C(f_{X},b-1)\]

여기서 \(C(f_{X},b-1)\)은 좌표 하나의 per-coordinate MSE입니다. Panter-Dite 고해상도 공식 [4]에 의해:

\[C(f_{X},b-1)\le \frac{\sqrt{3}\pi }{2d}\cdot \frac{1}{4^{b-1}}\]

모든 것을 조합하면:

\[D_{\text{prod}}(b)\le \frac{\pi }{2d}\|y\|_{2}^{2}\cdot d\cdot \frac{\sqrt{3}\pi }{2d}\cdot \frac{1}{4^{b-1}}\]

정리하면 (\(d\)가 약분되고, \(1/4^{b-1}=4/4^{b}\)):

\[=\frac{\pi }{2d}\cdot d\cdot \frac{\sqrt{3}\pi }{2d}\cdot \frac{4}{4^{b}}\cdot \|y\|_{2}^{2}=\frac{4\sqrt{3}\pi ^{2}}{4d}\cdot \frac{\|y\|_{2}^{2}}{4^{b}}=\frac{\sqrt{3}\pi ^{2}}{d}\|y\|_{2}^{2}\cdot \frac{1}{4^{b}}\]

핵심 메커니즘: Stage 1이 \(b-1\)비트로 달성한 MSE가 \(1/4^{b-1}\)이고, Stage 2의 QJL이 여기에 \(\pi /(2d)\cdot d=\pi /2\) 팩터를 곱하면서 분모에 추가 \(4\)가 들어가, 최종적으로 \(1/4^{b}\)가 됩니다. 비트 하나를 추가할 때마다 오류가 1/4로 줄어듭니다.

정보 이론적 하한과의 비교

위에서 상한을 구했으니, 이제 “어떤 방법으로든 이보다 더 잘할 수 없다”는 하한을 살펴봅시다.

하한의 논증 구조는 두 단계입니다 [4]:

Step 1 — Yao의 minimax 원리. 우리가 구하고 싶은 것은 “최악의 입력에 대한 최적의 (랜덤) 양자화 알고리즘의 오차”입니다. 수식으로 쓰면:

\[\min_{\text{랜덤 알고리즘 }Q}\max_{\text{입력 }x}\mathbb{E}[\text{오차}(Q,x)]\]

이걸 직접 풀기는 어렵습니다 — “최악의 입력”과 “최적의 랜덤 알고리즘”을 동시에 다뤄야 하니까요. Yao의 minimax 원리가 이것을 뒤집어줍니다:

\[\min_{\text{랜덤 }Q}\max_{x}\mathbb{E}[\text{오차}]=\max_{\text{입력 분포 }P}\min_{\text{결정론적 }Q}\mathbb{E}_{x\sim P}[\text{오차}]\]

왼쪽(원래 문제)은 랜덤 알고리즘의 worst-case이고, 오른쪽(변환된 문제)은 결정론적 알고리즘의 average-case입니다. 변환 후가 훨씬 다루기 쉬운데, “최악의 분포” \(P\)로 단위 초구 \(S^{d-1}\) 위의 균일 분포를 택하면 Shannon의 rate-distortion theory를 바로 적용할 수 있기 때문입니다.

Step 2 — Shannon의 손실 부호화 정리. 이제 입력이 \(S^{d-1}\) 위의 균일 분포에서 오는 상황입니다. Shannon의 rate-distortion theory에 의해, \(d\)차원 벡터를 총 \(B=b\cdot d\)비트로 인코딩할 때 달성 가능한 MSE의 하한은:

\[D_{\text{mse}}\ge 2^{-2B/d}=2^{-2b}=\frac{1}{4^{b}}\]

\(D_{\text{prod}}\)의 하한은 여기서 Pigeonhole principle로 한 단계 더 갑니다. 총 MSE를 좌표별로 분해하면:

\[D_{\text{mse}}=\sum_{j=1}^{d}\mathbb{E}[|x_{j}-\hat{x}_{j}|^{2}]\ge \frac{1}{4^{b}}\]

\(d\)개 항의 합이 \(1/4^{b}\) 이상이므로, 적어도 하나의 좌표 \(j^{*}\)에서:

\[\mathbb{E}[|x_{j^{*}}-\hat{x}_{j^{*}}|^{2}]\ge \frac{1}{d\cdot 4^{b}}\]

\(y=e_{j^{*}}\)(표준 기저 벡터, \(\|e_{j^{*}}\|=1\))를 선택하면, \(\langle e_{j^{*}},x-\hat{x}\rangle =x_{j^{*}}-\hat{x}_{j^{*}}\)이므로:

\[D_{\text{prod}}=\mathbb{E}[|\langle e_{j^{*}},x-\hat{x}\rangle |^{2}]\ge \frac{1}{d\cdot 4^{b}}\]

이것은 \(\|y\|=1\)인 특수한 경우이고, 일반적인 \(y\)에 대해서는 \(D_{\text{prod}}\)가 \(\|y\|^{2}\)에 비례하므로:

\[D_{\text{prod}}(Q)\ge \frac{\|y\|^{2}}{d}\cdot \frac{1}{4^{b}}\]

정리하면, 두 하한은:

\[D_{\text{mse}}(Q)\ge \frac{1}{4^{b}},D_{\text{prod}}(Q)\ge \frac{\|y\|^{2}}{d}\cdot \frac{1}{4^{b}}\]

상한 vs 하한 비교:

MSE distortion의 경우, TurboQuant 상한은 \(\frac{\sqrt{3}\pi }{2}\cdot \frac{1}{4^{b}}\)이고 하한은 \(\frac{1}{4^{b}}\)이므로, 그 비율은 \(\sqrt{3}\pi /2\approx 2.72\)—즉 정보 이론적 최적의 약 2.7배 이내입니다. \(b=1\)에서는 이 격차가 약 1.45배로 더 좁아집니다.

내적 distortion의 경우, 점근적 상한과 하한의 비율은 \(\sqrt{3}\pi ^{2}\approx 17.1\)로 MSE보다 크지만, 이것은 Panter-Dite 고해상도 근사에 기반한 값이며, 실제 낮은 비트 폭에서는 격차가 훨씬 작습니다.

그림 10. MSE Distortion rate 비교. TurboQuant는 Shannon 하한의 약 2.7배 이내에서 \(1/4^{b}\)로 스케일링됩니다.

다만, “정규화 → 랜덤 회전 → 좌표 양자화 → 비편향 추정”이라는 구조 자체는 TurboQuant가 처음이 아닙니다. 여기에 대해서는 짚고 넘어가야 할 부분이 있습니다.

RaBitQ와의 관계, 그리고 논쟁

RaBitQ(Gao & Long, SIGMOD 2024) [5]는 TurboQuant와 유사한 구조—정규화 → 랜덤 직교 회전 → 좌표 양자화 → 비편향 추정기—를 공유합니다. 그러나 RaBitQ는 항상 좌표당 1비트로 양자화하며(초큐브 \(\{-1/\sqrt{D},+1/\sqrt{D}\}^{D}\)의 정점), 다중 비트를 위해서는 제로 패딩으로 차원을 확대해야 합니다. TurboQuant는 임의의 \(b\) 비트에 대해 Beta 분포에 최적화된 Lloyd-Max 코드북을 사용합니다. 둘 다 \(b=1\)에서 부호 비트를 취한다는 점은 공통이지만, 코드북 값이 다르고 (TurboQuant: \(\pm \sqrt{2/\pi d}\), RaBitQ: \(\pm 1/\sqrt{D}\)), 내적 추정 방식도 다릅니다 (TurboQuant는 QJL 기반, RaBitQ는 \(\langle \bar{o},q\rangle /\langle \bar{o},o\rangle\) 비율 추정). Shannon 하한 대비 최적성 증명과 임의의 비트 폭 지원이 TurboQuant의 독자적 기여입니다.

다만, 두 방법의 관계에 대해서는 논쟁이 진행 중입니다. RaBitQ 저자들은 TurboQuant가 RaBitQ와의 구조적 유사성(특히 JL 변환/랜덤 회전)을 충분히 기술하지 않았고, 이론적 비교가 부정확하며, 실험 조건 공개가 불충분하다는 우려를 공개적으로 제기했습니다 [26]. 이 논의는 ICLR 2026 리뷰 과정에서도 다뤄졌으며, 커뮤니티 차원의 공개 기록으로 남아 있습니다.

실전 구현에서 드러난 문제들

2025년 후반부터 llama.cpp, vLLM, 독립 연구자들이 TurboQuant 계열을 구현하기 시작했고, 그 과정에서 논문이 예측하지 못한 몇 가지 문제가 드러났습니다.

QJL 잔차 보정의 실전적 한계

저도 처음 논문을 읽었을 때는 QJL 잔차 보정이 제일 깔끔한 부분이라고 생각했는데, 실전 결과는 정반대였습니다.

다수의 독립적 구현팀 [9][10]이 동일한 결론에 도달했습니다: QJL 잔차 보정을 적용하면 오히려 품질이 떨어지는 경우가 많다. llama.cpp 커뮤니티 토론 [14]에서는 head_dim=64인 GPT-2에서 QJL 적용 시 perplexity가 300% 증가했다는 보고가 있었고, scos-lab [16]의 재현 실험에서도 MSE 전용(+1.1% PPL)이 MSE+QJL(+6.5% PPL)을 크게 앞섰습니다.

다만, 이 결론이 보편적인 것은 아닙니다. 0xSero/turboquant [11]은 QJL을 파이프라인의 핵심 단계로 포함하면서 3-bit 키에서 cosine similarity 1.000000을 보고했고, hackimov/turboquant-kv [32]도 QJL을 기본으로 사용합니다. sharpner/turboquant-mlx [33]는 QJL을 선택적 옵션으로 제공하며, 3-bit에서 품질을 소폭 개선(+6.6% → +5.3%)하지만 ~30% 속도 저하가 수반된다고 보고합니다.

원인은 softmax를 통한 분산 증폭입니다. QJL 추정기는 내적에 대해 비편향(unbiased)이지만, 분산(variance)은 0이 아닙니다. Attention score는 내적을 softmax에 통과시키는데, softmax는 비선형 함수이므로:

\[\mathbb{E}[\text{softmax}(\hat{s}_{1},\ldots ,\hat{s}_{n})]\not =\text{softmax}(\mathbb{E}[\hat{s}_{1}],\ldots ,\mathbb{E}[\hat{s}_{n}])\]

즉, 내적이 비편향이어도 softmax 출력은 비편향이 아닙니다. QJL 단계가 추가하는 분산이 softmax를 통과하면서 증폭됩니다. 이 때문에 실전에서는 TurboQuantmse—MSE 단계만 사용하고 QJL 잔차 보정을 생략한 버전—이 더 좋은 성능을 보이는 경우가 많습니다. 정리하면: TurboQuant 논문의 Theorem 2 [4]는 내적 추정에 대해 비편향성을 증명한 것이지, softmax-weighted attention output에 대해 증명한 것이 아닙니다. 낮은 분산의 편향된 추정기(MSE 전용)가 높은 분산의 비편향 추정기(MSE+QJL)보다 softmax 이후에 더 안정적일 수 있다는 것이 다수 독립 구현의 결론입니다 [9][10][14].

그 외 실전적 제약 사항

• 작은 head dimension에서 이론 보장 약화: TurboQuant의 이론은 고차원 집중(concentration of measure)에 의존하므로 [4], \(d\)가 클수록 근사가 잘 맞습니다. \(d=128\) 이상에서는 Beta 분포의 가우시안 수렴이 충분하지만, \(d=64\)(일부 모델에서 사용)에서는 코드북 최적성 보장이 약해지고, llama.cpp 커뮤니티 [14]에서 실제로 품질 저하 사례가 보고되었습니다.

• K/V 비대칭: 다수의 구현 [10][16]에서 확인된 사실—밸류 캐시는 2비트까지 공격적으로 압축해도 품질 저하가 거의 없지만, 키 캐시는 훨씬 민감합니다. K/V 노름 비율이 1274배에 달하는 모델도 보고되었습니다 [16]. 실전에서는 K에 4비트, V에 2비트를 할당하는 비대칭 전략이 효과적입니다 [10].

• 경계 레이어 민감도: 첫 2개와 마지막 2개 레이어를 높은 정밀도로 유지하면, 품질 손실의 37-91%를 회복할 수 있습니다 [10]. 이는 TurboQuant 이론이 “모든 레이어에 균일하게 적용”을 가정하는 것과 다른 실전 전략입니다.

• Fused 커널 부재: 역양자화와 Attention 연산이 별도 커널로 실행되면 중간 결과를 HBM에 쓰고 다시 읽어야 하므로, 대역폭 이점이 상쇄됩니다. vLLM의 초기 draft PR [15]에서는 fused 커널 없이 특정 모델(Qwen2.5-7B, H100)에서 디코드 처리량이 baseline의 0.36배까지 하락한 사례가 보고되었습니다. 구현이 성숙되면 개선될 수 있지만, FlashAttention과의 통합이 실용화의 핵심 과제임을 보여줍니다.

오픈소스 구현 현황

공식 Google 코드는 아직 공개되지 않았지만 (2026년 4월 기준) [8], 커뮤니티 구현이 활발합니다:

다수 구현체의 실전 합의: QJL 잔차 보정은 softmax 분산 증폭으로 인해 주의가 필요합니다. 대부분의 경우 MSE 양자화만으로 충분하며 [9][10][14][16], K/V 비대칭 비트 할당 + 경계 레이어 보호가 효과적입니다. 다만 일부 구현 [11]에서는 QJL이 긍정적 결과를 보이기도 하여, 모델과 하드웨어에 따른 검증이 권장됩니다.

NPU에서 TurboQuant를 돌리려면

TurboQuant의 핵심 연산은 세 가지입니다: (1) Hadamard 변환 (에너지 분산), (2) 코드북 lookup (양자화/역양자화), (3) 저비트 정수 패킹/언패킹. 이 세 가지가 현재 NPU 하드웨어에 얼마나 잘 매핑되는지가 실용화의 관건입니다.

Hadamard 변환은 의외로 대부분의 NPU에서 네이티브 지원이 없습니다. NVIDIA Tensor Core에서는 HadaCore 기법으로 16x16 mma 명령어에 매핑할 수 있지만, 이는 Hadamard 구조를 활용하는 소프트웨어 최적화이지 하드웨어 네이티브 지원은 아닙니다. 다만 d=128 기준 WHT는 7 스테이지 × 64 butterfly = 약 900개의 덧셈/뺄셈으로 끝나기 때문에, 네이티브 지원이 없더라도 벡터 유닛에서 충분히 빠르게 처리됩니다. TurboQuant가 실제로 병목이 되는 지점은 Hadamard가 아니라 메모리 대역폭입니다. 그래도 향후 NPU 설계에서 butterfly 연산을 데이터패스에 통합한다면, 전처리 오버헤드를 더 줄이는 것이 가능할 것입니다.

코드북 lookup은 NPU의 약점입니다. NPU는 dense GEMM에 최적화되어 있어서, element-wise dequantization은 오히려 CPU보다 느릴 수 있습니다. T-MAN [31]에 따르면 Qualcomm NPU에서 element-wise float 연산이 CPU 대비 3.8배 느렸고, 이를 2단계 LUT로 퓨전하여 10.2배 속도 향상을 달성했습니다. TurboQuant의 코드북은 2-16개 항목으로 매우 작아서, 하드웨어 LUT에 잘 맞습니다. Qualcomm Hexagon의 VLUT16 명령어가 여기에 활용될 수 있습니다.

저비트 지원은 하드웨어마다 격차가 큽니다:

* Apple ANE는 가중치 palettization(1-8비트 LUT 저장 압축)을 Core ML로 지원하지만, 이는 가중치 전용 저장 압축이지 활성화/KV cache 양자화에 직접 적용되지 않습니다. 또한 dequant 후 FP16으로 연산되므로 compute는 저비트가 아닙니다.

테이블에서 보듯, TurboQuant의 주력 비트 폭인 3비트 정수를 네이티브로 지원하는 NPU는 아직 없습니다. NVIDIA Blackwell은 흥미로운 사례인데, Hopper에 있던 INT4 텐서코어를 빼고 NVFP4(부동소수)로 대체했습니다 — 이는 floating-point 4비트가 outlier 처리에 유리하기 때문이지만, TurboQuant 같은 코드북 양자화에는 여전히 정수 인덱스가 더 자연스럽습니다. Hadamard 네이티브 지원, 3비트 정수 연산, 소형 코드북 LUT을 데이터패스에 통합하는 것이 향후 NPU 설계의 과제입니다.

실전의 교훈을 종합하면, 이론의 핵심—랜덤 회전으로 분포를 예측 가능하게 만드는 것—은 여전히 유효합니다. QJL의 비편향성은 내적 수준에서는 정확하지만, softmax attention이라는 비선형 맥락에서는 분산 관리가 더 중요할 수 있습니다. 회전 후 최적 코드북을 적용하는 MSE 단계가 실전적 가치의 핵심이며, QJL의 실용성은 구현 맥락에 따라 다릅니다. 하드웨어 측면에서는, Hadamard + 저비트 코드북이라는 TurboQuant의 연산 프로파일에 맞는 NPU 설계가 점차 등장하고 있습니다.

마무리: 랜덤 회전이라는 핵심 도구

JL 이론(1984/2021) → QJL(2024) → PolarQuant(2025) → TurboQuant(2025)를 관통하는 공통 원리는 하나입니다:

40년을 관통하는 원리

랜덤 직교 행렬을 곱하면, 임의의 worst-case 벡터가 알려진 분포를 가진 랜덤 변수로 변환됩니다.

그림 11. 네 편의 논문을 관통하는 구조. “랜덤 회전 한 번”이 모든 것의 출발점입니다.

QJL은 부호 비트만으로 내적을 추정하고, PolarQuant는 극좌표 각도의 분포를 예측 가능하게 만들며, TurboQuant는 좌표의 Beta 분포로 최적 스칼라 코드북을 설계합니다. 세 경우 모두 회전이 데이터 의존성을 제거합니다.

물론, 이론과 실전 사이에는 간극이 있습니다. QJL의 비편향성은 softmax를 거치면 분산 증폭으로 오히려 해로울 수 있고, head dimension이 작거나 경계 레이어에서는 이론적 보장이 약해집니다. RaBitQ와의 구조적 유사성에 대한 학술적 논쟁도 진행 중입니다. 그럼에도, 랜덤 회전으로 분포를 예측 가능하게 만들고 그 분포에 맞는 양자화기를 설계한다는 핵심 아이디어는 실전에서 살아남았습니다—커뮤니티가 채택한 MSE 전용 양자화(TurboQuantmse)가 바로 이 원리의 산물입니다.

1984년의 순수 수학에서 시작된 아이디어가, 40년의 진화를 거쳐, LLM 추론의 핵심 병목에 이론적 해법을 제시했습니다. 이론이 실전과 만나면서 다듬어지는 과정은 아직 진행 중입니다.

참고 문헌

1. Freksen, C.B. (2021). An Introduction to Johnson-Lindenstrauss Transforms. arXiv:2103.00564

2. Zandieh, A., Daliri, M., Han, I. (2024). QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead. AAAI 2025. arXiv:2406.03482

3. Han, I., Kacham, P., Karbasi, A., Mirrokni, V., Zandieh, A. (2025). PolarQuant: Quantizing KV Caches with Polar Transformation. AISTATS 2026. arXiv:2502.02617

4. Zandieh, A., Daliri, M., Hadian, M., Mirrokni, V. (2025). TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate. ICLR 2026. arXiv:2504.19874

5. Gao, J., Long, C. (2024). RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. SIGMOD 2024. arXiv:2405.12497

6. Xiao, G., et al. (2023). SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models. ICML 2023.

7. Liu, Z., et al. (2024). SpinQuant: LLM Quantization with Learned Rotations. ICLR 2025. arXiv:2405.16406

8. Google Research Blog (2026). TurboQuant: Redefining AI Efficiency with Extreme Compression.

9. tonbistudio (2026). turboquant-pytorch: PyTorch TurboQuant implementation. QJL 잔차 보정 제거 후 MSE 전용 전환.

10. TheTom (2026). turboquant_plus: llama.cpp TurboQuant 통합. turbo2/3/4 포맷, Apple/NVIDIA/AMD 검증.

11. 0xSero (2026). turboquant (vLLM): vLLM TurboQuant 통합. Triton 커널, RTX 5090 벤치마크.

12. Gerganov, G. (2026). llama.cpp PR #21038: rotate activations for better quantization: Hadamard 회전으로 KV Cache 양자화 품질 개선.

13. elusznik (2026). llama.cpp PR #21089: TBQ3_0/TBQ4_0 KV cache quantization: CPU 전용 TurboQuant 포맷.

14. llama.cpp community (2026). Discussion #20969: TurboQuant extreme KV cache quantization.

15. vLLM community (2026). vLLM PR #38280: TurboQuant KV cache compression: Draft stage, fused 커널 없이 디코드 0.36배 하락 보고.

16. scos-lab (2026). turboquant (research reproduction): MSE 기반이 product-space 대비 우수, K/V 노름 비율 1274배 보고.

17. Ailon, N., Chazelle, B. (2009). The Fast Johnson-Lindenstrauss Transform and Approximate Nearest Neighbors. SIAM J. Comput. 39(1), 302–322.

18. Chee, J., et al. (2024). QuIP: 2-Bit Quantization of Large Language Models With Guarantees. NeurIPS 2023. arXiv:2307.13304

19. Tseng, A., et al. (2024). QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks. ICML 2024. arXiv:2402.04396

20. Johnson, W.B., Lindenstrauss, J. (1984). Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 189–206.

21. Dasgupta, S., Gupta, A. (2003). An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms, 22(1), 60–65.

22. Achlioptas, D. (2003). Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci., 66(4), 671–687.

23. Liu, Z., et al. (2024). KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache. ICML 2024. arXiv:2402.02750

24. Hooper, C., et al. (2024). KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization. NeurIPS 2024. arXiv:2401.18079

25. Vaswani, A., et al. (2017). Attention Is All You Need. NeurIPS 2017. arXiv:1706.03762

26. Long, C. (2026). Concerns from the RaBitQ Authors Regarding Method Description, Theoretical Comparison, and Experimental Disclosure. OpenReview public comment on TurboQuant, March 27, 2026.

27. NVIDIA (2025). NVIDIA Blackwell Architecture. NVFP4/FP8/INT8 지원, Transformer Engine.

28. Google (2025). Introducing Trillium, our 6th-generation TPU. TPU v6e (Trillium) / Ironwood 사양.

29. Qualcomm (2024). Qualcomm AI Engine Direct (QNN) SDK Documentation. Hexagon NPU, INT4/INT8 지원.

30. Apple (2024). Core ML Tools: Post-Training Palettization. ANE weight palettization (1–8 bit LUT).

31. Park, G., et al. (2025). T-MAN: Enabling End-to-End Low-Bit LLM Inference on NPUs via Unified Table Lookup. arXiv:2511.11248.

32. hackimov (2026). turboquant-kv: PyTorch TurboQuant KV cache 구현. QJL을 기본 포함.

33. sharpner (2026). turboquant-mlx: Apple MLX TurboQuant 구현. QJL 선택적 옵션.