Internalizing Search for Deliberate Reasoning

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 131 papers43 conceptsfrozen 2026-10-04

Standard Large Language Models (LLMs) operate on a "System 1" principle: they generate text through fast, associative next-token prediction. While effective for prose, this approach fails in complex planning and reasoning tasks because the model cannot "undo" a mistake once a token is generated. To solve this, a new research direction focuses on moving search and planning from external scaffolds into the model's internal weights and token streams.

The Problem of Linear Commitment

In traditional autoregressive generation, the model is locked into a single path. If it makes a logical error at step two, it has no native mechanism to "backtrack" and try a different branch. Early attempts to fix this, such as "Tree of Thoughts," used external scripts to call the LLM multiple times, managing a search tree outside the model.

However, researchers like Bilgehan Sel and Ahmad Al-Tawaha argue in Algorithm of Thoughts that this is inefficient. They propose that models can internalize search algorithms—like depth-first search—directly within their context window. By providing in-context examples of algorithmic reasoning, the model learns to explore multiple solution paths and backtrack autonomously within a single inference pass.

Linearizing the Search Tree

The core mechanism for internalizing search is the linearized search trace. Instead of training a model only on the "happy path" (the final correct answer), researchers are training models on the entire "messy middle" of the search process.

In Stream of Search (SoS), Kanishk Gandhi and colleagues demonstrate that representing search trees as flattened text sequences—complete with state transitions, goal checks, and backtracking operations—allows standard models to learn algorithmic behaviors. Similarly, Lucas Lehnert and the team at Meta developed Searchformer, which trains Transformers to predict the full execution trace of the A* algorithm. By learning the "thinking process" rather than just the solution, these models can eventually find optimal plans using fewer steps than the symbolic algorithms they were meant to imitate.

Learning from Failure

A recurring insight across this field is that failure is a prerequisite for robust reasoning. If a model only sees perfect solutions, it never learns how to recover from a dead end.

  • Trial-and-Error Data: Chenyang An and Zhibo Chen show in Learn from Failure that fine-tuning LLMs on trial-and-error data allows them to generate their own backtracking commands.
  • Tree-Structured Modeling: Doyoung Kim introduces TSLM, which teaches models to natively generate and explore complete search trees. By internalizing the topology of the search space, the model learns the logic of backtracking as a native linguistic pattern.
  • Self-Correction: In the context of board games, John Schultz and Jakub Adamek demonstrate in Mastering Board Games by External and Internal Planning that fine-tuning on minimax search traces allows a model to simulate future trajectories and change its initial move preference after "thinking" through the consequences in its context window.

Scaling Test-Time Compute

This shift toward internalization is the engine behind "Large Reasoning Models" like OpenAI’s o1 and Kimi k1.5. As Karthik Valmeekam notes in his evaluation of o1 on PlanBench, these models use "test-time compute"—spending more tokens to "think" before committing to an answer.

Frameworks like ASTRO by Joongwon Kim and Satori by Maohao Shen formalize this by training models to reflect and backtrack in-context. Rather than relying on an external verifier, the model internalizes the verification process. This allows a single model to allocate more compute to difficult problems by naturally extending its reasoning chain through self-directed exploration.

Why It Works: The Intuition

The intuition behind internalizing search is that reasoning is a path-finding problem in a latent space. By training on search traces, we are teaching the model the "map" of the problem space.

When a model internalizes search, it stops being a simple "stochastic parrot" and starts acting as a world model and search engine combined. It uses its parameters to propose a step, its internal "value function" to critique it, and its learned "search policy" to decide whether to continue or backtrack. As Xiaowen Yang suggests in Step Back to Leap Forward, this process eventually allows models to "distill" slow, deliberate search-based thinking into fast, intuitive responses, effectively upgrading the model's baseline intelligence.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_internalizing_search_for_deliberate_reas_7bfb2bc1,
  title = {Internalizing Search for Deliberate Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/internalizing-search-for-deliberate-reasoning/rdr_7bfb2bc139af4c4a8bf751ea2fe1cce6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-18},
}

This exact version (version 1, frozen text):

@misc{lacuna_internalizing_search_for_deliberate_reas_7bfb2bc1_v1,
  title = {Internalizing Search for Deliberate Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/internalizing-search-for-deliberate-reasoning/rdr_7bfb2bc139af4c4a8bf751ea2fe1cce6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-18},
}