  Recent work on neural algorithmic reasoning has investigated the reasoning
capabilities of neural networks, effectively demonstrating they can learn to
execute classical algorithms on unseen data coming from the train distribution.
However, the performance of existing neural reasoners significantly degrades on
out-of-distribution (OOD) test data, where inputs have larger sizes. In this
work, we make an important observation: there are many different inputs for
which an algorithm will perform certain intermediate computations identically.
This insight allows us to develop data augmentation procedures that, given an
algorithm's intermediate trajectory, produce inputs for which the target
algorithm would have exactly the same next trajectory step. We ensure
invariance in the next-step prediction across such inputs, by employing a
self-supervised objective derived by our observation, formalised in a causal
graph. We prove that the resulting method, which we call Hint-ReLIC, improves
the OOD generalisation capabilities of the reasoner. We evaluate our method on
the CLRS algorithmic reasoning benchmark, where we show up to 3$\times$
improvements on the OOD test data.
