Certified Rule-Outs in Catalytic Reaction Networks with a Solver-Directed DFT Budget

Computational catalysis often needs to answer a yes-or-no question, not to find an energy. Can this catalyst make methanol under these conditions, or can that possibility be ruled out? Answering it means checking a reaction network: a combinatorial web of intermediates and elementary steps, each step guarded by an activation barrier. The reference method for computing those barriers is density functional theory (DFT), a quantum-mechanical method that computes energies from the electron density, combined with nudged elastic band (NEB) searches for the saddle point between two states. On a large surface slab, one such search can take days.

Current workflows mostly spend this budget by statistical priority. A surrogate model guesses barriers, and DFT is run where the surrogate is unsure or where it predicts the rate-limiting step. The weakness shows up in the best-known case. On syngas over Rh(111), the scaling-relation/Gaussian-process loop cut DFT transition-state work by 95% but still could not rule out methanol at 90% confidence. We propose to treat "is product P reachable?" as a satisfiability question. A constraint solver encodes the chemistry that must hold for any valid mechanism: mass balance, catalytic site regeneration, and site availability for co-adsorbed species. Barrier evaluation is delegated to an outside specialist that answers in calibrated intervals. When the solver proves that no mechanism exists, the conflicting set of constraints it returns (the "unsatisfiable core") names exactly which few steps must be confirmed with DFT to turn the proof into a DFT-grade certificate.

Core Claim

Sound rule-outs need a cut. Every admissible mechanism to P must pass through at least one step that is shown to be too slow. A conflict-driven solver finds a small cut directly and spends DFT only on the steps in it. Uncertainty-ranked active learning spends DFT on the steps that look most uncertain or most rate-limiting. Those steps are generally not the ones whose verification closes the question.

We claim this yields correct reachable/unreachable decisions with substantially fewer DFT NEB calls. The gain should appear specifically on queries where admissibility is not plain graph reachability. One example is a step that consumes two adsorbates, which makes the network a hypergraph. Others are catalytic cycles that must return the active site, and steps that need a vacancy or a free neighboring site. On queries that reduce to ordinary graph reachability, we predict no advantage over a simple shortest-path-style algorithm. We treat that prediction as part of the claim, not a weakness to hide.

The mechanism comes from theory resolution. Stickel's theory resolution lets a general prover hand literals of a background theory to a dedicated decision procedure without losing refutational completeness. Miller and Schubert showed that such specialists can be fast procedural code over non-logical data structures. Both assume the specialist is exact. Ours is not: a machine-learned barrier predictor is approximate, and even DFT-NEB only reports the saddle it happened to find. That case of approximate, black-box theory delegation is precisely where the file notes that classical guarantees break. Our contribution is a delegation protocol that states what is guaranteed under approximation and escalates to the expensive exact-ish oracle only where the proof depends on it.

Research Program

Encoding. Elementary steps are generated by bond-change rules over atom-connectivity matrices, following the molecular-graph reaction-network method. That method enumerates intermediates and prunes them with a hard-coded minimum-chemical-distance heuristic before running DFT transition-state searches. We reuse its generator, extended with surface-site labels, including vacancy sites. We replace its heuristic pruning with declarative constraints in an SMT solver (Z3), where SMT means satisfiability modulo theories: SAT plus arithmetic.

Each step $s$ gets a Boolean "used" variable. Integer variables track adsorbate and site counts. The constraints require four things: the target product is formed; every consumed intermediate is produced by some used step or is a feed; the net site change over a closed cycle is zero; and steps requiring a neighboring free site or a vacancy are allowed only when one is available under a bounded coverage. A query also fixes a barrier ceiling $B$ that sets the kinetic criterion. A mechanism is admissible only if every used step has barrier below $B$.

This max-barrier criterion is a deliberate simplification of real kinetics. Extending it to an energetic-span criterion is a later step.

