Can Transformers Learn to Verify During Backtracking Search?

• URL: http://arxiv.org/abs/2605.22221v1
• Date: Thu, 21 May 2026 09:26:01 GMT
• Title: Can Transformers Learn to Verify During Backtracking Search?
• Abstract summary: Backtracking search underlies classical constraint solvers, planners, and theorem provers.<n>Recent transformer-based reasoning systems explore search trees over their own intermediate steps.<n>We show that decoder-only transformers trained on cumulative traces fail this requirement in two ways.
• Score: 5.709908922073304
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Backtracking search underlies classical constraint solvers, planners, and theorem provers. Recent transformer-based reasoning systems explore search trees over their own intermediate steps. A common training recipe fits an autoregressive next-token loss on offline solver traces. The model's input at each step is a cumulative trace of all prior decisions. The optimal continue-or-backtrack predictor depends only on the current search state, since two trajectories reaching the same state admit the same viable continuations. We show that decoder-only transformers trained on cumulative traces fail this requirement in two ways: the trace can scatter state features across many positions (scattered retrieval), and the predictor can condition on the trajectory rather than the state (history entanglement). We address scattered retrieval with localization, a trace-level fix that rewrites each decision block to expose state features locally. We address history entanglement with Selective State Attention (SSA), a fixed attention mask that enforces state-based decisions structurally without modifying training data, objective, or parameters. We focus on reactive verification, after propagation has exposed a contradiction. We test SSA on 3-SAT, graph coloring, Blocks World, and backtracking parsing. On same-state pairs that differ only in prior history, SSA emits identical decisions while a cumulative-trained causal baseline does not. Our contribution is a diagnostic of transformer behavior on serialized trajectory data, paired with a structural fix. Pretrained language models that search over their own reasoning steps may face the same failure. Our analysis opens up inference-time context clearing as a candidate way to apply the same isolation without retraining.

Related papers

• Iris: Climbing to the Search Frontier [21.066541702697112]
  We present Iris-mini and Iris-pro, two search agents trained at the 35B-A3B and 397B-A17B scales, together with the data pipeline and training recipe behind them.
  arXiv  Detail & Related papers  (2026-09-03T17:51:01Z)
• MNIST-PRO: MNIST is Back as a Partially Observable World for AI Agents [74.83535434786145]
  MNIST-PRO is a benchmark that isolates agentic perception by converting MNIST digit recognition into a sequential, glimpse-based search task with lookback constraints.<n>We evaluate ten multimodal models across four memory representations, including raw visual history, textual states, structured metric grid maps, and a consolidated visual canvas.
  arXiv  Detail & Related papers  (2026-08-31T16:05:39Z)
• Can We Break LLMs Out of Self-Loops? Fine-Grained Reasoning Control with Activation Steering [44.273459587532535]
  We analyze and discover latent transition dynamics in the reasoning traces from Large Language Models.<n>We show that failure trajectories get stuck in self-loops, exhausting the token budget without progress toward the final answer.<n>We propose SOPHIA: Steering Of reasoning Processes via Hidden-state Intervention and Activations.
  arXiv  Detail & Related papers  (2026-07-20T16:01:57Z)
• Data and Evaluation Closed-Loop for Model Capability Enhancement [8.245706308161504]
  We show that evaluation can be routine, auditable, and experimentally validated rather than intuitive.<n>We show that the evaluation-to-data inference can be routine, auditable, and experimentally validated rather than intuitive.
  arXiv  Detail & Related papers  (2026-06-26T14:45:57Z)
• Rethinking State Tracking in Recurrent Models Through Error Control Dynamics [26.942965240880515]
  We show that affine recurrent networks cannot correct errors along state-separating subspaces once they preserve state representations.<n>We prove that robust state tracking is determined not only by an architecture's theoretical expressivity but crucially by its error control.
  arXiv  Detail & Related papers  (2026-05-08T13:59:15Z)
• The UNDO Flip-Flop: A Controlled Probe for Reversible Semantic State Management in State Space Model [0.0]
  State space models (SSMs) have been shown to possess the theoretical capacity to model both star-free sequential tasks and bounded hierarchical structures.<n>We introduce the UNDO Flip-Flop task to fill this gap.<n>We evaluate one-layer and two-layer Mamba-2 under this framework.
  arXiv  Detail & Related papers  (2026-04-07T14:23:40Z)
• Test-Time Scaling with Diffusion Language Models via Reward-Guided Stitching [66.39914384073145]
  We propose a self-consistency framework that turns cheap diffusion-sampled reasoning into a reusable pool of step-level candidates.<n>We find that step-level recombination is most beneficial on harder problems.<n>Our training-free framework improves average accuracy by up to 2 across six math and coding tasks.
  arXiv  Detail & Related papers  (2026-02-26T11:08:39Z)
• Two failure modes of deep transformers and how to avoid them: a unified theory of signal propagation at initialisation [8.973965016201822]
  Finding the right initialisation for neural networks is crucial to ensure smooth training and good performance.<n>In transformers, the wrong initialisation can lead to one of two failure modes of self-attention layers: rank collapse, where all tokens collapse into similar representations, and entropy collapse, where highly concentrated attention scores lead to instability.<n>Here, we provide an analytical theory of signal propagation through deep transformers with self-attention, layer normalisation, skip connections and gradients.
  arXiv  Detail & Related papers  (2025-05-30T08:18:23Z)
• (How) Do Language Models Track State? [52.03388573068501]
  Transformer language models (LMs) exhibit behaviors that seem to require tracking the unobserved state of an evolving world.<n>We study state tracking in LMs trained or fine-tuned to compose permutations.<n>We show that LMs consistently learn one of two state tracking mechanisms for this task.
  arXiv  Detail & Related papers  (2025-03-04T18:31:02Z)
• Semi-DETR: Semi-Supervised Object Detection with Detection Transformers [105.45018934087076]
  We analyze the DETR-based framework on semi-supervised object detection (SSOD) We present Semi-DETR, the first transformer-based end-to-end semi-supervised object detector. Our method outperforms all state-of-the-art methods by clear margins.
  arXiv  Detail & Related papers  (2023-07-16T16:32:14Z)
• Consistent Diffusion Models: Mitigating Sampling Drift by Learning to be Consistent [97.64313409741614]
  We propose to enforce a emphconsistency property which states that predictions of the model on its own generated data are consistent across time. We show that our novel training objective yields state-of-the-art results for conditional and unconditional generation in CIFAR-10 and baseline improvements in AFHQ and FFHQ.
  arXiv  Detail & Related papers  (2023-02-17T18:45:04Z)
• Unsupervised Learning of Accurate Siamese Tracking [68.58171095173056]
  We present a novel unsupervised tracking framework, in which we can learn temporal correspondence both on the classification branch and regression branch. Our tracker outperforms preceding unsupervised methods by a substantial margin, performing on par with supervised methods on large-scale datasets such as TrackingNet and LaSOT.
  arXiv  Detail & Related papers  (2022-04-04T13:39:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.