🤖 machine learning

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

यह शोध पत्र टोकन अनुक्रमों की अंतर्निहित भाषाई संरचना का लाभ उठाने के लिए संभाव्य भाषा ट्राइज़ (probabilistic language tries) और प्रेडिक्टिव डेल्टा कोडिंग का उपयोग करते हुए एक क्रमिक KV कैश संपीड़न ढांचा प्रस्तावित करता है, जो सैद्धांतिक रूप से टर्बोक्वांट (TurboQuant) जैसे वर्तमान प्रति-वेक्टर क्वांटाइजेशन विधियों की तुलना में क्रमों के परिमाण अधिक संपीड़न अनुपात प्राप्त करता है।

मूल लेखक: Gregory Magarshak

प्रकाशित 2026-04-20

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Gregory Magarshak

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक अति-बुद्धिमान लाइब्रेरियन (AI) हैं जिसने अभी-अभी एक विशाल, 1,00,000 पन्नों की किताब पढ़कर समाप्त की है। अपने अगले प्रश्न का उत्तर देने के लिए, आपको वह सब कुछ याद रखने की आवश्यकता है जो आपने अभी पढ़ा है।

AI की दुनिया में, इस "याददाश्त" को KV Cache कहा जाता है। यह एक विशाल नोटबुक है जहाँ AI उन मुख्य विवरणों (Key और Value वेक्टर्स) को लिखता है जिन्हें उसने हर शब्द को प्रोसेस करते समय सीखा है।

वर्तमान समस्या: "भारी बैकपैक"

अभी, जब भी AI एक शब्द पढ़ता है, वह अपनी नोटबुक में एक नया पूरा पन्ना लिख देता है। भले ही वह शब्द केवल "the" या "and" जैसा हो, वह एक पूरा, विस्तृत पन्ना लिख देता है।

पुराना तरीका (TurboQuant): शोधकर्ताओं ने हाल ही में इन पन्नों को छोटा करने का तरीका खोजा है। 16-बिट फ्लोटिंग पॉइंट में पूर्ण रंग (full color) में लिखने के बजाय, वे इन्हें ब्लैक एंड व्हाइट (3 बिट्स) में लिखते हैं। यह एक शानदार सुधार है, जैसे एक हार्डकवर किताब से पेपरबैक में बदलना।
सीमा: लेकिन इसमें एक पेच है: AI अभी भी हर शब्द के लिए एक नया पन्ना लिख रहा है, भले ही वह शब्द अनुमानित (predictable) हो। यह "The" के लिए एक नया पन्ना लिखने जैसा है, जबकि आप जानते हैं कि अगला शब्द लगभग निश्चित रूप से "cat" या "dog" होगा। आप अभी भी रेडंडेंट (अनावश्यक) पन्नों से भरा एक भारी बैकपैक ढो रहे हैं।

नया विचार: "अनुमानित स्मृति" (Predictive Memory)

यह शोध पत्र तर्क देता है कि AI को हर शब्द के लिए एक नया पन्ना लिखने की आवश्यकता नहीं है। उसे केवल एक नोट लिखने की आवश्यकता है कि क्या बदला है।

लेखक इस मेमोरी को वर्तमान तरीकों की तुलना में लगभग दस लाख गुना कम करने के लिए दो-चरणीय "जादुंतर" का प्रस्ताव देते हैं।

लेयर 1: "साझा कहानी" का तरीका (Probabilistic Prefix Deduplication)

कल्पना कीजिए कि दो लोग बातचीत शुरू कर रहे हैं।

व्यक्ति A: "You are a helpful assistant who loves coding."
व्यक्ति B: "You are a helpful assistant who loves cooking."

वर्तमान AI: दोनों लोगों के लिए पूरा वाक्य लिख देता है। वह देखता है कि "You are a helpful assistant who loves..." अलग है क्योंकि आखिरी शब्द अलग है।
नया AI: यह महसूस करता है कि वाक्य के पहले 90% हिस्से का अर्थ बिल्कुल समान है। वह साझा हिस्से को एक मास्टर नोटबुक में एक बार लिखता है। व्यक्ति A और व्यक्ति B के लिए, वह केवल एक छोटा सा स्टिकी नोट लिखता है: "व्यक्ति A: 'coding' को 'cooking' में बदलें।"

इसे Probabilistic Prefix Deduplication कहा जाता है। यह समान बातचीत को एक साथ समूहबद्ध करता है और केवल अंतरों को संग्रहीत करता है।

लेयर 2: "अनुमान और जाँच" का तरीका (Predictive Delta Coding)

अब, कल्पना कीजिए कि AI एक कहानी पढ़ रहा है: "The sky is..."

वर्तमान AI: "blue" शब्द की पूरी, विस्तृत स्मृति लिख देता है।
नया AI: AI इतना अच्छा पाठक है कि वह पहले से ही जानता है कि अगला शब्द संभवतः "blue" होगा। वह "blue" की स्मृति नहीं लिखता। इसके बजाय, वह एक छोटा सा नोट लिखता है: "मेरा अनुमान 'blue' था, और वास्तविक शब्द 'blue' था। अंतर (residual) शून्य है।"

यदि कोई शब्द चौंकाने वाला आता है, जैसे: "The sky is purple," तो नोट थोड़ा बड़ा होता है: "मेरा अनुमान 'blue' था, लेकिन यह 'purple' था। यहाँ छोटा सा अंतर है।"

इसे Predictive Delta Coding कहा जाता है। पूरी स्मृति को संग्रहीत करने के बजाय, AI केवल अपने स्वयं के अनुमान की त्रुटि (error) को संग्रहीत करता है। चूंकि AI आमतौर पर सही होता है, इसलिए "त्रुटि" बहुत छोटी होती है और बहुत कम जगह लेती है।

यह सब कुछ कैसे बदल देता है

यह शोध पत्र एक चौंका देने वाला गणितीय तथ्य सिद्ध करता है:

पुराना सीमा (Old Limit): आवश्यक स्थान इस बात पर निर्भर करता है कि आप एक एकल शब्द की स्मृति लिखने के लिए कितने "बिट्स" का उपयोग करते हैं। यह प्रति शब्द एक निश्चित लागत है।
नई सीमा (New Limit): आवश्यक स्थान इस बात पर निर्भर करता है कि शब्द कितना आश्चर्यजनक (surprising) है।
- यदि कहानी अनुमानित है (जैसे कि कोई कानूनी अनुबंध या कोड ट्यूटोरियल), तो AI लगभग हमेशा सही होता है। मेमोरी की लागत गिरकर लगभग शून्य हो जाती है।
- यदि कहानी अराजक और आश्चर्यजनक है, तो लागत बढ़ जाती है, लेकिन यह पहले की तुलना में बहुत कम रहती है।

उपमा (Analogy):
पुरानी विधि को एक व्यक्ति के चलने का वीडियो रिकॉर्ड करने के रूप में सोचें। आप हर एक फ्रेम रिकॉर्ड करते हैं, भले ही वे स्थिर खड़े हों।
नई विधि उस वीडियो की तरह है जहाँ आप केवल गति (movement) को रिकॉर्ड करते हैं। यदि व्यक्ति स्थिर खड़ा है, तो आप कुछ भी रिकॉर्ड नहीं करते। यदि वह एक कदम लेता है, तो आप केवल वह कदम रिकॉर्ड करते हैं।

परिणाम

इन दोनों तरीकों को मिलाकर:

अलग-अलग बातचीत के साझा हिस्सों को साझा करना।
केवल उन अंतरों को संग्रहित करना जो AI के अनुमान और वास्तविकता के बीच थे।

लेखक गणना करते हैं कि लंबे, सुसंगत टेक्स्ट के लिए, यह विधि वर्तमान सर्वोत्तम तकनीक की तुलना में मेमोरी को 9,00,000 गुना तक संकुचित कर सकती है।

