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. deep learning, neural networks, mathematical reasoning, neuro-symbolic systems, formula simplification NeSy 2023, 17th International Workshop on Neural-Symbolic Learning and Reasoning, Certosa di Pontignano, Siena,
Designing systems that are able to learn abstract reasoning patterns from data is one of the
fundamental challenges in artificial intelligence research. In particular, the capacity to generalize
compositionally [
In this work, we introduce a novel neuro-symbolic architecture that solves reasoning problems on sequences of symbols in an iterative fashion. Our goal is to build a system that can learn to solve compositional tasks by only observing a subset of problem instances and then generalize the acquired knowledge to out-of-distribution (possibly more dificult) instances. The proposed system is made up of two parts: a deep learning module that is trained to generate candidate solutions that simplify a given input sequence, and a deterministic component that combines Italy ∗Corresponding author. ((21-6)*2) (15*2) the original input and the output of the neural module to produce the final output. Thanks to its hybrid nature, our system can learn the fundamental solution steps for a set of symbolic reasoning problems, and then apply these operations iteratively to novel problem instances.
We evaluate our model on the task of simplifying arithmetic expressions, which is well
suited to study systematic reasoning abilities and is still considered a great challenge even for
state-of-the-art deep learning models [
Our results show that the proposed hybrid architecture achieves better out-of-distribution generalization compared to a Transformer encoder-decoder trained to solve the same problem end-to-end, and to a large language model tested on the same task, adapting the original inputs to create appropriate prompts1.
The proposed architecture is composed of two parts (Figure 1): a trainable seq2seq model which we call the ‘solver’, and a deterministic module named the ‘combiner’. The system operates by pipelining the computation of the solver and the combiner, and then applying the pipeline iteratively. 1Our code is available at https://github.com/flavio2018/nesy23.
We can define as the set of nested arithmetical expressions represented as strings of symbols on which we test our model, and ⊂
as the subset of expressions that consist only of integer values, and thus represent the result (or values) of complex expressions. Furthermore, since each ∈ ⧵
is composed of nested expressions, for each we can identify one innermost sub-expression (only one in our specific case, see Data in Section 3) which can be solved independently from the context (we can define ∈ as the result of ). Finally, we can define a function which associates to each ∈ a chain of solution steps: ℎ() = ( , −1 , ..., 0), where , ∈ , ∈ {1, … , }
, 0 ∈ is the final solution of , and −1 can be described as where the innermost sub-expression has been solved.
Given the compositional nature of the problem, we can distinguish between the goal of solving the entire expression , i.e. finding 0, and the sub-goals of reducing sub-expressions, i.e. computing the result of each sub-expression , ∈ {1, … , } .
In our approach, the solver is trained to match arithmetical sub-expressions in their context to the corresponding numerical solution, by generating as output a string composed of two parts: a replacement candidate (i.e. the result of the innermost sub-expression ) and a replacement target (i.e. the innermost sub-expression itself ), concatenated using the ‘underscore’ symbol. For example, if the model receives as input the expression ( ( 2 1 - 6 ) * 2 ) it should produce as output the string 1 5 _ ( 2 1 - 6 ) . More formally, the solver can be defined as a function ∶ → × ( ) = ( , ) where ∈ is the nested input expression, ∈ is the innermost subexpression in , and ∈ is the result of .
The combiner receives the same string provided in input to the solver together with the solver’s output, i.e. ( , ), and produces −1 , i.e. the simplified version of where the sub-expression has been substituted by . −1 can be fed back into the system until the problem is completely solved (note that the combiner module is not required during training of the seq2seq model). Formally, the combiner can be defined as a function , , ( , )) = −1 .
Finally, the whole hybrid system can be defined as a function ℎ ∶ → , ( )) = −1 . Since the output domain of ℎ is the same as its input domain, it can be applied iteratively on its own output to solve arithmetical expressions step by step. Indeed, the system receives the expression represented as a sequence of characters as input and outputs a reduced version of the expression, which is fed back in the system unless the output only contains a positive or negative integer. ∶ × ( × ) → , ( ℎ ( ) = (
The solver is a standard Transformer encoder-decoder [
The purpose of the combiner is to deterministically replace part of the input string with the candidate solution proposed by the solver model. To enable the deterministic substitution in the combiner, the output of the solver must contain the expression and its numerical solution formatted according to a specific syntax. However, this may not be the case: we call ‘halted sequences’, the ones for which the solver output is not compliant with the required format. Indeed, in such cases the processing of the sequence should stop because there is no meaningful way to proceed with the simplification.
In order to reduce the number of halted sequences, we have chosen to employ a multi-output generation strategy. For each input expression, we generate outputs sampling from the distributions obtained from the softmaxed logits returned by the solver decoder. Since the Transformer generates the output in an auto-regressive fashion, for each token in the output sequence we sample from the distribution and feed back the updated sequence of output tokens to the decoder. The set of outputs is then given as input to the combiner, which first filters well-formed outputs, then selects the most frequently generated sequence, and finally applies the substitution of the target with the candidate in the input expression.
Data One of the goals in the design of our hybrid system is to combine the generalization capabilities of the solver with the deterministic nature of the combiner, which should allow learning by using a relatively small subset of the data. Intuitively, this subset should include the minimal amount of examples necessary for the model to learn the base solution step of a complex expression. We thus include in the training set only expressions with up to two nested operations between integers of up to two digits.
For simplicity, in all dataset splits and nesting levels, we build expressions that have only one operation for each nesting level. Therefore, the model never faces the ambiguous situation in which there are multiple operations that could be solved at the same time.
Since at test time the full hybrid system will be evaluated on expressions with up to 10 nested operations, it may happen that test expressions have intermediate or final results with more than two digits. We therefore take some measures to guarantee that the system will behave with more complex expressions. In particular, to ensure that the distribution of the expressions that will be used to test the model is coherent with the one that was used to train it, we limit both training and testing expressions to the ones that have intermediate and final results with at most two digits. Furthermore, we ensure that at training time the Transformer observes examples of a complete solution path of an arithmetical expression, i.e. all the steps leading to the final result. Hence, we ensure that the first-level simplification of some training samples involving two nested operations is also present in the training set.
To test out-of-distribution generalization more easily, we sample batches of data on-the-fly from the distribution described above, parameterized by the number of operations and size of operands in the expression. Given the data generation procedure and the number of expressions that could virtually be generated, the actual number of training examples observed by the model depends on the number of learning iterations. To ensure the separation of the training, validation and test splits, we use both a pre-computed split that ensures some of the training samples have a full solution path, as well as a hash-based split that sorts all remaining samples in three diferent splits on-the-fly.
Evaluation Metrics We use two metrics in the performance evaluation of all systems: character and sequence accuracy. Given a batch of target sequences, we define character accuracy as the percentage of correct characters in the output of a system, and sequence accuracy as the percentage of output sequences that match the target exactly. When measuring the performance of the solver and that of the hybrid system, these two metrics are applied to diferent kinds of output, as the solver and the hybrid system solve two diferent tasks. Both metrics, in the case of the hybrid system, are computed considering halted sequences as mistakes, i.e. the output sequence is assumed to be completely diferent from the target.
Model training The Transformer is trained in an auto-regressive regime, i.e. without teacher forcing. We have trained all models for 150k updates using Adam optimizer with a learning rate of 1 − 4 and batch size of 128.
To choose the best configuration for the solver hyperparameters we performed a random search on the number of heads and the dimensionality of embeddings. For both the Transformer encoder and decoder we have compared the performance of models with 4 and 8 heads, 256, 512 and 1024-dimensional embeddings, and 256, 512 and 1024-dimensional hidden feed-forward layer on the in-distribution validation set. We finally selected the solver model with 8 attention heads, a 1024-dimensional state and a 1024-dimensional feed-forward layer.
Using the multi-output generation strategy, the number of outputs generated for each input is an hyperparameter whose choice clearly requires trading model accuracy for speed. We compared the performance of the hybrid system on the solution of arithmetical expressions using = 1, 20, 40, 60, 80, 100 generated outputs per input. We have observed that sampling as few as 20 outputs for each input already guarantees much better results than a 1-shot output generation, especially in terms of surviving sequences. Nevertheless, we chose to generate 100 outputs as we observed marginal performance gains when continuing to increase the number of outputs.
Given the hybrid nature of our system, in order to measure its performance it is meaningful to consider both the trained solver module in isolation, and the hybrid system as a whole.
We also compare the performance of the hybrid system with that of a Transformer encoderdecoder trained to directly output the result of arithmetical expressions. Finally, we compare the ccsmall 57.2±17.5 92.1±15.2 99.2±1.3 97.6±4.9 98.4±4.5 99.5±1.2 99.9±0.2 99.3±0.9 98.1±2.8 98.9±1.6 rAmedium 72.2±17.4 96.8±5.4 99.7±1.0 100.0±0.0 100.0±0.0 99.7±0.8 100.0±0.0 100.0±0.1 99.5±1.5 99.6±1.2 ahClarge 78.5±12.6 96.7±4.6 98.8±2.8 100.0±0.0 98.5±4.5 99.5±1.6 99.9±0.2 99.9±0.1 97.6±6.2 99.5±0.8 cc small 28.1±25.4 82.3±27.8 98.5±2.6 93.5±12.9 97.1±8.0 99.2±2.1 99.4±1.5 98.4±1.9 96.2±6.1 97.4±3.5 eSqAlmaregdeium 5506..87±±2275..42 9932..62±±1111..08 9997..15±±25..70 10990..09±±00..30 10970..04±±07..50 9998..27±±13..83 10990..08±±00..40 9999..83±±01..60 9996..32±±19..68 9998..27±±22..41
We hypothesize that the solver module can leverage label positional encodings to achieve out-of-distribution generalization capacity on the sub-expression solution task. Therefore, the solver receives at test time complex arithmetical expressions with up to 10 nested operations, i.e. up to 8 more nested operations than seen during training. The goal of the model remains to output the result of the innermost expression contained in the input (replacement candidate) concatenated to the expression itself (replacement target).
The sequence accuracy of the solver on the sub-expression solution task is represented in Figure 2a, which shows that the use of Label Positional Encodings enables out-of-distribution generalization. We also report in Table 1 the performance of solver models with diferent embedding dimensionality to provide further insight on the impact of label positional encodings. Indeed, our results show that, independently of model size, a Transformer encoder-decoder using label positional encodings can generalize to out-of-distribution samples on this task.
Figure 2a shows that using Label Positional Encodings also leads to a lower performance on test expressions, especially on the nesting level 1. However, this has no impact on the functioning of the hybrid system when the multi-output generation strategy is used.
We then test the entire hybrid system on the arithmetic expressions resolution task.
Figure 2b shows the sequence accuracy of the hybrid system exploiting the multi-output generation strategy with 100 outputs per input on arithmetical expressions involving up to 10 nested operations. The performance metric shows that the combination of the architectural elements in our model allows to produce exact answers to harder problems than seen during training in a large fraction of cases. The slow performance decline is proportional to expression complexity, as it is due to the accumulation of errors committed by the solver module in several 0
Label PE Label PE (multi) Sinusoidal PE 2 4 6 Expression Nesting 8 10 2 4 6 Expression Nesting 8 10 (a) Performance of solver modules trained with(b) Performance of hybrid system, end-to-end and Label and Sinusoidal Positional Encodings. LLM baselines. Hybrid alt. refers to a hybrid Label PE (multi) refers to a solver that gen- system where the combiner selects the most erates 100 outputs per input and applies the frequent outputs before selecting well-formed same filtering rules applied by the combiner. outputs. iterations on the same expression. We have also experimented on a possible alternative combiner mechanism, where the selection of the most frequently generated output for a given input is done before filtering ill-formed outputs. Figure 2b shows that the method (Hybrid alt.) globally still achieves superior performance compared to baselines, but has worse performance with respect to the default combiner mechanism in harder problems due to the higher percentage of halted sequences, as shown in Table 2. The similar sequence accuracy of the two methods on expressions with fewer nested operations is due to the fact that the default combiner mechanism, despite halting fewer sequences, commits more semantic errors on the final results.
In the Appendix we provide further experimental evidence to shed light on the functioning of the proposed system. For completeness, we report character accuracy of the models we consider on the expressions resolution task in Table 3. In Table 4 we provide further insight on the impact of the number of outputs per input on both the accuracy of the hybrid system and the percentage of halted sequences. Finally, in Table 5 we report out-of-distribution performance metrics for hybrid systems built with diferently-sized solvers to provide experimental evidence on the impact of model size on the generalization capacity of the system.
To motivate empirically the presence of a deterministic component in our hybrid system, we compare the results of our system on the solution of arithmetical expressions with those obtained on the same problem by a Transformer trained to directly output the result of a given Hybrid 0.0±0.0 Hybrid alt. 0.1±0.3 arithmetical expression. Also in this case, we use label positional encodings on the Transformer encoder and decoder inputs, in order to control the efect of this architectural element on the performance of the system. The training hyperparameters and dataset splits are the same used to train the seq2seq part of the hybrid system. Furthermore, the Transformer has the same architecture and model size as the trained component in our system.
Figure 2b represents the sequence accuracy of the end-to-end trained system on this task. It is evident that, while on in-distribution samples the end-to-end trained Transformer has reasonably good performance, it nevertheless fails to generalize the learned solution process on longer and more complex expressions.
Finally, we compare our hybrid system with a Large Language Model (LLM), since these models
often achieve state-of-the-art performance in sophisticated reasoning tasks [
We prompt the model with an adapted version of our inputs, first showing the model an example of a correctly solved expression and then asking to complete the solution of a new expression. For example, given the expression ( ( ( 3 * 2 ) - 2 ) + 5 ) , a possible corresponding prompt could be ( ( 2 + 4 ) * 6 ) = 3 6 < E N D > \ n ( ( ( 3 * 2 ) - 2 ) + 5 ) = . We then require via API to stop the generation of the output string when the model outputs the < E N D > token. In this way, we ensure that the vast majority of the model outputs is the solution of the input expression proposed by the model.
Figure 2b shows the performance of the model in solving arithmetic expressions. Despite the gigantic size of the model and the amount of training data, the model cannot directly output the solution of complex arithmetical expressions.
In this work, we explored the idea that neural networks can learn to solve problems that require
composition of elementary solution steps, like arithmetic expressions, by iteratively applying a
learned substitution rule on the input string. Other works have recently explored similar ideas,
2https://platform.openai.com/docs/model-index-for-researchers
often in diferent kind of problems. In [
Recently, researchers have also focused on studying whether standard seq2seq models can generalize to out-of-distribution samples in compositional tasks. In [14] the authors show that relative positional encodings, carefully tuned early stopping and scaling of encodings can improve the performance of a Universal Transformer [15] on compositional generalization tasks. In a follow-up work [16], the same authors propose an approach to the solution of algorithmic tasks similar to the one we propose in this work. Their proposal consists of learning step-by-step solution strategies modifying the architecture of a Transformer encoder. Diferently from our case, the authors propose to recursively modify internal representations, rather than iteratively manipulating symbolic, external representations.
Another recent approach to exploit deep learning models to solve reasoning problems is to embed neural networks into existing automatic reasoning frameworks, such as logic or probabilistic programming languages [17, 18]. In such frameworks, systematic generalization is achieved by leveraging constructs in the pre-existing programming languages, supporting theoretical standpoints arguing that human cognition should be understood as a hybrid of neural and algorithmic mechanisms [19]. In our work, instead, we are interested in exploring the possibility that the solution process of symbolic reasoning problems can be implemented with neural systems, leveraging simpler additional mechanisms than the ones used in the works mentioned above, and by injecting learning biases in the neural system to allow the iterative solution of symbolic reasoning problems exploiting their recursive structure.
In this paper we have proposed a hybrid system that leverages the combination of a trained module and a deterministic one to achieve strong generalization abilities on the solution of simple arithmetical expressions. While we have only considered this specific task, it should be emphasized that the framework described in section 2 can be used to describe a more general class of symbolic problems where the solution can be derived iteratively. Indeed, one can easily imagine cases (such as symbolic mathematics) in which starting from the initial symbolic expression one can derive a tree - rather than a chain - of syntactically correct expressions. Furthermore, each expression could be the result of a more generic transformation than a solution or simplification step, which may even make the expression longer. As a consequence, the hybrid system we propose could in principle be adapted to a wider range of symbolic problems than the one considered here. In future work, we plan to explore this aspect, experimenting on tasks like symbolic mathematics, algorithmic tasks and program synthesis. [10] M. Setzler, S. Howland, L. A. Phillips, Recursive decoding: A situated cognition approach to compositional generation in grounded language understanding, CoRR abs/2201.11766 (2022). URL: https://arxiv.org/abs/2201.11766. a r X i v : 2 2 0 1 . 1 1 7 6 6 . [11] P. Shaw, J. Uszkoreit, A. Vaswani, Self-attention with relative position representations, in: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), Association for Computational Linguistics, New Orleans, Louisiana, 2018, pp. 464–468.
URL: https://aclanthology.org/N18-2074. doi:1 0 . 1 8 6 5 3 / v 1 / N 1 8 - 2 0 7 4 . [12] A. Trask, F. Hill, S. E. Reed, J. Rae, C. Dyer, P. Blunsom, Neural arithmetic logic units, in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018. URL: https://proceedings.neurips.cc/paper_files/paper/2018/file/ 0e64a7b00c83e3d22ce6b3acf2c582b6-Paper.pdf. [13] L. Ruiz, J. Ainslie, S. Ontañón, Iterative decoding for compositional generalization in transformers, CoRR abs/2110.04169 (2021). URL: https://arxiv.org/abs/2110.04169. a r X i v : 2 1 1 0 . 0 4 1 6 9 . [14] R. Csordás, K. Irie, J. Schmidhuber, The devil is in the detail: Simple tricks improve systematic generalization of transformers, in: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, Association for Computational Linguistics, Online and Punta Cana, Dominican Republic, 2021, pp. 619–634. URL: https: //aclanthology.org/2021.emnlp-main.49. doi:1 0 . 1 8 6 5 3 / v 1 / 2 0 2 1 . e m n l p - m a i n . 4 9 . [15] M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, L. Kaiser, Universal transformers, in: International Conference on Learning Representations, 2019. URL: https://openreview.net/ forum?id=HyzdRiR9Y7. [16] R. Csordás, K. Irie, J. Schmidhuber, The neural data router: Adaptive control flow in transformers improves systematic generalization, in: International Conference on Learning Representations, 2022. URL: https://openreview.net/forum?id=KBQP4A_J1K. [17] W.-Z. Dai, S. Muggleton, Abductive knowledge induction from raw data, in: Z.-H. Zhou (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, International Joint Conferences on Artificial Intelligence Organization, 2021, pp. 1845–1851. URL: https://doi.org/10.24963/ijcai.2021/254. doi:1 0 . 2 4 9 6 3 / i j c a i . 2 0 2 1 / 2 5 4 , main Track. [18] R. Manhaeve, S. Dumancic, A. Kimmig, T. Demeester, L. De Raedt, Deepproblog: Neural probabilistic logic programming, in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018. URL: https://proceedings.neurips.cc/paper_files/ paper/2018/file/dc5d637ed5e62c36ecb73b654b05ba2a-Paper.pdf. [19] G. F. Marcus, The Algebraic Mind, The MIT Press, 2001. URL: https://doi.org/10.7551/ mitpress/1187.001.0001. doi:1 0 . 7 5 5 1 / m i t p r e s s / 1 1 8 7 . 0 0 1 . 0 0 0 1 .
8 8 cc small 98.8±1.1 92.9±2.0 87.3±2.2 83.6±2.2 79.4±4.2 70.6±2.6 61.1±3.6 50.7±4.6 46.2±4.2 39.4±3.4 rAmedium 100.0±0.1 93.9±1.4 91.9±1.6 90.9±2.5 90.0±1.6 86.4±2.1 78.7±3.7 72.1±3.9 66.4±5.2 62.2±3.6 ahlarge 100.0±0.0 93.8±1.9 92.2±2.7 91.4±2.5 89.8±2.9 86.0±2.9 85.1±4.7 81.6±4.0 77.0±4.8 74.1±3.6 C cc small 97.3±2.4 84.2±4.0 74.8±4.0 66.5±4.8 61.8±6.0 50.2±5.7 45.8±4.2 33.4±5.2 30.1±2.9 23.0±4.1 Amedium 99.9±0.3 85.6±2.4 80.6±2.5 77.7±4.7 74.6±3.7 69.9±5.9 60.2±5.2 55.6±6.2 50.1±7.1 44.8±6.1 eSqlarge 100.0±0.0 89.8±3.2 85.2±4.0 83.8±2.7 80.5±3.6 74.8±3.2 74.6±6.9 69.0±6.0 63.8±6.5 63.4±5.3 dsmall lte medium a Hlarge