🤖 machine learning

Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies

This paper introduces a constraint-anchored attribution method for neural combinatorial optimization policies that decomposes decisions via LP-relaxation duals, certifies counterfactuals using combinatorial feasibility models, and bounds sufficient explanation sizes with Bonferroni-corrected PAC tests, demonstrating significantly higher accuracy than proxy gradients across multiple problem domains.

Original authors: Sohaib Lafifi

Published 2026-05-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sohaib Lafifi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart robot dispatcher that plans delivery routes or schedules factory jobs. It's incredibly good at its job, often beating human experts. But it's a "black box": you ask it, "Why did you send the truck to this house first?" and it just says, "Because my math said so."

This paper introduces a new way to open that black box, called Constraint-Anchored Attribution (CAX). Think of it as a translator that converts the robot's complex math into a story about rules rather than just numbers.

Here is how the paper explains this system using three main tools:

1. The "Rule-Book" Translator (Λ-attribution)

Usually, when we try to explain AI, we look at individual inputs (like "the distance to the house" or "the weight of the package"). The paper argues this is like blaming a single brick for a building collapsing, when really, it was the foundation or the roof that failed.

In these problems, decisions are driven by families of rules (e.g., "Don't exceed the truck's weight," "Don't arrive after 5 PM," "Don't drive too far").

The Old Way: Looks at every single number and guesses which rule mattered. It often gets it wrong because some numbers look "louder" (have more data) even if they aren't the real reason for the decision.
The New Way (CAX): It looks at the "shadow prices" (a fancy math term for how much a rule is squeezing the solution). It asks: "Which family of rules is the most stressed right now?"
The Result: It correctly identifies that the decision was driven by the "Time Window" rule, not just the "Distance" rule, even if the distance data was huge.

2. The "What-If" Reality Check (Feasibility-Certified Counterfactuals)

A common way to explain AI is to ask, "What small change would make the robot do something different?"

The Problem with Old Methods: They might suggest, "If the package weighed -50kg, the robot would go elsewhere." That's impossible! You can't have negative weight. These "counterfactuals" are mathematically valid but physically nonsense.
The CAX Solution: The paper uses a "feasibility certificate." Before accepting an explanation, it runs a strict test (like a safety inspector) to ensure the "What-If" scenario is actually possible in the real world.
The Analogy: Imagine asking, "Why did you take the bridge?" The old AI says, "Because if you took the tunnel, you'd crash." The CAX AI says, "Because if you took the tunnel, you'd crash AND the tunnel is actually open and drivable." It filters out impossible scenarios.

3. The "Minimum Evidence" Test (Bonferroni-PAC Subsets)

Sometimes, we want to know: "What is the smallest amount of information the robot needed to make this decision?"

The Method: The paper uses a statistical trick (Bonferroni correction) to find a small group of nodes (like a few specific houses on a route) that, if you knew only about them, the robot would still make the exact same choice.
The Result: It proves that the robot didn't need to look at the whole map; it only needed to look at a tiny, specific cluster of 5 locations to be 95% sure of its decision. This keeps the explanation short and focused.

The Big Test: Did it work?

The authors tested this on three different problems:

Delivery Routes (CVRPTW): Trucks with time windows and weight limits.
Prize Collection (OP): Visiting as many high-value spots as possible without running out of gas.
Factory Scheduling (FJSP): Assigning jobs to different machines.

The Findings:

On Delivery Routes: The old method (looking at raw numbers) was right only 75% of the time. The new CAX method was right 97% of the time. It successfully caught the "Time Window" rule that the old method missed.
On Prize Collection: The old method was right only 35% of the time. CAX jumped to 77%.
On Factory Scheduling: Both methods agreed perfectly (100%). This confirmed the theory: when the data and the rules line up nicely, the old method works, but when they get messy, CAX is the only one that gets it right.

In a Nutshell

This paper gives us a way to explain complex robot decisions by:

Grouping reasons by rules (not just numbers).
Checking that the "what-if" stories are physically possible.
Finding the smallest set of facts needed to justify the decision.

It turns a confusing math output into a clear, trustworthy story about why the robot made the choice it did, ensuring that the explanation is grounded in the actual rules of the game, not just statistical noise.

Technical Summary: Constraint-Anchored Attribution for Neural CO Policies

Problem Statement

Neural policies for Combinatorial Optimization (CO) are increasingly effective at solving routing and scheduling problems, yet their decision-making processes remain opaque. Standard Explainable AI (XAI) methods, such as gradient-based feature attribution (e.g., Integrated Gradients, DeepLIFT), fail in the CO domain because they operate at the feature level rather than the constraint level. CO problems are defined by families of constraints (e.g., capacity, time windows, precedence), which often span multiple feature tensors of varying ranks. Consequently, high-rank feature tensors may accumulate excessive gradient mass even when they do not represent the binding constraint driving a decision, leading to misaligned attributions.

Existing CO-specific explainers often rely on unconstrained counterfactuals that violate problem feasibility (e.g., negative demand or inverted time windows) or target static surrogate models rather than the autoregressive decoding process of neural policies. There is a lack of methods that decompose neural CO decisions by constraint families while providing formal feasibility guarantees.

Methodology: Constraint-Anchored Attribution (CAX)

The paper proposes CAX, a framework comprising three primitives that link neural explanations to the underlying optimization structure:

1. $\Lambda$ -attribution

This method decomposes a policy's decision gradient by constraint family rather than individual features. For a decision $a_t$ at step $t$ , the attribution to constraint family $c_k$ is calculated as:
$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$
Here, $\lambda^*_k$ represents the Lagrangian multiplier (dual value) from the Linear Programming (LP) relaxation of the problem, aggregated per family. This scaling ensures that the attribution reflects the "binding pressure" of the constraint. The framework supports three backends for estimating $\lambda^*$ :

LP: Dual values from the LP relaxation.
Subgrad: Lagrangian subgradient ascent on a relaxed subproblem.
Proxy: Uniform weighting ( $\lambda_k=1$ ), equivalent to a constraint-partitioned gradient $\times$ feature.

2. Bonferroni-PAC Sufficient Subset

To determine the minimal set of nodes required to preserve the policy's argmax decision, the method adapts Koriche et al.'s approach for CO decoders. It seeks the smallest subset $S$ such that the probability of the policy maintaining its decision under Gaussian perturbations is at least $1-\epsilon$ .

A greedy algorithm traverses the attribution ordering to find the smallest $k$ where the empirical preservation rate exceeds $1-\epsilon$ .
To control the family-wise error rate across adaptive queries (up to $k_{max}$ ), a Bonferroni correction is applied to the Hoeffding bound. This yields a sample size $M_{bonf}$ that guarantees a $(1-\delta)$ -PAC bound along the greedy ordering.

3. CSP-Certified Counterfactuals (CF)

Unlike standard Wachter-style counterfactuals that minimize perturbation norms without feasibility guarantees, CAX enforces a combinatorial feasibility certificate.

Process: A sampler generates perturbations to flip the argmax decision. Candidates first undergo arithmetic checks (e.g., field bounds).
Certification: The best candidate is verified against a Constraint Programming (CP) feasibility-decision model (implemented via CP-SAT).
Adjudication Signal: The family carrying the largest $L_1$ mass in a CSP-certified flipping perturbation serves as a ground-truth signal for the policy's local sensitivity. This signal is invariant to perturbation norms ( $L_1, L_2, L_\infty$ ) and dimension normalization.

Key Contributions

Constraint-Level Decomposition: CAX is the first method to decompose neural CO policy decisions by constraint families using LP-relaxation duals, correcting the mis-ranking issues inherent in feature-level attribution.
Feasibility-Certified Counterfactuals: It introduces a counterfactual generation process that strictly adheres to problem constraints via CSP feasibility-decision models, distinguishing it from unconstrained XAI methods.
PAC-Sufficient Subsets: It provides a Bonferroni-corrected, Hoeffding-controlled bound on the size of sufficient explanation subsets for neural CO policies.
Empirical Adjudication: The framework uses the CF-derived signal to validate attribution backends, demonstrating that LP duals rescue attribution accuracy when feature ranks and binding constraints are misaligned.

Experimental Results

The framework was evaluated on three distinct CO problems: Capacitated Vehicle Routing with Time Windows (CVRPTW), Orienteering Problem (OP), and Flexible Job-Shop Scheduling Problem (FJSP).

Agreement with CF Signal:
- CVRPTW: LP-anchored $\Lambda$ -attribution matched the CF-derived signal in 96.5% of cases ( $n_{cert}=344$ ), significantly outperforming the proxy gradient (75.0%). The difference (+0.215) was statistically significant (McNemar $p \le 10^{-14}$ ).
- OP: LP-anchored attribution achieved 77.2% agreement ( $n_{cert}=281$ ) versus 35.2% for the proxy (+0.420 difference, $p \le 10^{-14}$ ).
- FJSP: In this "rank-aligned" regime where high-mass tensors match binding families, both LP and proxy backends achieved 100% agreement on all 59 certified flips, confirming the theoretical prediction that LP duals add no extra information when ranks align.
Feasibility Rates: The CSP-certified counterfactuals maintained high feasibility. Arithmetic filtering alone passed 100% of winners, while a matched unconstrained baseline passed only 19.3% of candidates.
PAC Subsets: On CVRPTW, Bonferroni-corrected PAC subsets averaged 5.0 nodes per step ( $M=70, \epsilon=\delta=0.2$ ).

Significance and Claims

The paper claims that CAX provides a rigorous, constraint-grounded approach to explaining neural CO policies. Its primary significance lies in demonstrating that LP duals are necessary for accurate attribution only when feature tensor ranks are misaligned with the binding constraint family. When they align, simpler methods suffice; when they misalign, feature-level methods fail, and LP-anchored methods recover the correct constraint-level signal.

The framework is modest in its scope: it requires only a feasibility model (implemented here as CSP) and operates as a post-hoc analysis tool. It does not claim to solve the full subset lattice optimization (exact PAC-optimal subsets remain an open problem) but provides a conservative, certified bound via greedy ordering. The work establishes a new benchmark for evaluating XAI in CO by using CSP-certified counterfactuals as an adjudication signal, moving beyond heuristic feature importance to constraint-based validity.