💬 NLP

CentroidKV: Efficient Long-Context LLM Inference via KV Cache Clustering

CentroidKV एक सरल लेकिन प्रभावी फ्रेमवर्क है जो चंक्ड सॉफ्ट मैचिंग (chunked soft matching) और सेंट्रॉइड मर्जिंग (centroid merging) का उपयोग करने वाले ऑनलाइन KV कैश क्लस्टरिंग दृष्टिकोण के माध्यम से लॉन्ग-कॉन्टेक्स्ट LLM इन्फरेंस मेमोरी उपयोग को 75% तक कम करता है और डिकोडिंग को 1.92x तक तेज करता है।

मूल लेखक: Jie Hu, Shengnan Wang, Yutong He, Ping Gong, Jiawei Yi, Juncheng Zhang, Youhui Bai, Renhai Chen, Gong Zhang, Cheng Li, Kun Yuan

प्रकाशित 2026-06-16

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

CC BY 4.0

मूल लेखक: Jie Hu, Shengnan Wang, Yutong He, Ping Gong, Jiawei Yi, Juncheng Zhang, Youhui Bai, Renhai Chen, Gong Zhang, Cheng Li, Kun Yuan

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

कल्पना कीजिए कि आप एक बहुत ही महत्वपूर्ण सवाल का जवाब पाने के लिए एक विशाल, 1,00,000 पन्नों के उपन्यास को पढ़ने की कोशिश कर रहे हैं, जो कि बिल्कुल पहले वाक्य के बारे में है। जैसे-जैसे आप पढ़ते हैं, आपका मस्तिष्क स्वाभाविक रूप से हर पात्र, हर सेटिंग और हर कथानक (plot point) को याद रखने की कोशिश करता है। आर्टिफिशियल इंटेलिजेंस की दुनिया में, इस "याददाश्त" को KV Cache कहा जाता है।

समस्या क्या है? जैसे-जैसे कहानी लंबी होती जाती है, यह मेमोरी इतनी विशाल हो जाती है कि यह कंप्यूटर के मस्तिष्क (GPU) को क्रैश कर देती है, जिससे सब कुछ बहुत धीमा हो जाता है। यह एक मैराथन दौड़ते समय अपने बैकपैक में एक पूरी लाइब्रेरी ले जाने जैसा है।

मौजूदा समाधान इसे ठीक करने की कोशिश करते हैं या तो:

पन्ने फेंक देते हैं: वे कहानी के उन हिस्सों को हटा देते हैं जिन्हें वे महत्वहीन समझते हैं। लेकिन कभी-कभी, 50 पन्ने पहले का एक "बोरिंग" पन्ना अंत की कुंजी हो सकता है, जिससे AI भ्रमित हो जाता है।
फॉन्ट छोटा कर देते हैं: वे टेक्स्ट को कंप्रेस (compress) कर देते हैं, लेकिन इससे अक्सर पढ़ना कठिन हो जाता है और पढ़ने की गति धीमी हो जाती है।

CentroidKV इस मेमोरी को संभालने का एक नया, स्मार्ट तरीका है। आइए समझते हैं कि यह कैसे काम करता है, सरल उपमाओं (analogies) का उपयोग करके:

1. "ग्रुप हग" रणनीति (Clustering)

पन्ने हटाने या टेक्स्ट छोटा करने के बजाय, CentroidKV डुप्लिकेट्स (duplicates) को ढूंढता है।

कल्पना कीजिए कि आप 10,000 मेहमानों के साथ एक विशाल पार्टी आयोजित कर रहे हैं। कई मेहमानों ने बिल्कुल एक जैसी लाल शर्ट पहनी है और उनके बाल भी एक जैसे हैं। हर व्यक्ति को व्यक्तिगत रूप से याद रखने के बजाय, CentroidKV कहता है, "अरे, ये 50 लोग मूल रूप से एक जैसे हैं। आइए उन्हें एक साथ समूह में रखें और उन सभी का प्रतिनिधित्व करने के लिए एक 'सुपर-गेस्ट' (centroid) बनाएं।"

यह कैसे काम करता है: AI कहानी को स्कैन करता है और देखता है कि कुछ शब्द या वाक्यांश बहुत समान तरीकों से दिखाई देते हैं। यह इन समान "टोकन" (शब्दों) को एक साथ समूह में रखता है और पूरे समूह को उनके एक एकल, औसत संस्करण (averaged version) से बदल देता है।
परिणाम: आप 10,000 व्यक्तिगत मेहमानों को याद रखने के बजाय केवल कुछ सौ "सुपर-गेस्ट्स" को याद रखते हैं। यह मुख्य कहानी को खोए बिना मेमोरी के आकार को 75% तक कम कर देता है।

2. "चंक्ड" दृष्टिकोण (Chunked Soft Matching)

आप पूछ सकते हैं: "यदि मेरे पास 1,00,000 पन्ने हैं, तो आप उन्हें पढ़ने में बहुत अधिक समय लिए बिना डुप्लिकेट्स कैसे ढूंढते हैं?"

यदि आप हर पन्ने की हर दूसरे पन्ने से तुलना करने की कोशिश करते, तो इसमें बहुत समय लगता। CentroidKV एक चतुर तकनीक का उपयोग करता है जिसे Chunked Soft Matching कहा जाता है।

उपमा: कल्पना कीजिए कि आप कपड़ों के ढेर को छाँट रहे हैं। पूरे घर के हर मोज़े की तुलना हर दूसरे मोज़े से करने के बजाय, आप लॉन्ड्री को छोटे बक्सों (chunks) में विभाजित करते हैं।
रणनीति: प्रत्येक बक्से के अंदर, AI उन मोज़ों को ढूंढता है जो मेल खाते हैं। यह उन्हें जल्दी से जोड़ने के लिए एक विशेष "अल्टरनेटिंग" (alternating) विधि का उपयोग करता है। यह कुछ ऐसा है जैसे कहना, "इस टोकरी में, आइए लाल मोज़ों को नीले मोज़ों के साथ जोड़ें, लेकिन केवल तभी जब वे बहुत समान हों।"
यह तेज़ क्यों है: समस्या को छोटे, प्रबंधनीय टुकड़ों (chunks) में तोड़कर, AI इस ग्रुपिंग को तुरंत कर सकता है, भले ही कहानियाँ बहुत लंबी क्यों न हों।

3. "क्वालिटी कंट्रोल" फ़िल्टर

पेपर नोट करता है कि आप किसी भी दो चीजों को बस यूँ ही आपस में नहीं मिला सकते, अन्यथा आप महत्वपूर्ण विवरण खो देंगे।

उपमा: कल्पना कीजिए कि आप लोगों के एक समूह को मिला रहे हैं। आप एक शेफ को पायलट के साथ केवल इसलिए नहीं मिलाएंगे क्योंकि दोनों ने टोपी पहनी है। आप केवल उन लोगों को मिलाते हैं जो वास्तव में समान हैं।
प्रक्रिया: CentroidKV बहुत चूजी (picky) है। यह केवल उन समूहों को मर्ज करता है जो बहुत, बहुत समान होते हैं (उच्च विश्वास/high confidence)। यदि दो चीजें केवल "कुछ हद तक" समान हैं, तो यह उन्हें अकेला छोड़ देता है। यह आगे बढ़ते हुए और भी सख्त होता जाता है, यह सुनिश्चित करता है कि अंतिम "सुपर-गेस्ट्स" मूल समूह का सटीक प्रतिनिधित्व हैं।

परिणाम: तेज़ और हल्का

क्योंकि अब AI को बहुत छोटा "बैकपैक" (कंप्रेस्ड मेमोरी) ले जाना पड़ता है:

यह तेज़ी से पढ़ता है: इसकी "डिकोडिंग" गति (अगला शब्द बनाना) 1.92 गुना तक तेज़ है।
यह अधिक लोगों को संभालता है: सिस्टम एक ही समय में 4 गुना अधिक उपयोगकर्ताओं को सेवा दे सकता है क्योंकि यह मेमोरी की कमी का सामना नहीं करता है।
यह भूलता नहीं है: मेमोरी को सिकोड़ने के बावजूद, AI लगभग उतना ही अच्छा जवाब देता है जितना कि पूर्ण, अनकंप्रेस्ड मेमोरी के साथ।

यह क्या नहीं करता (सीमाएं)

पेपर ईमानदारी से बताता है कि यह विधि क्या नहीं करती है:

यह हर चीज़ के लिए जादू नहीं है: यदि कहानी बहुत विशिष्ट, रैंडम कोड्स (जैसे एक अद्वितीय ID नंबर जो केवल एक बार दिखाई देता है) पर निर्भर करती है, तो AI उस सटीक विवरण को बनाए रखने में संघर्ष कर सकता है क्योंकि यह समान चीजों को समूह में डाल देता है। यह कहानियों और अर्थों के लिए बहुत अच्छा है, लेकिन सटीक, रैंडम स्ट्रिंग्स को खोजने के लिए उतना परफेक्ट नहीं है।
यह GPU पर ही रहता है: वर्तमान में, यह ग्रुपिंग कंप्यूटर के मुख्य प्रोसेसर पर होती है। लेखक सुझाव देते हैं कि भविष्य में, हम इस ग्रुपिंग को एक धीमे, सस्ते प्रोसेसर (CPU) पर कर सकते हैं और परिणाम को मुख्य प्रोसेसर को भेज सकते हैं, लेकिन उन्होंने अभी तक इसे बनाया नहीं है।

