ClassicLogic (Shahid and Rothe, 2026) is an open-source benchmark of four logic puzzles — Sudoku, KenKen, Kakuro, and Futoshiki — in which each game carries a hierarchical knowledge base whose complex solving strategies are formally defined as compositions of simpler ones. When representative neuro-symbolic models (SATNet, Neural Module Networks, Logical Neural Networks) are trained on Easy/Moderate puzzles and tested on Hard puzzles that provably require novel compositions of known strategies, success collapses below 25% (best model 20–24%). The open problem is to develop a learning system that closes this procedural composition gap: trained only on the Easy/Moderate curriculum, it must form and apply novel multi-step compositions of the knowledge-base strategies to solve Hard puzzles across all four games, together with evidence that its success stems from genuine strategy composition rather than shortcuts.

Background

Compositional generalization — the ability to understand and produce novel combinations of previously learned components — is a long-standing weakness of neural networks, first isolated in linguistic benchmarks such as SCAN (Lake and Baroni, 2017), which tests systematic recombination of navigation commands, and COGS (Kim and Linzen, 2020), which tests semantic interpretation of novel sentence structures. ClassicLogic (Shahid and Rothe, 2026) extends the challenge from language to symbolic problem solving. Its suite covers four constraint-satisfaction puzzles: Sudoku (fill a 9×9 grid so each row, column, and 3×3 block contains each digit once), KenKen (additionally cage-based arithmetic targets), Kakuro (cross-sum clue filling), and Futoshiki (inequality constraints between cells). Puzzles are presented to an agent not as symbolic matrices but as visual grids rendered with MNIST handwritten-digit images, so the agent must first perceive the grid's clues before reasoning about them. The suite's core innovation is a hierarchical knowledge base (KB) per game in which advanced human solving strategies are explicitly defined as compositions of foundational ones — for example, the Sudoku 'naked pair' strategy is formally defined as a pattern-recognition step whose output (the cells and candidates to eliminate) feeds an elimination step, which the paper also describes as composing the 'naked single' and 'constraint propagation' strategies. Every generated puzzle instance is annotated with the strategies required to solve it, and instances are generated with unique solutions and mathematically validated difficulty. This pins three evaluation axes: entity composition (recognizing puzzle entities such as handwritten digits in the visual grid), relational composition (integrating cell-value states with arithmetic or inequality constraints), and procedural composition (chaining simple rules into novel multi-step strategies). The benchmark's authors evaluated three representative neuro-symbolic architectures — systems that combine neural learning with symbolic structure: SATNet (Wang et al., 2019), which embeds a differentiable MAX-SAT relaxation so a network can learn logical constraints; Neural Module Networks (Andreas et al., 2015), which dynamically assemble task-specific networks from specialized modules; and Logical Neural Networks (Riegel et al., 2020), whose neurons carry formal logical meaning (AND, OR). On the procedural composition protocol — training on a curriculum of Easy and Moderate puzzles that exposes every base and moderate strategy in the KB, then testing on Hard puzzles guaranteed to require composed strategy sequences not seen in training — all three architectures collapse to below 25% success, with the Logical Neural Network best at 20–24% and Neural Module Networks worst. The paper's conclusion is that current models, even with strong logical priors, lack mechanisms for flexible sequential planning: they can learn static rules but cannot compose them into new multi-step procedures, and the paper offers no solution or architectural guidance for this gap.

Problem Statement

