🤖 machine learning

Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret

यह शोध पत्र फ़िल्टर्ड अनुमानित-निकटतम-पड़ोसी (approximate-nearest-neighbor) प्रश्नों में चयनात्मकता-अनुमान त्रुटियों (selectivity-estimation errors) को एक चरण संक्रमण (phase transition) घटना के रूप में अभिलक्षित करता है, जो यह प्रदर्शित करता है कि निष्पादन योजना पछतावा (execution plan regret) उन महत्वपूर्ण सीमा क्षेत्रों में केंद्रित है जहाँ रणनीति प्रदर्शन की ढलानें (performance cliffs) घटित होती हैं, और कि ये त्रुटियाँ कॉर्पस के आकार से स्वतंत्र सार्वभौमिक परिमित-आकार स्केलिंग नियमों (universal finite-size scaling laws) का पालन करती हैं।

मूल लेखक: Madhulatha Mandarapu, Sandeep Kunkunuru

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

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

CC BY 4.0

मूल लेखक: Madhulatha Mandarapu, Sandeep Kunkunuru

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

कल्पना कीजिए कि आप लाखों किताबों (वेक्टर्स) के साथ एक विशाल पुस्तकालय चला रहे हैं। एक ग्राहक आता है और आपसे एक विशिष्ट विषय पर 10 सबसे अच्छी किताबें मांगता है, लेकिन एक शर्त के साथ, वे केवल वही किताबें चाहते हैं जो एक निश्चित नियम को पूरा करती हों, जैसे कि "2020 के बाद प्रकाशित" या "$10 से कम कीमत वाली।"

यह एक फिल्टर्ड ANN क्वेरी (Filtered ANN query) है। इस पुस्तकालय के पास इन किताबों को खोजने के तीन मुख्य तरीके हैं:

प्री-फिल्टर (Pre-filter): पहले, उन सभी किताबों को हटा दें जो नियम को पूरा नहीं करती हैं, फिर शेष बची हुई ढेर से सबसे अच्छी 10 किताबें खोजें।
पोस्ट-फिल्टर (Post-filter): पूरी लाइब्रेरी में सबसे अच्छी 10 किताबें खोजें, फिर उन किताबों को हटा दें जो नियम को पूरा नहीं करती हैं।
इन-फिल्टर (In-filter): सावधानी से खोजें, जैसे-जैसे आप आगे बढ़ें, केवल उन्हीं किताबों को देखें जो नियम को पूरा करती हैं।

समस्या यह है कि: आपको कौन सा तरीका इस्तेमाल करना चाहिए?

यदि नियम बहुत सख्त है (जैसे, "एक विशिष्ट लेखक द्वारा लिखी गई किताबें जो 1900 में मर गया था"), तो केवल 0.1% किताबें ही पास होती हैं। प्री-फिल्टर सबसे अच्छा है क्योंकि यह बाकी लाइब्रेरी को अनदेखा करके समय बचाता है।
यदि नियम बहुत ढीला है (जैसे, "21वीं सदी में प्रकाशित पुस्तकें"), तो 90% पुस्तकें पास होती हैं। पोस्ट-फिल्टर सबसे अच्छा है क्योंकि आप हर किताब की जांच करने में समय बर्बाद नहीं करना चाहते; बस शीर्ष 10 किताबें लें और अंत में उन्हें चेक करें।
यदि नियम बीच का है, तो इन-फिल्टर आमतौर पर विजेता होता है।

पुस्तकालय प्रबंधक (सिस्टम) को यह अनुमान लगाना होता है कि नियम कितना सख्त है (इस अनुमान को सेलेक्टिविटी/selectivity कहा जाता है) और एक रणनीति चुननी होती है। यदि वह गलत अनुमान लगाता है, तो वह धीमा तरीका चुन सकता है, जिससे समय बर्बाद होगा और अच्छी किताबें छूट जाएंगी।

बड़ी खोज: यह गणित नहीं, मौसम की तरह है

इस शोध के लेखकों ने पाया कि यह केवल एक साधारण गणित की समस्या नहीं है; यह मौसम के पैटर्न की तरह है।

उन्होंने पाया कि "सर्वश्रेष्ठ रणनीति" विशिष्ट टिपिंग पॉइंट्स (tipping points) पर अचानक बदल जाती है, जिससे फेज (phases) बनते हैं (जैसे ठोस, तरल और गैस)।

