📊 statistics

WildCat: Near-Linear Attention in Theory and Practice

WildCat एक उच्च-सटीक, कम-लागत वाली अटेंशन कम्प्रेशन विधि है जो रैंडमली पिवोटेड चोलेस्की सबसैंपलिंग के माध्यम से एक छोटे कोरेसेट (coreset) का चयन और उसे भारित करके लगभग रैखिक समय जटिलता (near-linear time complexity) और सुपर-पॉलीनोमियल एरर डिके (super-polynomial error decay) प्राप्त करती है, जो इमेज और लैंग्वेज टास्क में सैद्धांतिक गारंटी और व्यावहारिक प्रदर्शन दोनों में पूर्ववर्ती एप्रोक्सिमेशन से बेहतर प्रदर्शन करती है।

मूल लेखक: Tobias Schröder, Lester Mackey

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

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

CC BY 4.0

मूल लेखक: Tobias Schröder, Lester Mackey

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

कल्पना कीजिए कि आप अपने एक दोस्त के साथ हुई घंटों लंबी बातचीत को याद करने की कोशिश कर रहे हैं। एक मानक AI मॉडल (जैसे आज के चैटबॉट्स को चलाने वाले मॉडल) में, उस पूरी बातचीत के हर एक शब्द को एक साथ याद रखने की कोशिश करना वैसा ही है जैसे एक नई किताब लिखने के साथ-साथ अपने दिमाग में किताबों के एक पूरे पुस्तकालय को समाहित करने की कोशिश करना। आप जितने अधिक शब्द जोड़ते जाएंगे, यह उतना ही कठिन होता जाएगा, और इसके लिए आवश्यक मेमोरी क्वाड्रेटिकली (quadraticly) बढ़ती जाती है। इसका मतलब है कि यदि आप बातचीत की लंबाई को दोगुना करते हैं, तो इसे याद करने का प्रयास केवल दोगुना नहीं होता; बल्कि चार गुना हो जाता है। अंततः, कंप्यूटर की मेमोरी खत्म हो जाती है या उसे सोचने में बहुत लंबा समय लग जाता है।

यह शोध पत्र एक नई विधि पेश करता है जिसे WILDCAT (Weighted Iterative Low-rank Decomposition for Coreset ATtention) कहा जाता है ताकि इस समस्या को हल किया जा सके। यह कैसे काम करता है, इसके लिए सरल उपमाओं का उपयोग यहाँ दिया गया है:

समस्या: "लाइब्रेरी" की बाधा

लाइब्रेरी के रूप में AI की मेमोरी को एक विशाल पुस्तकालय की तरह समझें। जब AI को किसी प्रश्न का उत्तर देने की आवश्यकता होती है, तो उसे आमतौर पर प्रासंगिक जानकारी खोजने के लिए हर एक किताब (बातचीत के हर शब्द) को स्कैन करना पड़ता है।

पुराना तरीका: यदि लाइब्रेरी में 1,000 किताबें हैं, तो AI 1,000 किताबें चेक करता है। यदि लाइब्रेरी बढ़कर 10,000 किताबें हो जाती है, तो AI को 10,000 किताबें चेक करनी पड़ती हैं, लेकिन उन्हें आपस में जोड़ने का प्रयास विस्फोट की तरह बढ़ता है। यह घास के ढेर में सुई खोजने जैसा है, जहाँ आपको हर एक तिनके की तुलना दूसरे हर तिनके से करनी पड़ती है।

समाधान: "विशेषज्ञ पैनल" (WILDCAT)

WILDCAT रणनीति बदल देता है। सब कुछ पूरी तरह से याद रखने के बजाय, यह समझता है कि बातचीत का हर शब्द समान रूप से महत्वपूर्ण नहीं होता है। कुछ शब्द महत्वपूर्ण होते हैं, जबकि अन्य केवल 'फिलर' (बेकार के शब्द) होते हैं।

WILDCAT दो मुख्य कार्य करता है:

"कोर्सेट" (विशेषज्ञ पैनल) का चयन करना:
कल्पना कीजिए कि आपके पास 10,000 लोगों की एक विशाल भीड़ है, और आपको कमरे के सामान्य मिजाज (mood) को जानने की आवश्यकता है। हर किसी का साक्षात्कार लेने के बजाय, WILDCAT एक चतुर और तेज़ एल्गोरिदम (जिसे "रैंडमली पिवोटेड चोलेस्की" कहा जाता है) का उपयोग करके एक बहुत छोटे, प्रतिनिधि समूह को चुनता है, मान लीजिए 50 लोग।
- जादू: यह उन्हें केवल रैंडम तरीके से नहीं चुनता; यह उन सबसे महत्वपूर्ण लोगों को चुनता है जो पूरे समूह का सबसे अच्छा प्रतिनिधित्व करते हैं। यह एक शहर के सबसे मुखर और विविध सदस्यों को चुनने जैसा है ताकि वे एक परिषद बना सकें जो सभी की ओर से बोल सके।
आवाजों को भार देना (Weighting the Voices):
एक बार जब इसके पास यह छोटा समूह 50 लोगों का हो जाता है, तो WILDCAT उन सभी के साथ समान व्यवहार नहीं करता है। यह उन्हें "वेट्स" (भार) प्रदान करता है।
- उपमा: यदि इस छोटे समूह में एक व्यक्ति बहुत मुखर और प्रभावशाली नेता है, तो उसकी आवाज़ का महत्व अधिक होगा। यदि कोई दूसरा शांत है, तो उसकी आवाज़ का महत्व कम होगा। WILDCAT इन 50 लोगों में से प्रत्येक के लिए सही "वॉल्यूम" (आवाज़ का स्तर) की गणना करता है ताकि जब आप केवल उन्हें सुनें, तो यह बिल्कुल वैसा ही लगे जैसे आपने 10,000 लोगों की पूरी भीड़ को सुना हो।

यह एक बड़ी उपलब्धि क्यों है

शोध पत्र का दावा है कि WILDCAT तीन प्रमुख सफलताएं प्राप्त करता है:

गति (लगभग लीनियर): क्योंकि यह पूरी भीड़ के 10,000 लोगों के बजाय केवल 50 लोगों के छोटे समूह को सुनता है, इसलिए सोचने में लगने वाला समय बहुत धीरे बढ़ता है। यदि आप बातचीत की लंबाई को दोगुना करते हैं, तो समय केवल थोड़ा सा ही बढ़ता है, बहुत अधिक नहीं। यह एक किताब के हर पन्ने को पढ़ने के बजाय उसके एक अत्यधिक सटीक सारांश को पढ़ने जैसा है।
सटीकता (सुपर-पॉलीनोमियल): आमतौर पर, जब आप किसी चीज़ का सारांश बनाते हैं, तो आप विवरण खो देते हैं। WILDCAT विशेष है क्योंकि यह दावा करता है कि यह लगभग कोई भी महत्वपूर्ण विवरण नहीं खोता है। शोध पत्र गणितीय रूप से सिद्ध करता है कि जैसे-जैसे बातचीत लंबी होती जाती है, त्रुटि (छूटे हुए विवरण) अविश्वसनीय रूप से तेजी से कम होती जाती है—यह वर्तमान में उपयोग की जाने वाली लगभग किसी भी अन्य विधि से तेज़ है।
व्यावहारिकता: लेखकों ने केवल गणित नहीं किया; उन्होंने शक्तिशाली कंप्यूटर चिप्स (GPUs) पर इसका एक कामकाजी संस्करण बनाया। उन्होंने इसका परीक्षण किया:
- इमेज बनाना: इसने अन्य तरीकों की तुलना में उच्च गुणवत्ता वाली छवियां तेज़ी से बनाईं बिना उन्हें धुंधला या अजीब बनाए।
- इमेज क्लासिफिकेशन: इसने तस्वीरों में वस्तुओं को पहचानना उतनी ही अच्छी तरह से किया जितना कि पूर्ण, धीमी विधि ने किया, लेकिन बहुत तेज़ी से।
- लंबी बातचीत: इसने एक लैंग्वेज मॉडल को चैट के बहुत लंबे इतिहास को याद रखने की अनुमति दी बिना मेमोरी खत्म हुए, और अन्य "मेमोरी कंप्रेशन" तकनीकों की तुलना में बेहतर प्रदर्शन किया।

निचोड़

WILDCAT एक सुपर-कुशल सचिव की तरह है जो 10 घंटे की बैठक को सुन सकता है, तुरंत 50 सबसे महत्वपूर्ण क्षणों को चुन सकता है, उन्हें महत्व का सही स्तर दे सकता है, और फिर पूरी बैठक का इतना सटीक सारांश बना सकता है कि बॉस को ऐसा महसूस हो कि उन्होंने सब कुछ सुना है, लेकिन सचिव को केवल कुछ पन्ने ही लिखने पड़े।

