🤖 machine learning

Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit

이 논문은 KV 캐시를 개별 벡터가 아닌 시퀀스로 간주하여 확률적 언어 트라이 기반의 접두사 중복 제거와 예측 델타 코딩을 결합함으로써, 기존 TurboQuant 대비 이론적으로 최대 914,000 배에 달하는 압축 효율을 달성할 수 있는 새로운 시퀀셜 KV 압축 아키텍처를 제안합니다.

원저자: Gregory Magarshak

게시일 2026-04-20

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Gregory Magarshak

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

이 논문은 인공지능 (AI) 이 긴 대화를 하거나 긴 문서를 읽을 때 겪는 '기억력 부족'과 '메모리 과부하' 문제를 해결하는 획기적인 새로운 방법을 제안합니다.

기존의 기술이 "각각의 기억 조각을 더 작게 잘라내자"는 접근이었다면, 이 논문은 **"기억 조각들 사이의 연관성을 이용해, 아예 기억할 필요가 없는 부분을 없애자"**는 발상의 전환을 제시합니다.

이해하기 쉽게 세 가지 핵심 비유로 설명해 드리겠습니다.

1. 문제: 거대한 도서관과 무거운 책장 (KV 캐시)

AI 가 대화를 할 때, 매번 새로운 단어를 입력받으면 그 단어를 이해하기 위해 이전까지의 모든 대화 내용을 다시 떠올려야 합니다. 이를 위해 AI 는 'KV 캐시 (Key-Value Cache)'라는 메모리 공간에 대화 내용을 저장해 둡니다.

현실: 700 억 개의 파라미터를 가진 거대한 AI 가 12 만 단어 분량의 긴 문서를 읽으면, 이 '기억 공간'만 80GB나 됩니다. 이는 AI 자체의 두뇌 (모델 가중치) 보다도 더 무겁습니다.
기존 해결책 (TurboQuant): 지금까지는 이 거대한 메모리 공간에 들어있는 숫자들을 더 작은 숫자로 압축하는 기술 (양자화) 을 개발했습니다. 마치 거대한 책장을 더 얇은 종이로 만든 것처럼요. 하지만 이 방법에는 한계가 있습니다. 숫자를 아무리 잘게 쪼개도, 책장 자체의 '부피'는 줄어들지 않기 때문입니다.

2. 새로운 아이디어: "이미 알고 있는 건 적을 필요가 없다"

이 논문의 핵심은 **"AI 는 이미 다음 단어를 예측할 수 있다"**는 사실에 있습니다.

비유: 예측 가능한 대화
당신이 친구와 대화할 때, 친구가 "오늘 날씨가 정말..."이라고 말하면, 당신은 다음에 "좋다" 또는 "나쁘다"라고 말할 것이라고 99% 확신합니다.
만약 친구가 "오늘 날씨가 정말..."이라고 말하고, 당신이 "아이스크림을 먹자"라고 대답했다면, 그건 매우 놀라운 일입니다. 하지만 대부분의 대화는 예측 가능합니다.
이 논문의 접근법:
기존 기술은 "날씨가 정말..."이라는 문장 전체를 메모리에 저장했습니다. 하지만 이 논문은 이렇게 말합니다.

"AI 는 이미 '날씨가 정말...' 다음에 '좋다'가 올 것이라고 예측하고 있습니다. 그렇다면 '날씨가 정말...'이라는 문장을 다시 저장할 필요 없이, 예상과 실제의 차이 (오차) 만 저장하면 되지 않을까?"

만약 예상과 실제가 같다면, 저장할 데이터는 0이 됩니다. 차이가 아주 작다면, 아주 적은 비트만 저장하면 됩니다.

3. 두 단계의 마법 (기술적 해결책)

이 논문은 이 아이디어를 실현하기 위해 두 단계의 마법을 제안합니다.

1 단계: "유사한 대화는 하나로 합치자" (확률적 접두사 제거)

상황: 수많은 사용자가 AI 에게 질문을 합니다.
- 사용자 A: "안녕하세요, 비서님. 오늘 일정을 알려주세요."
- 사용자 B: "안녕하세요, AI 비서님. 오늘 일정을 알려주세요."
기존 방식: 두 문장이 글자가 조금 다르므로, AI 는 두 개의 완전히 다른 메모리 공간을 따로 마련합니다.
이 논문의 방식: 두 문장은 의미가 거의 동일합니다. AI 는 이 두 문장이 "비슷한 시작"을 가졌음을 알아챕니다. 그래서 공통된 시작 부분 (안녕하세요, 비서님...) 은 한 번만 저장하고, 나머지 작은 차이 ("오늘 일정을 알려주세요" vs "오늘 일정을 알려주세요") 만 따로 저장합니다.
- 비유: 같은 옷을 입은 여러 사람이 있다면, 옷은 한 벌만 사두고 사람마다 다른 신발 (차이점) 만 따로 챙기면 됩니다.

2 단계: "예상과 실제의 차이만 적자" (예측 델타 코딩)

상황: AI 가 다음 단어를 예측할 때, "다음 단어는 '사과'일 확률이 90% 입니다."라고 생각합니다.
기존 방식: '사과'라는 단어에 해당하는 거대한 숫자 덩어리 전체를 메모리에 저장합니다.
이 논문의 방식: AI 가 '사과'를 예측했는데, 실제로 입력된 단어가 '사과'였다면, 저장할 데이터는 0입니다. 만약 '배'라고 입력되었다면, '사과'와 '배' 사이의 아주 작은 차이만 저장합니다.
- 비유: 요리사가 "오늘 메뉴는 김치찌개일 것 같아"라고 예상했는데, 실제로 김치찌개가 나왔다면 메모장에 적을 게 없습니다. 만약 불고기라면, "김치찌개에서 불고기로 바뀐 점"만 적으면 됩니다.

4. 왜 이것이 혁명적인가? (결과)

이 두 가지 방법을 합치면 어떤 일이 일어날까요?

기존 기술 (TurboQuant): 메모리 크기가 대화 길이에 비례하여 일정한 비율로 계속 커집니다. (10 만 단어면 10 배, 20 만 단어면 20 배)
이 논문 (순차적 압축): 대화 길이가 길어질수록, AI 가 더 많은 맥락을 알게 되어 다음 단어를 더 정확하게 예측하게 됩니다. 따라서 저장해야 할 '차이'는 점점 줄어들고, 단어 하나당 필요한 메모리는 오히려 감소합니다.

결론적으로:
이 기술이 실현되면, AI 는 수백만 단어 분량의 문서를 읽어도 메모리 부족으로 멈추지 않을 것입니다. 오히려 문장이 길어질수록 AI 는 더 똑똑해지고, 기억하는 비용은 더 저렴해집니다.

요약

이 논문은 **"AI 의 기억을 단순히 작게 만드는 것 (기존 기술)"이 아니라, "AI 가 이미 알고 있는 것을 기억하지 않게 만드는 것 (새로운 기술)"**으로 문제를 해결합니다.

기존: 거대한 책장을 더 얇은 종으로 만듦.
새로운: 책장에 이미 있는 내용과 똑같은 내용은 아예 적지 않음. 그리고 예상과 다른 부분만 아주 작게 적음.

이 방법은 AI 가 긴 문맥을 이해하는 능력을 비약적으로 향상시키면서, 동시에 하드웨어 비용은 획기적으로 줄여줄 것입니다. 마치 기억력이 좋은 친구와 대화할 때, 이미 알고 있는 건 반복해서 설명하지 않아도 되는 것처럼 AI 도 이제 효율적으로 기억할 수 있게 된 것입니다.

1. 문제 정의 (Problem Statement)

대규모 언어 모델 (LLM) 의 추론 과정에서 KV 캐시 (Key-Value Cache) 는 컨텍스트 길이가 길어질수록 메모리 병목 현상의 주요 원인이 됩니다.

현재의 한계: 기존 KV 캐시 압축 기술 (TurboQuant 등) 은 주로 개별 벡터 (Per-Vector) 단위의 양자화에 집중합니다. TurboQuant 는 회전 (PolarQuant) 과 잔차 보정 (QJL) 을 통해 벡터 단위 압축의 Shannon 한계 (약 3 비트/성분) 에 근접했다고 주장합니다.
핵심 문제: KV 캐시는 독립적인 벡터들의 집합이 아니라, 순차적 (Sequential) 구조를 가진 데이터입니다. 토큰은 모델이 학습한 언어 분포에서 샘플링된 것이므로, 이전 토큰과 KV 벡터之间存在 강한 상관관계가 있습니다.
기회: 개별 벡터의 엔트로피가 아니라, 전체 시퀀스 조건부 엔트로피 (Conditional Entropy) 를 고려할 때, 언어의 예측 가능성 (Predictability) 으로 인해 KV 벡터의 정보량은 이론적으로 훨씬 적을 수 있습니다. 기존 연구는 이 순차적 구조를 활용하지 못했습니다.

