AI Paper Atlas

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

AAAI 2026 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
train with backtracking data and <backtrack> token, decode with N=8 samplingSFT Llama3.2-1B · Countdown (seen targets)accuracy: 28.60 -> 66.66Improved
add backtracking step (b = 1 vs b = 0) (ablation)Self-Backtracking, N = 32, Llama3.2-1B · Countdown (seen targets)accuracy: 70.66 -> 73.54Improved
add backtracking step (b = 1 vs b = 0) (ablation)Self-Backtracking, N = 32, Llama3.2-3B · Countdown (new targets)accuracy: 64.54 -> 66.64Improved
increase N to 32 (ablation)Best-of-N · Countdown (seen targets), Llama3.2-1Baccuracy: 41.26 -> 25.60Hurt
increase N from 8 to 32 (ablation)Self-Backtracking (b = 1) · Countdown (seen targets), Llama3.2-1Baccuracy: 67.60 -> 73.54Improved
add expert iteration self-improvement (3 rounds)Self-Backtracking greedy · Countdown (avg)accuracy: 72.76 -> 79.63Improved
add expert iteration self-improvementSelf-Backtracking · Countdown (avg)output tokens: 355 -> 34Improved
add DPO or KTO preference training on same dataSFT Llama3.2-1B · Countdown (seen targets)accuracy: 28.60 -> 29.06 (DPO), 28.34 (KTO)No clear effect
train with backtracking data, decode greedilyLlama3.2-3B · Countdown (seen targets)accuracy: 33.98 -> 31.06Hurt
use self-backtracking instead of optimal-path SFTLlama3.2-1B · Maze 20x20accuracy: 62.20 -> 93.10Improved
add backtrack token without explicit backtracking (b = 0) (ablation)Llama3.2-1B · Maze 30x30accuracy: 50.8 -> 88.0Improved
add one more backtrack depth (b = 1 vs b = 0, N = 8) (ablation)Self-Backtracking · Maze 20x20accuracy: 94.30 -> 93.10Hurt

Limitations

Experimental setup

Builds on: depth-first search imitation A* search imitation

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy