Chain-in-Tree: избирательное ветвление в древовидном поиске LLM

Фаза CiT (до ветвления):

ШАГ 1: Генерация кандидатов
→ Модель создаёт k_bn вариантов следующего шага
→ Формат: список действий/sub-вопросов

ШАГ 2: Оценка BN
→ BN-DP: вспомогательная модель оценивает "нужно ли ветвление?" (1-4)
→ BN-SC: кластеризация кандидатов, BN = размер_крупнейшего_кластера / k_bn

ШАГ 3: Решение
→ Если BN ≥ порог (0.5) И confidence ≥ порог → продолжить линейно (chaining)
→ Иначе → ветвление (классический tree search)

Всё это происходит внутри одного tree search запуска, заменяя стандартное "всегда ветвиться" на "ветвиться когда надо".

⚠️ Ограничение метода: CiT оптимизирует алгоритмическую часть tree search, не прямой промпт. Для обычного чата ChatGPT/Claude нужна адаптация принципа — ручная имитация избирательного ветвления.

Задача: Оценить стратегию выхода на рынок для нового онлайн-сервиса по доставке готовой еды в Москве. Нужно пройти через цепочку решений: ценообразование → аудитория → маркетинг → логистика. Где-то очевидный шаг, где-то нужна экспlorация вариантов.

Промпт (имитация CiT вручную):

Задача: Стратегия выхода на рынок для сервиса доставки еды в Москве.

Шаг 1: Начни с ценообразования. Предложи 3 варианта ценовой модели.

[модель выдаёт 3 варианта: эконом/средний/премиум]

Шаг 2: Оцени свою уверенность по шкале 1-4:
- 4 = очевидный следующий шаг, один путь
- 1 = нужна глубокая экспlorация вариантов

[модель: "уверенность 2 — нужно исследовать аудиторию под каждый сегмент"]

→ Ветвление: исследуй отдельно каждую ценовую модель + аудиторию

Шаг 3: Для эконом-сегмента. Какая аудитория? Дай 1 вариант.

[модель: "студенты и молодые специалисты 18-30 лет"]

Шаг 4: Уверенность?

[модель: "4 — очевидно, маркетинг через соцсети"]

→ Линейное продолжение: маркетинг через ВК/Telegram без экспlorации альтернатив

Результат: Модель чередует два режима: линейное продолжение на очевидных участках ("студенты → соцсети") и ветвление где нужна экспlorация ("три ценовых модели → три стратегии"). Экономия токенов на тривиальных шагах, глубина исследования на развилках.

Слабость LLM: Модели плохо различают тривиальные и сложные шаги внутри алгоритма. Tree search по умолчанию ветвится везде — даже там, где ответ "3+4=7" очевиден. Это фиксированная гранулярность — один шаг = одна операция, без учёта сложности.

Сильная сторона LLM: Модели отлично оценивают семантическую эквивалентность текста. Если сгенерировать 5 вариантов следующего шага и все они по сути одинаковы ("сначала найди сумму", "сложи числа", "вычисли 3+4") — значит модель уверена, один путь доминирует. Если варианты разные — модель в замешательстве, нужна экспlorация.

Как CiT использует это: Вместо слепого ветвления на каждом шаге, CiT спрашивает модель саму: "нужно ли здесь исследование?" Через BN-DP (прямая оценка) или BN-SC (кластеризация кандидатов). Если уверена → chaining (линейно вперёд, 1 вызов модели). Если не уверена → branching (классическое ветвление, k вызовов). Экономия токенов на очевидных шагах, полная мощность tree search на развилках.

Метафора: Это как опытный шахматист, который не анализирует 10 вариантов после каждого хода. В дебюте (известные паттерны) он играет быстро по теории. Но в миттельшпиле (неясная позиция) он замедляется и считает варианты. CiT учит LLM тому же — не форсировать анализ там, где один путь очевиден.

⚠️ Важно: CiT — это модификация алгоритма tree search (ToT, MCTS), не standalone промпт. Ниже — шаблон для ручной имитации принципа в обычном чате.

Задача: {описание_задачи}

Инструкция: Ты будешь решать задачу пошагово. На каждом шаге:

1. Предложи следующее действие
2. Оцени свою уверенность по шкале 1-4:
 - 4 = Очевидный единственный путь, можно идти дальше
 - 3 = Вероятно правильно, но есть нюансы
 - 2 = Нужно рассмотреть 2-3 варианта
 - 1 = Критическая развилка, нужна глубокая экспlorация

3. Действуй в зависимости от уверенности:
 - Уверенность 4: сделай шаг и продолжи линейно
 - Уверенность 3: сделай шаг, но объясни почему именно так
 - Уверенность 2-1: предложи {k_вариантов} альтернатив и исследуй каждую

Начни с шага 1.

Плейсхолдеры:

• {описание_задачи} — конкретная задача (планирование, математика, стратегия)
• {k_вариантов} — сколько альтернатив исследовать на развилках (2-5)

🚀 Быстрый старт — вставь в чат:

Вот шаблон Chain-in-Tree для избирательного ветвления. Адаптируй под мою задачу: [твоя задача]. 
Задавай вопросы, чтобы заполнить поля.

[вставить шаблон выше]

LLM спросит про тип задачи (математика/стратегия/планирование), сколько вариантов генерировать на развилках, какой порог уверенности использовать — потому что разные задачи требуют разной глубины исследования. Она возьмёт паттерн из шаблона и адаптирует под конкретную ситуацию.

Исследователи создали BN Evaluator — компонент который решает, нужно ли ветвление. Два варианта: Direct Prompting (прямая оценка) и Self-Consistency (кластеризация). Ниже — промпт для BN-DP из оригинала.

