Training-free, architecture-independent soundness certificates for neural algorithmic reasoning.
Neural algorithmic reasoners (NARs) trained on CLRS degrade out-of-distribution, and their softmax confidence does not reliably flag when an answer is wrong. This repository implements lightweight, post-hoc certificates that verify a model's predicted output against the algorithm's own optimality conditions. The certificate treats the model as a black box (architecture-independent) and requires no extra training (training-free).
When a certificate is clean, the output provably satisfies the algorithm's optimality conditions; empirically this gives P(correct | clean) = 1.000 across every architecture, algorithm, and out-of-distribution size we test. Confidence- and conformal-prediction baselines, by contrast, lose soundness as graphs grow.
Our prediction regarding the sharp threshold of Hamiltonian cycle failure was preregistered before collecting any Hamiltonian-cycle data. For reviewers verifying the pre-registration hash, we have uploaded an archival snapshot of the complete git repository (including the .git directory) to Zenodo at: https://doi.org/10.5281/zenodo.20723200.
See PREREGISTRATION.md for more details.
Given a model's predicted predecessor array pi, the verifier checks algorithm-specific conditions:
- Shortest paths (Bellman-Ford, Dijkstra). (1)
piforms a valid tree rooted at the source over the reachable set (no broken pointers, no cycles), and (2) no edge is relaxable:d[u] + w(u, v) >= d[v]for every edge. If both hold, the induced distances are provably optimal. - Minimum spanning tree (Prim). (1)
piforms a valid spanning structure, and (2) the cut/cycle property holds: no non-tree edge is lighter than the heaviest edge on the tree path between its endpoints.
A run with zero violations is clean; the continuous violation score (relax_rate for SSSP, viol_score for MST) is used as a ranking signal for the AUROC comparison against confidence.
| Signal | P(correct | clean) | Failure-detection AUROC |
|---|---|---|
| Certificate (this work) | 1.000 (all sizes) | ≈ 0.99 |
| Confidence monitor | collapses OOD | ≈ 0.73 – 0.78 |
algorithmic-guardrails/
├── configs/ # YAML configs
├── figures/ # generated paper figures
├── src/ag/ # Python modules (core package)
│ ├── env.py # force CPU execution + seed RNGs
│ ├── data.py # CLRS train/eval sampler construction
│ ├── train.py # train a NAR model from a config
│ ├── dump_certificate.py # soundness certificate — shortest paths
│ ├── dump_certificate_mst.py # soundness certificate — MST
│ ├── conformal_baseline.py # LTT conformal selective-risk baseline
│ ├── make_figures.py # generate fig1-fig5
│ ├── sat/ # 3-SAT experiments
│ ├── feas/ # 3-Colouring experiments
│ ├── opt/ # MIS experiments
│ ├── hamiltonian/ # Hamiltonian cycle experiments
│ ├── sssp_t/ # GPS-Transformer experiments
│ └── vc_*.py # Vertex Cover experiments
├── reproduce_all.sh # master reproducibility script
├── make_figures.py # generate remaining figures
├── requirements.txt # pip dependencies
├── PREREGISTRATION.md # preregistration hash details
├── LICENSE # Apache-2.0
└── NOTICE
checkpoints/ and data/ are git-ignored. The reproduce_all.sh pipeline generates the models and data splits.
Python 3.10+.
python -m venv .venv
source .venv/bin/activate # Windows PowerShell: .venv\Scripts\Activate.ps1
pip install -r requirements.txtAll scripts read the ag package from src/, and the code runs on CPU. Set these once per shell:
export PYTHONPATH=src
export JAX_PLATFORMS=cpu
export XLA_PYTHON_CLIENT_PREALLOCATE=false
# Windows PowerShell equivalent
# $env:PYTHONPATH="src"; $env:JAX_PLATFORMS="cpu"; $env:XLA_PYTHON_CLIENT_PREALLOCATE="false"Each experiment requires running a combination of data generation, model training, and evaluation scripts. We provide a single bash script that runs the entire pipeline end-to-end:
bash reproduce_all.shAlternatively, you can run the modules for each problem family independently as documented below:
# Example for Bellman-Ford MPNN
python -m ag.train configs/bellman_ford_mpnn.yaml 42
python -m ag.dump_certificate configs/bellman_ford_mpnn.yaml 42
python -m ag.dump_confidence_monitor configs/bellman_ford_mpnn.yaml 42Located in src/ag/vc_*.py.
python -m ag.vc_data
python -m ag.vc_train 42
python -m ag.vc_certificate 42Located in src/ag/feas/.
python -m ag.feas.dataset
python -m ag.feas.train # iterates seeds 42-51 internally
python -m ag.feas.eval_shift # certified yield under size/density shiftLocated in src/ag/opt/.
python -m ag.opt.mis
python -m ag.opt.train_mis # iterates seeds 42-51 internally
python -m ag.opt.eval_mis # iterates seeds 42-51 internallyLocated in src/ag/sat/.
python -m ag.sat.data
python -m ag.sat.train 42 # repeat for seeds 42-51
python -m ag.sat.eval_sweep # NeuroSAT certificate sweep (loads seeds 42-51)Located in src/ag/hamiltonian/.
python -m ag.hamiltonian.train_ham # manages its own seeds internally
python -m ag.hamiltonian.eval_sweep # optional flag: --proposer {gnn,random}Located in src/ag/sssp_t/.
# Self-contained: exports CLRS data, trains seeds 42-51, evaluates, writes outputs.
python -m ag.sssp_t.run_task_cOnce all data is generated and evaluated, run the figure plotting scripts.
python -m ag.make_figures generates figures/fig1_pareto to fig5_confidently_wrong.
python make_figures.py generates fig_density_U.pdf, fig_er_family.pdf, fig_mis.pdf, fig_size_curve.pdf, fig_uq_vs_cert.pdf.
python -m ag.conformal_baseline
python -m ag.conformal_strong
python -m ag.aggregate_seeds
python -m ag.aggregate_confidence_seeds mst_prim mpnn
python -m ag.make_figures
python make_figures.py
python -m ag.conformal_figure
python -m ag.plots.yield_vs_phi
python -m ag.separation_table@misc{sadhu2026algoguardrails,
title = {Algorithmic Guardrails: Training-Free, Architecture-Independent
Soundness Certificates for Neural Algorithmic Reasoning},
author = {Sadhu, Ankan},
year = {2026},
doi = {10.5281/zenodo.20723200},
note = {Preprint}
}Apache-2.0. See LICENSE and NOTICE. This project depends on the CLRS benchmark (also Apache-2.0).