🤖 AI

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

यह शोध पत्र GATS को प्रस्तुत करता है, जो एक नियोजन ढांचा (planning framework) है जो महंगी LLM इन्फरेंस को एक लेयर्ड वर्ल्ड मॉडल और UCB1-आधारित ट्री सर्च से प्रतिस्थापित करता है ताकि विविध जटिल कार्यों में 100% सफलता दर और नियत (deterministic), शून्य-कॉल नियोजन प्राप्त किया जा सके, जो LATS और ReAct जैसी मौजूदा विधियों से काफी बेहतर प्रदर्शन करता है।

मूल लेखक: Maureese Williams, Dymitr Nowicki

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

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

CC BY 4.0

मूल लेखक: Maureese Williams, Dymitr Nowicki

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

कल्पना कीजिए कि आप एक विशाल, पेचीदा भूलभुलैया (maze) को सुलझाने की कोशिश कर रहे हैं। आपके पास एक सुपर-स्मार्ट दोस्त है (एक लार्ज लैंग्वेज मॉडल, या LLM) जो आपसे बात कर सकता है और सुझाव दे सकता है कि किस तरफ मुड़ना है। लेकिन यहाँ एक पेंच है: हर बार जब आप अपने दोस्त से सलाह मांगते हैं, तो उन्हें सोचने के लिए एक लंबी नींद लेनी पड़ती है, और कभी-कभी एक ही सवाल पूछने पर वे हर बार अलग अंदाज़ा लगाते हैं। यदि भूलभुलैया में डेड एंड (रास्ते का बंद होना) हैं या लंबे दौर के मोड़ों की आवश्यकता है, तो हर एक कदम पर अपने दोस्त से मदद मांगना महंगा और भ्रमित करने वाला हो जाता है।

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

पुराना तरीका: "हर कदम पर पूछने" वाला दृष्टिकोण

पिछले तरीके, जैसे कि ReAct और LATS, थोड़े उस हाइकर (हाइकर) की तरह थे जो रास्ते में हर मोड़ पर अपने गाइड से रुककर पूछता है, "मुझे किस दिशा में जाना चाहिए?"

ReAct बस एक बार पूछता है और आगे बढ़ जाता है। यह तेज़ है, लेकिन अक्सर यह डेड एंड (बंद रास्तों) में फंस जाता है। उनके परीक्षणों में, इस पद्धति ने पेचीदा भूलभुलैया के परिदृश्यों में केवल 64% सफलता प्राप्त की।
LATS अधिक स्मार्ट है; यह गाइड से पूछता है, फिर अगले कदम के बारे में फिर से पूछता है, और फिर से, संभावनाओं का एक पेड़ (tree) बनाता है। लेकिन क्योंकि यह पेड़ की हर एक शाखा के लिए गाइड (LLM) से पूछता है, इसलिए यह थक जाता है और महंगा हो जाता है। परीक्षणों में, LATS 92% बार सफल रहा, लेकिन इसे प्रति कार्य गाइड से लगभग 37 बार पूछना पड़ता था। इसके अलावा, क्योंकि गाइड कभी-कभी रैंडम अनुमान लगाता है, यदि आप एक ही भूलभुलैया को दो बार आज़माते हैं, तो आपको एक अलग रास्ता मिल सकता है।

नया तरीका: GATS (द "मैप-मेकर" रणनीति)

GATS खेल बदल देता है। हर मोड़ के लिए गाइड से पूछने के बजाय, GATS एक लेयर्ड वर्ल्ड मॉडल (Layered World Model) का उपयोग करके अपना आंतरिक मानचित्र (map) बनाता है। सोचिए कि यह मानचित्र ज्ञान की तीन परतों वाला है:

लेयर 1 (सटीक नियम पुस्तिका): उन कार्यों के लिए जिन्हें सिस्टम पहले से पूरी तरह जानता है (जैसे "यदि मैं यह बटन दबाता हूँ, तो दरवाज़ा खुल जाता है"), यह एक सरल, त्वरित जांच का उपयोग करता है। इसमें सोचने की कोई आवश्यकता नहीं है। यह वैसा ही है जैसे यह जानना कि 2+2 हमेशा 4 होता है।
लेयर 2 (अनुभव लॉग): यदि सिस्टम ने कोई क्रिया पहले देखी है लेकिन उसके लिए उसके पास कोई सटीक नियम नहीं है, तो वह अपनी पिछली यात्राओं की डायरी चेक करता है। "पिछली बार जब मैंने यह किया, तो यह 10 में से 9 बार काम आया।" यह डेटा से सीखा जाता है, अनुमान से नहीं।
लेयर 3 (सुपर-जीनियस दोस्त): केवल तभी जब सिस्टम किसी बिल्कुल नई और अज्ञात चीज़ का सामना करता है, तब वह LLM गाइड को जगाता है। लेकिन यहाँ जादू है: एक बार जब गाइड उत्तर दे देता है, तो GATS उस उत्तर को मानचित्र में लिख लेता है। अगली बार जब वही स्थिति आती है, तो GATS बस मानचित्र देख लेता है। वह उस विशिष्ट चीज़ के लिए गाइड से दोबारा कभी नहीं पूछता।

