🤖 machine learning

LoRe: Adaptive Interaction-Evaluation Routing with Per-Step Interaction Budgets for Iterative Graph Solvers

LoRe एक प्रशिक्षण-मुक्त (training-free), इन्फरेंस-टाइम रैपर है जो उच्च-संघर्ष (high-conflict) या उच्च-अनिश्चितता (high-uncertainty) वाले किनारों (edges) पर प्रति-चरण इंटरैक्शन मूल्यांकन को गतिशील रूप से रूट करके कॉम्बिनेटरियल ऑप्टिमाइज़ेशन के लिए डिफ्यूजन-आधारित न्यूरल सॉल्वर्स की स्केलेबिलिटी को बढ़ाता है, जिससे MIS और TSP जैसी बड़ी समस्याओं पर समाधान की गुणवत्ता को बनाए रखते हुए महत्वपूर्ण गति वृद्धि और मेमोरी में कमी प्राप्त होती है।

मूल लेखक: Jintao Li, Yong-Yi Wang, Zheng-An Wang, Heng Fan

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

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

CC BY 4.0

मूल लेखक: Jintao Li, Yong-Yi Wang, Zheng-An Wang, Heng Fan

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

कल्पना कीजिए कि आप एक बहुत बड़े, जटिल पहेली को हल करने की कोशिश कर रहे हैं, जैसे कि हजारों टुकड़ों को जोड़कर एक तस्वीर बनाना। कंप्यूटर विज्ञान की दुनिया में, इसे "कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन प्रॉब्लम" (combinatorial optimization problem) कहा जाता है। यह शोध पत्र LoRe (लोकल री-इवैल्यूएशन) नामक एक नई विधि पेश करता है जो कंप्यूटर को इन पहेलियों को बहुत तेज़ी से और बिना मेमोरी खत्म हुए हल करने में मदद करती है।

यहाँ LoRe कैसे काम करता है, सरल उपमाओं के माध्यम से समझाया गया है:

समस्या: "थका हुआ शेफ" (The Exhausted Chef)

कल्पना कीजिए कि एक मास्टर शेफ (कंप्यूटर सॉल्वर) एक शहर के लिए एक विशाल दावत बनाने की कोशिश कर रहा है।

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

प्रेरणा: भौतिकी से मदद (Physics to the Rescue)

लेखकों ने देखा कि भौतिक विज्ञानी (physicists) कणों के विशाल समूहों (जैसे धातु में इलेक्ट्रॉन) के साथ समस्याओं को कैसे हल करते हैं। उन्होंने महसूस किया कि आपको एक साथ हर कण के बीच की सटीक बातचीत (interaction) को कैलकुलेट करने की ज़रूरत नहीं है। इसके बजाय, आप केवल उन कणों के छोटे समूह पर ध्यान केंद्रित करते हैं जो आपस में टकरा रहे हैं ("हॉटस्पॉट्स") और बाकी कमरे को एक शांत बैकग्राउंड की तरह मानते हैं।

समाधान: LoRe (एक स्मार्ट मैनेजर)

LoRe एक स्मार्ट मैनेजर की तरह काम करता है जो शेफ को ठीक वही बताता है जो उसे करना है, मिनट-दर-मिनट, बिना शेफ को दोबारा प्रशिक्षित किए।

"क्लस्टर" (हॉटस्पॉट्स):
हर व्यंजन को चखने के बजाय, मैनेजर रसोई की ओर देखता है और कहता है, "अभी, सूप और स्टेक नमक के डिब्बे के लिए लड़ रहे हैं। वे हॉटस्पॉट्स हैं। केवल उन दोनों को चखो।"

पेपर में: इसे क्लस्टर (Cluster) कहा गया है। कंप्यूटर केवल पहेली के उन विशिष्ट हिस्सों के बीच की बातचीत की गणना करता है जो वर्तमान में संघर्ष या भ्रम पैदा कर रहे हैं।

"बाथ" (बैकग्राउंड):
बाकी 99% व्यंजनों का क्या जो पहले से ही परफेक्ट हैं? मैनेजर उन्हें पूरी तरह से नज़रअंदाज़ नहीं करता है। वह बस एक त्वरित, कम प्रयास वाला संकेत देता है: "बाकी सब ठीक है, बस जो कर रहे हो वही करते रहो।"

पेपर में: इसे बाथ (Bath) कहा गया। यह एक हल्का "ग्लोबल सिग्नल" है जो शेफ को पूरी तस्वीर से जोड़े रखता है बिना हर एक चीज़ को चखने में ऊर्जा बर्बाद किए।

"ड्रिफ्टिंग" (यह क्यों खास है):
LoRe का जादू यह है कि "हॉटस्पॉट्स" बदलते रहते हैं। मिनट 1 में सूप ठीक हो सकता है, लेकिन मिनट 10 में केक जलने लग सकता है।

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

परिणाम: तेज़ और हल्का

इस पेपर ने दो प्रसिद्ध पहेली प्रकारों पर इसका परीक्षण किया:

मैक्सिमम इंडिपेंडेंट सेट (MIS): जैसे कि यह पता लगाना कि आप पार्टी में कितने लोग बुला सकते हैं ताकि उनमें से कोई भी एक-दूसरे को न जानता हो (ताकि वे लड़ें नहीं)।
ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP): जैसे कि 1,000 शहरों की यात्रा करने के लिए सबसे छोटा रास्ता खोजना।

क्या हुआ?

मेमोरी: पुराना तरीका क्रैश हो गया (मेमोरी खत्म हो गई) जब पहेली बहुत बड़ी (लगभग 20,000 नोड्स) हो गई। Loere ने बिना क्रैश हुए 3 गुना बड़े पहेली (50,000 नोड्स तक) को संभाला।
गति: Loere पुराने तरीके की तुलना में 8 से 15 गुना तेज़ था।
गुणवत्ता: भले ही इसने पहेली के अधिकांश "बोरिंग" हिस्सों को अनदेखा कर दिया, लेकिन अंतिम उत्तर उतना ही अच्छा था जितना कि धीमे, विस्तृत (exhaustive) तरीके का।

निष्कर्ष (The Bottom Line)

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

तकनीकी सारांश: LoRe – पुनरावृत्ति ग्राफ सॉल्वर के लिए अनुकूली इंटरेक्शन-इवैल्यूएशन रूटिंग (Adaptive Interaction-Evaluation Routing)

1. समस्या विवरण

कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन (CO) के लिए पुनरावृत्ति न्यूरल सॉल्वर्स (iterative neural solvers), विशेष रूप से डिफ्यूजन मॉडल (जैसे DIFUSCO) और ग्राफ न्यूरल नेटवर्क (GNNs) पर आधारित, एक महत्वपूर्ण स्केलेबिलिटी बाधा का सामना करते हैं। जबकि ये मॉडल मैक्सिमम इंडिपेंडेंट सेट (MIS) और ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP) जैसे कार्यों पर मजबूत प्रदर्शन करते हैं, इनका इन्फरेंस (inference) खर्च प्रत्येक रिफाइनमेंट स्टेप में इंटरेक्शन टोपोलॉजी (जैसे सभी एडजेस या फैक्टर पेयर्स) के बार-बार, सघन मूल्यांकन (dense evaluation) द्वारा नियंत्रित होता है।

यह "फुल-सपोर्ट स्वीप" (full-support sweep) कंप्यूटेशनल लागत को $O(T|A|)$ के रूप में बढ़ाता है और पीक मेमोरी उपयोग इंटरेक्शन सेट के आकार $|A|$ के साथ रैखिक रूप से बढ़ता है। फलस्वरूप, बड़े पैमाने के इंस्टेंस हार्डवेयर मेमोरी सीमाओं (आउट-ऑफ-मेमोरी, या OOM) से बाहर हो जाते हैं या अस्वीकार्य विलंबता (latency) उत्पन्न करते हैं। मौजूदा समाधान एक दुविधा प्रस्तुत करते हैं:

स्टेप्स कम करना (जैसे डिस्टिलेशन): यह कुल समय को कम करता है लेकिन प्रति स्टेप आवश्यक पीक मेमोरी को कम नहीं करता है।
स्थिर स्पार्सिफिकेशन (जैसे फिक्स्ड kNN ग्राफ): यह प्रति-स्टेप मेमोरी को कम करता है लेकिन कॉम्बिनेटोरियल संघर्षों (combinatorial conflicts) की स्टेट-डिपेंडेंट प्रकृति को पकड़ने में विफल रहता है। पुनरावृत्ति रिफाइनमेंट में, उच्च संघर्ष या अनिश्चितता के "हॉटस्पॉट्स" समय के साथ बदलते रहते हैं; एक स्थिर स्पार्स सपोर्ट अनिवार्य रूप से नए महत्वपूर्ण इंटरेक्शन को मिस कर देता है, जिससे एरर संचय (error accumulation) और ट्रजेक्टरी ड्रिफ्ट होता है।

2. कार्यप्रणाली: LoRe प्रोटोकॉल

कंडेंस्ड मैटर फिजिक्स की कम्प्यूटेशनल पद्धतियों—विशेष रूप से क्लस्टर डायनेमिकल मीन-फील्ड थ्योरी (C-DMFT)—से प्रेरित होकर, लेखक LoRe (लोकल रीकंप्यूट) का प्रस्ताव करते हैं। LoRe एक ट्रेनिंग-फ्री, इन्फरेंस-टाइम ड्रॉप-इन रैपर है जो एक प्रति-स्टेप इंटरेक्शन-इवैल्यूएशन बजट लागू करता है।

सभी इंटरेक्शन का मूल्यांकन करने के बजाय, LoRe गणना को एक समय-परिवर्तनीय इंटरेक्शन सबसेट ( $M_t$ ) की ओर गतिशील रूप से रूट करता है और शेष का अनुमान लगाता है। यह एक क्लस्टर-बाथ डिकंपोजिशन (Cluster-Bath decomposition) को क्रियान्वित करता है:

क्लस्टर ( $M_t$ ): उच्च-संघर्ष वाले इंटरेक्शन (एजेस या फैक्टर पेयर्स) का एक गतिशील रूप से चयनित सबसेट, जिसका प्रत्येक स्टेप में सटीक मूल्यांकन किया जाता है।
बाथ ( $A \setminus M_t$ ): वे छोड़े गए इंटरेक्शन जिनका प्रभाव एक हल्के ग्लोबल रिकॉल सिग्नल के माध्यम से अनुमानित किया जाता है, ताकि स्थानीय क्लस्टर को ग्लोबल स्टेट से अलग होने से रोका जा सके।

मुख्य तकनीकी घटक:

डायनेमिक रूटिंग: प्रत्येक स्टेप $t$ $t$ पर, LoRe एक $M_t$ $M_{t}$ सबसेट की पहचान करता है ताकि $|M_t| \le \rho|A|$ $∣ M_{t} ∣ \leq ρ ∣ A ∣$ हो सके, जहाँ $\rho$ $ρ$ एक निश्चित बजट अनुपात है। चयन एक प्रॉक्सी स्कोर $s_{t,a}$ $s_{t, a}$ पर आधारित है जो प्राथमिकता देता है:
- एंडपॉइंट अनसर्टेन्टी (Endpoint Uncertainty): वे इंटरेक्शन जहाँ नोड स्टेट्स अनिर्णय की स्थिति में हैं (जैसे $x_i \approx 0.5$ )।
- टेम्पोरल इनस्टेबिलिटी (Temporal Instability): वे इंटरेक्शन जहाँ पिछले स्टेप की तुलना में नोड स्टेट्स में महत्वपूर्ण परिवर्तन हुआ है।
- स्टैटिक स्केलेटन (Static Skeleton): संरचनात्मक रूप से महत्वपूर्ण एडजेस (जैसे हाई-डिग्री नोड्स) का एक छोटा, निश्चित सेट बरकरार रखा जाता है ताकि संरचनात्मक स्थिरता सुनिश्चित हो सके।
- $M_t$ को ड्रिफ्टिंग हॉटस्पॉट्स को ट्रैक करने के लिए हर $R$ स्टेप्स के बाद रिफ्रेश किया जाता है।
ग्लोबल रिकॉल (वैकल्पिक): छोड़े गए "बाथ" के प्रभाव का अनुमान लगाने के लिए, $A \setminus M_t$ पर पूलिंग के माध्यम से एक कम-लागत वाला ग्लोबल सिग्नल $g_t$ कंप्यूट किया जाता है। यह सिग्नल एक पैरामीटर-फ्री कवरेज-वेटेड इंटरपोलेशन के माध्यम से क्लस्टर के साथ जुड़ा होता है, जो एक मीन-फील्ड करेक्शन के रूप में कार्य करता है।
बजेटेड ऑपरेटर: मानक डेंस ऑपरेटर $T_t$ को एक बजटेड ऑपरेटर $\tilde{T}_t$ द्वारा प्रतिस्थापित किया जाता है जो केवल $M_t$ पर सटीक मूल्यांकन करता है और शेष के लिए रिकॉल टर्म लागू करता है। पोस्ट-प्रोसेसिंग (प्रोजेक्शन/रिपेयर) बेसलाइन के समान ही रहती है ताकि निष्पक्ष तुलना सुनिश्चित हो सके।

3. मुख्य योगदान

वैचारिक सूत्रीकरण: यह पेपर पुनरावृत्ति ग्राफ सॉल्वर्स के लिए प्रति-स्टेप ऑपरेटर बजटिंग को औपचारिक रूप देता है, जिससे एक ऐसा ढांचा स्थापित होता है जो सॉल्वर के होराइजन या बैकबोन पैरामीटर्स को बदले बिना प्रत्येक रिफाइनमेंट स्टेप के भीतर कंप्यूटेशनल और मेमोरी एनवेलप को सीमित करता है।
LoRe प्रोटोकॉल: एक ट्रेनिंग-फ्री रनटाइम रैपर का परिचय जो फिजिक्स-प्रेरित क्लस्टर-बाथ डिकंपोजिशन को क्रियान्वित करता है। यह स्टैटिक स्पेशियल स्पार्सिफिकेशन के बजाय डायनेमिक, स्टेट-डिपेंडेंट रूटिंग के माध्यम से टेम्पोरल ऑपरेटर स्पैरसिटी उत्पन्न करता है।
ऑडिटेबल अकाउंटिंग: लेखक एक पूर्णतः समावेशी, एंड-टू-एंड वॉल-क्लॉक अकाउंटिंग प्रोटोकॉल स्थापित करते हैं। रिपोर्ट किए गए सभी मेट्रिक्स (समय और मेमोरी) में डिफ्यूजन स्टेप्स, रूटिंग ओवरहेड और पोस्ट-प्रोसेसिंग शामिल हैं, जो एक पारदर्शी बेंचमार्क प्रदान करते हैं।

4. प्रयोगात्मक परिणाम

प्रयोग DIFUSCO कोडबेस और प्री-ट्रेन चेकपॉइंट्स का उपयोग करके मैक्सिमम इंडिपेंडेंट सेट (MIS) और ट्रैवलिंग सेल्सपर्सन प्रॉब्लम (TSP) पर किए गए।

स्केलेबिलिटी और मेमोरी व्यवहार्यता (MIS):
- LoRe बेसलाइन की OOM सीमा से 3 गुणा से अधिक आगे तक व्यवहार्य इन्फरेंस का विस्तार करता है।
- $n=15,000$ नोड्स (सबसे बड़ा स्केल जहाँ बेसलाइन व्यवहार्य है) पर, Loere 8.16× स्पीडअप प्राप्त करता है और पीक GPU मेमोरी को ~12× कम कर देता है (86.7 GB से 7.32 GB तक) जबकि समाधान की गुणवत्ता (रिटेंशन $\approx$ 1.01) बनाए रखता है।
- बेसलाइन $n=20,000$ पर विफल (OOM) हो जाता है, जबकि LoRe $n=50,000$ तक व्यवहार्य रहता है।
क्रॉस-टास्क जनरलाइजेशन (TSP):
- LoRe $n=1,000$ पर ~15× स्पीडअप और 44× मेमोरी रिडक्शन प्राप्त करता है।
- समाधान की गुणवत्ता (टूर लेंथ) बेसलाइन के साथ प्रतिस्पर्धी रहती है (विभिन्न स्केल्स पर रिटेंशन 0.94–1.01)।
- विधि बिना रिट्रेनिंग के, उसी डेंस-ट्रेन्ड चेकपॉइंट का उपयोग करके TSP पर सामान्यीकृत होती है।
मैकेनिज्म वैलिडेशन (एब्लेशन):
- स्टैटिक सपोर्ट (फिक्स्ड मास्क) और ग्रीडी डायनेमिक स्ट्रैटेजीज के मुकाबले नियंत्रित प्रयोग पुष्टि करते हैं कि स्टेट-डिपेंडेंट री-रूटिंग आवश्यक है। स्टैटिक सपोर्ट ड्रिफ्टिंग संघर्षों को ट्रैक करने में विफल रहते हैं, जिससे जल्दी सैचुरेशन और व्यवहार्य समाधान खोजने में विफलता होती है।
- Lo-Re का हाइब्रिड दृष्टिकोण (स्टैटिक स्केलेटन + डायनेमिक हॉटस्पॉट्स) शुद्ध रूप से डायनेमिक ग्रीडी सिलेक्शन की तुलना में अधिक स्थिर सिद्ध होता है।
रोबस्टनेस:
- जीरो-शॉट टोपोलॉजी शिफ्ट्स: Lo-Re बिना रिट्रेनिंग के Erdős–Rényi (ER), Barabási–Albert (BA), और Watts–Strogatz (WS) ग्राफ परिवारों के बीच ~8× स्पीडअप और ~12× मेमोरी रिडक्शन बनाए रखता है।
- हाइपरपैरामीटर सेंसिटिविटी: विधि हाइपरपैरामीटर के प्रति काफी असंवेदनशील है; एक एकल कॉन्फ़िगरेशन ( $\rho=0.08, R=10$ ) विभिन्न कार्यों और ग्राफ घनत्वों के लिए प्रभावी रूप से काम करता है।

5. महत्व और दावे

पेपर का दावा है कि Lo-Re बड़े पैमाने के कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन के लिए पुनरावृत्ति न्यूरल सॉल्वर्स के उपयोग में एक मौलिक बाधा को संबोधित करता है। "डेंस इवैल्यूएशन" से "बजेट-अवेयर डायनेमिक रूटिंग" की ओर शिफ्ट होकर, Lo-Re इन सॉल्वर्स के स्केलिंग प्रोफाइल को बदल देता है।

व्यावहारिकता: यह उन समस्या इंस्टेंस को हल करने में सक्षम बनाता है जो वर्तमान में मेमोरी बाधाओं (OOM) के कारण असंभव हैं, प्रभावी रूप से मानक हार्डवेयर पर हल करने योग्य सीमा को बढ़ा देता है।
दक्षता: यह बिना मॉडल रिट्रेनिंग या आर्किटेक्चरल बदलाव के पर्याप्त वॉल-क्लॉक स्पीडअप (15× तक) और मेमोरी रिडक्शन (44× तक) प्रदान करता है।
सामान्यीकरण: एक ड्रॉप-इन रैपर के रूप में, यह पैराडाइम-अग्नोस्टिक है और न्यूनतम अनुकूलन के साथ विभिन्न पुनरावृत्ति सॉल्वर्स (जैसे T2TCO, COExpander) और कार्यों (MIS, TSP) पर लागू किया जा सकता है।

लेखक निष्कर्ष निकालते हैं कि Lo-Re प्रति-स्टेप संसाधन बाधाओं को लागू करने के लिए एक कठोर, ट्रेनिंग-फ्री तंत्र प्रदान करता है, जिससे पुनरावृत्ति न्यूरल सॉल्वर्स वास्तविक दुनिया के, बड़े पैमाने के निर्णय प्रणालियों के लिए व्यवहार्य हो जाते हैं जहाँ लेटेंसी और मेमोरी बाध्यकारी बाधाएं होती हैं।