फेज के गहराई में: यदि नियम बहुत सख्त है, तो प्री-फिल्टर अन्य तरीकों की तुलना में इतना बेहतर है कि भले ही प्रबंधक सख्ती का गलत अनुमान लगाए, फिर भी वह सही तरीका ही चुनेगा। यह भारी बारिश के समान है; भले ही आप अनुमान लगाएं कि बारिश 10% अधिक तेज है, फिर भी आप छाता लाना जानते हैं। कोई पछतावा नहीं (No regret)।
सीमा पर (The Cliff): यह वह जगह है जहाँ चीजें खतरनाक हो जाती हैं। यहाँ एक बहुत ही महीन रेखा है जहाँ प्री-फिल्टर और पोस्ट-फिल्टर लगभग समान रूप से अच्छे हैं। यदि प्रबंधक का अनुमान थोड़ा भी गलत होता है, तो वह "प्री-फिल्टर" से "पोस्ट-फिल्टर" पर कूद सकता है और गलत विकल्प चुन सकता है।

"रिग्रेट वेज" (The Regret Wedge)

पेपर इस खतरे वाले क्षेत्र को "रिग्रेट वेज" कहता है।

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

दो विशिष्ट "क्लिफ" (Two Specific Cliffs)

पेपर दो विशिष्ट स्थानों की पहचान करता है जहाँ ये क्लिफ होते हैं, जिसमें अन्य क्षेत्रों के अलग-अलग गणित का उपयोग किया गया है:

द पोस्ट-फिल्टर क्लिफ (The Post-Filter Cliff): यह तब होता है जब नियम इतना सख्त होता है कि पूरी लाइब्रेरी से निकाली गई "शीर्ष 10" किताबों में बहुत कम वैध किताबें होने की संभावना होती है। गणितीय रूप से, यह तब होता है जब सख्ती लगभग 10 / (कुल किताबें जो जांची गईं) होती है।
द इन-फिल्टर क्लिफ (The In-Filter Cliff): यह तब होता है जब नियम इतना सख्त होता है कि यदि आप केवल वैध किताबों के माध्यम से नेविगेट करने की कोशिश करते हैं, तो रास्ता टूट जाता है। यह एक ऐसे पुल की तरह है जहाँ यदि आप बहुत अधिक तख्ते हटा देते हैं, तो पुल ढह जाता है। पेपर ने पाया कि यह एक विशिष्ट बिंदु पर होता है (लगभग लाइब्रेरी मैप के कनेक्शनों में 0.83 विभाजित), चाहे आपकी लाइब्रेरी कितनी भी बड़ी क्यों न हो।

"यूनिवर्सल वेज" (The Universal Wedge)

सबसे आश्चर्यजनक खोज यह है कि यह "रिग्रेट वेज" स्केल-इनवेरिएंट (scale-invariant) है।
चाहे आपके पास 1,00,000 किताबें हों या 1 करोड़, यदि आप सीमा पर ज़ूम करते हैं और लाइब्रेरी के आकार और प्रबंधक की त्रुटि के लिए समायोजन करते हैं, तो "गिरावट" का आकार बिल्कुल वैसा ही दिखता है। यह एक सार्वभौमिक पैटर्न है।

वास्तविक समस्या: मैप, न कि अनुमान

लेखकों ने वास्तविक, अव्यवस्थित डेटा (केवल आदर्श गणित नहीं) पर इसका परीक्षण किया। उन्होंने दो प्रकार की विफलताएं पाईं:

द ट्रांजिएंट वेज (The Transient Wedge): यदि आपका अनुमान थोड़ा सा भी गलत है, तो आप ढलान से नीचे गिर जाएंगे। यह अपरिहार्य है लेकिन केवल उस सूक्ष्म सीमा क्षेत्र तक ही सीमित है।
द पर्सिस्टेंट बैंड (The Persistent Band): यदि आपका कॉस्ट मॉडल (cost model) (वह मैप जिसका उपयोग आप यह तय करने के लिए करते हैं कि कौन सी रणनीति "सस्ती" है) पक्षपाती या गलत है, तो यह विफलता का एक स्थायी क्षेत्र बनाता है। भले ही आपका अनुमान एकदम सटीक हो, फिर भी आप गलत रणनीति चुन सकते हैं क्योंकि आपका मैप गलत है। मैप के टूटे होने पर बेहतर अनुमान लगाने से कुछ नहीं बदलेगा।

