Research map / Large language models / Reasoning and chain of thought
Step Back to Leap Forward: Self-Backtracking for Symbolic Reasoning and Planning in Language Models
Xiao-Wen Yang, Xuan-Yi Zhu, Ding-Chu Zhang, Wen-Da Wei, Jie-Jing Shao, Zhi Zhou, Lan-Zhe Guo, Yu-Feng Li
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes self-backtracking, training language models to emulate symbolic search with backtracking decisions for improved symbolic reasoning and planning (AAAI 2026 paper; full text unavailable, so details beyond the abstract are not filled).
Problem
Autoregressive language models are constrained in symbolic reasoning and decision-making; training them to imitate symbolic search (DFS, A*) helps, but the abstract's motivation is cut off before the specific limitation is stated.
Approach
Builds on training LMs to emulate symbolic search algorithms, extending it with self-backtracking so the model can step back during reasoning; the exact mechanism is not stated in the available abstract.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| train with backtracking data and <backtrack> token, decode with N=8 sampling | SFT Llama3.2-1B · Countdown (seen targets) | accuracy: 28.60 -> 66.66 | Improved |
| add backtracking step (b = 1 vs b = 0) (ablation) | Self-Backtracking, N = 32, Llama3.2-1B · Countdown (seen targets) | accuracy: 70.66 -> 73.54 | Improved |
| add backtracking step (b = 1 vs b = 0) (ablation) | Self-Backtracking, N = 32, Llama3.2-3B · Countdown (new targets) | accuracy: 64.54 -> 66.64 | Improved |
| increase N to 32 (ablation) | Best-of-N · Countdown (seen targets), Llama3.2-1B | accuracy: 41.26 -> 25.60 | Hurt |
| increase N from 8 to 32 (ablation) | Self-Backtracking (b = 1) · Countdown (seen targets), Llama3.2-1B | accuracy: 67.60 -> 73.54 | Improved |
| add expert iteration self-improvement (3 rounds) | Self-Backtracking greedy · Countdown (avg) | accuracy: 72.76 -> 79.63 | Improved |
| add expert iteration self-improvement | Self-Backtracking · Countdown (avg) | output tokens: 355 -> 34 | Improved |
| add DPO or KTO preference training on same data | SFT Llama3.2-1B · Countdown (seen targets) | accuracy: 28.60 -> 29.06 (DPO), 28.34 (KTO) | No clear effect |
| train with backtracking data, decode greedily | Llama3.2-3B · Countdown (seen targets) | accuracy: 33.98 -> 31.06 | Hurt |
| use self-backtracking instead of optimal-path SFT | Llama3.2-1B · Maze 20x20 | accuracy: 62.20 -> 93.10 | Improved |
| add backtrack token without explicit backtracking (b = 0) (ablation) | Llama3.2-1B · Maze 30x30 | accuracy: 50.8 -> 88.0 | Improved |
| add one more backtrack depth (b = 1 vs b = 0, N = 8) (ablation) | Self-Backtracking · Maze 20x20 | accuracy: 94.30 -> 93.10 | Hurt |
Limitations
- Full text unavailable; only the abstract was provided
Experimental setup
Builds on: depth-first search imitation A* search imitation
Closest papers by meaning
- Learning to Better Search with Language Models via Guided Reinforced Self-Training (NeurIPS 2025 · similarity 0.89)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.88)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.88)
- Boosting Inference with Guided Reasoning: Stochastic Exploration for Recursive Models (NeurIPS 2026 · similarity 0.88)
- Self-Guiding Exploration for Combinatorial Problems (NeurIPS 2024 · similarity 0.88)
- Non-myopic Generation of Language Models for Reasoning and Planning (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