इससे क्या फर्क पड़ता है?
वर्तमान में, यदि आप चाहते हैं कि एक AI पूरी किताब याद रखे, तो आपको भारी RAM वाले सुपरकंप्यूटर की आवश्यकता होती है। इस नई विधि के साथ, आप उसी AI को लैपटॉप या यहाँ तक कि फोन पर भी चला सकते हैं, क्योंकि मेमोरी का "बैकपैक" इतना हल्का हो जाता है कि उसका वजन लगभग नगण्य हो जाता है।

संक्षेप में: शोध पत्र कहता है, "AI जो जानता है उसे सब कुछ लिखना बंद करें। केवल वही लिखें जिसे AI सही ढंग से अनुमानित नहीं लगा सका। " और चूंकि AI एक जीनियस अनुमान लगाने वाला है, इसलिए आपके पास लिखने के लिए लगभग कुछ भी नहीं बचता है।

यहाँ ग्रेगरी मगरशाक के शोध पत्र "Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

KV (Key-Value) कैश बड़े पैमाने पर ट्रांसफॉर्मर इन्फरेंस (inference) में एक प्राथमिक बाधा (bottleneck) है। $L$ परतों, $H_{head}$ अटेंशन हेड्स, हेड डायमेंशन $d$ , और कॉन्टेक्स्ट लेंथ $n$ वाले मॉडल के लिए, कैश $2LH_{head}dn$ फ्लोटिंग-पॉइंट मानों को संग्रहीत करता है। 128k कॉन्टेक्स्ट वाले 70B-पैरामीटर मॉडल के लिए, इसे FP16 में लगभग 80GB मेमोरी की आवश्यकता होती है, जो अक्सर मॉडल वेट्स (weights) से भी अधिक होती है।

वर्तमान अत्याधुनिक समाधान, जैसे कि TurboQuant, पर-वेक्टर क्वांटाइजेशन (per-vector quantization) पर ध्यान केंद्रित करते हैं। वे प्रत्येक KV वेक्टर को एक वितरण (distribution) के आइसोलेटेड सैंपल के रूप में देखते हैं और उसे प्रत्येक घटक (component) के लिए ~3 बिट्स में कंप्रेस करते हैं। जबकि TurboQuant स्वतंत्र वेक्टर्स के लिए शैनन लिमिट (Shannon limit) के करीब पहुँचता है, यह शोध पत्र तर्क देता है कि यह वास्तविक चुनौती की तुलना में एक "काफी कमजोर समस्या" है: KV कैश को एक अनुक्रम (sequence) के रूप में कंप्रेस करना।

मुख्य अंतर्दृष्टि (The Core Insight): KV वेक्टर्स मनमाने फ्लोटिंग-पॉइंट डेटा नहीं हैं; वे मॉडल द्वारा उत्पन्न टोकन अनुक्रम के नियतात्मक फलन (deterministic functions) हैं। चूंकि मॉडल अपने प्रशिक्षण वाली भाषा का एक लगभग इष्टतम भविष्यवक्ता (near-optimal predictor) है, इसलिए पिछला KV वेक्टर ज्ञात होने पर अगला KV वेक्टर अत्यधिक अनुमानित (predictable) होता है। एक KV वेक्टर की सूचना सामग्री (information content) उसके इतिहास के सापेक्ष उसकी सशर्त एंट्रॉपी (conditional entropy) है, जो इसकी कच्ची एंट्रॉपी (raw entropy) की तुलना में काफी कम है।

2. कार्यप्रणाली: अनुक्रमिक KV संपीड़न (Methodology: Sequential KV Compression)

यह शोध पत्र एक दो-स्तरीय आर्किटेक्चर का प्रस्ताव करता है जो मौजूदा पर-वेक्टर क्वांटाइजेशन विधियों के समानांतर, KV कैश की अनुक्रमिक संरचना का लाभ उठाता है।

स्तर 1: संभाव्य प्रीफ़िक्स डीडुप्लिकेशन (Probabilistic Prefix Deduplication)

लक्ष्य: विभिन्न इन्फरेंस सत्रों (जैसे, समान सिस्टम प्रॉम्प्ट या फ्यू-शॉट उदाहरण साझा करने वाले कई उपयोगकर्ता) के बीच रेडंडेंसी (redundancy) को समाप्त करना।
तंत्र: सटीक स्ट्रिंग मिलान (जैसा कि vLLM/SGLang में उपयोग किया जाता है) के बजाय, यह विधि प्रोबेबिलिस्टिक लैंग्वेज ट्राइज़ (Probabilistic Language Tries - PLTs) का उपयोग करती है।
मीट्रिक: यह ट्राइ (trie) मीट्रिक $d_T(s, s') = -\log_2 P_M(s \land s')$ का उपयोग करता है, जहाँ $s \land s'$ सबसे लंबा सामान्य प्रीफ़िक्स (longest common prefix) है। यह संभाव्यता स्थान (probability space) में दो टोकन अनुक्रमों के बीच "दूरी" को मापता है।
प्रक्रिया:
1. सत्रों को उनके सिमेंटिक साम्य (semantic similarity) के आधार पर क्लस्टर किया जाता है (छोटा ट्राइ डिस्टेंस)।
2. एक सेंट्रॉइड (centroid) (क्लस्टर में सबसे संभावित प्रीफ़िक्स) को पूर्ण रूप में संग्रहीत किया जाता है।
3. क्लस्टर के अन्य सत्र केवल सेंट्रॉइड से विचलन (divergence) के बिंदु से डेल्टा (delta) को संग्रहीत करते हैं।
परिणाम: यह उस रेडंडेंसी को समाप्त करता है जो लेक्सिकल (lexical) रूप से समान न होने पर भी सिमेंटिक रूप से समान होती है।

स्तर 2: प्रेडिक्टिव डेल्टा कोडिंग (Predictive Delta Coding)

लक्ष्य: मॉडल की अपनी स्थिति (state) के आधार पर अगले KV वेक्टर का अनुमान लगाकर एक ही सत्र के भीतर रेडंडेंसी को समाप्त करना।
तंत्र:
1. कैश में $KV_i$ लिखने से पहले, मॉडल अगले टोकन की संभाव्यता वितरण $P_M(t_i | t_{<i})$ के आधार पर अनुमानित KV वेक्टर $\hat{KV}_i$ की गणना करता है।
2. सिस्टम कच्चे वेक्टर के बजाय रेसिडुअल (residual) $R_i = KV_i - \hat{KV}_i$ को संग्रहीत करता है।
एंट्रॉपी बाउंड (Entropy Bound): यह शोध पत्र सिद्ध करता है कि इस रेसिडुअल की एंट्रॉपी अगले टोकन के पर-टोकन सरप्राइज़ल (per-token surprisal) (अगले टोकन की सशर्त एंट्रॉपी) द्वारा सीमित है:
$H(KV_i | KV_{<i}) \leq H(t_i | t_{<i})$
अनुकूली क्वांटाइजेशन (Adaptive Quantization): चूंकि रेसिडुअल्स अनुमानित स्थानों (कम सरप्राइज़ल) पर छोटे और आश्चर्यजनक स्थानों (अधिक सरप्राइज़ल) पर बड़े होते हैं, इसलिए सिस्टम सरप्राइज़ल-अनुकूली क्वांटाइजेशन का उपयोग करता है, जिससे अनुमानित टोकन के लिए कम बिट्स और आश्चर्यजनक टोकनों के लिए अधिक बिट्स आवंटित किए जाते हैं।

संयोजन (Composition)

