💬 NLP

Training Tensor Attention Efficiently: From Cubic to Almost Linear Time

यह शोध पत्र यह प्रदर्शित करता है कि टेंसर अटेंशन (tensor attention) के बैकवर्ड ग्रेडिएंट को एक क्लोज्ड-फॉर्म समाधान और बहुपद सन्निकटन (polynomial approximation) एवं टेंसर बीजगणित पर आधारित एक तेज़ एल्गोरिदम प्रदान करके लगभग रैखिक समय में संगणित किया जा सकता है, जबकि यह भी सिद्ध करता है कि बाउंडेड एंट्री धारणाओं (bounded entry assumptions) के तहत यह दक्षता सटीक (tight) है।

मूल लेखक: Yang Cao, Yingyu Liang, Zhenmei Shi, Zhao Song

प्रकाशित 2026-01-27

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

CC BY 4.0

मूल लेखक: Yang Cao, Yingyu Liang, Zhenmei Shi, Zhao Song

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

कल्पना कीजिए कि आप एक सुपर-स्मार्ट रोबोट को दुनिया को समझना सिखाने की कोशिश कर रहे हैं। वर्तमान में, सबसे अच्छे रोबोट (जैसे चैटबॉट्स और इमेज जनरेटर को चलाने वाले) एक टूल का उपयोग करते हैं जिसे "अटेंशन" (Attention) कहा जाता है, ताकि यह पता लगाया जा सके कि सूचना के विभिन्न हिस्से एक-दूसरे से कैसे संबंधित हैं।

मानक अटेंशन (Standard Attention) को एक दो-व्यक्ति संवाद की तरह समझें। यह एक शब्द (एक "क्वेरी") को देखता है और पूछता है, "मुझे इस दूसरे शब्द (एक "की") की कितनी परवाह है?" यह एक बार में दो बिंदुओं को जोड़ता है। यह सरल वाक्यों के लिए बहुत अच्छा काम करता है, लेकिन जब आपको तीन या अधिक चीजों को एक साथ जोड़ने वाली जटिल संबंधों को समझने की आवश्यकता होती है—जैसे कि एक दृश्य को समझने के लिए ध्वनि, एक छवि और एक टेक्स्ट विवरण को एक साथ जोड़ना—तो यह संघर्ष करता है।

इसे ठीक करने के लिए, वैज्ञानिकों ने "टेन्सर अटेंशन" (Tensor Attention) का आविष्कार किया।

उपमा: दो-व्यक्ति संवाद के बजाय, एक तीन-तरफा (या बहु-तरफा) कॉन्फ्रेंस कॉल की कल्पना करें। टेन्सर अटेंशन रोबोट को एक ही समय में तीन या अधिक सूचनाओं को देखने और छिपे हुए पैटर्न खोजने की अनुमति देता है। यह जटिल, बहु-आयामी डेटा को समझने के लिए बहुत अधिक शक्तिशाली है।

बड़ी समस्या: "ट्रैफिक जाम"

एक बहुत बड़ी बाधा थी: जबकि मानक अटेंशन तेज़ था (जैसे एक साइकिल), टेन्सर अटेंशन अविश्वसनीय रूप से धीमा था (जैसे ट्रैफिक में फंसा एक भारी ट्रक)।

गणित: यदि आपके पास $n$ शब्दों वाला एक वाक्य है, तो मानक अटेंशन $n^2$ के अनुपात में समय लेता है (जैसे शब्दों के हर जोड़े की जाँच करना)। टेन्सर अटेंशन, क्योंकि यह शब्दों के हर तिहरे (triple) की जाँच करता है, $n^3$ के अनुपात में समय लेता था।
परिणाम: यदि आप इसे एक लंबे दस्तावेज़ पर आज़माते, तो कंप्यूटर सीखने में बहुत लंबा समय लेता। इसे प्रशिक्षित करना बहुत महंगा था, इसलिए कोई वास्तव में इसका उपयोग नहीं कर सकता था।

सफलता: "फास्ट लेन"

यह पेपर दावा करता है कि उन्होंने टेन्सर अटेंशन को एक फास्ट लेन में डालने का तरीका खोज लिया है, जिससे यह लगभग मानक संस्करण जितना तेज़ हो गया है।

उन्होंने इसे कैसे किया, इसके लिए सरल उपमाओं का उपयोग किया गया है:

"स्मूथ एप्रोक्सिमेशन" (Smooth Approximation) का तरीका:
टेन्सर अटेंशन के पीछे का गणित एक बहुत ही ऊबड़-खाबड़, जटिल वक्र (जैसे रोलरकोस्टर) से जुड़ा है जिसे सटीक रूप से कैलकुलेट करना कठिन है। लेखकों ने महसूस किया कि यदि हम यह मान लें कि शामिल संख्याएँ बहुत बड़ी नहीं हैं (एक "बाउंडेड एंट्रीज़" धारणा), तो आप उस ऊबड़-खाबड़ रोलरकोस्टर को एक स्मूथ, सरल बहुपद वक्र (जैसे एक हल्की पहाड़ी) से बदल सकते हैं।

उपमा: एक पहाड़ी रास्ते के सटीक, ऊबड़-खाबड़ पथ की गणना करने के बजाय, आप इसे एक सीधे, पक्के सड़क के रूप में अनुमानित करते हैं। यह बिल्कुल परफेक्ट नहीं है, लेकिन रोबोट के सीखने के लिए पर्याप्त करीब है, और इस पर चलना बहुत तेज़ है।

"लो-रैंक" (Low-Rank) शॉर्टकट:
उन्होंने एक गणितीय ट्रिक का उपयोग किया जिससे उन्हें पता चला कि भले ही डेटा विशाल और अस्त-व्यस्त दिखता है, लेकिन वास्तव में इसमें बहुत सारी छिपी हुई संरचना (अतिरेक/redundancy) है। उन्होंने इस विशाल गणना को छोटे, प्रबंधनीय टुकड़ों में संकुचित करने का तरीका खोजा।

उपमा: कल्पना करें कि आपके पास लाखों किताबों वाला एक पुस्तकालय है। हर एक पन्ने को पढ़ने के बजाय कि आप किसी विशिष्ट तथ्य को खोजें, आप महसूस करते हैं कि किताबें इस तरह व्यवस्थित हैं कि आपको 99% किताबें छोड़ने और सीधे उत्तर पर जाने की अनुमति मिलती है।

परिणाम:
इन ट्रिक्स को मिलाकर, उन्होंने सिद्ध किया कि "बैकवर्ड" चरण (जहाँ रोबोट अपनी गलतियों से सीखता है) अब लगभग लीनियर टाइम (linear time) में किया जा सकता है।

अनुवाद: यदि पुराने तरीके को एक बड़े डेटासेट पर प्रशिक्षित करने में 1,000,000 सेकंड लगते, तो नए तरीके में केवल कुछ सेकंड लग सकते हैं (या कम से कम, एक ऐसा समय जो डेटा बढ़ने के साथ बहुत धीरे बढ़ता है)।

"कैच" (यह जादू क्यों नहीं है)

पेपर बहुत सावधानी से कहता है कि यह स्पीड-अप केवल विशिष्ट स्थितियों में ही काम करता है।

"टाइट" (Tight) धारणा: लेखकों ने सिद्ध किया कि उनकी धारणा (कि संख्याएँ बहुत बड़ी नहीं हैं) आवश्यक है। यदि आप संख्याओं को थोड़ा बड़ा करने या समस्या को थोड़ा कठिन बनाने की कोशिश करते हैं, तो "फास्ट लेन" गायब हो जाती है, और आप फिर से $n^3$ के ट्रैफिक जाम में फंस जाते हैं।
उपमा: इसे एक हाई-स्पीड ट्रेन की तरह समझें। यह अविश्वसनीय रूप से तेज़ चलती है, लेकिन केवल एक बहुत ही विशिष्ट, अच्छी तरह से बनाए रखे गए ट्रैक पर। यदि आप इस ट्रेन को एक कीचड़ भरे कच्चे रास्ते (धारणा को कमजोर करना) पर चलाने की कोशिश करते हैं, तो यह खराब हो जाती है। उन्होंने सिद्ध किया कि आप कच्चे रास्ते के लिए तेज़ ट्रेन नहीं बना सकते; भौतिकी इसकी अनुमति नहीं देती है।

सारांश

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

संक्षेप में, उन्होंने एक सैद्धांतिक रूप से "प्रशिक्षण के लिए असंभव" टूल को एक व्यावहारिक टूल में बदल दिया, लेकिन केवल एक विशिष्ट, सुव्यवस्थित प्रकार के डेटा के लिए।

तकनीकी सारांश: टेंसर अटेंशन का कुशलतापूर्वक प्रशिक्षण (Training Tensor Attention Efficiently)

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

टेंसर अटेंशन (Tensor Attention) एक मल्टी-व्यू अटेंशन मैकेनिज्म है जिसे कई मोडैलिटीज (जैसे ऑडियो, विजन, टेक्स्ट) के बीच उच्च-क्रम सहसंबंधों (high-order correlations) को कैप्चर करने के लिए डिज़ाइन किया गया है, जिन्हें क्लासिकल मैट्रिक्स अटेंशन स्वाभाविक रूप से नहीं दर्शा सकता। जबकि मैट्रिक्स अटेंशन स्कोर की गणना युग्मवार इंटरैक्शन ( $QK^\top$ ) के आधार पर करता है, टेंसर अटेंशन ट्रिपल-वाइज या उच्च-क्रम संबंधों को मॉडल करने के लिए कॉलम-वाइज क्रोनेकर उत्पाद ( $K_1 \oslash K_2$ ) का उपयोग करता है।

हालाँकि, ट्रांसफॉर्मर्स में टेंसर अटेंशन का व्यावहारिक अनुप्रयोग इसकी कम्प्यूटेशनल जटिलता (computational complexity) के कारण बाधित है। एक मानक सेटिंग में, इनपुट सीक्वेंस लेंथ $n$ और फीचर डायमेंशन $d$ के साथ, टेंसर अटेंशन के फॉरवर्ड कंप्यूटेशन में $n \times n^2$ आकार का एक मैट्रिक्स शामिल होता है, जिससे इसकी टाइम कॉम्प्लेक्सिटी $O(n^3)$ हो जाती है। यह क्यूबिक बाधा (cubic barrier) बड़े $n$ (जैसे Llama2 में $n=4096$ ) के लिए प्रशिक्षण और अनुमान (inference) को असंभव बना देती है, क्योंकि समान संसाधन उपयोग बनाए रखने के लिए अनुक्रम की लंबाई को काफी कम करना होगा (जैसे $n=256$ तक)।

जबकि हाल के कार्यों ने दिखाया है कि बाउंडेड एंट्री धारणाओं (bounded entry assumptions) के तहत टेंसर अटेंशन का फॉरवर्ड कंप्यूटेशन लगभग लीनियर समय ( $n^{1+o(1)}$ ) में त्वरित किया जा सकता है, बैकवर्ड ग्रेडिएंट कंप्यूटेशन की जटिलता एक खुला प्रश्न बना हुआ था, क्योंकि नैव (naive) दृष्टिकोण अभी भी $O(n^3)$ समय की आवश्यकता रखते हैं।

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

लेखक टेंसर अटेंशन ट्रेनिंग के बैकवर्ड ग्रेडिएंट को लगभग लीनियर समय में कंप्यूट करने के लिए एक विधि प्रस्तावित करते हैं, जो फॉरवर्ड पास की जटिलता से मेल खाती है। यह कार्यप्रणाली तीन मुख्य घटकों पर आधारित है:

क्लोज्ड-फॉर्म ग्रेडिएंट व्युत्पत्ति (Closed-Form Gradient Derivation):
लेखक पहले टेंसर अटेंशन लॉस फंक्शन के ग्रेडिएंट के लिए एक सटीक क्लोज्ड-फॉर्म समाधान व्युत्पन्न करते हैं। वे लॉस को टेंसर अटेंशन आउटपुट और एक टारगेट मैट्रिक्स $E$ के बीच फ्रोबेनियस नॉर्म (Frobenius norm) के रूप में परिभाषित करते हैं। वेट मैट्रिक्स $X$ के सापेक्ष ग्रेडिएंट एक जटिल इंटरमीडिएट मैट्रिक्स $F(x)$ से संबंधित है जिसका आकार $n \times n^2$ है, जो प्राथमिक कम्प्यूटेशनल बाधा बनता है।
पॉलीनोमियल एप्रोक्सिमेशन और लो-रैंक डिकंपोजिशन (Polynomial Approximation and Low-Rank Decomposition):
$O(n^3)$ बाधा को दूर करने के लिए, लेखक पॉलीनोमियल एप्रोक्सिमेशन विधियों का उपयोग करते हैं। वे सॉफ्टमैक्स ऑपरेशन के भीतर एक्सपोनेंशियल फंक्शन को एप्रोक्सिमेट करते हैं, जिससे परिणामी मैट्रिसेस (विशेष रूप से नॉर्मलाइजेशन टर्म $D^{-1}$ और अटेंशन मैट्रिक्स $A$ ) को लो-रैंक उत्पादों के रूप में दर्शाया जा सके। इस तकनीक को, जो पहले फॉरवर्ड टेंसर अटेंशन के लिए लागू की गई थी, यहाँ ग्रेडिएंट फॉर्मूलेशन में विस्तारित किया गया है।
टेंसर बीजगणितीय तकनीकें (Tensor Algebraic Techniques):
कार्य का एक महत्वपूर्ण हिस्सा ग्रेडिएंट गणना के दौरान लो-रैंक स्ट्रक्चर को बनाए रखने के लिए नवीन टेंसर बीजगणितीय हेरफेर (manipulations) से संबंधित है। प्रमुख तकनीकों में शामिल हैं:
- डिस्ट्रीब्यूटेड रूल्स (Distributed Rules): रो-वाइज और कॉलम-वाइज क्रोनेकर उत्पादों के गुणों का उपयोग करके लो-रैंक एप्रोक्सिमेशन को ग्रेडिएंट समीकरण के विभिन्न घटकों में वितरित करना।
- फैक्टर्ड मल्टीप्लिकेशन (Factored Multiplication): विशिष्ट लेम्मा (जैसे Lemma 4.5) को लागू करना जो क्रोनेकर संरचनाओं वाले उत्पादों की गणना को छोटे मैट्रिक्स मल्टीप्लिकेशन में विघटित करने की अनुमति देते हैं, जिससे प्रभावी रूप से जटिलता से क्वाड्रेटिक $n^2$ फैक्टर हट जाता है।
- वेक्टराइजेशन ट्रिक्स (Vectorization Tricks): टेंसर ऑपरेशन्स को मानक मैट्रिक्स-वेक्टर मल्टीप्लिकेशन में बदलने के लिए वेक्टराइजेशन आइडेंटिटीज का उपयोग करना।

प्रस्तावित एल्गोरिदम (Algorithm 1) इंटरमीडिएट टर्म्स ( $S, V, W, F$ ) के लिए लो-रैंक एप्रोक्सिमेशन बनाता है और अंतिम ग्रेडिएंट एस्टीमेट $\tilde{g}$ को $n^{1+o(1)}$ समय में कंप्यूट करने के लिए उन्हें जोड़ता है।

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

क्लोज्ड-फॉर्म ग्रेडिएंट: पेपर टेंसर अटेंशन के ग्रेडिएंट के लिए पहला क्लोज्ड-फॉर्म समाधान (Lemma 3.1) प्रदान करता है और इसके नैव टाइम कॉम्प्लेक्सिटी (Theorem 3.3) का विश्लेषण करता है।
लगभग लीनियर टाइम एल्गोरिदम: लेखक एल्गोरिदम 1 प्रस्तुत करते हैं, जो $n^{1+o(1)}$ समय में अनुमानित ग्रेडिएंट की गणना करता है (Theorem 4.2)। यह समान बाउंडेड एंट्री धारणाओं के तहत फॉरवर्ड पास की जटिलता से मेल खाता है।
हार्डनेस एनालिसिस (Hardness Analysis): पेपर सिद्ध करता है कि बाउंडेड एंट्री धारणा आवश्यक और "टाइट" है। स्ट्रॉन्ग एक्सपोनेंशियल टाइम हाइपोथेसिस (SETH) के तहत, यदि मैट्रिक्स एंट्रीज पर बाउंड को थोड़ा भी कमजोर किया जाता है, तो कोई भी एल्गोरिदम टेंसर अटेंशन ग्रेडिएंट समस्या को वास्तव में सब-क्यूबिक समय में हल नहीं कर सकता (Theorem 5.3)।

परिणाम (Results)

कॉम्प्लेक्सिटी रिडक्शन: यह कार्य टेंसर अटेंशन ग्रेडिएंट कंप्यूटेशन की टाइम कॉम्प्लेक्सिटी को $O(n^3)$ से घटाकर $n^{1+o(1)}$ कर देता है।
एप्रोक्सिमेशन गारंटी: एल्गोरिदम एक ग्रेडिएंट मैट्रिक्स $\tilde{g}$ आउटपुट करता है ताकि $\|\tilde{g} - \frac{d\text{Loss}(X)}{dX}\|_\infty \leq \epsilon$ , जहाँ $\epsilon$ को $1/\text{poly}(n)$ के रूप में सेट किया जा सकता है।
धारणा की वैधता (Assumption Validity): परिणाम इस धारणा के तहत मान्य हैं कि इनपुट मैट्रिक्स एंट्रीज $B = o(\sqrt[3]{\log n})$ द्वारा बाउंडेड हैं और $O(\log n)$ बिट्स के साथ दर्शाई गई हैं। लेखक प्रदर्शित करते हैं कि इस बाउंड को शिथिल करने से समस्या कम्प्यूटेशनल रूप से कठिन हो जाती है।

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

पेपर दावा करता है कि यह कुशल हायर-ऑर्डर ट्रांसफार्मर ट्रेनिंग की सैद्धांतिक व्यवहार्यता स्थापित करता है। फॉरवर्ड और बैकवर्ड दोनों कंप्यूटेशन में $O(n^3)$ जटिलता बाधा को पार करके, यह कार्य व्यवहार में टेंसर अटेंशन आर्किटेक्चर का उपयोग करने के लिए एक मौलिक बाधा को हटा देता है।

लेखक कहते हैं कि उनके सैद्धांतिक परिणाम "टेंसर अटेंशन आर्किटेक्चर के व्यावहारिक अनुप्रयोगों को सुगम बना सकते हैं," विशेष रूप से मल्टी-मोडैलिटी मॉडल्स के लिए जिन्हें उच्च-क्रम सहसंबंधों (जैसे ऑडियो-विजन-टेक्स्ट रीजनिंग) को कैप्चर करने की आवश्यकता होती है। यह कार्य बड़े भाषा मॉडलों (LLMs) पर अनुभवजन्य मूल्यांकन (empirical evaluations) प्रस्तुत नहीं करता है, बल्कि खुद को एक मौलिक सैद्धांतिक कदम के रूप में स्थापित करता है जो भविष्य के अनुभवजन्य अनुसंधान को सक्षम बनाता है। लेखक इस बात पर जोर देते हैं कि उनका हार्डनेस एनालिसिस पुष्टि करता है कि उनकी धारणाएं केवल तकनीकी सुविधाएँ नहीं हैं, बल्कि किसी भी सब-क्यूबिक समाधान के लिए संभवतः आवश्यक हैं।