When building complex structured outputs—such as dependency trees, coreference chains, or semantic queries—incremental, step-by-step decision-making offers an alluring benefit: speed. Instead of evaluating an exponentially large space of global configurations, a greedy model makes a sequence of local choices, committing to each token or structural arc one at a time.
However, this efficiency comes with a severe vulnerability known as sequential error propagation. In a greedy framework, decisions are irreversible. If a model makes a single incorrect choice early in a sequence, it alters the context for all subsequent steps. This initial slip frequently triggers a cascade of further mistakes, completely derailing the final output structure.
The Mechanics of the Cascade
To understand why greedy models fail so catastrophically after a single mistake, we must look at two distinct phenomena: the garden path effect and exposure bias.
The garden path effect occurs because local decisions lack a global view of the entire structure. As noted by Daniel Fernández-González et al. in Left-to-Right Dependency Parsing with Pointer Networks, a transition-based system making incremental choices cannot anticipate the final topology of the output. An early choice might look highly plausible within a narrow local window, but it can lead the model into a structural dead end. Because the system cannot backtrack, it is forced to build the remainder of the structure on top of a broken foundation. Jinho D. Choi et al. demonstrate in Transition-based Dependency Parsing with Selectional Branching that these early commitments permanently bound the maximum achievable quality of the final output.
Standard Greedy Path:
[Correct State] ──> [Mistake] ──> [Unfamiliar State] ──> [Cascading Error] ──> Failure
│
(No recovery mechanism)
This structural trap is compounded by exposure bias during training. Typically, sequential models are trained exclusively on "gold-standard" paths. When a model makes an error during inference, it enters an unfamiliar state that it has never encountered during training. As Joakim Nivre et al. explain in Training Deterministic Parsers with Non-Deterministic Oracles, the model lacks the policy necessary to recover from these out-of-distribution states. Consequently, its subsequent decisions become increasingly erratic, causing errors to snowball.
This vulnerability is not unique to syntax parsing. It appears across diverse structured prediction tasks:
- Coreference Resolution: Early incorrect links between mention pairs propagate through a document, destroying global consistency (Xiaoqiang Luo et al., A Mention-Synchronous Coreference Resolution Algorithm Based On the Bell Tree).
- Semantic Parsing (Text-to-SQL): Selecting database columns or tables incrementally without holistic schema context leads to queries that are locally plausible but globally invalid (Ben Bogin et al., Global Reasoning over Database Structures for Text-to-SQL Parsing).
- Discourse Parsing: Document-level hierarchical trees suffer massive degradation if the initial high-level rhetorical relations are misidentified (Yang Liu, Learning Contextually Informed Representations for Linear-Time Discourse Parsing).
Strategy 1: Global Optimization and Beam Search
The most direct way to mitigate error propagation is to replace local greedy choices with a global search mechanism. Instead of optimizing each step in isolation, models can optimize for the entire sequence of actions.
Yue Zhang et al. demonstrate in Analyzing the Effect of Global Learning and Beam-Search on Transition-Based Dependency Parsing that global learning and beam search are deeply synergistic. Beam search maintains a set of $K$ high-probability hypothesis paths simultaneously, preventing a single early mistake from terminating the correct path. Crucially, the authors show that this global perspective allows the model to safely employ complex, non-local features that would otherwise cause a greedy parser to overfit and fail.
Similarly, Hao Zhou et al. (A Neural Probabilistic Structured-Prediction Model for Transition-Based Dependency Parsing) utilize global normalization to score entire sequences of actions. By evaluating the complete context of the output structure, these models eliminate the local decision bias that causes greedy decoding to spiral.
Strategy 2: Dynamic Oracles (Learning to Recover)
While beam search improves accuracy, it sacrifices the linear-time processing speed of greedy decoding. An alternative approach fixes the problem during training rather than inference: teaching the greedy model how to handle its own mistakes.
Dynamic Oracle Path:
[Correct State] ──> [Mistake] ──> [Unfamiliar State] ──> [Optimal Correction] ──> Graceful Recovery
│
(Trained on error states)
This is achieved via dynamic oracles. Instead of training a model on a single static "gold path," a dynamic oracle can calculate the optimal next step from any arbitrary, corrupted state. As introduced by Joakim Nivre et al. in Training Deterministic Parsers with Non-Deterministic Oracles, this training regime exposes the model to its own errors in a controlled environment. If the model makes a mistake during a training rollout, the dynamic oracle shows it how to minimize further damage.
By learning to navigate out of error states, the model becomes robust to minor deviations during inference. Francesco Sartorio et al. expanded this concept in A Tabular Method for Dynamic Oracles in Transition-Based Parsing, proving that equipping greedy architectures with error-recovery policies allows them to retain their lightning-fast inference speeds while drastically reducing cascading failures.
Strategy 3: Multi-Stage and Iterative Refinement
A third paradigm breaks the finality of sequential decoding by introducing multiple passes or separation of concerns.
In coreference resolution, Chao Ma 0001 et al. (Prune-and-Score: Learning for Greedy Coreference Resolution) decouple the problem into a two-stage process. A pruning function first filters out highly unlikely candidate antecedents globally, and a scoring function subsequently ranks the remaining candidates. This prevents the model from getting trapped in local optima by ensuring that long-range consistency is evaluated before making greedy commitments.
For parsing, Xiaoqing Zheng introduces an iterative approach in Incremental Graph-based Neural Dependency Parsing. Rather than relying on a single, irreversible left-to-right pass, the model generates a simple, low-order initial parse and then iteratively refines it using high-order structural features. This architecture effectively bridges the gap between paradigms: it leverages the speed of incremental processing while utilizing global feedback loops to correct the errors that inevitably propagate during the initial pass.