सारांश

सिस्टम: वस्तुओं की एक फ़िल्टर्ड सूची को खोजने का तरीका चुनना।
घटना: यह एक फेज ट्रांजिशन (जैसे पानी का जमना) की तरह काम करता है।
खतरा: गलतियाँ केवल तभी होती हैं जब आप दो रणनीतियों के बीच की सीमा पर खड़े होते हैं।
आकार: खतरा क्षेत्र एक "वेज" है जो आपकी डेटा के आकार के बावजूद एक जैसा ही रहता है।
सबक: आप केवल बेहतर अनुमान लगाकर एक खराब रणनीति चयन को ठीक नहीं कर सकते। यदि आपका "लागत" (cost) का मूल मॉडल पक्षपाती है, तो आपके पास हमेशा विफलता का एक क्षेत्र रहेगा जिसे अनुमान की त्रुटियां भी ठीक नहीं कर सकतीं।

यह पेपर कोई नया सर्च इंजन नहीं बना रहा है; यह केवल एक नक्शा खींच रहा है जो दिखाता है कि वर्तमान सर्च इंजन कहाँ और क्यों भ्रमित होते हैं, और यह सिद्ध करता है कि खतरा छोटे, महत्वपूर्ण क्षेत्रों में केंद्रित है।

तकनीकी सारांश: एक चरण संक्रमण (Phase Transition) के रूप में फ़िल्टर्ड ANN

समस्या विवरण
प्रोडक्शन वेक्टर सर्च में, क्वेरीज़ को अक्सर एक एट्रिब्यूट प्रेडिकेट $P$ (जैसे category='shoes') के अधीन $k$ निकटतम पड़ोसियों (nearest neighbors) को खोजने की आवश्यकता होती है। यह एक फ़िल्टर्ड एप्रोक्सिमेट नियरएस्ट नेबर (ANN) समस्या है। निष्पादन रणनीति (execution strategy) प्रेडिकेट की चयनात्मकता (selectivity) $s$ (वह अंश जो $P$ को संतुष्ट करता है) पर अत्यधिक निर्भर करती है। तीन प्राथमिक रणनीतियाँ मौजूद हैं:

प्री-फ़िल्टर (Pre-filter): $P$ द्वारा संतुष्ट होने वाले उपसमुच्चय $X_P$ को मैटेरियलाइज़ करें, और फिर उसके भीतर खोज करें। कम चयनात्मकता पर इष्टतम।
पोस्ट-फ़िल्टर (Post-filter): पूरे कॉर्पस पर एक अनफ़िल्टर्ड ANN खोज चलाएं और $P$ का उल्लंघन करने वाले परिणामों को हटा दें। उच्च चयनात्मकता पर इष्टतम।
इन-फ़िल्टर (In-filter): खोज के दौरान $P$ का सम्मान करते हुए इंडेक्स को नेविगेट करें। मध्यवर्ती शासन (intermediate regime) को लक्षित करता है।

इष्टतम रणनीति चुनने के लिए सिस्टम को $s$ का अनुमान लगाना चाहिए। हालाँकि, अनुमान त्रुटियाँ "प्लान रिग्रेट" (plan regret) की ओर ले जाती हैं—जो कि एक ऐसे ऑरेकल (oracle) की तुलना में रिकॉल (recall) की हानि है जो वास्तविक $s$ को जानता है। शोध इस बात की जांच करता है कि यह रिग्रेट मात्रात्मक रूप से कैसा है: विशेष रूप से, अनुमान त्रुटियाँ प्रदर्शन को कब और कितनी गंभीरता से कम करती हैं, और क्या यह व्यवहार कॉर्पस के आकार के across सार्वभौमिक (universal) है।

कार्यप्रणाली और मॉडल
लेखक रणनीति चयन को एक फेज ट्रांजिशन सिस्टम (phase-transition system) के रूप में मॉडल करते हैं।

