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

• URL: http://arxiv.org/abs/2605.25235v1
• Date: Sun, 24 May 2026 19:46:30 GMT
• Title: Constraint-Anchored Attribution: Feasibility-Certified Counterfactuals and Bonferroni-PAC Sufficient Subsets for Neural CO Policies
• Abstract summary: We give an attribution method for neural-optimisation (CO) policies that decomposes a decision by constraint families via LP-relaxation duals.<n>Across three CO problems and three seeds, our LP-anchored $$-attribution matches the CF-derived signal.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $Λ$-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=δ=0.2$, $k_{\max}=25$). Reference implementation: https://github.com/sohaibafifi/neuro-co-cax

Related papers

• Mean-to-Score Discrete Diffusion: Posterior-Mean Denoisers for Score Entropy [17.48959208263029]
  We introduce emphmean-to-score (M2S), which predicts a clean-token posterior mean and converts it to the score through an exact kernel-dependent linear map.<n>For uniform corruption, it maps the probability simplex onto the bridge polytope; for absorbing-mask corruption, the resulting objective recovers MD4 exactly.
  arXiv  Detail & Related papers  (2026-07-23T14:37:30Z)
• CaricHarmony: Contrastive Diffusion Paths for Identity-Preserving Caricature Synthesis [49.596677723190886]
  Sketch-based caricature synthesis suffers from a fundamental failure mode.<n>Identity and shape conditions are combined in diffusion models, causing collapse toward bland portraits or unrecognizable distortions.<n>We present CaricHarmony, the first training-free method that explicitly resolves this contamination through parallel uncontaminated diffusion paths.
  arXiv  Detail & Related papers  (2026-06-11T22:57:59Z)
• Automated Proving of Shannon-Type Entropy Inequalities via Fine-Tuned Language Models and Guided Tree Search [50.16356451328644]
  Proving Shannon-type entropy inequalities is a fundamental task in information theory.<n>We investigate whether small-scale large language models, fine-tuned on atomic proof steps, can automate this process.<n>We show that GPT-5.5 solves 1.7% samples under zero-shot prompting while Psitip solves 33.3% samples.
  arXiv  Detail & Related papers  (2026-06-04T05:43:12Z)
• Correcting Selection Bias in Sparse User Feedback for Large Language Model Quality Estimation: A Multi-Agent Hierarchical Bayesian Approach [0.9558392439655014]
  We propose a three-agent hierarchical Bayesian pipeline that does not require ground-truth labels on individual interactions.<n>A mild prior on the feedback channel (typical positive-feedback rate and negative-to-positive ratio) keeps Hierarchical-Informed within 4-13 pp of $Qstar$ as the bias ratio sweeps.<n>Without channel-side priors, every weak-prior variant misses $Qstar$ by 22-33 pp.
  arXiv  Detail & Related papers  (2026-05-12T14:22:06Z)
• Bayesian X-Learner: Calibrated Posterior Inference for Heterogeneous Treatment Effects under Heavy-Tailed Outcomes [0.0]
  We present X-Learner, an X-Learner built on cross-fitted doubly robust pseudo-outcomes.<n>On contaminated "whale" DGPs with up to 20-25% tail density, a one-flag extension (contamination_severity) that selects a Huber-$$ loss per Huber's minimax-$$ relation recovers $(x)$ with tight credible intervals.
  arXiv  Detail & Related papers  (2026-04-30T04:07:11Z)
• Covariant quantum error correction in a three-layer quantum brain model: computational analysis of layer-specific coherence dynamics [0.0]
  We evaluate approximate covariant quantum error correction (CQEC) across two radical-pair proteins.<n>CQEC maintains coherence of 0.83 (95% CI [0.76, 0.79); versus 0.12 without tunneling, $times6.96.9 improvement.<n>A $T sensitivity analysis confirms: at $T = 26$ms, CQEC-protected coherence remains 0.69.
  arXiv  Detail & Related papers  (2026-03-31T11:47:00Z)
• On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling [6.908972852063454]
  Correlation Clustering (CC) is a fundamental unsupervised learning primitive.<n>We study how much edge information is needed to retain LP-based guarantees.<n>We show via Yao's minimax principle that without pseudometric structure, any algorithm observing $o(n)$ uniformly random edges incurs an approximation ratio.
  arXiv  Detail & Related papers  (2026-02-14T09:12:15Z)
• Spectral Sentinel: Scalable Byzantine-Robust Decentralized Federated Learning via Sketched Random Matrix Theory on Blockchain [0.0]
  Byzantine clients poison gradients under heterogeneous (Non-IID) data.<n>We propose Spectral Sentinel, a Byzantine detection and aggregation framework.<n>We implement the full system with blockchain integration on Polygon networks.
  arXiv  Detail & Related papers  (2025-12-14T09:43:03Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Improved techniques for deterministic l2 robustness [63.34032156196848]
  Training convolutional neural networks (CNNs) with a strict 1-Lipschitz constraint under the $l_2$ norm is useful for adversarial robustness, interpretable gradients and stable training. We introduce a procedure to certify robustness of 1-Lipschitz CNNs by replacing the last linear layer with a 1-hidden layer. We significantly advance the state-of-the-art for standard and provable robust accuracies on CIFAR-10 and CIFAR-100.
  arXiv  Detail & Related papers  (2022-11-15T19:10:12Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.