🤖 machine learning

Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection

यह शोध पत्र Prof-K को पेश करता है, जो एक तेज़, स्केलेबल और वितरण-अज्ञेय (distribution-agnostic) वन-पास एल्गोरिदम है जो उच्च संभाव्यता के साथ शुद्धता की गारंटी देने के लिए संभाव्य नमूनाकरण (probabilistic sampling) का उपयोग करता है और मौजूदा विधियों की तुलना में महत्वपूर्ण गति प्राप्त करता है, विशेष रूप से बड़े पैमाने के परिदृश्यों में।

मूल लेखक: Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski, Jacek Tabor, Marcin Mazur

प्रकाशित 2026-08-14

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

CC BY 4.0

मूल लेखक: Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski, Jacek Tabor, Marcin Mazur

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

कल्पना कीजिए कि आप अरबों किताबों वाली एक विशाल, अराजक लाइब्रेरी के सामने खड़े हैं। आपको उन सभी को पढ़ने की ज़रूरत नहीं है; आपको बस एक विशेष डिस्प्ले शेल्फ पर रखने के लिए सबसे दिलचस्प 100 किताबें ढूँढनी हैं। कंप्यूटर विज्ञान की दुनिया में, इसे "टॉप-के सिलेक्शन" (Top-k selection) कहा जाता है। यह एक मौलिक कार्य है जो हर जगह होता है, इंटरनेट पर खोज परिणामों को व्यवस्थित करने से लेकर आर्टिफिशियल इंटेलिजेंस को यह तय करने में मदद करने तक कि किन विचारों पर ध्यान केंद्रित करना है और किन्हें अनदेखा करना है। जैसे-जैसे हमारा डिजिटल डेटा सूचना के पहाड़ों में बदल रहा है, इन "शीर्ष" वस्तुओं को खोजने का काम करने वाले कंप्यूटर अभिभूत होते जा रहे हैं। पारंपरिक तरीके पूरी तरह से सुनिश्चित होने के लिए हर एक किताब को छाँटने की कोशिश करते हैं, जो धीमा और थकाऊ है। अन्य तरीके पैटर्न के आधार पर अंदाज़ा लगाने की कोशिश करते हैं कि कौन सी किताबें अच्छी हैं, लेकिन उन्हें अजीब या चालाकी भरे डेटा से धोखा दिया जा सकता है। बड़ा सवाल वैज्ञानिकों के लिए यह है: हम शोर में खोए बिना या गलतियाँ किए बिना तेज़ी से सबसे अच्छी वस्तुओं को कैसे ढूँढ सकते हैं?

यहाँ आता है प्रोफ-के (Prof-K), एक नई विधि जिसे जेगिलोनिअन यूनिवर्सिटी के शोधकर्ता ताडेउज़ ज़ियार्मागा (Tadeusz Dziarmaga) और उनकी टीम ने पेश किया है। प्रोफेसर-के को एक चतुर, सुपर-फास्ट लाइब्रेरियन के रूप में समझें जो हर किताब को पढ़ने की कोशिश नहीं करता। इसके बजाय, लाइब्रेरियन लाइब्रेरी का "वाइब" (vibe) लेने के लिए अलमारियों से किताबों का एक छोटा सा, रैंडम हाथ थाम लेता है। इस छोटे से नमूने के आधार पर, वे गुणवत्ता का एक "कटऑफ लाइन" (सीमा रेखा) निर्धारित करते हैं। फिर, वे पूरी लाइब्रेरी के माध्यम से एक ही बार में, बिजली की गति से एक चक्कर लगाते हैं, केवल उन किताबों को उठाते हैं जो स्पष्ट रूप से उस रेखा से ऊपर हैं और बाकी को छोड़ देते हैं। प्रोफेसर-के का जादू यह है कि यह गणित का उपयोग करके यह सिद्ध करता है कि, बहुत उच्च संभावना के साथ, वास्तविक "शीर्ष 100" किताबें लगभग निश्चित रूप से उस छोटी सी ढेरी में होंगी, भले ही लाइब्रेरी में अजीब, अप्रत्याशित या "एडवर्सरियल" (adversarial) सामग्री वाली किताबें हों।