संक्षेप में: CentroidKV एक स्मार्ट लाइब्रेरियन की तरह है जिसे एहसास होता है कि एक विशाल लाइब्रेरी में कई किताबें वास्तव में एक ही कहानी के पुनर्मुद्रण (reprints) हैं। 1,000 कॉपियां रखने के बजाय, वे एक "मास्टर कॉपी" रखते हैं और एक नोट लिखते हैं, "यह 1,000 किताबों का प्रतिनिधित्व करता है।" यह स्थान बचाता है, खोज को तेज़ करता है, और कहानी को बरकरार रखता है।

तकनीकी सारांश: CentroidKV

समस्या विवरण

विस्तारित संदर्भ विंडो (1M टोकन तक) वाले लार्ज लैंग्वेज मॉडल्स (LLMs) को की-वैल्यू (KV) कैश के कारण महत्वपूर्ण परिनियोजन चुनौतियों का सामना करना पड़ता है। KV कैश, जो पुन: गणना (re-computation) से बचने के लिए पिछले टोकन के कीज़ और वैल्यूज़ को संग्रहीत करता है, संदर्भ लंबाई के साथ रैखिक रूप से बढ़ता है। यह अनुमान विलंबता (inference latency) और थ्रूपुट के लिए एक बाधा उत्पन्न करता है, क्योंकि प्रत्येक उत्पन्न टोकन के लिए संपूर्ण कैश तक पहुँचने की आवश्यकता होती है। इसके अलावा, बड़ा मेमोरी फुटप्रिंट परिनियोजन को जटिल बनाता है।

KV कैश आकार को कम करने के लिए मौजूदा समाधानों में शामिल हैं:

इविक्शन (Eviction): अटेंशन स्कोर के आधार पर कम महत्वपूर्ण टोकनों को हटा देना। इससे अक्सर प्रदर्शन में गिरावट आती है क्योंकि जिन्हें शुरू में महत्वहीन माना जाता है, वे भविष्य के जेनरेशन के लिए महत्वपूर्ण हो सकते हैं।
मर्जिंग (Merging): हटाए जाने वाले टोकनों को बनाए रखे गए टोकनों के साथ मिलाना। हालाँकि, मौजूदा विधियाँ अक्सर मर्जिंग सेट्स को परिभाषित करने के लिए प्रारंभिक इविक्शन पर निर्भर करती हैं, जिससे अर्थ संबंधी रूप से दूर स्थित टोकनों को समूहबद्ध करने के परिणामस्वरूप सेंट्रॉइड बायस (centroid bias) और सूचना की हानि होती है।
क्वांटाइजेशन और प्रूनिंग (Quantization and Pruning): ये सीमित दक्षता प्रदान करते हैं या उच्च कम्प्यूटेशनल ओवरहेड पेश करते हैं।

एक ऐसी विधि की आवश्यकता है जो महत्वपूर्ण जानकारी को हटाए बिना या अत्यधिक कम्प्यूटेशनल लागत के बिना, आंतरिक समानता के आधार पर KV कैश को संपीड़ित (compress) कर सके।

कार्यप्रणाली: CentroidKV

यह शोध पत्र एक ऑनलाइन KV कैश क्लस्टरिंग फ्रेमवर्क, CentroidKV प्रस्तुत करता है। इसका मुख्य नवाचार चंक्ड सॉफ्ट मैचिंग (Chunked Soft Matching - CSM) एल्गोरिदम है, जिसे कम कम्प्यूटेशनल जटिलता बनाए रखते हुए समानता के आधार पर KV अवस्थाओं को क्लस्टर करने के लिए डिज़ाइन किया गया है।

मुख्य घटक

