🤖 machine learning

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

यह शोध पत्र मल्टीप्रोब ग्रिड-आधारित ANN खोज का एक व्यवस्थित विश्लेषण प्रस्तुत करता है, जो ग्राफ, ट्री और विभाजन विधियों की तुलना में उच्च आयामों में इसकी बेहतर स्केलेबिलिटी और कम इंडेक्सिंग लागत को प्रकट करता है, जिससे पुनर्गठन-प्रधान (rebuild-heavy) अनुप्रयोगों और कुशल ट्रांसफार्मर आर्किटेक्चर को अनुकूलित करने के लिए इसकी क्षमता का सुझाव मिलता है।

मूल लेखक: Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

प्रकाशित 2026-07-03

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

CC BY 4.0

मूल लेखक: Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

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

यहाँ एक सरल भाषा और रोज़मर्रा के उदाहरणों का उपयोग करके पेपर की व्याख्या दी गई है।

बड़ी तस्वीर: बढ़ते और बदलते ढेर में सुई ढूँढना

कल्पना कीजिए कि आप घास के ढेर (haystack) में एक विशिष्ट सुई ढूँढ रहे हैं।

सुई: वह सटीक उत्तर जिसे आप ढूँढ रहे हैं ("निकटतम पड़ोसी" या nearest neighbor)।
घास का ढेर: डेटा पॉइंट्स का एक विशाल संग्रह (जैसे लाखों शब्द या चित्र)।
समस्या: जैसे-जैसे घास का ढेर बड़ा होता जाता है (अधिक डेटा) या सुइयाँ अधिक जटिल होती जाती हैं (उच्च आयाम/dimensions), उस विशिष्ट सुई को ढूँढना अविश्वसनीय रूप से धीमा और कठिन हो जाता है।

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

उपमा: सुपरमार्केट बनाम भूलभुलैया

तरीकों के बीच के अंतर को समझने के लिए, आइए दो उपमाओं का उपयोग करें:

1. आधुनिक तरीके (ग्राफ और ट्री): जटिल भूलभुलैया (The Complex Maze)
वर्तमान लोकप्रिय तरीके एक जटिल, बहु-स्तरीय भूलभुलैया की तरह हैं। सुई खोजने के लिए, आपको भूलभुलैया के माध्यम से एक घुमावदार रास्ते पर चलना होगा।

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

2. नया तरीका (मल्टीप्रोब ग्रिड): व्यवस्थित सुपरमार्केट (The Organized Supermarket)
इस पेपर में दिया गया तरीका एक पूरी तरह से व्यवस्थित सुपरमार्केट की तरह है।

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

पेपर ने क्या खोजा

लेखकों ने यह देखने के लिए प्रयोग किए कि दो चीजों में बदलाव होने पर ये तरीके कितने तेज़ होते हैं: डेटा का आकार (size) और डेटा की जटिलता (complexity)।

1. "आकार" का परीक्षण (अधिक घास के ढेर)

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

2. "जटिलता" का परीक्षण (डायमेंशन क्रॉसओवर)

सेटअप: उन्होंने डेटा को अधिक जटिल बनाया (अधिक फीचर्स जोड़कर, जैसे 2D ड्राइंग से 3D मॉडल में जाना, फिर 100D मॉडल में जाना)।
आश्चर्य: यह इस पेपर की सबसे बड़ी खोज है।
- "भूलभुलैया" वाले तरीके (ग्राफ/ट्री) जटिलता बढ़ने के साथ बहुत धीमे हो गए। डेटा जितना अधिक जटिल होता गया, उनके लिए गलत रास्तों को हटाना (prune करना) उतना ही कठिन होता गया।
- "सुपरमार्केट" (ग्रिड) विधि स्थिर रही। क्योंकि यह गलियारों को चुनने के लिए एक सरल मानचित्र का उपयोग करती है, इसलिए यह अतिरिक्त जटिलता से भ्रमित नहीं हुई।
क्रॉसओवर: जटिलता के एक निश्चित स्तर पर, ग्रिड विधि वास्तव में आधुनिक भूलभुलैया विधियों की तुलना में तेज़ हो गई। पेपर इसे "क्रॉसओवर" कहता है।

