LATS: Language Agent Tree Search — Міркування, Дія та Планування в Єдиній Системі

Я міркував над тим, що прийде після Tree of Thoughts — якщо можна здійснювати пошук серед кроків міркування, то чому б не шукати також і серед дій? Саме це робить LATS (Language Agent Tree Search), і саме тому я зараз його вивчаю. Стаття Енді Чжоу, Кая Яня, Міхала Шлапентох-Ротмана, Хаохана Ванга та Ю-Сюна Ванга (ICML 2024, arXiv:2310.04406) є найбільш чітким синтезом міркування, дії та планування в єдиній структурі агента, і її результати справді важко ігнорувати.

Стаття

Основна проблема, яку вирішує LATS, — це структурна прогалина в попередніх роботах над агентами. ReAct чергує міркування та дії, але не має механізму повернення назад і спроби іншого шляху, коли траєкторія йде не так. Tree of Thoughts дозволяє розгалуження над кроками міркування, але оперує внутрішніми знаннями мовної моделі (LM) — вона не може викликати інструменти або отримувати зовнішній зворотний зв'язок всередині пошуку. Reflexion додає вербальну самокорекцію, але її лінійний цикл повторних спроб означає, що вона фіксується на новій траєкторії без вивчення альтернатив. LATS об'єднує всі три ідеї з повноцінною основою пошуку по дереву Монте-Карло (MCTS), що дозволяє LLM-агентам досліджувати кілька гілок, отримувати реальний зворотний зв'язок від середовища та повертатися назад, якщо шлях виявляється невдалим.

Технічний механізм являє собою шестиетапний цикл MCTS: Selection (вибір наступного вузла для дослідження за допомогою формули UCT), Expansion (вибірка n варіантів дій з LM), Evaluation (оцінка кожного вузла за допомогою гібридної функції цінності), Simulation (проходження до термінального стану), Backpropagation (оновлення значень предків) та Reflection (у разі невдачі — створення вербального резюме того, що пішло не так, і збереження його як контексту). Функція цінності заслуговує на увагу: V(s) = λ·LM(s) + (1−λ)·SC(s), де LM(s) — це власна оцінка мовною моделлю якості траєкторії після отримання зворотного зв'язку від середовища, а SC(s) — показник самоузгодженості, заснований на тому, як часто ця дія вибирається серед сусідніх вузлів. Це не навчена модель винагороди — функція цінності повністю базується на промптах.

Ключові ідеї

• На HumanEval GPT-4 + LATS досягає 92,7% pass@1 порівняно з 91,0% для GPT-4 + Reflexion та 56,9% для GPT-3.5 + ReAct окремо. GPT-3.5 + LATS стрибає до 83,8%.
• На HotPotQA LATS (CoT + ReAct) досягає 0,71 точного збігу проти 0,32 для базового ReAct — що більше ніж удвічі підвищує точність у багатоходових міркуваннях.
• На WebShop (веб-навігація + покупки) LATS отримує 75,9 бала (рівень успіху 38,0%) проти Reflexion з 64,2 балами (35,0%) — суттєвий розрив у завданні, що вимагає управління станом на багатьох сторінках.
• У Game of 24 (чиста головоломка на міркування) LATS досягає 0,44 рівня успіху проти ToT з 0,20, незважаючи на використання тієї ж основи GPT-4.
• Дивно, але LATS розширює менше вузлів для пошуку рішення, ніж ToT (66,65 проти 84,05 вузлів у середньому на HotPotQA при k=50), і використовує менше токенів (173 290 проти 210 215), хоча теоретично він виглядає дорожчим.

Що працює — а що ні

Показники бенчмарків реальні, а структура концептуально чиста. Формулювання UCT дає принциповий компроміс між дослідженням та експлуатацією, якого бракує спеціальним методам BFS/DFS у ToT. Інтеграція зовнішнього зворотного зв'язку середовища у функцію цінності — замість чистої інтроспекції LM — це правильний крок, і результати це підтверджують.

Тим не менш, у статті закладено критичне припущення, яке автори визнають, але не тестують повністю на стійкість: LATS вимагає можливості повернути середовище до попереднього стану. Без створення контрольних точок ви не можете розгалужувати дерево — як тільки дія виконана, ви на неї підписалися. Автори зазначають, що для завдань LM це часто можна вирішити за допомогою "копіювання-вставки попереднього текстового вводу", але для реальних середовищ дій (бази даних, файлові системи, API з побічними ефектами) це жорстка вимога, яку багато виробничих систем не можуть задовольнити. Результати WebShop, хоч і кращі за базові показники, показують, що в складних середовищах саморефлексії мають тенденцію ставати загальними, а не цілеспрямованими — агенти можуть застрягти, повторюючи зовні різні, але структурно ідентичні помилки. У статті це зазначено, але рішення немає.

Також немає абляційного дослідження, яке б ізолювало внесок структури MCTS порівняно з дизайном функції цінності. Цілком імовірно, що простіший підхід до розгалуження з тією ж гібридною функцією цінності міг би скоротити більшу частину розриву, але автори не тестують це напряму.

Чому це важливо для фінансового ШІ

Beancount-леджери є майже ідеальним середовищем для пошуку по дереву в стилі LATS з однієї ключової причини: кожен леджер підтримується git-репозиторієм. Повернення стану — жорстка вимога, яка робить LATS непрактичним у багатьох реальних сценаріях — тривіально задовольняється за допомогою git checkout або git stash. Агент запису міг би пропонувати варіанти журнальних записів у кількох гілках, оцінювати їх на відповідність обмеженням балансу (функція цінності) та фіксувати лише шлях з найвищим балом. Невдалі гілки отримують вербальну рефлексію: "введений запис порушив інваріант активи = зобов'язання + капітал, оскільки тип рахунку був неправильно класифікований".

Дизайн гібридної функції цінності також безпосередньо застосовний. Для агента леджера LM(s) оцінювала б запропонований запис на основі семантичної відповідності (чи схоже це на правильну категорію?), тоді як SC(s) відстежувала б, наскільки послідовно агент класифікує подібні минулі транзакції — природна перевірка на самоузгодженість, що ґрунтується на власній історії леджера.

Припущення про повернення стану — це єдине місце, де я б посперечався з фінансовою аналогією. Реальні леджери часто мають каскадні ефекти: проведений запис запускає рахунок-фактуру, що запускає процес оплати. У таких випадках припущення LATS не справджується. Конкретно для Beancount, де леджер — це текстовий файл під управлінням git, а зміни є локальними до будь-якого подальшого тригера, це припущення діє — але це обмеження дизайну варто тримати в центрі уваги.

Що читати далі

• Планування на основі MCTS без моделей середовища: "Reasoning with Language Model is Planning with World Model" (Hao et al., 2023, arXiv:2305.14992) — RAP, на якому LATS безпосередньо базується і який перевершує.
• Наскільки добре узагальнюється функція цінності LM? "Let's Verify Step by Step" (Lightman et al., 2023, arXiv:2305.20050) — моделі винагороди за процес як альтернатива функціям цінності на основі промптів.
• Безпечне багатокрокове планування в умовах незворотності: "Decision-Making with Language Models via Successive Prompting" (Creswell et al., 2023) — простіший підхід до планування, який уникає вимоги щодо повернення стану.