Certified Adversarial Training for Neural Networks That Reason with Default Rules

Many perception systems end in a rule layer. A network reads the scene, and hand-written rules turn its outputs into decisions. Many useful rules are defaults that fire when something has not been established: "treat the lane as free unless an obstacle is detected", or "a position is winning if some move leads to a position that is not winning". Adversarial training teaches the network to hold up under small worst-case input perturbations. Today it can certify or harden only the network itself, or rule layers that are acyclic and free of such negation. When rules refer back to themselves through "not", nobody knows how to compute guaranteed bounds on the final conclusions over a whole perturbation ball, let alone train against those bounds.

The proposal is to use approximation fixpoint theory for this. Approximation fixpoint theory (AFT) is an algebraic toolkit from logic programming that evaluates rules with negation on intervals of truth ("at least this true, at most this true") rather than on single values, and it guarantees that this evaluation converges. Interval bound propagation, the standard certified-robustness tool, already produces exactly such intervals for the network's outputs over a perturbation ball. We claim the two fit together directly. The perception bounds become the starting interval for AFT's operator. AFT's least fixpoint then yields sound certified bounds on every rule conclusion, including conclusions reached through cyclic negation. The whole computation is piecewise-linear and differentiable, so it can serve as the inner "worst case" of adversarial training.

Core Claim

Let a neural network output truth degrees for base facts, and let a fuzzy logic program with negation-as-failure derive further atoms from them. For each base fact $i$, interval bound propagation over the $\ell_\infty$ ball of radius $\epsilon$ gives a lower and upper bound $[l_i, u_i]$ on its truth degree. AFT's approximator $A$ maps a pair $(x, y)$ of lower and upper truth assignments to a refined pair. It evaluates a rule body's lower bound using $x$ for positive literals and $1-y$ for negated ones, and its upper bound using $y$ for positive literals and $1-x$ for negated ones:

$$A(x,y) = \big(\, T^{\text{low}}(x, 1-y),\; T^{\text{up}}(y, 1-x) \,\big),$$

where $T^{\text{low}}$ and $T^{\text{up}}$ apply the program's t-norm and aggregation rules with the indicated arguments, and base facts are clamped to $[l_i, u_i]$.

The central claim has three parts. First, the well-founded (least precision) fixpoint of $A$, seeded this way, contains the program's well-founded and stable-model truth values for every input in the ball. This follows from the known result that the well-founded fixpoint lies below every stable model in the precision order, proved for fuzzy programs in Approximation Fixpoint Theory as a Unifying Framework for Fuzzy Logic Programming Semantics. It also needs a lemma we will prove: $A$ is monotone in the base-fact bounds, so widening the input interval only widens the output interval. Second, any finite number of iterations from the bottom of the precision order is still sound, only less tight. This is the same anytime property that Knowledge compilation of logic programs using approximation fixpoint theory exploits symbolically. Third, training on the resulting worst-case endpoints gives models whose rule-level conclusions are certifiably robust, in regimes where no existing method gives any certificate.

For a target atom $q$ with label $c \in \{0,1\}$, the certified loss uses the pessimistic endpoint of $q$'s interval $[\underline{q}_\epsilon, \overline{q}_\epsilon]$:

$$\mathcal{L}_{\text{cert}}(\theta) = -\,c \log \underline{q}_\epsilon(\theta) - (1-c)\log\big(1 - \overline{q}_\epsilon(\theta)\big),$$

mixed with clean cross-entropy and an $\epsilon$ ramp-up schedule, as in standard interval-bound certified training. The output interval can also leave an atom genuinely undefined, for example a drawn game position. In that case the gap $\overline{q}-\underline{q}$ is an honest abstention signal rather than a failure.

Relation to Prior Work

Four lines of work motivate the gap. Certified Robustness for Deep Equilibrium Models via Interval Bound Propagation solves an augmented fixed-point equation for values and interval bounds of implicit networks. It shows that fixpoint formulations can keep bounds from exploding, but it relies on contraction in real vector spaces and handles only linear maps plus activations, not rules. We borrow its lesson that bounds should be computed as a fixpoint, but our convergence comes from monotonicity in the precision order rather than from contraction. A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification compiles network plus symbolic layer into one graph and runs relaxation verifiers on it. That approach is post-hoc, it reports loose bounds as the symbolic part grows, and it presupposes an acyclic graph. Our method trains rather than only verifies, and it handles cycles. Adversarially Regularising Neural NLI Models to Integrate Logical Background Knowledge runs a true minimax loop against a logical inconsistency loss. It is limited to monotone first-order rules and heuristic sentence search, and it gives no guarantee over a perturbation set. ROAD-R: the autonomous driving dataset with logical requirements shows that soft constraint losses leave violations and that only a non-differentiable MaxSAT post-processor guarantees compliance, all on clean data.

