기술 요약: FibQuant: 임의 접근 KV 캐시 압축을 위한 범용 벡터 양자화

1. 문제 제기

자기회귀 트랜스포머의 장문맥 추론은 주로 Key-Value(KV) 캐시 때문에 메모리 대역폭과 용량에 의해 점점 더 제약받고 있습니다. 캐시 크기는 문맥 길이, 배치 크기, 레이어 수, 헤드 수에 비례하여 선형적으로 증가하며, 모든 디코딩 단계에서 접근되어야 합니다.

기존 압축 방법들은 임의 접근 (random access) 이라는 중요한 시스템 제약에 직면해 있습니다. 배포 가능한 캐시 코덱은 임의 토큰의 키나 값을 간단한 주소 산술을 통해 독립적으로 디코딩할 수 있도록 고정된 주소에 표현을 저장해야 합니다. 이 제약은 가변 길이 부호화와 문맥 의존적 표현을 배제하며, 고정 비트율 양자화의 사용을 강제합니다.

현재 최첨단 임의 접근 코덱인 TURBOQUANT와 같은 방법들은 "정규화 - 회전 - 양자화" 방식을 사용합니다:

1. 벡터 노름을 저장합니다.
2. 공유된 무작위 직교 (Haar) 회전을 적용합니다.
3. 스칼라 Lloyd-Max 테이블을 사용하여 각 회전된 좌표를 독립적으로 양자화합니다.

이 인터페이스는 범용적이고 임의 접근이 가능하지만, 이 논문은 기하학적으로 비최적이라고 주장합니다. 벡터가 정규화되고 Haar 회전된 후, $k$개의 연속된 좌표 블록은 독립적인 스칼라 주변 분포의 곱을 형성하지 않습니다. 대신 단위 구면 (unit ball) 상의 구형 - 베타 (spherical-Beta) 소스를 형성합니다. 스칼라 코덱은 좌표를 독립적으로 취급하여 회전된 블록에 내재된 기하학적 구조 (반경 및 각도 상관관계) 를 폐기합니다. 또한, 스칼라 방법은 좌표당 1 비트 미만에서 효과적으로 작동하는 데 어려움을 겪으며, 현재 범용 보정 불필요 코덱이 실패하는 "1 비트 미만 간격 (sub-one-bit gap)"을 만듭니다.

2. 방법론: FibQuant

FibQuant는 스칼라 방법과 동일한 "정규화 - 회전" 인터페이스를 유지하면서 스칼라 좌표 테이블을 공유 반경 - 각도 벡터 코드북으로 대체하는 범용 고정 비트율 벡터 양자화를 제안합니다.

2.1 표준 소스

저자들은 정규화 - Haar 회전 인터페이스가 원래 KV 데이터 분포와 무관하게 범용 소스 분포를 유도함을 증명합니다.

• 정규화: 스케일을 제거합니다.
• Haar 회전: 방향을 제거합니다.
• 결과: 회전된 단위 벡터는 구면 $S^{d-1}$에서 Haar 균일 분포를 따릅니다. 결과적으로, $k$개의 연속된 좌표 블록은 단위 구면 $B^k$ 상의 특정 구형 - 베타 밀도 $f_{d,k}$를 따릅니다.
• 함의: 소스 분포가 특정 입력에 불변하므로 단일 오프라인 코드북이 모든 레이어, 헤드, 프롬프트, 모델에 사용할 수 있습니다.

2.2 코드북 구성

FibQuant 코드북은 구형 - 베타 소스에 매칭되도록 구성되며, 세 가지 구성 요소를 결합합니다:

1. 반경 ($r_n$): Bennett-Gersho 컴팬딩 규칙을 사용하여 구형 - 베타 소스의 반경 밀도에 매칭됩니다. $k=2$인 경우, 베타 분위수 반경을 포함하는 폐쇄형 해를 도출합니다.
2. 방향 ($u_n$): 균일한 각도 패킹을 보장하기 위해 준균일 구면 점 집합을 사용하여 근사합니다:
   • $k=2$: 평면 피보나치 나선 (Golden Quantizer).
   • $k=3$: 피보나치 구면.
   • $k \ge 4$: Roberts-Kronecker 저불일치 시퀀스.
3. 정제: 결정론적 초기화를 다중 재시작 Lloyd-Max 알고리즘으로 정제하여 특정 유한 코드북 크기 $N$에 대해 평균 제곱 오차 (MSE) 를 최소화합니다.

2.3 인코딩 및 디코딩

• 인코더: 노름 $\nu = \|x\|_2$를 계산하고, 단위 벡터 $\Pi x / \nu$를 회전시킨 후, $d/k$개의 크기 $k$ 블록으로 분할하여 공유 코드북에 대해 최근접 코드워드 조회를 수행합니다.
• 디코더: 코드워드를 검색하고, 블록을 재구성한 후 블록을 연결하고, 역회전을 적용하며, 노름으로 스케일링합니다.
• 비트율: 비트율은 좌표당 $b = (\log_2 N) / k$ 비트입니다. $N$과 $k$를 변형함으로써 FibQuant는 조밀한 비트율 축을 달성하여 가변 길이 주소 지정 없이 분수 비트 및 1 비트 미만 작동 지점을 가능하게 합니다.

3. 주요 기여

3.1 표준 소스 식별

이 논문은 (정리 1) 노름 - 그 후 Haar 회전 인터페이스가 모든 비영 (nonzero) 입력 분포를 동일한 구형 - 베타 주변 분포 $f_{d,k}$로 매핑함을 증명합니다. 이는 공유 오프라인 코드북이 KV 캐시 압축을 위한 이론적으로 올바른 범용 객체임을 확립합니다.

3.2 스칼라 특화 대비 벡터 우위

저자들은 (정리 2) 최적의 $k$-벡터 코드가 매칭된 비트율에서 스칼라 곱 특화 ($k=1$) 를 엄격하게 우세함을 증명합니다. 고비트율 이득은 두 구성 요소로 분해됩니다:

1. 셀-성형 인자 ($\gamma_{cell}$): 벡터 양자화 셀 (예: 2 차원에서의 육각형) 은 직사각형 스칼라 셀보다 효율적입니다.
2. 밀도-매칭 인자 ($\gamma_{dens}$): 결합 구형 - 베타 밀도에 매칭하는 것은 스칼라 주변 분포에만 매칭하는 것보다 우수합니다.

3.3 조밀한 비트율 축

정수 비트율로 제한되는 스칼라 Lloyd-Max 테이블과 달리, FibQuant는 $b \in (0, \infty)$의 조밀한 비트율 집합을 실현합니다. 이는 1 비트 미만 영역 (예: $b \approx 0.19$) 에서의 작동을 허용하며, 현재 범용 임의 접근 코덱이 기능을 상실하는 영역입니다.

4. 실험 결과

4.1 소스 부호화 성능

표준 구형 - 베타 소스에서 FibQuant는 모든 정수 비트율에서 스칼라 TURBOQUANT 를 엄격하게 우세합니다. 또한 정수 비트율 간의 간격을 메워 스칼라 방법이 도달할 수 없는 작동 지점을 제공합니다.

4.2 KV 캐시 압축 (GPT-2 Small)

주의력 출력 코사인 유사도를 지표로 하여 GPT-2 작은 KV 캐시에서 평가:

• FibQuant는 5 배 압축 (0.99 유사도) 에서 34.1 배 압축 (0.946 유사도) 까지 메모리 - 충실도 프론티어를 추적합니다.
• 높은 압축 비율 (>10 배) 에서 FibQuant는 레이어별 보정이 필요한 저랭크 투영 방법을 능가하며 충실도를 유지하는 유일한 범용 보정 불필요 방법입니다.
• 논문은 전체 벡터 코드 ($k=d$) 가 극단적인 압축에서 반 벡터 코드 ($k=d/2$) 보다 성능이 뛰어나다고 지적합니다. 이는 모든 비트를 주의력 내적곱과 직접적으로 상관되는 각도 패킹에 집중하기 때문입니다.

4.3 엔드투엔드 언어 모델 성능 (TinyLlama-1.1B)

WikiText-103 퍼플렉시티와 HellaSwag 정확도로 평가:

• $b=4$ (4 배 압축) 에서: FibQuant는 fp16 기준보다 0.10 퍼플렉시티 이내이며 스칼라 TURBOQUANT 를 능가합니다.
• $b=2$ (8 배 압축) 에서: FibQuant는 15.88 퍼플렉시티를 달성하여 스칼라 TURBOQUANT(56.72) 와 토큰별 INT 양자화 (4450.5 로 붕괴됨) 를 현저히 능가합니다.
• 분수 비트율: FibQuant는 스칼라 코덱에서 사용할 수 없는 중간 작동 지점 (예: $b=2.5, 3.5$) 을 제공하여 캐시 예산을 먼저 선택하고 코덱을 이에 맞게 조정할 수 있게 합니다.

5. 중요성과 주장

이 논문은 종종 공학적 한계로 간주되는 임의 접근 제약이 심오한 수학적 결과를 가진다고 주장합니다: 데이터를 특정 구형 - 베타 기하학으로 강제합니다. 이 표준 소스를 인식함으로써 FibQuant는 스칼라 양자화가 놓친 "성형 및 밀도 매칭 이득"을 회복합니다.

중요성은 다음과 같습니다:

1. 범용성: 단일 코드북이 보정 없이 모든 모델 구성에서 작동합니다.
2. 1 비트 미만 작동: 스칼라 방법이 실패하는 영역에서 고충실도 압축을 가능하게 하여 장문맥 추론을 위한 사용 가능한 메모리 예산을 효과적으로 확장합니다.
3. 시스템 호환성: 디압축을 주의력 커널과 융합하는 데 필요한 고정 주소 임의 접근 인터페이스를 유지하여 기존 서빙 프레임워크에서 즉시 배포 가능합니다.

저자들은 임의 접근이 좋은 소스 부호화를 배제하지 않으며, 오히려 정확히 어떤 소스를 부호화해야 하는지를 규정한다고 결론지었습니다.