Beam search e suoi limiti

Tieni vive le k ipotesi migliori, butta tutto il resto. È un compromesso tra il greedy che non torna indietro e la ricerca esaustiva che esplode. E nasconde un paradosso: cercare meglio la sequenza più probabile può peggiorare il risultato.

Perché questo capitolo

C’è un esperimento che mette a disagio chiunque pensi che cercare di più sia sempre meglio. Prendi un modello di traduzione automatica neurale, addestrato bene, che produce traduzioni decenti. Lo fai decodificare con la beam search — l’algoritmo standard — e provi a variare un solo parametro: l’ampiezza del fascio di ricerca, il beam width. Con fascio stretto, traduzioni decenti. Allarghi il fascio: la qualità sale un poco. Continui ad allargare: la qualità cala. La spingi al massimo, e per più di metà delle frasi il modello ti dice che la traduzione che preferisce in assoluto è la stringa vuota. Non un errore di programmazione: il modello, interrogato a fondo, preferisce non tradurre nulla.

Questo è il punto di partenza del capitolo. La beam search è uno degli algoritmi più usati nella pratica dell’AI applicata: decodifica le traduzioni, trascrive il parlato, genera didascalie, struttura output. È vecchia di mezzo secolo — nasce nel riconoscimento del parlato degli anni ‘70 — e il suo scheletro è semplice: a ogni passo, tieni le k ipotesi parziali migliori e scarta le altre. Capirla bene significa due cose. Primo: capire un compromesso ricorrente in tutta l’AI, quello tra una ricerca greedy povera ma economica e una ricerca esaustiva ottima ma intrattabile. La beam search è il punto intermedio, e il suo parametro k è la manopola del compromesso. Secondo: capire perché quel compromesso, applicato ai modelli generativi moderni, espone un difetto profondo — la sequenza più probabile sotto un modello di linguaggio non è la sequenza migliore.

Per chi costruisce sistemi AI, questo si traduce in scelte operative concrete. Quando configuri la decodifica di un modello, scegli tra greedy, beam search e sampling: sono opzioni nelle API che usi ogni giorno. Sbagliare la scelta significa testo ripetitivo dove serviva creatività, o output instabile dove serviva una risposta canonica. La beam search non è un dettaglio accademico: è il motivo per cui un traduttore automatico funziona e un chatbot, se decodificato allo stesso modo, si bloccherebbe a ripetere la stessa frase.

Contesto

Il setting è lo stesso degli altri capitoli di ricerca di questa Parte. C’è uno spazio di stati: in search-bfs-dfs erano nodi di un grafo, qui uno stato è una sequenza parziale, un prefisso di output costruito finora. Ogni stato ha dei successori: i possibili simboli che possono seguire (un token, una parola, un fonema). Ogni transizione da uno stato a un successore ha uno score, in genere una log-probabilità prodotta da un modello. L’obiettivo è trovare la sequenza completa con score totale massimo.

Se questo suona come la ricerca su grafi pesati di search-a-star, è perché lo è. La beam search appartiene alla stessa famiglia. La differenza è una sola, e la vedremo in dettaglio: A* tiene in memoria tutta la frontiera; la beam search ne tiene solo una fetta.

Da dove viene

La beam search non nasce nell’elaborazione del linguaggio naturale moderna. Nasce nel riconoscimento automatico del parlato (ASR, automatic speech recognition), un decennio prima che le reti neurali contassero qualcosa.

Il sistema si chiama Harpy, completato alla Carnegie Mellon University (CMU) nel 1976. Harpy fu scritto da Bruce T. Lowerre, allora dottorando, sotto la guida di Raj Reddy (informatico indiano-americano, in seguito vincitore del Turing Award 1994 per il lavoro pionieristico sui sistemi di percezione, incluso il riconoscimento del parlato). Il contesto era una sfida finanziata dalla DARPA, lo Speech Understanding Research project, che chiedeva ai sistemi di riconoscere un vocabolario di circa mille parole. Harpy ne gestiva 1011, e vinse la sfida entro la scadenza del 1976.

Il problema computazionale di Harpy era questo. La conoscenza linguistica del sistema — quali sequenze di fonemi formano parole valide, quali sequenze di parole formano frasi plausibili — era compilata in una rete enorme: circa cento milioni di transizioni tra “phone”. Riconoscere una frase pronunciata significava trovare il cammino migliore in questa rete, guidati dagli score acustici (quanto un pezzo di segnale audio somiglia a un dato fonema). Una ricerca esaustiva di quel cammino, sull’hardware degli anni ‘70, era impensabile.

La soluzione di Lowerre: a ogni istante temporale, tieni solo le ipotesi di cammino con score migliore — entro una soglia, o entro un numero fisso — e pota via tutte le altre. La procedura fu inizialmente chiamata locus model of search. Raj Reddy introdusse il termine “beam search” intorno al 1977: l’immagine è quella di un fascio di luce stretto che illumina solo una striscia dello spazio di ricerca, lasciando tutto il resto al buio.

Vale la pena fissare un fatto che torna utile più avanti: la beam search nasce come tecnica di potatura per rendere trattabile una ricerca su grafo altrimenti impossibile. La sua identità originaria è quella di un algoritmo di ricerca, non di un metodo per generare testo. L’uso nei modelli sequence-to-sequence (i modelli che mappano una sequenza in un’altra, come la traduzione) è una riapplicazione dello stesso scheletro a un problema diverso, arrivata decenni dopo.

La seconda vita della beam search arriva intorno al 2014, con i primi modelli sequence-to-sequence neurali per la traduzione: un encoder comprime la frase sorgente in una rappresentazione interna, un decoder genera la traduzione token per token. Il decoder, a ogni passo, produce una distribuzione di probabilità sul vocabolario. Generare la traduzione diventa allora un problema di ricerca identico, nella forma, a quello di Harpy: trovare la sequenza di token a probabilità complessiva massima. Lo spazio è di nuovo troppo grande per l’esaustività — il branching factor è l’intero vocabolario — e di nuovo la beam search è la risposta. Non c’è una filiazione diretta tra il codice di Lowerre e i decoder NMT: è lo stesso problema strutturale, la ricerca del cammino migliore in un grafo enorme, che fa riemergere indipendentemente lo stesso algoritmo. La terza fase, dal 2019 in poi, è il parziale ritiro: per la generazione di testo aperta gli LLM passano al campionamento, per le ragioni che la sezione “Dove si rompe” renderà esplicite.

