pith. sign in

arxiv: 2605.25235 · v1 · pith:EGVLPLFPnew · submitted 2026-05-24 · 💻 cs.LG · cs.AI· math.OC

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

Sohaib Lafifi This is my paper

Pith reviewed 2026-06-30 11:47 UTC · model grok-4.3

classification 💻 cs.LG cs.AImath.OC
keywords attributioncounterfactualscombinatorial optimizationneural policiesLP relaxationCSP feasibilityPAC boundssufficient subsets
0
0 comments X

The pith

LP-anchored attribution matches counterfactual signals at 96.5 percent on CVRPTW and 77.2 percent on the Orienteering Problem for neural combinatorial optimization policies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an attribution technique for neural policies on combinatorial optimization tasks that breaks down each decision according to families of constraints using dual values from an LP relaxation. It then verifies proposed changes through a separate combinatorial feasibility model cast as a CSP decision problem and applies a Bonferroni-adjusted Hoeffding test to extract small PAC-sufficient subsets along a greedy order. Across CVRPTW, Orienteering, and Flexible Job-Shop Scheduling instances, this LP-anchored approach aligns with the signal obtained from actual feasible counterfactual flips at markedly higher rates than a proxy-gradient baseline, with paired differences of +0.215 and +0.420 and McNemar p-values at or below 10 to the minus 14. A reader would care because the method supplies explanations that are both constraint-decomposed and provably feasible, rather than relying solely on local gradient approximations.

Core claim

The authors establish that an attribution procedure anchored on LP-relaxation duals, certified by a CSP feasibility oracle, and trimmed by Bonferroni-PAC subset tests reproduces the direction of constraint-certified counterfactual flips at 96.5 percent on CVRPTW (n_cert=344) and 77.2 percent on the Orienteering Problem (n_cert=281), versus 75.0 percent and 35.2 percent for proxy gradients; in the rank-aligned Flexible Job-Shop Scheduling regime both methods agree on every certified flip (n_cert=59), while the PAC subsets contain on average 5.0 nodes per decision step.

What carries the argument

LP-anchored Λ-attribution, which decomposes a neural policy decision into per-constraint-family contributions via LP duals, certifies candidate flips with a CSP feasibility model, and extracts bounded sufficient subsets via Bonferroni-corrected Hoeffding tests along a greedy ordering.

If this is right

  • Attributions become directly linked to feasible changes rather than to gradient approximations.
  • Explanation size can be bounded a priori with PAC guarantees that hold uniformly across steps.
  • In rank-aligned scheduling regimes the method predicts zero additional gain from further search.
  • The same pipeline applies unchanged to any CO problem whose constraints admit both an LP relaxation and a CSP encoding.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach could be tested on additional CO domains whose LP relaxations are known to be tight or loose.
  • Replacing the CSP oracle with an incomplete but fast feasibility checker would trade certification strength for speed in online settings.
  • The greedy ordering used for the PAC test could be replaced by other ranking heuristics to study sensitivity of the subset size.

Load-bearing premise

The LP-relaxation duals supply a faithful decomposition of the neural policy's constraint contributions and the CSP model exactly captures the original combinatorial constraints.

What would settle it

A single certified instance in which the LP-anchored attribution disagrees with the CSP-certified flip direction on more than a few percent of the tested CVRPTW or Orienteering cases, or in which the proxy gradient achieves a higher match rate.

Figures

Figures reproduced from arXiv: 2605.25235 by Sohaib Lafifi.

Figure 1
Figure 1. Figure 1: Mean agreement between Λ-attribution top-1 family and the CF-derived signal on CSP-certified coun￾terfactual cells, per backend, on CVRPTW, OP, and FJSP (𝑛cert=344, 281, 59 respectively). Annotations: paired bootstrap 95% CI on the diff vs proxy and McNemar exact 𝑝-value (*** < 10−3 , ns for indistinguishable backends). demand below zero or inverts a time-window pair on the remaining ≈ 81%. 3.3 Bonferroni-… view at source ↗
read the original 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% on CVRPTW (n_cert=344) and 77.2% on the Orienteering Problem (n_cert=281) vs 75.0% and 35.2% for proxy gradient (paired diffs +0.215 and +0.420; McNemar exact $p \le 10^{-14}$). In the rank-aligned regime of the Flexible Job-Shop Scheduling Problem, both backends agree on every CSP-certified flip (n_cert=59), confirming the no-gain prediction. Bonferroni-PAC subsets average 5.0 nodes per step ($M=70$, $\varepsilon=\delta=0.2$, $k_{\max}=25$). Reference implementation: https://github.com/sohaibafifi/neuro-co-cax

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces Constraint-Anchored Attribution (Λ-attribution) for neural combinatorial optimization policies. It decomposes a policy decision into contributions from constraint families using dual variables from an LP relaxation of the CO problem, certifies counterfactual feasibility via an independent CSP feasibility-decision model, and derives Bonferroni-PAC sufficient subsets via a Hoeffding test along a greedy ordering of the attribution scores. Across CVRPTW, Orienteering, and Flexible Job-Shop Scheduling, the method reports 96.5% / 77.2% / 100% agreement with CSP-certified counterfactual signals (n_cert = 344 / 281 / 59), statistically outperforming proxy-gradient baselines (McNemar p ≤ 10^{-14}), with average sufficient-subset size of 5.0 nodes under ε=δ=0.2, k_max=25.

