Discrete Neural Algorithmic Reasoning
Gleb Rodionov Liudmila Prokhorenkova
Neural algorithmic reasoning aims to capture computations with neural
networks via learning the models to imitate the execution of classical
algorithms. While common architectures are expressive enough to contain the
correct model in the weights space, current neural reasoners are struggling to
generalize well on out-of-distribution data. On the other hand, classical
computations are not affected by distribution 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. 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 the SALSA-CLRS benchmark,
where we get perfect test scores for all tasks. Moreover, the proposed
architectural choice allows us to prove the correctness of the learned
algorithms for any test data.