Dove si colloca nel grafo

Il grafo concettuale, in una riga: la beam search sta tra la ricerca greedy (sceglie sempre il successore migliore, mai torna indietro) e la ricerca esaustiva (esplora tutto, garantisce l’ottimo). È un punto intermedio parametrizzato. Verso l’esaustiva si imparenta con search-bfs-dfs e search-a-star; per confronto si guarda anche monte-carlo-tree-search, l’altra strategia per spazi troppo grandi, e viterbi (in preparazione), il caso in cui la struttura del problema permette ancora la decodifica esatta.

Una distinzione utile da tenere a fuoco: la beam search è una strategia di ricerca, non di apprendimento. Non addestra niente, non ha parametri da ottimizzare. Riceve un modello già pronto — un modello che sa assegnare uno score a ogni transizione — e si limita a esplorarne lo spazio di output cercando una buona sequenza. Tutta la conoscenza sta nel modello; la beam search è solo il procedimento con cui quella conoscenza viene interrogata. Questo separa nettamente due fonti di errore, una distinzione che la sezione “Dove si rompe” userà come perno: un risultato cattivo può venire da una ricerca incompleta (la beam search ha mancato la sequenza buona) oppure da un modello difettoso (la sequenza buona non era quella a score massimo). Sono problemi diversi e si correggono in modi diversi.

L’intuizione

Tre angoli, prima di una riga di pseudocodice.

Angolo 1 — la manopola tra greedy ed esaustivo

Immagina di dover comporre una frase, parola dopo parola, e di voler massimizzare la “bontà” complessiva della frase. A ogni passo hai molte continuazioni possibili, ognuna con un punteggio.

La strategia più economica è greedy: a ogni passo prendi la parola con punteggio migliore, la fissi, e vai avanti. Non torni mai indietro. È velocissima, ma è miope: una parola che sembra ottima al passo 3 può intrappolarti in un vicolo cieco al passo 7, e tu non te ne accorgerai mai, perché hai buttato via tutte le alternative al passo 3. Il greedy non sa che una scelta localmente buona può essere globalmente cattiva.

La strategia più costosa è esaustiva: tieni vive tutte le frasi parziali possibili, le estendi tutte, e alla fine scegli la migliore. Garantisce di trovare la frase ottima — non puoi perdere niente se non scarti niente. Ma il numero di frasi parziali esplode: con b continuazioni possibili per parola e frasi lunghe L parole, hai b elevato a L cammini. Per qualunque problema realistico, intrattabile.

La beam search è la manopola tra i due. Invece di tenere una sola ipotesi (greedy) o tutte (esaustiva), ne tieni k. A ogni passo: prendi le tue k frasi parziali, generi tutte le loro continuazioni, e dal mucchio risultante tieni di nuovo le k migliori. Il parametro k è il beam width, l’ampiezza del fascio.

Gli estremi della manopola sono esattamente le altre due strategie. Con k = 1, la beam search è il greedy: tieni una sola ipotesi, prendi sempre la continuazione migliore. Con k che tende a infinito, non poti mai nulla e la beam search è la ricerca esaustiva. Greedy ed esaustiva non sono algoritmi diversi dalla beam search: sono i suoi due casi limite. Tutto il valore della beam search sta nei valori intermedi di k, dove paghi un costo k volte quello del greedy ma compri una capacità limitata di non restare intrappolato in scelte locali.

Angolo 2 — il fascio di torce nel labirinto

Cambia immagine. Sei a esplorare un labirinto al buio e hai k torce. Non puoi illuminare tutto — il labirinto è troppo grande — e non puoi seguire una torcia sola, perché rischi il vicolo cieco.

Allora fai così. Tieni le k torce ai k punti più promettenti esplorati finora. A ogni passo, da ognuno di quei k punti guardi tutti i corridoi che si aprono. Ora hai molti più di k punti candidati — fino a k per il numero di corridoi per punto. Li valuti tutti con un solo criterio, lo score, e riposizioni le k torce sui k candidati migliori del mucchio.

Due dettagli che questa immagine rende chiari, e che sono fonte di malintesi.

Primo: le k torce non sono assegnate a k rami fissi. Non è che la torcia numero 2 segue per sempre il secondo corridoio scelto all’inizio. A ogni passo tutti i candidati competono per le k posizioni. È perfettamente possibile che, dopo un passo, tutte e k le torce finiscano su corridoi che discendono dallo stesso punto del passo precedente, perché quel punto aveva le k continuazioni migliori in assoluto. La beam search non esplora k percorsi indipendenti: tiene viva una popolazione di k ipotesi che a ogni passo viene rimescolata.

Secondo: il fascio può perdere la soluzione migliore. Se al passo 5 la frase parziale che porterebbe al finale ottimo ha uno score appena fuori dai top-k, viene scartata, e con lei tutto il suo futuro. Nessuna torcia la illuminerà più. La beam search è un algoritmo incompleto: con k finito non c’è garanzia di trovare l’ottimo. Quando lo perde, si dice che ha commesso un search error, un errore di ricerca. Tieni a mente questo termine: nella sezione “Dove si rompe” scoprirai che i search error, contro ogni intuizione, a volte sono ciò che salva il risultato.

Angolo 3 — la selezione naturale di una popolazione di ipotesi

Un terzo modo di guardarla, più vicino al funzionamento interno. Pensa al beam come a una popolazione di k individui, dove ogni individuo è una sequenza parziale. A ogni generazione — ogni passo della ricerca — succedono due cose: una riproduzione e una selezione.

La riproduzione: ogni individuo della popolazione genera la sua prole, cioè tutte le sue continuazioni possibili. Una popolazione di k individui produce così una prole di fino a k per b sequenze, dove b è il branching factor. La popolazione si gonfia.

La selezione: si misura ogni individuo della prole con un’unica funzione di fitness — lo score cumulato — e si tiene in vita solo l’élite, i k migliori. Tutto il resto si estingue, senza lasciare discendenza.

