CS Paper Radar

On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

Guy Emerson

cs.LG cs.CCmath.PR ·submitted 2026-08-31 17:32 UTC · v1
theory

Abstract

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

Comment
14 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Probabilistic Circuits as Reasoning Machines in Artificial Intelligence (Part I)

cs.AI cs.LGmath.PR ·2026-08-17 ·Robert Peharz
similarity 0.64
Abstract · Habilitation Thesis

This cumulative habilitation thesis studies probabilistic circuits (PCs) as a powerful and tractable framework for reasoning and learning under uncertainty in artificial intelligence (AI). It first advocates for probability as a core language for AI, emphasizing its connections to logic and information theory; the conceptual simplicity of probabilistic reasoning---based primarily on the sum and product rules; the parallels between probabilistic inference and human cognition; and the role of probability in optimal decision making. However, probability also faces significant computational challenges, as probabilistic inference is NP-hard in almost all probabilistic models. PCs address these challenges through structural constraints that ensure exact computation of a wide range of inference queries in polynomial time, such as marginals, conditionals, most probable explanations, expectations, and more advanced inference tasks. This thesis synthesizes a decade of research across foundations, algorithmic developments, and empirical validation of PCs. Key contributions highlighted in this work are foundational theory of PCs, Bayesian approaches for learning PCs, scalable implementations and integration with deep learning, hybrid models that combine PCs with intractable models, and connections with symbolic machine learning paradigms. This is the first part of my Habilitation Thesis. The second part is omitted, as it comprises the cumulative part of the thesis and has been published at various venues (see Chapter 5).

0.20

A Nonlinear Abstract Domain for Bayesian Neural Networks

cs.PL ·2026-11-14 ·Qiuhan Gu, Gagandeep Singh
similarity 0.63
Abstract

Bayesian neural networks (BNNs) explicitly model epistemic uncertainty by leveraging probability distributions over network parameters, making them better suited for risk-aware decision-making. Yet soundly propagating uncertainty through the network and capturing the entire output distribution to support predictive uncertainty quantification remains a fundamental challenge. Existing approaches are either sampling-based, providing no formal guarantees, or propagate only selected statistical properties, such as expectations and entropy, limiting their applicability to general probabilistic queries. To address these challenges, we present the first nonlinear abstract domain for soundly approximating complete probability distributions of BNNs. The abstract domain builds upon a novel marginal collecting concrete semantics that soundly abstracts the classical joint-measure semantics. It combines support partitioning with exponential-affine bounds to represent probability measures, capturing both discrete and continuous components of mixed distributions as well as nonlinear density shapes over bounded and unbounded supports. We develop sound abstract transformers that can efficiently handle high-dimensional affine transformations and nonlinear ReLU activations, while remaining highly parallelizable. We further extend the framework beyond BNNs to support bounded-loop probabilistic programs with Bayesian inference to demonstrate its generality. We implement the resulting abstract interpreter as a GPU-accelerated analyzer. Experimental results show that the framework significantly improves precision over existing probabilistic reasoning approaches while soundly capturing the complete output distribution, demonstrating strong efficiency and scalability.

0.29

Structure and Complexity of Perfect Functional Representations

cs.IT ·2026-11-18 ·Serhat Emre Coban, Yanina Y. Shkel, Emre Telatar
published similarity 0.61
Abstract · 19 pages, 1 figure. Extended version of "On Perfect Functional Representations", presented at the 2026 IEEE International Symposium on Infor…

For given random variables $(X,Y)$, functional representation lemma states that there exists a random variable $Z$ and a deterministic function $g$ such that $Y = g(X,Z)$, and $X$ is independent of $Z$. In other words, $Z$ captures all the information about $Y$ not contained in $X$. We refer to $Z$ as a `perfect functional representation' if it satisfies $I(Y;Z) = H(Y|X)$. We show that the existence of perfect representation depends solely on the conditional distribution $p_{Y|X}$ and define the corresponding conditional distributions as perfectly representable. We provide a necessary and sufficient condition for $p_{Y|X}$ to be perfectly representable. Moreover, we cast the problem of checking perfect representability as a linear program, give an algorithm whose complexity is polynomial in $|\mathcal Y|$ and exponential in $|\mathcal X|$, and prove that deciding perfect representability is NP-complete for rational input matrices encoded in binary.

0.55

Neural Bayesian Networks for Modular and Scalable Decision-Making Under Uncertainty

cs.AI cs.LG ·2026-10-12 ·Giovanni Briglia, Marco Lippi, Stefano Mariani, Franco Zambonelli
publishedbenchmarkcode/data similarity 0.60
Abstract · Main text 10 pages, extra is supplementary. ACM CCS: Computing methodologies~Artificial intelligence~Knowledge representation and reasoning~…

Bayesian Networks (BNs) are established tools for letting agents reason under uncertainty in sequential decision-making. They split a joint distribution into local conditional mechanisms arranged on a directed acyclic graph, which makes them modular, interpretable, and ready to perform probabilistic inference. Their classical formulation, however, has limitations in both expressiveness and scale: each conditional is usually stored as a table or a linear-Gaussian form, and inference evaluates the graph one node and one query at a time. In this paper we introduce Neural Bayesian Networks (NBNs), in which each conditional is a differentiable, tensor-valued mechanism, while the graph and its factorization are unchanged. NBNs retain the modularity and local mechanisms of BNs, can represent any learnable conditional distribution, and run natively on GPUs. We also release NBN, a PyTorch-based library for learning and inference in NBNs, together with a public benchmark. Our evaluation shows gains in both expressiveness and scale: NBNs fit distributions that classical BN libraries struggle to represent, and on large networks and large batches of queries they run two orders of magnitude faster thanks to GPU parallelization. NBN is available at https://github.com/Giovannibriglia/NeuralBayesianNetworks.

0.40

Bayes Rule for Conditioning Probabilistic Programs

cs.PL cs.LO ·2026-10-07 ·Feras A. Saad
similarity 0.60
Abstract

Probabilistic programs provide a rigorous programming-language foundation for expressing rich probabilistic models and offer language-level support for solving challenging statistical inference problems. A key theoretical challenge that probabilistic programs inherit from probability theory is conditioning a probability distribution on an observation that has probability zero. Many languages address this challenge by using computational rules for conditioning that may work well for some problems but are statistically unsound for others. This article introduces a principled mathematical approach for conditioning probabilistic programs. We first show that existing techniques based on "soft conditioning" and "neighborhood limits" exhibit semantic issues from the perspective of measure theory and produce inference results that disagree with sound statistical reasoning. By leveraging tools from geometric measure theory, we construct a novel disintegration-based semantics for probabilistic program traces that enables sound conditioning. The theory delivers an explicit Bayes rule representation of the conditional distribution, which is directly compatible with widely used probabilistic inference algorithms that require access to unnormalized posterior densities. Our Bayes rule handles probabilistic models with loops, branches, discrete, continuous, and mixed-type distributions, observations on manifolds, differentiable structure, and additional modeling motifs that arise in practice.

0.15

Probabilistic Linear Explanations

cs.LG cs.AI ·2026-09-16 ·Frederic Koriche, Jean-Marie Lagniez, Chi Tran
similarity 0.58
Abstract · Under Review

Formal explainability provides mathematically grounded justifications for individual predictions. However, abductive explanations often exceed human cognitive limits by involving too many features, while probabilistic relaxations have remained largely limited to categorical classification. We present a unified framework for probabilistic explainability based on sparse, anchored linear models, applicable to both binary classification and continuous regression. By mapping instances to the Boolean hypercube, our linear explanations strictly generalize subset-based approaches: they capture both the magnitude and direction of feature contributions while enforcing a prescribed sparsity budget $k$. We show that minimizing the relevance error for such explanations is \ClassNPPP-hard when the underlying model is a neural network, and we relate this intractable objective to a tractable surrogate---the fidelity error. For a parameterized family of local distributions, the relevance error of any $k$-sparse explanation is bounded by its fidelity error up to a multiplicative factor that remains small locally. We address the resulting empirical problem using two complementary approaches: a Mixed Integer Programming (MIP) formulation that yields provably optimal empirical solutions while maintaining polynomial sample complexity, and a polynomial-time Iterative Hard Thresholding (IHT) algorithm with provable approximation guarantees. Empirical evaluations show that, unlike state-of-the-art baselines such as LIME and MAPLE, our explanations satisfy both the anchoring and sparsity constraints by construction, while consistently achieving lower relevance error.

0.25

Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

cs.LG cs.AIstat.ML ·2026-09-11 ·Hrad Ghoukasian, Anastasis Kratsios
theory similarity 0.57
Abstract · 58 pages, 7 figures, 6 tables

As compute scales, models evolve, and training algorithms advance, our ability to explain the increasingly powerful AI systems they enable is eroding. To help safeguard interpretability, we introduce a specialized training algorithm (MACCHIATO) that jointly constructs (i) an explicitly structured $\operatorname{ReLU}$-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$ gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$-circuit classes and exactly compile the resulting circuit into a $\operatorname{ReLU}$-MLP; we combine $\operatorname{ReLU}$-MLP circuit compilation, ESPRESSO logic minimization, and influence-based variable selection. Roughly speaking, our interpretability certificate is complemented by a statistical guarantee: under the theorem's influence-recovery conditions, if each of the $m$ stage-wise residuals depends on at most $\log_2(B)$ bits, a sample-splitting variant of our algorithm trained on $T$ observations returns a six-layer $\operatorname{ReLU}$-MLP (counting the input layer) of width $\mathcal{O}(mB)$ with truth-table error $\mathcal{O}\bigl(\sqrt{m(B+\log(m/δ))/T}\bigr)$. On synthetic random-junta tasks, our networks outperform depth- and hidden-width-matched Adam-trained MLPs in several data-sparse or projection-aligned regimes, while the trained ReLU-MLPs are stronger in others. Moreover, in our explicit PyEDA truth-table implementation, the iterative procedure completes in regimes where flat ambient-dimensional ESPRESSO exceeds the three-hour computational budget.

0.49

Exactness at Inference: A Representational Criterion for Out-of-Distribution Generalization

cs.LG cs.AIcs.LO ·2026-09-21 ·Filipe Marinho Rocha, Inês Dutra, Vítor Santos Costa, Luís Paulo Reis
similarity 0.57
Abstract

A model generalizes outside its training distribution only when it computes a representation structurally equivalent to the generating mechanism, not an approximation fitted to it. Such equivalence is necessary for exactness in and out of distribution, and extrapolation is governed by this exactness at inference, whatever its realization. Tensor Logic shows this: a zero-temperature contraction is equivalent to discrete logic, deducing in place with no artefact extracted, its tensors Boolean, its embeddings orthonormal, only its arithmetic continuous. Lacking infinite recursion it reaches Datalog, not Prolog, and though exact over closed domains it needs external memory to bind a novel entity. The criterion needs neither a discrete representation nor an extracted expression, and constrains inference, not training: an exact marginal in $[0,1]$ passes, a Neural Network thresholded to a hard label does not. Logic Tensor Networks fail it, while differentiable ILP and Tensor Logic at $T=0$ pass. Piecewise-affine extrapolation divergence and an inability to bind novel entities are two faces of a shortfall in exact representability. For hybrid architectures, a propagation rule follows: the output inherits the bounds of every fitted estimator on its path, explaining which axes fail in equivariant models and the ARC-AGI induction/transduction split. Only an exact hypothesis class certifies what the training data leave underdetermined: on a law-derived partition it finds the $56.3\%$ of distant queries that are answerable, which ensembles meet with false confidence and distance metrics rank backwards. Common inductive biases, from symmetries to memory, reach exactness only because humans inject them, an argument for inducing exact representations rather than fitting surrogates whose residuals, even at the arithmetic floor in training, diverge outside the data and compound under composition.

0.25