  Solving symbolic reasoning problems that require compositionality and
systematicity is considered one of the key ingredients of human intelligence.
However, symbolic reasoning is still a great challenge for deep learning
models, which often cannot generalize the reasoning pattern to
out-of-distribution test cases. In this work, we propose a hybrid system
capable of solving arithmetic problems that require compositional and
systematic reasoning over sequences of symbols. The model acquires such a skill
by learning appropriate substitution rules, which are applied iteratively to
the input string until the expression is completely resolved. We show that the
proposed system can accurately solve nested arithmetical expressions even when
trained only on a subset including the simplest cases, significantly
outperforming both a sequence-to-sequence model trained end-to-end and a
state-of-the-art large language model.