यह AI मॉडल्स को सुपर-कंप्यूटरों की आवश्यकता के बिना बहुत लंबी बातचीत और बड़े कार्यों को संभालने की अनुमति देता है, जिससे वे तेज़, सस्ते और अधिक संदर्भ (context) याद रखने में सक्षम बनते हैं।

तकनीकी सारांश: WILDCAT: सिद्धांत और व्यवहार में नियर-लीनियर अटेंशन (Near-Linear Attention)

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

अटेंशन मैकेनिज्म आधुनिक ट्रांसफॉर्मर-आधारित आर्किटेक्चर का एक आधार स्तंभ है, जो अनुक्रमों (sequences) में दीर्घ-रेंज डिपेंडेंसीज़ को मॉडल करने में सक्षम बनाता है। हालाँकि, इसकी तैनाती अत्यधिक महंगी है क्योंकि इसके संसाधन आवश्यकताएँ इनपुट सीक्वेंस की लंबाई $n$ के साथ द्विघाती ( $\Theta(n^2d)$ ) रूप से बढ़ती हैं। जबकि कई अनुमानित (approximate) अटेंशन विधियाँ मौजूद हैं, एक महत्वपूर्ण अंतर बना हुआ है:

व्यावहारिक सन्निकटन (Practical approximations) (जैसे Reformer, Performer, ScatterBrain) अक्सर कठोर त्रुटि गारंटी (error guarantees) की कमी रखते हैं या उच्च निष्ठा सुनिश्चित करने के लिए द्विघाती रनटाइम की आवश्यकता होती है।
सैद्धांतिक प्रगति (जैसे Alman & Song, 2023) दर्शाती है कि बाउंडेड इनपुट्स के लिए सुपर-पॉलीनोमियल एरर डिके (super-polynomial error decay) के साथ नियर-लीनियर समय ( $O(n^{1+o(1)})$ ) संभव है, लेकिन मौजूदा व्यावहारिक कार्यान्वयन या तो नियर-लीनियर समय में इस डिके को प्राप्त करने में विफल रहते हैं या इसे सुनिश्चित करने के लिए द्विघाती समय की आवश्यकता होती है।

यह शोध पत्र एक ऐसे दृष्टिकोण की आवश्यकता को पहचानता है जो एक साथ कम्प्यूटेशनल रूप से कुशल (नियर-लीनियर टाइम), स्पेक्ट्रल रूप से सटीक (सुपर-पॉलीनोमियल एरर डिके), और आधुनिक हार्डवेयर पर व्यावहारिक रूप से लागू करने योग्य हो।

कार्यप्रणाली (Methodology)

लेखक WILDCAT (Weighted Iterative Low-rank Decomposition for Coreset ATtention) पेश करते हैं, जो इनपुट कीज़ (keys) के एक छोटे, भारित कोसेसेट (weighted coreset) पर ध्यान केंद्रित करके सॉफ्टमैक्स अटेंशन मैकेनिज्म का सन्निकटन करता है। इसकी कार्यप्रणाली तीन मुख्य घटकों से बनी है:

1. रैंडमली पिवोटेड चोलेस्की (Randomly Pivoted Cholesky - RPC) के माध्यम से भारित कोसेसेट चयन

सभी $n$ कीज़ पर ध्यान केंद्रित करने के बजाय, WILDCAT $r$ कीज़ ( $r \ll n$ ) का एक उपसमूह चुनता है ताकि एक कोसेसेट $K_S$ बनाया जा सके।

एल्गोरिदम: चयन प्रक्रिया एक समानांतर (parallelized) रैंडमली पिवोटेड चोलेस्की (RPC) एल्गोरिदम का उपयोग करती है (Chen et al., 2022a से अनुकूलित)। यह एल्गोरिदम कर्नेल मैट्रिक्स $H = \exp(\beta K K^\top)$ का एक आंशिक चोलेस्की अपघटन (partial Cholesky decomposition) बनाता है।
पिवोटिंग नियम: प्रत्येक पुनरावृत्ति (iteration) में, वर्तमान अवशिष्ट कर्नेल मैट्रिक्स (residual kernel matrix) के विकर्ण (diagonal) से एक पिवोट इंडेक्स चुना जाता है। यह सुनिश्चित करता है कि चयनित बिंदु पूर्ण डेटासेट के स्पेक्ट्रल रूप से प्रतिनिधि हों।
दक्षता: चयन $O(nr^2)$ समय में चलता है। GPU थ्रूपुट को अधिकतम करने के लिए, लेखक एक डिवाइड-एंड-कॉन्कर रणनीति का उपयोग करते हैं, जो इनपुट को $B$ बिन्स में विभाजित करती है और उन्हें समानांतर में प्रोसेस करती है, जिससे रनटाइम घटकर $O(nr^2/B^3 + nrd/B^2)$ हो जाता है।

2. निस्ट्रॉम सन्निकटन (Nyström Approximation) के माध्यम से इष्टतम रीवेटिंग

एक बार कोसेसेट $K_S$ चुने जाने के बाद, यह विधि अटेंशन मैट्रिक्स के पुनर्निर्माण त्रुटि (reconstruction error) को कम करने के लिए इष्टतम भार (weights) की गणना करती है।

निस्ट्रॉम वेट्स (Nyström Weights): वेट्स $W$ को निस्ट्रॉम विधि का उपयोग करके प्राप्त किया जाता है: $W = h(K_S, K_S)^+ h(K_S, K)$ । यह पूर्ण कर्नेल फीचर्स को अनुमानित करने के लिए कोसेसेट फीचर्स का इष्टतम रैखिक संयोजन प्रदान करता है।
वैल्यू कम्प्रेशन (Value Compression): वैल्यू मैट्रिक्स $V$ को $V_S = WV$ के रूप में संकुचित किया जाता है, जिससे अंतिम अटेंशन आउटपुट को केवल $r$ कोसेसेट तत्वों का उपयोग करके कंप्यूट किया जा सकता है।

3. इनवेरिएंस और रीस्केलिंग (Invariance and Rescaling)

लेखक कीज़ के ग्लोबल रीसेंटरिंग और कीज़ एवं क्वेरीज़ के रीस्केलिंग के तहत सॉफ्टमैक्स अटेंशन की इनवेरिएंस का लाभ उठाते हैं।

रीसेंटरिंग (Recentering): कीज़ को उनका माध्य घटाकर रीसेंटर किया जाता है ( $K \leftarrow K - \bar{k}$ )।
टेम्परेचर स्केलिंग (Temperature Scaling): एक क्लोज्ड-फॉर्म रीस्केलिंग पैरामीटर $\tau$ निकाला जाता है जो कर्नेल मैट्रिक्स को लो-रैंक अनुमान योग्य बनाने ( $\tau$ को बढ़ाकर) और क्वेरी-आधारित एरर इन्फ्लेशन फैक्टर को न्यूनतम करने के बीच संतुलन बनाता है। यह पैरामीटर लैम्बर्ट-डब्ल्यू (Lambert-W) फंक्शन और क्वेरीज़ एवं कीज़ के नॉर्म्स पर निर्भर करता है।

मुख्य योगदान (Key Contributions)

यह शोध पत्र WILDCAT के लिए निम्नलिखित वांछनीय गुणों को स्थापित करता है:

नियर-लीनियर रनटाइम: WILDCAT सटीक अटेंशन की द्विघाती लागत से बचता है। $r \in n^{o(1)}$ आकार के कोसेसेट पर ध्यान केंद्रित करके, एल्गोरिदम नियर-लीनियर टाइम $O(n^{1+o(1)})$ में चलता है।
सुपर-पॉलीनोमियल एरर डिके: बाउंडेड इनपुट धारणाओं के तहत, WILDCAT $O(n^{-\sqrt{\log(\log(n))}})$ के सुपर-पॉलीनोमियल एरर डिके के साथ सटीक अटेंशन का सन्निकटन करता है। यह नियर-लीनियर रनटाइम बनाए रखते हुए प्राप्त किया गया है, जो एक ऐसी उपलब्धि है जिसे पिछले व्यावहारिक सन्निकटन बिना द्विघाती समय के प्राप्त नहीं कर सके थे।
वृद्धि के प्रति मजबूती (Robustness to Growth): सैद्धांतिक विश्लेषण (Corollary 2) दिखाता है कि WILDCT तब भी सुपर-पॉलीनोमियल एरर डिके बनाए रखता है जब इनपुट एंट्रीज़ या डाइमेंशन्स $n$ के साथ सुपर-लॉगारिदमिक रूप से बढ़ते हैं, जो अटेंशन के लिए पूर्ववर्ती कम्प्यूटेशनल हार्डनेस परिणामों की सीमाओं से आगे जाता है।
KV कैश कंप्रेशन: यह विधि एक COMPRESSKV मॉड्यूल शामिल करती है जो KV कैश के मेमोरी फुटप्रिंट को लीनियर $\Theta(nd)$ से बदलकर नियर-कांस्टेंट $O(rd)$ कर देती है, जिससे लॉन्ग-कॉन्टेक्स्ट इन्फरेंस सुलभ होता है।
व्यावहारिक कार्यान्वयन: लेखक एक GPU-अनुकूलित PyTorch कार्यान्वयन प्रदान करते हैं, जो सैद्धांतिक स्पेक्ट्रल गारंटी और वास्तविक प्रदर्शन के बीच के अंतर को पाटता है।

प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने तीन डोमेन में WILDCAT का मूल्यांकन किया:

इमेज जनरेशन (BigGAN): WILDCAT ने सटीक अटेंशन की तुलना में 4.33× स्पीड-अप प्राप्त किया। इसने इनसेप्शन स्कोर (Inception Score) में सबसे कम गिरावट (1.22%) और इमेजनेट वैलिडेशन सेट की तुलना में फ्रैचे इनसेप्शन डिस्टेंस (FID) में शून्य गिरावट प्रदर्शित की, जिसने Reformer, Performer, KDEformer और Thinformer को पीछे छोड़ दिया।
इमेज क्लासिफिकेशन (T2T-ViT): इमेजनेट क्लासिफिकेशन बेंचमार्क पर, WILDCAT ने सभी सन्निकटनों में उच्चतम औसत टॉप-1 सटीकता (82.19%, सटीक अटेंशन के 82.55% की तुलना में) प्राप्त की। इसने कम्प्यूटेशनल रूप से प्रभावी पहले लेयर के लिए 11.59× स्पीड-अप प्रदान किया।
लॉन्ग-कॉन्टेक्स्ट लैंग्वेज मॉडल्स (KV कैश कंप्रेशन): Qwen2.5-7B-Instruct मॉडल का उपयोग करते हुए 13 LongBench-E कार्यों पर, WILDCAT (COMPRESSKV के माध्यम से) विभिन्न कंप्रेशन स्तरों (75%, 87.5%, 93.75%) में औसत कंप्रेशन गुणवत्ता के मामले में पांच अग्रणी KV कैश कंप्रेशन विधियों (StreamingLLM, PyramidKV, और SnapKV सहित) से लगातार बेहतर रहा।
FlashAttention 2 के साथ तुलना: FlashAttention 2 के विरुद्ध बेंचमार्क दिखाते हैं कि जैसे-जैसे सीक्वेंस की लंबाई बढ़ती है ( $2^{13}$ से $2^{18}$ तक), WILDCAT का स्पीड-अप 1.1× से बढ़कर 68× हो जाता है, जबकि अनुमानित त्रुटि (approximation error) लगातार कम होती जाती है।

महत्व और दावे (Significance and Claims)

यह शोध पत्र अटेंशन एप्रोक्सिमेशन में थ्योरी-प्रैक्टिस गैप को सफलतापूर्वक पाटने का दावा करता है।

सैद्धांतिक सफलता: यह सिद्ध करता है कि व्यावहारिक, बाउंडेड इनपुट्स के लिए नियर-लीनियर टाइम में सुपर-पॉलीनोमियल एरर डिके प्राप्त करना संभव है, जो एक ऐसा सिद्धांत था जो पहले केवल सैद्धांतिक था या जिसके लिए द्विघाती रनटाइम की आवश्यकता थी।
व्यावहारिक उपयोगिता: यह पद्धति केवल एक सैद्धांतिक संरचना नहीं है; इसे कुशलतापूर्वक GPU पर लागू किया गया है और जनरेशन, क्लासिफिकेशन और लैंग्वेज अंडरस्टैंडिंग के लिए स्टेट-ऑफ-द-आर्ट मॉडल्स पर मान्य किया गया है।
स्केलेबिलिटी: KV कैश मेमोरी आवश्यकताओं को नियर-कांस्टेंट आकार तक कम करके, WILDCAT रिसोर्स-कंस्ट्रेंड हार्डवेयर पर लॉन्ग-कॉन्टेक्स्ट लैंग्वेज मॉडल्स की तैनाती को सक्षम बनाता है।

लेखक सीमाओं का उल्लेख करते हैं, विशेष रूप से कि वर्तमान कार्य कॉज़ल मास्किंग (causal masking) के साथ स्ट्रीमिंग जनरेशन को संबोधित नहीं करता है (हालांकि वे सुझाव देते हैं कि प्रिफिक्स सम या डिवाइड-एंड-कॉन्कर के माध्यम से विस्तार संभव है) और RPC में पिवोट चयन की क्रमिक (sequential) प्रकृति को भविष्य के कार्य में ओवरसैंपलिंग तंत्र के माध्यम से सुधारा जा सकता है।