acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Neural Algorithmic Reasoning, Graph Neural Networks, Noise and Uncertainty Aware, Probabilistic Graphs, Robust Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_iVT4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies neural algorithmic reasoning when graph inputs are noisy or partially observed. Instead of using a single adjacency and weight matrix, UANAR represents each graph through statistics from repeated noisy observations: mean edge weights, weight variances, and edge-existence frequencies. The method introduces a gated encoder with separate pathways for weight and structural uncertainty, uncertainty information in intermediate hints, and an additional loss that penalises confident incorrect predictions. The models are trained to recover algorithm outputs on the underlying clean graph. Experiments cover Floyd–Warshall, Bellman-Ford, Dijkstra, and Prim under weight corruption, missing edges, spurious edges, and combinations of these conditions. The paper reports improvements in accuracy and calibration, including comparisons where methods receive the same number of observations.

Critical strengths
  • The paper addresses a relevant limitation of neural algorithmic reasoning. Good performance on clean graphs does not establish that a model can recover useful answers from corrupted observations. Examining weight noise, missing edges, and spurious edges across four algorithms makes this problem concrete.
  • The equal-information comparison is a useful control. Table 5 shows that aggregation and denoising recover much of the performance lost by the deterministic baseline, but UANAR still improves over the denoising pipeline. This provides stronger evidence than a comparison against a single noisy input alone.
  • The paper acknowledges the limitations of the observation setting. Section 8.6 makes clear that repeated observations or a reliable noise model are needed and that single-observation deployment remains difficult.
Critical weaknesses
  • The contribution beyond learning from repeated observations needs stronger isolation. Table 4 shows that U-Base, which uses the belief inputs without the proposed additions, already increases mean accuracy significantly. This is a substantial result, but it also means that much of the headline improvement comes before the uncertainty-aware architectural components are added. Table 5 addresses this concern with equal-information baselines and shows a further improvement over denoising. However, that detailed comparison covers one Floyd-Warshall mixed-noise setting. The broader results would be more convincing if the strongest matched-information comparator were used consistently across algorithms and noise conditions. As presented, the evidence for richer observation statistics is stronger than the evidence for propagating uncertainty through the reasoning process.

  • The probabilistic interpretation of the graph representation needs more care. Eq. 2 defines pijp_{ij} as the frequency with which an edge appears in corrupted observations. This is not directly the probability that the edge exists in the underlying clean graph; that interpretation depends on the false +ve and false -ve processes. Likewise, observed weight variance measures variability in the measurements, rather than uncertainty in the estimated clean weight itself. Section 4.3 describes these quantities as separating aleatoric measurement uncertainty from epistemic structural uncertainty, but that distinction is not established by the construction. The representation can still be useful empirically. My concern is that the description as probabilistic inference over beliefs is stronger than what these statistics alone justify.

  • The calibration objective is an error-dependent confidence penalty, and its connection to calibration is insufficiently explained.

  • The uncertainty-propagating hints are not defined precisely enough. Since uncertainty propagation is one of the main proposed contributions, these details are necessary to assess the mechanism and reproduce it.

  • The headline architecture is difficult to identify from the main results. Table 4 reports several variants but does not include a model combining all three proposed additions. Different variants also perform best under different metrics. Meanwhile, Tables 2 and 3 report “UANAR (Ours)” without making the configuration explicit. I cannot tell from the main paper whether this denotes one fixed architecture or a configuration selected separately for each algorithm.

Questions for authors
  1. What is the standard deviation in Equation 9 calculated over, and where does the resulting quantity enter the next reasoning step?
  2. Is pijp_{ij} intended only as an empirical observation frequency, or as an estimate of clean-edge probability? If the latter, how are the corruption rates accounted for?
  3. Are comparisons against the strongest equal-information denoising baseline available beyond the Table 5 setting? These would help establish how broadly the improvement extends beyond observation aggregation.
Reviewer_AidLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • This paper proposes Uncertainty-Aware Neural Algorithmic Reasoning (UANAR) to improve the robustness and reliability of neural algorithm execution on noisy and partially observed graphs. The framework introduces belief-valued graph inputs that represent edge-weight statistics and edge-existence probabilities, together with a NTE, UPH, and an AECE.
  • Experiments across Floyd–Warshall, Bellman–Ford, Dijkstra, and Prim under 36 noise configurations report substantial improvements in accuracy and calibration over deterministic NAR baselines.
Critical strengths
  1. Meaningful problem formulation: The paper addresses an important limitation of existing NAR methods, which typically assume clean and fully observed graph inputs. Explicitly representing both edge-weight and structural uncertainty is a practically motivated approach.

  2. Extensive noise evaluation: The evaluation covers four algorithm families under diverse weight and structural corruption settings. The substantial improvements under false-positive edge noise are particularly notable.

  3. Equal-information comparisons and ablations: The authors include baselines using the same number of noisy observations and examine the effects of belief inputs and individual architectural components. These experiments help distinguish the benefits of richer input representations from those of the proposed model design.

