Beam search decoding — Hinglish notes

3.5.14 · AI-ML › Sequence Models

Greedy decoding ki problem

Jab hum sequences generate karte hain (translation, captioning, summarization), hum chahte hain:

y^{*} = ar g y max P (y ∣ x)

jahan $y = (y_{1}, y_{2}, \dots, y_{T})$ aur $P (y ∣ x) = \prod_{t = 1}^{T} P (y_{t} ∣ y_{< t}, x)$ .

Greedy decoding har step pe $y_{t} = ar g max P (y_{t} ∣ y_{< t}, x)$ pick karta hai. Yeh kyun fail hota hai: locally-optimal choices ka product globally optimal NAHI hota.

Example: "Je suis étudiant" ka English mein translation.

Greedy pick kar sakta hai: "I" (0.6) → "am" (0.7) → "student" (0.3) → $P = 0.126$
Better path: "I" (0.6) → "am" (0.65) → "a" (0.9) → "student" (0.8) → $P = 0.281$

Greedy path ne "a" miss kar diya kyunki step 2 mein "am" akela achha lag raha tha—lekin baad mein "a" include karna kaafi zyada natural phrase banata hai.

Derivation: Beam search sequences ko kaise score karta hai

Step 1: Objective function

Hum log-probability maximize karna chahte hain (raw probability se numerically zyada stable):

score (y) = lo g P (y ∣ x) = t = 1 \sum T lo g P (y_{t} ∣ y_{< t}, x)

Log kyun? Chhoti probabilities ka product underflow karta hai; logs ka sum range mein rehta hai. Aur: $ar g max P = ar g max lo g P$ kyunki $lo g$ monotonic hai.

Step 2: Length normalization

Raw log-probability longer sequences ko penalize karta hai (sum mein zyada terms, har ek negative). Ek 10-word sentence almost hamesha 3-word sentence se kam score karega, chahe woh better ho.

Fix: Length se divide karo (smoothing ke saath):

score_{norm} (y) = \frac{1}{T ^{α}} t = 1 \sum T lo g P (y_{t} ∣ y_{< t}, x)

Yahan $T$ generated tokens ki sankhya hai (matlab, hum <START> token count nahi karte, kyunki uski koi predicted probability nahi hoti). Neeche diye worked example mein, ek completed sequence jaise [<START>, Bonjour, <END>] ke $T = 2$ generated tokens hain (Bonjour aur <END>).

$α = 1$ : full normalization (average log-prob per token)
$α = 0$ : no normalization (raw sum)
$α \in (0.6, 0.7)$ : practice mein common hai (longer ke liye slight preference, kam penalty)

$α < 1$ kyun? Bahut short sequences ki average probabilities deceptively high ho sakti hain (jaise, "I." ki avg prob high hai but incomplete hai). Partial normalization balance banata hai.

Step 3: Algorithm

Formula Beam search algorithm

Input: Encoder output $h$ , beam width $k$ , length penalty $α$ Output: Top $k$ decoded sequences

beams = [([<START>], 0.0)]  # (sequence, cumulative_log_prob)
for t = 1 to max_length:
    candidates = []
    for (seq, score) in beams:
        if seq[-1] == <END>:
            candidates.append((seq, score))
            continue
        for token in vocabulary:
            new_seq = seq + [token]
            new_score = score + log P(token | seq, h)
            candidates.append((new_seq, new_score))
    # Keep top k by normalized score.
    # num_generated = number of tokens AFTER <START> (do not count <START>)
    beams = top_k(candidates, k, key=λ(s, sc): sc / num_generated(s)^α)
    
    if all sequences end with <END>: break
return beams

Length $T$ ke baare mein note: num_generated(s) = len(s) - 1 kyunki leading <START> token ek fixed marker hai, predicted token nahi. Yahi woh $T$ hai jo score formula mein use hota hai, isliye pseudocode aur worked example consistent hain.

Key insight: Har step pe hum $k \times V$ candidates generate karte hain lekin sirf $k$ rakhte hain. Yeh exponential search space ( $V^{T}$ total sequences) ko prune karta hai, $O (k T V)$ operations mein.

Worked example: "Hello" ka French mein translation

Setup: Vocabulary = {, Bonjour, Salut, }, beam width $k = 2$ , $α = 1$ .

Step 0: Initialize karo

Beams: [([<START>], 0.0)]

Step 1: <START> se expand karo

Candidates:
- [<START>, Bonjour]: $lo g 0.6 = - 0.51$
- [<START>, Salut]: $lo g 0.35 = - 1.05$
- [<START>, <END>]: $lo g 0.05 = - 3.0$
Top 2 rakho: Bonjour (-0.51), Salut (-1.05)

Yeh step kyun? Hum saare possible first words try karte hain, unhe model ki predicted probabilities se score karte hain, best 2 rakhte hain.

Step 2: Dono beams expand karo

Bonjour se:
- [<START>, Bonjour, <END>]: $- 0.51 + lo g 0.9 = - 0.51 - 0.11 = - 0.62$
- [<START>, Bonjour, Salut]: $- 0.51 + lo g 0.08 = - 0.51 - 2.53 = - 3.04$
Salut se:
- [<START>, Salut, <END>]: $- 1.05 + lo g 0.85 = - 1.05 - 0.16 = - 1.21$
- [<START>, Salut, Bonjour]: $- 1.05 + lo g 0.1 = - 1.05 - 2.30 = - 3.35$

Normalization ( $T =$ generated tokens ki sankhya $=$ len(seq) - 1 se divide karo; yahan har completed sequence mein 2 generated tokens hain, toh $T = 2$ ):

Bonjour <END>: $- 0.62/2 = - 0.31$
Salut <END>: $- 1.21/2 = - 0.605$

Top 2 rakho: [<START>, Bonjour, <END>] (normalized -0.31), [<START>, Salut, <END>] (normalized -0.605).

Yeh step kyun? Dono sequences end ho gayi, toh hum unke length-normalized scores compare karte hain. "Bonjour" jeetta hai kyunki model ne ise zyada probability assign ki.

Final output: "Bonjour" (score -0.31)

Common hyperparameters

Parameter	Typical range	Effect
Beam width $k$	4-10	Zyada = better quality, slower. ~10 ke baad diminishing returns.
Length penalty $α$	0.6-1.0	Zyada = longer sentences prefer karo. 0 = koi penalty nahi.
Min length	Task-dependent	Decoder ko kam se kam $n$ tokens generate karne par force karo (premature `<END>` se bachne ke liye).
N-gram blocking	2-4	Same $n$ -gram ko repeat hone se rokta hai (summarization mein useful).

Common mistake Common pitfall: Yeh sochna ki bade beams hamesha help karte hain

Galat intuition: " $k = 100$ must be better than $k = 5$ because we explore more."

Kyun sahi lagta hai: Zyada candidates = zyada thorough search = better result, hai na?

Fix:

Diminishing returns: $k \approx 10$ ke baad, top- $k$ sequences bahut similar hote hain (low-probability words mein alag hote hain). Tum sirf compute kharach kar rahe ho near-duplicates track karne ke liye.
Length bias amplify hoti hai: Bade $k$ ke saath, tum kaafi mediocre long sequences rakhte ho jo length normalization se benefit lete hain, better short sequences ko crowd out karte hue.
Empirical findings: Translation quality zyaadatar models ke liye $k = 4 - 10$ ke aas-paas peak karti hai (Britz et al., 2017).

Better approach: $k$ ko validation set pe tune karo. Agar $k = 5$ aur $k = 20$ similar BLEU scores dete hain, toh $k = 5$ use karo.

Common mistake Yeh bhool jana ki beam search ab bhi approximate hai

Galat intuition: "Beam search globally optimal sequence dhundh leta hai."

Kyun sahi lagta hai: Hum har step pe top-scoring sequences rakh rahe hain—surely hum best wala dhundh lenge?

Fix:

Beam search prunes karta hai. Agar true best sequence ka ek word early pe low-probability hai (jo top $k$ se bahar gir jaata hai), toh hum usse kabhi explore nahi karenge.
Example: True best hai "I have a cat" (overall prob 0.15), lekin "I have the" (0.12) aur "I own a" (0.13) step 2 pe beam mein hain. "I have a" ne step 2 pe 0.11 score kiya, toh prune ho gaya. Hum kabhi "I have a cat" tak nahi pahunchenge.
Implication: Beam search ek heuristic hai. Yeh greedy se kaafi better hai (jo deterministic aur bad hai), lekin exhaustive nahi hai. Critical applications ke liye, ensemble decoding ya sampling methods consider karo.

Doosre decoding methods ke saath comparison

Method	Search space	Quality	Diversity Speed
Greedy	1 path	Low	None
Beam search	$k$ paths	High	Low
Sampling (top- $p$ , temp)	Stochastic	Variable	High
Exhaustive	All $V^{T}$	Optimal	N/A

Beam search kab use karein:

Machine translation, summarization, captioning (single best output chahiye)
Jab fluency aur correctness creativity se zyada matter karti ho

Beam search kab use NA karein:

Story generation, dialogue (diversity chahiye; beam search generic responses produce karta hai)
Iske bajaye temperature ya nucleus sampling use karo

Connections

Seq2seq models — Beam search seq2seq ke liye standard decoding method hai
Attention mechanism — $P (y_{t} ∣ y_{< t}, x)$ encoder states pe attention use karke compute karo
Temperature sampling — Creative generation ke liye beam search ka alternative
BLEU score — Translation mein beam search outputs evaluate karne ke liye use hone wala metric

Recall 12 saal ke bacche ko samjhao

Imagine karo tum ek word game khel rahe ho jahan tum ek sentence ek word ek baar mein banate ho, aur har word ka ek "goodness score" hota hai (kitna likely lagta hai).

Greedy waise hai jaise sirf apna current sentence yaad rakho aur hamesha best next word pick karo. Lekin kabhi-kabhi ek word jo "okay" lagta hai abhi, baad mein kaafi better sentence lead kar sakta hai! Jaise agar tum "I want to eat pizza" bana rahe ho, aur tum "I want cookies" pick karte ho kyunki "cookies" ne 90 score kiya vs "to" ne 80. Lekin "to eat pizza" ne 90 × 95 = 8550 total score kiya hota, "cookies" (90) se kaafi better jo wahan khatam ho gaya.

Beam search waise hai jaise tumhare top 3 sentences ke liye sticky notes rakho har step pe. Tum teeno mein words add karne ki koshish karte ho, 3 × 26 = 78 nayi sentences milti hain, phir sirf best 3 rakhte ho. Toh tum multiple "what if I said THIS instead" paths explore kar rahe ho, lekin itne nahi ki tumhara brain explode ho jaaye.

"Beam width" yeh hai ki tumhare paas kitne sticky notes hain. 1 note = greedy. 100 notes = tumhara desk ek mess hai aur 10 notes ke baad zyada benefit nahi mil raha.

#flashcards/ai-ml

Greedy decoding aur beam search ke beech key difference kya hai? :: Greedy har step pe single highest-probability token pick karta hai (myopic). Beam search $k$ candidate sequences maintain karta hai aur multiple paths explore karta hai, global sequence quality improve karta hai.

Beam search mein hum raw probabilities ki jagah log-probabilities kyun use karte hain?

Numerical underflow avoid karne ke liye (chhoti numbers ka product floating point mein zero ho jaata hai) aur kyunki

lo g

products ko sums mein convert karta hai, jo compute aur compare karna aasan hai.

Beam search mein length normalization kya hai aur yeh kyun zaroori hai?

Cumulative log-probability ko

T^{α}

se divide karna, jahan

T

generated tokens ki sankhya hai (<START> exclude karke). Iske bina, longer sequences hamesha lower score karte hain (zyada negative terms), toh model short, incomplete outputs prefer karta.

Agar beam width

k = 1

ho, toh beam search kya ban jaata hai?

Greedy decoding—sirf single highest-probability sequence har step pe rakhi jaati hai.

Length $T$ , vocabulary size $V$ , aur beam width $k$ ke saath beam search ki computational complexity kya hai? :: $O (k T V)$ — $T$ steps mein se har ek par, hum $k$ sequences ko $V$ tokens consider karke expand karte hain.

Beam search globally optimal sequence dhundhne ki guarantee kyun nahi deta?

Yeh search tree prune karta hai—agar true best sequence ka ek token early pe low-probability hai jo top

k

se bahar gir jaata hai, toh woh path discard ho jaata hai aur kabhi explore nahi hota, chahe baad ke tokens usse optimal banate.

Production translation systems mein beam width ki typical range kya hai?

k = 4

10

. Zyada values ke diminishing returns hain aur length bias amplify ho sakti hai.

Tum beam search ki jagah sampling methods kab use karoge?

Creative generation tasks (stories, dialogue, diverse responses) ke liye jahan variety aur personality chahiye, single most probable (often generic) output nahi.

Length penalty hyperparameter

α

kya control karta hai?

Hum sequence length se kitni strongly normalize karte hain.

α = 0

: koi normalization nahi (short sequences prefer karta hai).

α = 1

: full normalization (average per token).

α \in (0.6, 0.7)

: common compromise.