https://arxiv.org/abs/2603.14303
SemantiCache: Efficient KV Cache Compression via Semantic Chunking and Clustered Merging
Existing KV cache compression methods generally operate on discrete tokens or non-semantic chunks. However, such approaches often lead to semantic fragmentation, where linguistically coherent units are disrupted, causing irreversible information loss and d
arxiv.org
Abstract.
기존의 KV cache 압축 방법들은 일반적으로 불연속적인 토큰이나 의미가 고려되지 않은(non-semantic) chunk 단위로 작동합니다. 그러나 이러한 접근 방식은 언어적으로 일관된 단위가 붕괴되는 semantic fragmentation을 자주 유발하며, 이는 정보 손실과 모델 성능 저하의 원인이 됩니다.
이를 해결하기 위해, 본 논문에서는 언어의 의미론적 계층 구조에 압축 과정을 align 함으로써 의미론적 무결성을 보존하는 새로운 압축 프레임워크를 제안합니다. 구체적으로, 먼저 자연스러운 의미적 경계를 나타내는 delimiters를 사용하여 cache를 의미론적으로 일관된 chunks로 분할합니다. 각 chunk 내에서는 토큰들을 의미론적 군집으로 묶기 위해 계산 효율적인 GSC(Greedy Seed-based Clustering) 알고리즘을 사용합니다. 이렇게 현성된 군집들은 proportional attention 메커니즘을 통해 더욱 압축된 semantic cores들로 병합되며, 이 메커니즘은 병합된 토큰들의 축소된 attention 기여도를 다시 균형있게 조정합니다.
Introduction.
다양한 task들을 처리하는 LLM의 능력이 빠르게 발전하고 있지만, long context 시나리오에서 발생하는 autoregressive inference의 높은 비용 문제는 여전히 남아있습니다. 여기서 핵심적인 병목은 이전 모든 토큰의 attention keys와 values들을 저장하는 KV cache입니다. 이 cache는 input sequence length에 따라 선형적으로 증가하며, 다음과 같은 두 가지 문제를 초래합니다: (1) 높은 메모리 사용량, (2) 추론 지연 시간의 증가.
앞서 언급한 문제들을 해결하기 위해 다양한 KV cache 압축 기술들이 제안되었습니다. 이러한 방법들은 크게 eviction-based와 merging-based가 있습니다. eviction-based 방법론은 attention score등의 요소를 바탕으로 덜 "중요하다"고 판단되는 토큰들을 영구적으로 폐기합니다. 그러나 이 방법은 삭제된 토큰에 포함된 정보의 돌이킬 수 없는 손실로 인해 성능 저하를 초래할 수 있습니다. 이러한 한계를 해결하기 위해, merging-based 방법론은 토큰을 pruning하는 대신 토큰들을 merging하여 cache를 압축하는 것을 목표로 합니다.
이러한 차이점에도 불구하고, 이 두 방법들은 치명적인 결함을 갖고 있습니다. 언어의 자연스러운 구조를 무시한 채, 불연속적인 토큰이나 임의의 non-semantic chunks 단위로 작동한다는 점입니다. 이러한 접근 방식은 구, 절 또는 문장과 같이 일관된 의미 구조를 쪼개버리는 semantic fragmentation을 유발합니다. 그리고 이러한 fragmentation은 중요한 의미의 솔실을 일으켜 모델 성능을 저하시킵니다.
자연어는 단어들의 평평한 흐름이 아니라. 의미 구조의 계층입니다. 본 논문의 저자들은 여기서 영감을 받아 chunk 압축 과정을 이 계층 구조와 align하여 일관된 의미 구조를 보존하고 fragmentation을 방지합니다. 이 과정은 인간이 긴 텍스트를 효율적으로 암기하기 위해 사용하는 인지 전략을 적용한 것입니다. 구체적으로, 사람들은 먼저 텍스트를 완전한 의미 단위(예: 문장 및 절)로 분할한 다음, 중심 개념을 식별하고 통합함으로써 각 단위의 핵심 의미를 추출하는 정보의 계층적 분해 과정을 모방합니다.
본 논문에서 제안하는 SemantiCache는 자연스러운 의미적 경계를 따라 cache를 분할하여 의미론적으로 일관된 chunk를 생성함으로써 이를 반영합니다. 그 다음, 이러한 chunk 내부에서 계산 효율적인 GSC 알고리즘을 도입하여 의미론적으로 일관된 토큰들을 그룹화함으로써 내부 구조를 분석합니다. 결과로 나온 군집들은 세부 semantic core로 병합됩니다. 이러한 병합으로 인해 발생하는 영향력의 희석을 방지하기 위해, 각 core의 attention 기여도를 재조정하는 proportional attention을 추가합니다. 이는 의미론적 무결성을 유지하면서 KV cache를 효과적으로 압축합니다.
Method.
Overall Pipeline.
semantic fragmentation 문제를 해결하면서 KV cache를 압축하기 위해, 3단계의 의미론적 계층 구로를 갖춘 새로운 파이프라인 SemanticCahce를 제안합니다. 그림 1. 에 묘사된 바와 같이, 본 논문의 접근법은 자연어의 delimiters를 경계로 사용하여 기존 KV cache를 의미론적 일관된 chunks로 분할하는 semantic chunking으로 시작합니다.
이어서 각 chunk에 대해 similarity clustering 단계가 수행되며, 이때 GSC 알고리즘을 사용하여 매우 유사한 토큰들을 semantic clusters라 정의한 별도의 세트들로 그룹화합니다. 마지막 clustered merging 단계에서는 각 군집 내의 KV들이 semantic core라고 정의된 형태로 통합됩니다. 최종적으로 압축된 KV cache는 이 semantic cores들과 초기 chunking 단계에서 보존된 원본 delimiters KV를 concat함으로써 구축되며, 이를 통해 의미론적 무결성을 유지하면서 cache 크기를 효과적으로 줄입니다.
Semantic Chunking.
semantic chunking 단계는 KV cache를 의미론적으로 일관된 chunk로 분할하며, 이 chunk들을 자연스러운 언어학적 경계인 delimiters에 align 시킵니다. 이 접근법은 의미적 경계를 깨뜨려 semantic fragmentation을 초래할 수 있는 기존의 고정된 크기 또는 임의의 chunking 기법들과 대조됩니다.
구체적으로, KV cache를 (K, V) = [(k1, v1), (k2, v2) ... (kn, vn)]으로 정의합니다. 여기서 ki와 vi는 각각 cache의 i-th key 및 value 벡터입니다. 미리 정의된 delimiter 토큰들의 집합을 D로 정의하고, delimiter들이 일관되게 높은 attention score를 받는다는 관찰에 영감을 받아, 이것이 구조적 anchor 역할을 하도록 이들에 해당하는 KV 상태를 수정 없이 그대로 보존합니다. chunking 과정은 sequence (K, V)를 구분자가 아닌 chunk와 구분자가 번갈아 나오는 series로 분할합니다:
*Note: delimiter로 구분하는 것이 최선인가? 뭐.. 의미론적 경계를 찾기 위해 별도의 작은 predictor를 돌리거나 복잡한 context 분석 알고리즘을 사용했다면, 압축을 통해 얻는 속도 이득보다 경계를 찾는 데 걸리는 오버헤드가 훨씬 커져서 조금은 coarse-grained한 방법을 사용한거 같습니다. 하지만 delimiter가 없는 데이터(예: 수학 수식, 프로그래밍 코드 등)가 들어오면 chunk의 길이가 매우 길어지며, GSC는 이 chunk내의 sequence length N에 대해서 O(N^2)의 알고리즘이기 때문에, 오버헤드가 매우 커지게 됩니다. 또한 Vision 영역으로 확장도 힘듭니다.
Similarity Clustering.
초기 단계 이후, 각 chunk Cm은 의미론적으로 일관되지만 잠재적으로 중복된 KV 상태들의 그룹을 포함하고 있습니다. similarity clustering의 목적은 의미론적으로 유사한 토큰들을 식별하고 그룹화함으로써, 이러한 chunks들을 더 finer-grained 의미 단위로 분할하는 것입니다.
토큰 간의 semantic affinity를 정량적으로 측정하기 위해, 풍부한 의미 정보가 encoding 되어 있는 keys를 사용합니다. chunk 내의 임의의 두 KV state (ki, vi)와 (kj, vj)에 대하여, 이들의 semantic affinity는 다음과 같이 정의됩니다:
이 metric을 기반으로, 아래의 알고리즘 1에 상세히 기술된 계산 효울적인 GSC 알고리즘을 사용합니다:
GSC는 식 (1)의 각 chunk에 대해 독립적으로 작동합니다. 이 알고리즘은 단 한 번의 sequence pass만을 수행합니다: 아직 할당되지 않은 토큰이 새로운 군집의 seed로 지정됩니다. 그런 다음 이 seed는 자신의 key vector와 semantic affinity가 threshold를 초과하는, 이후의 모든 할당되지 않은 토큰들을 greedy 하게 흡수합니다. 이 과정은 다음으로 사용 가능한 할당되지 않은 토큰이 새로운 시드를 형성하면서 반복되며, chunk 내의 모든 KV가 정확히 하나의 군집에 할당될 때까지 계속됩니다. 이 접근법은 토큰들을 서로 겹치지 않는 군집들로 분할하며 각 군집은 높은 내부적 의미론적 응집성을 보입니다.
*Note: 한 번의 pass만 한다는 것이 O(N)의 시간복잡도를 갖는 다는 얘기는 아닙니다. K-means처럼 clustering을 처음 한 다음에, 다시 처음부터 하는 과정을 반복하지 않고, 한 번의 pass 만으로 clustering을 완료한다는 뜻입니다. 즉 GSC의 시간복잡도는 N^2가 맞습니다.
Clustered Merging.
semantic cluster를 얻은 후, 마지막 단계는 clustering 기반 merging입니다. 단순한 merging 연산은 통합된 token들의 attention 기여도를 희석시킵니다. 이에 대응하기 위해, mean pooling을 통한 대표 벡터 생성과 이들의 영향력을 재조정하는 proportional attention 메커니즘을 적용합니다.
먼저, algorithm 1. 에 의해 생성된 partition Pm 내의 각 cluster St에 대하여, 다음과 같이 mean pooling을 통해 단일 대표 semantic core를 계산합니다:
|St|는 St의 원소 개수를 의미하며, 최종 압축된 KV cache인 (Kc, Vc)는 이 semantic core들을 chunking 단계에서 보존된 delimiter들의 KV와 concat 됨으로써 구성됩니다. 그 후, merging 된 token들의 축소된 atteniton 기여도의 균형을 다시 맞추기 위해 수정된 atteniton을 사용합니다:
여기서 s는 각 cluster의 크기를 포함하는 행 벡터이고, Q는 query 행렬입니다. 수학적으로 softmax 이전에 logits에 log s를 더하는 것은, exponentail operation 이후에 attention score에 s를 곱하는 것과 동일합니다. 이는 merging된 토큰의 기여도가 원래 크기에 비례하도록 보장하며, 그렇지 않을 경우에 발생했을 정보 희석 문제를 효과적으로 방지합니다.
Experiments.
(... 원본 논문 참조 ...)