2. 방법론 (Methodology)

저자는 순차적 KV 압축 (Sequential KV Compression) 이라는 2 계층 아키텍처를 제안합니다. 이는 기존 벡터 단위 양자화와 직교하며 결합 가능합니다.

계층 1: 확률적 접두사 중복 제거 (Probabilistic Prefix Deduplication)

개념: 기존 시스템 (vLLM 등) 은 '정확한' 토큰 일치 (Exact Prefix Matching) 만을 기반으로 KV 캐시를 공유합니다. 하지만 "You are a helpful assistant"와 "You are an AI assistant"처럼 의미적으로 유사하지만 토큰이 다른 경우에도 KV 벡터는 매우 유사합니다.
기술: 확률적 언어 트리 (Probabilistic Language Tries, PLT) 의 거리 척도 $d_T(s, s') = -\log_2 P_M(s \wedge s')$ $d_{T} (s, s^{'}) = - lo g_{2} P_{M} (s \land s^{'})$ 를 사용합니다.
- 이 척도는 두 시퀀스가 확률 공간에서 얼마나 가까운지 (공유된 고확률 접두사의 길이) 를 측정합니다.
- 거리 임계값 $\delta$ 내에서 유사한 세션을 클러스터링하고, 가장 확률이 높은 시퀀스 (Centroid) 의 KV 캐시 전체를 저장합니다.
- 다른 세션은 Centroid 와의 차이 (Delta) 만 저장합니다. 이는 의미적으로 유사하지만 토큰이 다른 세션 간의 중복을 제거합니다.

계층 2: 예측 기반 델타 코딩 (Predictive Delta Coding)

개념: 단일 세션 내에서, $t$ -번째 KV 벡터는 이전 컨텍스트 ( $t-1$ 까지) 에 의해 거의 결정됩니다. 따라서 실제 KV 벡터 대신 모델의 예측값과 실제값의 차이 (Residual) 만 저장합니다.
예측: 모델이 다음 토큰에 대해 가지는 확률 분포 $P_M(t_i | t_{<i})$ $P_{M} (t_{i} ∣ t_{< i})$ 를 사용하여, 기대되는 KV 벡터 $\hat{KV}_i$ $\hat{K V}_{i}$ 를 계산합니다.
- $\hat{KV}_i = \sum_{t \in V} P_M(t | t_{<i}) \cdot F_M(t_{<i}, t)$
- 실제 구현에서는 전체 어휘에 대한 연산 비용이 너무 크므로, 확률이 높은 Top-k 토큰만 사용하여 근사합니다.
저장: 실제 KV 벡터 $KV_i$ $K V_{i}$ 대신 잔차 $R_i = KV_i - \hat{KV}_i$ $R_{i} = K V_{i} - \hat{K V}_{i}$ 를 저장합니다.
- 모델이 다음 토큰을 잘 예측할수록 (Perplexity 가 낮을수록) 잔차의 크기와 엔트로피는 0 에 수렴합니다.

계층 3: 기존 양자화와의 결합

위 두 계층을 거친 후에도 남는 잔차 벡터 $R_i$ 에 대해 TurboQuant 와 같은 기존 벡터 단위 양자화를 적용하여 최종 압축을 수행합니다.

3. 주요 기여 (Key Contributions)

