Viterbi, beam search e reranking com LLM: como um algoritmo escolhe um sentido entre muitos

Em 2026, um autor no Habr monta uma cadeia que vai dos algoritmos clássicos de NLP ao reranking com LLM a partir de um único princípio: o que importa não é o melhor passo a cada jogada, mas o melhor caminho ao longo de toda a sequência. Para ilustrar, ele usa a interpretação de cartas de tarô.

Por que o greedy dá um resultado errado

O algoritmo greedy (guloso) escolhe a opção mais provável a cada passo, sem considerar o contexto seguinte. Em tarefas de NLP, como a marcação de classes gramaticais (POS tagging) e o reconhecimento de entidades nomeadas (NER), isso gera erros sistemáticos: a melhor tag local pode destruir a coerência de toda a sequência.

O algoritmo de Viterbi resolve o problema por programação dinâmica: ele avalia todos os caminhos pelos estados ocultos ao mesmo tempo 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. É mais caro, mas garante a otimalidade.

• Greedy: O(N × T), rápido, sem garantia de ótimo global
• Viterbi: O(N × T²), ótimo global exato segundo o modelo
• Beam search: mantém as k melhores hipóteses — um meio-termo 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
• Reranking com LLM: 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: guarda as k melhores hipóteses em vez de uma só. Com k = 1, ele equivale ao greedy; com k = ∞, à busca exaustiva. Valores de 4 a 10 ofereciam um equilíbrio razoável nos sistemas clássicos de tradução automática, incluindo o Google Translate antes da migração para transformers.

Os CRF (Campos Aleatórios Condicionais) adicionam parâmetros de transição treináveis: em vez de probabilidades fixas, o modelo aprende com os dados quais sequências de tags são plausíveis. No benchmark CoNLL-2003, o BiLSTM-CRF superou o BiLSTM sem CRF em 1–2 pontos percentuais de F1 — um ganho estável, que fez do CRF peça padrão nos pipelines de NER até a chegada do BERT.

«Mostro, com um contraexemplo, por que a melhor escolha local perde

para a global — e também onde termina a busca de estrutura e começa a geração de texto», formula a ideia central o autor do artigo no Habr.

Onde os LLMs entram nessa cadeia

Os transformers não usam o Viterbi diretamente: o texto é gerado de forma autorregressiva, token a token, e os métodos de decodificação padrão são beam search ou sampling (nucleus, temperature). O reranking com LLM cobre a lacuna no nível seguinte: o modelo gera de 10 a 20 respostas candidatas, e um LLM separado (ou o mesmo, com outro prompt) as ranqueia por critérios de qualidade — coerência, precisão factual e aderência à instrução.

Segundo o autor, é justamente aqui que passa a fronteira entre busca de estrutura e geração de texto — e entender essa fronteira explica por que o reranking em pipelines de LLM em produção continua trazendo ganho mensurável de qualidade nas métricas automáticas.

O que isso significa

A cadeia greedy → Viterbi → beam search → CRF → reranking com LLM é a evolução de um único princípio: buscar o melhor caminho global pelo espaço de sentidos possíveis. Entender essa hierarquia ajuda a escolher o método de decodificação para cada tarefa de NLP e explica as decisões de arquitetura dos modelos de linguagem atuais.

Perguntas frequentes

Qual a diferença entre o algoritmo de

Viterbi e o beam search?

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

O Viterbi é usado nos LLMs modernos?

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