Abstract
While Large Language Models (LLMs) excel at a variety of natural language tasks, they frequently struggle with systematic generalization—the ability to apply learned rules to problems of increasing complexity or recursive depth. This paper introduces the Neural Rewriting System (NRS), a modular architecture designed to bridge the "compositional gap" by decomposing complex formulas into iterative, manageable sub-tasks. By separating the logic of selection, computation, and replacement, the NRS significantly outperforms monolithic models like GPT-4 and the Neural Data Router (NDR) on deeply nested mathematical and logical expressions.
Introduction: The Compositional Gap
A fundamental challenge in neural symbolic reasoning is the ability to learn a rule on simple examples (e.g., $1 + 1$) and apply it recursively to massive, "out-of-distribution" problems (e.g., a formula with 20 nested parentheses). Standard Transformers often fail this test because they attempt to process the entire sequence at once. As the nesting depth or sequence length increases, the model's internal representation often breaks down—a phenomenon known as the "compositional gap."
To address this, the authors propose moving away from monolithic "black box" models toward a modular system inspired by classical symbolic AI, which treats problem-solving as a sequence of string-rewriting operations.
The Neural Rewriting System (NRS) Architecture
The NRS decomposes formula simplification into an iterative loop involving three distinct neural modules:
- The Selector: A Transformer-based module trained to identify the innermost "leaf formula"—a sub-expression that can be solved immediately (e.g., identifying
(3+4)within a larger string). To handle formulas much longer than those seen during training, it utilizes Label-based Positional Encodings and a Dynamic Windowing mechanism to scan the input string in segments. - The Solver: A sequence-to-sequence (seq2seq) Transformer that takes the isolated leaf formula and computes its result (e.g., mapping
(3+4)to7). Because the Solver only ever processes simple, flat expressions, it maintains high accuracy regardless of the original formula's total depth. - The Combiner: This module integrates the Solver's result back into the original string. The authors implemented this using a 2D Convolutional Neural Network (CNN) with dynamically set filters to perform exact string matching and replacement, ensuring the substitution is mathematically perfect.
The system operates in a continuous loop—Select, Solve, Combine—until the formula is reduced to a single value.
Experimental Setup and Benchmarks
The NRS was evaluated on three symbolic benchmarks designed to test depth generalization:
- ListOps: Operations such as
MAX,MIN, andMEDIANon integer lists. - Arithmetic: Nested addition, subtraction, and multiplication (modulo 100).
- Algebra: Simplifying expressions involving variables (e.g.,
(-7*a*x*y + 47*a*x*y)).
To test true systematic generalization, the models were trained only on "shallow" formulas (nesting levels 1–3) but were evaluated on "deep" formulas (nesting levels up to 6).
Key Results and Insights
The NRS demonstrated a stark advantage over monolithic architectures in out-of-distribution tasks:
- Superior Depth Generalization: On Arithmetic formulas with a nesting level of 6, the Neural Data Router (NDR) scored near 0%, and GPT-4 achieved only 13% accuracy. In contrast, the NRS maintained an accuracy of approximately 89%.
- Robustness in ListOps: The NRS achieved 93-98% accuracy across all tested depths and argument lengths, whereas the NDR's performance collapsed as soon as the formulas exceeded the complexity of the training set.
- Interpretability and Failure Analysis: Unlike standard Transformers where errors are difficult to diagnose, the modular nature of the NRS allows researchers to pinpoint failures. The authors found that the Solver is rarely the source of error; rather, the bottleneck is the Selector struggling to locate sub-expressions in extremely long strings. The introduction of "Dynamic Windowing" was shown to drastically reduce these selection errors in complex algebraic tasks.
Discussion and Future Work
The success of the NRS suggests that simply scaling parameter counts in LLMs may not solve the fundamental issue of recursive reasoning. By hard-coding reliability into the replacement mechanism (the Combiner) and isolating the logic of selection, the NRS achieves a level of robustness that monolithic models lack.
Currently, the NRS is optimized for confluent formulas, where the order of operations does not change the final result. Future research will explore how modular systems can handle non-confluent problems or branching logic, where the model must choose between multiple valid rewriting rules, potentially utilizing reinforcement learning to navigate more complex problem spaces.
Summary updated