Что такое beam search? Это поиск последовательности, при котором декодер ведёт несколько гипотез одновременно и отбрасывает слабые ветви. Вместо одного жадного продолжения алгоритм хранит фиксированное число лучших префиксов на каждом шаге. Такой поиск применяют в переводе, распознавании речи и суммаризации, где важна связная последовательность целиком.
Идея нескольких гипотез
Авторегрессионная генерация опирается на предположение, что вероятность последовательности слов раскладывается в произведение условных вероятностей следующего слова. Это записано в блоге Hugging Face «How to generate text»: вероятность всей последовательности равна произведению вероятностей каждого токена при условии предыдущих и начального контекста. Длина последовательности определяется по ходу генерации и соответствует шагу, на котором из распределения появляется токен EOS.
Из этой формулы вырастает главная идея beam search. Жадный поиск на каждом шаге берёт токен с максимальной условной вероятностью. Beam search удерживает несколько наиболее вероятных гипотез на каждом временном шаге и в конце выбирает гипотезу с наибольшей общей вероятностью. В блоге Hugging Face это описано как способ снизить риск потерять скрытую высоковероятную последовательность слов.
Слово «beam» здесь означает пучок параллельно развиваемых префиксов. Ширина пучка — гиперпараметр, который задаёт, сколько гипотез живёт одновременно. В документации Transformers параметр num_beams включает beam search, а значение больше единицы отличает его от жадного декодирования. При num_beams=1 и do_sample=False используется жадный выбор; при do_sample=True применяется sampling.
Практический смысл прост: один жадный путь может упереться в неудачный ранний токен и дальше идти по плохой ветке. Несколько гипотез дают шанс, что удачное продолжение сохранится в пучке и будет оценено на следующих шагах. Это вероятностный поиск по дереву с ограниченным набором сохраняемых гипотез.
Шаги алгоритма
Алгоритм удобно разложить на повторяющийся цикл. Ниже — порядок действий, который соответствует описанию в учебнике Dive into Deep Learning и в документации Transformers.
- Задать ширину пучка
kи максимальную длину выходаT'. - На первом шаге выбрать
kтокенов с наибольшими предсказанными вероятностями. Каждый становится началом отдельной гипотезы. - Для каждой активной гипотезы вычислить распределение следующего токена по словарю.
- Расширить каждую гипотезу всеми кандидатами словаря и получить
k × |Y|расширений. - Оценить расширения по накопленной вероятности префикса.
- Отобрать
kлучших продолжений и оставить их активными. - Повторять шаги 3–6, пока не сработает критерий остановки.
- Среди завершённых гипотез выбрать лучшую по итоговому счёту.
В учебнике Dive into Deep Learning этот цикл описан на примере словаря из пяти элементов и ширины пучка два. На первом шаге остаются токены A и C. На втором шаге вычисляются вероятности для всех продолжений и выбираются две лучшие пары, например A, B и C, E. На третьем шаге процедура повторяется, и в наборе кандидатов оказываются последовательности A, C, AB, CE, ABD и CED.
Ключевая деталь — стоимость. Полный перебор всех последовательностей имеет порядок O(|Y|^T'), экспоненциальный по длине. Жадный поиск стоит O(|Y| · T'). Beam search занимает промежуточное положение: O(k · |Y| · T'). Учебник приводит оценку: при словаре 10000 токенов и длине 10 полный перебор требует около 10^40 последовательностей, а жадный поиск обходится примерно 10^5.
Дерево greedy vs beam2
Разницу удобно увидеть на маленьком дереве фиксированной длины два. Это учебный арифметический пример; запуск модели здесь не проводился. На первом шаге два кандидата: A с вероятностью 0.60 и B с вероятностью 0.40. После A продолжают a1 с 0.51 и a2 с 0.49. После B продолжают b1 с 0.80 и b2 с 0.20.
Жадный поиск берёт на первом шаге A, затем a1. Накопленная вероятность такого пути равна 0.60 × 0.51 = 0.306. Beam width 2 на первом шаге хранит обе ветви, A и B. На втором шаге он оценивает четыре продолжения: 0.306, 0.294, 0.320 и 0.080. Лучшим оказывается B → b1 с вероятностью 0.320.
| Путь | Произведение вероятностей | Итог |
|---|---|---|
| A → a1 | 0.60 × 0.51 = 0.306 | лучший у greedy |
| A → a2 | 0.60 × 0.49 = 0.294 | отброшен |
| B → b1 | 0.40 × 0.80 = 0.320 | лучший у beam width 2 |
| B → b2 | 0.40 × 0.20 = 0.080 | отброшен |
Таблица двух лучших гипотез после второго шага: B → b1 со счётом 0.320 и A → a1 со счётом 0.306. Beam search сохранил путь, который жадный поиск отбросил на первом шаге. Этот пример показывает механику отбора на равной длине и не доказывает превосходство метода на реальных задачах.
Для самопроверки закройте столбец с итогами и восстановите путь отбора. Сначала сравните только начальные ветви: жадный выбор оставляет A. Затем посчитайте продолжения каждой сохранённой ветви с её собственной условной вероятностью. Сопоставьте лучший результат ветви B с лучшим результатом ветви A. Если умножить вероятность продолжения на вероятность чужого префикса, получится другое дерево и неверная проверка. После ручного расчёта откройте таблицу и найдите первый шаг расхождения. Такой разбор помогает проверить понимание роли префикса и ширины пучка; правильный итог без объяснения отбора этого ещё не показывает.
Проверить арифметику можно кодом на стандартном Python. Он перечисляет все четыре последовательности и сверяет результат beam width 2 с полным эталоном дерева.
from itertools import product
# Учебное дерево фиксированной длины 2.
# Шаг 1: A=0.60, B=0.40
# После A: a1=0.51, a2=0.49
# После B: b1=0.80, b2=0.20
first = {"A": 0.60, "B": 0.40}
second = {
"A": {"a1": 0.51, "a2": 0.49},
"B": {"b1": 0.80, "b2": 0.20},
}
paths = []
for head, p_head in first.items():
for tail, p_tail in second[head].items():
paths.append((head, tail, p_head * p_tail))
paths.sort(key=lambda item: item[2], reverse=True)
print("Все пути:", paths)
print("Beam width 2:", paths[:2])
greedy = max(paths, key=lambda item: (first[item[0]], item[2]))
print("Greedy:", greedy)
Запуск печатает четыре пути и два лучших. Сверка с полным перебором подтверждает, что на этом дереве beam width 2 находит максимум. При другой ширине пучка будущий лучший путь может быть потерян, поэтому результат зависит от k.
Почему считают логарифмы
Произведение вероятностей быстро становится очень маленьким числом. Каждый следующий множитель меньше единицы, и уже на десятках токенов произведение уходит в область, где обычная арифметика с плавающей точкой теряет точность. Логарифм превращает произведение в сумму: сумма логарифмов равна логарифму произведения.
Это свойство используют для устойчивого сравнения гипотез. Вместо перемножения длинной цепочки вероятностей алгоритм складывает их логарифмы. Порядок гипотез при этом сохраняется, потому что логарифм монотонно возрастает. Учебник Dive into Deep Learning записывает итоговый счёт как сумму логарифмов условных вероятностей, делённую на длину в степени α.
Условные вероятности относятся к каждому полному префиксу. Вероятность токена на третьем шаге зависит от первых двух токенов и контекста. Поэтому при расширении гипотезы пересчитывается распределение именно для её префикса. Сумма логарифмов по шагам даёт логарифм произведения вероятностей всей последовательности.
В коде это выглядит как накопление счёта. Каждое расширение получает счёт родителя плюс логарифм вероятности нового токена. Сортировка идёт по убыванию накопленного счёта. Такой приём описан и в блоге Hugging Face, и в документации Transformers как стандартная практика декодирования.
Длина и завершение
Разные длины ломают прямое сравнение произведений. У длинной последовательности больше множителей, и её сырое произведение почти всегда меньше. Учебник Dive into Deep Learning вводит нормировку: счёт делится на L^α, где L — длина финальной последовательности, а α обычно равен 0.75. В формуле учебника нормируется сумма логарифмов условных вероятностей: score = log P / L^α.
Логарифм вероятности неположителен. При фиксированном log P деление на больший положительный L^α приближает счёт к нулю, что повышает его при выборе максимума. Сами последовательности имеют разные вероятности, поэтому итог определяется всей формулой. Сырые произведения можно сравнивать как выбранную целевую функцию, но они склоняют отбор к коротким последовательностям. Для сравнения разных длин заранее определите формулу и правило остановки выбранной реализации.
Завершение связано с токеном EOS. В блоге Hugging Face показано, что при early_stopping=True генерация заканчивается, когда все гипотезы пучка достигли EOS. Документация Transformers описывает beam search как стратегию, которая после определённого числа шагов выбирает последовательность с наибольшей общей вероятностью.
Обработка завершённых гипотез различается между реализациями. В статье «Beam Decoding with Controlled Patience» на arXiv описаны две схемы. Вариант vanilla ищет top-k последовательностей, включая завершённые и незавершённые. Схема FCFS собирает завершённые последовательности в порядке поступления и удаляет их из пучка. Авторы отмечают, что эта разница может заметно влиять на результат, особенно в суммаризации новостей.
Там же предложен patience factor — одна изменённая строка, которая отделяет критерий остановки от ширины поиска. В обычной схеме FCFS ширина пучка k задаёт и ширину, и момент остановки. Множитель p задаёт, сколько завершённых кандидатов нужно набрать до завершения декодирования. Авторы сообщают, что фактор терпения улучшает результаты на переводе и суммаризации при незначительном замедлении.
| Схема | Что попадает в top-k | Когда останавливается |
|---|---|---|
| vanilla | завершённые и незавершённые | все top-k последовательности завершены |
| FCFS | только незавершённые в пучке | набрано k завершённых кандидатов |
| FCFS с patience | незавершённые в пучке | набрано k · p завершённых кандидатов |
Когда sampling уместнее
Beam search хорошо работает там, где длина выхода предсказуема. Блог Hugging Face относит к таким задачам машинный перевод и суммаризацию. В документации Transformers beam search назван подходящим для задач, привязанных к входу: описание изображения, распознавание речи. Там высокая общая вероятность последовательности часто совпадает с хорошим ответом.
Для открытой генерации картина другая. В блоге Hugging Face перечислены причины, по которым beam search может проигрывать: желаемая длина сильно варьируется, а повторяющиеся фрагменты трудно контролировать. Ссылаясь на работу Holtzman et al. 2019, автор пишет, что качественный человеческий текст следует распределению, которое не сводится к самым вероятным следующим словам.
Sampling выбирает следующий токен случайно по условному распределению. В документации Transformers multinomial sampling включается параметрами do_sample=True и num_beams=1. Такой режим может уменьшать повторяемость и давать более разнообразные выходы. Для диалогов, историй и других открытых задач это часто практичнее.
Промежуточные варианты — top-k и top-p. Top-k оставляет K самых вероятных слов и перераспределяет массу между ними. Top-p берёт минимальный набор слов, чья суммарная вероятность превышает порог p. В блоге Hugging Face приведён пример с p=0.92: в одном случае в набор вошли девять слов, в другом хватило трёх. Обе схемы хорошо работают на практике, а top-p может сочетаться с top-k.
Полезный приём — вернуть несколько гипотез и выбрать вручную. В блоге Hugging Face показано, что параметр num_return_sequences задаёт число лучших пучков для возврата, при этом значение не должно превышать num_beams. Такой режим удобен, когда автоматический счёт не отражает цель задачи.
Границы эвристики
Beam search — приближённый поиск с отсечением ветвей. На нашем двухшаговом дереве ширина два сохраняет все начальные ветви и находит более вероятный путь. Этот результат ограничен заданным деревом. При других распределениях и глубине отсечение может удалить перспективный префикс; глобальный максимум конечная ширина не гарантирует.
Ширина пучка не даёт гарантии качества. В статье «Beam Decoding with Controlled Patience» упоминается эффект, который исследователи называют проклятием beam search: большие пучки находят последовательности с более высоким счётом, а качество задачи при этом падает. Причина в расхождении между оптимизируемым счётом и метрикой, которая важна человеку.
Память и время растут вместе с шириной. Стоимость поиска оценивается как O(k · |Y| · T'). Документация NVIDIA NeMo для распознавания речи отмечает, что beam-декодирование может быть очень медленным, и рекомендует GPU-ускоренный вариант для продакшена. Там же указано, что быстрый beam даёт разницу около 20% по показателю RTFx относительно жадного декодирования.
Отдельная граница — зависимость от модели. В блоге Hugging Face приведена ссылка на Welleck et al. 2019: наблюдаемые недостатки жадного поиска и beam search, прежде всего повторы, связаны с самой моделью и способом её обучения. При изменении цели обучения человеческие оценки показывали более связный текст у beam search по сравнению с top-p.
Практический вывод: beam search — инструмент для задач с предсказуемой длиной и явной связью с входом. Для открытой генерации разумно сравнить его с sampling на своей задаче. Выбор ширины, штрафа за длину и правила остановки остаётся настройкой под конкретный сценарий.
Частые вопросы
Что такое beam search простыми словами?
Это способ выбирать продолжение текста, при котором модель ведёт несколько вариантов сразу. На каждом шаге слабые варианты отбрасываются, а сильные развиваются дальше. В конце выбирается вариант с лучшим суммарным счётом.
Чем beam search отличается от жадного поиска?
Жадный поиск держит один путь и на каждом шаге берёт самый вероятный токен. Beam search держит k путей и оценивает их накопленную вероятность. На учебном дереве с шириной два он сохранил путь B → b1 со счётом 0.320, который жадный поиск отбросил.
Почему в beam search используют логарифмы вероятностей?
Произведение многих вероятностей становится слишком маленьким числом. Логарифм превращает произведение в сумму и сохраняет порядок гипотез. Сумма логарифмов равна логарифму произведения вероятностей всей последовательности.
Когда лучше выбрать sampling?
Sampling уместен в открытой генерации: диалогах, историях, задачах со свободной длиной. В документации Transformers он включается через do_sample=True и num_beams=1. Такой режим может давать разнообразие и уменьшать повторяемость.
Гарантирует ли beam search лучший результат?
Нет. Блог Hugging Face указывает, что метод не гарантирует нахождение самой вероятной последовательности. Большая ширина пучка может ухудшить качество задачи при росте счёта. Итог зависит от модели, длины выхода и правила остановки.