The barrier specialist. For a step $s$, the cheap specialist runs an ML-accelerated NEB with an OC20-pretrained graph network, in the style of CatTSunami. It returns an interval $[\ell_s, u_s]$ rather than a point. The interval width is set by split-conformal calibration on held-out OC20NEB paths, so that the true DFT barrier lies inside with a chosen coverage $1-\alpha$. The specialist then reports one of three outcomes:

  • If $\ell_s \ge B$, it emits the lemma "step $s$ is not used."
  • If $u_s < B$, it marks the step feasible.
  • Otherwise the step is "straddling" and stays undecided.

An NEB that fails to converge is reported as undecided, never as a refutation. This deliberately departs from the tempting move of treating failed calculations as conflicts. A failed calculation is evidence about the optimizer, not about the chemistry.

The loop. The coordinator solves optimistically, treating straddling steps as allowed. Two outcomes are possible:

  • UNSAT (no admissible mechanism). P is ruled out at calibrated confidence. The unsatisfiable core lists the step lemmas the proof used, and only those steps go to DFT-NEB. If DFT confirms them, the rule-out holds relative to the functional and the saddle searches performed. If DFT overturns one, its lemma is withdrawn and the loop continues.
  • SAT (a candidate mechanism exists). The straddling or ML-only steps on the witness path are escalated to DFT. The step with the widest interval goes first.

The loop repeats until a DFT-verified witness or a DFT-verified core exists. This is a counterexample-guided refinement loop: the proposal is checked, the counterexample or proof is examined, and only the parts it depends on are refined. A key design choice is that the core is minimized before any DFT is spent. Core extraction is cheap relative to DFT, but becomes expensive with non-linear arithmetic, so we keep all theory content linear integer.

Honest limits of the certificate. A DFT-NEB barrier above $B$ is not a proof that no lower saddle exists. A different adsorbate orientation can open a lower path, which is exactly how the active-learning force-field protocol found a vacancy-mediated route on In₂O₃ with a 40% lower barrier. Our certificates are therefore conditional on the set of orientations screened for each core step. We spend that protocol's permutation screening only on core steps, where it buys the most.

Spin-polarized metals, where pretrained graph networks are known to fail, get wider calibrated intervals or are routed straight to DFT. We do not claim to fix that failure.

Baselines

The naive reference is exhaustive verification: run the cheap ML-NEB on every generated step, then run DFT-NEB on every step whose ML barrier is within a fixed margin of $B$. This gives the cost a careful practitioner pays today without any search logic. It also supplies the reference decisions for scoring correctness on small networks.

The strongest published method on the barrier-accuracy axis is CatTSunami. Its hybrid workflow relaxes endpoints with DFT, runs NEB with ML, and checks the saddle with one DFT single point. That paper reports a 91% success rate at finding transition states within 0.1 eV of DFT on OC20NEB, a 28× speedup, and a 0.04 eV barrier error on a CO hydrogenation network versus 0.20 eV for BEP scaling relations. Here BEP is the Brønsted-Evans-Polanyi linear relation between barrier and reaction energy. We run it in "All-ML" mode over the whole network, followed by DFT verification of the predicted lowest-barrier path to each product. It shares our cheap specialist, so any difference comes from how DFT is allocated.

The strongest method on the DFT-allocation axis is the Gaussian-process/BEP active-learning loop. It reports 60% fewer intermediate and 95% fewer transition-state DFT calculations on syngas/Rh(111), but no confident methanol rule-out at 90%. We reimplement it with the same DFT functional (BEEF-vdW), the same step set, and the same DFT budget as our method.

The baseline we consider most dangerous is optimistic-bound graph reachability, our own construction. It runs a bottleneck-path search using the lower interval bounds $\ell_s$, then DFT-verifies the edges of the minimum cut separating feeds from P. For queries that are pure reachability on an ordinary graph, this is polynomial-time and should match our method exactly.

All methods receive identical step sets, the same pretrained network and calibration data, and the same DFT code and functional. They are compared at matched DFT NEB budgets. The hyperparameters of each baseline are tuned on one held-out network not used for scoring.