Questa lente rende intuitive due proprietà della beam search. La prima: la beam search è elitaria e senza memoria del fallimento. Non tiene traccia di chi ha eliminato, non rivisita, non ripesca. Una linea genetica estinta è estinta. La seconda: la diversità della popolazione collassa facilmente. Se a un certo passo un singolo prefisso ha le k continuazioni migliori in assoluto, l’intera generazione successiva discende da quell’unico antenato — il beam si è ristretto a un solo lignaggio, mascherato da k individui che sono solo varianti vicine. È un fenomeno reale e fastidioso: nella generazione di testo, le k sequenze del beam finiscono spesso per differire di un paio di parole soltanto, una mancanza di diversità che vedremo tornare nella sezione “Dove si rompe”. Esistono varianti come la diverse beam search che aggiungono una penalità di similarità proprio per contrastare questo collasso.

La meccanica

Lo scheletro della beam search in pseudocodice. Lo stato è una sequenza parziale; score(t | s) è lo score della transizione che aggiunge il simbolo t alla sequenza s.

beam = [ sequenza_vuota con score 0 ]

ripeti finché ogni sequenza nel beam è completa (o si raggiunge max_len):
    candidati = []
    per ogni sequenza s nel beam:
        se s è completa:
            candidati.aggiungi(s)            # le complete restano in gara
        altrimenti:
            per ogni successore t di s:
                nuovo = s + t
                nuovo.score = s.score + score(t | s)
                candidati.aggiungi(nuovo)
    ordina candidati per score decrescente
    beam = primi k candidati                  # la potatura

restituisci la sequenza con score massimo nel beam

Tre righe meritano una lettura lenta.

nuovo.score = s.score + score(t | s) — lo score si accumula sommando. Quando lo score di una transizione è una log-probabilità, sommare i log equivale a moltiplicare le probabilità: $\log(p_1 \cdot p_2) = \log p_1 + \log p_2$ . La sequenza con somma di log massima è quindi la sequenza con probabilità-prodotto massima. Si lavora in spazio logaritmico per un motivo pratico: moltiplicare tante probabilità tutte minori di 1 produce numeri vicinissimi a zero, che un computer rappresenta male. Sommare log evita il problema. Tieni a mente un fatto: ogni log-probabilità è un numero negativo (la probabilità è minore di 1, il suo logaritmo è sotto zero). Più una sequenza è lunga, più termini negativi accumula, più basso è il suo score. Questa è una proprietà strutturale, e nella sezione “Dove si rompe” diventerà un problema serio.

ordina candidati ... beam = primi k candidati — è la potatura, il cuore dell’algoritmo. Il pool dei candidati a un dato passo ha dimensione fino a k per b, dove b è il branching factor, il numero di successori per stato. Da questo pool si tagliano i k migliori. Tutto il resto sparisce, con tutto il suo futuro possibile. Nota che il beam contiene k ipotesi in totale, non k per ogni ipotesi del passo precedente: il numero di ipotesi vive resta costante a k lungo tutta la ricerca.

se s è completa: candidati.aggiungi(s) — la gestione delle sequenze finite. Una sequenza si completa quando emette un simbolo di fine (in un modello di linguaggio, il token end-of-sequence, EOS). Ma le diverse ipotesi nel beam non si completano tutte insieme: una può finire al passo 8, un’altra continuare fino al 20. Cosa fare? Le strategie variano. La più semplice mette da parte le complete e continua finché il beam ha k sequenze terminate, poi sceglie. Altre si fermano quando la migliore sequenza completa ha score superiore a qualunque sequenza parziale ancora viva. Questo dettaglio sembra minore ma non lo è: la gestione dello stopping è una fonte nota di bug e di differenze silenziose tra implementazioni della stessa libreria.

Costo

Sia b il branching factor, k il beam width, L la lunghezza massima della sequenza. Per ognuno degli L livelli, la beam search genera O(k \cdot b) candidati e ne tiene k. Il costo in tempo è $O(L \cdot k \cdot b)$ ; il costo in memoria è $O(k \cdot L)$ , le k sequenze ognuna lunga fino a L.

Confronta con la ricerca esaustiva, che è $O(b^L)$ in tempo e memoria, e con il greedy, che è $O(L \cdot b)$ . La beam search prende l’esponente L della ricerca esaustiva e lo sostituisce con un fattore moltiplicativo k. Trasformare un’esplosione esponenziale in un fattore lineare: in una riga, questa è tutta la ragione d’essere della beam search.

Il legame formale con A*

Vale la pena rendere preciso il rapporto con search-a-star, perché non è un’analogia vaga ma una relazione esatta.

A* tiene in memoria tutta la frontiera, in una coda di priorità ordinata sulla funzione $f = g + h$ , dove g è il costo accumulato e h la stima euristica del costo residuo. La beam search fa la stessa cosa — ordina la frontiera su una funzione di score — ma a ogni livello tronca la frontiera ai migliori k nodi. Detto in modo netto: la beam search è A* con la frontiera potata ai top-k.

Da questa identità discendono i casi limite. Se non c’è euristica (h = 0), A* diventa una ricerca best-first sul solo costo accumulato, e la beam search corrispondente prende il nome di best-first beam search. Se k tende a infinito non si tronca nulla, e la beam search ridiventa la ricerca completa. Il troncamento della frontiera è precisamente ciò che fa perdere alla beam search la garanzia di ottimalità che A* possiede quando l’euristica è ammissibile. Si guadagna memoria limitata, si paga con l’incompletezza. Questa è una relazione tra algoritmi, non una somiglianza didattica: il lavoro Best-First Beam Search (Meister, Vieira, Cotterell, Transactions of the ACL 2020) la rende esplicita, mostrando che con uno score monotono nella lunghezza si può riformulare la beam search come una best-first search che restituisce lo stesso identico risultato con meno valutazioni di score.

Le varianti che lo scheletro rende possibili

Lo scheletro minimo — espandi, valuta, tieni i top-k — è abbastanza generale da ospitare una famiglia di varianti, ognuna pensata per un difetto specifico dell’algoritmo base.

La length normalization, già anticipata, modifica la funzione di score: non si massimizza la somma grezza di log-probabilità ma quella divisa per una funzione della lunghezza. È un cambio di criterio, non di scheletro.