Two works constrain the design. Semantic Loss Functions for Neuro-Symbolic Structured Prediction gives exact constraint gradients through compiled circuits but only for classical Boolean constraints, and its compilation can blow up. We therefore avoid circuit compilation and work with the operator directly. The fuzzy AFT paper restricts itself to involutive negations, so we commit to $1-x$ negation with Łukasiewicz or product connectives and leave Gödel negation out of scope. The method itself comes from AFT: the approximator, the alternating well-founded computation, and the "ultimate" approximator, which on the toy program $p \leftarrow p,\; p \leftarrow \sim p$ yields a lower bound of 0.5 where the standard approximator yields 0. That example tells us tightness depends on which approximator we pick, which matters directly for certified accuracy.

Research Program

The theory work has two parts. One is the soundness lemma: monotonicity of the seeded approximator in base-fact intervals, combined with the precision-order bound from fuzzy AFT, so that the well-founded interval covers every stable model for every point in the ball. The other is a stratification result: on stratified programs, the AFT bounds coincide with layer-by-layer interval propagation through the unrolled rule graph. That second result is important because it tells us where the method adds nothing. We also characterize which atoms are certifiable at all. An atom left undefined at $\epsilon = 0$ can never be certified, which separates logical ambiguity from adversarial fragility.

The system will be a differentiable layer that takes base-fact intervals and returns derived-atom intervals. It will run the alternating lower and upper least-fixpoint computations for a fixed budget of $K$ outer iterations, which are sound at any $K$, and backpropagate through the unrolled iterations. As an alternative, it will use implicit differentiation at the fixpoint, following the equilibrium-model approach. The layer will offer three approximators in increasing precision and cost. The Kripke-Kleene approximator is plain three-valued interval iteration of the rules. The well-founded approximator is the standard AFT least fixpoint. The ultimate approximator is tractable only on small rule bodies. This layer then sits on top of interval-bound or CROWN-style bounds from the perception network.

The benchmarks must contain cyclic negation; otherwise the comparison with unrolled verification is a tie by our own stratification result. We will build three. Visual Win-Move is a synthetic graph game. A convolutional network reads edge glyphs, MNIST digits placed on a grid, to recover a move graph. Labels come from the classic well-founded program "win(X) if move(X,Y) and not win(Y)", whose cycles produce drawn positions. ROAD-R-Default keeps ROAD-R's 243 constraints and adds a small set of hand-written default rules with mutual negation over agent roles and actions, such as "moving unless stopped is supported, stopped unless moving is supported", with targets recomputed by an exact well-founded solver. Multi-digit MNIST addition is fully stratified and serves as a negative control.

Baselines

The naive reference point is a network trained with ordinary cross-entropy, with rules applied at test time by an exact well-founded solver on its point predictions. It shows how badly undefended rule conclusions break under PGD and what clean accuracy costs us. On ROAD-R the clean reference is the unconstrained RCGRU at 30.78 frame mean average precision, and the best clean system is CLCO-RCGRU at 31.81 with 100% compliance (ROAD-R). We will reproduce both before adding attacks.

The strongest empirical competitor is PGD adversarial training with ROAD-R's fuzzy constrained loss, followed by exact post-hoc rule solving: MaxHS on the flat constraints plus the well-founded solver for the defaults. This combines the best clean-data compliance method with the standard robustness method, and it may well win on empirical robust accuracy. It will receive the same perception backbone, epochs, and hyperparameter search budget as our method, measured in GPU-hours rather than steps. It must be attacked adaptively, with PGD through the pre-solver outputs and with gradient-free attacks on the full pipeline, so that the non-differentiable solver cannot pass gradient masking off as robustness. We beat it if we match its PGD robust accuracy within two points while providing certificates it cannot. We also beat it if we exceed it under the adaptive gradient-free attack.

The strongest certified competitor is the end-to-end relaxation approach of A Scalable Approach to Probabilistic Neuro-Symbolic Robustness Verification, which we extend from verification to training. The rule program is unrolled to a fixed depth equal to our $K$, and interval-bound training runs through the unrolled graph. It gets the same perception bounds and compute. No reported certified or verified-bound number exists on Lacuna for ROAD-R, Win-Move, or MNIST addition, so we will produce this baseline ourselves. For the perception layer alone, the external anchor is interval-bound DEQ certified error of 19.11% on MNIST at $\epsilon = 0.4$, versus 28.98% for a 3-layer explicit network, and 66.87% on CIFAR-10 at $8/255$ (Certified Robustness for Deep Equilibrium Models via Interval Bound Propagation). Our digit reader should reach comparable perception-level certified error before rule-level numbers mean anything. Beating the unrolled baseline means higher certified accuracy on rule conclusions at equal $\epsilon$ and compute on the two cyclic benchmarks, and a tie on MNIST addition.

The ablation that isolates AFT's contribution swaps the approximator while keeping everything else fixed: Kripke-Kleene interval iteration, then the well-founded fixpoint, then the ultimate approximator. If Kripke-Kleene matches well-founded on both cyclic benchmarks, the AFT-specific refinement buys nothing in practice, and we will say so.

Why not just…?

Why not just unroll the rules and run an off-the-shelf bound propagator? On stratified programs, that is exactly what our method reduces to, and the MNIST-addition control is designed to confirm the tie. On cyclic negation, unrolling has no correct depth. A fixed number of rule applications at a single input can oscillate between two states instead of reaching a fixpoint, as with the even loop "moving unless stopped". In that case, bounds on the $K$-th iterate are not bounds on the program's meaning, and the certificate is not sound. We will test this directly by searching for perturbed inputs whose solved conclusion falls outside the unrolled interval. Any such case falsifies the baseline's certificate, while AFT's interval is sound by construction.

Why not just do PGD adversarial training and fix compliance with a MaxSAT solver afterwards? This is the real threat for empirical numbers. A solver guarantees that outputs are consistent, not that they are correct. An attacker who flips a few perception outputs can push the projected valid state to a wrong but consistent answer, and the pipeline certifies nothing. The neuro-symbolic verification paper shows that exact verification of such pipelines is $\mathrm{NP}^{\mathrm{PP}}$-complete and that solver-based checking is orders of magnitude slower than relaxation. Certifying this baseline afterwards is therefore not a practical fallback. If it beats us on adaptive empirical robustness at equal compute, we will report that our contribution is certification, not empirical hardening.

Why not just use a fuzzy constraint penalty or semantic loss? ROAD-R reports that the constrained loss alone still leaves violations. Semantic loss requires classical Boolean constraints and compilation that can explode, so it cannot express "not proven" defaults at all. More fundamentally, both are penalties evaluated at a single input. They shape average behaviour and give no statement about the whole perturbation ball. The comparison with the PGD-plus-constrained-loss baseline under certified evaluation will show this directly.

Why not just write three-valued interval iteration and skip the theory? That procedure is AFT's Kripke-Kleene approximator, so it is already one arm of our ablation. The theory adds two things. It proves that the iterate is sound with respect to well-founded and stable semantics. It also supplies tighter fixpoints: positive loops such as reachability cycles evaluate to false under the well-founded fixpoint but stay unknown under Kripke-Kleene. Whether that precision gain translates into certified accuracy is an empirical question the ablation settles.

Decisive Checks

Four results decide whether the idea holds. On MNIST addition, AFT bounds and unrolled bounds must agree to numerical precision; disagreement means a bug. On Visual Win-Move and ROAD-R-Default, strong adaptive attacks (PGD with restarts plus a gradient-free attack) must never produce a perturbed input whose exactly solved conclusion leaves the AFT interval. We will also count how often they escape the unrolled interval. Certified accuracy on rule conclusions after AFT certified training must exceed the unrolled-training baseline at equal compute. And clean frame mean average precision on ROAD-R-Default should stay within a few points of the CLCO clean reference. If the third check fails because Kripke-Kleene already suffices, the paper becomes a soundness result for a simple procedure. If the soundness check fails for the unrolled baseline, that alone shows that existing neuro-symbolic certificates are unsafe for programs with cyclic negation.