🤖 machine learning

LLM Priors for ERM over Programs

यह शोधपत्र \textsc{LLM-PV} को प्रस्तुत करता है, जो एक प्रपोज़-एंड-वेरिफाई (प्रस्ताव-और-सत्यापन) ढांचा है जो थकाऊ गणना (exhaustive enumeration) या ग्रेडिएंट अपडेट के बिना डिस्क्रीट प्रोग्राम क्लासेस पर कुशलतापूर्वक एम्पिरिकल रिस्क मिनिमाइजेशन करने के लिए प्री-ट्रेन्ड एलएलएम प्रायर्स (pretrained LLM priors) का लाभ उठाता है, जिससे उन एल्गोरिद्मिक कार्यों पर सुदृढ़ सामान्यीकरण सक्षम होता है जहाँ पारंपरिक विधियाँ विफल हो जाती हैं।

मूल लेखक: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

प्रकाशित 2026-07-03

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

CC BY 4.0

मूल लेखक: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

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

एक बड़ी समस्या: घास के ढेर में सुई ढूँढना

कल्पना कीजिए कि आप एक कंप्यूटर को एक गुप्त नियम सिखाने की कोशिश कर रहे हैं। नियम सरल है, जैसे "यदि संख्या 3 से विभाज्य है, तो 'हाँ' कहें; अन्यथा, 'नहीं' कहें।" लेकिन कंप्यूटर को नियम पता नहीं है; वह केवल संख्याओं के कुछ उदाहरण और उनके उत्तर देखता है।

कंप्यूटर विज्ञान की दुनिया में, इस नियम को खोजने के दो मुख्य तरीके हैं:

"ब्रूट फ़ोर्स" (Brute Force) जासूस: यह विधि ब्रह्मांड के हर एक संभव नियम को एक-एक करके लिखने की कोशिश करती है और फिर जाँचती है कि क्या वह उदाहरणों पर फिट बैठता है।
- समस्या: यदि नियम थोड़ा भी जटिल है, तो संभावित नियमों की संख्या इतनी विशाल हो जाएगी (जैसे पृथ्वी के सभी समुद्र तटों पर रेत के कणों की संख्या) कि इस विधि को पूरा होने में ब्रह्मांड की आयु से भी अधिक समय लगेगा। यह बहुत धीमा है।
"ग्रेडिएंट डिसेंट" (Gradient Descent) छात्र: आधुनिक AI (जैसे कि वे चैटबॉट्स जिनका आप उपयोग करते हैं) आमतौर पर इसी तरह सीखते हैं। यह एक अनुमान से शुरू होता है और धीरे-धीरे अपने आंतरिक 'नॉब्स' (knobs) को ट्यून करता है ताकि बेहतर परिणाम मिल सकें, ठीक वैसे ही जैसे एक छात्र परीक्षा के लिए तैयारी करने के लिए छोटी गलतियाँ करता है और उन्हें सुधारता है।
- समस्या: कुछ प्रकार के तार्किक नियमों (जैसे कि यह जाँचना कि संख्या अभाज्य है या नहीं, या विशिष्ट पैटर्न गिनना) के लिए, यह "ट्यूनिंग" करने वाली विधि अटक जाती है। यह अभ्यास टेस्ट को पूरी तरह से याद कर सकती है लेकिन एक नए, थोड़े अलग प्रश्न के सामने पूरी तरह विफल हो सकती है। यह उस छात्र की तरह है जिसने उत्तर तो रट लिए लेकिन गणित नहीं सीखा।

नया समाधान: LLM-PV (एक स्मार्ट लाइब्रेरियन)

लेखक एक तीसरा तरीका प्रस्तावित करते हैं जिसे LLM-PV कहा जाता है। इसे एक स्मार्ट लाइब्रेरियन (चतुर पुस्तकालयाध्यक्ष) को काम में रखने के रूप में सोचें जो आपको नियम खोजने में मदद करता है।

यहाँ प्रक्रिया चरण-दर-चरण दी गई है:

प्रस्ताव (लाइब्रेरियन का अनुमान): लाइब्रेरी की हर एक किताब को जाँचने (ब्रूट फ़ोर्स) या पूरी लाइब्रेरी को फिर से लिखने (ग्रेडिएंट डिसेंट) के बजाय, आप स्मार्ट लाइब्रेरियन (एक प्री-ट्रेन्ड लार्ज लैंग्वेज मॉडल) से कुछ सुझाव मांगते हैं।
- जादू: लाइब्रेरियन ने लाखों किताबें और कोड स्निपेट्स पढ़े हैं। जब आप उसे अपने उदाहरण दिखाते हैं, तो वह केवल तुक्का नहीं लगाता। वह अपने "अंतर्ज्ञान" (prior knowledge) का उपयोग करके कुछ संभाव्य (plausible) नियम सुझाता है जो काम कर सकते हैं। यह खोज को "सभी संभावित नियमों" से घटाकर "कुछ संभावित उम्मीदवारों" तक सीमित कर देता है।
सत्यापन (टेस्ट ड्राइव): लाइब्रेरियन इन नियमों को वास्तविक कंप्यूटर कोड के रूप में लिखता है। आप फिर इन कोड स्निपेट्स को अपने उदाहरणों के विरुद्ध चलाकर देखते हैं कि वास्तव में कौन सा काम करता है।
- महत्वपूर्ण बिंदु: लाइब्रेरियन को टेस्ट परिणामों के आधार पर अपना मन बदलने की अनुमति नहीं है। वह केवल सुझाव देता है। विजेता का चयन पूरी तरह से डेटा के विरुद्ध कोड की जाँच करके किया जाता है।
चयन (विजेता): आप उस कोड स्निपेट को चुनते हैं जो सबसे अधिक उत्तरों को सही बताता है।

यह एक बड़ी बात क्यों है

पेपर दिखाता है कि यह "स्मार्ट लाइब्रेरियन" दृष्टिकोण अविश्वसनीय रूप से कुशल है।

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

एक वास्तविक दुनिया का उदाहरण: बेकिंग सीखना

कल्पना कीजिए कि आप केक की गुप्त रेसिपी सीखना चाहते हैं।

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

निष्कर्ष

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

तकनीकी सारांश: प्रोग्राम्स पर ERM के लिए LLM Priors

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

यह शोध पत्र लेबल वाले डेटा से लघु, असतत (discrete) प्रोग्राम विवरणों (जैसे, "Python code") को सीखने में नमूना दक्षता (sample efficiency) और गणना दक्षता (computational efficiency) के बीच के मौलिक तनाव को संबोधित करता है।

शास्त्रीय लर्निंग थ्योरी (PAC learning) बताती है कि यदि कोई लक्षित फलन (target function) $\Sigma$ पर लंबाई $L$ का एक छोटा प्रोग्राम विवरण स्वीकार करता है, तो इसे प्रोग्रामों के वर्ग पर एम्पिरिकल रिस्क मिनिमाइजेशन (ERM) के माध्यम से $\tilde{O}(L \log |\Sigma|)$ उदाहरणों से सीखा जा सकता है। हालाँकि, ERM को लागू करने के लिए संभावित प्रोग्रामों का व्यापक अन्वेषण (exhaustive enumeration) आवश्यक है, जो $\Theta(|\Sigma|^L)$ के रूप में घातीय (exponentially) रूप से बढ़ता है, जिससे मध्यम $L$ के लिए भी यह गणनात्मक रूप से अव्यवहार्य हो जाता है।