La diverse beam search attacca il collasso di diversità descritto nell’Angolo 3. Divide il beam in gruppi e aggiunge, alla funzione di score, una penalità che scoraggia le sequenze troppo simili a quelle già scelte dagli altri gruppi. Il risultato è un beam dove le k ipotesi sono genuinamente diverse tra loro, non k varianti di una stessa frase. Utile quando si vogliono k traduzioni o k didascalie alternative invece di una sola.

La best-first beam search riorganizza l’ordine di esplorazione: invece di completare un livello prima di passare al successivo, espande sempre l’ipotesi globalmente più promettente. Quando lo score è monotono nella lunghezza restituisce lo stesso risultato della beam search classica, ma con meno valutazioni del modello — un guadagno puro di efficienza. Tutte e tre vivono sullo stesso scheletro: cambia la funzione di score o l’ordine di espansione, mai la struttura “tieni i k migliori”.

Esempi

Esempio 1 — beam search a mano, k = 2

Costruiamo una sequenza di tre simboli. A ogni passo ci sono tre simboli possibili: A, B, C. Lo score di ogni transizione è una log-probabilità (numero negativo: più vicino a zero, meglio è). Beam width k = 2.

Passo 1. Dalla sequenza vuota, i tre candidati con i loro score:

A   -0.3
B   -0.6
C   -1.5

I top-2 sono A (-0.3) e B (-0.6). Il beam diventa {A, B}. C è potato.

Passo 2. Estendiamo A e B. Score di transizione (dipendono dal prefisso):

da A:   A->A -1.0   A->B -0.2   A->C -2.0
da B:   B->A -0.4   B->B -0.5   B->C -0.9

Score cumulati dei sei candidati (score del prefisso più score della transizione):

AA  -0.3 + -1.0 = -1.3
AB  -0.3 + -0.2 = -0.5
AC  -0.3 + -2.0 = -2.3
BA  -0.6 + -0.4 = -1.0
BB  -0.6 + -0.5 = -1.1
BC  -0.6 + -0.9 = -1.5

I top-2 sono AB (-0.5) e BA (-1.0). Il beam diventa {AB, BA}. Nota: AB e… BA. Il greedy, al passo 2, sarebbe rimasto su A (il prefisso migliore) e avrebbe scelto AB. La beam search tiene anche BA, un prefisso che parte da B, sopravvissuto perché il suo score cumulato batte BB e AA. Le due torce non sono incollate al ramo A.

Passo 3. Estendiamo AB e BA:

da AB:  AB->A -0.1   AB->B -1.2   AB->C -1.8
da BA:  BA->A -2.0   BA->B -0.3   BA->C -0.7

Score cumulati:

ABA  -0.5 + -0.1 = -0.6
ABB  -0.5 + -1.2 = -1.7
ABC  -0.5 + -1.8 = -2.3
BAA  -1.0 + -2.0 = -3.0
BAB  -1.0 + -0.3 = -1.3
BAC  -1.0 + -0.7 = -1.7

La sequenza con score massimo è ABA (-0.6). È il risultato della beam search.

Domanda: era l’ottimo globale? Per saperlo bisognerebbe esplorare tutte le 3^3 = 27 sequenze. Con questi numeri sì, ABA lo era. Ma cambia un solo score — supponi che C->...->... portasse, lungo un cammino potato al passo 1, a uno score finale di -0.4 — e la beam search avrebbe restituito ABA (-0.6) mancando l’ottimo -0.4. Quel cammino era morto al passo 1, quando C uscì dai top-2. Questo è un search error: invisibile, perché l’algoritmo non sa cosa ha buttato via.

Esempio 2 — beam search in codice

Una implementazione compatta in Python. Il modello è astratto: una funzione successori(seq) che restituisce coppie (simbolo, log_prob).

import math

def beam_search(successori, e_completa, k, max_len):
    # ogni ipotesi: (sequenza, score_cumulato)
    beam = [([], 0.0)]

    for _ in range(max_len):
        if all(e_completa(seq) for seq, _ in beam):
            break

        candidati = []
        for seq, score in beam:
            if e_completa(seq):
                candidati.append((seq, score))          # resta in gara
                continue
            for simbolo, log_prob in successori(seq):
                candidati.append((seq + [simbolo], score + log_prob))

        # la potatura: tieni i k a score migliore
        candidati.sort(key=lambda x: x[1], reverse=True)
        beam = candidati[:k]

    return max(beam, key=lambda x: x[1])

Con k = 1 questa funzione è esattamente il greedy decoding: il beam ha una sola ipotesi, candidati[:1] prende sempre la continuazione migliore. Cambiando un solo argomento si passa da greedy a beam: la continuità tra i due non è teorica, è una riga di codice. La riga candidati.sort(...)[:k] è la potatura — l’unico punto in cui l’algoritmo decide cosa muore.

Una nota implementativa importante: questo codice ordina tutti i candidati per poi prenderne k. Quando k per b è grande — un modello di linguaggio ha un branching factor pari all’intero vocabolario, decine di migliaia di token — ordinare tutto è uno spreco. Le implementazioni reali usano una selezione parziale (un partial sort, o una coda di priorità di dimensione k) che trova i top-k senza ordinare il resto. Lo scheletro logico resta questo.

Esempio 3 — uno scenario reale: la traduzione automatica

Un sistema di traduzione automatica neurale (NMT, neural machine translation) riceve una frase sorgente e deve produrre la frase tradotta token per token. A ogni passo, il modello produce una distribuzione di probabilità su tutto il vocabolario della lingua di arrivo: per ogni token, quanto è plausibile come prossima parola della traduzione.

Decodificare con il greedy — prendere a ogni passo il token più probabile — funziona ma inciampa. Supponi che il modello, tradotta metà frase, abbia due continuazioni quasi pari merito: una imbocca una struttura sintattica che si rivelerà un vicolo cieco tre parole dopo, l’altra no. Il greedy ne sceglie una e non può più cambiare idea. La beam search con k = 5 tiene vive entrambe (e altre tre), e se la struttura buona produce parola dopo parola score migliori, alla fine emerge come sequenza vincente.

