Length Normalization and Practical Beam Search

Beam search ranks partial and completed sequences using accumulated model probabilities. A direct implementation has two important problems:

• Multiplying many probabilities can cause numerical underflow.
• Raw sequence probability tends to favor short outputs.

Log-space scoring solves the numerical problem, while length normalization reduces the undesirable preference for prematurely short sequences.

The Sequence Probability

For input \(x\) and output sequence\[ y=(y_1,y_2,\ldots,y_T), \]

an autoregressive model defines\[ P(y\mid x) = \prod_{t=1}^{T} P(y_t\mid y_{<t},x). \]

This is an application of the chain rule:\[ P(y_1,\ldots,y_T\mid x) = P(y_1\mid x) P(y_2\mid y_1,x) \cdots P(y_T\mid y_{<T},x). \]

A basic decoder attempts to find\[ y^* = \arg\max_y P(y\mid x). \]

Beam search approximates this maximization by retaining a limited number of promising prefixes.

Why Raw Probability Products Are Numerically Unstable

Each conditional probability lies in the interval\[ 0\leq P(y_t\mid y_{<t},x)\leq1. \]

In realistic vocabularies, most selected-token probabilities are substantially below 1. Multiplying many of them produces an extremely small number.

For example,\[ 0.01^{100}=10^{-200}. \]

For longer sequences or lower probabilities, the product may fall below the representable range of the floating-point format. It can then be rounded to zero.

This is called numerical underflow.

Once several candidate scores become zero, their relative ranking is lost.

Scoring in Log Space

Instead of multiplying probabilities, take their logarithms:\[ \log P(y\mid x) = \sum_{t=1}^{T} \log P(y_t\mid y_{<t},x). \]

Because the logarithm is strictly increasing,\[ \arg\max_y P(y\mid x) = \arg\max_y\log P(y\mid x). \]

Thus, log-space scoring does not change the maximizing sequence when no additional penalties are applied.

The accumulated beam score becomes\[ S(y_{1:t}) = \sum_{\tau=1}^{t} \log P(y_\tau\mid y_{<\tau},x). \]

When candidate token \(w\) extends a prefix, its score is\[ S(y_{1:t-1}\mathbin{\|}w) = S(y_{1:t-1}) + \log P(w\mid y_{<t},x). \]

Log-Probability Values Are Nonpositive

Because\[ 0<P\leq1, \]

we have\[ \log P\leq0. \]

For example:\[ \log(1)=0, \]\[ \log(0.5)\approx-0.693, \]\[ \log(0.01)\approx-4.605. \]

Every additional token normally adds another negative number. Consequently, raw accumulated log probability becomes more negative as sequence length increases.

Why Raw Scores Prefer Short Outputs

Compare two possible outputs:\[ y^{(1)} = (y_1,y_2,\text{<EOS>}) \]

and\[ y^{(2)} = (y_1,y_2,y_3,y_4,\text{<EOS>}). \]

The second output contains more probability factors:\[ P(y^{(2)}\mid x) = \prod_{t=1}^{5} P(y_t^{(2)}\mid y_{<t}^{(2)},x). \]

Even if every token is plausible, multiplying more values below 1 usually produces a smaller result.

In log space, the same effect appears because the longer output accumulates more negative terms.

This can make a decoder favor:

• Premature <EOS>
• Incomplete translations
• Missing phrases
• Overly concise outputs

The issue is not numerical underflow; it is a property of the scoring objective.

Basic Length Normalization

A simple correction divides the accumulated log probability by output length:\[ S_{\text{avg}}(y) = \frac{1}{T} \sum_{t=1}^{T} \log P(y_t\mid y_{<t},x). \]

This is the average token log probability.

It compares sequences according to how probable their tokens are on average rather than by the product of all token probabilities.

A longer sentence is no longer penalized merely because it contains more factors.

Partial Length Normalization

Full averaging may favor outputs that are too long. A more flexible score is\[ S_\alpha(y) = \frac{ \sum_{t=1}^{T} \log P(y_t\mid y_{<t},x) }{ T^\alpha }, \]

where\[ 0\leq\alpha\leq1. \]

No normalization

When\[ \alpha=0, \]

then\[ T^\alpha=1 \]

and\[ S_0(y)=\log P(y\mid x). \]

Full normalization

When\[ \alpha=1, \]

then\[ S_1(y) = \frac{1}{T}\log P(y\mid x). \]

Partial normalization

When\[ 0<\alpha<1, \]

the score lies between raw log probability and average log probability.

The value of \(\alpha\) is selected using validation performance.

Interpreting the Length Parameter

Increasing \(\alpha\) generally reduces the preference for short outputs.

Values outside the interval from 0 to 1 are mathematically possible, but they require care because they can distort length behavior substantially.

There is no universally optimal value. It depends on:

• The model
• The task
• The tokenizer
• The expected source-to-target length relationship
• Whether <EOS> is calibrated well
• Other decoding penalties

A Smoothed Length Penalty

Another common form avoids dividing directly by \(T^\alpha\):\[ \operatorname{lp}(T) = \left( \frac{k+T}{k+1} \right)^\alpha, \]

where \(k\) is a positive constant.

The score is\[ S_{\text{norm}}(y) = \frac{ \log P(y\mid x) }{ \operatorname{lp}(T) }. \]

This penalty changes more gradually near the beginning of the sequence.

Different systems use different conventions. A length-penalty value is meaningful only together with its precise formula.

Does <EOS> Count Toward Length?

A decoder must define whether\[ T \]

includes the <EOS> token.

Both choices are possible, but the convention must be consistent across:

• Candidate scoring
• Validation tuning
• Reported results
• Production decoding

Special tokens such as <BOS> are normally excluded from generated length because they are initialization symbols rather than predicted content.

When to Apply Length Normalization

There are two main approaches.

Normalize only completed hypotheses

During beam expansion, rank active prefixes by raw accumulated log probability. When a sequence reaches <EOS>, calculate its normalized final score.

This is simple, but pruning decisions are still made using a short-prefix-favoring score.

Normalize active and completed hypotheses

Apply a length-aware score during every pruning step.

This aligns intermediate pruning more closely with final ranking, but partial sequences and completed sequences may behave differently under the chosen penalty.

There is no single universally correct choice. The implementation should be documented because it can change results.

Maintaining Active and Finished Hypotheses

A robust beam-search implementation maintains two sets.

Active hypotheses

Prefixes that have not emitted <EOS> and may still be extended.

Finished hypotheses

Sequences that have emitted <EOS> and will no longer be expanded.

For each finished sequence, store:

• Token sequence
• Raw log probability
• Length
• Normalized score
• Optional coverage or constraint state

The final result is selected from the completed hypotheses according to the final scoring rule.

If no sequence finishes before the maximum length, the best active hypothesis may be returned after forced termination.

Beam Search with Length Normalization

A practical decoding loop is:

1. Encode the source.
2. Initialize the beam with <BOS> and log score 0.
3. Expand every active hypothesis.
4. Add next-token log probabilities to accumulated scores.
5. Move hypotheses ending in <EOS> to the finished set.
6. Rank active candidates and retain the best \(B\).
7. Continue until the stopping rule is satisfied.
8. Rank finished hypotheses using the normalized score.
9. Return the best completed sequence.

The score for a completed sequence may be\[ S_{\text{final}}(y) = \frac{ S_{\text{raw}}(y) }{ T^\alpha }. \]

Simplified Scoring Code

def normalized_score(
    log_probability,
    length,
    alpha
):
    effective_length = max(length, 1)

    return (
        log_probability
        / (effective_length ** alpha)
    )

def normalized_score(
    log_probability,
    length,
    alpha
):
    effective_length = max(length, 1)

    return (
        log_probability
        / (effective_length ** alpha)
    )

Because log probabilities are usually negative, dividing by a number larger than 1 makes the result less negative. This compensates for the accumulation of negative terms.

Batched Beam Expansion

Suppose there are \(B\) active hypotheses and vocabulary size \(V\).

The decoder produces log probabilities\[ L\in\mathbb{R}^{B\times V}. \]

Let the accumulated beam scores be\[ s\in\mathbb{R}^{B}. \]

Candidate raw scores are\[ C_{b,v} = s_b+L_{b,v}. \]

These form \(BV\) possible extensions. The decoder selects the top candidates globally, records their parent beams, and reorders the model state accordingly.

Only \(B\) decoder states are processed, not \(BV\) separate model instances.

Selecting the Beam Width

The beam width \(B\) controls the search–cost trade-off.

Small beam

Advantages:

• Faster decoding
• Lower memory use
• Lower latency
• Simpler state management

Disadvantages:

• More aggressive pruning
• Greater risk of discarding a good prefix
• Results closer to greedy search

Large beam

Advantages:

• Explores more alternatives
• Reduces some search errors
• Can find higher-scoring hypotheses

Disadvantages:

• Higher computation
• Greater memory use
• Increased latency
• Diminishing returns
• Potentially stronger exposure to model-scoring flaws

Beam width should be tuned rather than chosen by convention.

Beam Width Does Not Guarantee Better Quality

As \(B\) increases, beam search generally becomes better at optimizing its decoding score. However, that score may not perfectly represent translation or transcription quality.

A larger beam may expose problems such as:

• Preference for short outputs
• Repetition
• Generic phrasing
• Omitted source content
• Overconfidence in <EOS>
• Poorly calibrated probabilities

This means that a larger beam can sometimes improve model score while worsening human evaluation or task metrics.