इसके विपरीत, उच्च-क्षमता वाले न्यूरल नेटवर्क पर स्टोकेस्टिक ग्रेडिएंट डिसेंट (SGD) का उपयोग करने वाले आधुनिक डीप लर्निंग दृष्टिकोण स्पष्ट अन्वेषण से बचते हैं और गणनात्मक रूप से कुशल होते हैं। फिर भी, स्टोकेस्टिक क्वेरी (SQ) फ्रेमवर्क में सैद्धांतिक परिणाम संकेत देते हैं कि ग्रेडिएंट-आधारित विधियाँ संरचित, "SQ-कठिन" परिवारों (जैसे, पैरिटी फंक्शन्स और क्रिप्टोग्राफिक प्रिमिटिव्स) के साथ संघर्ष करती हैं। ये विधियाँ सफल होने के लिए घातीय संख्या में नमूनों की आवश्यकता रखती हैं क्योंकि ग्रेडिएंट इंटरफ़ेस लक्षित नियम की असतत संरचना के साथ ठीक से मेल नहीं खाता है, जिससे प्रशिक्षण अनुक्रम लंबाई से परे सामान्यीकरण (generalization) करने में विफलता आती है।

केंद्रीय प्रश्न यह है: क्या हम पूर्ण अन्वेषण की पूरी लागत चुकाए बिना, छोटे प्रोग्रामों पर ERM की नमूना दक्षता को पुनः प्राप्त कर सकते हैं?

कार्यप्रणाली: LLM-PV

लेखक LLM-PV (LLM Propose-and-Verify) प्रस्तावित करते हैं, जो एक लर्निंग एल्गोरिदम है जो प्री-ट्रेन्ड लार्ज लैंग्वेज मॉडल (LLM) को केवल एक प्रेडिक्टर के रूप में नहीं, बल्कि ERM के लिए एक सर्च प्रायर (search prior) के रूप में उपयोग करता है।

एल्गोरिदम

LLM-PV प्रस्ताव (proposal) और चयन (selection) की भूमिकाओं को अलग करता है:

प्रस्ताव (The Prior): एक प्री-ट्रेन्ड LLM को एक प्रशिक्षण सेट $S_{tr}$ के साथ प्रॉम्प्ट किया जाता है ताकि उम्मीदवार प्रोग्रामों पर एक डेटा-डिपेंडेंट वितरण प्रेरित किया जा सके। LLM कुछ चुनिले उम्मीदवार प्रोग्राम (या संपादन) उत्पन्न करता है जो डेटा की व्याख्या करने की परिकल्पना करते हैं।
सत्यापन (The ERM Step): प्रत्येक उम्मीदवार प्रोग्राम को एक होल्ड-आउट वैलिडेशन सेट $S_{val}$ पर कंपाइल और निष्पादित किया जाता है। जो प्रोग्राम कंपाइल होने में विफल रहते हैं, रुकते नहीं हैं (do not halt), या अमान्य आउटपुट देते हैं, उन्हें हटा दिया जाता है।
चयन (Selection): एल्गोरिदम उस प्रोग्राम का चयन करता है जिसमें न्यूनतम वैलिडेशन एरर होता है। महत्वपूर्ण रूप से, LLM पर कोई ग्रेडिएंट अपडेट नहीं किया जाता है, और खोज के दौरान LLM के सैंपलिंग वितरण को अनुकूलित करने के लिए वैलिडेशन फीडबैक का उपयोग नहीं किया जाता है। LLM केवल एक इंडक्टिव बायस मैकेनिज्म के रूप में कार्य करता है।

सैद्धांतिक ढांचा (Theoretical Framework)

शोध पत्र "प्रपोज-एंड-वेरिफाई" गारंटी का उपयोग करके LLM-PV के प्रदर्शन को औपचारिक रूप देता है। यदि LLM का प्रस्ताव वितरण उन प्रोग्रामों पर एक गैर-नगण्य द्रव्यमान (non-negligible mass) $p_\epsilon(S_{tr})$ रखता है जिनका जनसंख्या एरर $\le \epsilon$ है, तो एक अच्छे हाइपोथीसिस को खोजने के लिए आवश्यक परीक्षणों की संख्या $k$ , $O(\log(1/\delta) / p_\epsilon(S_{tr}))$ के रूप में स्केल होती है। यह एक्सपोनेंशियल सर्च स्पेस $|\Sigma|^L$ को प्रभावी सर्च साइज $1/p_\epsilon(S_{tr})$ से बदल देता है।