शोधकर्ताओं ने पाया कि यह दृष्टिकोण अविश्वसनीय रूप से कुशल है। अपने परीक्षणों में, प्रोफेसर-के उन अत्यधिक अनुकूलित मानक उपकरणों की तुलना में 1.5 से 10 गुना तेज़ था जिनका वर्तमान में कंप्यूटरों द्वारा उपयोग किया जाता है (जैसे PyTorch का topk और एक टूल जिसका नाम RadiK है)। सबसे बड़ी जीत तब हुई जब लाइब्रेरी बहुत बड़ी थी (अरबों आइटम) लेकिन रखी जाने वाली वस्तुओं की संख्या अपेक्षाकृत कम थी। पुराने तरीके जो शायद विफल हो जाते यदि डेटा अव्यवस्थित या विषम होता, प्रोफेसर-के के गारंटीदार परिणाम डेटा के वितरण के बावजूद सही रहते हैं। यह एक ऐसे फिल्टर की तरह है जो उतना ही अच्छा काम करता है चाहे किताबें करीने से व्यवस्थित हों या ढेर में फेंकी गई हों।

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

यह पेपर इस फिल्टर को सेट करने के लिए एक गणितीय "रेसिपी" भी प्रदान करता है। शोधकर्ताओं ने गणना की कि प्रारंभिक रैंडम सैंपल का आदर्श आकार धीरे-धीरे बढ़ता है—विशेष रूप से, यह कुल आइटमों के घनमूल (cube root) और आपके पास रखने योग्य आइटमों की संख्या के गुणनफल के रूप में स्केल करता है। इसका मतलब है कि एक अरब किताबों वाली लाइब्रेरी के लिए भी, आपको एक विश्वसनीय कटऑफ सेट करने के लिए केवल एक बहुत छोटे हिस्से (उनके उदाहरण में लगभग 4,600 किताबें) को देखने की आवश्यकता है। यदि फिल्टर गलती से बहुत अधिक या बहुत कम किताबें अंदर आने देता है, तो सिस्टम के पास एक सुरक्षा जाल है: यह तुरंत धीमी, सटीक विधि पर वापस स्विच कर सकता है ताकि यह सुनिश्चित हो सके कि कुछ भी छूटा नहीं है।

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

तकनीकी सारांश: Prof-K – कुशल Top-k चयन के लिए संभाव्यता-आधारित एक-पास फ़िल्टरिंग (Probabilistic One-Pass Filtering)

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

Top-k चयन डेटाबेस, सूचना पुनर्प्राप्ति (information retrieval), और आधुनिक मशीन लर्निंग (जैसे, स्पार्स एक्टिवेशन, अटेंशन प्रूनिंग) में एक मौलिक प्रिमिटिव है। जैसे-जैसे टेंसर का आकार ( $N$ ) बढ़ता है, विशेष रूप से बड़े पैमाने के GPU वर्कलोड में, सटीक top-k चयन की लागत एक बाधा बन जाती है। यह विशेष रूप से बड़े- $N$ , छोटे-से-मध्यम- $k$ शासन (regime) में सबसे अधिक तीव्र होता है, जहाँ केवल तत्वों का एक बहुत छोटा हिस्सा ही रखा जाता है।

मौजूदा सटीक विधियाँ (सॉर्टिंग, हीप्स, पार्टिशनिंग) किए गए कंप्यूटेशन के सापेक्ष उच्च मेमोरी मूवमेंट और सिंक्रोनाइज़ेशन लागतों का सामना करती हैं। जबकि अनुमानित (approximate) विधियाँ मौजूद हैं, वे अक्सर नाजुक ह्यूरिस्टिक्स पर निर्भर करती हैं या विशिष्ट इनपुट वितरणों (जैसे, सुव्यवस्थित डेटा) को मानती हैं, जो उन्हें भारी-पूंछ (heavy-tailed) या प्रतिकूल (adversarial) इनपुट के तहत अविश्वसनीय बनाती हैं। चुनौती वितरण परिवर्तनों (distribution shifts) के प्रति शुद्धता की गारंटी या मजबूती से समझौता किए बिना top-k चयन के कम्प्यूटेशनल ओवरहेड को कम करने की है।

2. कार्यप्रणाली: Prof-K एल्गोरिदम (Methodology: The Prof-K Algorithm)

Prof-K एक संभाव्यता-आधारित एक-पास फ़िल्टरिंग एल्गोरिदम है जिसे सटीक top-k चयन के लिए खोज स्थान (search space) को कम करने के लिए डिज़ाइन किया गया है। यह चार चरणों में कार्य करता है:

सैंपलिंग (Sampling): $N$ इनपुट तत्वों में से बिना प्रतिस्थापन (without replacement) के आकार $S$ का एक छोटा, समान यादृच्छिक नमूना लिया जाता है।
थ्रेशोल्ड अनुमान (Threshold Estimation): नमूने में प्राप्त मानों को सॉर्ट किया जाता है, और एक विशिष्ट रैंक $t$ के आधार पर एक थ्रेशोल्ड $\tau$ चुना जाता है। यह थ्रेशोल्ड पूर्ण जनसंख्या के $(k/N)$ -क्वांटाइल के एक रूढ़िवादी अनुमान के रूप में कार्य करता है।
फ़िल्टरिंग (एक-पास) (Filtering - One-Pass): पूरे इनपुट टेंसर को एक बार स्ट्रीम किया जाता है। कोई भी तत्व $x_i \ge \tau$ को आकार $M$ के एक कॉम्पैक्ट कैंडिडेट बफर में रखा जाता है (जहाँ $M$ , $k$ का एक छोटा गुणक है)। $\tau$ से नीचे के तत्वों को हटा दिया जाता है।
रिफाइनमेंट (Refinement): अंतिम परिणाम उत्पन्न करने के लिए केवल रिटेन किए गए उम्मीदवारों (retained candidates) पर एक सटीक top-k रूटीन चलाया जाता है।

फ़ालबैक तंत्र (Fallback Mechanism): यदि बफर ओवरफ्लो हो जाता है (यदि $M$ से अधिक तत्व फ़िल्टर पास करते हैं) या यदि $k$ से कम तत्व रिटेन किए जाते हैं, तो एल्गोरिदम पूर्ण इनपुट पर एक मानक सटीक top-k कंप्यूटेशन पर फ़ालबैक करता है।

सैद्धांतिक गारंटी और पैरामीटर चयन (Theoretical Guarantees and Parameter Selection)

मुख्य अंतर्दृष्टि यह है कि नमूना-आधारित थ्रेशोल्ड की रैंक एक निगेटिव हाइपरजियोमेट्रिक वितरण (negative hypergeometric distribution) का पालन करती है, जो केवल रैंक पर निर्भर करती है, मानों पर नहीं। यह Prof-K को वितरण-अज्ञेय (distribution-agnostic) गारंटी प्रदान करने की अनुमति देता है।

लेखक यह सुनिश्चित करने के लिए मापदंडों $(S, t, M)$ के लिए स्पष्ट सूत्र व्युत्पन्न करते हैं कि कुल विफलता की संभावना एक उपयोगकर्ता-निर्दिष्ट $\epsilon$ द्वारा सीमित हो:

रिकॉल विफलता ( $R < k$ ): $t$ को इस तरह चुनने से नियंत्रित होता है कि थ्रेशोल्ड रूढ़िवादी रूप से कम रहे।
बफर ओवरफ्लो ( $R > M$ ): इसे बफर क्षमता $M$ को पर्याप्त रूप से बड़ा सेट करके नियंत्रित किया जाता है।

कुल कम्प्यूटेशनल ओवरहेड (सैंपलिंग लागत + रिफाइनमेंट लागत) को कम करने के लिए इष्टतम नमूना आकार $S^*$ व्युत्पन्न किया गया है। स्पार्स शासन (sparse regime) में ( $k \ll N$ ), इष्टतम नमूना आकार:
$S^* \propto (kN)^{1/3}$
यह स्केलिंग $N$ या $k$ में रैखिक वृद्धि की तुलना में काफी धीमी है, जिसका अर्थ है कि सैंपलिंग ओवरहेड विशाल टेंसरों के लिए भी नगण्य रहता है।

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

वितरण-अज्ञेय शुद्धता (Distribution-Agnostic Correctness): क्वांटाइल-अनुमान विधियों के विपरीत जो विशिष्ट डेटा वितरणों को मानती हैं, Prof-K केवल यूनिफॉर्म सैंपलिंग के कॉम्बिनेटोरियल गुणों के आधार पर संभाव्यता-आधारित शुद्धता गारंटी प्रदान करता है। यह हेवी-टेल्ड और एडवर्सरियल इनपुट के विरुद्ध मजबूत बना रहता है।
सीमित विफलता के साथ एक-पास फ़िल्टरिंग (One-Pass Filtering with Bounded Failure): एल्गोरिदम $N$ तत्वों के चयन की समस्या को एक छोटे बफर आकार $M \approx k$ तक कम कर देता है, जिसमें विफलता की गणितीय रूप से सीमित संभावना ( $\le \epsilon$ ) होती है।
इष्टतम पैरामीटर स्केलिंग (Optimal Parameter Scaling): पेपर सैंपलिंग की लागत और कैंडिडेट बफर को रिफाइन करने की लागत के बीच संतुलन बनाते हुए इष्टतम नमूना आकार $S^* \propto (kN)^{1/3}$ के लिए एक सैद्धांतिक व्युत्पत्ति प्रदान करता है।
लचीला सटीकता-गति ट्रेड-ऑफ (Flexible Accuracy-Speed Trade-off): उपयोगकर्ता सख्त शुद्धता और अधिकतम गति के बीच ट्रेड-ऑफ करने के लिए विफलता बजट $\epsilon$ और बफर मल्टीप्लायर को ट्यून कर सकते हैं, जिसमें विफल होने पर सटीक कंप्यूटेशन के लिए गारंटीकृत फ़ालबैक शामिल है।

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

लेखकों ने सिंथेटिक बेंचमार्क और एक वास्तविक दुनिया के मशीन लर्निंग वर्कलोड पर Prof-K का मूल्यांकन किया।

सिंथेटिक बेंचमार्क (Synthetic Benchmarks)

स्पीडअप (Speedups): Prof-K ने अत्यधिक अनुकूलित बेसलाइन (PyTorch torch.topk और RadiK) पर 1.5 $\times$ से 10 $\times$ स्पीडअप प्राप्त किया।
प्रभावशीलता का शासन (Regime of Effectiveness): लाभ बड़े- $N$ , छोटे-से-मध्यम- $k$ शासन में सबसे अधिक स्पष्ट थे।
मेमोरी दक्षता (Memory Efficiency): रेडिक्स-आधारित विधियों (जैसे, RadiK) के विपरीत जिन्हें $O(N)$ सहायक स्थान की आवश्यकता होती है, Prof-K का मेमोरी फुटप्रिंट बफर आकार $M$ द्वारा सीमित है, जो विशाल एरेज़ पर आउट-ऑफ-मेमोरी (OOM) त्रुटियों को रोकता है।
मजबूती (Robustness): प्रदर्शन यूनिफॉर्म, नॉर्मल और हेवी-टेल्ड पारेटो (Pareto) वितरणों के बीच अपरिवर्तित रहा।

