Beam search — стратегия генерации, которая поддерживает несколько лучших вариантов продолжения последовательности вместо одного, отбирая наиболее перспективные пути.
Определение
Beam search — это алгоритм поиска последовательности, который сохраняет несколько лучших частичных вариантов ответа на каждом шаге генерации. В отличие от жадного поиска, который выбирает только один самый вероятный токен, beam search хранит K лучших кандидатов (beam size) и развивает каждый из них. Такой подход позволяет модели исследовать пространство вариантов шире и избегать локально оптимальных, но глобально слабых решений.
Beam search используется в языковых моделях, системах машинного перевода, генерации кода, поиске оптимальных последовательностей и задачах структурного вывода.
Как работает
Алгоритм поддерживает список K частичных гипотез. На каждом шаге каждая гипотеза расширяется всеми возможными токенами, после чего выбираются K лучших новых вариантов по совокупной лог-вероятности.
- инициализация — beam состоит из одной пустой гипотезы (или токена BOS);
- расширение — каждая гипотеза порождает h новых веток по количеству токенов словаря;
- оценка — рассчитывается суммарная лог-вероятность кандидата;
- фильтрация — отбираются K лучших гипотез;
- остановка — генерация завершается, когда все гипотезы достигли токена EOS или лимита длины.
Чтобы избежать предпочтения коротких последовательностей, используется length normalization — корректировка лог-правдоподобия в зависимости от длины.
Где применяется
- Машинный перевод.
- Генерация кода.
- Суммаризация текста.
- Построение ответов в диалоговых системах.
- Генерация структур (формулы, JSON, XML).
- Поиск оптимальной последовательности действий в пошаговых системах.
- Мультимодальные генеративные модели (описания изображений, аудио-транскрипции).
Практические примеры использования
В машинном переводе beam search улучшает согласованность фраз: вместо выбора самого вероятного слова на каждом шаге модель рассматривает несколько вариантов развития фразы. Например, жадный метод может выбрать дословный, но неестественный перевод, тогда как beam search найдёт более грамматически правильный вариант.
В генерации кода beam search помогает удерживать структурную согласованность: альтернативные ветки позволяют исправить ранние ошибки последовательности.
В задачах суммаризации beam search улучшает логическую структуру итогового текста, так как модель может сравнивать несколько конкурирующих вариантов.
В ASR-моделях (распознавание речи) алгоритм позволяет выбирать лучшее текстовое соответствие по вероятностному выравниванию аудиофрагментов.
Ключевые параметры beam search
Поведение алгоритма сильно зависит от настроек:
- beam size — количество одновременно поддерживаемых кандидатов;
- length penalty — штрафы и нормализация длины;
- early stopping — остановка при достижении качественных гипотез;
- diversity penalty — борьба с дублирующимися ветками.
Большой beam size улучшает качество, но увеличивает вычисления. Малый beam size увеличивает риск локальных оптимумов.
Вариации beam search
Современные модели используют улучшенные варианты алгоритма:
- diverse beam search — разнообразит гипотезы, уменьшает копирование;
- no-repeat n-gram decoding — предотвращает повторяющиеся фрагменты;
- beam search с температурой — комбинирует стохастичность и детерминизм;
- constrained beam search — учитывает ограничения структуры (XML, JSON, код);
- masked beam search — исключает заведомо неверные токены;
- beam search + reranking — после генерации кандидаты переоцениваются отдельной моделью.
Преимущества и ограничения
- Плюс: улучшает качество генерации по сравнению с greedy decoding.
- Плюс: уменьшает риск локальных оптимумов.
- Плюс: подходит для задач с жесткими структурными требованиями.
- Плюс: детерминирован, воспроизводим.
- Минус: вырастает вычислительная стоимость при увеличении beam size.
- Минус: может приводить к однообразным или слишком предсказуемым ответам.
- Минус: склонен к избыточно коротким последовательностям без length penalty.
- Минус: хуже работает в творческих задачах по сравнению с sampling.
Связанные термины
- Greedy decoding
- Sampling
- Temperature
- Top-k sampling
- Top-p sampling
- Reranking
- Autoregressive decoding