Beam Search, Length Normalization, and Language Model Decoding

Purpose

A trained autoregressive model gives you $p(x_t \mid x_{<t})$ , a distribution over the next token. It does not give you a sequence. This note explains how greedy decoding and beam search choose sequences, why wider beams expose a preference for short outputs, how length normalization and per-word rewards correct that bias, and when sampling is a better objective. The model side of the factorization lives in Decoder-Only Transformers.

Beam curse and length normalization

The beam curse is the observation that increasing beam width can produce worse translations. In the translation experiments reported by Murray and Chiang (2018), wider beams find higher-scoring sequences that are shorter and have worse BLEU. A locally normalized sequence model can assign its highest probability to output that is too short. Each additional token contributes another log-probability term at or below zero, so a longer hypothesis usually gets a more negative raw log-probability.

Murray and Chiang (2018) connect this length bias to the drop in BLEU observed with wider beams. Their experiments find that correcting the preference for short hypotheses almost eliminates the beam problem.

Beam score	Formula	What it changes
Raw log-probability	$s(e) = \sum_t \log p(e_t \mid e_{<t})$	Favors hypotheses that accumulate fewer negative terms, often short output
Length normalization	$s(e) / \lvert e\rvert$	Compares average log-probability per token; this correction has no additional parameter
Per-word reward	$s(e) + \gamma \lvert e\rvert$	Adds a tunable reward for each generated token and can be applied while hypotheses remain in the beam

Length normalization does not make a wider beam inherently better. It changes the score used to compare hypotheses so that search is less dominated by sequence length. The correction must still be evaluated for the task and model; the per-word reward parameter $\gamma$ is tuned on held-out data.

Decoding as search

A decoder-only model factorizes sequence probability as $p(x_{1:T}) = \prod_t p(x_t \mid x_{<t})$ . Finding the most probable sequence under this factorization is a search over a tree that branches by the vocabulary size at every step, so exact search is intractable and every practical decoder is a heuristic.

Greedy decoding takes $\arg\max_x p(x \mid x_{<t})$ at each step. It is cheap and deterministic, and it can commit to a locally likely token that leads to a globally poor continuation, since the product of conditionals is not maximized by maximizing each factor.

Beam search keeps the $k$ highest-scoring partial hypotheses at each step, extends each by every token, and re-prunes to $k$ . It approximates the mode of the sequence distribution far better than greedy, which is why it became standard in machine translation. The Hugging Face generation docs recommend it for input-grounded tasks like translation and captioning, where the output is tightly constrained by the input and the mode is a sensible target.

Decoding as distribution shaping

Open-ended generation flips the problem. Holtzman et al. (2020) show that maximizing likelihood at decode time produces text that is bland and repetitive, and that models fall into repetition loops that likelihood actually rewards. Human text is not a sequence of maximally probable tokens. So instead of searching for the mode, sampling-based decoding draws from a reshaped version of the model’s distribution.

All of the following operate on the logits $x_i$ before the softmax, or on the resulting probabilities, at each step.

Temperature rescales logits before the softmax:

p_{i} = \frac{exp ( x _{i} / T )}{\sum _{j} exp ( x _{j} / T )}

$T < 1$ sharpens the distribution toward the argmax, $T > 1$ flattens it, and $T \to 0$ recovers greedy decoding. Temperature alone cannot remove the tail, only reweight it.

Top-k keeps the $k$ most probable tokens, renormalizes, and samples. The truncation size is fixed, which is the weakness: when the distribution is flat, $k$ tokens may cut off many reasonable options, and when it is peaked, $k$ tokens include junk.

Top-p (nucleus) sampling truncates adaptively. Holtzman et al. define the nucleus $V^{(p)}$ as the smallest set of tokens whose cumulative probability reaches $p$ :

x \in V^{(p)} \sum p (x ∣ x_{< t}) \geq p

Sampling then renormalizes over $V^{(p)}$ . Their argument is that the tail of the distribution is unreliable, individually low-probability tokens that jointly hold real mass, and sampling from it is what derails generations. The nucleus adapts per step: they observe it typically ranges from one to around a thousand candidates, and with GPT-2 large, $p \approx 0.95$ produced text closest to human statistics on their metrics.

Repetition penalty discounts tokens that already appeared. The formulation from CTRL divides the logit of any previously generated token by $\theta$ inside the softmax, with $\theta \approx 1.2$ reported as a good balance between staying truthful to the model and avoiding loops. Hugging Face exposes this as repetition_penalty, plus a hard variant no_repeat_ngram_size that forbids repeating any n-gram outright, which can misfire on text that legitimately repeats, like a name appearing many times.