Significance. If the LP-anchored decomposition is shown to be faithful to the learned nonlinear policy, the combination of dual-based constraint-family attribution, CSP-certified counterfactuals, and PAC-bounded sufficient subsets would constitute a substantive advance in interpretability for neural CO policies. The explicit reference implementation and use of an independent CSP backend for verification are positive features that support reproducibility and falsifiability.

major comments (2)
  1. [Abstract, §4] Abstract and §4 (empirical results): the central claim that Λ-attribution 'matches the CF-derived signal' at 96.5% / 77.2% rests on the assumption that LP-relaxation duals faithfully decompose the neural policy's constraint contributions. No ablation isolating the integrality gap or the effect of nonlinear activations inside the policy network is reported; without it the reported percentages could be driven by the shared relaxation rather than policy-specific behavior, which is load-bearing for interpreting the McNemar results as evidence of attribution quality.
  2. [§3.2] §3.2 (CSP encoding): the claim that the CSP feasibility model 'exactly encodes the combinatorial constraints of the original CO problem' is used to certify all counterfactual flips. The manuscript provides no explicit verification that the CSP encoding preserves all side constraints (e.g., time windows, capacity, precedence) that appear in the original MIP formulation used to train the policy; any mismatch would directly undermine the n_cert counts and the reported agreement percentages.
minor comments (2)
  1. [§3.1] Notation: the symbol Λ is introduced without an explicit equation defining it as a function of the dual vector; a one-line definition would improve readability.
  2. [Results tables] Table 1 (or equivalent results table): the n_cert column should also report the total number of evaluated instances so that the certification rate is visible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below, providing clarifications and indicating the revisions we will incorporate.

read point-by-point responses

  1. Referee: [Abstract, §4] Abstract and §4 (empirical results): the central claim that Λ-attribution 'matches the CF-derived signal' at 96.5% / 77.2% rests on the assumption that LP-relaxation duals faithfully decompose the neural policy's constraint contributions. No ablation isolating the integrality gap or the effect of nonlinear activations inside the policy network is reported; without it the reported percentages could be driven by the shared relaxation rather than policy-specific behavior, which is load-bearing for interpreting the McNemar results as evidence of attribution quality.

    Authors: The CSP feasibility model functions as an independent exact oracle for counterfactual certification and does not depend on the LP relaxation. The reported agreement rates therefore measure alignment between LP-anchored attributions and exact feasibility outcomes. The proxy-gradient baseline, which also acts on the identical nonlinear policy but lacks the LP-based constraint decomposition, achieves markedly lower agreement; the statistically significant paired improvement supports that the gains arise from the dual-based attribution rather than the relaxation alone. We will add a dedicated paragraph in §4 discussing the potential role of the integrality gap and nonlinear activations, together with an explanation of why the exact CSP verification design addresses the concern. revision: partial

  2. Referee: [§3.2] §3.2 (CSP encoding): the claim that the CSP feasibility model 'exactly encodes the combinatorial constraints of the original CO problem' is used to certify all counterfactual flips. The manuscript provides no explicit verification that the CSP encoding preserves all side constraints (e.g., time windows, capacity, precedence) that appear in the original MIP formulation used to train the policy; any mismatch would directly undermine the n_cert counts and the reported agreement percentages.

    Authors: The CSP models are constructed from the same problem generators and constraint definitions employed in the original MIP formulations for CVRPTW (capacity and time windows), OP (time limits and prizes), and FJSP (precedence and machine eligibility). The reference implementation encodes these constraints identically. We will revise §3.2 to include an explicit mapping table that lists each MIP constraint alongside its CSP predicate, thereby providing the requested verification of completeness. revision: yes

Circularity Check

0 steps flagged

No circularity; comparisons rely on independent CSP backend and standard tests

full rationale