ऑर्डर पैरामीटर (Order Parameter): चयनात्मकता $s$ ।
फेज़ (Phases): वे क्षेत्र जहाँ प्री-फ़िल्टर, पोस्ट-फ़िल्टर, या इन-फ़िल्टर रणनीतियाँ हावी होती हैं।
बाउंड्रीज़ (Boundaries): वे महत्वपूर्ण बिंदु जहाँ इष्टतम रणनीति बदल जाती है।

अध्ययन रिग्रेट ( $\Delta R$ ) को इष्टतम रणनीति और अनुमानित रणनीति (जिसमें मल्टीप्लिकेटिव एरर $Q$ है, जहाँ $\hat{s} = s \cdot Q$ ) के बीच रिकॉल@k के अंतर के रूप में परिभाषित करता है। विश्लेषण एक "प्रतिस्पर्धी शासन" (contested regime) पर केंद्रित है जहाँ कंप्यूट बजट $B$ सीमित है ( $B < \sqrt{kn}$ ), जिसका अर्थ है कि कोई भी एकल रणनीति सभी चयनात्मकताओं के लिए पूर्ण नहीं है।

सैद्धांतिक व्युत्पत्ति स्वतंत्र गणितीय ढाँचों का उपयोग करके फेज बाउंड्रीज़ का स्थान निर्धारित करती है:

पोस्ट-फ़िल्टर क्लिफ (Post-filter Cliff): ऑर्डर स्टैटिस्टिक्स (order statistics) से व्युत्पन्न। संक्रमण वहां होता है जहाँ शीर्ष- $K$ उम्मीदवारों में अपेक्षित पात्र आइटम $k$ के बराबर होते हैं, जिससे $s \approx k/K$ पर एक सीमा प्राप्त होती है।
इन-फ़िल्टर क्लिफ (In-filter Cliff): ज्यामितिक ग्राफ पर साइट परकोलेशन (site percolation) से व्युत्पन्न। संक्रमण वहां होता है जहाँ पात्र नोड्स का ग्राफ अपने विशाल जुड़े घटक (giant connected component/navigability) को खो देता है, जिससे $s_c \approx 0.83/M$ (जहाँ $M$ ग्राफ डिग्री है) पर एक सीमा प्राप्त होती है, जो कॉर्पस आकार $n$ से स्वतंत्र है।

मुख्य योगदान

बंद-रूप सीमाओं (Closed-Form Boundaries) के साथ फेज डायग्राम: पेपर स्थापित करता है कि रणनीति चयन का परिदृश्य दो विशिष्ट सीमाओं द्वारा नियंत्रित होता है: $s \approx k/K$ (ऑर्डर स्टैटिस्टिक्स) और $s_c \approx 0.83/M$ (परकोलेशन)।
क्रिटिकैलिटी लॉ (फ्लिप-मार्जिन): लेखक सिद्ध करते हैं कि रिग्रेट क्रिटिकल है, जिसका अर्थ है कि यह फेज़ के भीतर गहरा होने पर नगण्य होता है लेकिन सीमाओं पर तीव्रता से केंद्रित होता है।
- "फ्लिप-मार्जिन" (वह क्षेत्र जहाँ एक त्रुटि गलत निर्णय का कारण बनती है) की लॉग-चौड़ाई अनुमान त्रुटि $\epsilon$ के बराबर होती है।
- रिग्रेट की ऊंचाई स्थानीय ढलान (local slope) $|V'(s^*)| \epsilon$ के समानुपाती होती है।
- व्युत्क्रम ढलान $1/|V'(s^*)|$ निर्णय के लिए एक कंडीशन नंबर (condition number) के रूप में कार्य करता है।
फाइनाइट-साइज़ स्केलिंग कोलैप्स (Finite-Size Scaling Collapse): प्रयोगों के माध्यम से, लेखक प्रदर्शित करते हैं कि जब रिग्रेट कर्व्स को अनुमान त्रुटि $\epsilon$ और बाउंड्री स्लोप $|V'(s^*)|$ द्वारा पुन: स्केल किया जाता है, तो वे दो दशकों के कॉर्पस आकार ( $n$ ) में एक एकल सार्वभौमिक वेज (universal wedge) पर कोलैप्स हो जाते हैं। यह इंगित करता है कि चयन रिग्रेट स्केल-इनवेरिएंट (scale-invariant) है।
मॉडल मिसमैच विश्लेषण: अध्ययन दो विफलता मोड के बीच अंतर करता है:
- ट्रांजिएंट वेज (Transient Wedge): अनुमान शोर (estimation noise) के कारण होने वाला रिग्रेट, जो गायब हो जाता है यदि अनुमान सटीक हो।
- पर्सिस्टेंट मिसकैलिब्रेशन बैंड (Persistent Miscalibration Band): एक पक्षपाती लागत मॉडल (biased cost model) के कारण होने वाला रिग्रेट (जैसे, गलत लागत धारणाएँ)। यह एक निरंतर रिग्रेट बैंड बनाता है जिसे अनुमान-त्रुटि मजबूती (estimation-error robustness) ठीक नहीं कर सकती।