Per questo, dal periodo dei primi sistemi sequence-to-sequence (l’architettura encoder-decoder per la traduzione, attorno al 2014) la beam search è diventata lo standard di fatto per la decodifica in traduzione, tipicamente con k tra 4 e 10. Il sistema Google Neural Machine Translation descritto da Wu et al. nel 2016 (paper Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation, arXiv 2016) usa la beam search con due correttivi che vedremo tra poco: la length normalization e la coverage penalty.

Ma qui lo scenario reale incontra il paradosso. Lo stesso paper, e il lavoro che lo segue, mostra che spingere k oltre quel piccolo intervallo non migliora le traduzioni: le peggiora.

Vale la pena fermarsi un istante su questo, perché è il punto in cui la beam search smette di comportarsi come un comune algoritmo di ricerca. In una ricerca su grafo classica — un GPS che calcola un percorso — cercare di più non fa mai danno: al massimo trovi lo stesso ottimo, più probabilmente uno migliore. Nella decodifica neurale no. Qui cercare di più ti porta dritto verso una soluzione che il modello adora e che è pessima. Per capire perché un algoritmo innocuo diventi controproducente, bisogna entrare nella sezione dei limiti.

Esempio 4 — il bias verso le sequenze corte, con i numeri

Un quarto esempio, breve e numerico, per rendere tangibile un problema che la sezione “Dove si rompe” tratterà a fondo. Mette a confronto due sequenze candidate complete che un modello potrebbe produrre.

La sequenza A è corta, tre token, ognuno con probabilità 0.5. La sequenza B è lunga, otto token, ognuno con probabilità 0.7 — quindi B è “fatta meglio”, ogni suo token è più probabile di ogni token di A.

La probabilità della sequenza è il prodotto delle probabilità dei token:

A:  0.5^3  = 0.125
B:  0.7^8  ≈ 0.0576

In log (somma dei logaritmi naturali, numeri negativi):

A:  3 × ln(0.5) = 3 × (-0.693) = -2.08
B:  8 × ln(0.7) = 8 × (-0.357) = -2.85

La beam search che massimizza lo score grezzo sceglie A: il suo score (-2.08) è più alto di quello di B (-2.85). Ma A è composta di token mediocri (probabilità 0.5, una moneta lanciata), B di token solidi (0.7). L’unica ragione per cui A vince è che è più corta: ha accumulato meno termini negativi. Otto buoni passi perdono contro tre passi così così, solo per una questione di conteggio.

Ora applica la length normalization, dividendo lo score per la lunghezza (qui, per semplicità, una divisione diretta — la formula di Wu et al. è una variante smussata):

A:  -2.08 / 3 = -0.69
B:  -2.85 / 8 = -0.36

Con lo score normalizzato vince B (-0.36 batte -0.69), che è la risposta che ci aspettavamo. La length normalization non è un dettaglio cosmetico: senza, la beam search ha una preferenza strutturale e costante per la brevità, indipendente dalla qualità del contenuto.

Applicazioni pratiche

La beam search è viva e diffusa, ma in un sottoinsieme di task ben definito: quelli con una risposta corretta a struttura forte.

Traduzione automatica. Beam search con k piccolo (4-10) e length normalization è ancora lo standard. La frase tradotta “giusta” esiste, ha una struttura sintattica vincolata, e il beam stretto evita la maledizione descritta sotto.

Riconoscimento del parlato (ASR). Il dominio nativo, lo stesso di Harpy mezzo secolo fa. I decoder ASR combinano lo score acustico (quanto un pezzo di segnale somiglia a un fonema) con uno score linguistico (quanto una sequenza di parole è plausibile in quella lingua) e cercano la sequenza di parole che concilia al meglio i due. La beam search è il motore di questa ricerca; esistono varianti specializzate, come la beam search con fusione dei prefissi per i modelli addestrati con CTC (connectionist temporal classification, una funzione di costo che permette di addestrare un modello sequenza-a-sequenza senza allineamento esplicito tra audio e testo). Qui la maledizione della beam search non morde con la stessa forza: il task ha vincoli forti — esiste una trascrizione corretta — e questo tiene il modello lontano dalle soluzioni degeneri.

Summarization e image captioning. Generare un riassunto o una didascalia è un task con un output relativamente strutturato e una nozione di risposta corretta. La beam search moderata è una scelta comune.

Output strutturato e generazione di codice vincolato. Quando l’output deve rispettare una grammatica o uno schema (JSON valido, codice sintatticamente corretto), cercare a beam tra le sole continuazioni valide è più affidabile del campionamento puro, che può produrre output malformati.

Reasoning negli LLM. Una variante moderna applica la beam search non allo spazio dei token ma allo spazio dei passi di ragionamento: si tengono i k percorsi di ragionamento parziale migliori, valutati da un process reward model (un modello che assegna un punteggio alla qualità di ogni passo intermedio). È la beam search trasportata su un albero di pensieri invece che di parole — un ponte verso search-reasoning (in preparazione) nella Parte sul test-time compute.

Il punto operativo: se il tuo task ha una risposta “giusta” con struttura, beam search è una scelta solida. Se il tuo task è generazione aperta — dialogo, scrittura, completamento libero — non lo è, e la prossima sezione spiega perché.

C’è anche un filo che lega tutte queste applicazioni e che vale la pena rendere esplicito: la beam search rende meglio quando la funzione di score è affidabile lungo tutta la sequenza parziale, non solo alla fine. Una traduzione, una trascrizione, una didascalia hanno questa proprietà — il modello sa già a metà strada se la frase parziale è plausibile. È quando lo score parziale è informativo che tenere k ipotesi e potare ha senso. Quando invece la qualità di una sequenza si rivela solo arrivando in fondo, la beam search lavora alla cieca, e conviene un’altra famiglia di algoritmi, come si vedrà nel confronto con MCTS.

Dove si rompe

Questa è la sezione che conta di più. La beam search ha due classi di limiti: uno è algoritmico e atteso, l’altro è profondo e controintuitivo.

Limite 1 — l’incompletezza: i search error

Il limite atteso. La beam search con k finito è incompleta: può non trovare la sequenza a score massimo. Lo abbiamo visto nell’Esempio 1: una sequenza parziale che porterebbe all’ottimo, se al passo intermedio cade fuori dai top-k, viene potata con tutto il suo futuro. L’algoritmo non lo saprà mai.

