Worked Example: Length 2 Decoding

Consider decoding a length 2 sequence over vocabulary {A, B} using a "Greedy trap" transition table and beam width 1.

1. At depth 0, the initial beam contains only the empty prefix "" with probability 1.
2. We expand "" to "A" and "B". The transition probabilities are:
   • P(A) = 6/10
   • P(B) = 4/10
3. With beam width 1, we retain the top 1 prefix by joint probability. Since 6/10 > 4/10, the beam becomes ["A"].
4. At depth 1, we expand "A" to "AA" and "AB". The conditional probabilities given prefix "A" are:
   • P(A | A) = 5/10
   • P(B | A) = 5/10
5. The joint probabilities are:
   • P("AA") = P("A") * P(A | A) = (6/10) * (5/10) = 30/100 = 3/10 (0.300000)
   • P("AB") = P("A") * P(B | A) = (6/10) * (5/10) = 30/100 = 3/10 (0.300000)
6. We retain the top 1 prefix. Since the probabilities are tied (3/10), we resolve lexicographically with A < B. The final beam winner is "AA" with probability 3/10.

However, the exhaustive best sequence is "BA". The joint probability of "BA" is P("B") * P(A | B) = (4/10) * (99/100) = 396/1000 = 99/250 (0.396000). Beam Search with width 1 fell into a greedy trap because it pruned the branch "B" early.

Experimenting with Beam Width

You can use the Beam Search Decoding module to verify how the beam width affects the final selected sequence.

1. Set the Beam width control to 1.
2. Set the Output length control to 2.
3. Set the Transition table control to Greedy trap.
4. Observe that the selected sequence is AA (probability 3/10), while the exhaustive best sequence is BA (probability 99/250).
5. Now, increase the Beam width control to 2.
6. Observe that the selected sequence is now BA, successfully matching the exhaustive best sequence, because the branch B was retained at the first step.

Limitations and Assumptions

This visualization uses a fixed toy conditional table without an end-of-sequence (EOS) token or length normalization. All candidate sequences share the same fixed output length, so comparing probabilities across different lengths is not necessary here. Zero-probability candidates remain in the beam when its width permits them; exact ties, including zero ties, use lexicographic order A before B. No logarithm of zero is evaluated.

In a real production language model, conditional probabilities are continuous and derived from a large neural network. Furthermore, beam search is not guaranteed to find the globally optimal sequence (as shown by the greedy trap), and a larger beam width increases the number of retained candidates. It does not guarantee globally optimal decoding or improved real-world text quality.

References and Primary Literature

This exact probabilistic path decoding strategy comes from fundamental literature on heuristic sequence generation. The following text comprehensively analyzes this heuristic sequence decoding technique.

• Dive into Deep Learning (D2L): Beam Search. This primary source chapter details the complete beam search algorithm, how probabilities multiply across steps, and its exact role in modern heuristic sequence decoding for language models.