Learning neuro-symbolic convergent term rewriting systems Journal: Artificial Intelligence Journal
Flavio Petruzzellis, Alberto Testolin, Alessandro Sperduti · 2025
Read Learning neuro-symbolic convergent term rewriting systems Journal: Artificial Intelligence Journal by Flavio Petruzzellis, Alberto Testolin, Alessandro Sperduti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19372.txt.
Introduction
Teaching a neural network to run a symbolic algorithm, and to keep working on inputs bigger than its training set, is an old ambition of AI research. Flavio Petruzzellis, Alberto Testolin, and Alessandro Sperduti build the learner around the algorithm itself in a 2025 paper. Their target is term rewriting, the rule-based simplification of expressions.
Two systems result: a neural rewriting system and a faster sibling that uses less memory and runs quicker. Both generalize beyond their training distribution on formula simplification tasks. A single model also learned several problem types at once. The systems beat a transformer built for algorithmic tasks and a leading general-purpose language model. The authors credit the win to architecture that mirrors the rewriting process.
Catalog record
| CREATOR | Flavio Petruzzellis, Alberto Testolin, Alessandro Sperduti |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-19372
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning neuro-symbolic convergent term rewriting systems Journal: Artificial Intelligence Journal Flavio Petruzzellis, Alberto Testolin, Alessandro Sperduti Abstract Building neural systems that can learn to execute symbolic algorithms is a challenging open problem in artificial intelligence, especially when aiming for strong generalization and out-of-distribution performance. In this work, we introduce a general framework for learning convergent term rewriting systems using a neuro-symbolic architecture inspired by the rewriting algorithm itself. We present two modular implementations of such architecture: the Neural Rewriting System (NRS) and the Fast Neural Rewriting System (FastNRS). As a result of algorithmic-inspired design and key architectural elements, both models can generalize to out-of-distribution instances, with FastNRS offering significant improvements in terms of memory efficiency, training speed, and inference time. We evaluate both architectures on four tasks involving the simplification of mathematical formulas and further demonstrate their versatility in a multi-domain learning scenario, where a single model is trained to solve multiple types of problems simultaneously. The proposed system significantly outperforms two strong neural baselines: the Neural Data Router, a recent transformer variant specifically designed to solve algorithmic problems, and GPT-4o, one of the most powerful general-purpose large-language models. Moreover, our system matches or outperforms the latest o1-preview model from OpenAI that excels in reasoning benchmarks. † † highlights: A neuro-symbolic system inspired by rewriting algorithms can learn convergent term rewriting systems from training data. The system exhibits systematic generalization beyond the training distribution, outperforming relevant neural baselines. The system can learn several convergent term rewriting systems at the same time when trained in a multi-domain setting. 1 Introduction Deep learning systems have spread dramatically in the last decade thanks to their ability to automatize tasks typically carried out by humans, from basic pattern recognition ( He et al. 2016 ) , to natural language processing ( Brown et al. 2020 ) and the generation of synthetic but stunningly realistic media content ( Chang et al. 2023 ) . However, despite these advances, neural network models struggle with tasks that require iterative and reflective reasoning, which in humans require conscious deliberation and understanding beyond pattern recognition ( Kahneman 2011 ) . As a result, deep learning often fails in problems where the ability to reason systematically through compositional concepts is essential, such as learning to simulate symbolic algorithms or solve advanced mathematical formulas ( Testolin 2024 ; Davis 2024 ) . On the other hand, computer programs stemming from classical artificial intelligence techniques have traditionally been very successful in the domain of mathematics and formal reasoning ( Newell and Simon 1956 ) . In such a framework, computer scientists model real-world phenomena using two equally important and complementary formalization tools: algorithms and data structures. The latter can be viewed as a formal description of the entities involved in the modeled phenomena, while the former are descriptions of the processes that can bring the modeled entities to a desired state. Under the assumption that input data are stored in specific data structures that the algorithm was designed to process, the result of the algorithm’s execution will be predictable for the end-user. The power of algorithms can therefore be reduced to the use of abstractions that formally describe real-world entities and processes ( Cormen and Leiserson 2022 ) . Classical algorithms in computer science – such as sorting or graph traversal algorithms – can map inputs to outputs independently of the data distribution from which the input was drawn, with well-studied time and space scaling laws. On the other hand, from a statistical perspective, it is almost always assumed that the inputs to deep learning models belong to the same data distribution of training samples, making it challenging to design learning architectures that can handle out-of-distribution (OOD) test data ( Hendrycks et al. 2021 ; Ye et al. 2021 ) . At the same time, however, the design and implementation of classical algorithms requires a significant amount of human labor: the programmer needs to formalize each problem class using specific data structures and engineer explicit algorithms that can solve the problem at hand. Given the immense wealth of digital data that is now available to organizations and the value they can bring if processed by computer programs, new lines of research propose to reduce the need for humans in the automation loop exploiting machine learning. In this context, information is encoded using distributed representations and is processed by manipulating numerical vectors rather than with classical algorithms and data structures ( Rumelhart et al. 1986 ) . For example, graph neural networks have recently been used to learn graph algorithms, combining the strong real-world data handling capabilities of deep learning with the theoretical guarantees of classical algorithms ( Velickovic et al. 2020 ; Velickovic and Blundell 2021 ) . In this work, we consider a class of problems from the tradition of artificial intelligence and computer science that can be formalized as convergent term rewriting systems ( Baader and Nipkow 1998 ) . Generally speaking, rewriting systems are composed of a set of elements and a set of rules that describe how to transform those elements. Elements can be several different mathematical objects, including strings, graphs, or terms in a formula. When combined with an appropriate algorithm, rewriting systems become programs that can execute the transformation of a sequence of objects into another one by the subsequent application of the given rules. We consider here term rewriting systems, in which the elements are mathematical expressions represented as sequences of symbols, and the rules define their semantically equivalent forms. Specifically, in a convergent term rewriting system, rewrite rules applied sequentially always transform the input into the same final output, independently of the order of application, and sequences of rewrite rules never form loops. We present two related neuro-symbolic architectures designed to learn convergent term rewriting systems: the Neural Rewriting System (NRS) and the Fast Neural Rewriting System (FastNRS). Both models are built upon a shared architectural blueprint inspired by rewriting algorithms. They exhibit strong generalization capabilities, approaching those of traditional term rewriting systems, but their processing dynamics emerges through learning from data rather than manual design. Both models can be trained on a limited subset of formulas and effectively generalize to more complex ones, eliminating the need for exhaustive training on all possible formulas. Such capability for out-of-distribution generalization is enabled by a modular approach informed by the rewrite mechanism and by architectural modifications to the transformer block. We show that these models can function in a multi-domain scenario, a setting where a single model is trained on multiple datasets simultaneously without task-specific architectural adjustments. This results in a “multi-potent” system capable of solving a variety of problem instances within the considered class. Unlike the more conventional multi-task setting in machine learning ( Caruana 1997 ) , where a shared backbone architecture is typically combined with task-specific outputs, our architecture’s algorithmic-inspired design allows the same components to be effectively applied to learn multiple term rewriting systems, enabling robust generalization without task-specific modifications. While the NRS has been described in recent work ( Petruzzellis et al. 2024c ) , the FastNRS is presented here for the first time, together with analysis of the performance of both systems in a multi-domain scenario. The FastNRS system improves