परिणाम: गति, निश्चितता और सफलता

शोधकर्ताओं ने इसे 100 सिंथेटिक प्लानिंग टास्क पर टेस्ट किया जो पेचीदा थे, जिनमें ब्रांचिंग पाथ और डेड एंड शामिल थे।

GATS की सफलता दर 100% रही।
LATS की 92% रही।
ReAct की 64% रही।

लेकिन असली बात यह है कि GATS ने इन कार्यों के दौरान प्लानिंग के समय LLM को शून्य कॉल किया। इसने सारा काम अपने स्वयं के मानचित्र और नियमों का उपयोग करके किया। क्योंकि यह LLM के रैंडम अनुमानों पर निर्भर नहीं था, GATS ने हर बार एक ही सटीक योजना बनाई। इसमें जीरो वेरिएंस (शून्य भिन्नता) था।

उन्होंने 12 कठिन श्रेणियों (जैसे कोडिंग वर्कफ़्लो, फ्लाइट बुकिंग और जटिल भूलभलैया नेविगेशन) में 120 कार्यों के साथ एक बड़ा "स्ट्रेस टेस्ट" भी चलाया।

GATS ने अभी भी 100% सफलता हासिल की।
LATS गिरकर 88.9% पर आ गया।
ReAct गिरकर 23.9% पर पहुँच गया।

यह क्यों काम करता है (सीक्रेट सॉस)

पेपर का सुझाव है कि GATS इसलिए जीतता है क्योंकि यह रैंडम अनुमान लगाने के बजाय एक व्यवस्थित खोज (जिसे UCB1 कहा जाता है) का उपयोग करता है। कल्पना कीजिए कि एक जासूस हर सुराग को व्यवस्थित रूप से जाँचता है बजाय इसके कि वह केवल एक अंतर्ज्ञान (hunch) का पीछा करे।

व्यवस्थित बनाम रैंडम: LATS इस पर निर्भर करता है कि LLM यह अनुमान लगाए कि कौन सा रास्ता अच्छा लग रहा है। यदि LLM का "अंतर्ज्ञान" गलत होता है, तो पूरी योजना विफल हो जाती है। GATS सभी विकल्पों को व्यवस्थित रूप से जाँचता है, यह सुनिश्चित करता है कि वह सही रास्ता न चूक जाए क्योंकि गाइड का दिन खराब था।
डिटरमिनिस्टिक बनाम स्टोकेस्टिक: क्योंकि GATS अधिकांश चरणों के लिए अपने स्वयं के मानचित्र का उपयोग करता है, परिणाम हमेशा एक जैसा होता है। LATS, LLM पर निर्भर रहकर, आपको एक अलग उत्तर दे सकता है यदि आप एक ही कार्य को दो बार चलाते हैं।

इसका क्या अर्थ है (और क्या नहीं)

लेखक उनकी सफलता की सीमाओं के बारे में बहुत स्पष्ट हैं। ये परिणाम सिमुलेशन और सिंथेटिक टास्क पर आधारित हैं जहाँ खेल के नियम (एक्शन स्पेसिफिकेशन) पहले से ज्ञात थे। इन नियंत्रित वातावरणों में, GATS एक चैंपियन है।

हालाँकि, पेपर स्पष्ट रूप से इस विचार को खारिज करता है कि GATS अभी हर चीज़ के लिए एक जादुई समाधान है। यदि आप GATS को एक पूरी तरह से जंगली, खुले संसार में डाल देते जहाँ इसके पास कोई नियम या सीखने के लिए पिछले लॉग नहीं हैं, तो इसे LLM पर अधिक निर्भर होना पड़ेगा (लेयर 3), जिससे यह धीमा और कम कुशल हो जाएगा। लेखक सुझाव देते हैं कि वास्तविक दुनिया में GATS को चमकने के लिए, हमें पहले बेहतर मानचित्र (वर्ल्ड मॉडल्स) बनाने होंगे, शायद इंसानों द्वारा टूल्स के उपयोग के लॉग से सीखकर।

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

तकनीकी सारांश: GATS (लेयर्ड वर्ल्ड मॉडल्स के साथ ग्राफ-ऑगमेंटेड ट्री सर्च)

समस्या विवरण

लार्ज लैंग्वेज मॉडल (LLM) एजेंटों ने मल्टी-स्टेप प्लानिंग और टूल उपयोग में क्षमता प्रदर्शित की है, फिर भी वर्तमान दृष्टिकोण जैसे ReAct और LATS (लैंग्वेज एजेंट ट्री सर्च) दो महत्वपूर्ण सीमाओं का सामना करते हैं:

कंप्यूटेशनल लागत: मौजूदा तरीके प्रत्येक प्लानिंग स्टेप या सर्च नोड पर महंगी LLM इन्फरेंस (inference) पर निर्भर करते हैं, जिससे उच्च लेटेंसी और संसाधन खपत होती है।
स्टोकेस्टिसिटी (Stochasticity): LLM सैंपलिंग वेरिएंस (variance) पेश करती है, जिसके परिणामस्वरूप गैर-पुनरुत्पादनीय (non-reproducible) योजनाएं बनती हैं और विभिन्न रन के बीच प्रदर्शन में विसंगति आती है।

मुख्य चुनौती एक ऐसा प्लानिंग फ्रेमवर्क विकसित करना है जो LLM की तर्क क्षमताओं को बनाए रखते हुए, स्टेट प्रेडिक्शन के लिए इन्फरेंस-टाइम LLM कॉल्स को समाप्त कर सके, जिससे एक नियत (deterministic), कुशल और स्केलेबल एजेंट प्लानिंग प्राप्त की जा सके।

कार्यप्रणाली: GATS फ्रेमवर्क

लेखक GATS (Graph-Augmented Tree Search) प्रस्तावित करते हैं, जो एक प्लानिंग आर्किटेक्चर है जो वर्ल्ड मॉडल को LLM से अलग करता है। GATS एक व्यवस्थित UCB1-आधारित ट्री सर्च को एक लेयर्ड वर्ल्ड मॉडल (Layered World Model) और एक निरंतर स्टेट-ट्रांज़िशन ग्राफ (State-Transition Graph) के साथ जोड़ता है।

1. लेयर्ड वर्ल्ड मॉडल ( $W$ )