Questo è il prezzo dichiarato del compromesso. Lo si mitiga aumentando k — più torce, meno probabile perdere il cammino buono — ma k costa tempo e memoria, e (sorpresa che arriva tra poco) aumentarlo non sempre aiuta. Per molti task pratici l’incompletezza è accettabile: una traduzione quasi ottima è una buona traduzione. Per altri no. Quando la struttura del problema lo permette, conviene usare un algoritmo esatto: la decodifica di Viterbi sugli HMM (Hidden Markov Model) trova l’ottimo globale senza potare, sfruttando la programmazione dinamica — vedi viterbi (in preparazione) e programmazione-dinamica. La beam search è ciò che si usa quando lo spazio degli stati esplode e nemmeno la programmazione dinamica salva.

Qui nasce la domanda pratica più frequente: che valore dare a k? Non c’è una risposta universale, perché k bilancia due pressioni opposte. Un k più grande riduce la probabilità di un search error, ma costa di più e — nei modelli neurali — rischia la maledizione descritta più sotto. Un k più piccolo è economico e, controintuitivamente, spesso dà risultati migliori sui modelli seq2seq. Nella pratica della traduzione automatica i valori vincenti sono piccoli, tra 4 e 10, e raramente vale la pena salire oltre; per la ricerca su grafi classici, dove non c’è il difetto del modello generativo, k si sceglie in base al budget di memoria disponibile. La lezione è che k non è una manopola “più è meglio”: è un parametro con un punto dolce, e quel punto va trovato per il problema specifico, non assunto al massimo.

Limite 2 — il bias verso le sequenze corte

Ricordi la nota sulla meccanica: ogni log-probabilità è negativa, e lo score si accumula sommando. Conseguenza diretta: più una sequenza è lunga, più è basso il suo score. Una sequenza di 5 token che accumula 5 numeri negativi avrà, a parità di “qualità per token”, uno score più alto di una di 20 token che ne accumula 20.

La beam search, massimizzando lo score grezzo, è quindi sistematicamente parziale verso le sequenze corte. In traduzione automatica questo produce traduzioni troppo brevi, che tagliano pezzi della frase sorgente. Nel caso patologico, come vedremo, produce la traduzione vuota.

La correzione standard è la length normalization: invece di massimizzare lo score grezzo, si massimizza lo score diviso per una funzione della lunghezza. La formula di Wu et al. 2016 divide lo score per $((5 + \text{len}) / 6)^\alpha$ , dove len è la lunghezza della sequenza e α un iperparametro tipicamente intorno a 0.6-0.7. Lo stesso paper aggiunge una coverage penalty, regolata da un parametro β, che premia le traduzioni che “coprono” tutte le parole della frase sorgente, misurando la copertura tramite le probabilità di attention. Sono due correttivi empirici: non discendono da un principio, sono manopole accordate finché la beam search non si comporta bene. Il fatto stesso che servano è un indizio del problema più profondo.

Limite 3 — la maledizione della beam search

Ed eccolo, il limite controintuitivo. È documentato in modo solido a partire dal 2018-2019 e ha un nome: la maledizione della beam search (beam search curse), o degenerazione da beam search.

Il fatto, nudo: nei modelli sequence-to-sequence neurali, allargare il beam oltre un valore piccolo peggiora la qualità misurata. La metrica di qualità (per la traduzione, il punteggio BLEU) sale leggermente passando da beam 1 a beam 4-5, poi scende, e con beam molto largo crolla. Questo contraddice frontalmente l’intuizione costruita finora: un beam più largo cerca meglio, trova sequenze a probabilità più alta, dovrebbe dare risultati migliori. Invece no. Cercare meglio peggiora.

La spiegazione arriva da un esperimento di Felix Stahlberg e Bill Byrne (paper On NMT Search Errors and Model Errors: Cat Got Your Tongue?, EMNLP 2019). I due costruiscono una procedura di inferenza esatta — beam search combinata con una depth-first search che garantisce di trovare la sequenza a score globalmente massimo — e la applicano a tutto il test set WMT15 inglese-tedesco con un Transformer. Il risultato è netto e imbarazzante: per oltre il 50% delle frasi, la sequenza che il modello considera più probabile in assoluto è la traduzione vuota.

Rileggi la frase. Il modello, interrogato sulla sequenza che ritiene più probabile, per più di metà degli input preferisce non produrre nulla. La beam search standard non trova queste sequenze degeneri solo perché è incompleta: i suoi search error la salvano. La conclusione di Stahlberg e Byrne, che gli autori stessi definiscono “altamente insoddisfacente”: la traduzione automatica neurale vaniglia funziona perché la beam search commette esattamente la giusta quantità di errori di ricerca. Abbastanza errori da non trovare la stringa vuota, non così tanti da perdere le traduzioni buone. Allargare il beam riduce gli errori di ricerca, e quindi avvicina la beam search alle sequenze degeneri che il modello, sbagliando, preferisce.

Perché mai la stringa vuota dovrebbe risultare la più probabile? Il meccanismo si lega al Limite 2. Una traduzione lunga è un prodotto di tante probabilità, ognuna minore di 1: ogni token aggiunto moltiplica per un fattore che abbassa il totale. La stringa vuota, che emette subito il token di fine, è un cammino cortissimo, e quindi parte avvantaggiata in questa gara al ribasso. Se il modello non è abbastanza sicuro dei propri token — e su frasi difficili spesso non lo è — il prodotto di molte probabilità incerte scende sotto la singola probabilità, modesta ma sola, di chiudere subito. Il bias verso le sequenze corte e la maledizione della beam search sono due facce dello stesso difetto: la moda di un modello probabilistico di sequenze tende verso il silenzio.

La diagnosi profonda è questa: il problema non è la ricerca, è il modello. Più precisamente, è l’obiettivo. Massimizzare la probabilità della sequenza — quello che in statistica si chiama decoding MAP, maximum a posteriori — è l’obiettivo sbagliato. La sequenza più probabile sotto il modello non è la sequenza migliore. La beam search, facendo bene il suo lavoro di cercare il modo della distribuzione, espone questo difetto invece di nasconderlo. Una beam search peggiore lo nasconde meglio.

Limite 4 — la degenerazione del testo: ripetizione e piattezza

Il lavoro che porta lo stesso fenomeno dalla traduzione alla generazione di testo aperta è The Curious Case of Neural Text Degeneration di Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes e Yejin Choi (arXiv aprile 2019, pubblicato a ICLR 2020). Il paper studia cosa succede quando si genera testo libero con GPT-2 (il modello di linguaggio di OpenAI del 2019) usando il decoding per massimizzazione.

Trova due cose. La prima: greedy e beam search producono testo che degenera. Diventa piatto, generico, e soprattutto si blocca in cicli ripetitivi. Con GPT-2 Large e una beam search di ampiezza 32, il testo entra in loop, ripetendo la stessa frase. C’è un meccanismo di feedback positivo: la probabilità che una frase venga ripetuta cresce a ogni ripetizione. Più il modello ha già ripetuto qualcosa, più è confidente nel ripeterlo ancora. La beam search, che cerca l’alta probabilità, cade dritta in questi pozzi di ripetizione e ci resta.

La seconda, più sottile: c’è una differenza distribuzionale netta tra testo umano e testo generato per massimizzazione. Il testo umano non sta sui token più probabili a ogni passo. Salta, sorprende, ha una “sorpresa” — la perplexity — che oscilla. La probabilità per-token del testo scritto da una persona non è massima: è alta abbastanza da essere coerente, ma non massima. Ne segue una conclusione che rovescia l’intuizione: massimizzare la probabilità della sequenza produce testo poco umano proprio perché troppo probabile. La frase più probabile è anche la più prevedibile, e il linguaggio umano vivo non è quello.

La proposta di Holtzman et al. è il nucleus sampling, anche detto top-p: invece di massimizzare, si campiona dal più piccolo insieme di token la cui probabilità cumulata supera una soglia p (per esempio 0.9), troncando la “coda inaffidabile” della distribuzione — i tantissimi token improbabili che, sommati, possono comunque rubare massa di probabilità e produrre incoerenza. È un metodo di campionamento, non di massimizzazione. Il punto teorico: per la generazione aperta non si vuole il modo della distribuzione, si vuole diversità controllata.

Un lavoro successivo, Is MAP Decoding All You Need? di Bryan Eikema e Wilker Aziz (COLING 2020), articola la tesi in forma generale: il problema è il criterio MAP. La distribuzione del modello, presa nel suo insieme, è ragionevole; è la sua moda — il singolo punto più probabile — a essere un pessimo rappresentante. La soluzione che propongono, il Minimum Bayes Risk decoding, sceglie la sequenza più “centrale” rispetto a un campione di sequenze, non quella più probabile.

Le strategie di decoding e quando si usa cosa

A questo punto si capisce perché esiste un intero ventaglio di strategie di decoding, e perché la beam search ne è solo una. Dato un modello che a ogni passo produce una distribuzione sui token successivi:

Greedy — prendi il token a probabilità massima. È beam search con k = 1. Deterministico, veloce, miope. Per quando serve l’output più canonico e rapido.
Beam search — tieni k ipotesi, massimizza la probabilità della sequenza. Buona per i task con una risposta giusta e struttura forte. Cattiva per la generazione aperta.
Sampling puro — campiona dalla distribuzione completa. Diversità massima, ma la coda lunga di token improbabili produce incoerenza.
Temperature — non un metodo a sé, ma un modulatore: scala i logit (i punteggi grezzi prima della softmax) dividendoli per un valore T. Con T < 1 la distribuzione diventa più appuntita (più vicina al greedy); con T > 1 più piatta (più casuale); con T = 1 resta quella nativa.
Top-k — campiona solo tra i k token più probabili, azzerando gli altri. Tronca la coda, ma con un k fisso: su una distribuzione molto appuntita include token spazzatura, su una piatta esclude token buoni.
Top-p / nucleus — campiona dal più piccolo insieme di token la cui massa cumulata supera p. La dimensione dell’insieme si adatta alla forma della distribuzione: pochi token quando il modello è sicuro, molti quando è incerto.

La regola pratica: per i task con una risposta corretta e struttura forte (traduzione, trascrizione, codice strutturato, summarization) hanno senso beam search o greedy. Per la generazione aperta (dialogo, scrittura creativa, completamento libero) si usa il sampling, quasi sempre top-p combinato con una temperature.

Questo chiude il ponte verso gli LLM. I moderni modelli di linguaggio generativi, quelli esposti via API, non usano beam search per il loro caso d’uso dominante. Usano sampling con temperature e top_p. Non è una svista: è la conseguenza diretta di tutto ciò che questa sezione ha descritto. Il loro compito principale è la generazione aperta, e per la generazione aperta cercare la sequenza più probabile è l’obiettivo sbagliato. La beam search resta — eccome — in traduzione, in trascrizione del parlato, in summarization, nei task con risposta strutturata. Ma il chatbot che ti risponde lo fa campionando, non massimizzando.

Limite 5 — beam search non rivede le sue stime

Un’ultima crepa, utile per il confronto con monte-carlo-tree-search. La beam search è una potatura deterministica in ampiezza: a ogni livello tiene i k migliori e va avanti, e lo score di una sequenza parziale non cambia mai in base a ciò che la ricerca scopre dopo. Una volta che un prefisso ha un certo score, quello è.

MCTS fa l’opposto: campiona traiettorie fino in fondo, usa i risultati per aggiornare stime di valore degli stati intermedi, e ridistribuisce lo sforzo di ricerca verso i rami che si rivelano promettenti. La beam search non ha questo meccanismo di retropropagazione. È adatta quando lo score parziale è già informativo di per sé — un modello di linguaggio assegna una log-probabilità sensata a ogni prefisso — e meno adatta quando il valore di uno stato si conosce bene solo arrivando in fondo, come una posizione di scacchi a metà partita. Scegliere tra beam search e MCTS è, in buona parte, scegliere se ti fidi dello score parziale.

Limite 6 — lo stopping e il costo che la teoria nasconde

Due crepe pratiche, meno profonde delle precedenti ma capaci di far sbagliare chi implementa.