순차적 엔트로피 상한선 (Sequential Entropy Bound, Theorem 1):
- KV 벡터의 조건부 엔트로피는 모델의 토큰 단위 놀라움 (Per-token Surprisal) 으로 상한이 잡힌다는 것을 수학적으로 증명했습니다.
- 수식: $H(KV_i | KV_{<i}) \le H(t_i | t_{<i})$ .
- 이는 KV 벡터가 토큰 시퀀스의 결정론적 함수이므로, 토큰의 예측 가능성이 KV 벡터의 예측 가능성으로 직접 이어진다는 것을 의미합니다.
이론적 압축률 분석:
- 일반적인 영어 텍스트의 Perplexity(10~~20) 를 가정할 때, 토큰당 필요한 비트 수는 약 **3.3~~4.3 비트**입니다.
- 반면, TurboQuant 는 벡터의 각 성분 (Component) 당 3 비트를 사용하며, 헤드가 64~128 개, 레이어가 80 개인 모델의 경우 토큰당 약 390 만 비트가 필요합니다.
- 이론적 압축 비율: TurboQuant 대비 약 914,000 배의 압축이 가능합니다. (현실적인 오버헤드를 고려한 보수적 추정치인 1,000 배 오버헤드 상황에서도 약 914 배의 압축률 유지).
컨텍스트 길이에 따른 압축률 향상:
- 기존 벡터 단위 방법은 컨텍스트 길이가 길어질수록 메모리 사용량이 선형적으로 증가합니다.
- 순차적 압축은 컨텍스트가 길어질수록 모델의 예측 정확도가 높아져 (잔차 감소) 마지널 토큰당 비용이 감소합니다. 즉, 긴 컨텍스트일수록 상대적으로 더 효율적입니다.
직교성 (Orthogonality):
- 제안된 두 계층 (접두사 중복 제거, 예측 델타 코딩) 은 서로 독립적이며, 기존 양자화 기술과 결합하여 시너지 효과를 낼 수 있음을 증명했습니다.

4. 실험 결과 및 이론적 성과 (Results & Significance)

이론적 한계의 재정의: TurboQuant 가 증명했던 "벡터 단위 Shannon 한계"는 부분 문제 (Sub-problem) 의 한계일 뿐이며, 전체 시퀀스 관점에서는 훨씬 더 낮은 엔트로피 한계가 존재함을 보였습니다.
메모리 벽 (Memory Wall) 의 해결: KV 캐시 메모리 요구량이 컨텍스트 길이에 따라 선형적으로 증가한다는 기존의 통념을 깨뜨립니다. 순차적 압축을 적용하면 긴 컨텍스트 추론 시 토큰당 메모리 비용이 감소하여, 수백만 토큰 단위의 문서 분석이나 지속적 에이전트 메모리 구현이 경제적으로 가능해집니다.
예측적 델타 코딩의 효율성: 모델이 확신하는 토큰 (낮은 Surprisal) 에서는 잔차가 거의 0 이 되어 비트 할당이 거의 필요 없으며, 불확실한 토큰에만 비트를 집중할 수 있습니다. 이는 Rate-Distortion 관점에서 최적의 할당 전략입니다.
구현 가능성:
- Top-k 근사: 전체 어휘에 대한 예측 대신 Top-k 토큰만 사용하여 예측 KV 벡터를 계산함으로써 추론 오버헤드를 최소화합니다.
- Speculative Decoding과의 호환성: Speculative Decoding 에서 사용하는 Draft 모델의 Top-k 분포를 그대로 KV 예측에 재사용할 수 있어 추가적인 계산 비용이 거의 들지 않습니다.

5. 결론 및 의의

이 논문은 KV 캐시 압축의 패러다임을 개별 벡터의 양자화에서 시퀀스 구조의 활용으로 전환시킵니다.

핵심 통찰: 언어 모델이 학습한 언어의 구조적 예측 가능성 (Predictability) 은 KV 캐시 데이터의 실제 정보량 (엔트로피) 을 크게 줄여줍니다.
의의: TurboQuant 와 같은 기존 기술이 도달한 한계는 '절대적인 한계'가 아닙니다. 순차적 압축 기법을 통해 이론적으로 수만 배에서 수십만 배에 이르는 추가적인 압축 잠재력이 존재하며, 이는 장거리 컨텍스트 추론의 실용성을 획기적으로 높일 수 있는 소프트웨어적 해결책을 제시합니다.

요약하자면, 이 연구는 **"KV 캐시는 단순한 숫자의 나열이 아니라, 예측 가능한 언어의 흐름이다"**라는 전제하에, 그 예측 가능성을 수학적으로 증명하고 이를 활용한 초고효율 압축 아키텍처를 제안한 획기적인 논문입니다.