Computing exact probabilities or verifying complex logical statements is notoriously difficult. In the worst case, tasks like marginalization (summing out variables) or checking logical satisfiability (SAT) force us to navigate an exponential explosion of states, rendering them NP-hard.
To bypass this bottleneck, the field of knowledge compilation translates complex logical theories and probability distributions into deep computational graphs—known as circuits—that guarantee queries can be answered in polynomial or linear time. As reviewed by Darwiche et al. (2024), this paradigm shifts the computational burden to an offline compilation phase, ensuring that online reasoning remains lightning-fast.
The secret to this tractability lies in enforcing strict structural constraints on how the circuit processes variables. The most fundamental of these constraints is decomposability, which has recently been extended into structured decomposable squaring to unlock highly expressive, non-monotonic generative models.
The Magic of Decomposability
What makes a circuit "tractable"? Consider a deep Boolean circuit like a Decomposable Negation Normal Form (DNNF). In a DNNF, an AND gate is decomposable if the sub-circuits feeding into it depend on entirely disjoint sets of variables. As Darwiche (1999) demonstrated, this single structural property allows satisfiability checking and existential quantification to be performed in linear time relative to the circuit's size.
To understand why this works, think about integration or summation. Suppose you need to compute a joint volume or sum over two variables, $x$ and $y$, for a function that splits into independent parts: $f(x, y) = g(x) \times h(y)$. Because the variables are separated, the joint operation factorizes perfectly:
$$\sum_{x, y} g(x)h(y) = \left(\sum_{x} g(x)\right) \times \left(\sum_{y} h(y)\right)$$
Instead of evaluating every combination of $x$ and $y$ together (an exponential problem), you solve two independent, smaller problems and multiply the results. Decomposable circuits scale this mathematical trick across massive, deep hierarchies. Darwiche et al. (2002) formalized these trade-offs in a "knowledge compilation map," establishing decomposability as a cornerstone for tractable reasoning.
By pairing decomposability with other structural constraints, circuits can handle an even wider menu of operations:
- Determinism: Enforcing that at most one child of an OR (or sum) node can be active for any given input enables linear-time optimization and model counting. This applies to valued formulas outside binary logic [Fargier et al. (2007)] and discriminative models like Logistic Circuits [Liang et al. (2019)].
- Smoothness: In Probabilistic Circuits (PCs), requiring all children of a sum node to share the exact same variable scope guarantees exact polynomial-time marginalization [Sidheekh et al. (2024)].
As Vergari et al. (2021) showed in their compositional atlas, preserving these structural traits allows researchers to pipeline atomic operations to compute highly complex queries, such as entropy and KL-divergence, completely tractably.
The Frontier: Subtraction and the Squaring Trick
Standard probabilistic circuits are monotonic: they are built using non-negative weights and sum operations. This means they can only ever add probability mass. To fit intricate, high-dimensional data distributions, monotonic models require a massive number of components, making them bulky and inefficient.
To gain an exponential boost in expressive power, we want subtractive mixture models. Allowing negative weights lets a circuit carve out complex probability shapes by subtracting mass from regions. However, this introduces a fatal flaw: a circuit with negative weights can output a negative value, violating the core axioms of probability.
To guarantee that the model always outputs a valid, non-negative probability while still allowing internal subtraction, we can square the entire circuit's output:
$$p(x) \propto (f(x))^2$$
While squaring solves the non-negativity problem, it completely breaks standard tractability. If a sum node in our circuit computes $f(x) = A + B$, squaring it yields:
$$(A + B)^2 = A^2 + 2AB + B^2$$
To normalize this distribution (i.e., compute its partition function), we must integrate this expression. Integrating $A^2$ and $B^2$ is straightforward if the underlying circuits are decomposable. But integrating the cross-term $2AB$ requires integrating the product of two different circuits. In general, integrating the product of two arbitrary circuits forces us to look at all pairwise combinations of their internal states, destroying our polynomial-time guarantees.
How Structured Decomposability Saves the Day
To make squaring tractable, we must upgrade standard decomposability to structured decomposability.
Standard decomposability simply requires that an AND (or product) node splits its variables into disjoint sets. It does not care how that split happens. Structured decomposability, however, mandates that every single circuit in our system decomposes its variables according to the exact same hierarchical tree, known as a variable tree (vtree).
[vtree]
/ \
{x,y} {z,w}
/ \ / \
{x} {y}{z} {w}
When two circuits, $A$ and $B$, are synchronized by the same vtree, their internal structures are perfectly aligned. As Loconte et al. (2024) demonstrated with Squared Non-Monotonic Probabilistic Circuits ($NPC^2$s), this structural alignment completely tames the cross-terms.
Because $A$ and $B$ split their variables at the exact same locations in the graph, the product $AB$ decomposes in perfect harmony. Every product operation within the cross-term multiplies sub-circuits that still operate on strictly disjoint variable scopes. Consequently, the integral of the cross-term factors completely into independent sub-integrals, allowing the entire squared circuit to be integrated and normalized in polynomial time.
Real-World Impact and Trade-Offs
Structured decomposable squaring bridges the gap between the raw expressiveness of deep generative models and the mathematical rigor of exact inference. This paradigm yields significant practical advantages across several domains:
- Hardware Efficiency: Strict structural constraints like structured decomposability are highly predictable. Trapp et al. (2022) demonstrated that this predictability maps beautifully to parallel hardware architectures (such as tensor-based operations), enabling energy-efficient exact inference on low-power edge devices without sacrificing accuracy.
- Explainable AI (XAI): Representing decision logic via decomposable circuits allows algorithms to bypass the traditional NP-hardness of finding prime implicants. Ji (2022) showed that this enables the extraction of the shortest necessary explanations in output-polynomial time, while Hirth (2023) leveraged specialized "reason circuits" to compactly encode exponentially many sufficient reasons for a model's decision.
Ultimately, as proven by Leland et al. (2025), the fundamental trade-off between a model's size and its tractability is unyielding—even when settling for approximations. Structured decomposable squaring represents a precise mathematical loophole: by enforcing rigid structural synchronization across the computational graph, we can use subtraction to compress the model's size exponentially while keeping exact inference strictly tractable.
Key Foundational Work
A Knowledge Compilation Map (2002) — contributed 2 concept elements to this direction.
Compiling Knowledge into Decomposable Negation Normal Form (1999) — contributed 1 concept elements to this direction.