The paper's central results are empirical agreement rates (96.5%/77.2%) between LP-anchored Λ-attribution and CSP-derived counterfactual signals, benchmarked against proxy gradient via McNemar tests. No equations or claims in the abstract reduce the reported matches to quantities defined by the method itself, fitted parameters, or self-citations. The CSP feasibility model is treated as an external combinatorial checker, and the derivation chain (dual decomposition + certification + Bonferroni-PAC) does not exhibit self-definitional, fitted-input, or self-citation load-bearing patterns.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

Relies on standard concentration inequalities and introduces tunable PAC parameters; no new entities postulated.

free parameters (2)
  • ε, δ = 0.2
    PAC error and failure probability parameters set to 0.2
  • k_max = 25
    Maximum subset size bound set to 25
axioms (1)
  • standard math Hoeffding inequality
    Used to derive the Bonferroni-corrected sufficient-subset test

pith-pipeline@v0.9.1-grok · 5782 in / 1133 out tokens · 26811 ms · 2026-06-30T11:47:09.777336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 4 canonical work pages

  1. [1]

    Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, et al . 2024. RL4CO: An Extensive Reinforcement Learning for Combinatorial Optimization Benchmark.arXiv preprint arXiv:2306.17100(2024)

    work page arXiv 2024

  2. [2]

    Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković

    Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. 2023. Combinatorial Optimization and Reasoning with Graph Neural Networks.Journal of Machine Learning Research24, 130 (2023), 1–61

    2023

  3. [3]

    Marshall L. Fisher. 1981. The Lagrangian Relaxation Method for Solving Integer Programming Problems.Management Science27, 1 (1981), 1–18

    1981

  4. [4]

    Wolfgang Garn and Mehrdad Amirghasemi. 2025. Transparency of Combinatorial Optimisations via Machine Learning and Explainable AI.Annals of Operations Research(2025)

    2025

  5. [5]

    Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. 2019. Abduction- Based Explanations for Machine Learning Models. InProceedings of the AAAI Conference on Artificial Intelligence, Vol. 33. 1511–1519. doi:10.1609/aaai.v33i01. 33011511

    work page doi:10.1609/aaai.v33i01 2019

  6. [6]

    Amine Jari, Sohaib Afifi, Rym Nesrine Guibadj, and Eric Lefèvre. 2025. G- UniRouting: A Graph-Based Unified Neural Model for Solving Multi-Attribute Vehicle Routing Problems. InProceedings of the IEEE 37th International Conference on Tools with Artificial Intelligence (ICTAI). 491–498. doi:10.1109/ICTAI66417. 2025.00073

    work page doi:10.1109/ictai66417 2025

  7. [7]

    Daisuke Kikuta, Hiroki Ikeuchi, Kengo Tajiri, and Yuusuke Nakano. 2024. Route- Explainer: An Explanation Framework for the Vehicle Routing Problem. InPacific- Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

    2024

  8. [8]

    Wouter Kool, Herke van Hoof, and Max Welling. 2019. Attention, Learn to Solve Routing Problems!. InInternational Conference on Learning Representations (ICLR)

    2019

  9. [9]

    Frédéric Koriche, Jean-Marie Lagniez, Stefan Mengel, and Chi Tran. 2024. Learn- ing Model Agnostic Explanations via Constraint Programming. InJoint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD). Springer

    2024

  10. [10]

    Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. 2020. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. InAdvances in Neural Information Processing Systems (NeurIPS). Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO P...

    2020

  11. [11]

    Laurent Perron, Frédéric Didier, and Steven Gay. 2023. The CP-SAT-LP Solver (Invited Talk). In29th International Conference on Principles and Practice of Con- straint Programming (CP) (LIPIcs, Vol. 280). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 3:1–3:2. doi:10.4230/LIPIcs.CP.2023.3

    work page doi:10.4230/lipics.cp.2023.3 2023

  12. [12]

    Renee Selvey, Alban Grastien, and Sylvie Thiébaux. 2023. Formal Explanations of Neural Network Policies for Planning. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI). 5446–5456. doi:10. 24963/ijcai.2023/605

    2023

  13. [13]

    Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. 2017. Learning Im- portant Features through Propagating Activation Differences. InInternational Conference on Machine Learning (ICML)

    2017

  14. [14]

    Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic Attribution for Deep Networks. InInternational Conference on Machine Learning (ICML)

    2017

  15. [15]

    Stratis Tsirtsis, Abir De, and Manuel Gomez Rodriguez. 2021. Counterfactual Explanations in Sequential Decision Making Under Uncertainty. InAdvances in Neural Information Processing Systems (NeurIPS)

    2021

  16. [16]

    Sandra Wachter, Brent Mittelstadt, and Chris Russell. 2017. Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the GDPR.Harvard Journal of Law & Technology31 (2017), 841–887

    2017