Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning

# Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning
Source: [https://arxiv.org/html/2607.07492](https://arxiv.org/html/2607.07492)
Dmitry Beresnev1,3Vladimir Makharev1,2Roman Khalikov3 Ivan Oseledets2Petr Anokhin2,3 1Innopolis University, Innopolis, Russia2AXXX, Moscow, Russia 3Lomonosov Moscow State University, Moscow, Russia d\.beresnev\.work@gmail\.com

###### Abstract

Many reasoning tasks are not well described by a single left\-to\-right chain: a solver may need to pursue a plausible branch, observe delayed failure, and return to the latest prefix that can still be completed\. We introduce Pyligent, a training and inference framework inspired by the Diligent Learner formulation that represents reasoning as validated search over partial solution chains\. A task validator labels generated continuations and failures, and the resulting search trees are converted into supervised targets for three actions: continue, finish, and backtrack, with optional traces that summarize abandoned branches\. We evaluate Pyligent on a hidden directed graph task designed to isolate delayed\-failure recovery, and on structured reasoning domains with exact validators, including4×44\{\\times\}4Sudoku, Sudoku with reasoning traces, and Blocksworld\. Compared with gold\-only supervised fine\-tuning, Pyligent improves solve rate by72\.772\.7percentage points on hidden graphs, by1717and1818points on mixed and expert Sudoku, by2727and1414points on mixed and expert Sudoku with reasoning traces, and by1313points on Blocksworld\. These results suggest that explicit failed\-branch supervision can teach useful recovery behavior beyond imitation of polished solution chains\.

## 1Introduction

Reasoning is often presented as a linear chain of intermediate steps, but many hard tasks are not naturally linear\. A solver may need to try a plausible direction, discover only later that the branch cannot lead to a solution, and return to the decision point where another continuation is possible\. Standard chain\-of\-thought supervision hides this process: training data usually contains the polished successful path, not the failed attempts and recoveries that produced it\.

\(Shalev\-Shwartz and Shashua,[2025](https://arxiv.org/html/2607.07492#bib.bib15)\)formalize this view in the Diligent Learner method\. Their theory separates the ability to*search*for a solution from the ability to*validate*a proposed reasoning chain, and argues that validation is often much easier than generation\. The central sufficient conditions are correspondingly behavioral rather than token\-level: a learner should generate a correct next reasoning step with fixed nonzero probability, and when a branch is revealed to be wrong, it should learn to backtrack to the latest prefix that can still be completed\. Their constructive proof shows that, under these assumptions, a depth\-first search procedure with learned backtracking can avoid the exponential blowups that affect naive search, Tree\-of\-Thoughts\-style branching, and pure gold\-path imitation\.

This paper studies the practical question left open by that theory: can we turn these conditions into an implementable training pipeline for contemporary, relatively small LLMs? We introduce Pyligent, a framework that represents reasoning as a tree of partial chains, uses a task validator to label generated continuations, and converts both successful and failed branches into supervised training examples\. The resulting action space contains ordinary continuation and termination actions, plus explicit<backtrack\>actions for recovery\.

Pyligent instantiates the validator assumed by the theory with task\-specific checkers, use it to label both successful continuations and failed leaves, and train models on three corresponding action types: continue, finish, and backtrack\. The resulting experiments operationalize the Diligent Learner conditions in contemporary LLM training, and our backtrack categories measure whether generated recoveries return to repairable prefixes rather than merely matching the syntax of a recovery action\.

Our most controlled test is the hidden directed graph task\. The model only observes outgoing moves from the current node, so a locally legal action may later reveal a dead end or a failure state\. Solving the task therefore requires trying next actions, identifying mistakes from delayed feedback, and returning to the relevant earlier choice point\. We use this task to measure whether recovery can be learned directly, and then study how Pyligent transfers to more structured reasoning domains such as Sudoku and Blocksworld\.

## 2Related work

Chain\-of\-thought \(CoT\) prompting\(Weiet al\.,[2022](https://arxiv.org/html/2607.07492#bib.bib19)\)showed that exposing intermediate reasoning steps can substantially improve LLM performance on arithmetic, commonsense, and symbolic tasks\. Most CoT supervision, however, presents only the successful trajectory: a solution is generated left\-to\-right, and failed branches are usually absent from the training signal\. This makes CoT a useful representation of reasoning, but not by itself a training procedure for learning when to abandon an unproductive branch and resume from an earlier state\.

Several lines of work address this limitation by adding search, critique, or revision around the model\. Tree\-of\-Thoughts\(Yaoet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib21)\)and MCTS\-based methods such as Reasoning\-via\-Planning\(Haoet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib5)\)and AlphaLLM\(Tianet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib18)\)externalize exploration into an explicit inference\-time tree, using model\- or discriminator\-based evaluations to select promising continuations\. Prompting\-level refinement methods, including Self\-Refine\(Madaanet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib11)\), Reflexion\(Shinnet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib16)\), and CRITIC\(Gouet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib2)\), instead keep the interaction in context by alternating generation with feedback or critique\. These methods demonstrate that reasoning often benefits from non\-linear exploration, especially when reliable feedback is available\(Huanget al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib6); Kamoiet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib7)\)\.

A complementary direction trains models directly on search\-like traces\. Stream of Search\(Gandhiet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib3)\)serializes DFS and BFS trajectories; Searchformer\(Lehnertet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib10)\)and DualFormer\(Suet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib17)\)distill planner traces into transformer models; Self\-Backtracking\(Yanget al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib20)\)introduces explicit<backtrack\>actions; and ASTRO\(Kimet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib24)\)turns MCTS rollouts into reasoning traces that include reflection and recovery\. Larger\-scale correction policies have also been trained with reinforcement learning, including SCoRe\(Kumaret al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib9)\), RISE\(Quet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib12)\), DeepSeek\-R1\(DeepSeek\-AIet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib4)\), and Kimi k1\.5\(Teamet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib8)\)\. Our work follows this broad search\-training view, but focuses on a specific source of supervision: failed branches produced by a task validator and converted into explicit recovery examples\.