Develop a learning system that closes the procedural composition gap on the ClassicLogic benchmark. The system — either a single unified model or one method instantiated and trained per game, following the benchmark's published per-game protocol — receives its task-specific training only on the benchmark's Easy/Moderate curriculum for each of the four games (Sudoku, KenKen, Kakuro, Futoshiki), which exposes all base and moderate-level strategies in each game's hierarchical knowledge base but no composed Hard-level strategy sequence; pretrained components or external data (for example, a digit recognizer) must not themselves supply Hard-level composed strategies or puzzle-specific solving knowledge. It must then solve Hard puzzles — instances guaranteed by the benchmark's construction to require composed strategies applied in sequences not seen during training — across all four games, raising per-game success rates from the reported collapse below 25% (best model 20–24%) and closing the benchmark's documented generalization gap: in each of the four games, Hard success must reach at least 50% and must fall no more than 10 percentage points below the system's own in-domain Easy/Moderate accuracy measured under the same protocol, so that the gap is closed by genuine Hard-puzzle capability rather than by comparison against a weakened, self-selected baseline. This success must arise from forming and applying novel compositions of the knowledge-base strategies rather than from exploiting surface statistics of the puzzle generator or embedding a hand-coded constraint solver, and the open question is what mechanisms enable this flexible sequential planning over a strategy knowledge base. The benchmark's published protocol (open-source code, unique-solution generation, per-instance strategy annotations) defines the evaluation; extending the benchmark to additional puzzle families is community engineering outside this problem's completion boundary.

References

  1. Mahnoor Shahid and Hannes Rothe. ClassicLogic: A Knowledge-Driven Benchmark of Classic Puzzle Games for Evaluating Compositional Generalization. arXiv:2607.05185 (2026). DOI: 10.48550/arXiv.2607.05185. https://arxiv.org/abs/2607.05185
  2. Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. arXiv:1711.00350 (2017). DOI: 10.48550/arXiv.1711.00350. https://arxiv.org/abs/1711.00350
  3. Najoung Kim and Tal Linzen. COGS: A Compositional Generalization Challenge Based on Semantic Interpretation. arXiv:2010.05465 (2020). DOI: 10.48550/arXiv.2010.05465. https://arxiv.org/abs/2010.05465
  4. Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. arXiv:1905.12149 (2019). DOI: 10.48550/arXiv.1905.12149. https://arxiv.org/abs/1905.12149
  5. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural Module Networks. arXiv:1511.02799 (2015). DOI: 10.48550/arXiv.1511.02799. https://arxiv.org/abs/1511.02799
  6. Ryan Riegel, Alexander Gray, Francois Luus, Naweed Khan, Ndivhuwo Makondo, Ismail Yunus Akhalwaya, Haifeng Qian, Ronald Fagin, Francisco Barahona, Udit Sharma, Shajith Ikbal, Hima Karanam, Sumit Neelam, Ankita Likhyani, and Santosh Srivastava. Logical Neural Networks. arXiv:2006.13155 (2020). DOI: 10.48550/arXiv.2006.13155. https://arxiv.org/abs/2006.13155
  7. Mahnoor Shahid and Hannes Rothe. AGEL-Comp: A Neuro-Symbolic Framework for Compositional Generalization in Interactive Agents. arXiv:2604.26522 (2026). DOI: 10.48550/arXiv.2604.26522. https://arxiv.org/abs/2604.26522
  8. Mahnoor Shahid and Hannes Rothe. Grounding vs. Compositionality: On the Non-Complementarity of Reasoning in Neuro-Symbolic Systems. arXiv:2604.26521 (2026). DOI: 10.48550/arXiv.2604.26521. https://arxiv.org/abs/2604.26521
  9. Danial Kamali, Elham J. Barezi, and Parisa Kordjamshidi. NeSyCoCo: A Neuro-Symbolic Concept Composer for Compositional Generalization. arXiv:2412.15588 (2024). DOI: 10.48550/arXiv.2412.15588. https://arxiv.org/abs/2412.15588
  10. Yiyou Sun, Shawn Hu, Georgia Zhou, Ken Zheng, Hannaneh Hajishirzi, Nouha Dziri, and Dawn Song. OMEGA: Can LLMs Reason Outside the Box in Math? Evaluating Exploratory, Compositional, and Transformative Generalization. arXiv:2506.18880 (2025). DOI: 10.48550/arXiv.2506.18880. https://arxiv.org/abs/2506.18880
  11. Zhen Hao Wong, Jingwen Deng, Runming He, Zirong Chen, Qijie You, Hejun Dong, Hao Liang, Chengyu Shen, Bin Cui, and Wentao Zhang. LogicPuzzleRL: Cultivating Robust Mathematical Reasoning in LLMs via Reinforcement Learning. arXiv:2506.04821 (2025). DOI: 10.48550/arXiv.2506.04821. https://arxiv.org/abs/2506.04821