La prima è lo stopping. La sezione sulla meccanica lo ha accennato: le k ipotesi del beam non si completano insieme. Quando una sequenza emette il token di fine, cosa si fa? Si interrompe tutta la ricerca? Si mette quella sequenza da parte e si continua con le altre k-1? Si va avanti finché si hanno k sequenze complete? Ogni scelta cambia il risultato. Un criterio troppo aggressivo si ferma presto e restituisce una sequenza corta che era solo la prima a finire, non la migliore; un criterio troppo conservativo spreca calcolo estendendo ipotesi che non vinceranno mai. Il lavoro A Call for Clarity in Beam Search (Kasai et al., 2022) documenta che librerie diverse — e versioni diverse della stessa libreria — implementano criteri di stop differenti, e che questo da solo basta a spiegare risultati non riproducibili tra un esperimento e l’altro. Quando configuri una beam search, lo stopping non è un dettaglio: è un iperparametro silenzioso.

La seconda è il costo reale. La formula $O(L \cdot k \cdot b)$ dice che il costo cresce linearmente in k, e suona innocuo. Ma k non è solo un fattore di tempo: in una decodifica neurale, ognuna delle k ipotesi del beam richiede una passata del modello a ogni passo. Un beam di ampiezza 10 significa decuplicare il numero di valutazioni del modello rispetto al greedy. Su un modello di linguaggio grande, il costo di una passata è alto, e questo si traduce in latenza e in spesa. La beam search non è gratis: paga il suo compromesso anche in moneta computazionale, e questo è un altro motivo — accanto alla maledizione descritta sopra — per cui i sistemi che servono generazione in tempo reale tendono a preferire greedy o sampling, che richiedono una sola passata per token.

Fraintendimenti ricorrenti

Cinque idee sbagliate che vale la pena disinnescare, perché circolano spesso.

“La beam search trova la sequenza ottima.” Falsa. La beam search con k finito è incompleta: la sequenza migliore può cadere fuori dai top-k a un passo intermedio e sparire. Solo k infinito garantisce l’ottimo, e a quel punto non è più beam search ma ricerca esaustiva. Il termine search error nomina esattamente i casi in cui la beam search non trova la sequenza a score massimo.

“Un beam più largo è sempre meglio.” Falsa per i modelli seq2seq neurali. Oltre un valore piccolo, allargare il beam peggiora la qualità misurata. Cercare meglio espone il fatto che la sequenza più probabile non è la migliore.

“Greedy e beam search sono algoritmi diversi.” Falsa. Il greedy è la beam search con k = 1. Stessa famiglia, stesso scheletro; il greedy è il caso degenere a una sola ipotesi.

“La beam search è un metodo di generazione di testo.” Imprecisa. Storicamente e concettualmente è un algoritmo di ricerca su grafi. La generazione di testo è un’area di applicazione, arrivata decenni dopo la nascita dell’algoritmo nella speech recognition.

“La beam search con k=2 esplora due alberi separati.” Falsa. I k slot del beam non sono assegnati a k rami fissi: a ogni passo tutti i candidati competono per i k posti, e tutte le k ipotesi sopravvissute possono discendere dallo stesso antenato del passo precedente. Il beam è una popolazione che si rimescola, non un fascio di percorsi paralleli indipendenti.

Collegamenti

search-bfs-dfs — la beam search è una breadth-first search potata: a ogni livello tiene solo i k nodi migliori invece dell’intera frontiera. Lo scheletro frontiera/espansione è quello del capitolo sulla ricerca non informata.
search-a-star — la relazione è esatta, non analogica: beam search è A* con la frontiera troncata ai top-k. Il troncamento è ciò che fa perdere la garanzia di ottimalità che A* ha con euristica ammissibile.
monte-carlo-tree-search — l’altra grande strategia per spazi di ricerca troppo grandi per l’esaustività. Confronto di filosofie: beam search deterministica e a score parziale fisso, MCTS stocastica e con stime di valore aggiornate.
programmazione-dinamica — quando la struttura del problema lo permette, la programmazione dinamica trova l’ottimo esatto senza potare. La beam search è ciò che si usa quando lo spazio degli stati esplode oltre la portata della DP.
viterbi (in preparazione) — la decodifica di Viterbi sugli HMM è il caso in cui la decodifica esatta è possibile; la beam search ne è l’approssimazione euristica quando lo spazio degli stati è troppo grande.
greedy-beam (in preparazione, Parte sull’anatomia degli LLM) — le strategie di decoding viste dal lato dei modelli di linguaggio: greedy, beam, sampling stocastico.
output-logits (in preparazione, stessa Parte) — temperature, top-k, top-p come post-processing dei logit del modello, il livello su cui agiscono le strategie di sampling.
search-reasoning (in preparazione, Parte sul reasoning e test-time compute) — la beam search applicata allo spazio dei passi di ragionamento, valutati da un process reward model.
seq2seq-2014 (in preparazione, Parte sulla storia dell’AI) — l’architettura encoder-decoder per la traduzione, il contesto in cui la beam search ha avuto la sua seconda vita come standard di decodifica.

Per andare oltre

Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, Yejin Choi, The Curious Case of Neural Text Degeneration (arXiv:1904.09751, 2019; ICLR 2020). Il paper di riferimento sulla degenerazione del testo neurale: documenta il loop di ripetizione e la differenza distribuzionale tra testo umano e testo massimizzato, introduce il nucleus sampling.
Felix Stahlberg, Bill Byrne, On NMT Search Errors and Model Errors: Cat Got Your Tongue? (EMNLP 2019). L’esperimento di inferenza esatta che mostra come il modo del modello sia, per oltre metà delle frasi, la traduzione vuota. La fonte primaria sulla maledizione della beam search.
Yonghui Wu et al., Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation (arXiv:1609.08144, 2016). Introduce la length normalization e la coverage penalty per la beam search nella traduzione automatica.
Clara Meister, Tim Vieira, Ryan Cotterell, Best-First Beam Search (Transactions of the ACL, 2020). Formalizza la beam search come A* con frontiera limitata e mostra l’equivalenza con una best-first search più efficiente.
Bryan Eikema, Wilker Aziz, Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation (COLING 2020). Articola in forma generale la tesi che il problema è il criterio MAP, e propone il Minimum Bayes Risk decoding come alternativa.