**System message:**

You are an expert at deciding whether a single reasoning step is *logically compulsory* given the task and the partial solution path.

Input fields:
(A) Task description - one paragraph.
(B) Partial reasoning path so far.
(C) Candidate next step.

ONLY output a single number from 1 to 4.

Scale:
4 - **Unavoidable next step**: given the current path, this step must come next to proceed logically.
3 - Strongly expected: skipping it now would be very unusual, though not impossible.
2 - Potentially useful but avoidable: alternative coherent next steps exist.
1 - **Optional**: the step is not logically required at this point.

Think silently, then output the single line - nothing else.

**User message:**

(A) (task)
(B) (partial path)
(C) (candidate step)

💡 Адаптация для стратегических решений:

Принцип CiT можно применить к бизнес-стратегии или карьерным решениям — где некоторые шаги очевидны (собрать данные, сделать расчёт), а другие требуют экспlorации вариантов (выбор стратегии, оценка рисков).

Задача: Принять решение о смене карьеры с разработчика на продакт-менеджера.

Инструкция: Иди пошагово. На каждом шаге:
- Если действие очевидно (например, "изучи требования к PM") → сделай и продолжи
- Если развилка (например, "выбор между стартапом и корпорацией") → предложи 3 варианта, исследуй каждый

Шаг 1: {начни с оценки текущих навыков}

Эффект: Модель не тратит токены на очевидные вещи ("нужен нетворкинг", "изучи вакансии"), но ветвится на ключевых выборах ("стартап vs корпорация", "фронтенд vs бэкенд продукты"). Линейное продолжение где уверена, экспlorация где нужна.

🔧 Техника: Self-Consistency как индикатор уверенности

Если вместо BN evaluator кластеризовать ответы вручную:

Задача: {твоя_задача}
Текущий контекст: {что_уже_сделано}

Предложи 5 вариантов следующего шага. Для каждого — одно предложение.

---

Теперь сгруппируй их: какие варианты по сути одинаковы?

Если 4 из 5 в одной группе → ты уверен, выбери этот вариант и продолжи.
Если 2-3 группы примерно равны → ты не уверен, исследуй каждую группу отдельно.

Эффект: Ручная имитация BN-SC. Модель сама оценивает консистентность своих вариантов. Высокая консистентность = уверенность = линейное продолжение. Низкая = развилка = ветвление.

⚠️ Требует модификации алгоритма: CiT не работает "из коробки" в ChatGPT/Claude. Это плагин для tree search фреймворков (ToT, MCTS), требует доступа к внутренним механизмам поиска.

⚠️ BN-SC нестабилен в некоторых случаях: В 4 из 14 тестовых настроек BN-SC генерирует больше вызовов чем baseline из-за отдельных примеров с экстремально длинными цепочками рассуждений. BN-DP стабилен везде.

⚠️ Качество BN evaluator критично: Когда слабая модель (LLaMA-8B) оценивает необходимость ветвления, точность падает ниже baseline, иногда до уровня простого CoT. Сильная модель (Qwen-32B) восстанавливает качество. Плохой BN evaluator = плохой результат.

⚠️ Узкий домен тестирования: Метод проверен только на математических задачах (GSM8K, Math500). В доменах с детерминированным action space (шахматы, навигация) может не понадобиться LLM для BN — достаточно rule-based проверки.

Команда проверила CiT на 14 конфигурациях: два бенчмарка (GSM8K, Math500), три базовых метода tree search (ToT-BS, ReST-MCTS, RAP), и две модели в роли policy/BN evaluator (Qwen3-32B, LLaMA3-8B). Ключевая идея: сравнить CiT-версии методов с оригинальными по количеству токенов, вызовов модели, времени и точности.

Дизайн эксперимента простой: взяли первые 100 примеров из каждого датасета, прогнали через baseline tree search (без CiT) и через три варианта CiT (BN-DP, BN-SC[1], BN-SC[2]). Измерили сколько раз вызывали policy, сколько токенов сгенерировали, сколько времени ушло — отдельно для policy и для всех LLM-ролей (policy + reward + transition + BN evaluator).

Главный вывод: BN-DP сокращает runtime на 75–85% почти везде, без потери точности. BN-SC эффективен в 10 из 14 случаев, но проваливается в 4 настройках из-за отдельных "проблемных" примеров — на этих примерах CiT генерирует экстремально длинные цепочки вместо ветвления, что убивает эффективность.

Почему так происходит? Анализ на уровне отдельных примеров показал: в провальных настройках BN-SC эффективнее baseline на 73–83% примеров, но 5–10% примеров генерируют настолько длинные цепочки (сотни шагов), что съедают всю экономию. Это нестабильность алгоритма — не системная проблема, а хвостовой риск на отдельных кейсах.

Второй инсайт: качество BN evaluator решает всё. Когда слабая модель (LLaMA-8B) оценивает необходимость ветвления, точность падает ниже baseline — иногда до уровня простого CoT. Модель переоценивает уверенность, форсирует chaining там где нужно ветвление, ошибки накапливаются. Когда сильная модель (Qwen-32B) берёт роль BN evaluator, точность восстанавливается до уровня baseline или выше. Вывод: BN evaluation — не просто вспомогательная роль, это критический компонент, который определяет успех метода.

Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search

Xinzhe Li (Independent Researcher)

GitHub: github.com/xinzhel/chain_in_tree

Связанные работы:

• Tree of Thoughts (Yao et al., 2023)
• ReST-MCTS (Zhang et al., 2024)
• RAP: Reasoning with Language Model is Planning with World Model (Hao et al., 2023)