वर्ल्ड मॉडल वर्तमान स्टेट ( $s$ ) और एक्शन ( $a$ ) दिए जाने पर अगला स्टेट ( $s'$ ) और कॉन्फिडेंस ( $p$ ) की भविष्यवाणी करता है। यह बढ़ती हुई व्यापकता और कंप्यूटेशनल लागत के क्रम में तीन परतों (layers) को क्वेरी करता है:

L1 (सिंबोलिक): उन एक्शन्स के लिए सटीक प्रीकंडिशन-इफेक्ट मैचिंग जिनके ज्ञात STRIPS-शैली के स्पेसिफिकेशन हैं। यह लेयर न्यूनतम कंप्यूटेशनल लागत (सिंबोलिक लुकअप) के साथ नियत भविष्यवाणियां ( $p=1.0$ ) प्रदान करती है।
L2 (लर्नड स्टैटिस्टिक्स): निष्पादन लॉग्स (execution logs) से प्राप्त सांख्यिकीय भविष्यवाणियां। उन एक्शन्स के लिए जो निष्पादन के दौरान देखे गए हैं लेकिन जिनमें औपचारिक स्पेसिफिकेशन की कमी है, यह सबसे अधिक बार होने वाले प्रभाव को $p = \min(\text{count}(a)/10, 1.0)$ कॉन्फिडेंस के साथ लौटाता है।
L3 (जेनेरेटिव/LLM): वास्तव में नवीन या अस्पष्ट एक्शन्स के लिए LLM-आधारित भविष्यवाणी। महत्वपूर्ण रूप से, L3 से प्राप्त भविष्यवाणियों को कैश (cache) किया जाता है ताकि समान ट्रांज़िशन के लिए बार-बार इन्फरेंस कॉल्स से बचा जा सके।

सिस्टम कवरेज को अधिकतम करने के लिए L1 और L2 को प्राथमिकता देता है, और L3 को केवल आवश्यकता होने पर ही बुलाता है। यह LLM लागत को "एमोर्टाइज" (amortize) करता है, जिससे यह प्रति-स्टेप इन्फरेंस आवश्यकता से बदलकर एक वन-टाइम बूटस्ट्रैपिंग लागत बन जाती है।

2. पर्सिस्टेंट स्टेट-ट्रांज़िशन ग्राफ

स्वतंत्र रूप से नोड्स को विस्तारित करने वाले पारंपरिक ट्री सर्च के विपरीत, GATS एक स्पष्ट ग्राफ $G = (V, E)$ बनाए रखता है जहाँ नोड्स कैनोनिकल स्टेट कीज़ $k(s)$ का प्रतिनिधित्व करते हैं।

स्टेट मर्जिंग: यदि विभिन्न एक्शन सीक्वेंस एक ही स्टेट तक पहुँचते हैं, तो वे एक एकल नोड में मर्ज हो जाते हैं। यह पथों के बीच ट्रांज़िशन प्रेडिक्शंस, विजिट काउंट्स और वैल्यू एस्टीमेट्स के पुन: उपयोग की अनुमति देता है।
पर्सिस्टेंस (Persistence): ग्राफ प्लानिंग स्टेप्स के दौरान बना रहता है। एक एक्शन निष्पादित होने के बाद, प्लानिंग ग्राफ नोड से पुनः शुरू होती है न कि सर्च को फिर से शुरू करके, जिससे पूरे एपिसोड पर वैल्यू एस्टीमेशन और सर्च स्टैटिस्टिक्स का लाभ मिलता है।
डेड-एंड डिटेक्शन: जिन नोड्स का लक्ष्य तक कोई पथ नहीं है, उन्हें डेड एंड के रूप में चिह्नित किया जाता है, जिससे प्लानर को उन क्षेत्रों में जाने वाले एक्शन्स को कम वैल्यू देने की अनुमति मिलती है।

3. UCB1-आधारित सर्च

GATS ग्राफ एडजेस (edges) पर एक UCB1 (Upper Confidence Bound) सिलेक्शन स्ट्रैटेजी का उपयोग करता है।

एक्शन सिलेक्शन: प्रत्येक स्टेट पर, एल्गोरिदम उस एक्शन $a$ को चुनता है जो $Q(s, a) + c\sqrt{\frac{2 \ln N(s)}{N(s, a)}}$ को मैक्सिमाइज करता है। यह सुनिश्चित करता है कि उच्च-मूल्य वाले पथों के लिए प्रतिबद्ध होने से पहले सभी लागू एक्शन्स का व्यवस्थित अन्वेषण (exploration) किया जाए।
वैल्यू एस्टीमेशन: स्टेट की वैल्यू BFS-आधारित ह्यूरिस्टिक का उपयोग करके लक्ष्य तक की सबसे छोटी अनुमानित दूरी ( $d_G$ ) से प्राप्त की जाती है: $StateValue(s) = \frac{\alpha}{d_G(s, G) + 1}$ ।
कॉन्फिडेंस इंटीग्रेशन: बैकअप वैल्यू वर्ल्ड मॉडल के कॉन्फिडेंस को शामिल करती है: $v = p \cdot StateValue(s') - \lambda(1-p)$ , जो अनिश्चित भविष्यवाणियों को दंडित करती है।

मुख्य योगदान

लेयर्ड वर्ल्ड मॉडल आर्किटेक्चर: एक नवीन एकीकरण जो कुशल स्टेट प्रेडिक्शन को सक्षम बनाता है और LLM निर्भरता को कम करता है।
ग्राफ मेमोरी के साथ व्यवस्थित UCB1 सर्च: एक प्लानिंग एल्गोरिदम जो सर्च एविडेंस को पुन: उपयोग करने और नियत परिणाम सुनिश्चित करने के लिए एक निरंतर ग्राफ का लाभ उठाकर रैंडम LLM-गाइडेड एक्सप्लोरेशन से बेहतर प्रदर्शन करता है।
व्यापक मूल्यांकन: कोडिंग, वेब नेविगेशन और लॉन्ग-होरिज़न परिदृश्यों को कवर करने वाले 100 सिंथेटिक प्लानिंग टास्क और एक 12-श्रेणी के स्ट्रेस टेस्ट (120 टास्क) पर विस्तृत परीक्षण।
प्लानिंग के दौरान शून्य LLM कॉल्स: प्रदर्शित किया गया कि GATS प्लानिंग चरण के दौरान शून्य LLM कॉल्स के साथ 100% सफलता दर प्राप्त कर सकता है, जो कि दर्जनों कॉल्स की आवश्यकता वाले बेसलाइन्स के बिल्कुल विपरीत है।

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

सिंथेटिक प्लानिंग टास्क (100 टास्क)

सफलता दर: GATS ने 100% सफलता प्राप्त की (बजट $b=10$ के साथ), जो LATS (92%) और ReAct (64%) से बेहतर है।
दक्षता: GATS को प्रति टास्क 0 LLM कॉल्स की आवश्यकता थी, जबकि LATS को ~37 कॉल्स की आवश्यकता थी।
नियतता (Determinism): GATS ने रैंडम सीड्स केAcross 0% वेरिएंस के साथ प्लान तैयार किए, जबकि LIMS और ReAct ने LLM स्टोकेस्टिसिटी के कारण 1-5% वेरिएंस दिखाया।
इष्टतमता (Optimality): GATS ने 1.00 का ऑप्टिमलिटी रेशियो प्राप्त किया, जो ऑरेकल (Oracle) के बराबर है।

स्ट्रेस टेस्ट (12 श्रेणियाँ, 120 टास्क)

स्ट्रेस टेस्ट में कोडिंग वर्कफ़्लो, वेब नेविगेशन, डीप होराइजन टास्क और अपरिवर्तनीय निर्णय लेने (डेड-एंड्स) जैसे चुनौतीपूर्ण परिदृश्य शामिल थे।

कुल प्रदर्शन: GATS ने सभी श्रेणियों में 100% सफलता बनाए रखी।
तुलनात्मक प्रदर्शन: LATS का समग्र प्रदर्शन गिरकर 88.9% हो गया, जिसमें कोडिंग (63.3%), वेब नेविगेशन (63.3%) और डीप होराइजन (63.3%) कार्यों में महत्वपूर्ण संघर्ष देखा गया। ReAct 23.9% पर विफल रहा।
विशिष्ट लाभ: GATS ने LATS की तुलना में कोडिंग, वेब नेविगेशन और डीप होराइजन कार्यों में सबसे अधिक सुधार (+36.7%) दिखाया।

एब्लेशन स्टडीज (Ablation Studies)

सर्च बजट: प्रदर्शन $b=10$ के बजट पर संतृप्त (saturated) हो गया; इसे और बढ़ाने से घटते रिटर्न मिले।
वर्ल्ड मॉडल लेयर्स: सिंथेटिक टास्क पर L1 या L3 को अलग-अलग हटाने से सफलता दर पर प्रभाव नहीं पड़ा, जहाँ L2 ने पर्याप्त कवरेज प्रदान किया, जो सिस्टम के सुचारू क्षरण (graceful degradation) की पुष्टि करता है। ओपन-डोमेन प्रोजेक्शन में, L3 (LLM) से नवीन एक्शन्स को संभालने की उम्मीद है।

महत्व और दावे

पेपर यह तर्क देता है कि लर्नड वर्ल्ड मॉडल्स के साथ व्यवस्थित सर्च, LLM-गाइडेड एक्सप्लोरेशन की तुलना में काफी बेहतर प्रदर्शन कर सकता है। GATS की प्राथमिक महत्ता इसकी क्षमता में निहित है:

इन्फरेंस-टाइम LLM लागत को समाप्त करना: भविष्यवाणियों को कैश करके और सिंबोलिक/लर्नड लेयर्स पर भरोसा करके, GATS बार-बार LLM कॉल्स की कंप्यूटेशनल बाधा को हटा देता है।
पुनरुत्पादनीयता सुनिश्चित करना: लेयर्ड वर्ल्ड मॉडल और UCB1 सर्च की नियत प्रकृति LLM सैंपलिंग से जुड़ी स्टोकेस्टिक वेरिएंस को समाप्त करती है।
जटिल प्लानिंग को संभालना: फ्रेमवर्क उन ब्रांचिंग पाथ्स, डेड-एंड्स और लॉन्ग-होरिज़न डिपेंडेंसीज़ को सफलतापूर्वक नेविगेट करता है जहाँ शुद्ध रूप से LLM-आधारित तरीके (ReAct) और LLM-हैवी ट्री सर्च (LATS) विफल या कम प्रदर्शन करते हैं।

लेखक GATS को उन डोमेन के लिए एक अनुकूलित समाधान के रूप में प्रस्तुत करते हैं जहाँ एक्शन सेमेंटिक्स को औपचारिक रूप दिया जा सकता है (जैसे, API, स्ट्रक्चर्ड टूल उपयोग), जो अधिक कुशल और विश्वसनीय स्वायत्त एजेंटों की ओर एक मार्ग प्रदान करता है। वे स्वीकार करते हैं कि अज्ञात एक्शन प्रभावों वाले ओपन-एंडेड डोमेन में, L3 लेयर पर निर्भरता बढ़ जाएगी, जिससे दक्षता का लाभ कम होगा लेकिन पूरी तरह समाप्त नहीं होगा।