LATS: Language Agent Tree Search — uvažovanie, konanie a plánovanie v jednom rámci

Premýšľal som nad tým, čo príde po Tree of Thoughts – ak dokážete vyhľadávať v krokoch uvažovania, prečo nevyhľadávať aj v akciách? Presne to robí LATS (Language Agent Tree Search) a práve preto ho teraz študujem. Článok od Andyho Zhoua, Kaia Yana, Michala Shlapentokh-Rothmana, Haohana Wanga a Yu-Xionga Wanga (ICML 2024, arXiv:2310.04406) predstavuje doteraz najjasnejšiu syntézu uvažovania, konania a plánovania v rámci jedného agenta a výsledky sú skutočne ťažko spochybniteľné.

O článku

Hlavným problémom, ktorý LATS rieši, je štrukturálna medzera v predchádzajúcej práci s agentmi. ReAct strieda uvažovanie a konanie, ale nemá mechanizmus na návrat a vyskúšanie inej cesty, keď sa trajektória vyvíja nesprávne. Tree of Thoughts umožňuje vetvenie v krokoch uvažovania, ale pracuje s internými znalosťami jazykového modelu (LM) – nedokáže volať nástroje ani prijímať externú spätnú väzbu v rámci vyhľadávania. Reflexion pridáva verbálnu sebaopravu, ale jeho lineárna slučka opakovaných pokusov znamená, že sa zaviaže k novej trajektórii bez skúmania alternatív. LATS spája všetky tri nápady s poriadnym jadrom Monte Carlo Tree Search (MCTS), čo umožňuje LLM agentom skúmať viacero vetiev, prijímať reálnu spätnú väzbu z prostredia a vrátiť sa späť, keď cesta zlyhá.

Technické fungovanie zabezpečuje šesťkroková slučka MCTS: Výber (výber ďalšieho uzla na prieskum pomocou vzorca UCT), Expanzia (vzorkovanie n kandidátskych akcií z LM), Hodnotenie (bodovanie každého uzla pomocou hybridnej hodnotovej funkcie), Simulácia (prechod do koncového stavu), Spätná propagácia (aktualizácia hodnôt predkov) a Reflexia (pri zlyhaní generovanie verbálneho zhrnutia toho, čo sa stalo zle, a jeho uloženie ako kontext). Hodnotová funkcia si zaslúži pozornosť: V(s) = λ·LM(s) + (1−λ)·SC(s), kde LM(s) je vlastný odhad LM o kvalite trajektórie po prijatí spätnej väzby z prostredia a SC(s) je skóre sebakonzistentnosti založené na tom, ako často je daná akcia vzorkovaná medzi súrodeneckými uzlami. Nejde o trénovaný model odmien – hodnotová funkcia je plne riadená promptom.

Kľúčové myšlienky

• V HumanEval dosahuje GPT-4 + LATS 92,7 % pass@1 v porovnaní s 91,0 % pre GPT-4 + Reflexion a 56,9 % pre samotný GPT-3.5 + ReAct. GPT-3.5 + LATS vyskočí na 83,8 %.
• V HotPotQA dosahuje LATS (CoT + ReAct) presnú zhodu 0,71 oproti 0,32 pre základný ReAct – čo je viac ako zdvojnásobenie presnosti pri viacúrovňovom uvažovaní.
• V WebShop (webová navigácia + nakupovanie) skóruje LATS 75,9 (miera úspešnosti 38,0 %) oproti Reflexion so 64,2 (35,0 %) – čo je významný rozdiel pri úlohe, ktorá si vyžaduje správu stavu naprieč mnohými stránkami.
• V Game of 24 (čisto logická hádanka) dosahuje LATS mieru úspešnosti 0,44 oproti 0,20 pri ToT, napriek použitiu rovnakého jadra GPT-4.
• Prekvapivo, LATS expanduje menej uzlov na nájdenie riešenia ako ToT (priemerne 66,65 vs 84,05 uzlov v HotPotQA pri k=50) a spotrebuje menej tokenov (173 290 vs 210 215), hoci sa teoreticky zdá byť nákladnejší.

Čo obstojí — a čo nie

Čísla v benchmarkoch sú skutočné a rámec je koncepčne čistý. Formulácia UCT poskytuje principiálny kompromis medzi prieskumom a využitím (exploration-exploitation), ktorý ad-hoc metódam BFS/DFS v ToT chýba. Integrácia externej spätnej väzby z prostredia do hodnotovej funkcie – namiesto čistej introspekcie LM – je správnym krokom a výsledky to potvrdzujú.

To znamená, že v článku je skrytý kritický predpoklad, ktorý autori priznávajú, ale plne neotestujú: LATS vyžaduje schopnosť vrátiť prostredie do skoršieho stavu. Bez možnosti ukladania bodov obnovy (checkpointing) nemôžete vetviť strom – akonáhle sa vykoná akcia, ste jej viazaní. Autori poznamenávajú, že pre úlohy LM je to často riešiteľné „kopírovaním historického textového vstupu“, ale pre prostredia so skutočnými akciami (databázy, súborové systémy, API s vedľajšími účinkami) je to tvrdá požiadavka, ktorú mnohé produkčné systémy nedokážu splniť. Výsledky WebShopu, hoci sú lepšie ako východiskové hodnoty, ukazujú, že v zložitých prostrediach majú sebareflexie tendenciu stať sa generickými namiesto cielenejších – agenti môžu uviaznuť pri opakovaní povrchne odlišných, ale štrukturálne identických chýb. Článok to spomína, ale neponúka riešenie.

Chýba tiež ablácia izolujúca prínos štruktúry MCTS oproti návrhu hodnotovej funkcie. Je pravdepodobné, že jednoduchší prístup k vetveniu s rovnakou hybridnou hodnotovou funkciou by výrazne znížil tento rozdiel, čo však autori priamo netestujú.

Prečo je to dôležité pre AI vo financiách

Účtovné knihy Beancount sú takmer ideálnym prostredím pre vyhľadávanie v strome v štýle LATS z jedného hlavného dôvodu: každá účtovná kniha je spravovaná v git repozitári. Vrátenie stavu – tvrdá požiadavka, ktorá robí LATS nepraktickým v mnohých reálnych scenároch – je triviálne splnené pomocou git checkout alebo git stash. Agent so spätným zápisom by mohol navrhovať kandidátske účtovné zápisy vo viacerých vetvách, vyhodnocovať ich voči obmedzeniam súvahy (hodnotová funkcia) a potvrdiť (commit) len cestu s najvyšším skóre. Zlyhané vetvy dostanú verbálnu reflexiu: „vložený zápis porušil invariant aktíva = pasíva + vlastné imanie, pretože typ účtu bol nesprávne klasifikovaný.“

Dizajn hybridnej hodnotovej funkcie je tiež priamo aplikovateľný. Pre agenta účtovnej knihy by LM(s) bodovalo navrhovaný zápis na základe sémantickej zhody (vyzerá to ako správna kategória?), zatiaľ čo SC(s) by sledovalo, ako konzistentne agent klasifikuje podobné minulé transakcie – prirodzená kontrola sebakonzistentnosti zakorenená v histórii samotnej účtovnej knihy.

Predpoklad o vrátení stavu je jediným bodom, kde by som pri finančnej analógii oponoval. Skutočné účtovné knihy majú často následné efekty: zaúčtovaný zápis spustí faktúru, ktorá spustí platobný proces. V týchto prípadoch predpoklad LATS zlyháva. Špeciálne pre Beancount, kde je účtovná kniha plain-text súborom pod kontrolou gitu a zmeny sú lokálne pred akýmkoľvek následným spúšťačom, tento predpoklad platí – ale je to dizajnové obmedzenie, ktoré stojí za to ponechať explicitné.

Čo si prečítať ďalej

• Plánovanie založené na MCTS bez modelov prostredia: „Reasoning with Language Model is Planning with World Model“ (Hao et al., 2023, arXiv:2305.14992) – RAP, na ktorom LATS priamo stavia a prekonáva ho.
• Ako dobre zovšeobecňuje hodnotová funkcia LM? „Let's Verify Step by Step“ (Lightman et al., 2023, arXiv:2305.20050) – procesné modely odmien ako alternatíva k hodnotovým funkciám založeným na promptoch.
• Bezpečné viacstupňové plánovanie pri nezvratnosti: „Decision-Making with Language Models via Successive Prompting“ (Creswell et al., 2023) – jednoduchší prístup k plánovaniu, ktorý sa vyhýba požiadavke na vrátenie stavu.