The Limitations of Greedy Token Selection in Sequence Generation

143 concepts131 papers1 proposal

When modern generative models—whether large language models, diffusion models, or molecular generators—produce an output, they typically do so step-by-step. At each step, the model calculates a probability distribution over a vocabulary of possible tokens and selects the candidate that looks best in the immediate moment.

This approach, known as greedy decoding, relies on a dangerous assumption: that a sequence of locally optimal choices will aggregate into a globally optimal result. In practice, maximizing immediate token confidence often leads to catastrophic global suboptimality. Because early choices tightly constrain future possibilities, myopic decoding strategies frequently trap models in logical dead ends, structural failures, and repetitive loops.

The Myopia of Step-by-Step Decisions

To understand why greedy decoding fails, consider how autoregressive generation factorizes the joint probability of a sequence. The probability of a complete sequence $X = (x_1, x_2, \dots, x_n)$ is calculated as the product of conditional probabilities:

$$P(X) = \prod_{i=1}^{n} P(x_i \mid x_1, \dots, x_{i-1})$$

Greedy decoding attempts to maximize $P(X)$ by strictly maximizing each individual term $P(x_i \mid x_{<i})$ in isolation. As Di He et al. observe in their work on Neural Machine Translation, this creates a severe "myopic bias." The model selects the next token based entirely on immediate probability, completely failing to account for how that choice will influence the grammatical structure or semantic coherence of the remaining sequence.

This short-sightedness triggers what Yichuan Mo et al. describe as "cascading errors" in Large Language Diffusion Models. An early token selection that appears highly confident locally can alter the context window in a way that prevents the model from ever reaching a coherent or correct final state. Once the model takes a wrong turn, every subsequent conditional probability distribution is skewed, forcing it to choose from an increasingly flawed set of options.

[Context] ---> Choose Max P(x_i) ---> Skewed Context ---> Cascading Errors
                  (Local Optima)                              (Global Failure)

Local Traps and Reasoning Dead Ends

The consequences of this local optimization bias manifest across diverse generation tasks. In generative retrieval systems, for example, Weizhen Qi et al. demonstrate that autoregressive models frequently fall into "local traps" when navigating massive keyword libraries (ProphetNet-Ads). If a highly relevant document happens to begin with a low-probability prefix, a greedy decoder will prune that path immediately, favoring a high-probability prefix that ultimately leads to irrelevant results.

Similarly, in multi-step reasoning and logic tasks, Jinlin Lai argues that greedy decoding routinely fails because it prioritizes immediate token probability over the global coherence of the logical chain (Quasi-random Multi-Sample Inference). When forced to make decisions token-by-token, models easily wander into reasoning dead ends. As Lei Lin et al. show, this short-term focus often causes models to become trapped in repetitive loops or local optima, preventing them from exploring alternative, accurate reasoning paths (Just Ask One More Time!).

This problem is not unique to natural language. In structure-based drug design, ZAIXI ZHANG et al. point out that constructing molecules sequentially atom-by-atom or fragment-by-fragment causes models to miss globally optimal molecular configurations (Learning Subpocket Prototypes). Early fragment choices satisfy local geometric constraints but inadvertently block the formation of high-affinity bonds later in the generation process.

Structural Dead Ends in Constrained Generation

The limitations of greedy decoding become even more acute when models must adhere to strict structural rules, such as generating JSON, code, or mathematical proofs.

In grammar-constrained decoding, the generation engine uses a set of guardrails to mask out tokens that violate syntactical rules. However, as Kanghee Park et al. explain, standard implementations still operate greedily by only validating the immediate next token (Grammar-Aligned Decoding). This creates a scenario where a model selects a token that is perfectly valid according to the grammar right now, but guarantees a structural dead end a few steps later.

Token Path:  [Valid] ---> [Valid] ---> [Valid] ---> [DEAD END: No valid next token exists]
                                                     ^ Greedy choice made here blocked all future paths

Luca Beurer-Kellner et al. detail this phenomenon in DOMINO, noting that without a mechanism to look ahead, decoding algorithms regularly reach states where no subsequent tokens can complete a valid sequence. When generating source code, this lack of foresight is particularly damaging. Lakshya A. Agrawal et al. observe that when a model selects a locally plausible identifier that violates repository-wide context, standard greedy decoders lack the backtracking mechanisms required to recover, forcing the generation to fail entirely (Monitor-Guided Decoding).

The Path to Global Optimization

To overcome these constraints, the field has increasingly shifted toward decoding strategies that incorporate global planning, lookahead mechanisms, and joint probability verification.

One prominent direction involves simulating future generation steps before committing to a token. For instance, Sanghyun Lee et al. introduce a method that evaluates the long-term impact of unmasking decisions in diffusion models by selecting paths that minimize sequence-level uncertainty (Lookahead Unmasking). Similarly, in information retrieval, Hansi Zeng et al. bypass the limitations of token-by-token pruning by using a fast, simultaneous decoding step to estimate document-level scores, ensuring that high-relevance documents are not discarded due to low-probability prefixes (Planning Ahead in Generative Retrieval).

Ultimately, these advancements demonstrate that sequence generation cannot be treated as a mere sequence of isolated, confident guesses. By moving away from myopic token selection and toward frameworks that evaluate how current choices constrain or empower future generation, researchers are building models capable of true global coherence.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_greedy_decoding_limitations_f439b0c6,
  title = {greedy decoding limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-decoding-limitations/rdr_f439b0c6fb87419f873e89b7d51026f8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_greedy_decoding_limitations_f439b0c6_v1,
  title = {greedy decoding limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/greedy-decoding-limitations/rdr_f439b0c6fb87419f873e89b7d51026f8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake