https://arxiv.org/abs/2504.19874
TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
Vector quantization, a problem rooted in Shannon's source coding theory, aims to quantize high-dimensional Euclidean vectors while minimizing distortion in their geometric structure. We propose TurboQuant to address both mean-squared error (MSE) and inner
arxiv.org
양자화는 잘 아는 분야가 아니라 조금 어렵겠지만.... 요즘 화두가 된 논문이니 한번 읽어보려고 합니다.
사전 지식
| 1. 벡터 양자화, Vector Quantization | 실수 벡터 를 낮은 bit의 정수/bit string으로 바꾸고, 다시 근사 벡터 x~로 복원하는 압축 기법 | TurboQuant의 본질은 LLM 전용 기법이 아니라 고차원 벡터를 압축하는 일반적 VQ 알고리즘임 |
| 2. Bit-width | (b)-bit quantization은 좌표 하나당 평균 b bit를 쓴다는 뜻. 예: 16-bit → 4-bit → 2-bit로 갈수록 압축률은 커지지만 정보 손실도 커짐 | 논문은 모든 bit-width b에서 distortion이 얼마나 줄어드는지 이론적으로 분석함 |
| 3. Quantization / Dequantization | Quantization은 Q(x), dequantization은 Q^{-1}(Q(x))=. 즉, 원본 벡터를 저장하지 않고 압축 표현만 저장한 뒤 근사 복원 | Algorithm 1과 Algorithm 2가 각각 Quant와 DeQuant 절차로 구성됨 |
| 4. MSE distortion | 원본 벡터와 복원 벡터의 거리 손실. E[∥x−x~∥^2_2] | TurboQuantmse는 이 값을 최소화하는 방향으로 설계됨 |
| 5. Inner product distortion | 와 ⟨y,x~⟩의 차이. 즉, 압축 후에도 query와 vector의 dot product가 얼마나 보존되는지 | attention, embedding search, nearest neighbor search는 대부분 inner product/cosine similarity에 의존하므로 매우 중요함 |
| 6. Bias / Unbiased estimator | 압축 후 추정값의 평균이 원래 값과 같으면 unbiased. 즉, E[⟨y,x~⟩]=⟨y,x⟩ | 논문은 MSE에 최적인 quantizer가 inner product에는 bias를 만들 수 있음을 지적하고, residual QJL로 이를 해결함 |
| 7. Random rotation | 벡터를 무작위 직교행렬 Π로 회전시키는 것. 길이와 inner product는 보존하지만 좌표 분포를 균질하게 만듦 | TurboQuant의 핵심 출발점. worst-case 벡터도 회전 후에는 구면 위 랜덤 벡터처럼 다룰 수 있음 |
| 8. 고차원 구면과 concentration | 고차원 unit sphere의 랜덤 점은 각 좌표가 매우 작고, 대략 N(0,1/d)처럼 분포함 | 논문은 random rotation 후 각 좌표가 Beta distribution을 따르고, 고차원에서는 Gaussian에 가까워진다는 점을 이용함 |
| 9. Scalar quantization | 벡터 전체를 한 번에 양자화하지 않고, 각 좌표를 독립적으로 양자화하는 방식 | TurboQuant는 random rotation 덕분에 좌표별 scalar quantization만으로도 near-optimal vector quantization을 달성한다고 주장함 |
| 10. Lloyd-Max quantizer / 1D k-means | 1차원 분포를 여러 구간으로 나누고 각 구간을 centroid로 대표하게 하는 최적 scalar quantization 방법 | TurboQuantmse는 회전된 좌표의 Beta/Gaussian-like 분포에 대해 Lloyd-Max 방식으로 optimal codebook을 만든다 |
| 11. QJL, Quantized Johnson-Lindenstrauss | 랜덤 projection 후 sign만 저장하는 1-bit quantization. inner product를 unbiased하게 추정하는 데 사용됨 | TurboQuantprod는 MSE quantization의 residual에 QJL을 적용해 inner product bias를 제거함 |
| 12. Rate-distortion theory | 주어진 bit budget에서 이론적으로 달성 가능한 최소 distortion을 분석하는 정보이론 분야 | 논문의 강점은 TurboQuant가 정보이론적 lower bound에 약 2.7 X이내로 가까운 near-optimal rate를 달성한다고 증명한 점임 |
| 13. KV cache | Transformer decoder가 이전 token들의 Key/Value 벡터를 저장해 다음 token 생성에 재사용하는 메모리 | Long-context LLM에서는 KV cache가 매우 커지므로, TurboQuant를 이용해 KV cache를 낮은 bit로 압축하는 것이 주요 응용임 |
| 14. Product Quantization, PQ | vector DB/ANN search에서 많이 쓰이는 codebook 기반 벡터 압축 방법. 보통 k-means로 codebook을 학습함 | 논문은 TurboQuant가 PQ보다 preprocessing이 거의 없고, recall도 좋다고 비교함 |
| 15. Nearest Neighbor Search | query vector와 가장 비슷한 database vector를 찾는 문제. embedding retrieval, RAG, vector DB의 핵심 | TurboQuant는 압축된 벡터로도 top-k nearest neighbor를 잘 찾는지를 실험함 |
기존 offline/data_dependent 방식은 데이터셋에 맞춰 codebook를 학습해야 하므로 preprocessing 비용이 크고, KVcache 처럼 토큰이 생성될 때마다 백터가 계속 생기는 online setting에는 적합하지 않음
단순 Scalar quntization이나 기존 product Quantization 계열은 계산은 가능해도 MSE, inner product distortion에 대한 최적 distortion rate 보장이 약함. 특히 LLM에는 attention이 키, 벨류, 쿼리 간 inner product 구조에 크게 의존하므로 벡터를 압축해도 이 기하 구조를 잘 보존해야 함
입력 벡터를 random rotation matrix로 회전함
회전된 벡터의 각 좌표는 구면 위 랜덤 벡터의 좌표처럼 행동하며, Beta distribution을 따름 => 고차원에서는 이 분포가 대략 N(0, 1d)에 가까워지므로 각 좌표에 대해 Lloyd-Max 방식의 1D optimal scalar quantizer을 적용
De quantization에서는 저장된 codebook index를 centroid로 복원한뒤 랜덤 회전 행렬의 변환행렬을 곱해 원래 좌표로 되돌림
= MSE 기준에서 near-optimal
위의 MSE-optimal quantizer는 inner product estimation에는 bias를 만든다. => 2stage 구조를 통해 해결
1. b-1 bit로 MSE quantization 수행
2. 원본과 복원값 차이인 residual 을 계산
3. 이 residual을 1-bit QJL(Quantized Johnson-Lindenstrauss transform)으로 양자화
4. 최종 복원은 MSE 복원값과 QJL residual 복원값을 더해서 만듬
TurboQuant로 양자화한 뒤 원래와 복원 벡터의 차이를 오차 분포로 나타낸 것으로 위쪽은 분포 중심이 거의 0에 있고, 아래는 우측으로 치우친 편향이 보인다. inner product 추정에 bias가 생긴 것이다.
=> 아래는 mse에는 좋지만 inner product에는 bias를 만들 수 있음을 보여줌 == MSE를 잘 줄이는 quantizer가 inner product까지 항상 잘 보존하는 것은 아니다.
여기선 bit-width를 2로 고정하고, 벡터 쌍의 평균 inner product가 커질 때 error 분포를 확인
위는 분포가 0 중심으로 유지되지만, 아래는 inner product가 커질수록 에러 분포가 오른쪽으로 이동 => 바이어스가 커짐
=>TurboQuan mse의 inner product bias가 단순한 외즈가 아니라 inner product 크기와 연관된 systematic bias임을 보여줌
이론적 바운드와 실제 에러의 비교로 논문에서 증명한 바운드 사이에 잘 들어오는지 보여준다.
Needle in a haystack에서 kv cache 압축 성능을 보여주는 그림으로 needle을 모델이 제대로 찾아내는지 평가한다.
TurboQuant는 KC cache를 4배 이상 압축해도 long-context 능력을 거의 손상시키지 않음을 보여줌
위는 LongBench에서의 실제 downstream generation 성능을 보여주는 것으로, 성능 하락이 거의 없음을 보여준다.
그리고 타 방법론에 비해 양자화 시간이 0에 가까움을 보여줌
TurboQuant는 KV cache뿐 아니라 vector DB나 RAG용 embedding index compression에서도 효과적임.
즉, 압축 후에도 inner product 기반 검색 품질이 잘 유지됨
| 해결하려는 문제 | LLM KV cache, vector DB, nearest neighbor search에서는 고차원 벡터를 낮은 bit로 압축해야 하지만, 기존 방법은 느리거나 distortion 보장이 약함 | 단순 압축이 아니라 벡터의 기하 구조, 특히 거리와 inner product를 보존하는 것이 핵심 |
| 기존 방법의 한계 | Product Quantization 계열은 codebook 학습이 필요해 offline preprocessing 비용이 큼. 일부 online quantization은 빠르지만 distortion-rate가 비최적임 | KV cache처럼 토큰 생성 중 실시간으로 벡터가 생기는 환경에서는 data-dependent 학습 방식이 부적합 |
| 핵심 아이디어 | 입력 벡터를 random rotation하여 좌표 분포를 균질화한 뒤, 각 좌표를 optimal scalar quantizer로 독립 양자화 | 복잡한 데이터 기반 codebook 없이도 고차원에서는 좌표별 양자화만으로 near-optimal 성능 가능 |
| MSE용 TurboQuant | x를 random rotation Πx로 변환하면 각 좌표가 Beta distribution을 따르고, 고차원에서는 N(0, 1/d)에 가까워짐. 이후 Lloyd-Max quantizer로 좌표별 최적 양자화 수행 | MSE distortion을 최소화하는 online vector quantizer 구성 |
| Inner product용 TurboQuant | MSE-optimal quantizer는 inner product estimation에 bias를 만들 수 있음. 이를 해결하기 위해 (b-1) bit MSE quantization 후 residual을 1-bit QJL로 추가 양자화 | 최종 inner product estimator가 unbiased가 됨. 즉, E[⟨y,x^~⟩]=⟨y,x⟩ |
| 이론적 보장 | MSE distortion은 ≤ (3π)^{0.5}/2 *4 ^{−b}, inner product distortion은 ≤ (3π)^{0.5} / 2 * ∥y∥^{2} / d * 4^{−b} | 정보이론적 lower bound와 같은 4^{-b} rate를 달성하며, 최적 대비 약 2.7배 이내의 작은 상수 차이 |
| Lower bound 기여 | Shannon lower bound와 Yao’s minimax principle을 이용해 어떤 randomized quantizer도 4^{-b}보다 좋은 distortion-rate를 일반적으로 달성할 수 없음을 보임 | TurboQuant의 성능이 단순 empirical improvement가 아니라 정보이론적으로 거의 최적임을 증명 |
| 실험 1: 이론 검증 | DBpedia Entities + OpenAI embedding에서 MSE와 inner product error가 이론적 상·하한과 잘 정렬됨 | 논문의 수학적 distortion 분석이 실제 embedding 데이터에서도 유효함을 확인 |
| 실험 2: KV cache 압축 | Needle-In-A-Haystack에서 Llama-3.1-8B-Instruct 기준 TurboQuant는 4× 이상 압축해도 full precision과 동일한 score 0.997 달성 | long-context retrieval에서 KV cache를 크게 줄여도 핵심 정보 검색 능력이 유지됨 |
| 실험 3: LongBench | Llama-3.1-8B-Instruct에서 full cache 평균 50.06, TurboQuant 3.5-bit도 50.06. 2.5-bit는 49.44로 소폭 하락 | 3.5-bit 수준에서는 사실상 quality-neutral KV cache quantization 가능 |
| 실험 4: Nearest Neighbor Search | GloVe, OpenAI embedding 데이터에서 PQ/RabitQ보다 높은 recall을 보이며, quantization time은 거의 0에 가까움 | vector DB indexing에서 학습 기반 PQ보다 빠르고 실용적인 대안 가능 |
| 가장 중요한 차별점 | online, data-oblivious, accelerator-friendly, near-optimal distortion-rate, unbiased inner product estimation을 동시에 만족 | LLM serving과 vector search 양쪽에 적용 가능한 범용 고차원 벡터 양자화 프레임워크 |
| 한계 및 주의점 | random rotation/QJL projection의 실제 시스템 latency, norm 저장 overhead, 더 다양한 모델·attention 구조에서의 검증은 추가 필요 | 이론과 실험은 강하지만, production-level deployment에서는 하드웨어 최적화와 대규모 serving 검증이 중요 |
| 최종 요약 | TurboQuant는 random rotation으로 벡터 분포를 균질화하고, scalar quantization과 residual QJL을 결합해 MSE와 inner product를 거의 최적으로 보존하는 온라인 양자화 방법 | 이 논문의 핵심 가치는 이론적 최적성에 가까운 distortion 보장과 LLM KV cache/vector search에서의 실용성 결합 |
| 논문 제목 | TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate | 고차원 벡터를 빠르게 압축하면서도 MSE와 inner product 구조를 거의 최적으로 보존하는 온라인 양자화 방법 제안 |