Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

तकनीकी सारांश: LLM-सहायता प्राप्त एल्गोरिदम खोज के लिए कॉन्ट्रास्टिव कॉन्सेप्ट-ट्री सर्च (CCTS)

समस्या विवरण

लार्ज लैंग्वेज मॉडल (LLM)-सहायता प्राप्त एल्गोरिदम खोज एक पुनरावृत्ति (iterative), ब्लैक-बॉक्स अनुकूलन प्रक्रिया के रूप में कार्य करती है जहाँ एक LLM संभावित प्रोग्राम प्रस्तावित करता है, और एक बाहरी इवैल्यूएटर (evaluator) कार्य पर फीडबैक प्रदान करता है। जबकि हालिया प्रतिमानों (जैसे, Funsearch, AlphaEvolve) ने कॉम्बिनेटरियल समस्याओं (जैसे, Erdős-शैली की समस्याएं) के समाधानों को सफलतापूर्वक पुनः खोजने या सुधारने में सफलता प्राप्त की है, वे काफी हद तक फिटनेस-संचालित विकासवादी अपडेट (evolutionary updates) पर निर्भर करते हैं। इन मौजूदा प्रणालियों में, पैरेंट चयन प्रोग्राम के कच्चे प्रदर्शन (फिटनेस) द्वारा निर्धारित होता है, और खोज प्रोग्रामों की वंशावली (lineage) पर एक वॉक के रूप में आगे बढ़ती है जो प्रदर्शन के क्रम में व्यवस्थित होती है।

इस दृष्टिकोण की एक महत्वपूर्ण सीमा यह है कि प्रोग्राम स्पेस संरचनात्मक रूप से कमजोर रहता है। भले ही LLM द्वारा नियंत्रित किया गया हो, उत्पन्न एल्गोरिदम अक्सर स्पष्ट स्थानीयता (locality), सुचारू भिन्नता (smooth variation), या संरचनात्मक संयोजन (compositional structure) का अभाव रखते हैं जिनका उपयोग खोज एल्गोरिदम द्वारा किया जा सके। फलस्वरूप, मार्गदर्शन मुख्य रूप से कच्चे फिटनेस संकेतों और LLM के निहित पूर्व ज्ञान (implicit prior) से प्राप्त होता है, न कि इस स्पष्ट समझ से कि एल्गोरिदम के कौन से अर्थपूर्ण घटक (semantic components) वास्तव में उपयोगी हैं। यह शोध पत्र इस प्रश्न को संबोधित करता है कि खोज दक्षता और व्याख्यात्मकता (interpretability) में सुधार के लिए LLM के आंतरिक प्रोग्राम प्रतिनिधित्व का अधिकतम लाभ कैसे उठाया जाए।

कार्यप्रणाली: कॉन्ट्रास्टिव कॉन्सेप्ट-ट्री सर्च (CCTS)

लेखक कॉन्ट्रास्टिव कॉन्सेप्ट-ट्री सर्च (CCTS) पेश करते हैं, जो एक ढांचा है जो खोज मार्गदर्शन को कच्चे फिटनेस से बदलकर एक सीखे हुए, पदानुक्रमित अर्थपूर्ण अवधारणा स्थान (hierarchical semantic concept space) की ओर ले जाता है। मूल परिकल्पना यह है कि एल्गोरिदम को एक अंतर्निहित अर्थपूर्ण अवधारणा स्थान के रूप में वर्णित किया जा सकता है जो एक पदानुक्रम (hierarchy) के रूप में व्यवस्थित है, जहाँ नोड्स (nodes) अवधारणाओं का प्रतिनिधित्व करते हैं और किनारे (edges) परिशोधन या विशिष्टता (refinement or specialization) को एनकोड करते हैं।

1. अवधारणा प्रतिनिधित्व और ट्री निर्माण

• विशेषता निष्कर्षण (Feature Extraction): प्रत्येक संभावित प्रोग्राम $x$ को एक अर्थपूर्ण विशेषता प्रतिनिधित्व $b = \Phi(x)$ में मैप किया जाता है, जिसे LLM को प्रासंगिक अवधारणाओं की एक सूची उत्पन्न करने के लिए प्रॉम्प्ट करके निकाला जाता है।
• पदानुक्रमित संरचना (Hierarchical Structure): इन अवधारणाओं को एक रूटेड कॉन्सेप्ट ट्री (rooted concept tree) में व्यवस्थित किया जाता है। एक कॉन्सेप्ट वेक्टर $b$ एक इंडिकेटर वेक्टर है जहाँ सक्रियण पूर्वज-बंद (ancestor-closed) होते हैं (एक चाइल्ड कॉन्सेप्ट को सक्रिय करने का अर्थ उसके सभी पूर्वजों को सक्रिय करना है)। यह ट्री गतिशील है, जो खोज के दौरान नई अवधारणाओं की खोज के साथ बढ़ता जाता है।

2. कॉन्सेप्ट उपयोगिता का कॉन्ट्रास्टिव लर्निंग (Contrastive Learning of Concept Utility)

केवल उनके फिटनेस स्कोर के आधार पर पैरेंट चुनने के बजाय, CCTS यह सीखता है कि कौन सी अवधारणाएं अनुभवजन्य रूप से उच्च प्रदर्शन से जुड़ी हैं:

• विभाजन (Partitioning): मूल्यांकित प्रोग्रामों के संग्रह को एक प्रदर्शन थ्रेशोल्ड के आधार पर "अच्छे" ($y_i \ge \tau_t$) और "बुरे" ($y_i < \tau_t$) उपसमूहों में विभाजित किया जाता है।
• मॉडल फिटिंग (Model Fitting): अच्छे और बुरे उपसमूहों के फीचर वितरण पर दो संभाव्यता मॉडल, $\hat{p}_{\eta^+}(b)$ और $\hat{p}_{\eta^-}(b)$, क्रमशः फिट किए जाते हैं। लेखक एक ट्री-स्ट्रक्चर्ड पारसेन एस्टिमेटर (TPE) शैली के दृष्टिकोण का उपयोग करते हैं जो एक फैक्टराइज्ड पदानुक्रमित बर्नौली मॉडल (factorized hierarchical Bernoulli model) का उपयोग करता है। यह मॉडल अपने पैरेंट के सापेक्ष फीचर्स की सशर्त स्वतंत्रता (conditional independence) को मानता है।
• लाइकलीहुड रेशियो स्कोरिंग (Likelihood Ratio Scoring): प्रत्येक प्रोग्राम के लिए एक लाइकलीहुड-रेशियो स्कोर (लॉग-कॉन्सेप्ट उपयोगिता) की गणना की जाती है:
  $$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$$
  यह स्कोर यह मात्रा निर्धारित करता है कि विशिष्ट अवधारणाओं का सेट उच्च-प्रदर्शन वाले समाधानों को निम्न-प्रदर्शन वाले समाधानों से कितनी मजबूती से अलग करता है।

3. पैरेंट चयन और खोज गतिशीलता (Parent Selection and Search Dynamics)

• बायस्ड सैंपलिंग (Biased Sampling): पैरेंट को उनके लाइकलीहुड-रेशियो स्कोर के आनुपातिक संभावना के साथ संग्रह से चुना जाता है। यह खोज को उन प्रोग्रामों की ओर पक्षपाती बनाता है जिनमें उन अवधारणाओं के संयोजन शामिल हैं जो अनुभवजन्य रूप से सुधार से जुड़े हैं।
• एक्सप्लोरेशन मैकेनिज्म (Exploration Mechanism): समयपूर्व अभिसरण (premature convergence) को रोकने और नई अवधारणाओं की खोज को प्रोत्साहित करने के लिए, CCTS एक हल्का एक्सप्लोरेशन मैकेनिज्म शामिल करता है। इसमें शामिल हैं:
  • बीटा प्रायर्स (Beta Priors): काउंट्स को स्मूथ करना ताकि यह सुनिश्चित हो सके कि नई खोजी गई अवधारणाओं की संभावना कभी शून्य न हो।
  • नोवेल्टी बायस (Novelty Bias): उन अवधारणाओं को कम महत्व देना जिन्हें बार-बार आजमाया गया है, जिससे कॉन्सेप्ट ट्री के कम खोजे गए क्षेत्रों को प्राथमिकता मिले।
  • मिश्रण रणनीति (Mixture Strategy): एक्सप्लोइटेशन (सीखे गए कॉन्ट्रास्टिव मॉडल पर आधारित) और एक्सप्लोरेशन (नोवेल्टी पर आधारित) का एक मिश्रण, चाइल्ड जनरेशन के लिए LLM के प्रॉम्प्ट में अवधारणाओं को इंजेक्ट करने के लिए मार्गदर्शन करता है।

मुख्य योगदान

