PaperlayerView exact revision on arXiv

Source-linked AI summary

DART: Distributional Adversarial Recurrent Training for Algorithm Learning

Hieu Tran Bao, Phung Thanh Dang, Pham Quang Nhat Minh, Hoang Thanh Tung

arXiv:2609.05988v1cs.LGcs.AI

TL;DR

Instance-level supervision can become brittle for recurrent reasoning models as task difficulty grows and valid solutions occupy a constrained part of the solution space. DART uses a local target distribution and adversarial alignment, and improves solution quality, stability, and robustness across the evaluated tasks and models.

  • Problem

    As logical problems become harder, valid solutions remain highly constrained while incorrect solutions proliferate, and recurrent models’ out-of-distribution performance has not been systematically examined.

    Source: §1 · pp. 1–2

  • Method

    DART replaces single-point supervision with a local target distribution around the ground-truth solution and adversarially aligns generated reasoning states to it.

    Source: §1 · p. 2

  • Results

    Across Maze, Chess, and masked Sudoku, DART improves peak solution quality and robustness under distribution shift, with gains across the evaluated recurrent reasoning models.

    Source: §1 · p. 2, §7 · p. 11

  • Takeaways & Limitations

    The paper frames easy-to-hard generalization through valid–invalid solution-space imbalance, which becomes more severe as problem complexity increases.

    Source: §1 · p. 2

    Current recurrent reasoning models lack explicit mechanisms for verification, structured exploration, and backtracking, a limitation exposed by Chess and Sudoku’s strategic and combinatorial demands.

    Source: §6 · p. 11

Abstract

from arXiv · show

Recurrent reasoning models (RRMs) can solve structured problems, achieving easy-to-hard generalization through iterative computation in hidden space. These models are typically trained with instance-level supervision, which becomes increasingly problematic as task difficulty grows: valid solutions occupy a tiny region of the solution space, while invalid solutions proliferate rapidly. We propose Distributional Adversarial Recurrent Training (DART), a training framework that replaces single-point supervision with a local target distribution around the ground-truth solution and aligns model outputs with this distribution through an adversarial objective. DART provides a richer learning signal and encourages more stable iterative trajectories toward valid solutions. When evaluated on Maze, Chess, and masked Sudoku with multiple RRMs, including Deep Thinking Systems and Tiny Recursive Models, DART improves solution quality, stability, and robustness under the evaluated distribution shifts. Comparisons with label smoothing, Gaussian softened targets, and progressive training show that DART is not explained by target softening alone and is complementary to training schemes that stabilize long-horizon recurrence. These results identify DART as a promising approach for improving robustness across the evaluated recurrent reasoning models.

1 Introduction

Recurrent reasoning models can generalize to harder logical tasks through iterative computation, but instance-level supervision becomes brittle as valid solutions shrink relative to invalid ones. DART replaces single-point targets with a local distribution and adversarial alignment; evaluations report improvements across the tested models and tasks.

1 Introduction

  • RRMs can solve challenging logical tasks through hidden-state iteration, but their out-of-distribution performance has not been systematically examined.Prior work also reports easy-to-hard generalization by increasing recurrent steps at test time.Source: §1 · pp. 1–2
  • As problem complexity rises, valid solutions remain constrained while incorrect solutions proliferate, making instance-level training brittle and difficult reasoning unstable.Harder instances can result from larger problems or less information in the statement.Source: §1 · p. 2
  • DART replaces single-point supervision with a noisy local target distribution and aligns generated reasoning states to it through an adversarial critic.The target preserves the observed solution under arg max decoding; it does not enumerate distinct discrete solutions.Source: §1 · p. 2
  • DART improves DTS accuracy and iteration stability on Maze and Chess, and improves TRM reasoning on more heavily masked Sudoku.The Sudoku easy-to-hard setting trains on lower masking ratios and evaluates on higher ones.Source: §1 · p. 2
  • The paper frames easy-to-hard difficulty as an imbalance between valid and invalid solution spaces that worsens as complexity increases.It compares against label smoothing, Gaussian softened targets, and progressive training to distinguish target softening, adversarial alignment, and long-horizon stabilization.Source: §1 · pp. 2–3

2 Related Work

Prior work studies algorithm learning and iterative reasoning, adaptive computation, and adversarial guidance for structured learning. DART is positioned as changing the supervision signal rather than the recurrent architecture or computation allocation.