प्रायोगिक परिणाम
परिकल्पों को सिंथेटिक गॉसियन कॉर्पस और वास्तविक दुनिया के SIFT1M डेटासेट पर प्री-रजिस्टर्ड निर्णय नियमों के तहत सत्यापित किया गया।

रिग्रेट का संकेंद्रण (Concentration of Regret): रिग्रेट बाउंड्री पर अत्यधिक केंद्रित है, जो फेज़ के इंटीरियर की तुलना में $\sim 290\times$ वृद्धि दिखाता है।
स्केलिंग कोलैप्स: डेटा को पुन: स्केल करने से पुष्टि हुई कि विभिन्न कॉर्पस आकार और त्रुटि परिमाणों के रिग्रेट कर्व्स एक ही यूनिवर्सल कर्व पर कोलैप्स हो जाते हैं, जो स्केल-इनवेरिएंस दावे को मान्य करता है।
परकोलेशन थ्रेशोल्ड: ग्राफ कनेक्टिविटी पर प्रयोगों ने पुष्टि की कि इन-फ़िल्टर क्लिफ $s_c \approx 0.83/M$ पर होता है, जो लोक-कथा (folklore) $O(\log n / M)$ बाउंड को परिष्कृत करता है।
वास्तविक इंडेक्स व्यवहार: एक वास्तविक अनुमानित HNSW इंडेक्स एनालिटिक बाउंड को करीब से ट्रैक करता है। हालाँकि, एक पक्षपाती लागत मॉडल (जैसे, लागत अनुमान में $\pm 30\%$ की त्रुटि) पेश करने से एक निरंतर रिग्रेट बैंड खुल जाता है जिसे अनुमान-त्रुटि शमन (mitigation) हल नहीं कर सकता है।

महत्व और दावे
पेपर स्पष्ट रूप से अपने योगदान को एक नए इंडेक्स, प्लानर या एल्गोरिदम के बजाय एक समस्या के चरित्रांकन (characterization) के रूप में फ्रेम करता है।

मामूली नवीनता (Modest Novelty): लेखक स्वीकार करते हैं कि तीन रणनीतियाँ, "मिडल रिजीम", और थ्रेशोल्ड का उपयोग पूर्ववर्ती कार्यों में स्थापित है।
वैचारिक अंतर (Conceptual Delta): नवीनता चयन रिग्रेट की मात्रात्मक क्रिटिकैलिटी में निहित है। पेपर एक सटीक "फ्लिप-मार्जिन" लॉ (कंडीशन नंबर) प्रदान करता है और फाइनाइट-साइज़ स्केलिंग के माध्यम से रिग्रेट के स्केल-इनवेरिएंस को प्रदर्शित करता है।
व्यावहारिक अंतर्दृष्टि: मुख्य निष्कर्ष यह है कि अनुमान शोर के प्रति मजबूती केवल महत्वपूर्ण सीमाओं के पास आवश्यक है। अधिक महत्वपूर्ण, अनफिक्सेबल जोखिम कॉस्ट-मॉडल कैलिब्रेशन है; यदि कॉस्ट मॉडल पक्षपाती है, तो सिस्टम सटीक प्रति-क्वेरी अनुमान के बावजूद निरंतर रिग्रेट का शिकार होगा।

यह कार्य वेक्टर सर्च प्लानर्स के विफल होने के कारणों और कब ऐसा होता है, इसे समझने के लिए एक सैद्धांतिक और अनुभवजन्य लेंस के रूप में कार्य करता है, इस बात पर जोर देता है कि "खतरा क्षेत्र" सामान्य अनुमान शोर के बजाय संरचनात्मक रूप से फेज बाउंड्रीज़ द्वारा परिभाषित है।