Certified Pruning from Counterfactual Consistency: Exact Certificates and Structured SAT Families

• URL: http://arxiv.org/abs/2509.07000v3
• Date: Mon, 06 Oct 2025 12:05:54 GMT
• Title: Certified Pruning from Counterfactual Consistency: Exact Certificates and Structured SAT Families
• Abstract summary: We formalize epsilon-counterfactual instrumentation and epsilon-stability, capturing noisy but testable constraints in laboratory contextuality experiments.<n>We extend these constraints to networks of contexts, yielding contextuality-type inequalities that apply globally across a CNF-SAT instance.<n>We implement a propagate-and-prune solver in which every learned clause is certified by a dual Farkas certificate verified in exact arithmetic.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a certified pruning framework that consolidates the principles of counterfactual consistency and their networked extensions into a single operational model, with consequences for both quantum foundations and cryptographic hardness. First, we formalize epsilon-counterfactual instrumentation and epsilon-stability, capturing noisy but testable constraints in laboratory contextuality experiments. Second, we extend these constraints to networks of contexts, yielding contextuality-type inequalities that apply globally across a CNF-SAT instance. Third, we implement a propagate-and-prune solver in which every learned clause is certified by a dual Farkas certificate verified in exact arithmetic. This guarantees soundness while enabling sub-exponential pruning: if the induced network provides a per-variable pruning rate rho in (0,1) under epsilon-stable propagation, the search runs in time (2-rho)^n. These bounds do not contradict ETH or SETH: the worst case remains exponential, but structured families admit provable speedups. In cryptography, the results highlight how such reductions could affect hardness margins in idealized primitives; in foundations, they motivate laboratory tests of counterfactual bounds as potential probes of computational complexity. We explicitly distinguish experimental epsilon, which quantifies laboratory visibility, from numerical epsilon, which is a solver tolerance. This builds directly on our earlier framework for epsilon-instrumentation, here integrated into certified pruning with dual certificates.

Related papers

• BioZKFHE: Scalable Encrypted Biometric Identification via Verifiable Homomorphic Similarity Evaluation [20.524348401618735]
  BioZKFHE is a framework for scalable encrypted biometric identification via verifiable homomorphic similarity evaluation.<n>It combines BGV homomorphic computation with committee-mediated proof opening/decryption and smart-contract verification of opened proof batches.<n>Experiments on FaceNet and MobileFaceNet show near-lossless biometric utility, up to 67 percent encrypted-storage reduction, and about 22 to 44 seconds end-to-end proof-verified runtime.
  arXiv  Detail & Related papers  (2026-07-24T08:08:54Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  We show that a lower bound holds for every admissible function and follows from a convex relaxation giving stronger bounds.<n>A theory verifies each agent one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point in the interval.
  arXiv  Detail & Related papers  (2026-06-30T06:10:25Z)
• Hybrid Robustness Verification for Spatio-Temporal Neural Networks [19.026662893450425]
  Existing verification methods rely on overly conservative approximations or incur prohibitive computational costs.<n>In practice, adversarial perturbations exhibit structured spatial and temporal correlations, constrained to lower-dimensional, semantically meaningful subspaces.<n>We study robustness verification 3D CNNs processing video inputs, targeting applications in action recognition (UCF-101), autonomous driving (Udacity), medical imaging (MedMNIST)
  arXiv  Detail & Related papers  (2026-06-08T17:06:51Z)
• Compile to Compress: Boosting Formal Theorem Provers by Compiler Outputs [48.390500145598544]
  Large language models (LLMs) have demonstrated significant potential in formal theorem proving.<n>We exploit an informative structure in formal verification: the observation that compilers map a vast space of diverse proof attempts.<n>We introduce a learning-to-refine framework that leverages this compression to perform efficient learning and proof exploration.
  arXiv  Detail & Related papers  (2026-03-13T01:33:20Z)
• Causal Identification from Counterfactual Data: Completeness and Bounding Results [54.147490305295456]
  We develop an algorithm for identifying counterfactual queries from an arbitrary set of Layer 3 distributions.<n>We establish the theoretical limit of which counterfactuals can be identified from physically realizable distributions.<n>We derive novel analytic bounds for such quantities using realizable counterfactual data.
  arXiv  Detail & Related papers  (2026-02-26T22:48:12Z)
• TorchLean: Formalizing Neural Networks in Lean [71.68907600404513]
  We introduce TorchLean, a framework that treats learned models as first-class mathematical objects with a single, precise semantics shared by execution and verification.<n>We validate TorchLean end-to-end on certified robustness, physics-informed residual bounds for PINNs, and Lyapunov-style neural controller verification.
  arXiv  Detail & Related papers  (2026-02-26T05:11:44Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Toward Scalable and Valid Conditional Independence Testing with Spectral Representations [25.258360465513338]
  Conditional independence (CI) is untestable in many settings without additional assumptions.<n>We introduce a practical bi-level contrastive algorithm to learn representations derived from the singular value decomposition of the partial covariance operator.<n>Preliminary experiments suggest that this approach offers a practical and statistically grounded path toward scalable CI testing.
  arXiv  Detail & Related papers  (2025-12-22T16:05:18Z)
• Theoretical Bounds for Stable In-Context Learning [0.0]
  In-context learning (ICL) is flexible but its reliability is sensitive to prompt length.<n>This paper establishes a non-asymptotic lower bound that links the minimal number of demonstrations to ICL stability.<n>We propose a two-stage observable estimator with a one-shot calibration that produces practitioner-ready prompt-length estimates.
  arXiv  Detail & Related papers  (2025-09-25T02:25:05Z)
• SIM-CoT: Supervised Implicit Chain-of-Thought [108.30049193668083]
  Implicit Chain-of-Thought (CoT) methods offer a token-efficient alternative to explicit CoT reasoning in Large Language Models.<n>We identify a core latent instability issue when scaling the computational budget of implicit CoT.<n>We propose SIM-CoT, a plug-and-play training module that introduces step-level supervision to stabilize and enrich the latent reasoning space.
  arXiv  Detail & Related papers  (2025-09-24T17:01:32Z)
• Counterfactual Local Friendliness: An epsilon-Bounded Interaction-Free Paradox and a Disturbance-Robust Three-Box Inequality [0.0]
  We show a Wigner's-friend-type logical collision in which every decisive inference is obtained by interaction-free flags.<n>Under (Q) universal unitarity for outside observers, (S) single-outcome facts, (C) cross-agent consistency, and (IF-$epsilon$) $epsilon$-counterfactuality of the friends' internal modules.<n>We also derive an $epsilon$-IF three-box noncontextual bound: any single-world, noncontextual model satisfying exclusivity must obey $P(A) + P(B)
  arXiv  Detail & Related papers  (2025-09-01T09:19:34Z)
• Reconstructing Trust Embeddings from Siamese Trust Scores: A Direct-Sum Approach with Fixed-Point Semantics [0.0]
  We study the inverse problem of reconstructing high-dimensional trust embeddings from the one-dimensional Siamese trust scores that many distributed-security frameworks expose.<n>A suite of synthetic benchmarks confirms that, even in the presence of Gaussian noise, the recovered embeddings preserve inter-device geometry as measured by Euclidean and cosine metrics.<n>The paper demonstrates a practical privacy risk: publishing granular trust scores can leak latent behavioural information about both devices and evaluation models.
  arXiv  Detail & Related papers  (2025-08-02T20:19:22Z)
• Many-Body Fluctuation Theorems for Quantum Coherence and Correlation Dynamics [11.651470433850731]
  We extend quantum fluctuation theorems to quantum information dynamics and many-body systems.<n>By extending to quasiprobability, we derive quantum fluctuation theorems for many-body coherence and quantum correlations.<n>These findings uncover the statistical structure underlying the nonequilibrium quantum information dynamics.
  arXiv  Detail & Related papers  (2025-07-02T11:10:42Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Topological Mixed States: Axiomatic Approaches and Phases of Matter [11.884072864070937]
  In closed quantum systems, topological orders are understood through equivalence classes of ground states of gapped local Hamiltonians.<n>Here, we fill this gap by proposing an approach based on three axioms: ($i$) local recoverability, ($ii$) absence of long-range correlations, and ($iii$) spatial uniformity.<n>Results lay the foundation for a systematic classification of topological states in open quantum systems.
  arXiv  Detail & Related papers  (2025-06-04T17:58:45Z)
• Latent Veracity Inference for Identifying Errors in Stepwise Reasoning [78.29317733206643]
  We introduce Veracity Search (VS), a discrete search algorithm over veracity assignments.<n>It performs otherwise intractable inference in the posterior distribution over latent veracity values.<n>It generalizes VS, enabling accurate zero-shot veracity inference in novel contexts.
  arXiv  Detail & Related papers  (2025-05-17T04:16:36Z)
• Local theories with parallel realities and the epistemic view of the quantum state [1.2891210250935148]
  We introduce a general framework that combines the randomness of single-world theories with the coexistence of diverse instances.<n>This framework has relevance in quantum communication complexity and leads to novel technical questions.
  arXiv  Detail & Related papers  (2025-02-19T15:19:08Z)
• Universal quantum theory contains twisted logic [0.0]
  Heisenberg's uncertainty principle leads to the impossibility of stringing together logical deductions about outcomes of consecutive non-compatible measurements. We show how overlooking this non-trivial logical structure leads to the erroneous possibility of distinguishing non-orthogonal states with a single measurement.
  arXiv  Detail & Related papers  (2024-09-30T16:40:58Z)
• Minimal operational theories: classical theories with quantum features [41.94295877935867]
  We introduce a class of probabilistic theories, where system dynamics are constrained to the minimal set of operations.<n>Specifically, the allowed instruments are limited to those derived from compositions of preparations, measurements, swap transformations, and conditional tests.<n>We demonstrate that minimal theories with conditioning and a spanning set of non-separable states satisfy two quantum no-go theorems.
  arXiv  Detail & Related papers  (2024-08-02T16:24:09Z)
• Incorporating Zero-Probability Constraints to Device-Independent Randomness Expansion [11.765274200974774]
  We explore various forms of randomness that are certifiable in the so-called device-independent (DI) paradigm. In this work, we determine the certifiable randomness when zero-probability constraints are incorporated into the task of DI randomness expansion.
  arXiv  Detail & Related papers  (2024-01-16T15:57:17Z)
• Efficient Error Certification for Physics-Informed Neural Networks [25.712851771991218]
  We introduce $partial$-CROWN: a general, efficient and scalable post-training framework to bound PINN residual errors. We demonstrate its effectiveness in obtaining certificates tight by applying it to two classically studied PINNs and two more challenging ones with real-world applications.
  arXiv  Detail & Related papers  (2023-05-17T12:19:43Z)
• Indeterminate Probability Theory [18.320645632562663]
  This paper proposes Indeterminate Probability Theory (IPT)<n>IPT is an observer-centered framework in which experimental outcomes are represented as distributions combining ground truth with observation error.<n>IPT is consistent with classical probability theory and subsumes the frequentist equation in the limit of vanishing observation error.
  arXiv  Detail & Related papers  (2023-03-21T01:57:40Z)
• Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness [0.0]
  We prove that the stability of BP holds upon the following generalizations. We introduce classification based on the $ell$ norms of the groups and show numerically that it can be accurate and offers considerable speedups.
  arXiv  Detail & Related papers  (2022-05-05T09:12:07Z)
• Observers of quantum systems cannot agree to disagree [55.41644538483948]
  We ask whether agreement between observers can serve as a physical principle that must hold for any theory of the world. We construct examples of (postquantum) no-signaling boxes where observers can agree to disagree.
  arXiv  Detail & Related papers  (2021-02-17T19:00:04Z)

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.