ये दोनों स्तर ऑर्थोगोनल (orthogonal) हैं और इन्हें TurboQuant जैसे मौजूदा पर-वेक्टर क्वांटाइजर्स के नीचे स्टैक किया जा सकता है। पूर्ण स्टैक इस प्रकार है:

प्रीफ़िक्स डीडुप्लिकेशन (स्तर 1) $\rightarrow$ केवल पूंछ (tail) का डेल्टा संग्रहीत करता है।
प्रेडिक्टिव डेल्टा कोडिंग (स्तर 2) $\rightarrow$ पूंछ के रेसिडुअल को संग्रहीत करता है।
पर-वेक्टर क्वांटाइजेशन (जैसे, TurboQuant) $\rightarrow$ रेसिड्यूअल्स को कंप्रेस करता है।

3. मुख्य योगदान और सैद्धांतिक परिणाम (Key Contributions & Theoretical Results)

A. अनुक्रमिक एंट्रॉपी बाउंड (Theoreom 1)

यह शोध पत्र औपचारिक रूप रूप से सिद्ध करता है कि पिछले सभी KV कैश प्रविष्टियों के दिए जाने पर $i$ -वें KV वेक्टर की सशर्त एंट्रॉपी, मॉडल के प्रति-टोकन सरप्राइज़ल द्वारा ऊपरी रूप से सीमित (upper-bounded) है:
$H(KV_i | KV_{<i}) \leq H(t_i | t_{<i})$

निहितार्थ: 10–20 की पर्प्लेक्सिटी (perplexity) वाले प्रवाहपूर्ण अंग्रेजी टेक्स्ट के लिए, औसत एंट्रॉपी सभी परतों और हेड्स को कवर करते हुए 3.3–4.3 बिट्स प्रति टोकन पोजीशन है।
तुलना: TurboQuant प्रत्येक घटक के लिए ~3 बिट्स संग्रहीत करता है। 128 घटकों वाले हेड, 64 हेड्स और 80 परतों के साथ, TurboQuant प्रति टोकन पोजीशन ~3.93 मिलियन बिट्स का उपयोग करता है। अनुक्रमिक बाउंड ~4.3 बिट्स है।
सैद्धांतिक अनुपात: यह TurboQuant की तुलना में ~914,000× का सैद्धांतिक कंप्रेशन अनुपात प्रदान करता है। एंट्रॉपी फ्लोर पर 1000× के अत्यधिक निराशावादी ओवरहेड के साथ भी, अनुपात ~914× बना रहता है।

B. एसिम्प्टोटिक व्यवहार (Corollary 5)

पर-वेक्टर विधियाँ: मेमोरी लागत एक निश्चित दर पर कॉन्टेक्स्ट लेंथ ( $O(n)$ ) के साथ रैखिक रूप से बढ़ती है।
अनुक्रमिक संपीड़न: जैसे-जैसे कॉन्टेक्स्ट लेंथ $n$ बढ़ता है, मॉडल का प्रेडिक्टिव वितरण अधिक सटीक होता जाता है (सरप्राइज़ल $H(t_i|t_{<i})$ कम हो जाता है)। फलस्वरूप, प्रति टोकन सीमांत लागत (marginal cost per token) घटती जाती है। लंबा-कॉन्टेक्स्ट इन्फरेंस अधिक महंगा होने के बजाय सस्ता हो जाता है।

C. रेट-डिस्टॉर्शन विश्लेषण (Rate-Distortion Analysis)

यह शोध पत्र लॉसलेस (lossy) कंप्रेशन के विश्लेषण को बढ़ाता है, यह दिखाते हुए कि कम-सरप्राइज़ल वाले टोकनों के लिए, रेसिडुअल वेरिएंस इतना छोटा है कि लक्षित डिस्टॉर्शन स्तर प्राप्त करने के लिए शून्य बिट्स की आवश्यकता हो सकती है, जो यूनिफॉर्म क्वांटाइजेशन से कहीं बेहतर प्रदर्शन करता है।

4. व्यावहारिक कार्यान्वयन (Practical Implementation)