3. सेटअप लागत (स्टोर बनाना)

सेटअप: इंडेक्स बनाने (शेल्फ सेट करने) में कितना समय लगता है ताकि आप खोज शुरू कर सकें?
परिणाम: ग्रिड विधि को सेट अप करना अविश्वसनीय रूप से तेज़ है। ग्रिड विधि को दस लाख वस्तुओं को व्यवस्थित करने में 4 से 36 सेकंड लगे। आधुनिक भूलभ "मिनटों से लेकर 25 मिनट से अधिक" का समय ले गए।
यह क्यों मायने रखता है: यदि आपके पास ऐसा सिस्टम है जहाँ आप लगातार पुराना डेटा हटाते हैं और नए सिरे से एक नया इंडेक्स बनाते हैं (जैसे कि एक रिकमेंडेशन सिस्टम जो हर घंटे अपडेट होता है), तो ग्रिड विधि एक विजेता है क्योंकि यह बहुत तेज़ी से बनता है।

"कुल लागत" का समीकरण (The Total Cost Equation)

पेपर का तर्क है कि आपको केवल यह नहीं देखना चाहिए कि खोज दौरान खोज कितनी तेज़ है। आपको कुल लागत (Total Cost) देखनी चाहिए:

कुल लागत = (बनाने का समय) + (खोज का समय × आप कितनी बार खोज करते हैं)

परिदृश्य A: आप इंडेक्स को एक बार बनाते हैं और दस लाख बार खोज करते हैं। धीमी गति से बनने वाले भूलभुलैया वाले तरीके जीत सकते हैं क्योंकि वे खोजने में तेज़ होते हैं।
परिदृश्य B: आप इंडेक्स को अक्सर बनाते हैं (rebuild-heavy) या केवल कुछ ही बार खोज करते हैं। ग्रिड विधि जीतती है क्योंकि इसे बनाना बहुत सस्ता और तेज़ है।

AI के लिए यह क्यों महत्वपूर्ण है (द "अटेंशन" कनेक्शन)

पेपर उल्लेख करता है कि आधुनिक AI (ट्रांसफॉर्मर) यह तय करने के लिए "अनुमानित निकटतम पड़ोसी" (Approximate Nearest Neighbor) खोज करने का काम करता है कि किन शब्दों पर ध्यान देना है।

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

सारांश

पेपर कहता है: "सरल ग्रिड को नज़रअंदाज़ न करें।"
जबकि सभी लोग जटिल, भूलभुलैया जैसे खोज विधियों के प्रति जुनूनी रहे हैं, सरल, व्यवस्थित "सुपरमार्केट" दृष्टिकोण (मल्टीप्रोब ग्रिड) वास्तव में निम्नलिखित को संभालने में बेहतर है:

विशाल डेटासेट (अनुमानित गति)।
बहुत जटिल डेटा (यह उच्च आयामों से भ्रमित नहीं होता)।
बार-बार पुनर्गठन (यह मिनटों के बजाय सेकंडों में सेट अप हो जाता है)।

यह एक याद दिलाता है कि कभी-कभी "पुराने स्कूल" का तरीका, जब उसे सही ढंग से सुधारा जाए, तो काम के लिए सबसे कुशल उपकरण होता है।

तकनीकी सारांश: उच्च आयामों में ग्रिड-आधारित अनुमानित निकटतम पड़ोसी (ANN) खोज के लिए स्केलिंग लॉज़

समस्या विवरण

अनुमानित निकटतम पड़ोसी (ANN) खोज आधुनिक मशीन लर्निंग का एक मौलिक प्रिमिटिव है, जो पारंपरिक रिट्रीवल कार्यों और ट्रांसफार्मर आर्किटेक्चर के लिए एक कम्प्यूटेशनल बिल्डिंग ब्लॉक (जहाँ सेल्फ-अटेंशन को एक ANN ऑपरेशन के रूप में औपचारिक रूप दिया जाता है) दोनों के रूप में कार्य करता है। जबकि अनुभवजन्य स्केलिंग लॉज़ बड़े पैमाने के मॉडलों के डिज़ाइन का मार्गदर्शन करते हैं, डेटासेट के आकार ( $N$ ) और आयाम ( $d$ ) के संबंध में ANN एल्गोरिदम का स्केलिंग व्यवहार एक महत्वपूर्ण, फिर भी कम-चरित्रांकित क्षेत्र बना हुआ है।

मौजूदा साहित्य ने ग्राफ-आधारित (जैसे HNSW), ट्री-आधारित, और पार्टिशनिंग-आधारित विधियों का व्यापक विश्लेषण किया है। हालाँकि, ग्रिड-आधारित दृष्टिकोण, अपने प्रारंभिक ANN सिद्धांत में मौलिक भूमिका के बावजूद, आधुनिक स्केलिंग विश्लेषणों से काफी हद तक अनुपस्थित रहे हैं। यह शोध पत्र एक मल्टीप्रोब ग्रिड एल्गोरिदम के स्केलिंग डायनेमिक्स को व्यवस्थित रूप से चरित्रित करके इस अंतराल को भरता है, विशेष रूप से यह जांच करता है कि इसका प्रदर्शन $N$ और $d$ के सापेक्ष अत्याधुनिक प्रतिस्पर्धियों की तुलना में कैसे स्केल होता है।

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

मल्टीप्रोब ग्रिड एल्गोरिदम

लेखक एक मल्टीप्रोब ग्रिड एल्गोरिदम प्रस्तावित करते हैं जो पूर्ण आयाम $d$ से सेल चयन को अलग करता है। वर्कफ़्लो इस प्रकार है:

PCA प्रोजेक्शन: डेटा पॉइंट्स को $\mathbb{R}^d$ से एक निम्न-आयामी सबस्पेस $\mathbb{R}^m$ ( $m \ll d$ ) में प्रोजेक्ट किया जाता है।
ग्रिड पार्टिशनिंग: सबस्पेस को एक समान ग्रिड की $G^m$ सेल्स में विभाजित किया जाता है।
मल्टीप्रोब चयन: क्वेरी के समय, एल्गोरिदम "होम" सेल की पहचान करता है और क्वेरी से स्क्वेर्ड वॉल डिस्टेंस ( $w_i^2$ ) द्वारा क्रमबद्ध होकर अधिकतम $2^m - 1$ पड़ोसी सेल्स को प्रोब करता है।
री-रैंकिंग: प्रोब की गई सेल्स से एकत्र किए गए उम्मीदवारों को मूल उच्च-आयामी स्थान $\mathbb{R}^d$ में पुनः रैंक किया जाता है।

सैद्धांतिक मॉडल

लेखक क्वेरी लागत (क्वेरीज प्रति सेकंड, QPS) और रिकॉल ( $R$ ) के बीच एक क्लोज्ड-फॉर्म संबंध व्युत्पन्न करते हैं।

कॉस्ट मॉडल: क्वेरी लागत प्रोब की गई सेल्स की संख्या ( $n_{probe}$ ) और प्रति सेल बिंदुओं की संख्या ( $N/G^m$ ) में रैखिक होती है।
रिकॉल मॉडल: एक समान वितरण (uniform distribution) मानते हुए, प्रोब की गई सेल में वास्तविक निकटतम पड़ोसी होने की संभावना वॉल डिस्टेंस के साथ तेजी से (exponentially) घटती है।
परिणामी संबंध: मॉडल QPS और रिकॉल के बीच एक लॉग-लीनियर संबंध की भविष्यवाणी करता है: $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ । यह सेल्स के बीच सदस्यता की संभावना के घातीय क्षय (exponential decay) और कैंडिडेट सेट के आकार के रैखिक विकास से उत्पन्न होता है।

अनुभवजन्य मूल्यांकन

यह अध्ययन चार बेसलाइनों के विरुद्ध मल्टीप्रोब ग्रिड का मूल्यांकन करता है जो प्रमुख ANN परिवारों का प्रतिनिधित्व करते हैं:

