On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods

arXiv:2403.04929v1 Announce Type: new
Abstract: 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 …

abstract arxiv cs.ai cs.lg cs.ne designs embeddings future markov networks neural networks observation paradigm property reasoning research results step-by-step type