1. स्पष्ट अर्थपूर्ण संरचना (Explicit Semantic Structure): यह शोध पत्र एल्गोरिदम स्पेस की गुप्त संरचना को एक पदानुक्रमित कॉन्सेप्ट ट्री सीखकर स्पष्ट बनाने का प्रस्ताव देता है, जो मानक विकासवादी एल्गोरिदम द्वारा उपयोग किए जाने वाले असंरचित प्रोग्राम स्पेस से आगे जाता है।
2. कॉन्ट्रास्टिव मार्गदर्शन (Contrastive Guidance): यह एक कॉन्ट्रास्टिव सांख्यिकीय ढांचे को पेश करता है जो यह सीखने में सक्षम है कि किन अवधारणाओं को प्राथमिकता दी जानी चाहिए और, महत्वपूर्ण रूप से, किन अवधारणाओं से बचना चाहिए, न कि केवल यह ट्रैक करना कि कौन से प्रोग्राम सबसे अच्छा प्रदर्शन करते हैं।
3. व्याख्यात्मकता (Interpretability): यह विधि व्याख्या योग्य, कार्य-विशिष्ट कॉन्सेप्ट ट्री बनाती है जो खोज के दौरान खोजी गई एल्गोरिदम रणनीतियों के अर्थपूर्ण ढांचे को प्रकट करती है।
4. सिंथेटिक सत्यापन (Synthetic Validation): लेखकों ने एक "टीचर" कॉन्सेप्ट ट्री और ग्राउंड-ट्रुथ उपयोगिताओं के साथ एक नियंत्रित सिंथेटिक वातावरण बनाया है। यह उन्हें यह सत्यापित करने की अनुमति देता है कि CCTS अंतर्निहित अर्थपूर्ण संरचना को पुनः प्राप्त करता है और देखे गए खोज गतिकी (search dynamics) विशिष्ट LLM आर्टिफैक्ट्स के बजाय कॉन्सेप्ट उपयोगिताओं के सीखने से संचालित होते हैं।

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

लेखकों ने सर्कल पैकिंग, अरिथमेटिक काकेया अनुमान (Arithmetic Kakeya conjecture), हीलब्रोन ट्रायंगल समस्या (Heilbronn's triangle problem), और स्क्वायर्स-इन-स्क्वायर समस्या सहित ओपन एर्डोस-प्रकार की कॉम्बिनेटरियल समस्याओं के बेंचमार्क पर CCTS का मूल्यांकन किया।

• प्रदर्शन लाभ (Performance Gains): CCTS ने कई कार्यों में बेसलाइन रणनीतियों (यूनिफॉर्म, ग्रीडी, और $k$-एलीट चयन) की तुलना में लगातार उच्च स्कोर और तेज़ सुधार प्राप्त किया।
• सुधार का तंत्र (Mechanism of Improvement): विश्लेषण से पता चला कि प्रदर्शन लाभ मुख्य रूप से यह सीखने से प्रेरित हैं कि किन अवधारणाओं से बचना है। सफल रन ने उच्च-उपयोगिता वाली अवधारणाओं का एक समान सेट पहचाना, लेकिन निम्न-उपयोगिता (हानिकारक) अवधारणाओं को दबाने की काफी बेहतर क्षमता प्रदर्शित की। यह सुझाव देता है कि CCTS भ्रामक सहसंबंधों के कारण होने वाली अनुत्पादक खोज को कम करके खोज को स्थिर करता है।
• सिंथेटिक सत्यापन: सिंथेटिक वातावरण में, सीखे गए कॉन्सेप्ट उपयोगिताओं ने ग्राउंड-ट्रुथ टीचर उपयोगिताओं के साथ मजबूत सहसंबंध ($r=0.94$) दिखाया, जिससे पुष्टि होती है कि विधि प्रभावी ढंग से सार्थक अर्थपूर्ण प्रतिनिधित्व को पुनः प्राप्त करती है।
• संरचना निर्भरता (Structure Dependence): पाया गया कि एक्सप्लोरेशन और एक्सप्लोइटेशन के बीच इष्टतम संतुलन अंतर्निहित कॉन्सेप्ट ट्री (जैसे, ब्रांचिंग रेशियो) की संरचना पर निर्भर करता है, जो बताता है कि खोज रणनीतियों को समस्या के टोपोलॉजी के अनुसार अनुकूलित किया जाना चाहिए।

महत्व और दावे

यह शोध पत्र वर्तमान LLM-सहायता प्राप्त एल्गोरिदम खोज में एक मौलिक बेमेल (mismatch) को संबोधित करने का दावा करता है: उच्च-स्कोर वाले एल्गोरिदम आवश्यक रूप से मजबूत वंशज उत्पन्न नहीं करते हैं क्योंकि एक कमजोरly संरचित स्थान में फिटनेस, 'इवॉलेबिलिटी' (evolvability) का एक खराब प्रॉक्सी है। कच्चे फिटनेस से सुधार के अर्थपूर्ण साक्ष्य की ओर चयन को बदलकर, CCTS खोज को एक ऐसे कॉन्सेप्ट स्पेस में संचालित करने की अनुमति देता है जहाँ दूरी, पुनर्संयोजन (recombination) और खोज दिशा सार्थक है।

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