Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Technical Summary: Recurrent Reasoning on Symbolic Puzzles with Sequence Models

Problem Statement
Large language models (LLMs) often demonstrate apparent proficiency in symbolic and algorithmic tasks, yet this performance frequently masks brittle behavior when problems increase in length, difficulty, or deviate slightly from the training distribution. Current reasoning benchmarks often prioritize the production of a valid final answer over the robustness, minimality, and stability of the solution process. This paper argues that for algorithmic problems, correctness requires not just a plausible endpoint but the ability to repeatedly choose valid intermediate actions, avoid illegal transitions, and maintain consistency over long horizons. The authors posit that algorithmic reasoning serves as a critical setting to distinguish genuine robustness from shallow pattern matching.

Methodology: The RecurrReason Benchmark
To address these limitations, the authors introduce RecurrReason, a difficulty-controlled benchmark comprising four recurrent logic puzzles:

1. Block World: Rearranging blocks in stacks.
2. Checkers Jumping: Swapping positions of red and blue checkers on a linear board.
3. Tower of Hanoi: Moving disks between pegs under size constraints.
4. River Crossing: Transporting actor-agent pairs across a river with safety constraints.

The benchmark is constructed with the following characteristics:

• Scalable Difficulty: Each puzzle is parameterized by a single integer $N \in \{1, \dots, 10\}$.
• Optimal Trajectories: All instances are solved using Breadth-First Search (BFS) to generate optimal trajectories, totaling 10,817 unique puzzles and 285,933 moves.
• Task Formulation: The task is framed as a "predict-the-next-step" problem. Models receive the current state ($s_t$) and the goal state ($g$) and must predict the next state ($s_{t+1}$). Evaluation involves autoregressive rollouts without ground-truth intermediate states.
• Evaluation Protocol: Models are trained on instances where $N=1$ to $7$ and evaluated on held-out in-distribution instances ($N=1$ to $7$) and out-of-distribution (OOD) instances ($N=8$ to $10$). Metrics include trajectory success rate, move legality, and optimality gap.

Experimental Setup
The study benchmarks two Transformer families under consistent data splits and training conditions (scratch, zero-shot, and fine-tuned):

1. T5-style (Encoder-Decoder): A 60M parameter model (T5-small) where the encoder computes bidirectional attention over the concatenated state and goal, making the goal a "first-class" conditioning signal at every step.
2. GPT-2-style (Decoder-Only): A 124M parameter model (GPT-2) using a causal mask, which prevents the current state tokens from attending to the goal tokens (which appear later in the sequence), creating a structural bottleneck for goal-directed planning.

Key Results
The experiments reveal that puzzle structure is a stronger determinant of learnability than model scale or pre-training:

• Block World Success: The fine-tuned pre-trained T5 model achieved 97.27% validation accuracy and 81.00% OOD accuracy. This success is attributed to the puzzle's local transition function (checking only the top of a stack, $O(1)$ complexity), linear solution length growth ($L(N) = O(N)$), and dense training signals.
• Failure on Other Puzzles:
  • River Crossing: All models scored 0.00% under all conditions. The puzzle requires global constraint verification ($O(N)$) at every step and has a combinatorial action space, which defeated all architectures.
  • Tower of Hanoi: Models achieved at most 11.11% validation accuracy (only on trivial $N=1$ cases) and 0.00% OOD. The exponential solution length ($2^N - 1$) causes compounding errors that prevent generalization beyond $N=1$.
  • Checkers Jumping: Models achieved at most 1.11% validation accuracy, solving only trivial instances where the start state equals the goal. The quadratic solution length and need to avoid dead-ends proved insurmountable.
• Architecture vs. Scale: The smaller T5 model (60M) significantly outperformed the larger GPT-2 model (124M). The authors attribute this to the encoder-decoder architecture's ability to attend bidirectionally to the goal, whereas the causal mask in decoder-only models creates a bottleneck for planning.
• Pre-training Transfer: Pre-training benefits were observed only for puzzles with locally structured transition functions (Block World). It provided no transfer for puzzles requiring global constraints (River Crossing) or recursive decomposition (Tower of Hanoi).

Failure Mode Analysis
The authors identify specific failure modes correlated with puzzle structure:

• Invalid Moves: Dominated failures in globally constrained puzzles (Tower of Hanoi, River Crossing), indicating a failure to generalize constraints.
• Loops: The primary failure mode for Block World in decoder-only models, suggesting partial rule learning without goal-directed selection.
• Premature Stops: Observed in GPT-2 on Tower of Hanoi, linked to statistical overrepresentation of stop tokens in training data.

Significance and Claims
The paper claims that architectural inductive biases matter more than scale for systematic algorithmic reasoning. Specifically:

1. Structural Determinism: The learnability of a puzzle is determined by three structural properties: transition locality, action space size, and solution length growth. The authors formalize a compounding error model showing that success probability decays exponentially with solution length ($P \approx e^{-\epsilon L(N)}$).
2. Goal Conditioning: Bidirectional goal conditioning (as in T5) is critical for goal-directed planning, while causal attention (as in GPT-2) creates a structural bottleneck that prevents effective planning even with larger parameter counts.
3. Limits of Pre-training: Pre-training imparts a hierarchical inductive bias that transfers only to tasks with locally decomposable structures. It does not inherently equip models to handle global constraints or recursive depth.
4. Future Direction: The results suggest that reliable multi-step reasoning in LLMs requires either architectural search capabilities or explicit symbolic constraint checking, rather than merely scaling model size.

The authors conclude that RecurrReason provides a controlled testbed for future work on length generalization, goal-conditioned planning, and the architectural requirements for systematic algorithmic reasoning.