On the Markov Property of Neural Algorithmic Reasoning: Analyses and
  Methods
Montgomery Bohde Meng Liu Alexandra Saxton Shuiwang Ji
Neural algorithmic reasoning is an emerging research direction that endows
neural networks with the ability to mimic algorithmic executions step-by-step.
A common paradigm in existing designs involves the use of historical embeddings
in predicting the results of future execution steps. Our observation in this
work is that such historical dependence intrinsically contradicts the Markov
nature of algorithmic reasoning tasks. Based on this motivation, we present our
ForgetNet, which does not use historical embeddings and thus is consistent with
the Markov nature of the tasks. To address challenges in training ForgetNet at
early stages, we further introduce G-ForgetNet, which uses a gating mechanism
to allow for the selective integration of historical embeddings. Such an
enhanced capability provides valuable computational pathways during the model's
early training phase. Our extensive experiments, based on the CLRS-30
algorithmic reasoning benchmark, demonstrate that both ForgetNet and
G-ForgetNet achieve better generalization capability than existing methods.
Furthermore, we investigate the behavior of the gating mechanism, highlighting
its degree of alignment with our intuitions and its effectiveness for robust
performance.