Что такое tree search agents (MCTS for LLM) и когда они эффективны?

Краткий тезис

Tree search agents — это подход, в котором LLM-агент использует алгоритм Tree Tree Monte Carlo Tree Search (MCTS) для планирования последовательности действий. MCTS строит дерево возможных ходов, симулирует их исходы с помощью самого LLM (как policy и value network) и выбирает оптимальную траекторию. Метод эффективен в задачах с конечным деревом решений (глубина до 20 шагов), чёткой reward в конце (например, правильный ответ в математике или выигрыш в игре) и дискретным пространством действий. Главный недостаток — экспоненциальный рост вызовов LLM (K^depth), что делает его дорогим.

1. Термин: Tree Search Agents и MCTS

Tree search agents — это класс AI-агентов, которые на каждом шаге рассматривают несколько возможных действий, строят дерево решений и выбирают наилучший путь с помощью поиска. В контексте LLM такой поиск обычно реализуется через Tree Tree Monte Carlo Tree Search (MCTS) — алгоритм, изначально разработанный для игр (AlphaGo, AlphaZero). MCTS балансирует exploration (исследование новых ветвей) и exploitation (углубление в перспективные ветви) с помощью статистической оценки узлов.

В отличие от простого жадного выбора (как в ReAct), MCTS позволяет агенту «заглядывать вперёд», симулируя цепочки действий до терминального состояния, что критично для задач, где локально оптимальный шаг может вести к тупику.

2. Классический MCTS: четыре фазы

Алгоритм MCTS состоит из четырёх повторяющихся фаз:

1. Selection (выбор): начиная от корня, спускаемся по дереву, выбирая на каждом уровне узел с максимальным значением UCB1 (Upper Confidence Bound): [ UCB1 = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}} ] где (w_i) — число побед в узле, (n_i) — число посещений, (N) — общее число посещений родителя, (c) — коэффициент exploration.

2. Expansion (расширение): если достигнут листовой узел, добавляем одного или нескольких потомков (возможные действия).

3. Simulation (симуляция): от нового узла выполняем случайную (или эвристическую) симуляцию до терминального состояния и получаем reward (например, 1 за победу, 0 за поражение).

4. Backpropagation (обратное распространение): обновляем статистику ((w_i, n_i)) для всех узлов на пути от листа до корня.

После достаточного числа итераций выбирается действие с наибольшим числом посещений (или лучшей средней наградой).

3. Адаптация MCTS для LLM: Policy и Value Networks

В классическом MCTS симуляция часто делается случайно. Для LLM-агентов это заменяется на LLM-симуляции:

• Policy network — сам LLM, который генерирует (K) возможных следующих действий (например, варианты ответа, вызовы функций, шаги доказательства). Каждое действие — это текст (промпт + генерация).
• Value network — LLM (или отдельная модель), который оценивает текущее состояние (узел) без полной симуляции: выдаёт число от 0 до 1, предсказывая вероятность успеха. Это ускоряет поиск, заменяя дорогие симуляции.

Процесс для LLM:

• Selection: используем UCB1, где (w_i) — сумма value оценок посещённых состояний (или накопленная reward).
• Expansion: LLM генерирует (K) вариантов действий (промпт: «Предложи следующие шаги»).
• Simulation: либо запускаем LLM до терминального состояния (дорого), либо используем value network для оценки листа.
• Backpropagation: обновляем статистику.

Таким образом, MCTS для LLM — это гибрид поиска и генерации, где LLM выступает и как генератор гипотез, и как оценщик.

4. Когда MCTS эффективен: условия и примеры

MCTS оправдан, когда выполнены следующие условия:

Примеры успешного применения:

• Математика (Lean, Coq): MCTS перебирает возможные тактики доказательства, симулирует их и выбирает ведущие к цели. (DeepMind's AlphaProof)
• Генерация кода: агент выбирает, какую функцию реализовать, какие библиотеки использовать; reward — прохождение тестов.
• Игры (шахматы, Go): классический домен MCTS, но с LLM вместо нейросети.
• Поиск по графу знаний: в agentic RAG MCTS может выбирать, какой документ прочитать или какой запрос выполнить, чтобы собрать информацию для ответа.

5. Ограничения и вычислительная сложность

Главный минус — стоимость. Если на каждом шаге генерируется (K) вариантов, а глубина (D), то в худшем случае требуется (O(K^D)) вызовов LLM. На практике используют pruning (отсечение неперспективных ветвей) и ограничение бюджета итераций.

Другие ограничения:

• Зависимость от качества value network: плохая оценка состояния ведёт к неверному выбору.
• Проблема длинного контекста: при симуляции длинных цепочек контекст может превысить лимит LLM.
• Необходимость чёткого терминального условия: если reward не определён (например, открытые вопросы), MCTS не применим.

6. Сравнение с альтернативными методами

MCTS даёт лучшие результаты в задачах, где ошибочный ранний шаг необратим, но платит за это экспоненциальной стоимостью.

7. MCTS в контексте Agentic RAG

В agentic RAG агент может использовать MCTS для multi-hop retrieval: на каждом шаге он выбирает, какой запрос отправить к векторной БД, какой документ прочитать, какой инструмент вызвать. Reward — наличие ответа в собранном контексте или оценка faithfulness.

Пример: вопрос «Какая столица страны, где родился автор книги "1984"?» Агент строит дерево: сначала ищет автора (Оруэлл), затем страну (Великобритания), затем столицу (Лондон). MCTS позволяет перебирать альтернативные пути (например, если первый запрос не дал результата) и выбирать наиболее надёжный.

8. Практическая реализация: инструменты и подходы

Для реализации MCTS с LLM можно использовать:

• Библиотеки: LangChain (AgentExecutor с кастомным планировщиком), Microsoft's Guidance, или написать свой цикл.
• Промпты: для генерации действий: «Ты — агент. Твоя цель — {goal}. Текущее состояние: {state}. Предложи 3 следующих действия в формате JSON.».
• Value network: можно использовать тот же LLM с промптом «Оцени вероятность успеха от 0 до 1, если продолжить из этого состояния».
• Управление контекстом: хранить историю в списке сообщений, для симуляции создавать копии контекста.

Псевдокод:

class MCTSNode:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.value = 0.0

def mcts(root, llm, iterations=100):
    for _ in range(iterations):
        node = select(root)
        if not node.is_terminal():
            node = expand(node, llm)
        reward = simulate(node, llm)
        backpropagate(node, reward)
    return best_child(root)

9. Пет-проект для закрепления

Задача: Реализовать MCTS-агента для решения простой математической задачи: «Докажите, что сумма двух чётных чисел чётна». Агент должен выбирать шаги доказательства (аксиомы, определения, логические переходы).

Инструменты: Python, OpenAI API (или локальная LLM), библиотека для работы с деревьями (anytree).

Шаги:

1. Определить пространство действий: список возможных тактик (например, «использовать определение чётности», «сложить два числа», «вынести 2 за скобки»).
2. Реализовать класс MCTSNode с полями state (текущее доказательство) и reward (1, если доказательство завершено, иначе 0).
3. Написать функцию expand(node, llm): LLM генерирует 3 следующих шага из текущего состояния.
4. Написать simulate(node, llm): запустить LLM до терминального состояния (до 5 шагов) и вернуть reward.
5. Запустить MCTS на 50 итераций, выбрать лучший путь.
6. Вывести итоговое доказательство.

Ожидаемый результат: Агент находит корректное доказательство (например, «Пусть a=2k, b=2m, тогда a+b=2(k+m) — чётное»). Вы увидите, как MCTS перебирает разные варианты и выбирает правильный.

10. Связь с другими вопросами

MCTS — это один из методов планирования (planning), который можно комбинировать с ReAct (для генерации действий) и Reflexion (для исправления ошибок). В multi-agent системах MCTS может координировать действия нескольких агентов.

Навигация

• Предыдущий: 569
• Следующий: 571
• Индекс: 00. Индекс разборов