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

Um autor no Habr constrói em 2026 uma cadeia que vai dos algoritmos clássicos de NLP ao LLM-reranking por meio de um único princípio: não o melhor passo em cada jogada, mas o melhor caminho ao longo de toda a sequência — e explica isso usando o exemplo da interpretação de cartas de Tarô.

Por que o greedy fornece um resultado incorreto

O algoritmo greedy seleciona a opção mais provável em cada etapa, isolado do contexto subsequente. Em tarefas de NLP — anotação de classes gramaticais (POS tagging), reconhecimento de entidades nomeadas (NER) — isso leva a erros sistemáticos: a melhor tag local pode destruir a coerência de toda a sequência.

O algoritmo Viterbi resolve o problema usando programação dinâmica: ele considera todos os caminhos pelos estados ocultos simultaneamente e encontra o ótimo global. A complexidade computacional é O(N × T²) contra O(N × T) do greedy, onde N é o comprimento da sequência e T é o número de estados; isso é mais custoso, mas garante a otimalidade.

• Greedy: O(N × T), rápido, sem garantia de ótimo global
• Viterbi: O(N × T²), ótimo global exato de acordo com o modelo
• Beam search: mantém k melhores hipóteses — um compromisso entre precisão e velocidade (k típico = 4–10)
• CRF (Conditional Random Fields): parâmetros de transição treináveis sobre o decodificador Viterbi
• LLM reranking: um modelo de linguagem ranqueia o conjunto final de candidatos

O que beam search e CRF acrescentam

O beam search ocupa uma posição intermediária: mantém k melhores hipóteses em vez de uma. Para k = 1, coincide com greedy; para k = ∞, equivale à busca exaustiva. Valores de 4 a 10 proporcionavam um equilíbrio razoável em sistemas clássicos de MT, incluindo o Google Translate antes da transição para transformers.

O CRF (Campos Aleatórios Condicionais) adiciona parâmetros de transição treináveis: em vez de probabilidades fixas, o modelo aprende a partir dos dados quais sequências de tags são plausíveis. Com base nos resultados do benchmark CoNLL-2003, o BiLSTM-CRF superou o BiLSTM sem CRF em 1–2 pontos percentuais de F1 — um ganho consistente que garantiu ao CRF um papel padrão nos pipelines de NER antes do advento do BERT.

"Usando um contraexemplo, mostro por que a melhor escolha local perde para a global — e também onde termina a busca por estrutura e começa a geração de texto", formula o autor do artigo no

Habr a ideia central.

Onde os LLMs se encaixam nessa cadeia

Os transformers não usam Viterbi diretamente: o texto é gerado de forma autorregressiva, token por token; o método padrão de decodificação é beam search ou sampling (nucleus, temperature). O LLM reranking fecha a lacuna no próximo nível: o modelo gera 10–20 candidatos de resposta e, em seguida, um LLM separado (ou o mesmo, com um prompt diferente) os ranqueia por critérios de qualidade — coerência, precisão factual, conformidade com a instrução.

Como aponta o autor, é precisamente aqui que se encontra a fronteira entre a busca por estrutura e a geração de texto — e compreender essa fronteira explica por que o reranking em pipelines de produção de LLM ainda proporciona uma melhoria mensurável de qualidade em métricas automáticas.

O que isso significa

A cadeia greedy → Viterbi → beam search → CRF → LLM reranking é a evolução de um único princípio: a busca pelo melhor caminho global pelo espaço de significados possíveis. Compreender essa hierarquia ajuda a escolher o método de decodificação para uma tarefa de NLP específica e explica as decisões arquiteturais dos modelos de linguagem modernos.

Perguntas frequentes

Como o algoritmo Viterbi difere do beam search?

O Viterbi garante encontrar o caminho globalmente ótimo por todos os estados — é um algoritmo exato com busca exaustiva. O beam search mantém apenas k melhores hipóteses em cada etapa: é mais rápido, mas não garante a otimalidade.

O Viterbi é usado em LLMs modernos?

O Viterbi não é usado diretamente em transformers: a geração autorregressiva requer beam search ou sampling. O Viterbi permanece relevante em camadas CRF sobre encoders — por exemplo, em tarefas de NER e POS tagging baseadas em arquiteturas do tipo BERT.