By the 3rd step, beam search with beam width 2 has found two sequences BFI and BGK, each with probability .49*.5*.51 = 0.12495, but greedy search found ADH, with probability .51*.4*.99 = 0.20196

Exploring more of the tree may cause beam search to get stuck on paths that seem more promising at first, but end up with lower probability than the greedy path. Is this right, or have I misunderstood how beam search works?

Thanks for your response Jung. This is not quite an adversarial example – I discovered a very similar one “in the wild” while analyzing my own implementation of beam search.

Since I’ve heard that increasing the beam width increases the probability of the best path, I attempted to test my implementation with that idea. If my implementation was correct, then it should show path probability monotonically increasing with beam width when searching through any random tree.

But instead I found that there is often dips in the path probabilities as beam width increases, especially for longer paths.