वास्तविक दुनिया का अनुप्रयोग: बैचटॉपके स्पार्स ऑटोएनकोडर्स (BatchTopK Sparse Autoencoders - SAEs)

लेखकों ने BatchTopK स्पार्स ऑटोएनकोडर्स के ट्रेनिंग लूप में Prof-K को एकीकृत किया, जहाँ top-k चयन एक आवर्ती बाधा है।

सेटअप: Pythia-70m मॉडल के साथ OpenWebText पर ट्रेनिंग, जिसमें डिक्शनरी का आकार 12,288 और बैच साइज 4,096 ( $N \approx 50$ मिलियन) है।
कर्नेल स्पीडअप (Kernel Speedup): टॉप-के कर्नेल रनटाइम ~2.56 ms से घटकर ~1.13 ms (2.27 $\times$ स्पीडअप) हो गया।
एंड-टू-एंड प्रभाव (End-to-End Impact): कुल ट्रेनिंग स्टेप समय ~30.73 ms से घटकर ~29.42 ms हो गया, जिससे कुल ट्रेनिंग समय में 1.044 $\times$ (4.25%) की कमी आई।
गुणवत्ता संरक्षण (Quality Preservation): मेट्रिक्स जिनमें नॉर्मलाइज्ड मीन स्क्वेर्ड एरर (NMSE), क्रॉस-एन्ट्रॉपी डिग्रेडेशन, और वेरिएंस एक्सप्लेंड शामिल हैं, ने torch.topk और Prof-K के बीच कोई मापने योग्य अंतर नहीं दिखाया। संभाव्यता-आधारित रिलैक्सेशन ने सीखे गए रिप्रेजेंटेशन या स्पार्सिटी व्यवहार को नहीं बदला।

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

पेपर का दावा है कि Prof-K बड़े पैमाने के स्पार्स मशीन लर्निंग वर्कलोड के लिए एक सिद्धांत-आधारित, सिस्टम-लेवल ऑप्टिमाइजेशन प्रदान करता है। इसका महत्व निम्नलिखित में निहित है:

स्केलेबिलिटी (Scalability): यह प्रभावी रूप से बड़े- $N$ शासन में top-k चयन के मेमोरी-बैंडविड्थ बॉटलनेक को संबोधित करता है जहाँ सटीक विधियाँ संघर्ष करती हैं।
मजबूती (Robustness): यह वितरण-स्वतंत्र गारंटी प्रदान करता है जो इनपुट वितरण के आधार पर नहीं बदलती है, जो व्यावहारिक रूप से सामना किए जाने वाले एडवर्सरियल या हेवी-टेल्ड डेटा के लिए एक महत्वपूर्ण विशेषता है।
व्यावहारिक उपयोगिता (Practical Utility): यह प्रदर्शित करता है कि रिकॉल लक्ष्य (जैसे, एक छोटी विफलता संभावना स्वीकार करना) को कम करने से डाउनस्ट्रीम कार्यों (जैसे SAE ट्रेनिंग) की गुणवत्ता से समझौता किए बिना पर्याप्त स्पीडअप मिलता है।

लेखक निष्कर्ष निकालते हैं कि हालांकि उनके विशिष्ट SAE प्रयोग में एंड-टू-एंड स्पीडअप मामूली (~4%) था, लेकिन top-k प्रिमिटिव की लागत में कमी महत्वपूर्ण है। वे तर्क देते हैं कि बड़े मॉडलों या लंबे प्रशिक्षण चक्रों के लिए, ये बचत महत्वपूर्ण वॉल-क्लॉक टाइम रिडक्शन में बदल जाएगी, जिससे संभाव्यता-आधारित फ़िल्टरिंग सटीक चयन के एक व्यवहार्य और मजबूत विकल्प के रूप में स्थापित होगी।