Control Beam Search Length Bias with Score Normalization

Beam search usually ranks partial sequences by accumulated token log probability. That score has a built-in dependence on sequence length: each additional token contributes another log probability that is zero or negative. As a result, raw cumulative scores can favor shorter completed sequences even when a longer candidate is preferable for the application.

Length normalization changes the ranking rule rather than the model distribution. The distinction matters because decoding can produce different outputs without changing a single model parameter or next-token probability.

Cumulative log probability carries a length effect

For a generated sequence y_1, ..., y_L conditioned on input x, an autoregressive model assigns:

log P(y | x) = sum_(t=1)^L log P(y_t | y_<t, x)

Every token probability lies between zero and one, so each finite log probability is at most zero. Extending a sequence therefore cannot increase its raw cumulative log probability.

Consider two completed candidates:

A: -0.4 + -0.5             = -0.9
B: -0.2 + -0.2 + -0.2 + -0.2 = -0.8

Under raw sequence probability, B ranks above A because -0.8 is greater than -0.9. But adding another token with log probability -0.3 changes B to -1.1, placing it below A. The comparison reflects both token quality and the number of factors multiplied into the sequence probability.

This is mathematically consistent with the autoregressive probability model. It becomes a decoding concern when the desired output length is not represented well by direct comparison of completed sequence probabilities.

Normalization changes the ranking objective

A simple length-normalized score divides cumulative log probability by sequence length:

score(y) = log P(y | x) / L

This is the average token log probability. It removes the direct accumulation of one negative term per token, but it also defines a different ranking objective from raw sequence probability.

A more general form uses an exponent:

score(y) = log P(y | x) / L^alpha

With alpha = 0, the rule reduces to raw cumulative log probability. Increasing alpha gives sequence length more influence in the denominator and can make longer candidates more competitive.

Some decoding systems use other penalty functions, including shifted or bounded functions of length. Those formulas are not interchangeable. A parameter value only has meaning together with the exact scoring equation and the point at which that equation is applied.

The end token participates in the competition

Sequence length is tied to the model’s end-of-sequence decision. A beam that emits the end token becomes a completed candidate, while another beam continues accumulating token scores.

If completed and unfinished candidates are compared using raw cumulative scores, an early end token can create a short candidate with a favorable score. Length normalization can alter that competition by changing how completed hypotheses of different sizes are ranked.

The end token itself is still a model prediction. Normalization does not modify its conditional probability unless the implementation explicitly adjusts token logits. It changes the score used by the search procedure to retain or select hypotheses.

This separation helps diagnose short-output behavior. A model may assign excessive probability to ending early, or a decoder may amplify a milder model preference through its sequence scoring rule. Those are different mechanisms and call for different changes.

Applying the score only at the end is not equivalent

Beam search prunes candidates during generation. If length normalization is used only for final reranking, candidates that would have scored well under the normalized objective may already have been removed.

Suppose a beam width of two retains only the two highest raw cumulative scores at each position. A longer prefix with a lower raw score can be discarded before its eventual normalized score becomes competitive. Final normalization cannot recover that prefix.

Applying a length-aware score during beam maintenance changes which prefixes survive. Applying it only after completion changes only the ordering among candidates that survived under another rule.

Implementations therefore need to specify at least two details: the formula used for sequence scoring and the stages of search at which that formula affects pruning. Matching a parameter name without matching these semantics can produce different outputs.

Partial and completed hypotheses need compatible treatment

A partial sequence has an unknown final length. Normalizing it by its current length is simple, but that score may not be directly comparable with a completed candidate if the partial sequence is expected to grow.

Some decoders keep active and completed hypotheses in separate sets. Others compare them using bounds or heuristic scores. Early stopping rules can also depend on whether any unfinished beam could still surpass the current completed candidates.

These details interact with length penalties. A decoder that stops as soon as enough completed candidates exist can terminate differently from one that waits until active beams cannot overtake the best completed score.

There is no universal length-normalization rule that makes every stopping policy equivalent. The scoring and termination logic form one decoding algorithm and should be evaluated together.

Tokenization changes the unit called length

A token count is not a character count or a word count. Two text strings with similar visible size can contain different numbers of tokens, and different tokenizers can segment the same text differently.

A penalty based on generated token count therefore depends on the tokenizer. Moving the same conceptual decoding rule to a model with another vocabulary can change its practical effect even when alpha remains unchanged.

Special tokens require an explicit convention as well. An implementation may count or exclude beginning, end, padding, or prompt tokens when computing generated length. The chosen convention changes the denominator and can matter most for short outputs.

For reproducible decoding, the length definition belongs beside the score formula rather than being left implicit.

Normalization does not fix model probability errors

Length normalization can compensate for a mismatch between raw sequence scoring and an application’s preferred output lengths. It does not make token probabilities better calibrated, improve factual content, or correct an end token that receives inappropriate probability from the model.

A strong penalty can also push the decoder toward longer text even when the extra tokens add little value. The resulting output may score higher under the decoding rule while having lower task utility.

That makes the penalty a search hyperparameter, not a general correction to the probability model. Its useful value depends on the task, output format, tokenizer, beam width, stopping rule, and scoring equation.

Evaluation should therefore inspect both task quality and output-length behavior. If a change in alpha improves a task metric only by shifting the length distribution, that mechanism is worth making explicit.

Score definitions belong in decoding specifications

A beam width alone does not fully specify beam search. Sequence scoring, length treatment, end-token handling, pruning, and stopping criteria can each alter the selected output.

For developers comparing inference libraries or reproducing a model setup, recording the exact length-normalization equation is more useful than recording a generic length_penalty label. The same label can represent different formulas across implementations.

The practical boundary is that length normalization controls how the decoder compares hypotheses; it does not rewrite the probabilities produced by the model. Keeping those layers separate makes changes in output behavior easier to attribute and evaluate.