Is beam search always better than greedy search?

[robz]

How to generate text states:

Beam search will always find an output sequence with higher probability than greedy search

It’s not clear to me why that is the case. Consider this example, comparing greedy search with beam search with beam width 2:

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!

Robby

[Jung]

I think this is an interesting adversarial case for beam-search
So I agree with you that in this case Greedy found the more probable path.

[robz]

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.

Here’s my full implementation, tested with different lengths and a few different trees: Google Colab

[Prithvi52]

Hey robz. I went through your code and your observations sounds interesting. Can we have some discussion offline?