Two ablations isolate the key ingredients. The first keeps the solver but picks which straddling step to verify at random instead of by core membership. The second keeps core-guided selection but drops the stoichiometric and site constraints, leaving plain graph reachability. If the second ablation matches the full system, the symbolic layer is not earning its keep.

Beating the field means two things. On site- and stoichiometry-constrained queries, we must reach the reference decision on at least as many queries as every baseline while using clearly fewer DFT NEB calls. On the Rh(111) methanol question, we must produce a definite verdict under a budget at which the GP loop leaves it open. For decision-level DFT call counts on rule-out queries, we found no reported result on Lacuna for any baseline, so these numbers will be produced here.

Why not just…?

Why not just do uncertainty-driven active learning on barriers? Active learning reduces barrier error where the model is uncertain, but a rule-out depends on steps that are confidently high, not uncertain. The Rh(111) loop shows the gap: it achieved large savings and still left methanol undecided at 90% confidence. The random-selection ablation and the GP baseline measure the gap directly. If the GP loop reaches the same verdicts at equal budget, our claim fails.

Why not just run All-ML exhaustively and verify the best path? It is cheap: CatTSunami reports a 1500× speedup, 12 GPU days versus 52 GPU years. But verifying the predicted best path only establishes reachability. A rule-out requires showing that all paths are blocked, and a point-estimate model gives no account of which blocked steps are load-bearing. A 9% failure rate at the 0.1 eV level matters exactly near the ceiling $B$. This baseline will likely win on queries whose answer is "reachable." We expect to beat it only on unreachable queries, and we will report results split by answer type.

Why not just use graph search with a min-cut instead of an SMT solver? This is the real threat, and for ordinary graph reachability we concede it: the optimistic-bound min-cut baseline should tie us. The solver is justified only when admissibility involves joint conditions that a simple graph cannot express: steps consuming two adsorbates, site regeneration over a cycle, and vacancy or neighbor-site availability. Under these, reachability resembles Petri-net coverability rather than path search. The experiments therefore stratify queries by whether such constraints bind. If the graph-only ablation matches the full system on the constrained stratum, we will conclude that the declarative layer is unnecessary.

Proposed Experiments

Calibration. Interval coverage is set on a split of OC20NEB's 932 RPBE NEB calculations. We report empirical coverage separately for the in-domain half and the out-of-domain half, because a rule-out at nominal $\alpha$ is meaningless if out-of-domain coverage collapses. For the organic-chemistry setting, a Transition1x-trained reactive potential plays the cheap specialist. Its reported barrier error is 0.075 eV, versus 0.495 eV for a model trained on equilibrium-only data.

Test networks. The main experiment uses four reaction networks:

  • syngas on Rh(111), with the methanol question as the headline query;
  • the CatTSunami CO hydrogenation network;
  • cobalt-catalyzed hydroformylation from the graph-network paper, which needed 36 DFT transition-state searches there;
  • CO₂ hydrogenation on In₂O₃.

On each network we issue product-reachability queries across a sweep of ceilings $B$. Each query is labeled with reference decisions from exhaustive verification. The main metrics are the decision accuracy against those labels, the number of DFT NEB calls to decision, and the empirical false-rule-out rate compared with $\alpha$.

Decisive checks. Three checks decide whether the claim holds.

  1. Stratified advantage. The full system must use fewer DFT calls than the min-cut and graph-only baselines on site- and stoichiometry-constrained queries, and must tie them on unconstrained ones.
  2. Recall on In₂O₃. With vacancy sites encoded, the coordinator must not rule out the vacancy-mediated route that manual intermediates missed. A spurious rule-out there would expose the orientation-conditional weakness of our certificates.
  3. Rh(111) verdict. The system must deliver a DFT-verified verdict on methanol over Rh(111), either a witness mechanism or a core, at or below the DFT budget the GP loop used.