Mitigating Error Propagation with Search and Planning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2289 papers331 conceptsfrozen 2026-10-04

In many sequential tasks—from parsing a sentence to navigating a room or solving a math problem—models must make a series of discrete decisions. The standard approach is greedy decoding: at each step, the model picks the single most likely next action and moves on.

While efficient, greedy decoding has a "glass heel." Because each decision is irreversible, a single mistake early in the sequence can lead to a "snowball effect" or error propagation. Once the model deviates from a valid path, it enters a state it never encountered during training, leading to a cascade of subsequent failures.

To solve this, researchers are moving beyond forward-only generation, instead treating sequential reasoning as a problem of search and planning.

The Greedy Trap and Exposure Bias

The fundamental problem with greedy decoding is that it lacks a mechanism for self-correction. As Kushal Arora and colleagues explain in Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation, this is often rooted in exposure bias. During training, models are usually shown "gold-standard" paths. During inference, however, they must generate from their own (potentially flawed) previous outputs.

When a model makes a sub-optimal choice, it drifts into "low-probability states." Because it wasn't trained to recover from these unfamiliar configurations, its performance degrades quadratically. This is visible in everything from repetitive text generation to the "irreversible failure" of navigation agents described by Chih-Yao Ma in The Regretful Agent: Heuristic-Aided Navigation Through Progress Estimation.

Look-Ahead: Planning the Path

One way to avoid the greedy trap is to look before you leap. Instead of committing to the immediate best step, models can use Monte-Carlo Tree Search (MCTS) or other planning algorithms to simulate potential futures.

In Faithful Question Answering with Monte-Carlo Planning, Ruixin Hong and his team treat multi-step reasoning as a discrete decision-making problem. By using MCTS to explore different reasoning paths, the model can identify which steps actually lead to a verifiable conclusion, outperforming much larger models that rely on simple generation.

Similarly, Biqing Qi proposes the Evolution of Thought (EoT) framework. EoT uses genetic algorithms to "evolve" reasoning paths, balancing quality and diversity. By exploring multiple chains of thought simultaneously, the system avoids getting stuck in the local logical errors that plague greedy reasoners.

Backtracking: The Power of Regret

If a model does make a mistake, it needs a way to turn back. This is the core intuition behind backtracking search.

In the context of Vision-Language Models, Guowei Xu and Hao Li introduced LLaVA-CoT, which employs a test-time backtracking search called SWIRES. If the model realizes a reasoning path is inconsistent, it can backtrack and revise earlier premises. This "regret" mechanism allows smaller models to match the performance of giants like GPT-4o by simply being more deliberate.

This concept is not limited to language. In A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem, Shikui Tu and Zhihao Xing show that combining the pattern recognition of GNNs with the strategic look-ahead of MCTS allows solvers to refine decisions and generalize to much larger problem sizes than they saw during training.

Training to Recover: Dynamic Oracles

While search helps at inference time, we can also change how models are trained. Traditional "static" training only teaches a model how to behave on the perfect path. Dynamic oracles teach the model how to behave even after it has made a mistake.

Miguel Ballesteros and colleagues demonstrated this in Training with Exploration Improves a Greedy Stack LSTM Parser. By allowing the parser to explore sub-optimal states during training and showing it the best way to "recover" from those states, they significantly boosted the accuracy of greedy systems.

This line of work, furthered by researchers like Giorgio Satta in An Efficient Dynamic Oracle for Unrestricted Non-Projective Parsing, provides a mathematical framework for teaching models that an initial error doesn't have to be fatal—provided they know how to find the next-best path.

Global vs. Local Optimization

The shift from greedy decoding to search-based methods is ultimately a shift from local to global optimization.

Early pioneers like Mehryar Mohri and I. Dan Melamed laid the groundwork for this by using Weighted Finite-State Transducers (WFSTs) and geometric mapping to search across all levels of representation simultaneously. As Mohri argued in Algorithms for Speech Recognition and Language Processing, achieving a globally optimal interpretation requires a method to evaluate multiple hypotheses at once, rather than relying on a sequence of high-confidence but potentially brittle local decisions.

Papers in this version

Showing 60 of 289 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 155 papers
  2. Version 1 · 2026-10-04 · 289 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_error_propagation_greedy_search_error_pr_14c4bc9e,
  title = {error propagation (greedy search error propagation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/error-propagation-greedy-search-error-propagation/rdr_14c4bc9e2f914228822a40c43f6dc5ca},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_mitigating_error_propagation_with_search_14c4bc9e_v1,
  title = {Mitigating Error Propagation with Search and Planning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mitigating-error-propagation-with-search-and-planning/rdr_14c4bc9e2f914228822a40c43f6dc5ca/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}