These compose. A common stack is temperature, then top-k or top-p truncation, then renormalize and sample.

Sampling from toy logits

The whole pipeline is a few lines over a logit vector. This example applies temperature, top-k, and top-p to a toy distribution:

import numpy as np
 
rng = np.random.default_rng(0)
logits = np.array([4.0, 3.0, 2.5, 1.0, 0.5, -1.0, -2.0, -5.0])
 
def softmax(x):
    z = np.exp(x - x.max())
    return z / z.sum()
 
def sample(logits, temperature=1.0, top_k=None, top_p=None):
    logits = logits / temperature
    probs = softmax(logits)
    order = np.argsort(probs)[::-1]          # tokens by descending probability
    keep = np.ones_like(probs, dtype=bool)
    if top_k is not None:
        keep[order[top_k:]] = False
    if top_p is not None:
        csum = np.cumsum(probs[order])
        cut = np.searchsorted(csum, top_p) + 1   # smallest prefix with mass >= p
        keep[order[cut:]] = False
    probs = np.where(keep, probs, 0.0)
    probs /= probs.sum()
    return rng.choice(len(probs), p=probs), probs
 
token, probs = sample(logits, temperature=0.8, top_p=0.9)
print(np.round(probs, 3))   # [0.695 0.199 0.107 0.    0.    0.    0.    0.   ]
print(token)                # 0

At $T = 0.8$ with $p = 0.9$ , the nucleus holds three of eight tokens and the tail five are zeroed out. Raise the temperature to 1.5 and the same $p = 0.9$ nucleus grows to four tokens, which is the adaptivity that fixed top-k lacks.

Greedy and beam search over the same interface are a search loop rather than a sampling call. A minimal beam step scores every extension of every hypothesis and keeps the top $k$ by summed log-probability, which is where the length bias enters: each extension adds a negative term, so shorter hypotheses look better unless the score is corrected.

Task tradeoffs

flowchart TD
    Q{"Is the output tightly<br/>constrained by the input?"}
    Q -->|"yes: translation,<br/>summarization, captioning"| B["Beam search<br/>+ length correction"]
    Q -->|"no: continuation,<br/>dialogue, stories"| S["Truncated sampling"]
    S --> T["Temperature<br/>reshape the distribution"]
    T --> K{"Truncation rule"}
    K -->|"fixed cutoff"| TK["Top-k<br/>keep k most probable"]
    K -->|"adaptive cutoff"| TP["Top-p (nucleus)<br/>keep smallest set with mass ≥ p"]
    B -.->|"beam width 1"| G["Greedy decoding"]

    style B fill:#e3f2fd,stroke:#1565c0
    style TP fill:#e8f5e9,stroke:#2e7d32

The search-versus-sampling split follows the task. When the output is heavily determined by the input, translation, summarization, speech transcription, the mode is meaningful and beam search with a length correction is the right tool. When the task is open-ended, continuation, dialogue, story generation, the mode is degenerate and truncated sampling wins; this is the central empirical claim of Holtzman et al., who found beam search text far more repetitive than human text while nucleus sampling matched human statistics most closely. The objective mismatch is the same in both cases. Likelihood was the training objective, and decoding gets to choose how literally to take it.

Serving constraints

Decoding policy is not free at serving time. Beam search multiplies the KV-cache footprint by the beam width, since each hypothesis needs its own cache, which cuts directly into the memory budget described in Memory Management in LLM Serving Systems. Sampling parameters vary per request, so a batched server applies temperature and truncation per row of the logit matrix, cheap relative to the forward pass but part of every decode step in the loop described in Batching. Speculative decoding interacts with the sampling policy itself: the rejection rule in Speculative Decoding preserves the target distribution under sampling, and greedy or heavily truncated policies change draft acceptance rates. Assisted generation in the Hugging Face docs is the same idea exposed as a decoding strategy.

Elijah's Notes

Explorer

Beam Search, Length Normalization, and Language Model Decoding

Purpose

Beam curse and length normalization

Decoding as search

Decoding as distribution shaping

Sampling from toy logits

Task tradeoffs

Serving constraints

Sources

Graph View

Table of Contents

Elijah's Notes

Explorer

Beam Search, Length Normalization, and Language Model Decoding

Purpose

Beam curse and length normalization

Decoding as search

Decoding as distribution shaping

Sampling from toy logits

Task tradeoffs

Serving constraints

Sources

Related notes

Graph View

Table of Contents