Tree of Thoughts (ToT)

Tree of Thoughts (ToT) — это подход к инжинирингу промптов, при котором большая языковая модель (LLM) решает задачу, исследуя дерево частичных решений. На каждом шаге модель предлагает несколько вариантов следующего шага, называемых мыслями, оценивает перспективность каждого полученного состояния, а алгоритм поиска решает, какие ветви развивать, сохранять или отбрасывать. В отличие от промптинга с цепочкой рассуждений, который с первого токена следует одной линии рассуждений, ToT позволяет заглядывать вперёд и возвращаться к предыдущим шагам. Шуньюй Яо и коллеги из Принстонского университета и Google DeepMind представили этот метод в работе «Дерево мыслей: осознанное решение задач с помощью больших языковых моделей», опубликованной на NeurIPS 2023. В том же месяце Цзеъи Лун предложил похожую систему поиска по дереву для решения судоку с помощью LLM. В головоломке Game of 24 ToT повысил долю успешных решений GPT-4 с 4% при промптинге с цепочкой рассуждений до 74%.

Как работает Tree of Thoughts#

Яо и соавторы описывают ToT через четыре проектных решения:

• Декомпозиция мыслей: Что представляет собой один шаг. В Game of 24 мысль — это одно уравнение; в генерации текста — план текста; в кроссворде — слово для заполнения.
• Генератор мыслей: Как формируются варианты. Модель либо независимо генерирует несколько мыслей, что подходит для открытых задач, либо предлагает список разных вариантов в одном промпте, чтобы избежать повторов, когда выбор ограничен.
• Оценщик состояний: Как оценивается прогресс. Модель отдельно оценивает каждое состояние, например как «вероятное», «возможно» или «невозможное» для достижения цели, либо голосует за лучший из нескольких вариантов. Эти оценки служат эвристикой поиска, аналогом функции оценки, написанной вручную для классического поиска.
• Алгоритм поиска: Как исследуется дерево. Поиск в ширину сохраняет b лучших состояний на каждом уровне, а поиск в глубину следует по самой перспективной ветви, отсекает состояния, исключённые оценщиком, и возвращается назад.

Пример: Game of 24#

В Game of 24 нужно объединить четыре числа с помощью операций +, -, x и /, чтобы получить 24, используя каждое число один раз. ToT разбивает решение на три шага, каждый из которых представляет собой уравнение, объединяющее два числа. Для входных чисел 4 9 10 13 промпт с запросом вариантов может предложить, например:

13 - 9 = 4 (left: 4 4 10)
10 - 4 = 6 (left: 6 9 13)
4 + 9 = 13 (left: 10 13 13)
4 x 13 = 52 (left: 9 10 52)

Затем промпт для оценки спрашивает, можно ли получить 24 из каждого оставшегося набора. Для «4 4 10» ответ — «вероятно», поскольку (10 - 4) x 4 = 24. То же относится к «6 9 13», поскольку (13 - 9) x 6 = 24. А варианты «10 13 13» и «9 10 52» невозможны, поэтому поиск продолжает только первые две ветви. Для первой ветви: 10 - 4 = 6 (остаются 4 и 6), затем 4 x 6 = 24.

В экспериментах авторов на 100 сложных задачах поиск в ширину сохранял на каждом шаге 5 лучших состояний и трижды оценивал каждое состояние. ToT с GPT-4 решил 74% задач против 7,3% при прямом промптинге, 4,0% при промптинге с цепочкой рассуждений и 9,0% при использовании цепочки рассуждений с согласованием результатов. Даже лучший результат среди 100 сгенерированных цепочек рассуждений составил только 49%, а ToT, сохранявший одно состояние на каждом шаге, решил 45% задач.

Место Tree of Thoughts среди других методов#

ToT полезен для задач, где ранние решения ограничивают последующие, а ошибку на первом шаге трудно исправить: головоломок, планирования и многошаговой математики. В мини-кроссвордах 5×5 ToT с поиском в глубину и отсечением ветвей правильно заполнил 60% слов и решил 4 из 20 головоломок. Недостаток — вычислительные затраты: каждый уровень дерева требует нескольких вызовов генерации и оценки, поэтому на один ответ могут уйти десятки вызовов модели или больше и намного больше токенов, чем для одной цепочки, а задержка инференса увеличивается соответствующим образом.

Тот же цикл генерации, оценки и расширения проявляется на гораздо более высоком уровне абстракции при автоматизированном поиске экспериментов, например при настройке гиперпараметров. В AutoTrain на платформе Ultralytics Ask AI может обучить несколько моделей Ultralytics YOLO, различающихся одним параметром — размером изображения: 640, 800 и 960, после чего сравнить завершённые запуски по значению mAP50-95 на валидационной выборке и предложить следующий эксперимент на основе лучшего результата.

Tree of Thoughts и родственные методы#

• Промптинг с цепочкой рассуждений: Единственная линия рассуждений — то же, что дерево с одной ветвью на каждом уровне.
• Промптинг ReAct: Чередует рассуждения с действиями во внешней среде, например с поиском или вызовами инструментов, и продолжает на основе их результатов. ToT выполняет поиск по собственным вариантам рассуждений модели.
• Согласование результатов: Генерирует несколько полных цепочек рассуждений и выбирает итоговые ответы большинством голосов, не оценивая промежуточные шаги.
• Граф мыслей: Обобщает дерево до графа, в котором мысли можно также объединять и уточнять; сообщалось, что качество сортировки на 62% выше, чем у ToT, при этом затраты более чем на 31% ниже.
• Поиск по дереву методом Монте-Карло (MCTS): Алгоритм поиска, лежащий в основе AlphaGo. Он балансирует между исследованием новых ветвей и использованием перспективных ветвей и может заменить поиск по мыслям в ширину или глубину.
• Модели рассуждений: Обучаются с помощью обучения с подкреплением генерировать длинные цепочки рассуждений за один проход, тогда как ToT получает ветвление и возврат к предыдущим шагам благодаря внешней программе поиска, работающей поверх обычной модели.