# A Neural Rewriting System to Solve Algorithmic Problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 32 references that are in the map.
- First posted on arXiv 27 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [HyperNetworks](https://mlsanity.com/paper/1609.09106/) (2016)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Making Transformers Solve Compositional Tasks](https://mlsanity.com/paper/2108.04378/) (2021)
- [The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization](https://mlsanity.com/paper/2110.07732/) (2021)
- [Memorize or generalize? Searching for a compositional RNN in a haystack](https://mlsanity.com/paper/1802.06467/) (2018)
- [Is a Modular Architecture Enough?](https://mlsanity.com/paper/2206.02713/) (2022)
- [Systematic Generalization and Emergent Structures in Transformers Trained on Structured Tasks](https://mlsanity.com/paper/2210.00400/) (2022)
- [Can neural networks do arithmetic? A survey on the elementary numerical skills of state-of-the-art deep learning models](https://mlsanity.com/paper/2303.07735/) (2023)
- [CTL++: Evaluating Generalization on Never-Seen Compositional Patterns of Known Functions, and Compatibility of Neural Representations](https://mlsanity.com/paper/2210.06350/) (2022)
- [Analyzing the Nuances of Transformers' Polynomial Simplification Abilities](https://mlsanity.com/paper/2104.14095/) (2021)
- [Learning of Human-like Algebraic Reasoning Using Deep Feedforward Neural Networks](https://mlsanity.com/paper/1704.07503/) (2017)

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

- [Learning neuro-symbolic convergent term rewriting systems](https://mlsanity.com/paper/2507.19372/) (2025)
- [Iterative In-Context Learning to Enhance LLMs Abstract Reasoning: The Case-Study of Algebraic Tasks](https://mlsanity.com/paper/2509.01267/) (2025)

## Abstract (arXiv)

Modern neural network architectures still struggle to learn algorithmic procedures that require to systematically apply compositional rules to solve out-of-distribution problem instances. In this work, we focus on formula simplification problems, a class of synthetic benchmarks used to study the systematic generalization capabilities of neural architectures. We propose a modular architecture designed to learn a general procedure for solving nested mathematical formulas by only relying on a minimal set of training examples. Inspired by rewriting systems, a classic framework in symbolic artificial intelligence, we include in the architecture three specialized and interacting modules: the Selector, trained to identify solvable sub-expressions; the Solver, mapping sub-expressions to their values; and the Combiner, replacing sub-expressions in the original formula with the solution provided by the Solver. We benchmark our system against the Neural Data Router, a recent model specialized for systematic generalization, and a state-of-the-art large language model (GPT-4) probed with advanced prompting strategies. We demonstrate that our approach achieves a higher degree of out-of-distribution generalization compared to these alternative approaches on three different types of formula simplification problems, and we discuss its limitations by analyzing its failures.