अवलोकन (Observations):
- स्थानीयकृत समानता (Localized Similarity): की अवस्थाएं (Key states) अनुक्रम आयाम (sequence dimension) के साथ उच्च कोसाइन समानता प्रदर्शित करती हैं, जहाँ समान टोकन स्थानीय क्षेत्रों में क्लस्टर होते हैं।
- दूरी सहसंबंध (Distance Correlation): जैसे-जैसे टोकन की दूरी बढ़ती है, की अवस्थाओं की कोसाइन समानता आम तौर पर निरंतरता से घटती है और एक उत्तल (convex) प्रवृत्ति का पालन करती है।
अनुमान पाइपलाइन (Inference Pipeline):
- प्री-फिलिंग (Pre-filling): अनुक्रम को प्रोसेस किया जाता है, और यदि KV कैश बजट से अधिक हो जाता है, तो पहला क्लस्टरिंग राउंड निष्पादित किया जाता है।
- डिकोडिंग (Decoding): प्रत्येक टोकन के साथ कैश बढ़ता है। बजट के भीतर कैश बनाए रखने के लिए प्रत्येक $g$ स्टेप्स के बाद क्लस्टरिंग को बुलाया जाता है।
- संरक्षण (Preservation): मॉडल स्थिरता सुनिश्चित करने के लिए विभाजन से पहले अटेंशन सिंक्स (attention sinks) और हाल के टोकनों को संरक्षित किया जाता है।
चंक्ड सॉफ्ट मैचिंग (CSM):
- चंकिंग (Chunking): लंबे संदर्भों को कुशलतापूर्वक संभालने के लिए अनुक्रम को चंक्स में विभाजित किया जाता है।
- अल्टरनेटिंग पार्टीशन (Alternating Partition): प्रत्येक चंक के भीतर, टोकनों को बारी-बारी से दो सेटों ( $A$ और $B$ ) में विभाजित किया जाता है। सैद्धांतिक विश्लेषण सिद्ध करता है कि देखे गए निरंतर और उत्तल समानता रुझानों को देखते हुए यह रणनीति इष्टतम है, जो यह सुनिश्चित करती है कि अत्यधिक समान टोकनों को मिलान की सुविधा के लिए अलग-अलग सेटों में रखा जाए।
- मैचिंग (Matching): विज़न ट्रांसफॉर्मर में उपयोग किए जाने वाले बाइपार्टाइट सॉफ्ट मैचिंग (BSM) के समान, CSM सेट $A$ और $B$ के बीच अत्यधिक समान टोकन जोड़ों की पहचान करता है।
- संपीड़न (Compression): सभी जोड़ों को मर्ज करने के बजाय, एल्गोरिदम समानता के आधार पर उम्मीदवार मैचों को रैंक करता है और केवल शीर्ष अंश को मर्ज करता है जो संपीड़न अनुपात $r$ द्वारा नियंत्रित होता है।
- प्रोग्रेसिव शेड्यूलिंग (Progressive Scheduling): संपीड़न अनुपात $r$ को कई क्लस्टरिंग राउंड में रैखिक रूप से एनेलेट (anneal) किया जाता है ( $r = r_{init} - j \cdot \delta_r$ )। यह मर्जिंग को बाद के राउंड में अधिक चयनात्मक बनाता है, जिससे उच्च-विश्वास वाली संरचनाएं सुरक्षित रहती हैं।
एकत्रीकरण (Aggregation):
- प्रत्येक क्लस्टर के लिए, की और वैल्यू अवस्थाओं को डिग्री-वेटेड एवरेजिंग का उपयोग करके एक एकल सेंट्रॉइड में मर्ज किया जाता है। "डिग्री" ( $n_t$ ) उन टोकनों के संचयी योगदान को ट्रैक करता है जिन्हें विभिन्न राउंड में एक सेंट्रॉइड में मर्ज किया गया है।
- अटेंशन मैकेनिज्म को इन सेंट्रॉइड्स का उपयोग करने के लिए अनुकूलित किया जाता है, जिसमें मूल अटेंशन आउटपुट का अनुमान लगाने के लिए क्लस्टर डिग्री को सॉफ्टमैक्स गणना में एक लॉग-टर्म के रूप में शामिल किया जाता है।

मुख्य योगदान