शोध पत्र इसे व्यवहार्य बनाने के लिए इंजीनियरिंग चुनौतियों का समाधान करता है:

कुशल भविष्यवाणी (Efficient Prediction): पूरे वोकैबुलरी (vocabulary) पर अपेक्षित KV वेक्टर की गणना करना बहुत महंगा है। लेखक एक Top-k सन्निकटन (approximation) (शीर्ष 20 टोकन का उपयोग करके) या एक लीनियर एम्बेडिंग एप्रोक्सिमेशन का प्रस्ताव करते हैं ताकि नगण्य ओवरहेड के साथ प्रेडिक्टेड KV वेक्टर का अनुमान लगाया जा सके।
एकीकरण (Integration): यह विधि इन्फरेंस लूप में एकीकृत होती है, जो कैश करने से पहले (सोफ्टमैक्स आउटपुट का उपयोग करके) रेसिडुअल की गणना करती है।
ट्राइ इंडेक्स (Trie Index): एक स्पार्स ट्राइ डेटा स्ट्रक्चर कुशल इंसर्शन, नेरेस्ट-नेबर लुकअप (प्रीफ़िक्स डीडुप्लिकेशन के लिए), और इविक्शन (eviction) का समर्थन करता है।

5. महत्व और प्रभाव (Significance and Impact)

मेमोरी वॉल को फिर से परिभाषित करना: यह शोध पत्र तर्क देता है कि मेमोरी वॉल केवल एक हार्डवेयर सीमा नहीं है बल्कि एक सॉफ्टवेयर अवसर भी है। भाषा की अनुक्रमिक रेडंडेंसी विशाल है और वर्तमान में पर-वेक्टर विधियों द्वारा अप्रयुक्त है।
TurboQuant से परे: यह प्रदर्शित करता है कि TurboQuant की "शैनन लिमिट" केवल आइसोलेटेड वेक्टर्स पर लागू होती है। कैश को एक अनुक्रम के रूप में मानकर, वास्तविक सीमा बहुत कम है।
जेवन्स विरोधाभास (Jevons Paradox): लंबे कॉन्टेक्स्ट की सीमांत लागत को नाटकीय रूप से कम करके, यह तकनीक पहले से अव्यवहारिक अनुप्रयोगों (जैसे, रीयल-टाइम मिलियन-टोकन विश्लेषण, निरंतर एजेंट मेमोरी) को सक्षम कर सकती है, जो प्रति-टोकन लागत को कम करते हुए कुल मेमोरी मांग को बढ़ा सकती है।
स्पेक्टेटिव डिकोडिंग के साथ तालमेल: शोध पत्र स्पेक्टेटिव डिकोडिंग और KV प्रेडिक्शन के बीच एक द्वैत (duality) नोट करता है; ड्राफ्टिंग टोकन के लिए उपयोग किए जाने वाले समान top-k वितरण का उपयोग प्रेडिक्टेड KV मीन (mean) की गणना के लिए किया जा सकता है, जिससे दोनों तकनीकें बिना किसी अतिरिक्त इन्फरेंस ओवरहेड के चल सकती हैं।

निष्कर्ष

"Sequential KV Cache Compression" वेक्टर्स को कंप्रेस करने के बजाय वेक्टर्स के अनुक्रम (sequence of vectors) को कंप्रेस करने की ओर एक प्रतिमान बदलाव (paradigm shift) का प्रस्ताव करता है। भाषा की संभाव्य संरचना (PLTs के माध्यम से) और मॉडल की अपनी भविष्यवाणी शक्ति का लाभ उठाकर, यह सैद्धांतिक रूप से वर्तमान अत्याधुनिक क्वांटाइजेशन की तुलना में कई गुना अधिक कंप्रेशन अनुपात प्राप्त करता है, और इसका प्रदर्शन कॉन्टेक्स्ट लेंथ बढ़ने के साथ बेहतर होता जाता है।