Beam search

Beam search — эвристический алгоритм поиска, который используется в ИИ для выбора наиболее вероятной последовательности слов или символов. Его задача — не перебирать все варианты подряд, а фокусироваться на самых перспективных ветвях, экономя вычислительные ресурсы.

Алгоритм лежит в основе машинного перевода, распознавания речи, автодополнения и больших языковых моделей. На каждом шаге существуют десятки тысяч вариантов следующего токена, а число комбинаций растёт экспоненциально, поэтому полный перебор невозможен даже для суперкомпьютера.

Интуитивно это выглядит так: мы движемся по дереву продолжений, но не проверяем каждую ветку, а задаём ширину луча n (например, 5). Сначала выбираем пять самых вероятных первых слов, затем для каждого из них смотрим возможные вторые и оставляем пять лучших комбинаций по суммарной вероятности. Так продолжаем до конца предложения, выбирая итоговую последовательность из оставшихся кандидатов. Узкий луч рискует отсечь хороший вариант из-за ранней ошибки; широкий даёт более точное решение, но требует больше памяти и времени.

Пример — машинный перевод. Переводя «The cat sat on the mat», алгоритм удерживает несколько правдоподобных вариантов на каждом шаге («кошка», «кот», «сидела», «лежала») и в итоге собирает связную фразу, отбрасывая абсурдные сочетания.

Таким образом, beam search — это компромисс между точностью и скоростью. Он позволяет нейросетям генерировать осмысленный текст за доли секунды. Понимание алгоритма объясняет, почему современные модели говорят так связно и почему иногда «застревают» на типовых шаблонах.