2 Related Work

  • Prior algorithm-learning work includes Neural Turing Machines, Neural GPUs, and Deep Thinking Systems, while later work addresses overthinking through recall, progressive training, or constrained recurrence.The paper uses the Recall architecture in its DTS experiments and compares against progressive training.Source: §2 · p. 3
  • Adaptive-computation methods allocate computation or train over longer horizons, whereas DART changes the supervision signal at each training example.The related work includes ACT, Universal Transformers, Adaptive Recurrent Vision, and PonderNet.Source: §2 · p. 3
  • Adversarial objectives have also guided structured learning, including diffusion models’ semantic constraints and feature-statistic perturbations for robustness.The cited examples are SADM and AdvBN [27].Source: §2 · p. 3
  • DART differs from prior recurrent-model work by addressing valid–invalid solution-space imbalance with adversarial guidance, without changing the recurrent architecture or learning a halting policy.It replaces a one-hot target with a local soft target distribution and an input-conditioned critic.Source: §2 · pp. 3–4

3 Preliminary

The preliminary section introduces structured-solution prediction and the recurrent model families used in the paper. DTS iteratively refines a solution representation, while TRM separates low-level reasoning from high-level answer updates.

3 Preliminary

  • Logical reasoning tasks predict a structured solution from an input, while DTS and TRM use final-step supervised loss against the ground-truth solution.That deterministic target ignores local structure in the valid solution space.Source: §3 · p. 4
  • DTS iteratively refines a whole-solution representation without intermediate-step supervision, and the Recall variant feeds the original input into every recurrent step.The paper uses Recall as its DTS backbone; increasing or decreasing recurrent iterations at test time can target harder or easier instances.Source: §3 · p. 4
  • TRM alternates low-level refinement with high-level answer updates, repeatedly drafting, checking, and refining its prediction.Its low-level state supports constraint exploration, while its high-level state stores the current global solution hypothesis; a shared lightweight block is reused across recursive steps.Source: §3 · p. 4

4 Proposed Method

DART recasts reasoning supervision as learning a local distribution around the ground-truth solution and aligns generated solutions with it adversarially. The framework combines a reasoning critic with supervised training of the recurrent model.

4.1 Soft Solution Distribution

  • DART perturbs one-hot target elements with Gaussian noise, then applies softmax to form local target distributions while preserving the original solution under argmax decoding.The neighborhood is not intended to represent all semantically distinct valid solutions when multiple completions exist.Source: §4.1 · p. 5

4.2 Adversarial Solution Alignment

  • A WGAN-inspired adversarial objective aligns solutions generated by the reasoning model with the local soft target distribution.The critic receives the input problem concatenated with either a generated solution or a softened target solution.Source: §4.2 · p. 5, §4.2.1 · p. 5

4.2.1 Reasoning Critic Network

  • The reasoning critic scores problem–candidate pairs, assigning higher scores to softened targets and lower scores to generated solutions.Its output is a scalar score for the concatenated input and candidate solution.Source: §4.2.1 · p. 5

4.2.2 Training Objective

  • The critic is trained to maximize Wasserstein distance under a Lipschitz constraint, while the reasoning model combines supervised and adversarial losses.Critic weight clipping enforces the constraint; the reasoning-model update holds critic parameters fixed.Source: §4.2.2 · pp. 5–6

5 Experiments

The experiments evaluate DART on easy-to-hard Maze and Chess tasks with DTS and masked Sudoku with TRM. Across these settings, DART improves solution quality and stability over instance-level CE; comparisons also show how it relates to progressive training and simpler target augmentations.

5.1 Datasets, model architecture and training

  • The evaluation uses DTS for easy-to-hard Maze and Chess tasks and TRM for Sudoku, which is reformulated as an easy-to-hard benchmark.The paper also reports model architecture and training details in Appendix A.1.Source: §5.1 · p. 6

5.2.1 DART improves over instance-level CE

  • At 31 × 31, DART reaches 99.91 ± 0.13% peak and final accuracy, while CE reaches 73.92 ± 26.01% peak accuracy.At 13 × 13, CE already reaches 99.88 ± 0.00% peak and 99.85 ± 0.03% final accuracy, so its weakness emerges under harder spatial extrapolation.Source: Table 1 · p. 7, §5.2.1 · p. 7, Figure 1 · p. 7
  • On Chess, DART raises peak accuracy to 84.83 ± 0.03%, versus CE’s 80.81 ± 0.37%, though DART alone does not eliminate late-iteration overthinking.CE falls to 0.92 ± 0.08% by iteration 50.Source: §5.2.1 · pp. 7–8
  • On Sudoku, DART beats CE at every tested computation depth and masking ratio, with depth-56 gains of 0.5%, 3.3%, and 5.6% at 30%, 40%, and 50% masking.The gap grows with masking, the harder distribution shift.Source: Figure 2 · p. 7, Table 2 · p. 8, §5.2.1 · p. 8
  • Across held-out trajectories, DART finishes all 128 evaluated Maze samples in an exact state, while CE finishes at 43.8% exact match.Figure 3 shows representative Maze and Chess trajectories; Table 3 aggregates held-out samples, including 128 Maze and 512 Chess samples.Source: Table 3 · p. 8, Figure 3 · p. 8, §5.2.1 · p. 9

5.2.2 DART and progressive training are complementary

  • Progressive DART reaches 83.52 ± 0.16% final Chess accuracy, while Progressive CE reaches 83.46 ± 0.02% at iteration 50; on 31 × 31 Maze, Progressive DART reaches 98.75 ± 1.25%.Progressive training reduces late-iteration collapse, while DART alone reaches the highest Chess peak accuracy.Source: Table 1 · p. 7, Table 4 · p. 9, Figure 4 · p. 9

5.2.3 DART versus simple target augmentations

  • On Maze, label smoothing reaches 98.22 ± 0.64% peak accuracy and Gaussian softened targets reach 59.58 ± 38.86%; on Chess, Gaussian targets reach 82.22 ± 0.09% peak accuracy.DART reaches 99.91 ± 0.13% peak accuracy on Maze and 84.83 ± 0.03% on Chess, exceeding these target-augmentation baselines.Source: Table 5 · p. 10, §5.2.3 · pp. 10–11, Table 6 · p. 11

6 Discussion

DART improves recurrent reasoning across the evaluated tasks, but its gains are more nuanced on Chess and Sudoku than on Maze. It stabilizes trajectories without providing the verification, exploration, or backtracking needed to solve the underlying search problem.

6 Discussion

  • DART improves reasoning reliability but does not fully address the search and verification demands of complex tasks.The discussion identifies learned verification, scoring, and structured backtracking as promising complementary reasoning primitives.Source: §6 · p. 11
  • DART’s gains are strongest on spatial Maze tasks and more nuanced on Chess and Sudoku, where strategic depth and combinatorial structure matter.Chess requires choosing among plausible moves, while masked Sudoku requires hypothesis generation, verification, and correction.Source: §6 · p. 11
  • DART expands a local soft neighborhood around the observed target, but does not enumerate semantically distinct valid discrete solutions.The perturbation preserves the observed target under arg max decoding and smooths supervision around it.Source: §6 · p. 11
  • Progressive training and DART address distinct difficulties: late-iteration collapse on Chess versus larger difficulty shifts on Maze, respectively.The discussion describes combining distributional training with curriculum, verification, or search as a natural next step.Source: §6 · p. 11

7 Conclusion

DART replaces pointwise supervision with distribution-guided adversarial alignment and improves solution quality, stability, and robustness across the evaluated settings. The appendix identifies the datasets used and their sources.

7 Conclusion

  • DART replaces purely instance-level supervision with adversarial alignment around a local neighborhood of the ground-truth solution.The conclusion frames predictions as progressively moving toward a local soft target neighborhood.Source: §7 · p. 11
  • Across Maze, Chess, and masked Sudoku, DART improves peak solution quality and robustness under distribution shift, especially when point-wise supervision becomes unstable.Comparisons indicate target softening alone is task-dependent, while adversarial alignment and progressive training address complementary failure modes.Source: §7 · p. 11

A.1 Datasets

  • The Maze and Chess datasets are publicly available through the easy-to-hard-data Python package, while Masked Sudoku is built from the Extreme Sudoku dataset [9].Source: §A.1 · p. 14

A.1.1 Maze Dataset

The appendix describes Maze generation and the representation and provenance of the Chess puzzle dataset. Maze instances are generated by depth-first search, while Chess examples encode board states and optimal moves as tensors and masks.

A.1.1 Maze Dataset

  • Maze instances are generated by depth-first search, which visits cells and removes walls along traversal paths to ensure connectivity.The generated mazes have non-uniform path lengths, and duplicate samples occur at a rate below 0.5%.Source: §A.1.1 · p. 14

A.1.2 Chess Puzzle Dataset

  • Chess puzzles come from Lichess and use 8 × 8 × 12 board tensors, with optimal moves encoded as 8 × 8 binary masks marking origin and destination squares.Source: §A.1.2 · p. 14
  • The Chess dataset analyzes approximately 200 million games with Stockfish 12/13 NNUE and is released under CC0, although user identities may be indirectly inferred through puzzle replay.Source: §A.1.2 · p. 14

A.1.3 Masked Sudoku Dataset

Masked Sudoku puzzles are created by hiding cells from complete solutions, with harder evaluation settings masking more cells. The appendix also describes checkpoint selection and points to a table of training hyperparameters.

A.1.3 Masked Sudoku Dataset

  • Masked Sudoku inputs are 9 × 9 grids with randomly masked cells, while the complete solved grid is the target output.Source: §A.1.3 · p. 14
  • Training masks 20% of 1,000 solved grids, while evaluation increases masking to 30%, 40%, and 50% to test harder inference from fewer observed constraints.Source: §A.1.3 · p. 14
  • Evaluation uses a held-out set of 10,000 puzzles, and Sudoku checkpoints are validated at the target test masking ratio.The input-output format stays fixed across difficulty levels while the amount of observed information changes.Source: §A.1.3 · p. 14, §A.2 · p. 14

A.2 Hyperparameters

  • Table 7 summarizes the training hyperparameters, with dashes indicating options that were not used.Source: Table 7 · p. 15

A.3 Model architectures

The appendix specifies the recurrent model and training setups, reports their computational costs, and examines how DART's target width affects performance.

A.3 Model architectures

  • DTS uses a 128-dimensional convolutional projection, a two-convolution residual recurrent block, and 30 training iterations; TRM uses H=3 and L=6 cycles.DART uses σ=0.3 and a critic mirroring the generator, with fewer recurrent iterations or cycles; weight clipping is 0.01, and only Sudoku also uses gradient clipping.Source: §A.3 · p. 15

A.4 Computational resources

  • DART adds a critic during training, approximately doubling trainable parameters, but discards it at inference, where Maze evaluation takes 334 seconds for both CE and DART.Chess evaluation takes 9.5 seconds for CE and 10.0 seconds for DART; DTS Maze training takes up to two hours, while DTS Chess and TRM Sudoku take 6–8 hours.Source: §A.4 · p. 15

B.1 Effect of Target Distribution Width.

  • 84.82 ± 0.18% and 84.93 ± 0.03% versus CE's 80.8 ± 0.37% on Chess; DART's two target widths perform similarly.On Maze, changing σ from 0.1 to 0.3 yields 99.88 ± 0.12% and 99.91 ± 0.13%, respectively; the larger σ produces a wider high-accuracy plateau on Chess.Source: §B.1 · p. 16

B.2 Effects of Critic Architecture

Both feedforward and recurrent critics improve DART's performance over CE, while the recurrent critic is associated with greater stability across reasoning iterations.

B.2 Effects of Critic Architecture

  • 84.90 ± 0.03% for the feedforward critic and 84.93 ± 0.03% for the recurrent critic, versus CE's 80.8 ± 0.37% on Chess.Both critic variants outperform CE, but the recurrent critic maintains high accuracy across a wider range of reasoning iterations.Source: Figure 6 · p. 16, §B.2 · p. 16
  • 96.23±5.32% for DART with a feedforward critic versus 73.92±26.01% for CE on Maze; recurrent-critic DART reaches 99.88 ± 0.12% at σ = 0.1.The feedforward critic improves performance over CE but is less stable than the recurrent critic in this setting.Source: Figure 6 · p. 16, §B.2 · p. 16
  • DART improves solution quality with either critic design, while the recurrent critic is associated with more stable trajectories, especially on harder tasks.The feedforward critic stacks five independent residual blocks; the recurrent critic reuses one block for five iterations.Source: §B.2 · p. 16

B.3 Additional Sample Trajectory Analysis

Trajectory analyses show that DART more consistently retains valid solutions through recurrent refinement than CE, particularly on Chess, where overthinking is prominent.

B.3 Additional Sample Trajectory Analysis

  • DART finishes every evaluated Maze sample in an exact state and spends 68.9% of its trajectory in exact match, versus CE's 43.8% final rate and 28.4% exact-match AUC.In the representative example, both first reach exact match at iteration 97, but CE loses it 11 times afterward while DART remains exact.Source: §B.3 · p. 17
  • On Chess, DART raises post-solution retention from 11.6% to 63.5% and exact-match AUC from 4.5% to 32.3%, while CE's final exact-match rate is 0.0%.In a representative case, CE reaches exact match at iteration 29 but DART reaches it at iteration 27 and stays exact through the final iteration.Source: §B.3 · p. 17
  • The analyses identify large spatial extrapolation in Maze and late-iteration overthinking in Chess as settings where point-wise supervision becomes brittle.The authors describe the critic as encouraging outputs to remain in regions resembling softened successful traces for the specific input.Source: §B.3 · p. 17
  • The exact-match trace tests whether trajectories enter the valid discrete solution set, since high overlap can still conceal invalid Maze paths or incorrect Chess moves.The authors interpret DART's stability as consistent with aligning generated outputs to an input-conditioned local target neighborhood rather than supervising only one target configuration.Source: §B.3 · p. 17
Loading 2609.05988v1…