Discrete Neural Algorithmic Reasoning
This addresses the generalization issue in neural algorithmic reasoning, which is incremental by building on existing methods to improve robustness.
The paper tackles the problem of neural algorithmic reasoning struggling with out-of-distribution generalization by forcing models to maintain execution trajectories as discrete states, achieving perfect test scores on multiple algorithmic problems.
Neural algorithmic reasoning aims to capture computations with neural networks by training models to imitate the execution of classical algorithms. While common architectures are expressive enough to contain the correct model in the weight space, current neural reasoners struggle to generalize well on out-of-distribution data. On the other hand, classical computations are not affected by distributional shifts as they can be described as transitions between discrete computational states. In this work, we propose to force neural reasoners to maintain the execution trajectory as a combination of finite predefined states. To achieve this, we separate discrete and continuous data flows and describe the interaction between them. Trained with supervision on the algorithm's state transitions, such models are able to perfectly align with the original algorithm. To show this, we evaluate our approach on multiple algorithmic problems and achieve perfect test scores both in single-task and multitask setups. Moreover, the proposed architectural choice allows us to prove the correctness of the learned algorithms for any test data.