Как работает tree search (MCTS) для LLM агентов?

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

Tree Tree Monte Carlo Tree Search (MCTS) — это эвристический алгоритм поиска в дереве решений, который балансирует исследование (exploration) новых ходов и эксплуатацию (exploitation) уже известных хороших ходов. Для LLM-агентов MCTS позволяет строить дерево возможных следующих шагов (действий или мыслей), оценивать их «полезность» через симуляции и выбирать наиболее перспективную траекторию. Ключевые фазы — Selection, Expansion, Simulation и Backpropagation — повторяются N раз (обычно 50–200), чтобы накопить статистику и принять решение.

1. Зачем LLM-агенту дерево поиска?

LLM-агенты часто решают задачи, требующие многошагового планирования:

• математическое доказательство,
• генерация кода]],
• веб-навигация (например, заказ билета через несколько страниц),
• игра с правилами.

Прямая генерация цепочки шагов одним проходом LLM рискованна: ошибка на раннем шаге обрекает весь ответ. Tree search позволяет агенту «думать» о нескольких вариантах, оценивать их, возвращаться назад и выбирать лучший. MCTS — один из самых эффективных методов такого поиска, он хорошо масштабируется на большие пространства состояний и не требует полного перебора.

2. Четыре фазы MCTS

MCTS — итеративный алгоритм. Каждая итерация проходит четыре фазы:

Итерация 1: Selection → Expansion → Simulation → Backpropagation
Итерация 2: Selection → Expansion → Simulation → Backpropagation
...
Повтор N раз → выбор лучшего пути из корня

Рассмотрим каждую фазу подробно.

2.1 Selection (Выбор)

Начинаем от корня дерева (текущее состояние задачи). На каждом уровне выбираем дочерний узел с максимальным значением Confidence Bound|Upper Confidence Bound]] (UCB1):

UCB1 = Q(s, a) + C * sqrt( ln(N(s)) / N(s,a) )

• Q(s,a) — средняя полученная награда (value) для пары состояние-действие.
• N(s) — количество посещений состояния s.
• N(s,a) — количество раз, когда из состояния s было выбрано действие a.
• C — константа, регулирующая exploration (обычно от 0.5 до 2).

Первое слагаемое (Q) способствует exploitation — выбору ходов, которые уже показали высокую награду. Второе слагаемое (exploration bonus) растёт, когда действие a посещалось редко, тем самым алгоритм не застревает в локальном оптимуме.

Selection продолжается, пока не достигнем листа (узла, который ещё не полностью развёрнут или ещё не симулировался).

2.2 Expansion (Расширение)

Когда мы дошли до листа, мы расширяем дерево: генерируем одно или несколько возможных следующих действий. Для LLM-агента это означает вызов большой модели для получения списка кандидатов на следующее действие/мысль.

Например, для математической задачи LLM может предложить три подхода:

• «применить формулу квадрата суммы»,
• «вынести общий множитель»,
• «проверить частный случай».

Каждое действие становится новым дочерним узлом. Их initial values (количество посещений и награда) устанавливаются в 0, после чего алгоритм переходит к симуляции.

2.3 Simulation (Симуляция / Rollout)

От выбранного нового узла выполняется симуляция до терминального состояния (конца эпизода) с помощью некоторой политики. Политика может быть случайной, или, что эффективнее для LLM, используется быстрая (lightweight) модель (например, GPT-2) или даже эвристика. Цель — получить оценку Q для этого узла без полного построения дерева.

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

Результат симуляции — reward (награда), обычно число от 0 до 1.

2.4 Backpropagation (Обратное распространение)

Полученная награда распространяется вверх по пути, пройденному на фазе Selection, обновляя значения викии счётчикии счётчики для каждого узла на пути.

Формула обновления:

N(s,a) += 1
Q(s,a) = (Q(s,a) * (N(s,a)-1) + reward) / N(s,a)

После нескольких итераций статистика в узлах становится более надёжной, и UCB1-значения точнее направляют поиск.

3. Выбор лучшего пути

После N итераций (например, 100) дерево содержит множество посещённых путей. Финальное решение принимается по одному из критериев:

• максимум посещений (most visited child) — robust child;
• максимум средней награды (max Q);
• комбинация.

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

4. Как LLM участвует в каждой фазе?

Таким образом, LLM вызывается только на этапах Expansion и Simulation, что делает MCTS относительно эффективным: основная «тяжёлая» работа — генерация вариантов — ограничена количеством расширенных узлов.

5. Преимущества и недостатки MCTS для LLM-агентов

Преимущества

• Баланс exploration / exploitation — за счёт UCB.
• Не требует полной модели среды – достаточно симулятора (чекер, тесты, быстрая LLM).
• Может работать с огромными пространствами (разные формулировки мыслей).
• Легко распараллеливается – итерации независимы.
• Даёт объяснимость – можно показать, какие варианты рассматривались.

Недостатки

• Затраты по времени – тысячи итераций × вызовы LLM для симуляций.
• Качество симуляции критично – если роллаут-политика слишком слаба, оценка будет шумной.
• Требуется хороший UCB-параметр C – плохая настройка ведёт к перекосу.
• Неприменим, если нет быстрой симуляции (например, для оценки креативного текста).

6. Сравнение с другими методами поиска

Для задач с открытыми ответами (математика, код) MCTS часто превосходит beam search, так как может «откатиться» от тупиковых ветвей.

7. Практический пример: решение математической задачи

Пусть задача: «Решите уравнение x² – 5x + 6 = 0».

1. Корень: «x² – 5x + 6 = 0».
2. Expansion (LLM) предлагает три действия:
   • «Найти дискриминант»
   • «Попробовать разложить на множители»
   • «Угадать корни: 2 и 3»
3. Для каждого действия запускается симуляция (быстрая LLM или чекер). Действие «Угадать корни» даёт reward=1 (проверка подстановкой). Разложение – 0.8 (возможно, неверно). Дискриминант – 0.7 (долго).
4. Backpropagation обновляет узлы.
5. После 50 итераций дерево «Угадать корни» набирает больше посещений → выбирается как ответ.

8. Известные реализации и вариации

• AlphaGo / AlphaZero – классический MCTS с нейронными сетями.
• Tree-of-Thoughts (ToT) – адаптация MCTS для рассуждений LLM: каждый узел – это цепочка мыслей, оценка через LLM-самооценку.
• RAP (Reasoning via Planning) – использует MCTS для генерации цепочек мыслей с обратной связью от среды.
• MCTS для генерации кода – узлы – фрагменты кода, симуляция – запуск на тестах.

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

Задача: Реализовать MCTS для задачи «Сортировка трёх чисел» (или «Решить квадратное уравнение») с LLM-агентом на основе OpenAI API.

Инструменты:

• Python + asyncio для параллельных вызовов,
• API OpenAI (gpt-3.5-turbo) для expansion и симуляции,
• NumPy для UCB1.

Шаги:

1. Определить структуру узла: state, children, visits, value, parent.
2. Реализовать UCB1 (C=1.0).
3. Selection: идти по максимальному UCB1 до листа.
4. Expansion: вызвать LLM с промптом «Предложи 3 следующих шага для состояния X» и создать дочерние узлы.
5. Simulation: из листа вызвать LLM с промптом «Реши задачу до конца одним шагом» и получить reward (0/1).
6. Backpropagation: обновить value и visits на пути.
7. Запустить 30 итераций, вывести лучший путь.

Ожидаемый результат: Агент научится выбирать правильную последовательность шагов (например, «проверить, что числа разные → упорядочить по возрастанию») и избегать тупиков.

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

Навигация

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