Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies Conference: arXiv preprint; 2026;
Sohaib Afifi · 2026
Read Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies Conference: arXiv preprint; 2026; by Sohaib Afifi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25235.txt.
Introduction
Sohaib Afifi gives an attribution method for neural combinatorial optimization policies that explains choices by constraint group. Dual variables from a linear programming relaxation split the outcome across constraint groups. Counterfactuals are certified via a combinatorial feasibility model, and explanation size is capped by a Bonferroni-corrected Hoeffding test in greedy order. On vehicle routing, the method matches the counterfactual-derived signal at 96.5 percent, and on the orienteering problem at 77.2 percent, ahead of proxy gradients. In flexible job-shop scheduling, both backends agree on certified flips.
Catalog record
| CREATOR | Sohaib Afifi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23193 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25235
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies Conference: arXiv preprint; 2026; Sohaib Afifi Abstract . We give an attribution method for neural combinatorial-optimisation (CO) policies that (i) decomposes a decision by constraint families via LP-relaxation duals, (ii) certifies counterfactuals through a combinatorial feasibility model (implemented as a CSP feasibility-decision model), and (iii) bounds the size of a PAC-sufficient explanation with a Bonferroni-corrected Hoeffding sufficient-subset test along a greedy ordering. Across three CO problems and three seeds, our LP-anchored Λ \Lambda -attribution matches the CF-derived signal at 96.5 % 96.5\% on CVRPTW ( n cert = 344 n_{\mathrm{cert}}{=}344 ) and 77.2 % 77.2\% on OP ( n cert = 281 n_{\mathrm{cert}}{=}281 ) vs 75.0 % 75.0\% and 35.2 % 35.2\% for proxy gradient (diffs + 0.215 +0.215 and + 0.420 +0.420 ; McNemar p ≤ 10 − 14 p\leq 10^{-14} ). In the rank-aligned FJSP regime, both backends agree on every CSP-certified flip ( n cert = 59 n_{\mathrm{cert}}{=}59 ), confirming the no-gain prediction. Bonferroni-PAC subsets average 5.0 5.0 nodes per step ( M = 70 M{=}70 , ε = δ = 0.2 \varepsilon{=}\delta{=}0.2 , k max = 25 k_{\max}{=}25 ). Code: https://github.com/sohaibafifi/neuro-co-cax . 1. Introduction Neural combinatorial-optimisation (CO) policies now compete with classical solvers on routing ( Kool et al. 2019 ; Kwon et al. 2020 ; Berto et al. 2024 ; Jari et al. 2025 ) and scheduling ( Cappart et al. 2023 ) . As they move from benchmarks to deployment, the question why did the policy choose this action at this step? becomes operationally important: a dispatcher needs to know whether a route was chosen because of a tight time window, a near-capacity vehicle, or a geometric shortcut. Why generic XAI fails on CO. Post-hoc feature-attribution methods such as gradient \times input and gradient-axiomatic variants (integrated gradients ( Sundararajan et al. 2017 ) , DeepLIFT ( Shrikumar et al. 2017 ) ) attribute each decision to the input features at the node level. A CO problem, however, is defined by its constraint families , each typically spanning several feature tensors of different ranks. As Section 3 shows on routing, a high-rank feature tensor accumulates more gradient mass than a low-rank one even when the underlying constraint family is not the binding one at the LP optimum, so feature-level attribution mis-ranks the constraint that actually drives the decision. Why existing CO-specific explainers fall short. The closest prior work, RouteExplainer ( Kikuta et al. 2024 ) , trains a per-edge classifier on counterfactual labels for Vehicle Routing Problem variants and narrates the labels with an LLM. The counterfactuals it generates are unconstrained: on \approx 81\% of our routing instances (Section 3 ) they push demand below zero or invert a time window, and the explanation surface is restricted to edges in a routing solution rather than the underlying CO constraints. PAC explanations via constraint programming ( Koriche et al. 2024 ) and abduction-based explanations ( Ignatiev et al. 2019 ) target generic classifiers, and formal CP-based explanations of neural policies ( Selvey et al. 2023 ) target classical planning domains, not the autoregressive CO decoder we study. Other recent threads in XAI-for-CO either focus on surrogate models of static optimisation instances (e.g., SHAP-style attribution on a knapsack ML-surrogate ( Garn and Amirghasemi 2025 ) ) or remain pre-print; none, to our knowledge, decomposes a neural CO policy’s decisions by constraint family with a CP-grounded feasibility certificate. Our contribution: Constraint-Anchored Attribution (CAX). Three primitives that connect neural explanations to the optimisation structure of the underlying CO problem: (1) \Lambda -attribution (Section 2.1 ): decompose a step’s gradient by constraint family, scaled by the LP-relaxation Lagrangian multiplier \lambda_{k}^{*} . Yields constraint-level attribution that no feature-level method can produce. (2) Bonferroni-corrected PAC sufficient subset (Section 2.2 ): adapt Koriche et al. ( Koriche et al. 2024 ) to the CO decoder to give a family-wise Hoeffding-controlled top- k size along the greedy attribution ordering, against which any attribution method can be scored. (3) CSP-certified counterfactual (Section 2.3 ): lowest- L_{1} perturbation found by the sampler that flips the argmax while satisfying the problem’s CSP feasibility-decision model. The certificate distinguishes CAX from Wachter ( Wachter et al. 2017 ) and Tsirtsis et al. ( Tsirtsis et al. 2021 ) . The framework only requires a feasibility model; in our experiments, all counterfactual certificates are implemented as CSP feasibility-decision models. The counterfactual primitive in (3) (henceforth abbreviated CF) additionally produces a CF-derived adjudication signal that distinguishes three candidate backends for the \Lambda multipliers; on the benchmark of Section 3 this signal is invariant under the norm ( L_{1} / L_{2} / L_{\infty} ) and per-family-dimension normalisation of the perturbation mass, supporting its use as a reference for ranking attribution backends. The implementation runs on a single CPU and adds one post-hoc feasibility-oracle call per decoding cell. 1 1 1 Code: https://github.com/sohaibafifi/neuro-co-cax (MIT). 2. Method Setup. Let \mathcal{P} be a CO problem with N nodes (customers, operations, …) and constraint families \mathcal{C}=\{c_{1},\ldots,c_{K}\} . An instance is described by feature tensors x=(x^{(1)},\ldots,x^{(F)}) with total dimension d=\sum_{i}|x^{(i)}| ; each family c_{k} is parameterised by a subset \mathcal{F}(c_{k})\subseteq\{1,\ldots,F\} of feature tensors. A learned policy \pi_{\theta} unrolls over T decoding steps, producing at step t a state s_{t} (function of x and the prefix of actions a_{0},\ldots,a_{t-1} ) and a distribution over feasible actions a\in\mathcal{A}(s_{t}) . We write a^{\star}(x):=\arg\max_{a}\pi_{\theta}(a\mid s_{0}(x)) for the greedy first action induced by instance x . We assume \mathcal{P} admits an LP relaxation \widetilde{\mathcal{P}}(x) whose dual yields a per-row multiplier vector; we aggregate to one scalar per family by taking the mean absolute dual over the rows in that family, giving \lambda^{*}(x)=(\lambda_{1}^{*},\ldots,\lambda_{K}^{*})\in\mathbb{R}_{\geq 0}^{K} . Sensitivity to the aggregation choice (mean vs sum vs max) is reported in Section 3.4 . 2.1. \Lambda -attribution We attribute decision a_{t} to constraint family c_{k} as (1) \Lambda_{k}(t)=\lambda_{k}^{*}(x)\cdot\sum_{i\in\mathcal{F}(c_{k})}\sum_{j}\bigl|\nabla_{x^{(i)}_{j}}\log\pi_{\theta}(a_{t}\mid s_{t})\cdot x^{(i)}_{j}\bigr|, where j ranges over the scalar entries of feature tensor x^{(i)} . \Lambda_{k}(t) is non-negative; the family with the largest \Lambda_{k}(t) is the one whose binding pressure most explains the policy’s preference for a_{t} . Three backends estimate \lambda^{*} : lp (dual values of the LP relaxation \widetilde{\mathcal{P}} ), subgrad (Lagrangian subgradient ascent on a relaxed subproblem ( Fisher 1981 ) ), and proxy ( \lambda_{k}=1 , which recovers a constraint-partitioned gradient \times feature). The cost of \Lambda is one backward pass per decoding step plus K per-family masked aggregations of \nabla\log\pi\cdot x ; our v0.2 reference implementation runs K separate backwards for clarity, which is the cost reported below and is trivially reducible. The LP solve on \widetilde{\mathcal{P}} is shared across all decoding steps of an instance and amortises over T . 2.2. Bonferroni-PAC sufficient subset For PAC parameters (\varepsilon,\delta)\in(0,1)^{2} , we want the smallest node subset S preserving the policy’s argmax under a Gaussian neighbourhood of x : (2) \displaystyle\min_{S}\;|S|\;\text{s.t.}\;\Pr_{x^{\prime}\sim\mathcal{N}(x,\sigma^{2}I)}\!\!\bigl[a^{\star}(x^{\prime}_{|S})=a^{\star}(x^{\prime})\bigr]\geq 1-\varepsilon, where x^{\prime}_{|S} masks feature entries at nodes \notin S to a baseline value. A greedy variant walks an attribution ordering and accepts the smallest k at which the empirical preserved-argmax rate exceeds 1-\varepsilon . The procedure inspects up to k_{\max} candidate subsets adaptively, so we apply the Bonferroni union bound to obtain a family-wise (1-\delta) -PAC guarantee along the greedy ordering: