🤖 machine learning

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases

यह शोध पत्र यह सिद्ध करके कि ALiBi अटेंशन मैकेनिज्म को उच्च प्रायिकता के साथ रैंडमाइज्ड ब्लॉक-डायगोनल बाइनरी मास्क द्वारा अनुमानित किया जा सकता है, जिससे लंबे-कॉन्टेक्स्ट अटेंशन के लिए कुशल नियर-लीनियर टाइम कंप्यूटेशन सक्षम होता है, पोजीशनल बायस और लोकैलिटी-सेंसिटिव हैशिंग के बीच एक औपचारिक संबंध स्थापित करता है, और इस प्रकार पोशनल बायस, मास्क और एम्बेडिंग्स को एक एकल सैद्धांतिक ढांचे में एकीकृत करता है।

मूल लेखक: Daniel Wolfson, Tal Wagner

प्रकाशित 2026-05-12

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

CC BY 4.0

मूल लेखक: Daniel Wolfson, Tal Wagner

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

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

हालाँकि, एक समस्या है: जब पुस्तकालय बहुत बड़ा हो जाता है (लंबे संदर्भों के साथ), तो हर किताब के लिए हर दूसरी किताब को पढ़ना अविश्वसनीय रूप से धीमा और महंगा हो जाता है। इसे ठीक करने के लिए, शोधकर्ताओं ने ALiBi (Linear Biases के साथ Attention) का आविष्कार किया। ALiBi को एक ऐसे नियम के रूप में सोचें जो कहता है, "शेल्फ पर एक-दूसरे के बगल में रखी किताबों को दूर स्थित किताबों की तुलना में अधिक ज़ोर से बात करनी चाहिए।" यह एक चतुर तरीका है जिससे AI जटिल स्थिति मार्करों (position markers) की आवश्यकता के बिना पास के शब्दों पर ध्यान केंद्रित कर सकता है।

लेकिन यहाँ एक पेंच है: ALiBi अभी भी गणितीय रूप से भारी है। इसके लिए प्रत्येक इंटरैक्शन के लिए एक विशाल, जटिल "बायस मैप" (bias map) की गणना करने की आवश्यकता होती है, जो काम को धीमा कर देता है।

मुख्य विचार: "पोज़िशनल LSH" (Positional LSH)

इस शोध पत्र के लेखकों ने एक सरल प्रश्न पूछा: क्या हम इस जटिल ALiBi नियम को बहुत सरल चीज़, जैसे कि बाइनरी स्विच (ऑन/ऑफ) के सेट का उपयोग करके अनुमानित (approximate) कर सकते हैं?

उन्होंने पाया कि वे इसे लोकेलिटी-सेंसिटिव हैशिंग (Locality-Sensitive Hashing - LSH) की अवधारणा का उपयोग करके कर सकते हैं।

उपमा: "ग्रुपिंग गेम" (The Grouping Game)

कल्पना कीजिए कि आपके पास एक गलियारे में लोगों (टोकन्स) की एक लंबी कतार है।

पुराना तरीका (ALiBi): आप यह तय करने के लिए कि उन्हें कितनी बात करनी चाहिए, लोगों के हर जोड़े के बीच की सटीक दूरी की गणना करते हैं। यह सटीक है लेकिन इसमें बहुत समय लगता है।
नया तरीका (Positional LSH): सटीक दूरियों को मापने के बजाय, आप एक खेल खेलते हैं। आप गलियारे के ऊपर एक विशाल, यादृच्छिक (random) "नेट" फेंकते हैं।
- इस नेट में अलग-अलग आकार के छेद हैं।
- जो कोई भी एक ही छेद में फँसा है, उसे "1" मिलता है (वे एक साथ समूह में हैं)।
- जो कोई भी अलग छेदों में है, उसे "0" मिलता है (उन्हें इस दौर के लिए अनदेखा कर दिया जाता है)।
- क्योंकि नेट रैंडम है, इसलिए कभी लोग जो पास में हैं वे ग्रुप में आते हैं, और कभी वे नहीं।

जादू: यदि आप इस "नेट फेंकने" वाले खेल को कई बार दोहराते हैं और परिणामों का औसत निकालते हैं, तो यह पैटर्न कि कौन किसके साथ ग्रुप में आया, जटिल ALiBi नियम की सटीक नकल करता है।

यह शोध पत्र वास्तव में क्या सिद्ध करता है

लेखकों ने केवल यह अनुमान नहीं लगाया कि यह काम करेगा; उन्होंने इसे गणितीय रूप से सिद्ध किया:

संरचनात्मक संबंध (The Structural Connection): उन्होंने दिखाया कि जटिल ALiBi बायस मैट्रिक्स वास्तव में कई सरल, ब्लॉक वाले, बाइनरी मास्क का "औसत" है। इसे एक उच्च-रिज़ॉल्यूशन वाली फोटो की तरह समझें (ALiBi) जिसे कई निम्न-रिज़ॉल्यूशन, ब्लैक-एंड-व्हाइट पिक्सेलेटेड परतों (बाइनरी मास्क) को एक के ऊपर एक रखकर पूरी तरह से पुनर्गठित किया जा सकता है।
गति में वृद्धि (The Speed Boost): क्योंकि ये बाइनरी मास्क केवल "ऑन" और "ऑफ" के ब्लॉक्स हैं, इसलिए कंप्यूटर को भारी गणित करने की आवश्यकता नहीं होती है। यह विशाल पुस्तकालय को छोटे, प्रबंधनीय कमरों (ब्लॉक्स) में तोड़ सकता है और उन्हें अलग-अलग प्रोसेस कर सकता है। यह एक धीमी, भारी गणना को एक तेज़, लगभग लीनियर (linear) गणना में बदल देता है।
सटीकता (Accuracy): उन्होंने सिद्ध किया कि भले ही प्रत्येक व्यक्तिगत "नेट टॉस" एक मोटा अनुमान हो, कई टॉस का औसत अविश्वसनीय रूप से सटीक होता है। आप जितनी बार नेट फेंकते हैं (सैंपल करते हैं), आप सटीक ALiBl परिणाम के उतने ही करीब पहुँच जाते हैं।

प्रयोग (The Experiments)

इसका परीक्षण करने के लिए, शोधकर्ताओं ने वास्तविक, बड़े AI मॉडल (जैसे Llama और Mistral) पर इसे आज़माया।

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

सीमाएँ (जो शोध पत्र नहीं बताता)

लेखक इस बारे में बहुत ईमानदार हैं कि यह अभी तक क्या नहीं करता है:

वर्तमान हार्डवेयर पर तत्काल गति में वृद्धि नहीं: हालांकि गणित कहता है कि यह तेज़ होना चाहिए (लगभग लीनियर समय), उनके वर्तमान सॉफ़्टवेयर प्रोटोटाइप ने आज के GPU पर मौजूदा, अत्यधिक अनुकूलित (optimized) ALiBi कोड को नहीं हराया। इसका कारण यह है कि वर्तमान कंप्यूटर चिप्स बहुत कुशलता से विशाल, सघन (dense) गणनाओं को संभालने के लिए बनाए गए हैं। काम को कई छोटे टुकड़ों में तोड़ना (जो यह विधि करती है), हमेशा वर्तमान हार्डवेयर पर तेज़ नहीं होता है, भले ही गणित यह कहे कि इसमें कुल ऑपरेशन्स कम हैं।
यह पहले एक सिद्धांत है: यह शोध पत्र एक सैद्धांतिक सफलता है जो एक दरवाज़ा खोलती है। यह साबित करता है कि दरवाज़ा मौजूद है और यह दिखाता है कि चाबी कैसे बनाई जाए, लेकिन उन्होंने अभी तक इसके माध्यम से चलने के लिए सबसे तेज़ कार नहीं बनाई है।

सारांश

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

तकनीकी सारांश: पोजीशनल LSH: अटेंशन के लिए बाइनरी ब्लॉक मैट्रिक्स एप्रोक्सिमेशन विद लीनियर बायस

समस्या विवरण

ट्रांसफॉर्मर आर्किटेक्चर टोकन स्थानों को सूचित करने के लिए पोजीशनल एनकोडिंग पर निर्भर करता है, फिर भी तीन प्रमुख प्रतिमानों—पोजीशनल एम्बेडिंग्स (जैसे, RoPE), अटेंशन मास्क (जैसे, स्लाइडिंग विंडोज), और अटेंशन बायस (जैसे, ALiBi)—के बीच औपचारिक संबंध सीमित हैं। एक विशिष्ट कम्प्यूटेशनल बाधा अटेंशन विद लीनियर बायस (ALiBi) में आती है, जो लॉन्ग-कॉन्टेक्स्ट मॉडलिंग के लिए एक व्यापक रूप से अपनाई जाने वाली विधि है। जबकि ALiBi बिना स्पष्ट पोजीशनल एम्बेडिंग्स के लंबे अनुक्रमों (sequences) को प्रभावी ढंग से संभालता है, लंबे संदर्भों पर सटीक बायस मैट्रिक्स (bias matrix) की गणना करना कम्प्यूटेशनल रूप से महंगा ( $O(n^2)$ ) है। मौजूदा कुशल अटेंशन दृष्टिकोण अक्सर टोकन एम्बेडिंग्स के लोकैलिटी-सेंसिटिव हैशिंग (LSH) पर निर्भर करते हैं, लेकिन ALiBi बायस मैट्रिक्स को ही अनुमानित (approximate) करने के लिए टोकन पोज़िशन्स पर LSH लागू करने के लिए कोई औपचारिक ढांचा मौजूद नहीं था।

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

लेखक एक पोजीशनल लोकैलिटी-सेंसिटिव हैशिंग (LSH) ढांचे का प्रस्ताव करते हैं जो ALiBi बायस मैट्रिक्स को निरंतर ब्लॉक-डायगोनल बाइनरी मास्क के प्रत्याशा (expectation) के रूप में पुनर्व्याख्या करता है।

1. सैद्धांतिक ढांचा: पोजीशनल LSH

मुख्य अंतर्दृष्टि यह है कि ALiBi बायस मैट्रिक्स $L^*$ , जिसे $L^*_{ij} = e^{-|i-j|/\sigma}$ द्वारा परिभाषित किया गया है, टोकन पोज़िशन्स पर एक लैपलेसियन कर्नेल (Laplacian kernel) के अनुरूप है। टोकन पोज़िशन्स को एक मीट्रिक स्पेस में ऑब्जेक्ट्स के रूप में मानकर, लेखक विशेष रूप से अनुक्रम के पूर्णांक इंडेक्स (integer indices) पर रैंडम बिनिंग फीचर्स (RBFs) LSH योजना (जो मूल रूप से लैपलेसियन कर्नेल के लिए राहीमी और रेच्ट द्वारा परिभाषित की गई थी) लागू करते हैं।

तंत्र (Mechanism): एक हैश फ़ंक्शन $h$ अनुक्रम इंडेक्स को निरंतर बिनों (bins) में विभाजित करता है। प्रेरित बाइनरी मैट्रिक्स $M(h)$ में वहां 1 होते हैं जहां इंडेक्स एक ही बिन में आते हैं और अन्यथा 0 होते हैं।
प्रत्याशा (Expectation): ALiBi मैट्रिक्स इन रैंडम बाइनरी मास्क के प्रत्याशा के रूप में सटीक है: $L^* = \mathbb{E}_{h \sim \mathcal{H}}[M(h)]$ ।
संरचना: एम्बेडिंग्स पर मानक LSH के विपरीत, जो मनमाने ब्लॉक स्ट्रक्चर उत्पन्न करता है, पूर्णांक इंडेक्स पर RBF योजना यह गारंटी देती है कि परिणामी ब्लॉक्स निरंतर (contiguous) और गैर-ओवरलैपिंग होंगे।

2. स्ट्रक्चरल एप्रोक्सिमेशन (थ्योरम 2.1)

पेपर सिद्ध करता है कि ALiBi मैट्रिक्स को इन बाइनरी मास्क के $s$ i.i.d. सैंपल्स के अनुभवजन्य माध्य (empirical mean) $\tilde{M} = \frac{1}{s}\sum M_i$ द्वारा अनिश्चित रूप से अच्छी तरह से अनुमानित किया जा सकता है।

अभिसरण गारंटी (Convergence Guarantees): लेखक दोनों स्पेक्ट्रल नॉर्म (spectral norm) और मैक्स-नॉर्म (max-norm) में एप्रोक्सिमेशन एरर के लिए उच्च-संभाव्यता सीमाएं स्थापित करते हैं।
ब्लॉक साइज कंट्रोल: महत्वपूर्ण रूप से, विश्लेषण उच्च संभाव्यता के साथ अधिकतम निरंतर ब्लॉक्स के आकार ( $b_{max}$ ) को बांधता है, यह दिखाते हुए कि $b_{max} \approx \sigma \log \log n$ । यह सुनिश्चित करता है कि एप्रोक्सिमेशन एक एकल बड़े ब्लॉक में विकृत न हो जाए, जिससे लोकैलिटी प्रॉपर्टी बनी रहे।
उपकरण (Tools): प्रमाण सब-एक्सपोनेंशियल मैट्रिक्स बर्नस्टीन (sub-exponential matrix Bernstein), टोप्लिट्ज़ मैट्रिसेस (Toeplitz matrices) के फूरियर विश्लेषण, और RBFs के आधार पर गामा वितरण के गुणों का उपयोग करता है।

3. एल्गोरिद्मिक रिडक्शन (थ्योरम 2.2)

स्ट्रक्चरल थ्योरम के आधार पर, लेखक लगभग-लीनियर समय $O(nd(\sigma s \log(s/\delta) + 1))$ में ALiBi-बायस्ड अटेंशन को अनुमानित करने के लिए एक एल्गोरिदम का प्रस्ताव करते हैं।

रिडक्शन: लॉन्ग-कॉन्टेक्स्ट ALiBi अटेंशन को रैंडमाइज्ड, शॉर्ट-कॉन्टेक्स्ट, पोशनली अनबायस्ड अटेंशन ऑपरेशन्स के एक संग्रह में कम कर दिया जाता है।
यूनिफॉर्म गारंटी: एप्रोक्सिमेशन उच्च संभाव्यता के साथ सभी क्वेरी-की-वैल्यू इनपुट्स के लिए समान रूप से मान्य है, बशर्ते कि सैंपल की संख्या $s$ , कॉन्टेक्स्ट लेंथ $n$ के साथ लॉगरिदमिक रूप से स्केल करे।
एरर बाउंड: आउटपुट एरर को बायस्ड अटेंशन वेट्स के न्यूनतम रो सम (row sum) के अनुपात द्वारा बायस मैट्रिक्स में एप्रोक्सिमेशन एरर से बांधा गया है।

मुख्य परिणाम

सैद्धांतिक निष्कर्ष

औपचारिक संबंध: यह कार्य पोजीशनल बायस, मास्क और एम्बेडिंग्स के बीच एक कठोर गणितीय लिंक स्थापित करता है, यह दिखाते हुए कि बायस को मास्क के एक एक्सपेक्टेशन के रूप में देखा जा सकता है जो पोजीशनल LSH द्वारा प्रेरित होते हैं।
एप्रोक्सिमेशन की गुणवत्ता: स्पेक्ट्रल और मैक्स-नॉर्म एरर $O(1/\sqrt{s})$ के रूप में घटते हैं, जिससे अपेक्षाकृत कम सैंपल्स के साथ उच्च-परिशुद्धता एप्रोक्सिमेशन संभव होता है।
जटिलता: विधि ALiBi के लिए एक प्रमाणित निकट-लीनियर टाइम एल्गोरिदम प्रदान करती है, जो सटीक लॉन्ग-कॉन्टेक्स्ट अटेंशन की कम्प्यूटेशनल बाधा को संबोधित करती है।

प्रयोगात्मक सत्यापन

लेखकों ने अपने सिद्धांत को प्री-ट्रेंड मॉडल्स (Llama-4-Scout-17B-16E, Mistral-7B) और ट्रेनिंग प्रयोगों (Qwen3-0.6B, Mistral-7B) का उपयोग करके मान्य किया।

अभिसरण (Convergence): प्रयोगों ने पुष्टि की कि मैट्रिक्स नॉर्म एरर्स ( $\|L^* - \tilde{M}\|$ ) और आउटपुट एरर्स ( $\|T^* - \tilde{T}^*\|$ ) सैंपल साइज $s$ बढ़ने के साथ शून्य की ओर घटते हैं, जो सैद्धांतिक भविष्यवाणियों से मेल खाते हैं।
डाउनस्ट्रीम प्रदर्शन:
- Qwen3-0.6B (स्क्रैच से प्रशिक्षित) में, छोटे सैंपल साइज ( $s=10, 20$ ) के साथ पोजीशनल LSH ने सटीक ALiBi के तुलनीय परप्लेक्सिटी और सटीकता प्राप्त की और बिना बायस वाले मूल मॉडल से बेहतर प्रदर्शन किया।
- Mistral-7B (फाइन-ट्यून किया गया) में, जैसे-जैसे $s$ बढ़ता है, पोशनल LSH सटीक ALiBi के करीब पहुंच जाता है, जो "फिक्स्ड ब्लॉक्स" बेसलाइन से काफी बेहतर प्रदर्शन करता है।
- पद्धति ने लेंथ एक्सट्रपलेशन परिदृश्यों (जैसे, 8k पर प्रशिक्षण, 16k पर मूल्यांकन) में मजबूती प्रदर्शित की।

महत्व और दावे

पेपर का दावा है कि यह ALiBi के एक नए परिवार के बजाय इसके स्ट्रक्चरल और एल्गोरिद्मिक विश्लेषण प्रदान करता है। इसके प्राथमिक योगदान हैं:

वैचारिक एकीकरण: यह पोशनल बायस, मास्क और एम्बेडिंग्स को LSH पर आधारित एक एकल औपचारिक ढांचे के तहत एकीकृत करता है।
दक्षता: यह प्रमाणित एप्रोक्सिमेशन गारंटी के साथ, रैंडमाइज्ड शॉर्ट-कॉन्टेक्स्ट ऑपरेशन्स में बदलकर कुशल लॉन्ग-कॉन्टेक्स्ट ALiBi के लिए एक सैद्धांतिक मार्ग प्रदान करता है।
LSH अनुप्रयोग में नवीनता: टोकन कंटेंट को हैश करने वाले पिछले LSH-आधारित अटेंशन कार्यों के विपरीत, यह कार्य अद्वितीय रूप से टोकन पोज़िशन्स पर LSH लागू करता है, जिसके लिए मैट्रिक्स कन्वर्जेंस और ब्लॉक साइज कंट्रोल के लिए विशिष्ट प्रमाणों की आवश्यकता होती है।

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

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