Greedy decoding and beam search

Greedy decoding picks the most likely token at each step. It amounts to setting the temperature to zero and always yields the same output for the same input (Alammar & Grootendorst, 2024, pp. 79–80). Its flaw is short-sightedness: the best choice at each step is not the best overall. An example with made-up probabilities:

first step: "the" 0.5 · "once" 0.4 after "the": "house" 0.4 (the rest spread out) → "the house": 0.5 × 0.4 = 0.20 after "once": "upon" 0.9 → "once upon": 0.4 × 0.9 = 0.36

Greedy decoding commits to "the" and never sees the more likely sequence. Beam search keeps the k best partial sequences in parallel (the beam width), extends them all, and again keeps the k best. With k = 2 it finds "once upon."

Beam search was the standard in neural machine translation: Sutskever et al. (2014) found that a beam of size 2 already gave most of the benefit (2014, sec. 3.2), and the original Transformer used a beam of 4 with a length penalty (Vaswani et al., 2017, sec. 6.1), as did GPT-3 on free-form tasks (Brown et al., 2020, sec. 2.4). In conversation and open-ended writing, however, searching for the most likely sequence produces bland, repetitive text, which is why sampling is preferred (Holtzman et al., 2020).

For a psycholinguist, greedy short-sightedness has a name: garden-path sentences, such as Bever's (1970) classic "The horse raced past the barn fell," where the reader commits to the most likely parse and has to backtrack. An autoregressive model cannot backtrack: what is written stays written. Beam search is a limited way of keeping several readings open at once.