Uncertainty-Aware Neural Algorithmic Reasoning: Learning to Execute Algorithms over Belief-Valued Graphs

Neural Algorithmic Reasoning (NAR) aims to learn algorithmic execution with neural networks, but current models assume fully observable deterministic inputs and fail under real-world uncertainty. In practice, graph structures, measurements are noisy, partially observable, or edge weights are only approximate. In this paper, we introduce a framework for Uncertainty-Aware NAR (UANAR) that reformulates algorithmic execution from a deterministic mapping into a probabilistic inference task. We propose a belief-valued graph representation that aggregates noisy observations via Monte Carlo sampling, explicitly encoding input ambiguity through edge-wise means, variances, and existence probabilities. Furthermore, we improve the reasoning pipeline to predict calibrated distributions over algorithmic steps rather than point estimates. By optimizing proper scoring rules—specifically Negative Log-Likelihood—instead of hard accuracy, our model learns to quantify epistemic uncertainty, distinguishing between confident solutions and ambiguous evidence. Extensive evaluation demonstrates that our belief-valued graph representation with distributional decoding provides the first neural reasoner capable of principled uncertainty quantification. It performs reliably on clean data and remains well-calibrated under noisy and uncertain conditions.