Search quality and model quality are different.

Diminishing Returns

The largest improvement often occurs when moving from greedy search to a small beam.

Increasing the beam further may produce progressively smaller gains because:

• The most useful alternatives are already preserved.
• Additional hypotheses are minor variations.
• Model error becomes more important than search error.
• Hardware and memory costs continue increasing.

A suitable beam is the smallest one that provides adequate quality for the application’s latency and memory requirements.

Maximum Output Length

Beam search needs a hard maximum length:\[ T\leq T_{\max}. \]

This prevents infinite or excessively long generation when <EOS> is not produced.

For translation, \(T_{\max}\) may depend on source length:\[ T_{\max} = \lfloor rT_x+c \rfloor, \]

where \(r\) and \(c\) are selected constants.

A fixed maximum may be sufficient when input lengths are tightly bounded.

Minimum Output Length

The decoder can also prohibit <EOS> before a minimum length:\[ T\geq T_{\min}. \]

Before \(T_{\min}\), the log probability of <EOS> can be set to negative infinity.

This prevents clearly premature termination, but an excessive minimum can force unnecessary or fabricated content.

Early Stopping

Stopping as soon as the first completed hypothesis appears is generally unsafe. An unfinished prefix may later produce a better normalized sequence.

A stronger stopping rule compares:

• The best finished score
• An upper bound on what active hypotheses could achieve

If no active hypothesis can outperform the best finished sequence, search can stop safely under the chosen scoring assumptions.

Exact upper bounds become more complicated when using length normalization, coverage rewards, or other nonmonotonic score adjustments.

Coverage Penalties

Length normalization addresses sequence length but does not ensure that all source content is represented.

An attention-based model may ignore part of the input. A coverage score can encourage broader source attention:\[ S(y,x) = S_{\text{norm}}(y) + \beta C(y,x). \]

The coverage term may reward attention distributed over source positions or penalize insufficient coverage.

Coverage penalties must be tuned carefully because attention weights are not always faithful explanations of content use.

Repetition Penalties

Sequence models can repeat words or phrases. A decoding score may include penalties for:

• Repeating an \(n\)-gram
• Reusing a token too frequently
• Repeatedly attending to the same source region
• Generating loops

Hard repetition constraints can prevent exact duplicates but may also suppress legitimate repetition.

Search and Model Error

Suppose a system produces \(\hat{y}\), while a better reference or candidate is \(y^*\).

Compare their model scores.

Search error

If\[ P(y^*\mid x) > P(\hat{y}\mid x), \]

then the search failed to find a sequence the model itself prefers.

Possible responses include:

• Increasing beam width
• Correcting state bookkeeping
• Improving pruning
• Fixing length normalization
• Revising stopping rules

Model error

If\[ P(y^*\mid x) \leq P(\hat{y}\mid x), \]

then the model prefers the worse output.

Increasing the beam width is unlikely to solve this. The model, data, objective, or calibration needs improvement.

Comparison with Breadth-First Search

Beam search resembles breadth-first exploration because it advances level by level through sequence length. However, it prunes nearly all nodes at every level.

Breadth-first search retains every node at the current depth and can be exact under suitable conditions. Beam search retains only \(B\) hypotheses and is therefore approximate.

Once a hypothesis is removed from the beam, it cannot return.

Common Mistakes

Multiplying probabilities directly

Use accumulated log probabilities to prevent underflow.

Saying log probabilities are less than or equal to 1

For valid probabilities,\[ \log P\leq0. \]

Comparing raw scores across different lengths

This often creates a strong preference for short sequences.

Assuming length normalization is theoretically neutral

It changes the decoding objective and may change which sequence is selected.

Keeping finished hypotheses in the active beam

Completed sequences should normally be stored separately rather than repeatedly expanded.

Retaining \(B\) candidates for every parent

The search must choose the top \(B\) candidates globally across all parent-token combinations.

Stopping after the first <EOS>

A later completed hypothesis may receive a better final score.

Increasing beam width without diagnosis

A wider beam helps search errors, not model-ranking errors.

Key Takeaway

Beam search should accumulate scores in log space:\[ \log P(y\mid x) = \sum_{t=1}^{T} \log P(y_t\mid y_{<t},x), \]

which prevents numerical underflow while preserving the raw probability ranking.

Because accumulated log probability tends to favor short outputs, practical decoders often apply length normalization:\[ S_\alpha(y) = \frac{ \log P(y\mid x) }{ T^\alpha }. \]

The parameter \(\alpha\) controls the trade-off between no normalization and full average log probability.

Beam width controls a separate trade-off: larger beams explore more hypotheses but require more computation and may expose weaknesses in the model’s scoring function. A reliable implementation must jointly manage log-space scores, length penalties, finished hypotheses, stopping rules, decoder-state reordering, and realistic validation metrics.