🤖 machine learning

Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification

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

मूल लेखक: Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

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

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

CC BY 4.0

मूल लेखक: Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan Kalayci

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

कल्पना कीजिए कि आप एक जासूस हैं जो एक रहस्य सुलझाने की कोशिश कर रहे हैं, लेकिन आपके पास दो बहुत अलग उपकरण हैं, और दोनों का उपयोग करने के लिए पैसे खर्च होते हैं।

उपकरण:

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

समस्या:
आपके पास संदिग्धों की एक सूची है (AI द्वारा उत्पन्न संभावित उत्तर)। आपको वह एक दोषी व्यक्ति ढूंढना है (सही उत्तर)।

यदि आप हर किसी पर "झूठ पकड़ने वाली मशीन" का उपयोग करते हैं, तो आप दिवालिया हो जाएंगे।
यदि आप केवल अपनी "अंतरात्मा की आवाज़" पर भरोसा करते हैं, तो आप गलत व्यक्ति को गिरफ्तार कर सकते हैं।
पुराना तरीका यह था कि एक निश्चित नियम चुना जाता था: "मैं लगभग 100 लोगों के बारे में अंतरात्मा की आवाज़ पूछूँगा, फिर शीर्ष 5 पर झूठ पकड़ने वाली मशीन का उपयोग करूँगा।"
- खामी: कुछ रहस्य आसान होते हैं (दोषी व्यक्ति स्पष्ट होता है), इसलिए आपने 100 लोगों की जाँच करके पैसा बर्बाद किया। अन्य रहस्य कठिन होते हैं (दोषी व्यक्ति छिपा हुआ होता है), इसलिए केवल 5 की जाँच करना पर्याप्त नहीं था, और आप विफल रहे। आप हर मामले के लिए एक निश्चित नियम का उपयोग नहीं कर सकते।

समाधान: "ADAP" (अनुकूली जासूस - The Adaptive Detective)
लेखकों ने एक स्मार्ट रणनीति बनाई है जिसे ADAP कहा जाता है। एक निश्चित नियम पर टिके रहने के बजाय, ADAP एक ऐसे जासूस की तरह है जो मौके पर ही सीखता है।

ADAP कैसे काम करता है, इस सरल उपमा का उपयोग करके देखें:

द "शेल" (कवच/परत) रणनीति

कल्पना कीजिए कि आप घास के ढेर में सुई ढूंढ रहे हैं, लेकिन आपको नहीं पता कि घास का ढेर कितना बड़ा है।

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

यह क्यों शानदार है?

आसान मामलों के लिए: यदि उत्तर स्पष्ट है, तो ADAP बहुत कम जांचों के साथ इसे जल्दी से ढूंढ लेता है। यह बहुत सारा पैसा बचाता है।
कठिन मामलों के लिए: यदि उत्तर छिपा हुआ है, तो ADAP तब तक चलता रहता है जब तक कि वह उसे ढूंढ न ले। यह एक निश्चित नियम की तरह समय से पहले हार नहीं मानता।
परिणाम: औसतन, ADAP पुराने "निश्चित नियम" वाले तरीकों की तुलना में बहुत कम पैसा खर्च करता है और फिर भी 100% बार सही उत्तर ढूंढ लेता है।

"मोनोटोनिसिटी" (एकदिशता) का नियम (गुप्त सूत्र)

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

इस पेपर ने क्या सिद्ध किया

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

आदर्श परिदृश्य: उन्होंने पहले एक ऐसे जासूस की कल्पना की जो जानता है कि प्रत्येक संदिग्ध के दोषी होने की कितनी संभावना है। उन्होंने रहस्य सुलझाने के लिए न्यूनतम लागत की गणना की।
वास्तविक दुनिया: उन्होंने दिखाया कि ADAP, बिना भविष्य को जाने, उस "परफेक्ट" लागत के एक स्थिर कारक के भीतर रह सकता है। सरल शब्दों में: ADAP उस "परफेक्ट" जासूस के लगभग बराबर है जिसके पास भविष्य देखने की शक्ति है, लेकिन इसे उसकी आवश्यकता नहीं है।
संरचना की आवश्यकता: उन्होंने यह भी सिद्ध किया कि यदि "अंतरात्मा की आवाज़" पूरी तरह से अराजक (कोई पैटर्न नहीं) होती, तो कोई भी रणनीति कुशल नहीं होती। पैसा बचाने के लिए आपको उस "उच्च स्कोर = सही होने की अधिक संभावना" वाले पैटर्न की आवश्यकता है।

वास्तविक दुनिया का परीक्षण

टीम ने इस पर दो कठिन कार्यों का परीक्षण किया:

गणित की समस्याएं: जटिल गणितीय प्रश्नों को हल करना।
कोडिंग: कंप्यूटर प्रोग्राम लिखना जो छिपे हुए परीक्षणों को पास करते हैं।

परिणाम:

ADAP ने 100% बार सही उत्तर पाया।
पुराने निश्चित तरीके (निश्चित संख्या में लोगों की जाँच करना) या तो उत्तर खोजने में विफल रहे या समान परिणाम प्राप्त करने के लिए 3 से 5 गुना अधिक पैसा खर्च किया।
यहाँ तक कि एक "स्मार्ट" पद्धति की तुलना में, जो समस्या की कठिनाई का पहले से अनुमान लगाने की कोशिश करती थी, ADAP समान या बेहतर प्रदर्शन करता है, बिना किसी पूर्व ज्ञान के।

सारांश

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

तकनीकी सारांश: एडेप्टिव जनरेट-रैंक-वेरिफाई (Adaptive Generate-Rank-Verify)

समस्या का निरूपण (Problem Formulation)

यह शोध पत्र लार्ज लैंग्वेज मॉडल्स (LLMs) में लागत-संवेदनशील इन्फरेंस-टाइम कंप्यूट आवंटन (cost-sensitive inference-time compute allocation) की समस्या को संबोधित करता है। आधुनिक रीजनिंग पाइपलाइन्स अक्सर एक "जनरेट-रैंक-वेरिफाई" प्रतिमान (paradigm) का उपयोग करती हैं: एक LLM कई संभावित समाधान (candidate solutions) उत्पन्न करता है, एक सस्ता लेकिन शोर वाला रिवॉर्ड मॉडल (reward model) उन्हें रैंक करता है, और एक महंगा वेरिफायर (verifier) (जैसे कि कोड में हिडन-टेस्ट निष्पादन या गणित में सटीक उत्तर मिलान) शीर्ष उम्मीदवारों को सत्यापित करता है।

मुख्य चुनौती यह है कि कंप्यूट संसाधनों का इष्टतम आवंटन (कितने जनरेशन बनाम कितनी वेरिफिकेशन) प्रॉम्प्ट-निर्भर (prompt-dependent) होता है। निश्चित नीतियां (जैसे $N_{rew}$ सैंपल जेनरेट करना और शीर्ष $N_{ver}$ को वेरिफाई करना) अक्षम हैं: वे आसान प्रॉम्प्ट्स पर अत्यधिक खर्च करती हैं और कठिन प्रॉम्प्ट्स पर कम खर्च करती हैं। लेखक इसे एक्टिव सर्च (Active Search) के रूप में औपचारिक रूप देते हैं, जो एक अनुक्रमिक निर्णय समस्या (sequential decision problem) है जहाँ एक पॉलिसी को अनुकूल रूप से (adaptively) निम्नलिखित कार्य करने चाहिए:

उम्मीदवारों को जेनरेट (Generate) करना और उनके रिवॉर्ड स्कोर को देखना (लागत $c_{rew}$ )।
चुने गए उम्मीदवारों को वेरिफाई (Verify) करना ताकि ग्राउंड-ट्रुथ लेबल प्राप्त हो सकें (लागत $c_{ver}$ )।
केवल तभी रुकना (Stop) जब एक वेरिफाइड-सही (verified-correct) प्रतिक्रिया मिल जाए।

लक्ष्य 100% सफलता दर (यदि जनरेशन वितरण में कोई सही उत्तर मौजूद है) सुनिश्चित करते हुए अपेक्षित कुल लागत $J = c_{rew}N_{rew} + c_{ver}N_{ver}$ को न्यूनतम करना है।

कार्यप्रणाली (Methodology)

1. डिस्ट्रीब्यूशन-अवेयर बेंचमार्क (Distribution-Aware Benchmark)

लेखक पहले एक सैद्धांतिक निचली सीमा (lower bound) स्थापित करते हैं, यह मानते हुए कि पॉलिसी के पास वातावरण का पूर्ण ज्ञान है:

$D_x$ : प्रॉम्प्ट $x$ के लिए रिवॉर्ड स्कोर का वितरण।
$h^*_x(r)$ : सशर्त सफलता फलन (conditional success function), जो यह दर्शाता है कि स्कोर $r$ वाला एक उम्मीदवार वेरिफिकेशन पास करने की संभावना रखता है।

थ्योरम 3.2 इस आदर्श स्थिति में इष्टतम पॉलिसी की विशेषता बताता है। यह सिद्ध करता है कि इष्टतम रणनीति एक थ्रेशोल्ड नियम (threshold rule) है: किसी भी उम्मीदवार को तुरंत वेरिफाई करें यदि उसकी सशर्त सफलता संभावना $h^*_x(r)$ एक विशिष्ट ब्रेक-ईवन थ्रेशोल्ड $\tau^*$ से अधिक हो, अन्यथा उसे छोड़ दें। थ्रेशोल्ड $\tau^*$ इस समीकरण का एकमात्र समाधान है: $c_{ver} \mathbb{E}[\max\{h^*(R) - \tau^*, 0\}] = \tau^* c_{rew}$ ।

2. ADAP एल्गोरिदम

व्यावहारिक रूप से, $D_x$ और $h^*_x$ अज्ञात हैं। लेखक ADAP (Adaptive Generate-Rank-Verify) प्रस्तावित करते हैं, जो एक शेलवाइज (shellwise) ऑनलाइन एल्गोरिदम है जो स्कोर वितरण या सफलता फलन के पूर्व ज्ञान के बिना कार्य करता है, और केवल मोनोटोनिसिटी धारणा (monotonicity assumption) (उच्च रिवॉर्ड स्कोर वेरिफिकेशन पास करने की कम संभावना नहीं रखते) पर निर्भर करता है।

ADAP तंत्र:

शेलवाइज सर्च (Shellwise Search): एल्गोरिदम सैंपल की संख्या ( $m$ ) और वेरिफिकेशन की संख्या ( $k$ ) के लिए डायडिक स्केल्स (dyadic scales) के "शेल" पर खोज करता है। प्रत्येक शेल $s$ , लागत रेंज $[2^s c_{min}, 2^{s+1} c_{min})$ के अनुरूप है।
प्रोग्रेसिव एक्सपेंशन (Progressive Expansion): छोटे शेल से शुरू करते हुए, ADAP उम्मीदवारों का एक बैच जेनरेट करता है, उन्हें एक पूल में जोड़ता है, और पूरे पूल को रिवॉर्ड स्कोर द्वारा रैंक करता है।
वेरिफिकेशन (Verification): यह पूल के शीर्ष $k$ उम्मीदवारों को वेरिफाई करता है। यदि एक पॉजिटिव लेबल मिलता है, तो यह रुक जाता है। यदि नहीं, तो यह बड़े $m$ और $k$ के साथ अगले शेल की ओर बढ़ता है।
पूल-आधारित दक्षता (Pool-Based Efficiency): स्ट्रीमिंग पॉलिसियों के विपरीत जो अनवेरिफाइड उम्मीदवारों को हटा देती हैं, ADAP एक पूल बनाए रखता है। शुरुआती शेल में जेनरेट किए गए उच्च-रिवॉर्ड वाले उम्मीदवार बाद के शेल में वेरिफिकेशन के लिए उपलब्ध रहते हैं यदि उन्हें अभी तक क्वेरी नहीं किया गया है।

3. सैद्धांतिक गारंटी (Theoretical Guarantees)

ऊपरी सीमा (Upper Bound): मोनोटोनिसिटी धारणा के तहत, थ्योरम 4.2 सिद्ध करता है कि ADAP वितरण-जागरूक इष्टतम $J^*$ के भीतर एक स्थिरांक कारक (विशेष रूप से $\le 400$ ) के भीतर अपेक्षित लागत प्राप्त करता है। यह गारंटी सभी व्यवहार्य प्रॉम्प्ट्स और अज्ञात वितरणों के लिए समान रूप से लागू होती है।
निचली सीमाएँ और संरचना की आवश्यकता (Lower Bounds & Necessity of Structure): लेखक प्रदर्शित करते हैं कि संरचनात्मक धारणाएँ आवश्यक हैं। सेंटर्ड स्टार नंबर ( $s_0$ ) (एक लर्निंग-थ्योरेटिक कॉम्प्लेक्सिटी मेजर) का उपयोग करते हुए, थ्योरम 6.2 दिखाता है कि स्कोर और लेबल के बीच संबंध (अर्थात, यदि $s_0 = \infty$ ) पर धारणाओं के बिना, कोई भी साउंड ऑनलाइन पॉलिसी वितरण-जागरूक ओरेकलल के विरुद्ध एक कांस्टेंट-फैक्टर कॉम्पिटिटिव रेश्यो प्राप्त नहीं कर सकती। वर्स्ट-केस गैप $\Omega(\min\{s_0, c_{ver}/c_{rew}\})$ के रूप में स्केल हो सकता है।

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

औपचारिकीकरण (Formalization): जनरेट-रैंक-वेरिफाई पाइपलाइन को एक लागत-संवेदनशील एक्टिव सर्च समस्या के रूप में परिभाषित किया, जो फिक्स्ड पूल को क्वेरी करने के बजाय ऑनलाइन उम्मीदवार जेनरेट करने की आवश्यकता के कारण मानक एक्टिव लर्निंग से अलग है।
इष्टतम बेंचमार्क (Optimal Benchmark): ब्रेक-ईवन सक्सेस प्रोबेबिलिटीिटी के आधार पर वितरण-जागरूक इष्टतम पॉलिसी को एक सरल थ्रेशोल्ड नियम के रूप में वर्णित किया।
अनुकूली एल्गोरिदम (ADAP): एक व्यावहारिक, ऑनलाइन एल्गोरिदम प्रस्तावित किया जो अनुकूल रूप से जनरेशन और वेरिफिकेशन प्रयासों को स्केल करता है। यह मोनोटोनिसिटी के तहत अज्ञात वितरणों के सापेक्ष इष्टतम ओरेकल के लिए सिद्ध स्थिरांक-कारक (constant-factor) गारंटी प्रदान करता है।
लर्निंग-थ्योरेटिक सीमाएँ (Learning-Theoretic Limits): यह स्थापित किया कि संरचनात्मक धारणाएं (जैसे मोनोटोनिसिटी) केवल तकनीकी सुविधाएँ नहीं हैं, बल्कि कुशल एक्टिव सर्च के लिए मौलिक आवश्यकताएं हैं, जिन्हें सेंटर्ड स्टार नंबर के माध्यम से औपचारिक रूप दिया गया है।
प्रायोगिक सत्यापन (Empirical Validation): गणितीय तर्क (HMMT) और प्रतिस्पर्धी प्रोग्रामिंग (LiveCodeBench) कार्यों पर दृष्टिकोण का सत्यापन किया।

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

लेखकों ने ADAP का मूल्यांकन इनके विरुद्ध किया:

SampleAware: एक ओरेकल लोअर बाउंड जो प्रत्येक विशिष्ट परीक्षण के लिए रेट्रोस्पेक्टिवली सबसे सस्ते $(N_{rew}, N_{ver})$ को चुनता है।
DAPk: एक डिफिकल्टी-एडाप्टिव बेसलाइन जो ऐतिहासिक पास रेट के आधार पर प्रॉम्प्ट्स को $k$ कठिनाई वर्गों में विभाजित करती है और प्रत्येक के लिए एक निश्चित रणनीति असाइन करती है।
Uniform: एक निश्चित पॉलिसी जो ADAP की औसत लागत से मेल खाती है।

निष्कर्ष:

लागत दक्षता (Cost Efficiency): व्यवहार्य प्रॉम्प्ट्स के उपसमूह पर, ADAP ने गणित कार्यों पर सर्वश्रेष्ठ फिक्स्ड पॉलिसी की तुलना में 2.9 $\times$ कम और कोडिंग कार्यों पर 5.5 $\times$ कम औसत लागत के साथ 100% सफलता दर प्राप्त की।
DAPk के साथ तुलना: ADAP ने ऐतिहासिक कठिनाई लेबल या ऑफलाइन ट्यूनिंग की आवश्यकता के बिना DAPk (यहाँ तक कि $k=10$ के साथ भी) की बराबरी की या उससे बेहतर प्रदर्शन किया। कोडिंग कार्यों पर, DAPk कभी भी ADAP को नहीं हरा सका, जबकि गणित कार्यों पर, DAPk केवल तभी ADAP के प्रदर्शन के करीब पहुँचा जब $k$ इतना बड़ा था कि वह प्रति-समस्या ओरेकल के करीब पहुँच सके।
मजबूती (Robustness): फिक्स्ड पॉलिसियों पर ADAP का लाभ जनरेशन लागत ( $c_{rew}$ ) के सापेक्ष वेरिफिकेशन लागत ( $c_{ver}$ ) बढ़ने के साथ बढ़ गया।

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

यह शोध पत्र दावा करता है कि इन्फरेंस-टाइम सर्च के लिए ऑनलाइन, प्रॉम्प्ट-डिपेंडेंट एडैप्टेशन स्टैटिक या ऐतिहासिक रूप से ट्यून की गई पॉलिसियों की तुलना में बेहतर है। समस्या को एक्टिव सर्च के रूप में मानकर और रिवॉर्ड सिग्नल्स की मोनोटोनिसिटी का लाभ उठाकर, ADAP विशिष्ट प्रॉम्प्ट्स की कठिनाई के साथ तालमेल बिठाने के लिए कंप्यूट संसाधनों को गतिशील रूप से आवंटित कर सकता है।

लेखक इस बात पर जोर देते हैं कि उनका कार्य निम्नलिखित प्रदान करता है:

सिद्ध गारंटी: अज्ञात वितरणों को जाने बिना इष्टतम लागत का एक कांस्टेंट-फैक्टर एप्रोक्सिमेशन।
व्यावहारिक दक्षता: उच्च-दांव वाले रीजनिंग कार्यों के लिए कंप्यूट लागत (लेटेंसी, GPU घंटे, API खर्च) में महत्वपूर्ण कमी।
सैद्धांतिक आवश्यकता: एक प्रदर्शन कि रिवॉर्ड-वेरिफायर संबंध पर संरचनात्मक धारणाएं कुशल सर्च प्राप्त करने के लिए अपरिहार्य हैं, जो एक्टिव सर्च और एक्टिव लर्निंग थ्योरी के बीच के अंतर को पाटती हैं।

शोध पत्र निष्कर्ष निकालता है कि हालांकि वेरिएबल कॉस्ट और पैरेलल जनरेशन की ओर विस्तार भविष्य की दिशाएं हैं, वर्तमान ढांचा विविध उम्मीदवारों को जेनरेट करने और सबसे आशाजनक उम्मीदवारों को वेरिफाई करने के बीच के मौलिक तनाव को सफलतापूर्वक संबोधित करता है।