Beam search — стратегия генерации, которая поддерживает несколько лучших вариантов продолжения последовательности вместо одного, отбирая наиболее перспективные пути.
Определение
Beam search — это алгоритм поиска последовательности, который сохраняет несколько лучших частичных вариантов ответа на каждом шаге генерации. В отличие от жадного поиска, который выбирает только один самый вероятный токен, beam search хранит K лучших кандидатов (beam size) и развивает каждый из них. Такой подход позволяет модели исследовать пространство вариантов шире и избегать локально оптимальных, но глобально слабых решений.
Beam search используется в языковых моделях, системах машинного перевода, генерации кода, суммаризации и задачах структурного вывода.
Как работает
Алгоритм поддерживает список K частичных гипотез. На каждом шаге каждая гипотеза расширяется всеми возможными токенами, после чего выбираются K лучших новых вариантов по совокупной лог-вероятности.
- Инициализация — beam состоит из одной пустой гипотезы или токена начала последовательности.
- Расширение — каждая гипотеза порождает множество новых веток по количеству возможных токенов.
- Оценка — рассчитывается суммарная лог-вероятность последовательности для каждого кандидата.
- Фильтрация — сохраняются K лучших гипотез, остальные отбрасываются.
- Остановка — генерация завершается, когда все гипотезы достигли токена конца или лимита длины.
Чтобы избежать перекоса в пользу слишком коротких последовательностей, часто используют нормализацию по длине (length normalization) или length penalty, корректируя итоговый скор.
Где применяется
- Машинный перевод с жёсткими требованиями к связности и грамматике.
- Генерация кода и формальных языков.
- Суммаризация длинных текстов.
- Построение ответов в детерминированных диалоговых системах.
- Генерация структурированных документов (JSON, XML, формулы).
- Поиск оптимальной последовательности действий в пошаговых системах.
- Мультимодальные модели: расшифровка аудио, подписи к изображениям.
Практические примеры использования
В машинном переводе beam search улучшает согласованность предложения: модель рассматривает несколько конкурирующих вариантов перевода целиком, а не принимает решение только на уровне следующего токена. Это снижает риск грамматически корректных, но смыслово слабых фраз, которые часто даёт жадный декодер.
В генерации кода beam search помогает восстановить правильную структуру программы, даже если локально более вероятный токен ведёт к тупику. Альтернативные гипотезы позволяют «перепрыгнуть» через ранние ошибки и прийти к рабочему продолжению.
В задачах суммаризации beam search даёт модели возможность выбирать между более информативными и более компактными резюме текста, балансируя длину и содержательность.
В системах распознавания речи beam search используется поверх акустической модели: алгоритм перебирает разные расшифровки аудио и выбирает последовательность с максимальным объединённым скором языковой и акустической моделей.
Ключевые параметры beam search
На поведение алгоритма сильно влияют несколько настроек:
- Beam size — количество параллельных гипотез. Чем больше значение, тем выше качество, но тем дороже вычисления.
- Length penalty / normalization — коэффициенты, компенсирующие склонность к коротким последовательностям.
- Early stopping — стратегии остановки при появлении достаточно хороших гипотез.
- Diversity penalty — штрафы за слишком похожие гипотезы, чтобы повысить разнообразие вариантов.
Вариации beam search
В продакшене beam search редко используется в «чистом» виде. Чаще применяются модификации:
- Diverse beam search — добавляет штраф за схожесть между гипотезами и повышает разнообразие вариантов.
- No-repeat n-gram decoding — запрещает повтор одних и тех же n-грамм, снижая эффект «зацикливания» текста.
- Constrained beam search — накладывает структурные ограничения (например, корректный 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