CentroidKV फ्रेमवर्क: एक सरल, प्लग-एंड-प्ले समाधान जो लंबे संदर्भ परिदृश्यों में अनुमान दक्षता में सुधार करता है।
चंक्ड सॉफ्ट मैचिंग एल्गोरिदम: एक नवीन क्लस्टरिंग एल्गोरिदम जो KV कैश संपीड़न के लिए बाइपार्टाइट सॉफ्ट मैचिंग का विस्तार करता है। यह चंक्स के भीतर एक अल्टरनेटिंग पार्टीशन रणनीति का उपयोग करता है, जो देखे गए समानता पैटर्न के लिए सैद्धांतिक रूप से इष्टतम सिद्ध हुआ है।
सैद्धांतिक विश्लेषण: पेपर इंट्रा-चंक पार्टीशनिंग रणनीति की इष्टतमता का औपचारिक प्रमाण प्रदान करता है और कम्प्यूटेशनल जटिलता का विश्लेषण करता है, यह प्रदर्शित करते हुए कि CSM, K-Means ($O(inkd) $) या पूर्ण पेयरवाइज मेश विधियों ($ O(n^2d) $) की तुलना में कम जटिलता ($ O(ncd)$) प्राप्त करता है।
अनुभवजन्य सत्यापन (Empirical Validation): RULER और LongBench बेंचमार्क पर Llama-3.1-8B और Mistral-7B मॉडल्स पर व्यापक प्रयोग।

परिणाम

मेमोरी दक्षता: CentroidKV मॉडल के प्रदर्शन को बनाए रखते हुए KV कैश मेमोरी उपयोग में 75% तक की कमी (कैश आकार को ~4x कम करना) प्राप्त करता है।
अनुमान गति (Inference Speed):
- डिकोडिंग विलंबता (Decoding Latency): यह डिकोडिंग चरण को 1.92× तक तेज करता है (Time Per Output Token में कमी के रूप में मापा गया)।
- थ्रूपुट (Throughput): vLLM फ्रेमवर्क में एकीकृत होने पर सर्विसिंग थ्रूपुट को 4× तक बढ़ाता है।
सटीकता (Accuracy):
- RULER बेंचमार्क पर, CentroidKV विभिन्न कैश बजटों (25%–75%) में सर्वश्रेष्ठ या निकटतम-सर्वश्रेष्ठ प्रदर्शन प्राप्त करता है, विशेष रूप से उन कार्यों पर जिनमें अर्थ संबंधी समझ (जैसे S-NIAH-1/2, MK-NIAH-1, VT) की आवश्यकता होती है।
- LongBench पर, यह Single-Doc QA, Multi-Doc QA और Summarization पर लगातार अच्छा प्रदर्शन करता है।
- सीमाएँ: सिंथेटिक कार्यों और सूक्ष्म-स्तर के रिट्रीवल कार्यों (जैसे UUID-आधारित कुंजियाँ) पर प्रदर्शन थोड़ा गिर जाता है जहाँ सटीक टोकन मिलान महत्वपूर्ण होता है। लेखक नोट करते हैं कि कंटेंट-अवेयर विधियाँ आमतौर पर स्ट्रीमिंगLLM जैसे पोजीशन-आधारित तरीकों की तुलना में अर्थहीन रैंडम स्ट्रिंग्स के साथ संघर्ष करती हैं।

महत्व और दावे

पेपर का दावा है कि CentroidKV सटीकता और दक्षता के बीच एक अनुकूल संतुलन प्रदान करता है। की अवस्थाओं की अंतर्निहित समानता का लाभ उठाकर और एक हल्के, सिंगल-पास क्लस्टरिंग एल्गोरिदम का उपयोग करके, यह नैव इविक्शन (naive eviction) से जुड़ी प्रदर्शन गिरावट और K-Means जैसी पुनरावृत्त क्लस्टरिंग विधियों के उच्च कम्प्यूटेशनल ओवरहेड से बचता है।

लेखक इस बात पर जोर देते हैं कि CentroidKV एक हल्का, प्लग-एंड-प्ले समाधान है जिसके लिए मॉडल रिट्रेनिंग की आवश्यकता नहीं है। यह प्रभावी रूप से लंबे-संदर्भ वाले LLMs की मेमोरी बाधा को संबोधित करता है, जिससे मॉडल की लंबी-दूरी की निर्भरताओं को समझने की क्षमता से समझौता किए बिना तेज़ डिकोडिंग और उच्च थ्रूपुट सक्षम होता है।

लेखकों द्वारा नोट की गई सीमाएँ:

वर्तमान कार्यान्वयन GPU-आधारित संपीड़न पर केंद्रित है और मेमोरी ऑफलोडिंग रणनीतियों (जैसे CPU क्लस्टरिंग) का अन्वेषण नहीं करता है।
संपीड़न अनुपात शेड्यूल मैन्युअल रूप से निर्दिष्ट किया गया है, और विधि प्रत्येक चरण में कैश को अधिकतम आधे तक कम करने को प्रतिबंधित करती है। भविष्य के कार्य अनुकूली (adaptive) संपीड़न रणनीतियों का पता लगा सकते हैं।