लेखक यह दिखाने के लिए सैद्धांतिक निचली सीमाएं (lower bounds) भी प्रदान करते हैं कि प्लांटेड $k$ -पैरिटी समस्याओं के लिए, परिमित-परिशुद्धता मिनी-बैच कोऑर्डिनेट SGD को $\Omega(\sqrt{N}/2^b)$ नए उदाहरणों की आवश्यकता होती है (जहाँ $N$ संभावित लक्ष्यों की संख्या है), जबकि एन्यूमरेशन के लिए $\Theta(|\Sigma|^L)$ समय लगता है। यह एक ऐसा क्षेत्र स्थापित करता है जहाँ न तो सहज एन्यूमरेशन और न ही मानक ग्रेडिएंट-आधारित प्रशिक्षण सफल होता है, जो LLM-PV दृष्टिकोण को प्रेरित करता है।

मुख्य योगदान

कंप्यूट-सैंपल तनाव को औपचारिक बनाना: शोध पत्र एक विशिष्ट छोटे-डेटा शासन (प्लांटेड $k$ -पैरिटी) को अलग करता है जहाँ परिमित-क्लास ERM नमूना-कुशल है लेकिन गणनात्मक रूप से कठिन है, जबकि ग्रेडिएंट-आधारित प्रशिक्षण गणनात्मक रूप से सुविधाजनक है लेकिन SQ-हार्डनेस के कारण नमूना-अकुशल है।
LLM-PV एल्गोरिदम: एक स्वच्छ "प्रपोज-एंड-वेरिफाई" पाइपलाइन का परिचय जो प्री-ट्रेन्ड LLM का उपयोग सख्ती से एक प्रस्ताव तंत्र के रूप में करता है। यह ERM की ऑडिटेबिलिटी और सैद्धांतिक गारंटी (होल्ड-आउट एरर के आधार पर चयन) को बनाए रखता है, जबकि LLM की तर्कसंगत हाइपोथीसिस पर ध्यान केंद्रित करने की क्षमता का लाभ उठाता है।
नियम रिकवरी का अनुभवजन्य प्रमाण: विविध एल्गोरिथमिक कार्यों (पैरिटी वेरिएंट, पैटर्न मैचिंग, पैलिंड्रोम, Dyck-2, प्राइमैलिटी टेस्टिंग, सेलुलर ऑटोमेटा, और SHA-256 पैरिटी) पर व्यापक प्रयोग दिखाते हैं कि LLM-PV केवल 200 लेबल वाले उदाहरणों से सटीक अंतर्निहित नियम को पुनः प्राप्त कर लेता है।
लंबाई सामान्यीकरण (Length Generalization): SGD-ट्रेन्ड ट्रांसफॉर्मर, फाइन-ट्यून्ड मॉडल, या इन-कॉन्टेक्स्ट लर्निंग (ICL) बेसलाइन्स के विपरीत, जो अक्सर प्रशिक्षण वितरण को याद कर लेते हैं और लंबी इनपुट अनुक्रमों पर विफल हो जाते हैं, LLM-PV अक्सर डायमेंशन-इनवेरिएंट प्रोग्राम सिंथेसाइज करता है जो प्रशिक्षण सेट से कहीं अधिक लंबी इनपुट लंबाई तक पूरी तरह से सामान्यीकरण करते हैं।
ऑडिटेबिलिटी: विधि एक निष्पादन योग्य, मानव-पठनीय कोड और एक पूर्ण रीजनिंग ट्रेस (प्रस्तावित प्रोग्रामों का अनुक्रम और उनके वैलिडेशन एरर) उत्पन्न करती है, जिससे सीखने की प्रक्रिया का सीधा डिबगिंग और मैकेनिस्टिक सत्यापन संभव होता है।

परिणाम

लेखकों ने LLM-PV का क्लासिक ML (XGBoost, SVM, जेनेटिक एल्गोरिदम), SGD-ट्रेन्ड मॉडल (स्क्रैच से और फाइन-ट्यून्ड), और बड़े इंस्ट्रक्शन-ट्यून्ड मॉडल्स के साथ ICL सहित कई बेसलाइन्स के विरुद्ध मूल्यांकन किया।

एल्गोरिद्मिक कार्य: 10-पैरिटी, सेलुलर ऑटोमेटा पैरिटी, और प्राइमैलिटी टेस्टिंग जैसे कार्यों पर, मानक बेसलाइन्स (30B+ पैरामीटर वाले ICL मॉडल्स सहित) टेस्ट लेंथ ( $n=100$ ) पर लगभग संयोग (50% सटीकता) के पास प्रदर्शन करते हैं, भले ही उन्हें 200 उदाहरणों पर प्रशिक्षित किया गया हो। इसके विपरीत, LLM-PV ने उन्हीं 200 उदाहरणों के साथ इन कार्यों पर 100% टेस्ट सटीकता प्राप्त की।
सामान्यीकरण: जब छोटे अनुक्रमों ( $n=10$ ) पर प्रशिक्षित किया गया और लंबे अनुक्रमों ( $n=100$ ) पर टेस्ट किया गया, तो SGD और फाइन-ट्यूनिंग बेसलाइन्स संयोग सटीकता पर गिर गए। LLM-PV ने उच्च सटीकता बनाए रखी, सफलतापूर्वक ऐसे नियम सिंथेसाइज किए जो इनपुट लंबाई के प्रति इनवेरिएंट थे।
डेटा स्केलिंग: SGD-आधारित मॉडल्स के लिए प्रशिक्षण सेट का आकार बढ़ाने (100k उदाहरणों तक) से भी पैरिटी और सेलुलर ऑटोमेटा कार्यों पर सामान्यीकरण की विफलता हल नहीं हुई, जो ग्रेडिएंट-आधारित लर्नर्स के लिए इन कार्यों की SQ-हार्ड प्रकृति की पुष्टि करता है।
टूल उपयोग: शोध पत्र नोट करता है कि हालांकि टूल-ऑगमेंटेड ICL (जहाँ मॉडल कोड चला सकता है) डायरेक्ट प्रॉम्प्टिंग की तुलना में प्रदर्शन में सुधार करता है, फिर भी यह एल्गोरिद्मिक नियमों को विश्वसनीय रूप से रिकवर करने में विफल रहता है। LLM-PV की सफलता टूल एक्सेस के बजाय विशिष्ट सर्च ऑब्जेक्टिव (प्रोग्राम प्रस्तावित करना और वैलिडेशन एरर द्वारा चयन करना) के कारण है।
टेबुलर डेटा: मानक टेबुलर बेंचमार्क पर, LLM-PV ने मजबूत टेबुलर लर्नर्स के तुल्य प्रदर्शन किया, जो सुझाव देता है कि यह दृष्टिकोण केवल सिंथेटिक सीक्वेंस कार्यों तक सीमित नहीं है।

महत्व और दावे

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

मुख्य महत्व भूमिकाओं के पृथक्करण में निहित है: LLM का उपयोग केवल हाइपोथीसिस प्रस्तावित करने के लिए किया जाता है, जबकि लर्निंग ऑब्जेक्टिव निष्पादन योग्य सत्यापन और होल्ड-आउट एरर पर आधारित रहता है। यह दृष्टिकोण:

प्रेडिक्टर्स के "ब्लैक बॉक्स" स्वभाव से बचता है क्योंकि यह स्पष्ट, सत्यापन योग्य कोड आउटपुट करता है।
उन संरचित, असतत कार्यों पर ग्रेडिएंट-आधारित तरीकों की नमूना अक्षमता को दूर करता है जहाँ लक्ष्य का एक संक्षिप्त विवरण मौजूद होता है।
एक ऐसा तंत्र प्रदान करता है जो लंबाई के सामान्यीकरण (length generalization) की अनुमति देता है जिसे मानक डीप लर्निंग विधियाँ प्राप्त करने में विफल रहती हैं।

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