तकनीकी सारांश: विस्तारवादी खोज स्थानों (Expanding Search Spaces) पर LLMs में स्टेप-बाय-स्टेप ऑप्टिमाइज़ेशन-जैसी तर्क प्रक्रिया

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

जबकि लार्ज लैंग्वेज मॉडल्स (LLMs) ने सत्यापन योग्य रिवॉर्ड ट्रेनिंग के माध्यम से गणितीय और कोडिंग तर्क (reasoning) में सफलता प्रदर्शित की है, वे प्रतिबंधित स्टेप-बाय-स्टेप निर्णय लेने वाले कार्यों (constrained step-by-step decision-making tasks) में नाजुक बने हुए हैं। इन परिदृश्यों में, एक स्थानीय रूप से प्रशंसनीय (plausible) कदम शेष समस्या को अव्यवहार्य बना सकता है या कम गुणवत्ता वाले परिणाम की ओर धकेल सकता है। मानक उत्तर-सत्यता (answer-correctness) सेटिंग्स के विपरीत, जहाँ एक ही सही उत्तर होता है, कई वास्तविक दुनिया के कार्यों (जैसे, संसाधन आवंटन, शेड्यूलिंग, रूटिंग) में कई व्यवहार्य समाधान शामिल होते हैं, जहाँ उद्देश्य बाधाओं के तहत एक उच्च-मूल्य वाला समाधान बनाना है।

वर्तमान स्केलिंग विधियाँ दो बाधाओं का सामना करती हैं:

1. ऐसे विविध कार्य उत्पन्न करना जो विश्वसनीय रूप से गैर-मामूली तर्क की आवश्यकता रखते हों, कठिन है।
2. मध्यवर्ती चरणों के लिए पर्यवेक्षण (supervision) प्राप्त करना महंगा है, क्योंकि इसके लिए यह पहचानना आवश्यक है कि कौन से आंशिक कार्य इष्टतम परिणामों की ओर ले जाते हैं।

यह शोध पत्र विस्तारवादी खोज स्थानों पर ऑप्टिमाइज़ेशन-जैसे तर्क करने के लिए LLMs को प्रशिक्षित करने की चुनौती को संबोधित करता है, जहाँ कठिनाई को एक जटिलता पैरामीटर $\alpha$ द्वारा नियंत्रित किया जाता है, जिसके लिए नए मानव लेबल की आवश्यकता नहीं होती है।

2. कार्यप्रणाली: OPT⋆ फ्रेमवर्क

लेखक OPT⋆ (OPTimization-based Scalable Tasks for Auto-verifiable Reasoning) पेश करते हैं, जो स्टेप-बाय-स्टेप तर्क को प्रशिक्षित करने और मूल्यांकन करने के लिए डिज़ाइन किया गया कार्यों का एक परिवार है।

2.1 कार्य परिभाषा

एक OPT⋆ कार्य उदाहरण $t$ एक नियंत्रित निर्णय प्रक्रिया है जिसे निम्नलिखित द्वारा परिभाषित किया गया है:

• स्केलेबल जनरेशन: उदाहरणों को एक प्रक्रिया $Build_\alpha(\cdot)$ द्वारा उत्पन्न किया जाता है जो एक जटिलता पैरामीटर $\alpha$ (जैसे, TSP में शहरों की संख्या, Knapsack में वस्तुओं की संख्या) द्वारा नियंत्रित होता है। $\alpha$ को बढ़ाने से खोज स्थान $M(t)$ का विस्तार होता है, लेकिन एनोटेशन लागत नहीं बढ़ती है।
• सस्ता सत्यापन (Cheap Verification): प्रत्येक कार्य दो सस्ते रूटीन प्रदान करता है:
  • व्यवहार्यता जांचकर्ता (Feasibility Checker - $chkt$): आंशिक कार्यों को मान्य करता है (जैसे, यह सुनिश्चित करना कि लोड सीमा पार न हो)।
  • परिणाम मूल्यांकनकर्ता (Outcome Evaluator - $evalt$): पूर्ण टर्मिनल समाधानों को स्कोर करता है (जैसे, कुल टूर लंबाई)।
• स्व-सत्यापन योग्य (Auto-verifiability): $chkt$और$evalt$ दोनों बहुपद समय (polynomial time) में गणनीय हैं, भले ही इष्टतम समाधान खोजना कठिन हो।

2.2 प्रशिक्षण शासन (Training Regimes)

लेखक उपलब्ध सॉल्वर (solver) की उपलब्धता के आधार पर दो पूरक प्रशिक्षण दृष्टिकोण प्रस्तावित करते हैं:

A. सॉल्वर-निर्देशित ऑनलाइन पॉलिसी ऑप्टिमाइज़ेशन (Online RL)

जब एक आंशिक अवस्था (partial state) से सर्वोत्तम पूर्णता मान (best completion value) की गणना करने के लिए एक तेज़ सॉल्वर उपलब्ध हो:

• तंत्र: सॉल्वर एक 'वैल्यू ऑरेकल' के रूप में कार्य करता है। एक दिए गए स्टेट के लिए, संभावित अगले कदमों को सैंपल किया जाता है, और प्रत्येक को एक निश्चित सॉल्वर बजट के तहत सर्वोत्तम सुलभ टर्मिनल मान द्वारा स्कोर किया जाता है।
• रिवॉर्ड शेपिंग: पॉलिसी को रैंक-आधारित रिवॉर्ड्स (जैसे, GRPO, GSPO, PPO) का उपयोग करके अपडेट किया जाता है, जहाँ उच्च-मूल्य वाले पूर्णता की ओर ले जाने वाले कार्यों को उच्च रैंक दी जाती है।
• लक्ष्य: उन कदमों को सुदृढ़ करना जो बेहतर अंतिम परिणामों की ओर ले जाते हैं, प्रभावी रूप से सॉल्वर ह्यूरिस्टिक्स को पॉलिसी में डिस्टिल (distill) करना।

B. सर्च-आधारित ऑफलाइन RL

जब आंशिक अवस्थाओं के लिए सॉल्वर उपलब्ध न हों या बहुत महंगे हों:

• तंत्र: मॉडल संभावित प्रक्षेप पथ (trajectories) उत्पन्न करता है। एक खोज एल्गोरिदम (जैसे, MCTS, Beam Search) स्थान का अन्वेषण करता है, अमान्य पथों को हटाने के लिए $chkt$का उपयोग करता है और टर्मिनल नोड्स को स्कोर करने के लिए$evalt$ का उपयोग करता है।
• प्रमुख खोज घटक:
  1. व्यवहार्यता छंटनी (Feasibility Pruning): उन बच्चों (children) को हटाना जहाँ $chkt(s, a) = 0$ हो।
  2. डुप्लिकेट मर्जिंग (Duplicate Merging): अलग-अलग टेक्स्ट आउटपुट को जो एक ही स्ट्रक्चर्ड एक्शन से मैप होते हैं, उन्हें समूहबद्ध करना ताकि खोज बजट बर्बाद न हो।
• प्रशिक्षण: मॉडल को खोज प्रक्रिया द्वारा खोजे गए सर्वोत्तम प्रक्षेप पथों पर फाइन-ट्यून (SFT) किया जाता है, प्रभावी रूप से उच्च-मूल्य वाले तर्क पथों की नकल करना सीखना।

2.3 सैद्धांतिक आधार

यह शोध पत्र एक सूचना-सैद्धांतिक सीमा (Theorem A.3) स्थापित करता है जो बड़े खोज स्थानों में सफलता को प्रति इकाई खोज बजट से निकाले गए सूचना से जोड़ता है। जैसे-जैसे जटिलता $\alpha$ बढ़ती है, प्रभावी इष्टतमों की संख्या बढ़ती है। एक स्थिर सफलता की संभावना बनाए रखने के लिए, एक तर्ककर्ता (reasoner) को या तो खोज बजट बढ़ाना होगा या प्रति चरण अधिक सूचना निकालनी होगी। खोज दक्षता को मापने के लिए एक मीट्रिक के रूप में प्रभावी ब्रांचिंग फैक्टर ($b_{eff}$) पेश किया गया है; कम $b_{eff}$ यह दर्शाता है कि एक खोज बजट उच्च-मूल्य वाले टर्मिनल स्टेट्स पर अधिक द्रव्यमान (mass) रखता है।

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

1. वैचारिक (OPT⋆): अनुकूलन-जैसे तर्क के लिए एक स्केलेबल, ऑटो-वेरिफिएबल टास्क फैमिली का औपचारिककरण। यह फ्रेमवर्क जटिलता पैरामीटर्स का उपयोग करके खोज स्थानों का विस्तार करते हुए सत्यापन को सस्ता रखकर एनोटेशन प्रयास को तर्क से अलग करता है।
2. एल्गोरिद्मिक:
   • प्लग-एंड-प्ले सर्च कंपोनेंट्स (व्यवहार्यता जांच और डुप्लिकेट मर्जिंग) का विकास जो ऑफलाइन सेटिंग्स में खोज दक्षता में काफी सुधार करता है।
   • $\nu$PO (Solver-Guided Policy Optimization) का परिचय, एक विधि जो ऑनलाइन RL के लिए स्टेप-लेवल रिवॉर्ड्स प्रदान करने के लिए सॉल्वर्स का लाभ उठाती है, जिससे आंशिक अवस्थाओं पर प्रशिक्षण संभव होता है।
3. अनुभवजन्य (Empirical):
   • यह दिखाना कि OPT⋆ पर प्रशिक्षण ऑप्टिमाइज़ेशन कार्यों में स्टेप-बाय-स्टेप तर्क में सुधार करता है।
   • प्रमाण कि करिकुलम लर्निंग (आसान $\alpha_1$ से कठिन $\alpha_4$ तक प्रशिक्षण) केवल कठिन कार्यों पर प्रशिक्षण देने की तुलना में बेहतर सामान्यीकरण (generalization) प्रदान करती है।
   • यह प्रदर्शित करना कि ऑप्टिमाइज़ेशन प्रशिक्षण स्थानिक तर्क (spatial reasoning) क्षमताओं (जैसे, रोटेशन, रिफ्लेक्शन, कवरेज) में स्थानांतरित होता है और गणितीय बेंचमार्क (AMC, AIME) पर प्रदर्शन में सुधार करता है।

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

लेखकों ने Role Assignment, MaxSAT, Single-machine Scheduling, TSP, 2D Packing, और Quadratic Assignment Problem (QAP) सहित कार्यों पर फ्रेमवर्क का मूल्यांकन किया।

• खोज दक्षता (Offline RL):
  • व्यवहार्यता छंटनी और डुप्लिकेट मर्जिंग को सक्षम करने से प्रभावी ब्रांचिंग फैक्टर ($b_{eff}$) काफी कम हो गया। उदाहरण के लिए, QAP में, इन घटकों के साथ $\nu$MCTS ने $b_{eff} \approx 24$ प्राप्त किया, जबकि बिना LLM प्रस्तावों वाले सॉल्वर-रेफरेंस बेसलाइन के लिए $b_{eff} \approx 728$ था।
  • ये घटक खोज दक्षता के प्राथमिक चालक थे, जिन्होंने QAP में pass@16 को ~13% से बढ़ाकर ~85% कर दिया।
• मॉडल सुधार:
  • OPT⋆ कार्यों (Role Assignment, MaxSAT) पर प्रशिक्षित मॉडल्स ने बेस मॉडल्स की तुलना में पर्याप्त सुधार दिखाया। उदाहरण के लिए, Qwen2.5-3B ने Role Assignment पर pass@1 को Level 1 के लिए 32.5% से 44.5% और Level 4 के लिए 17.8% से 31.1% तक सुधार किया।
  • सॉल्वर-निर्देशित ऑनलाइन RL ने डोमेन-ट्रांसफर बेसलाइन्स (जैसे, Math या Code कार्यों पर प्रशिक्षण का ऑप्टिमाइज़ेशन कार्यों पर अच्छा ट्रांसफर नहीं हुआ) से लगातार बेहतर प्रदर्शन किया।
• सामान्यीकरण (Generalization):
  • ऑप्टिमाइज़ेशन कार्यों पर प्रशिक्षण ने आउट-ऑफ-डिस्ट्रीब्यूशन (OOD) स्थानिक QA कार्यों (जैसे, रोटेशन, सिमिट्री, ओवरलैप) और मानक गणित बेंचमार्क (AMC'23, AIME'24/25) पर प्रदर्शन में सुधार किया।
  • करिकुलम प्रभाव: मिश्रित करिकुलम प्रशिक्षण ($\alpha_1 \to \alpha_4$) ने "केवल आसान" और "केवल कठिन" प्रशिक्षण रणनीतियों दोनों की तुलना में बेहतर प्रदर्शन किया, विशेष रूप से कठिन स्तरों और OOD कार्यों पर।

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

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

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

संक्षेप में, यह शोध पत्र प्रदर्शित करता है कि ऑटो-वेरिफिएबल ऑप्टिमाइज़ेशन कार्यों और पूरक ऑफलाइन/ऑनलाइन RL रणनीतियों का लाभ उठाकर, LLMs विस्तारवादी खोज स्थानों को अधिक प्रभावी ढंग से नेविगेट करना सीख सकते हैं, जिससे उनके ऑप्टिमाइज़ेशन प्रदर्शन और उनके अंतर्निहित स्थानिक एवं तार्किक कौशल दोनों में सुधार होता है।