# Learning to Solve Constraint Satisfaction Problems with Recurrent Transformer

arXiv: https://arxiv.org/abs/2307.04895 · HTML: https://mlsanity.com/paper/2307.04895/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 10 Jul 2023.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [PEGASUS: Pre-training with Extracted Gap-sentences for Abstractive Summarization](https://mlsanity.com/paper/1912.08777/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Multi-modal Transformer for Video Retrieval](https://mlsanity.com/paper/2007.10639/) (2020)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Improving Coherence and Consistency in Neural Sequence Models with Dual-System, Neuro-Symbolic Reasoning](https://mlsanity.com/paper/2107.02794/) (2021)
- [Graph Transformer for Graph-to-Sequence Learning](https://mlsanity.com/paper/1911.07470/) (2019)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [Neural-Symbolic Integration: A Compositional Perspective](https://mlsanity.com/paper/2010.11926/) (2020)
- [Modeling Recurrence for Transformer](https://mlsanity.com/paper/1904.03092/) (2019)
- [Techniques for Symbol Grounding with SATNet](https://mlsanity.com/paper/2106.11072/) (2021)
- [Deep Reasoning Networks: Thinking Fast and Slow](https://mlsanity.com/paper/1906.00855/) (2019)

## Built on by (most cited first, 21 of 21)

- [Artificial Kuramoto Oscillatory Neurons](https://mlsanity.com/paper/2410.13821/) (2024)
- [Learning Iterative Reasoning through Energy Diffusion](https://mlsanity.com/paper/2406.11179/) (2024)
- [On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encoding](https://mlsanity.com/paper/2410.01405/) (2024)
- [Neuro-symbolic Learning Yielding Logical Constraints](https://mlsanity.com/paper/2410.20957/) (2024)
- [Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction](https://mlsanity.com/paper/2502.15794/) (2025)
- [Step-resolved data attribution for looped transformers](https://mlsanity.com/paper/2602.10097/) (2026)
- [Learning Reliable Logical Rules with SATNet](https://mlsanity.com/paper/2310.02133/) (2023)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [Hyper-SET: Designing Transformers via Hyperspherical Energy Minimization](https://mlsanity.com/paper/2502.11646/) (2025)
- [Throttling Web Agents Using Reasoning Gates](https://mlsanity.com/paper/2509.01619/) (2025)
- [Generalizable Reasoning through Compositional Energy Minimization](https://mlsanity.com/paper/2510.20607/) (2025)
- [Guided Discrete Diffusion for Constraint Satisfaction Problems](https://mlsanity.com/paper/2512.14765/) (2025)
- [Beyond Test-Time Memory: State-Space Optimal Control for LLM Reasoning](https://mlsanity.com/paper/2603.09221/) (2026)
- [Large Neighborhood Search meets Iterative Neural Constraint Heuristics](https://mlsanity.com/paper/2603.20801/) (2026)
- [Winfree Oscillatory Neural Network](https://mlsanity.com/paper/2605.20922/) (2026)
- [Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives](https://mlsanity.com/paper/2508.20978/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Blocked Gibbs meets Diffusion Transformers: Unsupervised Learning for Constraint Optimization](https://mlsanity.com/paper/2605.25129/) (2026)
- [Position: Certified Correctness in Neural Constraint Reasoning Requires Symbolic Integration](https://mlsanity.com/paper/2608.14569/) (2026)
- [Dissecting Hierarchical Reasoning Models: A Mechanistic Study](https://mlsanity.com/paper/2609.22197/) (2026)
- [The Geometry of Logic: Stratification Induces Semantic Structure and Robust Reasoning](https://mlsanity.com/paper/2609.32927/) (2026)

## Abstract (arXiv)

Constraint satisfaction problems (CSPs) are about finding values of variables that satisfy the given constraints. We show that Transformer extended with recurrence is a viable approach to learning to solve CSPs in an end-to-end manner, having clear advantages over state-of-the-art methods such as Graph Neural Networks, SATNet, and some neuro-symbolic models. With the ability of Transformer to handle visual input, the proposed Recurrent Transformer can straightforwardly be applied to visual constraint reasoning problems while successfully addressing the symbol grounding problem. We also show how to leverage deductive knowledge of discrete constraints in the Transformer's inductive learning to achieve sample-efficient learning and semi-supervised learning for CSPs.