ग्राफ-आधारित: Voyager, PyNNDescent।
ट्री-आधारित: Annoy।
पार्टिशनिंग/क्वांटाइजेशन: FAISS-IVF।

प्रयोग ann-benchmarks फ्रेमवर्क का उपयोग करके दो डेटासेट्स पर किए गए:

GloVe-200-angular (वर्ड एम्बेडिंग्स, $d=200$ , $N \approx 1.18 \times 10^6$ )।
SIFT-128-euclidean (इमेज डिस्क्रिप्टर्स, $d=128$ )।

मूल्यांकन $N$ ( $\alpha_N$ ) और $d$ ( $\alpha_d$ ) के लिए स्केलिंग एक्सपोनेंट्स, पारेटो फ्रंट्स (थ्रूपुट बनाम रिकॉल), और कुल लागत विश्लेषण पर केंद्रित था।

मुख्य परिणाम

1. लॉग-लीनियर थ्रूपुट-रिकॉल संबंध

GloVe-200 पर पारेटो फ्रंट विश्लेषण सैद्धांतिक भविष्यवाणी की पुष्टि करता है: मल्टीप्रोब ग्रिड रिकॉल बढ़ने के साथ थ्रूपुट में एक लॉग-लीनियर कमी प्रदर्शित करता है। यह व्यवहार बेसलाइनों से भिन्न है और ग्रिड ज्योमेट्री तथा निकटतम-पड़ोसी सदस्यता की घातीय गिरावट द्वारा संचालित होता है।

2. $N$ -स्केलिंग: निकट-रैखिक गिरावट

मल्टीप्रोब ग्रिड डेटासेट के आकार ( $N$ ) के साथ निकट-रैखिक (near-linearly) रूप से स्केल करता है।

रिकॉल@10 = 0.80 पर, स्केलिंग एक्सपोनेंट $\alpha_N \approx -0.94$ (GloVe) और $-0.83$ (SIFT) है।
इसके विपरीत, ग्राफ-आधारित और ट्री-आधारित बेसलाइन सब-लीनियर स्केलिंग ( $\alpha_N$ का रेंज $-0.44 $से$ -0.59$) प्रदर्शित करते हैं।
निहितार्थ: जबकि ग्राफ विधियों की तुलना में $N$ बढ़ने पर मल्टीप्रोब ग्रिड का थ्रूपुट तेजी से घटता है, यह एल्गोरिदम के डिज़ाइन का एक यांत्रिक परिणाम है (कैंडिडेट काउंट $N$ के साथ रैखिक रूप से बढ़ता है)।

3. $d$ -स्केलिंग: एक महत्वपूर्ण क्रॉसओवर

GloVe एम्बेडिंग फैमिली पर एक पहले से अनरिपोर्टेड $-d$ -स्केलिंग क्रॉसओवर देखा गया है।

बेसलाइन्स: जैसे-जैसे आयाम $d$ बढ़ता है, ग्राफ, ट्री और पार्टिशनिंग विधियों का थ्रूपुट काफी घट जाता (तीव्र $\alpha_d$ ), जो "डायमेंशनलिटी का अभिशाप" (curse of dimensionality) और उच्च आयामों में ज्यामितीय छंटनी (geometric pruning) की विफलता को दर्शाता है।
मल्टीप्रोब ग्रिड: $d$ बढ़ने पर स्केलिंग एक्सपोनेंट $\alpha_d$ अपेक्षाकृत फ्लैट और अनुकूल रहता है।
तंत्र: एक निम्न-आयामी PCA सबस्पेस ( $m \ll d$ ) में सेल चयन करके और ग्रिड पैरामीटर्स ( $m, G$ ) को $d$ और लक्षित रिकॉल के आधार पर अनुकूलित करके, एल्गोरिदम पूर्ण उच्च-आयामी स्थान को पार करने से बचता है। री-रैंकिंग लागत केवल कैंडिडेट काउंट के साथ रैखिक रूप से बढ़ती है, जो पूर्ण $d$ -आयामी स्थान को पार करने वाली विधियों के लागत विकास की तुलना में कम आक्रामक है।

4. कुल लागत और इंडेक्सिंग दक्षता

यह पेपर कुल लागत $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ का विश्लेषण करता है, जहाँ $I$ इंडेक्सिंग लागत, $C$ कंप्यूट लागत और $M$ मेमोरी फुटप्रिंट है।

इंडेक्सिंग स्पीड: मल्टीप्रोब ग्रिड बेसलाइनों की तुलना में बनाने में काफी तेज़ है। $N = 1.18 \times 10^6$ पर, यह Voyager के 1,569 सेकंड की तुलना में केवल 4–36 सेकंड में इंडेक्स बनाता है।
क्वेरी लेटेंसी: मल्टीप्रोब ग्रिड की प्रति-क्वेरी लेटेंसी अधिक है (उच्च रिकॉल पर Voyager से लगभग 120 $\times$ धीमी)।
प्रतिस्पर्धी शासन (Competitive Regime): यह विधि तब प्रतिस्पर्धी हो जाती है जब रीबिल्ड-टू-क्वेरी अनुपात ( $f_I/f_C$ ) अधिक होता है। विशेष रूप से, यदि एक इंडेक्स को लगभग 2,600–20,400 क्वेरीज में से एक बार बनाया जाता है, तो मल्टीप्रोब ग्रिड कम कुल लागत प्रदान करता है। यह इसे "रीबिल्ड-हैवी" परिदृश्यों के लिए उपयुक्त बनाता है।

महत्व और दावे

यह पेपर दावा करता है कि ग्रिड-आधारित विधियाँ, जिन्हें अक्सर आधुनिक स्केलिंग विश्लेषणों में अनदेखा किया जाता है, विशिष्ट शासन में एक विशिष्ट और प्रतिस्पर्धी सेट ऑफ ट्रेड-ऑफ पेश करती हैं:

डायमेंशनल रोबस्टनेस (आयामी मजबूती): मल्टीप्रोब ग्रिड उच्च-आयामी सेटिंग्स में अद्वितीय रूप से मजबूत है जहाँ ज्यामितीय छंटनी विफल हो जाती है, और यह ग्राफ और ट्री विधियों से बेहतर प्रदर्शन करता है।
कम इंडेक्सिंग ओवरहेड: एल्गोरिदम जटिल, डेटा-निर्भर ग्राफ निर्माण की आवश्यकता वाले ग्राफ-आधारित तरीकों की तुलना में लगभग तत्काल इंडेक्सिंग प्रदान करता है।
ट्रांसफॉर्मर के लिए प्रासंगिकता: सेल्फ-अटेंशन को एक ANN ऑपरेशन के रूप में औपचारिक रूप दिए जाने के कारण, ANN एल्गोरिदम के $N$ $N$ - और $d$ $d$ -स्कीलिंग गुण ट्रांसफार्मर दक्षता के लिए सीधे प्रासंगिक हैं। लेखक सुझाव देते हैं कि मल्टीप्रोब ग्रिड उन ट्रांसफार्मर आर्किटेक्चर में फायदेमंद हो सकता है जहाँ:
- कॉन्टेक्स्ट लेंथ ( $N$ ) या हेड डायमेंशन ( $d$ ) बदलता है।
- इन्क्रीमेंटल अपडेट्स (जैसे, KV-कैशे का विस्तार करना) बार-बार होते हैं, क्योंकि एक ग्रिड में टोकन जोड़ने के लिए केवल एक सिंगल सेल असाइनमेंट की आवश्यकता होती है, न कि पूर्ण ग्राफ रीबिल्ड की।
कुल लागत परिप्रेक्ष्य: पेपर का तर्क है कि ANN विधि का चयन केवल क्वेरी लेटेंसी पर निर्भर नहीं होना चाहिए, बल्कि इसमें इंडेक्सिंग फ्रीक्वेंसी और रीबिल्ड लागत सहित कुल लागत फंक्शन पर भी विचार किया जाना चाहिए। उच्च-रीबिल्ड परिदृश्यों में, ग्रिड विधियों की कम इंडेक्सिंग लागत उनकी उच्च क्वेरी लेटेंसी की भरपाई कर सकती है।

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