Critical weaknesses
  1. Validity of noise generation and belief construction: Alg.1 does not clearly mask edge weights when false-negative edges are removed. As written, the belief representation may retain weights of unobserved edges, potentially providing information unavailable in a genuine partial-observation setting. The outlier noise definitions also differ between Section 4.2 and Alg.1, raising reproducibility concerns.

  2. Unclear contributions of the combined components: Appendix A.8 shows that U-Full, which combines the proposed components, does not consistently outperform simpler variants. Moreover, the headline results in Table 2 match the best-performing variants for individual algorithms. This raises questions about model selection and whether each component provides a consistent independent contribution.

  3. Limitations of the calibration objective: The proposed AECE loss appears to penalize confidence on incorrect predictions rather than directly optimizing ECE. Since it relies on argmax-based correctness indicators and a hard threshold, the implementation of gradient handling and optimization stability should be clarified. Comparisons with standard calibration approaches, such as temperature scaling, are also missing.

  4. Missing strong classical baseline: Although the equal-information comparisons are valuable, the paper does not evaluate a classical algorithm applied to a graph reconstructed from the aggregated belief observations. MC-Exact instead runs the exact algorithm independently on noisy graph realizations and aggregates the outputs. A denoised-graph-plus-exact-solver baseline would better isolate the benefit of neural algorithmic reasoning.

  5. Limited generalizability: The main experiments rely on synthetic 16-node Erdős–Rényi graphs, and absolute accuracy declines substantially for some algorithms under size extrapolation. The reliance on repeated observations or an accurate noise model further limits applicability to realistic partially observed graphs.

Questions for authors
  1. When false-negative edges are removed in Alg. 1, are their associated weights also masked before computing belief statistics? Which outlier corruption procedure was actually used, given the discrepancy between Section 4.2 and Alg.1?

  2. Do the headline results in Table 2 correspond to U-Full or to the best-performing variant selected separately for each algorithm? Why does U-Full underperform simpler configurations in several settings?

  3. How are gradients handled through the argmax-based correctness indicators and thresholding in AECE? Could the authors compare AECE with temperature scaling or other differentiable calibration objectives?

  4. Could the authors evaluate an exact classical solver applied to a graph reconstructed from the same K noisy observations? This would help distinguish improved graph reconstruction from the benefits of uncertainty-aware neural reasoning.

  5. What distribution and dimensions are used to compute the standard deviation in UPH? Why do some reported results remain identical between U-UPH and U-Base?

  6. How well does UANAR perform when repeated observations are unavailable or the noise model is misspecified? Can the approach be evaluated on more diverse graph structures and larger instances?

Reviewer_ESyLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Uncertainty-Aware Neural Algorithmic Reasoning to predict clean algorithm outputs from repeated noisy graph observations. It summarizes edge weights and connectivity through means, variances, and observation frequencies, then adds a gated encoder, uncertainty hints, and a calibration penalty to a CLRS-style reasoner. Experiments cover Floyd–Warshall, Bellman–Ford, Dijkstra, and Prim, including corruption robustness, calibration, ablations, and larger graphs.

Critical strengths
  1. The framework combines edge-weight means, variances, and observation frequencies with CLRS-style supervision, providing a concrete formulation for learning algorithm execution from repeated noisy graph observations (Sections 4–5).

  2. Table 5 reports 87.1% accuracy and expected calibration error 0.024 for UANAR versus 79.2% and 0.057 for Denoiser -> NAR using the same 16 observations. Recomputing the supplied Floyd–Warshall CSV also reproduces Table 4's mean accuracies of 71.1% and 85.1%.

Critical weaknesses
  1. The observation and inference protocols are not consistently specified. Section 4.2 defines outliers as uniform weight replacement, whereas Algorithm 1 adds five times Gaussian noise. The latter produces no corruption at zero Gaussian severity, despite the isolated-outlier results in Table 19. Separately, notebook cell 13 constructs the initial distance hint D[0] from the clean graph; cell 24 encodes it at the first prediction step when encoded_decoded hints are used. A different configuration could avoid this exposure, but the saved Kruskal configuration does not identify the reported Floyd–Warshall setup. The actual noise and inference settings therefore need to be established.

  2. The reported uncertainty and larger-graph results need reconciliation. Appendix A.7 specifies five independently trained runs. For [email protected] over 36 conditions, the smallest nonzero five-run sample standard deviation is about 1.24 percentage points, incompatible with 0.26 in Table 2. This discrepancy is independent of the notebook's purpose or default seed count. Table 13 also reports 9.76% accuracy for a 32-node configuration, below the worst-case values of 13.4% and 18.4% in Tables 12 and 14. Different models or condition sets could explain the latter difference, but must be identified. The supplied CSVs reproduce point estimates without resolving these issues.

Questions for authors
  1. Which outlier process and inference configuration generated the reported results? Please reconcile Section 4.2 with Algorithm 1 and identify the code version used for Floyd–Warshall, including whether clean initial D and connectivity hints were encoded. An implementation avoiding this exposure would resolve the inference concern; evaluations using the affected path would need to be repeated with inputs derived exclusively from noisy observations.

  2. Please provide the five per-run [email protected] counts and identify the models and condition sets underlying Tables 12–14. How do these explain the reported error bars and worst-case accuracies? Corrected statistics and consistent experimental details could resolve the reporting concerns and materially improve the assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.