기술 요약: 프랙탈 KV-캐시 아카이브 (Fractal KV-Cache Archives)

문제 정의

트랜스포머 언어 모델을 긴 컨텍스트에서 서빙하는 것은 연산 제한(compute-bound)의 문제에서 메모리 제한(memory-bound)의 문제로 전환되었습니다. 오토레그레시브 어텐션에 필요한 키-값(Key-Value, KV) 캐시는 컨텍스트 길이에 따라 선형적으로 증가하며, 종종 모델 가중치보다 커져 배치 크기를 제약합니다. 기존 솔루션들이 손실 압축(양자화, 제거, 오프로딩)에 집중하는 반면, 본 논문은 다음과 같은 하위 단계의, 흔히 암묵적으로 던져지는 질문을 다룹니다: 벡터 양자화를 통해 KV 상태가 심볼 스트림으로 축소된 후, 그 스트림을 어떻게 저장해야 하는가?

저자들은 저장 계층이 단순한 블롭(blob)이 아니라, 성장하는 캐시의 특정 액세스 패턴을 지원할 수 있는 능동적인 구성 요소여야 한다고 주장합니다: 즉, O(1) 분할 상환 첨가(amortized append) (새로운 토큰이 도착할 때)와 O(1) 무작위 접근(random access) (과거 위치를 검색할 때)을 지원하면서, 인플레이스(in-place) 검색과 같은 추가 기능을 제공할 수 있어야 합니다.

방법론

1. 저장 프리미티브: 수축 반복 맵 코드 (Contractive Iterated-Map Codes)

본 논문은 양자화된 KV 인덱스의 직렬화 계층으로 무손실 수축 반복 맵 코드(구체적으로는 카오스 게임 표현(Chaos Game Representation)과 유니버설 시퀀스 맵(Universal Sequence Maps)의 일반화)를 사용할 것을 제안합니다.

• 메커니즘: 크기가 $N$인 알파벳 위의 심볼 시퀀스는 2D 평면상의 점 궤적으로 매핑됩니다. 하나의 정점을 각 심볼에 할당한 정 $N$-각형이 고정됩니다. 심볼 $c_k$는 현재 점 $p_{k-1}$을 수축 $p_k = V(c_k) + r(p_{k-1} - V(c_k))$를 통해 새로운 점 $p_k$로 매핑합니다 (여기서 $r$은 수축 비율입니다).
• 특성:
  • 무손실: 수축 비율 $r$이 각 심볼에 대해 서로 분리된 "셀(cell)"을 보장할 만큼 충분히 작다면, 이 맵은 가역적(invertible)입니다.
  • 효율성: 인코딩은 선형 시간 내에 이루어집니다. 디코딩은 가장 가까운 저장된 앵커 포인트(anchor point)로부터 필요한 구간만을 재구성함으로써 임의의 위치에 대한 무작위 접근을 허용합니다.
  • 자기 유사성: 도달 가능한 점들의 집합은 프랙탈 끌개(attractor)를 형성합니다 (예: $N=3$일 때 시에르핀스키 가스켓).
• 구현: 역전 과정에서의 부동 소수점 오차 증폭을 완화하기 위해, 코덱은 고정된 길이의 구간당 하나의 점을 저장하고 앵커 기반 역방향 탐색(anchored backward search)을 통해 구간을 재구성합니다.

2. 양자화 전략

저자들은 이 아카이브에 입력될 최적의 양자화 방식을 결정하기 위해 **GPT-2 (124M)**와 1024-토큰 컨텍스트를 대상으로 통제된 연구를 수행했습니다.

• 정확한 윈도우 (Exact Window): 성능 유지를 위해 작은 정확한 윈도우(4개의 "어텐션 싱크" 토큰 + 최근 32개 토큰)를 유지합니다. 나머지 컨텍스트는 아카이브됩니다.
• 양자화 변체:
  • 풀링(Pooled) vs. 헤드별(Per-Head): 모든 어텐션 헤드가 공유하는 단일 코드북과 개별 헤드별 코드북을 비교합니다.
  • 잔차 벡터 양자화 (Residual Vector Quantization, RVQ): 벡터를 $s$개의 코드북 인덱스 합으로 저장합니다.
  • 키/값 비대칭성 (Key/Value Asymmetry): 키(K)와 값(V)을 각각 양자화할 때의 차등적인 영향을 조사합니다.

3. 인플레이스 검색 (In-Place Retrieval)

본 논문은 반복 맵 코드의 기하학적 특성을 활용합니다: 공통된 길이 $s$의 접미사(suffix)를 공유하는 점들은 공간적으로 가깝습니다 (거리 $\approx 2r^s$). 이를 통해 주변 텍스트를 디컴프레션하지 않고도 저장된 2D 벡터에 대한 **근사 부분 문자열 쿼리(approximate substring queries)**를 직접 실행할 수 있습니다.

주요 결과

1. 코덱 성능

프랙탈 코덱은 모델과 독립적인 고성능 저장 프리미티브 역할을 합니다:

• 인코딩: 0.68 µs/char (선형 시간).
• 무작위 접근: 1M-캐릭터 문서 기준 룩업당 311 µs.
• 첨가 (Append): 토큰당 175 µs (분할 상환).

2. 양자화 결과 (GPT-2, 1024 토큰)

• 헤드별 우위: 헤드별 코드북은 동일한 비트 예산에서 풀링된 코드북보다 성능이 훨씬 뛰어납니다. 헤드별 RVQ (깊이 2)는 퍼플렉시티(perplexity) 증가를 **+29.2%**에서 **+15.0%**로 줄였습니다.
• 키/값 비대칭성: 키를 양자화하는 것이 값을 양자화하는 것보다 퍼플렉시티에 약 4배 더 치명적입니다.
  • 값만 양자화 (키는 정확함): +4.0% 퍼플렉시티.
  • 키만 양자화 (값은 정확함): +14.5% 퍼플렉시티.
  • 이는 키가 어텐션 라우팅을 결정(높은 민감도)하는 반면, 값은 평균화(오차 감쇄)된다는 점을 확인시켜 줍니다.
• 최적의 하이브리드 스킴: 키에 더 많은 비트(4단계 RVQ)를 할당하고 값에 적은 비트(2단계 RVQ)를 할당하는 것이 최상의 트레이드오프를 제공합니다:
  • 압축률: fp16 캐치 대비 36배 감소.
  • 퍼플렉시티 비용: +11.2% (특히 아카이브가 지배적인 "컨텍스트의 두 번째 절반"에서는 +16.6%).
  • 저장 용량: 1025 bytes/token.

3. 검색 능력

• 정확한 회상 (Exact Recall): 저장된 점들 사이의 거리를 임계값 처리하면, 길이가 $\ell$인 일치하는 접미사를 가진 모든 위치를 **1.00의 재현율(recall)**로 찾아냅니다.
• 정밀도 (Precision): 수치적 정밀도에 의해 제어됩니다. 배정밀도(double-precision) 인덱스는 0.89–1.00의 정밀도를 달성하며, 단정밀도(single precision)는 거친 필터 역할을 합니다.
• 효율성: 2D 공간에서 100K 위치에 대한 브루트 포스 최근접 이웃(nearest-neighbor) 탐색은 쿼리당 약 0.9 ms가 소요됩니다.
• 디코딩: 매칭된 컨텍스트는 매칭된 벡터로부터 역방향으로 디코딩되며, 이때 외부 텍스트에 접근하지 않습니다.

의의 및 주장

본 논문은 코드북의 기하학이나 벡터 저장 엔진에 집중하는 동시기 연구들(예: FibQuant, RetroInfer)과 구별되는 세 가지 주요 기여를 주장합니다:

1. 통합된 아카이브 형식: 수축 반복 맵 코드를 무손실 저장소, 무작위 접근 디코더, 그리고 인플레이스 검색 인덱스를 동시에 수행하는 실용적인 KV 아카이브로 프레임화합니다. 저장과 검색을 단일 표현으로 통합한 것이 참신한 기여입니다.
2. 양자화 통찰: 키/값 비대칭성을 구체적인 퍼플렉시티 예산으로 정량화하여, 비트 비대칭 하이브리드 스킴(키에 4배의 비트, 값에 2배의 비트)이 롱 컨텍스트 압축을 위한 최적의 운용 지점임을 입증했습니다.
3. 검색 가능한 메모리: 아카이브가 임베딩에 대한 시맨틱 검색이 아닌 **시퀀스 구조 매칭(접미사 매칭)**을 직접 지원함을 보여줌으로써, 모델이 전체 캐시를 실체화하지 않고도 관련 과거 컨텍스트를 찾을 수 있는 검색 증강 디코딩(retrieval-augmented decoding)을 가능하게 합니다.

저자가 인정한 한계점

• 규모: 실험은 GPT-2 (124M) 및 단일 1024-토큰 컨텍스트로 제한됩니다. 더 큰 모델에 대한 결과는 테스트되지 않았습니다 (단, 더 관대할 것으로 예상됨).
• 코드북 학습: 코드북은 데이터 전반에 걸쳐 분할 상환되는 방식이 아니라 코퍼스별로 학습됩니다.
• 검색 범위: 검색은 임베딩에 대한 시맨틱 검색이 아니라 엄격한 **시퀀스 구조 매칭(접미사)**입니다.
• 압축률: 프랙탈 코덱의 순수 압축률은 표준 바이트 패커(byte-packers)와 비슷합니다. 이들의 이점은 순수 크기 감소보다는 액세스 패턴(무작위 접근/검색)에 있습니다.
• 벤치마킹: 본 논문은 FibQuant와 같은 동시기 연구들의 특정 코드북 설계를 벤치마킹하지 않았으며, 이러한 양자화 도구들을 본 저장 형식과 결합하는 것이 향후 과제임을 명시했습니다.