Viterbi, beam search и LLM-reranking: как алгоритм выбирает один смысл из многих

Автор на Хабре выстраивает в 2026 году цепочку от классических NLP-алгоритмов до LLM-rerankinga через единственный принцип: не лучший шаг на каждом ходу, а лучший путь через всю последовательность — и объясняет это на примере интерпретации карт Таро.

Почему жадный greedy даёт неверный результат

Greedy-алгоритм выбирает наиболее вероятный вариант на каждом шаге в отрыве от последующего контекста. В NLP-задачах — разметке частей речи (POS-теггинг), распознавании именованных сущностей (NER) — это приводит к системным ошибкам: локально лучший тег может разрушить согласованность всей последовательности.

Алгоритм Viterbi решает задачу методом динамического программирования: он рассматривает все пути через скрытые состояния одновременно и находит глобальный оптимум. Вычислительная сложность — O(N × T²) против O(N × T) у greedy, где N — длина последовательности, T — число состояний; это дороже, но гарантирует оптимальность.

• Greedy: O(N × T), быстрый, без гарантии глобального оптимума
• Viterbi: O(N × T²), точный глобальный оптимум по модели
• Beam search: хранит k лучших гипотез — компромисс между точностью и скоростью (типичные k = 4–10)
• CRF (Conditional Random Fields): обучаемые параметры переходов поверх Viterbi-декодера
• LLM reranking: языковая модель ранжирует итоговый набор кандидатов

Что добавляют beam search и CRF

Beam search занимает промежуточное место: сохраняет k лучших гипотез вместо одной. При k = 1 он совпадает с greedy, при k = ∞ — с полным перебором. Значения от 4 до 10 обеспечивали разумный баланс в классических MT-системах, включая Google Translate до перехода на трансформеры.

CRF (Условные случайные поля) добавляют обучаемые параметры переходов: вместо фиксированных вероятностей модель учится на данных, какие последовательности тегов правдоподобны. По результатам бенчмарка CoNLL-2003, BiLSTM-CRF превосходил BiLSTM без CRF на 1–2 процентных пункта F1 — стабильный прирост, обеспечивший CRF стандартную роль в NER-пайплайнах до появления BERT.

«На контрпримере показываю, почему лучший локальный выбор проигрывает

глобальному — а также где заканчивается поиск структуры и начинается генерация текста», — формулирует ключевую идею автор статьи на Хабре.

Где в эту цепочку встраиваются LLM

Трансформеры не используют Viterbi напрямую: текст генерируется авторегрессивно, токен за токеном; стандартный метод декодирования — beam search или sampling (nucleus, temperature). LLM reranking закрывает разрыв на следующем уровне: модель генерирует 10–20 вариантов ответа, затем отдельный LLM (или тот же, с другим промптом) ранжирует их по критериям качества — связности, фактической точности, соответствию инструкции.

Как указывает автор, именно здесь проходит граница между поиском структуры и генерацией текста — и понимание этой границы объясняет, почему reranking в production LLM-пайплайнах по-прежнему даёт измеримый прирост качества по автоматическим метрикам.

Что это значит

Цепочка greedy → Viterbi → beam search → CRF → LLM reranking — это эволюция одного принципа: поиск глобально лучшего пути через пространство возможных смыслов. Понимание этой иерархии помогает выбирать метод декодирования под конкретную NLP-задачу и объясняет архитектурные решения современных языковых моделей.

Частые вопросы

Чем алгоритм Viterbi отличается от beam search?

Viterbi гарантирует нахождение глобально оптимального пути через все состояния — это точный алгоритм с полным перебором. Beam search сохраняет только k лучших гипотез на каждом шаге: он быстрее, но не гарантирует оптимальность.

Используется ли Viterbi в современных LLM?

В трансформерах Viterbi не применяется напрямую: авторегрессивная генерация требует beam search или sampling. Viterbi актуален в CRF-слоях поверх энкодеров — например, в задачах NER и POS-теггинга на базе BERT-подобных архитектур.