A Neural Rewriting System to Solve Algorithmic Problems
This addresses a fundamental challenge in AI for improving systematic generalization in neural networks, though it is incremental as it builds on existing symbolic AI concepts.
The paper tackled the problem of neural networks struggling with algorithmic procedures requiring systematic generalization, specifically for formula simplification tasks, and demonstrated that their modular architecture achieved higher out-of-distribution generalization compared to Neural Data Router and GPT-4.
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.