A Neural Rewriting System to Solve Algorithmic Problems
Flavio Petruzzellis Alberto Testolin Alessandro Sperduti
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 propose an original
approach to learn algorithmic tasks inspired by rewriting systems, a classic
framework in symbolic artificial intelligence. We show that a rewriting system
can be implemented as a neural architecture composed by specialized modules:
the Selector identifies the target sub-expression to process, the Solver
simplifies the sub-expression by computing the corresponding result, and the
Combiner produces a new version of the original expression by replacing the
sub-expression with the solution provided. We evaluate our model on three types
of algorithmic tasks that require simplifying symbolic formulas involving
lists, arithmetic, and algebraic expressions. We test the extrapolation
capabilities of the proposed architecture using formulas involving a higher
number of operands and nesting levels than those seen during training, and we
benchmark its performance 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.