Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Contrast beam search with greedy decoding in sequence models. Greedy picks highest…

  1. User

    Contrast beam search with greedy decoding in sequence models. Greedy picks highest probability each step. Beam keeps top k sequences. Why does beam avoid local maxima but not guarantee global optimal?

  2. Assistant

    Explaining beam search vs greedy decoding

    Beam search keeps the top k partial sequences by cumulative probability at each step, exploring multiple candidates to reduce early mistakes and overcome some local maxima that greedy decoding (beam width 1) can get stuck in. However, because beam width is finite, it prunes low-scoring prefixes and thus may exclude the globally optimal sequence, making it an approximate, incomplete search heuristic rather than a guaranteed global optimizer. In both cases you are doing a left–to–right search over a tree whose branches are the vocabulary. The model assigns a score to a complete path as a product of the per‑time‑step conditionals, so the sequence with the largest per‑time‑step choices need not be the one with the largest product.

    A greedy decoder sets the beam width to one: expand one node, take the highest scoring child, and throw the rest away. If the best complete path starts with a low–scoring token, it will never be seen.

    Beam search widens that horizon. At step (t) you keep the (k) best prefixes under the cumulative score (\prod_{i\leq t}p(y_i\mid y_{<i},x)) (or sum of log‑scores), and expand all of them. That allows prefixes that are not locally best to survive long enough to pay off later, so it is less prone to the “local optimum” behaviour of the one‑step greedy rule.

    However, it is still a truncated search. With finite (k) you prune any prefix that falls out of the top (k), even if, with hindsight, it could have been extended to the globally best sequence. Only an exhaustive search over all branches would guarantee finding the global maximum; beam search is a heuristic that trades optimality for tractability.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.