Recent empirical studies help explain why this supervision matters\.\(Gandhiet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib27)\)find that the structure of search traces can be more important than final\-answer labels for eliciting verification and backtracking behaviors\. At the same time, backtracking is not universally helpful in every domain or at every frequency:\(Qinet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib13)\)and\(Caiet al\.,[2025](https://arxiv.org/html/2607.07492#bib.bib23)\)show that the usefulness of backtracking depends strongly on task structure and training distribution\. These observations motivate our ablations over trace use, exploration policy, and failed\-branch weighting\.

The closest conceptual foundation for our work is the Diligent Learner method of\(Shalev\-Shwartz and Shashua,[2025](https://arxiv.org/html/2607.07492#bib.bib15)\)\. Their theory separates generation from validation and gives sufficient conditions for CoT learnability in terms of two behavioral capabilities: the model should generate a valid next semantic step with nonzero probability, and when a branch is found to be incorrect, it should backtrack toβ​\(c\)\\beta\(c\), the maximal prefix that can still be completed\. Their analysis further shows why the target of a backtrack matters: returning only to the immediate parent can be insufficient when a whole sub\-branch is invalid, while overshooting can discard useful progress\.

## 3Framework methodology

Pyligent turns chain\-of\-thought generation into a validated search over partial solution chains \([Figure˜1](https://arxiv.org/html/2607.07492#S3.F1)\)\. Instead of training only on polished gold trajectories, it records successful continuations and failed branches, then converts them into supervised examples for continuing, terminating, and recovering\. In the language of\(Shalev\-Shwartz and Shashua,[2025](https://arxiv.org/html/2607.07492#bib.bib15)\), the solver supplies approximate next\-step generation and the task validator supplies retrospective correctness labels\.

![Refer to caption](https://arxiv.org/html/2607.07492v1/x1.png)Figure 1:The Pyligent framework\. The pipeline iterates fort=1,…,Tmaxt=1,\\ldots,T\_\{\\max\}rounds, alternating between fine\-tuning on teacher\-generated gold chains \(SFT\-A\) and exploration\-driven fine\-tuning on*ChainTree*\-structured trajectories containing successful, backtracked, and traced paths \(SFT\-B\)\.### 3\.1Representation and components

For each problem instance, we maintain a tree of partial reasoning states\. A state is a prefix

ct=\(a0,a1,…,at\),c\_\{t\}=\(a\_\{0\},a\_\{1\},\\ldots,a\_\{t\}\),where each action uses a restricted markup vocabulary:

<node\>ID CONTENT</node\>,<done\>ANSWER</done\>,<backtrack\>ID REASON</backtrack\>\.\\texttt\{<node\>ID CONTENT</node\>\},\\quad\\texttt\{<done\>ANSWER</done\>\},\\quad\\texttt\{<backtrack\>ID REASON</backtrack\>\}\.
Here<node\>appends one intermediate step,<done\>proposes a final answer, and<backtrack\>returns control to an earlier node\. The explicit node identifiers make branch structure visible to both the data\-generation pipeline and the inference runtime\.

The framework has four components\. The*solver*is the trainable language model, which emits one action at a time\. The*explorer*selects prefixes from which the solver should sample continuations and controls how much breadth or depth to allocate\. The*validator*checks whether each proposed action is legal for the task state\. The*ChainTree*stores accepted and rejected branches, assigns backtrack targets for failed branches, and converts the resulting search tree into prefix\-to\-action training examples\. We use linear and dendritic explorers in the experiments; the former keeps cost predictable by extending a bounded number of parallel chains, while the latter starts broad and then concentrates budget on deeper continuations\. Full explorer definitions are given in[Section˜8\.1](https://arxiv.org/html/2607.07492#S8.SS1)\.

### 3\.2Training pipeline

Training proceeds in three stages\. First, SFT\-A trains the solver on gold solution chains, teaching the action format and giving the model a nonzero chance of proposing valid next steps\. Second, validator\-guided exploration runs the solver from selected prefixes and records both valid continuations and failed branches\. Third, SFT\-B fine\-tunes on the examples constructed from the resulting ChainTree\.

SFT\-B contains success pairs, failure pairs, and, for traced recovery, continuation\-after\-trace pairs\. Success pairs train the model to extend valid generated or gold branches\. Failure pairs train the model to emit a<backtrack\>action when a branch violates task constraints\. For a failed branch that diverges after nodeiiand reaches invalid leafjj, ChainTree creates the target

cj↦<backtrack\>​i​r​</backtrack\>,c\_\{j\}\\mapsto\\texttt\{<backtrack\>\}i~r\\texttt\{</backtrack\>\},whererris a validator\-derived reason\. We use a reverse curriculum over prefixes: exploration starts near the end of a gold chain, where the remaining continuation is short, and later moves toward the root so that the solver must handle longer recovery\-aware trajectories\. Pair construction and curriculum details are shown in[Section˜8\.2](https://arxiv.org/html/2607.07492#S8.SS2)\.

### 3\.3Inference and traced recovery

At inference time, the solver generates one action at a time\. A<node\>action is appended to the current chain, a<done\>action terminates with the proposed answer, and a<backtrack\>action is checked for a valid target before the runtime truncates the context to that node\. Inference stops when the solver emits<done\>or exhausts a fixed step budget\.

Plain backtracking removes the failed branch from context, which can lead the solver to repeat the same mistake\. To preserve compact failure information, traced recovery inserts a runtime\-generated<trace\>after truncation\. The trace records the validator reason and a short summary of the abandoned branch; it is never a model target\. During SFT\-B we inject synthetic traces for matching failure examples, producing continuation pairs that teach the model how to resume after recovery\. The exact trace format is given in[Section˜8\.3](https://arxiv.org/html/2607.07492#S8.SS3)\.

## 4Tasks methodology

### 4\.1Hidden directed graph task

The hidden directed graph task is a controlled benchmark for testing whether a solver has learned an effective search and backtrack policy\. Each instance is a directed graph with distinguished nodesSTART,GOAL, andFAIL\. The model must find a path fromSTARTtoGOALwhile avoidingFAIL, but it only observes the outgoing moves from its current node\. After the model chooses a legal non\-terminal move, the environment reveals the outgoing moves from the newly reached node as the next observation\. This makes the task useful for evaluating Pyligent under the Diligent Learner assumptions: the model cannot solve by copying a static problem description, and a locally valid move can still expose a branch that must be abandoned\.

This task is intentionally close to the search\-theoretic examples in\(Shalev\-Shwartz and Shashua,[2025](https://arxiv.org/html/2607.07492#bib.bib15)\)\. The difficulty is not parsing the local action format: from any visible node, choosing an outgoing edge is easy to validate\. The difficulty is that a locally valid edge can be globally wrong, and the evidence for that mistake may appear only several moves later\. A successful solver must therefore learn to propose plausible moves under partial information and, once a dead end orFAILnode is revealed, return to the latest useful choice point\.

Formally, an instance is a directed graphG=\(V,E\)G=\(V,E\)with start nodess, goal nodegg, and forbidden failure nodedd\. At steptt, the environment state is the explored pathpt=\(s,v1,…,vt\)p\_\{t\}=\(s,v\_\{1\},\\ldots,v\_\{t\}\), but the model\-facing observation exposes only the outgoing neighborsO​\(vt\)=\{u:\(vt,u\)∈E\}O\(v\_\{t\}\)=\\\{u:\(v\_\{t\},u\)\\in E\\\}\. The solver must choose a visible neighbor, terminate when the goal is visible, or backtrack when the current branch is invalid or revealed to be unsolvable\.

STARTAB×\\timesCDFAILGOALfail branchno movesbacktrackbacktrackInitial observation Visible moves: START \-\> A, B The model sees only choices fromSTART\.Model action <node\>MOVE B</node\>Environment reveal <obs\>B \-\> C, D</obs\> The new node’s outgoing moves enter context\.Recovery signal IfC \-\> FAILis revealed, the target is <backtrack\>1 Failure reached</backtrack\>\.

Figure 2:Hidden directed graph interaction\. The environment contains a full graph, but the prompt exposes only the current node’s outgoing moves\. Accepted moves reveal a new<obs\>line; branches that revealFAILor no outgoing moves become supervised backtrack examples\.The model\-facing action space is deliberately small, so task performance mostly reflects search decisions rather than output\-format complexity\. A non\-terminal move is written as<node\>MOVE X</node\>, a terminal answer as<done\>START \-\> \.\.\. \-\> GOAL</done\>, and recovery as<backtrack\>ID REASON</backtrack\>\. Accepted moves reveal a new observation, rendered separately as<obs\>\.\.\.</obs\>, so the target action remains the decision rather than asking the model to hallucinate hidden graph structure\.

The validator is exact and enforces local visibility, terminal\-action consistency, and recovery from revealed dead ends\. Thus the task separates two questions cleanly: whether the model can choose plausible visible moves, and whether it can return to the appropriate earlier choice point after a locally valid branch becomes impossible\. All hidden directed graph experiments use Qwen3\-0\.6B and 300 training examples; full validation rules are given in[Section˜8\.5](https://arxiv.org/html/2607.07492#S8.SS5)\.

### 4\.2Sudoku 4x4 task

We instantiate Pyligent on4×44\{\\times\}4Sudoku\. The grid contains digits11–44, empty cells are rendered as\_, and the four2×22\{\\times\}2boxes are separated in the text representation\. Each row, column, and box must contain each digit exactly once in a completed solution\. The task is small enough to permit exact validation, but still exposes the failure mode targeted by the Diligent Learner theory: a locally plausible fill can make a later branch invalid unless the model can return to an earlier state\.

#### 4\.2\.1Gold chains and validation

Each Sudoku action contains a complete grid rather than a coordinate\-level edit, and the solver emits exactly one<node\>,<done\>, or<backtrack\>tag per turn\. The full action format is given in[Section˜8\.5](https://arxiv.org/html/2607.07492#S8.SS5)\.

Gold chains are stepwise grid completions\.[Figure˜7](https://arxiv.org/html/2607.07492#S8.F7)\(green arrows\) shows a representative path: the initial puzzle is node 0 and each subsequent node fills exactly one cell\. The terminal<done\>action must repeat the completed grid\. Invalid generated branches are converted into backtrack targets rather than being discarded \([Figure˜7](https://arxiv.org/html/2607.07492#S8.F7), red arrows\); their validator reasons become the natural\-language reason field in backtrack targets and, in traced mode, the reason field inside the injected trace\.[Section˜8\.5](https://arxiv.org/html/2607.07492#S8.SS5)gives the exact Sudoku validation rules\.

#### 4\.2\.2Experimental setup

We evaluate two4×44\{\\times\}4Sudoku datasets\. The*mixed*train dataset contains 1,200 training chains: 300 examples for each of the easy, medium, hard, and expert difficulty buckets\. Difficulty is controlled through the number of pre\-filled cells; the generation configuration uses minimum clue counts of 14, 10, 8, and 6 respectively for the four buckets\. Evaluation*mixed*dataset contains 50 puzzles for each difficulty \(200 puzzles in total\)\. The*expert*datasets contains only expert\-difficulty puzzles — 1,200 for training and 200 for evaluation, — using the same minimum clue count of 6\. All Sudoku experiments use Qwen3\-4B with QLoRA fine\-tuning\.

### 4\.3Sudoku w/ RT 4x4 Task

The Sudoku with reasoning trances \(w/ RT\) task augments standard Sudoku solving by attaching a natural\-language explanation to each grid transition\. The motivation is practical rather than evaluative: when a model spells out*why*a particular cell is filled, each step becomes easier to inspect and recover from\. This variant tests whether the same validated\-search pipeline remains useful when the action contains both a verifiable grid transition and an unverified natural\-language rationale\.

Each chain begins with a partially filled Sudoku grid and each<node\>action contains a grid followed by a brief justification\. The dataset is produced by sampling Sudoku puzzles, solving them into one\-cell\-at\-a\-time reference chains, and prompting Qwen3\-32B to add concise explanations for each transition\. Grid states are validated exactly as in the standard Sudoku task, while the natural\-language reasoning is not validated\. Further generation details and the prompt template are given in[Sections˜8\.5](https://arxiv.org/html/2607.07492#S8.SS5)and[8\.6](https://arxiv.org/html/2607.07492#S8.SS6)\.

### 4\.4Blocksworld task

Blocksworld is a classical planning domain in which a set of lettered blocks must be rearranged from an initial stack configuration into a specified goal configuration using four primitive actions: pick up, put down, stack, and unstack\. Subject to strict physical preconditions: only one block may be held at a time, and a block can only be picked up or unstacked if nothing is on top of it\(Valmeekamet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib28)\)\. Despite its apparent simplicity, Blocksworld has become a canonical stress\-test for LLM planning: standard autoregressive models and even chain\-of\-thought prompting fail reliably on instances beyond a few blocks, because valid plans require maintaining a consistent world\-state across many interdependent steps and recovering gracefully when a chosen action renders a necessary precondition unreachable\(Valmeekamet al\.,[2022](https://arxiv.org/html/2607.07492#bib.bib29); Kambhampatiet al\.,[2024](https://arxiv.org/html/2607.07492#bib.bib30)\)\.

##### Data generation

We generate Blocksworld instances with 3 to 12 blocks using the standard\(Valmeekamet al\.,[2023](https://arxiv.org/html/2607.07492#bib.bib28)\)framework, solve valid instances with the Fast\-Forward planner\(Hoffmann and Nebel,[2001](https://arxiv.org/html/2607.07492#bib.bib31)\), and convert the resulting PDDL plans into text action chains\. In total, we generated 9,132 tasks with plan lengths ranging from 3 to 39 actions, reserving 30% for testing while preserving the plan\-length distribution\. To decrease the amount of linearly increasing solutions during exploration, we preserved tasks with up to 16 actions required to solve them\. The final size of the training dataset was 3 ,035 tasks\. As a test set, we used full plan\-length distribution with up to 42 actions and total size of 2,740 tasks\. Additional generation details are given in[Section˜8\.5](https://arxiv.org/html/2607.07492#S8.SS5)\.

##### Validation

The correctness is determined by VAL\(Howeyet al\.,[2004](https://arxiv.org/html/2607.07492#bib.bib32)\), which symbolically simulates the candidate plan and checks both the action preconditions and the satisfaction of the final goal\. This provides an exact validator for the planning domain, analogous to the graph and Sudoku validators\.

## 5Results

This section presents the evaluation protocol used to analyze correction behavior\. Unless stated otherwise, aggregate results are reported as mean±\\pmstandard deviation over three runs\. The primary task metric is percent of solved examples: a chain succeeds when its terminal<done\>action parses as a complete valid answer for the given problem\. We also track search cost through generated steps, generated length, and the number of backtracks\. Because Pyligent explicitly trains recovery, we additionally classify every emitted backtrack into four categories: invalid, valid, correct and perfect \([Table˜4](https://arxiv.org/html/2607.07492#S8.T4)\)\.

We report two checkpoint families\. A*Pyligent checkpoint*is obtained by the full iterative pipeline: train, explore, convert the resulting search trees into supervision, and repeat forTTiterations\. A*finetuned checkpoint*, referred in tables and plots usually as*model FT*, is a fresh copy of the base model fine\-tuned once on the final dataset collected by the Pyligent pipeline\. Thus, Pyligent checkpoints see the data through the iterative training\-and\-exploration loop, while model FT checkpoints are trained on the full Pyligent dataset at once\. We compare both families against the base model and a gold\-only fine\-tuned base model reference\.

### 5\.1Hidden directed graph

Table 1:Hidden directed graph evaluation results, reported as mean±\\pmstandard deviation\. The final column reports the percentage of all generated backtracks that are perfect; the full mutually exclusive category breakdown is shown in[Figure˜3](https://arxiv.org/html/2607.07492#S5.F3)\.![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/graph_hidden_backtracks.png)Figure 3:Hidden directed graph backtrack quality\. Pie charts show mean backtrack counts over three runs, using the mutually exclusive invalid, valid\-only, correct\-only, and perfect categories from[Table˜4](https://arxiv.org/html/2607.07492#S8.T4)\.The hidden graph results show a sharp separation between imitating successful paths and learning recovery behavior\. The base model without thinking never solves an example, while thinking gives only0\.2±0\.3%0\.2\\pm 0\.3\\%success and neither setting emits usable backtracks \([Table˜1](https://arxiv.org/html/2607.07492#S5.T1)and[Figure˜3](https://arxiv.org/html/2607.07492#S5.F3)\)\. Gold\-only SFT gives a small improvement to3\.8±1\.2%3\.8\\pm 1\.2\\%success, but it still behaves mostly like a long forward search: average generated length is24\.21±1\.2224\.21\\pm 1\.22actions against an average gold length of5\.05\.0, and only23\.2%23\.2\\%of its backtracks are perfect\.

By contrast, the Pyligent checkpoint reaches76\.5±2\.3%76\.5\\pm 2\.3\\%success with much shorter generations and active correction\. Its average generated length is10\.96±0\.4310\.96\\pm 0\.43actions, less than half the gold\-only SFT length, and it emits427\.7±31\.1427\.7\\pm 31\.1backtracks across 200 examples\. Almost all of these are non\-invalid, with47\.7%47\.7\\%perfect backtracks, meaning the model often returns to the immediate choice point responsible for the failed branch rather than merely jumping to some earlier valid node\. At the example level,11\.0±5\.8%11\.0\\pm 5\.8\\%of runs containing at least one valid\-only backtrack still finish successfully, and each such run later emits a correct or perfect backtrack that repairs the earlier imprecise recovery\. The matched comparison is therefore consistent with the goal of the task: validator\-guided failed branches provide the signal needed to learn when to abandon a revealed dead end, while gold\-only training mostly teaches the format of successful paths\.

### 5\.2Sudoku 4x4

Table 2:Sudoku4×44\{\\times\}4results for Qwen3\-4B\. All entries are solved validation puzzles \(%\) reported as mean±\\pmstandard deviation over three runs\. Pyligent architectures use traces and one failed\-path epoch\. ‘Sudoku w/ RT’ refers to Sudoku4×44\{\\times\}4with reasoning traces\.![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/sudoku4x4_ablations.png)Figure 4:Sudoku4×44\{\\times\}4ablations on the mixed dataset with Qwen3\-4B, reported as mean±\\pmstandard deviation over three runs\. ‘No traces’ uses architectures without traces and one failed\-path epoch\. ‘Traces’ uses architectures with traces and one failed\-path epoch, matching the first\-row setting in[Table˜2](https://arxiv.org/html/2607.07492#S5.T2)\. ‘More failed\-path epochs’ uses traces and three failed\-path epochs\.![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/sudoku4x4_backtracks.png)Figure 5:Sudoku4×44\{\\times\}4backtrack quality on the mixed dataset with Qwen3\-4B\. Pie charts show mean backtrack counts over three runs\. All listed architectures use traces\.#### 5\.2\.1Sudoku 4x4 Task

The Sudoku results show that Pyligent models improve over both gold\-only SFT and the base model on both datasets\. On the mixed validation split, the Pyligent model with linear explorer reaches82±1\.0%82\\pm 1\.0\\%, compared with65±0\.3%65\\pm 0\.3\\%for gold\-only SFT and11±0\.9%11\\pm 0\.9\\%for the base model \([Table˜2](https://arxiv.org/html/2607.07492#S5.T2)\)\. On the expert\-only split, absolute accuracy is lower for every model, as expected from the harder puzzle distribution, but the gap remains large: the best Pyligent model reaches66±0\.8%66\\pm 0\.8\\%, compared with48±1\.0%48\\pm 1\.0\\%for gold\-only SFT and0±0\.0%0\\pm 0\.0\\%for the base model\. The finetuned checkpoints also improve over the base model, but they do not match the best Pyligent checkpoints, indicating that the iterative training\-and\-exploration loop is useful beyond just collecting a larger supervised dataset\.

The ablations demonstrate two practical effects on the mixed dataset\. First, moving from no traces to traces notably improves performance across the Pyligent and model FT variants \([Figure˜4](https://arxiv.org/html/2607.07492#S5.F4)\)\. This supports the motivation for traced recovery: preserving a compact account of the failed branch helps the model continue after backtracking instead of repeating the same local mistake\. Second, increasing failed\-path training from one epoch to three epochs usually reduces solve rate for Pyligent checkpoints, although finetuned checkpoints do not show the same drop\. The backtrack\-quality plots explain part of this tradeoff: the extra failed\-path focus improves the quality of generated backtracks, but better backtrack syntax and target selection do not automatically translate into better final continuation \([Figure˜5](https://arxiv.org/html/2607.07492#S5.F5)\)\.

#### 5\.2\.2Sudoku w/ RT 4x4

Using the same training set size as in the standard Sudoku4×44\{\\times\}4setting, Sudoku4×44\{\\times\}4with reasoning traces \(w/ RT\) allows the model to generate not only completed grids but also natural\-language reasoning steps\. The goal is to give the model more room to ‘think’ before making each prediction\.

Although the overall scores are generally lower than for standard Sudoku4×44\{\\times\}4, the superiority of the Pyligent models is preserved \([Table˜2](https://arxiv.org/html/2607.07492#S5.T2)\)\. While reasoning traces appear to be more harmful than helpful in this particular setting, the experiment nevertheless suggests that the proposed Pyligent framework may still improve performance on tasks that require natural\-language reasoning, such as MATH and GSM8K\.

### 5\.3Blocksworld

Table 3:Blocksworld evaluation results, reported as mean±\\pmstandard deviation\. The final column reports the percentage of all generated backtracks that are perfect; the full mutually exclusive category breakdown is shown in[Figure˜6](https://arxiv.org/html/2607.07492#S5.F6)\.![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/blocksworld_backtracks.png)Figure 6:Blocksworld backtrack quality\. Pie charts show mean backtrack counts over three runs, using the mutually exclusive invalid, valid\-only, correct\-only, and perfect categories from[Table˜4](https://arxiv.org/html/2607.07492#S8.T4)\.In Blocksworld, the base model is again unable to solve the task and emits a large amount of valid backtracks without any improvement \([Table˜3](https://arxiv.org/html/2607.07492#S5.T3)and[Figure˜6](https://arxiv.org/html/2607.07492#S5.F6)\)\. Gold\-only SFT improves the accuracy up to29\.37±0\.1529\.37\\pm 0\.15but the model failed to emit any reasonable number of backtracks\. The Pyligent model solves50\.35±0\.12%50\.35\\pm 0\.12\\%of validation tasks and achieves more than 20% accuracy against the gold\-only SFT model\. It learns how to perform backtracks, and additional training examples increased the capabilities of the model: nearly 700 tasks were uniquely solved by Pyligent across 3 runs and backtracks helped to solve more than 11% of these tasks \(See[Section˜8\.7](https://arxiv.org/html/2607.07492#S8.SS7)for a task success distribution analysis\)\.

Blocksworld is a much less forgiving domain than the Sudoku because local action validity does not imply global progress toward the goal\. A generated plan may satisfy every precondition for many steps, while still dismantling useful structure or postponing a necessary subgoal\. However, a proper fine\-tuning and backtracks improved the Qwen3\-4B capabilities noticeably\.

## 6Conclusion

The results should be read as an empirical implementation study of the Diligent Learner hypothesis\. Pyligent turns the theory’s behavioral conditions into a concrete training recipe for smaller LLMs by combining gold\-chain SFT, validator\-guided exploration, supervised backtrack targets, and traced continuation after recovery\.

The hidden directed graph task provides the cleanest evidence for this framing\. Gold\-only SFT learns the surface format of successful paths but rarely recovers from mistakes, while the Pyligent checkpoint actively uses valid and often perfect backtracks to solve substantially more examples\. This supports the claim that the useful signal is not only the final answer or the polished reasoning path, but the structure of failed attempts and the correct point of return\. In this sense, the graph task is not just another benchmark; it is a direct probe of whether the model has learned the recoverability behavior required by the theory\.

The broader tasks show both promise and limits\. Sudoku and Blocksworld supply exact validators, making them natural domains for the same mechanism, but the ablations indicate that training recovery is sensitive to trace format, exploration policy, checkpoint family, and failure\-data weighting\. In particular, increasing exposure to failed branches can improve the number of non\-invalid backtracks without reliably improving final solve rate\. This suggests that learning to emit a syntactically valid recovery action is easier than learning the full policy of when to abandon a branch and where to resume\. Future work should therefore separate next\-action quality, failure detection, backtrack target quality, and post\-backtrack continuation more explicitly\.

Overall, our findings are consistent with the search\-theoretic motivation while making its engineering requirements concrete\. Reliable backtracking is not a behavior that should be expected to emerge automatically from gold solutions alone; it needs to be represented in the action space, generated during exploration, validated in hindsight, and trained as an explicit target\.

## 7Limitations and Future Work

Pyligent is currently evaluated on small or synthetic tasks with exact validators, so its behavior may not transfer directly to broader text\-based reasoning settings where validation is weaker, delayed, or ambiguous\. The present experiments also use relatively small solver models and focus on domains where the action format can be constrained tightly\. It remains unclear how much of the observed recovery behavior would persist with open\-ended natural\-language actions\.

The framework also adds cost\. Exploration requires repeated solver sampling and validator calls; traced recovery increases context length; and failed\-branch supervision introduces a weighting choice that can improve backtrack quality without improving final solve rate\. Future work should measure this accuracy\-cost tradeoff more systematically\.

Finally, promising extensions include validators for rationale quality in reasoning\-annotated tasks, larger solver models, and evaluation on natural\-language benchmarks where verification can be decomposed into smaller checked steps\.

## References

- How much backtracking is enough? exploring the interplay of SFT and RL in enhancing LLM reasoning\.External Links:[Link](https://arxiv.org/abs/2505.24273),[Document](https://dx.doi.org/10.48550/arXiv.2505.24273),2505\.24273Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p4.1)\.
- DeepSeek\-AI, D\. Guo, D\. Yang, H\. Zhang, J\. Song, P\. Wang, Q\. Zhu, R\. Xu, R\. Zhang, S\. Ma, X\. Bi, X\. Zhang, X\. Yu, Y\. Wu, Z\. F\. Wu, Z\. Gou, Z\. Shao, Z\. Li, Z\. Gao, A\. Liu, B\. Xue, B\. Wang, B\. Wu, B\. Feng, C\. Lu, C\. Zhao, C\. Deng, C\. Zhang, C\. Ruan, D\. Dai, D\. Chen, D\. Ji, E\. Li, F\. Lin, F\. Dai, F\. Luo, G\. Hao, G\. Chen, G\. Li, H\. Zhang, H\. Bao, H\. Xu, H\. Wang, H\. Ding, H\. Xin, H\. Gao, H\. Qu, H\. Li, J\. Guo, J\. Li, J\. Wang, J\. Chen, J\. Yuan, J\. Qiu, J\. Li, J\. L\. Cai, J\. Ni, J\. Liang, J\. Chen, K\. Dong, K\. Hu, K\. Gao, K\. Guan, K\. Huang, K\. Yu, L\. Wang, L\. Zhang, L\. Zhao, L\. Wang, L\. Zhang, L\. Xu, L\. Xia, M\. Zhang, M\. Zhang, M\. Tang, M\. Li, M\. Wang, M\. Li, N\. Tian, P\. Huang, P\. Zhang, Q\. Wang, Q\. Chen, Q\. Du, R\. Ge, R\. Zhang, R\. Pan, R\. Wang, R\. J\. Chen, R\. L\. Jin, R\. Chen, S\. Lu, S\. Zhou, S\. Chen, S\. Ye, S\. Wang, S\. Yu, S\. Zhou, S\. Pan, S\. S\. Li, S\. Zhou, S\. Wu, S\. Ye, T\. Yun, T\. Pei, T\. Sun, T\. Wang, W\. Zeng, W\. Zhao, W\. Liu, W\. Liang, W\. Gao, W\. Yu, W\. Zhang, W\. L\. Xiao, W\. An, X\. Liu, X\. Wang, X\. Chen, X\. Nie, X\. Cheng, X\. Liu, X\. Xie, X\. Liu, X\. Yang, X\. Li, X\. Su, X\. Lin, X\. Q\. Li, X\. Jin, X\. Shen, X\. Chen, X\. Sun, X\. Wang, X\. Song, X\. Zhou, X\. Wang, X\. Shan, Y\. K\. Li, Y\. Q\. Wang, Y\. X\. Wei, Y\. Zhang, Y\. Xu, Y\. Li, Y\. Zhao, Y\. Sun, Y\. Wang, Y\. Yu, Y\. Zhang, Y\. Shi, Y\. Xiong, Y\. He, Y\. Piao, Y\. Wang, Y\. Tan, Y\. Ma, Y\. Liu, Y\. Guo, Y\. Ou, Y\. Wang, Y\. Gong, Y\. Zou, Y\. He, Y\. Xiong, Y\. Luo, Y\. You, Y\. Liu, Y\. Zhou, Y\. X\. Zhu, Y\. Xu, Y\. Huang, Y\. Li, Y\. Zheng, Y\. Zhu, Y\. Ma, Y\. Tang, Y\. Zha, Y\. Yan, Z\. Z\. Ren, Z\. Ren, Z\. Sha, Z\. Fu, Z\. Xu, Z\. Xie, Z\. Zhang, Z\. Hao, Z\. Ma, Z\. Yan, Z\. Wu, Z\. Gu, Z\. Zhu, Z\. Liu, Z\. Li, Z\. Xie, Z\. Song, Z\. Pan, Z\. Huang, Z\. Xu, Z\. Zhang, and Z\. Zhang \(2025\)DeepSeek\-r1: incentivizing reasoning capability in LLMs via reinforcement learning\.645\(8081\),pp\. 633–638\.External Links:ISSN 0028\-0836, 1476\-4687,[Link](http://arxiv.org/abs/2501.12948),[Document](https://dx.doi.org/10.1038/s41586-025-09422-z),2501\.12948 \[cs\]Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- K\. Gandhi, A\. Chakravarthy, A\. Singh, N\. Lile, and N\. Goodman \(2025\)Cognitive behaviors that enable self\-improving reasoners, or, four habits of highly effective STaRs\.External Links:[Link](https://arxiv.org/abs/2503.01307),[Document](https://dx.doi.org/10.48550/arXiv.2503.01307),2503\.01307Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p4.1)\.
- K\. Gandhi, D\. H\. J\. Lee, G\. Grand, M\. Liu, W\. Cheng, A\. Sharma, and N\. Goodman \(2024\)Stream of search \(SoS\): learning to search in language\.External Links:[Link](https://arxiv.org/abs/2404.03683),[Document](https://dx.doi.org/10.48550/arXiv.2404.03683),2404\.03683Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- Z\. Gou, Z\. Shao, Y\. Gong, Y\. Shen, Y\. Yang, N\. Duan, and W\. Chen \(2023\)CRITIC: large language models can self\-correct with tool\-interactive critiquing\.External Links:[Link](https://arxiv.org/abs/2305.11738),[Document](https://dx.doi.org/10.48550/arXiv.2305.11738),2305\.11738Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- S\. Hao, Y\. Gu, H\. Ma, J\. Hong, Z\. Wang, D\. Wang, and Z\. Hu \(2023\)Reasoning with language model is planning with world model\.InProceedings of the 2023 Conference on Empirical Methods in Natural Language Processing,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),pp\. 8154–8173\.External Links:[Link](https://aclanthology.org/2023.emnlp-main.507/),[Document](https://dx.doi.org/10.18653/v1/2023.emnlp-main.507)Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- J\. Hoffmann and B\. Nebel \(2001\)The FF planning system: fast plan generation through heuristic search\.14\(1\),pp\. 253–302\.External Links:ISSN 1076\-9757Cited by:[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.SSS0.Px1.p1.1)\.
- R\. Howey, D\. Long, and M\. Fox \(2004\)VAL: automatic plan validation, continuous effects and mixed initiative planning using PDDL\.InProceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence,ICTAI ’04,pp\. 294–301\.External Links:ISBN 978\-0\-7695\-2236\-4,[Link](https://doi.org/10.1109/ICTAI.2004.120),[Document](https://dx.doi.org/10.1109/ICTAI.2004.120)Cited by:[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.SSS0.Px2.p1.1)\.
- J\. Huang, X\. Chen, S\. Mishra, H\. S\. Zheng, A\. W\. Yu, X\. Song, and D\. Zhou \(2023\)Large language models cannot self\-correct reasoning yet\.External Links:[Link](https://arxiv.org/abs/2310.01798),[Document](https://dx.doi.org/10.48550/arXiv.2310.01798),2310\.01798Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- S\. Kambhampati, K\. Valmeekam, L\. Guan, M\. Verma, K\. Stechly, S\. Bhambri, L\. P\. Saldyt, and A\. B\. Murthy \(2024\)LLMs can’t plan, but can help planning in LLM\-modulo frameworks\.External Links:[Link](https://arxiv.org/abs/2402.01817),[Document](https://dx.doi.org/10.48550/arXiv.2402.01817),2402\.01817Cited by:[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.p1.1)\.
- R\. Kamoi, Y\. Zhang, N\. Zhang, J\. Han, and R\. Zhang \(2024\)When can LLMs actually correct their own mistakes? a critical survey of self\-correction of LLMs\.12,pp\. 1417–1440\.External Links:[Link](https://aclanthology.org/2024.tacl-1.78/),[Document](https://dx.doi.org/10.1162/tacl%5Fa%5F00713)Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- J\. Kim, A\. Goyal, L\. Tan, H\. Hajishirzi, S\. Iyer, and T\. Wang \(2025\)ASTRO: teaching language models to reason by reflecting and backtracking in\-context\.arXiv\.External Links:[Link](http://arxiv.org/abs/2507.00417),[Document](https://dx.doi.org/10.48550/arXiv.2507.00417),2507\.00417 \[cs\]Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- A\. Kumar, V\. Zhuang, R\. Agarwal, Y\. Su, J\. D\. Co\-Reyes, A\. Singh, K\. Baumli, S\. Iqbal, C\. Bishop, R\. Roelofs, L\. M\. Zhang, K\. McKinney, D\. Shrivastava, C\. Paduraru, G\. Tucker, D\. Precup, F\. Behbahani, and A\. Faust \(2024\)Training language models to self\-correct via reinforcement learning\.External Links:[Link](https://arxiv.org/abs/2409.12917),[Document](https://dx.doi.org/10.48550/arXiv.2409.12917),2409\.12917Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- L\. Lehnert, S\. Sukhbaatar, D\. Su, Q\. Zheng, P\. McVay, M\. Rabbat, and Y\. Tian \(2024\)Beyond a\*: better planning with transformers via search dynamics bootstrapping\.External Links:[Link](https://arxiv.org/abs/2402.14083),[Document](https://dx.doi.org/10.48550/arXiv.2402.14083),2402\.14083Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- A\. Madaan, N\. Tandon, P\. Gupta, S\. Hallinan, L\. Gao, S\. Wiegreffe, U\. Alon, N\. Dziri, S\. Prabhumoye, Y\. Yang, S\. Gupta, B\. P\. Majumder, K\. Hermann, S\. Welleck, A\. Yazdanbakhsh, and P\. Clark \(2023\)Self\-refine: iterative refinement with self\-feedback\.External Links:[Link](https://arxiv.org/abs/2303.17651),[Document](https://dx.doi.org/10.48550/arXiv.2303.17651),2303\.17651Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- T\. Qin, D\. Alvarez\-Melis, S\. Jelassi, and E\. Malach \(2025\)To backtrack or not to backtrack: when sequential search limits model reasoning\.External Links:[Link](https://arxiv.org/abs/2504.07052),[Document](https://dx.doi.org/10.48550/arXiv.2504.07052),2504\.07052Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p4.1)\.
- Y\. Qu, T\. Zhang, N\. Garg, and A\. Kumar \(2024\)Recursive introspection: teaching language model agents how to self\-improve\.External Links:[Link](https://arxiv.org/abs/2407.18219),[Document](https://dx.doi.org/10.48550/arXiv.2407.18219),2407\.18219Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- S\. Shalev\-Shwartz and A\. Shashua \(2025\)From reasoning to super\-intelligence: a search\-theoretic perspective\.arXiv\.External Links:[Link](http://arxiv.org/abs/2507.15865),[Document](https://dx.doi.org/10.48550/arXiv.2507.15865),2507\.15865 \[cs\]Cited by:[§1](https://arxiv.org/html/2607.07492#S1.p2.1),[§2](https://arxiv.org/html/2607.07492#S2.p5.1),[§3](https://arxiv.org/html/2607.07492#S3.p1.1),[§4\.1](https://arxiv.org/html/2607.07492#S4.SS1.p2.1)\.
- N\. Shinn, F\. Cassano, E\. Berman, A\. Gopinath, K\. R\. Narasimhan, and S\. Yao \(2023\)Reflexion: language agents with verbal reinforcement learning\.External Links:[Link](https://arxiv.org/abs/2303.11366),[Document](https://dx.doi.org/10.48550/arXiv.2303.11366),2303\.11366Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- D\. Su, S\. Sukhbaatar, M\. Rabbat, Y\. Tian, and Q\. Zheng \(2024\)Dualformer: controllable fast and slow thinking by learning with randomized reasoning traces\.External Links:[Link](https://arxiv.org/abs/2410.09918),[Document](https://dx.doi.org/10.48550/arXiv.2410.09918),2410\.09918Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- K\. Team, A\. Du, B\. Gao, B\. Xing, C\. Jiang, C\. Chen, C\. Li, C\. Xiao, C\. Du, C\. Liao, C\. Tang, C\. Wang, D\. Zhang, E\. Yuan, E\. Lu, F\. Tang, F\. Sung, G\. Wei, G\. Lai, H\. Guo, H\. Zhu, H\. Ding, H\. Hu, H\. Yang, H\. Zhang, H\. Yao, H\. Zhao, H\. Lu, H\. Li, H\. Yu, H\. Gao, H\. Zheng, H\. Yuan, J\. Chen, J\. Guo, J\. Su, J\. Wang, J\. Zhao, J\. Zhang, J\. Liu, J\. Yan, J\. Wu, L\. Shi, L\. Ye, L\. Yu, M\. Dong, N\. Zhang, N\. Ma, Q\. Pan, Q\. Gong, S\. Liu, S\. Ma, S\. Wei, S\. Cao, S\. Huang, T\. Jiang, W\. Gao, W\. Xiong, W\. He, W\. Huang, W\. Xu, W\. Wu, W\. He, X\. Wei, X\. Jia, X\. Wu, X\. Xu, X\. Zu, X\. Zhou, X\. Pan, Y\. Charles, Y\. Li, Y\. Hu, Y\. Liu, Y\. Chen, Y\. Wang, Y\. Liu, Y\. Qin, Y\. Liu, Y\. Yang, Y\. Bao, Y\. Du, Y\. Wu, Y\. Wang, Z\. Zhou, Z\. Wang, Z\. Li, Z\. Zhu, Z\. Zhang, Z\. Wang, Z\. Yang, Z\. Huang, Z\. Huang, Z\. Xu, Z\. Yang, and Z\. Lin \(2025\)Kimi k1\.5: scaling reinforcement learning with LLMs\.arXiv\.External Links:[Link](http://arxiv.org/abs/2501.12599),[Document](https://dx.doi.org/10.48550/arXiv.2501.12599),2501\.12599 \[cs\]Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- Y\. Tian, B\. Peng, L\. Song, L\. Jin, D\. Yu, L\. Han, H\. Mi, and D\. Yu \(2024\)Toward self\-improvement of LLMs via imagination, searching, and criticizing\.External Links:[Link](https://arxiv.org/abs/2404.12253),[Document](https://dx.doi.org/10.48550/arXiv.2404.12253),2404\.12253Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.
- K\. Valmeekam, M\. Marquez, A\. Olmo, S\. Sreedharan, and S\. Kambhampati \(2023\)PlanBench: an extensible benchmark for evaluating large language models on planning and reasoning about change\.External Links:[Link](https://arxiv.org/abs/2206.10498),[Document](https://dx.doi.org/10.48550/arXiv.2206.10498),2206\.10498Cited by:[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.SSS0.Px1.p1.1),[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.p1.1)\.
- K\. Valmeekam, A\. Olmo, S\. Sreedharan, and S\. Kambhampati \(2022\)Large language models still can’t plan \(a benchmark for LLMs on planning and reasoning about change\)\.External Links:[Link](https://arxiv.org/abs/2206.10498),[Document](https://dx.doi.org/10.48550/arXiv.2206.10498),2206\.10498Cited by:[§4\.4](https://arxiv.org/html/2607.07492#S4.SS4.p1.1)\.
- J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, B\. Ichter, F\. Xia, E\. H\. Chi, Q\. V\. Le, and D\. Zhou \(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.External Links:[Link](https://arxiv.org/abs/2201.11903),[Document](https://dx.doi.org/10.48550/arXiv.2201.11903),2201\.11903Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p1.1)\.
- X\. Yang, X\. Zhu, W\. Wei, D\. Zhang, J\. Shao, Z\. Zhou, L\. Guo, and Y\. Li \(2025\)Step back to leap forward: self\-backtracking for boosting reasoning of language models\.arXiv\.External Links:[Link](http://arxiv.org/abs/2502.04404),[Document](https://dx.doi.org/10.48550/arXiv.2502.04404),2502\.04404 \[cs\]Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p3.1)\.
- S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. L\. Griffiths, Y\. Cao, and K\. R\. Narasimhan \(2023\)Tree of thoughts: deliberate problem solving with large language models\.External Links:[Link](https://arxiv.org/abs/2305.10601),[Document](https://dx.doi.org/10.48550/arXiv.2305.10601),2305\.10601Cited by:[§2](https://arxiv.org/html/2607.07492#S2.p2.1)\.

## 8Appendix

3\_ \| 1221 \| 43\-\-\-\-\+\-\-\-\-43 \| 211\_ \| 3434 \| 1221 \| 43\-\-\-\-\-\+\-\-\-\-43 \| 211\_ \| 3434 \| 1221 \| 43\-\-\-\-\+\-\-\-\-43 \| 2113 \| 3434 \| 1221 \| 43\-\-\-\-\+\-\-\-\-43 \| 2112 \| 34constraintviolatedDone\!r1​c2=4r\_\{1\}c\_\{2\}=4r4​c2=3r\_\{4\}c\_\{2\}=3r4​c2=2r\_\{4\}c\_\{2\}=2backtrack

Figure 7:Example of Sudoku4×44\{\\times\}4trees\.Table 4:Backtrack categories used for correction\-aware evaluation\. The categories are nested in quality: perfect backtracks are also correct, correct backtracks are also valid, and valid backtracks are also non\-invalid\.### 8\.1Explorer schedules

RootLinear: fixed\-width parallel chains\.RootSweet point: balances between linear and exponentialRootExponential: produces same number of branches on each depth

Figure 8:Exploration schedules\. Linear exploration spawns a bounded number of parallel chains, while exponential exploration branches from each node\.We study multiple explorers because the useful search regime is task\-dependent\. If the explorer branches too little, the model cannot recover from an early local mistake\. If it branches too aggressively, the number of candidate partial chains grows too quickly and the exploration budget is spent on shallow alternatives rather than on finishing promising trajectories\.

LetBBbe the branching factor and letdddenote a frontier depth relative to the selected prefix root\. A naive exponential branching policy allows every frontier to generate up toBBchildren,

cexp​\(d\)=B,c\_\{\\exp\}\(d\)=B,so the number of nodes reachable by depthDDgrows on the order of

1\+B\+B2\+⋯\+BD=O​\(BD\)\.1\+B\+B^\{2\}\+\\cdots\+B^\{D\}=O\(B^\{D\}\)\.This is undesirable in our setting because training requires validator calls and pair construction for explored branches; exponential growth therefore converts a small increase in depth into a large increase in cost while often failing to improve branch quality\.

The linear explorer implements the opposite extreme\. Its frontier capacity is

clin​\(d\)=\{B,d=0,1,d\>0\.c\_\{\\text\{lin\}\}\(d\)=\\begin\{cases\}B,&d=0,\\\\ 1,&d\>0\.\\end\{cases\}This createsBBparallel chains rather than a dense tree: the root can spawn up toBBalternatives, and each alternative then continues as a single line\. Linear exploration is attractive when depth matters more than local breadth, because cost remains predictable and the explorer can advance multiple candidate chains in parallel\.

The dendritic explorer is designed for the intermediate regime\. It keeps a bounded per\-iteration child budgetUUbut scores frontiers so that search behavior shifts from breadth\-first to depth\-first as the local tree grows\. LetNNbe the number of discovered nodes in the current prefix\-local tree\. The transition is controlled by

σ​\(N\)=11\+exp⁡\(−h​\(logB⁡N−s\)\),\\sigma\(N\)=\\frac\{1\}\{1\+\\exp\\left\(\-h\\left\(\\log\_\{B\}N\-s\\right\)\\right\)\},α​\(N\)=αbfs\+\(αdfs−αbfs\)​σ​\(N\),\\alpha\(N\)=\\alpha\_\{\\text\{bfs\}\}\+\\left\(\\alpha\_\{\\text\{dfs\}\}\-\\alpha\_\{\\text\{bfs\}\}\\right\)\\sigma\(N\),wheressis the transition point andhhcontrols sharpness\. Early in exploration,α​\(N\)\\alpha\(N\)is close toαbfs\\alpha\_\{\\text\{bfs\}\}and the explorer favors shallower frontiers; later it approachesαdfs\\alpha\_\{\\text\{dfs\}\}and increasingly favors deeper continuations\.

For an expandable frontierii, letdid\_\{i\}be its relative depth, letcmax​\(i\)c\_\{\\max\}\(i\)be its maximum number of children, and letgapi=cmax​\(i\)−childreni\\mathrm\{gap\}\_\{i\}=c\_\{\\max\}\(i\)\-\\mathrm\{children\}\_\{i\}denote remaining child capacity\. The dendritic explorer uses the log\-score

log⁡scorei=α​\(N\)​log⁡\(1\+diDimax\)\+β​log⁡\(1\+gapimax⁡\(1,cmax​\(i\)\)\+ε\),\\log\\mathrm\{score\}\_\{i\}=\\alpha\(N\)\\log\\\!\\left\(1\+\\frac\{d\_\{i\}\}\{D\_\{i\}^\{\\max\}\}\\right\)\+\\beta\\log\\\!\\left\(1\+\\frac\{\\mathrm\{gap\}\_\{i\}\}\{\\max\(1,c\_\{\\max\}\(i\)\)\}\+\\varepsilon\\right\),whereDimaxD\_\{i\}^\{\\max\}is the remaining allowed depth from the current prefix andβ\\betaweights the unused\-capacity term\. After scoring frontiers, the explorer deterministically allocates the budgetUUacross the highest\-scoring nodes\. In practice, this yields a broad\-then\-deep pattern: the explorer first discovers competing branches and then concentrates resources on extending the most promising ones\.

### 8\.2SFT\-B pair construction

Input:

\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<node\>2StepE</node\>\]

Target:

<done\>Solution\!</done\>

\(a\)Success pair\.
Input:

\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<node\>2StepB</node\>

<node\>3StepC</node\>

<node\>4StepD</node\>\]

Target:

<backtrack\>

1Constraintsviolated

</backtrack\>

\(b\)Failed pair\.
Input:

\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<trace\>

Reason:Constraintsviolated

Explorednode:<node\>2StepB</node\>

Errornode:<node\>4StepD</node\>

</trace\>\]

Target:

<node\>2StepE</node\>

\(c\)Continue pair\.

Figure 9:Example of different SFT\-B pair kinds for prefix<node\>0 puzzle input</node\>, <node\>1 Step A</node\>\.The SFT\-B dataset contains three kinds of pairs \([Figure˜9](https://arxiv.org/html/2607.07492#S8.F9)\)\. Success pairs train the model to continue along valid generated or gold branches\. Failure pairs train the model to emit a<backtrack\>action when a branch violates task constraints\. Continue pairs train the model to resume from a valid prefix after a compact trace of the failed branch has been inserted\. Trace construction is described separately in[Section˜8\.3](https://arxiv.org/html/2607.07492#S8.SS3)\.

We use a reverse curriculum over prefixes\. Early training explores near\-solution prefixes, where the remaining continuation is short and validation feedback is dense\. Later stages move the starting prefix closer to the root, increasing the amount of search the solver must perform before reaching a valid<done\>action\. For a chainct=\(a0,a1,…,at\),\|ct\|=t\+1c\_\{t\}=\(a\_\{0\},a\_\{1\},\\ldots,a\_\{t\}\),\|c\_\{t\}\|=t\+1, the curriculum starts withT=tT=t, so the solver is asked to generateata\_\{t\}given the prefix\(a0,a1,…,at−1\)\(a\_\{0\},a\_\{1\},\\ldots,a\_\{t\-1\}\)\. After the SFT\-A, exploration, and SFT\-B passes,T=t−1T=t\-1is set, so the new prefix becomes\(a0,a1,…,at−2\)\(a\_\{0\},a\_\{1\},\\ldots,a\_\{t\-2\}\)\. This process repeats untilT=1T=1is reached, at which point the solver is asked to produce the whole chain based on the task description only\.

### 8\.3Trace format and traced recovery

During traced inference, when the model emits

<backtrack\>ID REASON</backtrack\>,\\texttt\{<backtrack\>ID REASON</backtrack\>\},the runtime truncates the context to the target node and injects a compact trace:

<trace\>REASON SUMMARY</trace\>\.\\texttt\{<trace\>REASON SUMMARY</trace\>\}\.The trace is never generated by the model as a target action\. It is inserted by the runtime and appears only in the subsequent context\. In our implementation the summary records the validator reason, the first explored action after the backtrack target, and the final erroneous action in the failed branch:

```
<trace>
    Reason: Invalid step: must fill exactly one empty cell
    Explored node: <node>2 ...</node>
    Error node: <node>4 ...</node>
</trace>
```

Introducing traces requires careful handling to avoid distribution shift\. The ordinary SFT\-B failure pair teaches the model to emit a backtrack, but does not by itself teach the model how to continue after the runtime inserts a trace\. To mitigate this mismatch, we create synthetic traces during SFT\-B training: for each failure pair, we insert a synthetic trace after the backtrack target and create a continuation target from the corresponding valid branch\.

We evaluate three recovery regimes\. In*reset*mode, the runtime truncates the context to the target node and discards the failed branch\. In*preserve*mode, the raw<backtrack\>action remains in context\. In*traced*mode, the runtime truncates to the target node and appends<trace\>\.\.\.</trace\>\. The Sudoku ablations in[Figure˜4](https://arxiv.org/html/2607.07492#S5.F4)compare traced and non\-traced training, while the main Sudoku results in[Table˜2](https://arxiv.org/html/2607.07492#S5.T2)use traced recovery\.

### 8\.4Finetune expanders

1\.\[<node\>0puzzleinput</node\>\]

\-\-\><node\>1StepA</node\>

2\.\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>\]

\-\-\><node\>2StepE</node\>

3\.\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<node\>2StepE</node\>\]

\-\-\><done\>Solution\!</done\>

\(a\)allexpander\.
1\.\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>\]

\-\-\><node\>2StepE</node\>

2\.\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<node\>2StepE</node\>\]

\-\-\><done\>Solution\!</done\>

\(b\)prefixexpander\.
1\.\[<node\>0puzzleinput</node\>

<node\>1StepA</node\>

<node\>2StepB</node\>

<node\>3StepC</node\>

<node\>4StepD</node\>\]

\-\-\><backtrack\>

1Constraintsviolated

</backtrack\>

\(c\)finalexpander\.

Figure 10:Finetune expander examples for prefix<node\>0 puzzle input</node\>, <node\>1 Step A</node\>\. Format is\[training prefix\] \-\-\> training target\.Finetune expanders control which prefix\-target pairs are materialized from a successful or failed chain before SFT\-B \([Figure˜10](https://arxiv.org/html/2607.07492#S8.F10)\)\. We need multiple expanders because the same explored tree can emphasize different learning signals\. Theallexpander supervises every intermediate continuation, producing dense next\-step imitation\. Theprefixexpander keeps later generated prefixes and the terminal answer, reducing dataset size while still teaching continuation from non\-root contexts\. Thefinalexpander is used for failed leaves: it trains the model to emit the final recovery action from the full failed branch\. In Sudoku4×44\{\\times\}4, the main traced setting combines prefix\-style supervision for successful branches with final failed\-branch supervision, so the model sees both post\-trace continuation targets and explicit backtrack targets without over\-weighting every intermediate failed prefix\.

### 8\.5Additional task methodology details

##### Training and evaluation hyperparameters\.

Unless stated otherwise, most experiments use the following parameters\. We train Qwen3\-4B with themax\_seq\_len=2560, vLLM GPU memory utilization 0\.8, gradient checkpointing and 10 dataloader workers and exploration batch size 256\. For exploration we use a linear explorer with branching budgetB=5B=5, leaf multipliercleaf=3c\_\{\\mathrm\{leaf\}\}=3, maximum leaf capability 20, adaptiveTmaxT\_\{\\text\{max\}\}\(so the maximum curriculumTTis taken for each gold chain individually based on its length\) and deduplication \(what means we do not include exactly the same generated nodes on one depth into separate chains\)\. We also use*restricted solver*— vLLM with restricted regex output on during diligent pipeline — in order to generate well\-structured chains on exploration phase\. The SFT schedule is one epoch for SFT\-A, one epoch for all SFT\-B examples\. The optimizer and adapter settings are QLoRA in bfloat16, learning rate5⋅10−55\\cdot 10^\{\-5\}, LoRA rank 32 and alpha 64, per\-device batch size 16, gradient accumulation 1, cosine learning\-rate schedule, warmup ratio 0\.03, weight decay 0\.01, and LoRA dropout 0\.05\. For FT and Gold models we fine\-tune for 3 epochs\. Evaluation uses each task’s maximum evaluation step budget: 30 steps for Sudoku4×44\{\\times\}4, 30 for Sudoku w/ RT4×44\{\\times\}4, 50 for Blocksworld and 30 for Hidden graph\. We conducted experiment on NVIDIA A100 80Gb\.

##### Hidden directed graph validation\.

For<node\>actions, the hidden graph validator checks that the requested target is visible from the current node, rejects moves toFAIL, rejects moving toGOALinstead of emitting<done\>, and requires<done\>whenGOALis already visible\. For terminal actions, it verifies that the answer is exactly the current path extended byGOAL, thatGOALis currently visible, and thatFAILis absent\. A valid move can still reveal a losing branch: if the new observation isX \-\> FAILorX \-\> \(none\), the explorer records a failed leaf with a reason such asFailure reached after START \-\> X\.

##### Sudoku validation\.

Every Sudoku action contains a complete grid rather than a coordinate\-level edit\. The solver is instructed to output exactly one tag per turn\. If the current grid still contains empty cells, it may output a<node\>that fills exactly one empty cell or a<backtrack\>if the branch is invalid\. If the current grid is already complete, it must output<done\>with the same complete grid; filling the final empty cell and terminating are therefore two separate turns:

```
<node>0
3 4 | 1 2
2 1 | 4 3
----+----
4 3 | 2 1
1 _ | 3 4
</node>
```

```
<node>1
3 4 | 1 2
2 1 | 4 3
----+----
4 3 | 2 1
1 2 | 3 4
</node>
```

```
<done>
3 4 | 1 2
2 1 | 4 3
----+----
4 3 | 2 1
1 2 | 3 4
</done>
```

The Sudoku validator preserves all initial clues, enforces row, column, and box constraints, and requires each<node\>transition to place exactly one digit into an empty cell without clearing or rewriting any filled cell\. For<done\>, the validator additionally requires that the action repeats the latest complete grid and that no empty cells remain\. During exploration, failures such as changing an initial clue, placing multiple digits at once, or emitting<done\>before completion become validator reasons for backtrack targets\.

##### Sudoku w/ RT generation and validation\.

Sudoku w/ RT supports grids from4×44\{\\times\}4to9×99\{\\times\}9\. Each chain begins with a partially filled Sudoku grid; every<node\>action contains the updated grid followed by a brief justification separated by a blank line, and<done\>must reproduce the fully solved grid\. The primary training dataset contains 1,2004×44\{\\times\}4puzzles with reasoning generated by Qwen3\-32B\. Grid transitions are validated using the standard Sudoku validator above, but the reasoning text is not validated\.

##### Blocksworld generation and validation\.

Blocksworld initial and goal states are sampled uniformly at random with thebwstatesutility and formatted as PDDL problems under the standard blocksworld\-4ops domain\. Duplicate problems and already\-solved initial states are discarded; generation moves to the next block count when more than 90% of samples in a rolling window of 2048 tasks are duplicates\. Valid problems are solved with Fast\-Forward \(FF\), and the returned plans are converted from PDDL into text prompts with color names for blocks\. VAL validates candidate outputs by simulating plan execution from the initial state, checking action preconditions and effects at each step, and confirming that the resulting state satisfies the goal\.

### 8\.6Sudoku w/ RT task reasoning generation prompt

For each pair of consecutive grids\(Gt,Gt\+1\)\(G\_\{t\},G\_\{t\+1\}\)in a solution chain, the LLM receives a prompt containing the current grid and the next grid \(with one cell filled\) in visual format, optionally preceded by the reasoning from the previous step for context\. The prompt instructs the model to identify which cell changed, state what digit was placed, and explain why that digit is the only valid option using standard Sudoku constraints\. The model is asked to respond concisely in 1–3 sentences without numbering or meta\-references\.

The full prompt template is:

![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/blocksworld_pyligent_vs_gold_sft_pie.png)Figure 11:Distribution of task outcomes on the Blocksworld test set for the Gold\-only SFT model and the Pyligent model, aggregated across 3 runs\. "Both solved" indicates that both models reached a valid<done\>node and completed the task successfully in all 3 runs\. The remaining slices show which tasks were solved uniquely by one model or left unsolved by both\.```
You are analyzing a single-cell transition in a {size}x{size} Sudoku puzzle.

Current grid:
{current_visual}
[Previous reasoning (if available):
{previous_reasoning}]

Next grid (one cell was filled):
{next_visual}

Explain the logical reasoning that justifies the newly filled cell.
Use only standard Sudoku constraints (row, column, and box rules).

Important rules:
- Identify which cell changed and what digit was placed.
- Explain why this digit is the only valid option for that cell.
- Do NOT mention ’Next grid’ or ’Current grid’ in your reasoning.
- Write concisely in 1-3 sentences.

Answer directly with the reasoning. Do not number your response.
```

### 8\.7Blocksworld task success distribution analysis

[Figure˜11](https://arxiv.org/html/2607.07492#S8.F11)shows the solvability of each task across all 3 runs\. Both models were able to solve 28\.2% of tasks and failed on 42\.5 % of tasks\. The Gold\-only SFT model never succeeded via backtracking and solved only 4\.1% of tasks uniquely\. In comparison, the Pyligent model was able to complete 25\.2% of tasks uniquely, and more than 11% of these successes were achieved via backtracking\. This indicates that the Pyligent training endowed the model with backtracking capabilities and improved its overall task understanding\.

In[Figure˜12](https://arxiv.org/html/2607.07492#S8.F12), the success rate of both models declines as the number of actions in the gold plan increases, confirming that action count is a reasonable proxy for task difficulty\. This decline also reflects the models’ extrapolation capabilities, since both were trained only on tasks with up to 16 actions per gold chain\. The Pyligent model consistently outperforms the Gold\-only SFT model across the observed range, maintaining a higher success rate even as task complexity grows\. The average number of backtracks per task for Pyligent also increases with action count, suggesting that the model relies on backtracking more heavily as tasks become harder\. Moreover, the contribution of backtracking to overall success grows with task difficulty: at the hardest tasks, backtracking accounted for roughly 50% of successes at 28 actions, albeit based on a small number of successful tasks, indicating that backtracking becomes increasingly important for solving the hardest tasks\.

![Refer to caption](https://arxiv.org/html/2607.07492v1/figs/blocksworld_gold_action_metrics.png)Figure 12:Distribution of Blocksworld successes and backtracks across the number of actions in the gold chains\. The number of actions correlates with task difficulty, though the number of blocks may vary\. The lines show the trend in success rate for Gold\-only SFT model and Pyligent model, each bar shows the average number of backtracks per task, and the number above each bar indicates how many of the successful tasks involved at least one backtrack\. The absence of a number indicates that none of the successes involved a backtrack\.