Tractable Probabilistic Inference via Knowledge Compilation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 244 papers53 conceptsfrozen 2026-10-04

In many areas of artificial intelligence, we face a fundamental conflict: we want the expressive power of formal logic, but we cannot afford its computational cost. Tasks like counting the number of ways a formula can be satisfied (#P-complete) or finding the marginal probability of an event in a complex network are notoriously difficult.

The research direction of Knowledge Compilation (KC) offers a way out of this bottleneck. As Adnan Darwiche and Pierre Marquis explain in Knowledge compilation, the core idea is to shift the computational burden. By pre-processing (compiling) a complex logical theory into a "tractable" representation, we can transform NP-hard or #P-hard problems into simple operations that run in polynomial—often linear—time relative to the size of the compiled structure.

From Flat Logic to Tractable Circuits

Most logical problems are framed in "flat" formats like Conjunctive Normal Form (CNF). While easy to write, CNF is difficult to reason with because the dependencies between variables are tangled. Knowledge compilation transforms these flat formulas into deep Boolean circuits, specifically Negation Normal Forms (NNF).

The power of these circuits comes from enforcing specific structural properties. Two properties are particularly critical:

  1. Decomposability: An AND gate is decomposable if its inputs do not share any variables. This allows a large problem to be split into independent sub-problems.
  2. Determinism: An OR gate is deterministic if no two of its inputs can be true at the same time. This ensures that the paths through the circuit are mutually exclusive.

When a circuit satisfies both—becoming a deterministic Decomposable Negation Normal Form (d-DNNF)—it becomes a powerful engine for probabilistic reasoning. As Frédéric Koriche demonstrates in Compiling Combinatorial Prediction Games, representing a decision space as a d-DNNF transforms complex optimization and sampling tasks into linear-time operations, enabling real-time learning in massive, constrained environments.

Turning Logic into Arithmetic

The most profound intuition behind d-DNNFs is that they allow us to treat logic as arithmetic. If a circuit is deterministic and decomposable, we can replace every "OR" gate with an addition (+) and every "AND" gate with a multiplication (×).

This process, known as Weighted Model Counting (WMC), is the engine behind modern probabilistic logic. Daan Fierens, Guy Van den Broeck, and colleagues showed in Inference in Probabilistic Logic Programs using Weighted CNF's that by compiling logic programs into d-DNNFs, marginal inference becomes a simple pass over the circuit. Because addition and multiplication are differentiable, this also makes the entire reasoning process compatible with gradient-based learning.

Bridging the Neurosymbolic Gap

This differentiability is why knowledge compilation has become a cornerstone of neurosymbolic AI. Purely neural models often struggle with hard logical constraints or long-term temporal reasoning. Systems like NeSyA, developed by George Paliouras and Nikolaos Manginas in NeSyA: Neurosymbolic Automata, use d-DNNF circuits to bridge perceptual neural networks with symbolic automata.

By compiling logical transitions into these circuits, the system can compute the probability of a complex sequence being valid through simple arithmetic. This allows the model to outperform Transformers in low-data regimes where the "rules of the game" are known but the data is sparse. Similarly, Yaqi Xie and Harold Soh found in Embedding Symbolic Knowledge into Deep Networks. that neural networks learn and generalize logical constraints much more effectively when those constraints are presented in tractable forms like d-DNNF rather than standard CNF.

Scaling to Real-World Complexity

The utility of knowledge compilation extends far beyond theoretical AI. It is used to solve high-stakes engineering problems where failure is not an option:

The Cost of Tractability

Knowledge compilation is not a "free lunch." The process of compiling a formula into a d-DNNF can itself be exponentially difficult. However, as Adnan Darwiche and Jinbo Huang argue in The Language of Search, we can view the search for a solution as the process of building the circuit itself. By capturing the trace of an exhaustive search, we create a reusable artifact that makes all future questions about that problem easy to answer.

Whether it is identifying the most robust feature subset in a Bayesian network (YooJung Choi et al., Optimal Feature Selection for Decision Robustness in Bayesian Networks) or calculating the contribution of a specific fact in a probabilistic database (Pratik Karmakar et al., Expected Shapley-Like Scores of Boolean Functions), knowledge compilation provides the structural foundation for efficient, exact reasoning in an uncertain world.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 74 papers
  2. Version 1 · 2026-10-04 · 44 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_knowledge_compilation_tractable_knowledg_2dcca879,
  title = {knowledge compilation (tractable knowledge compilation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/knowledge-compilation-tractable-knowledge-compilation/rdr_2dcca879412a427799ec442dca2ab046},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tractable_probabilistic_inference_via_kn_2dcca879_v1,
  title = {Tractable Probabilistic Inference via Knowledge Compilation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tractable-probabilistic-inference-via-knowledge-compilation/rdr_2dcca879412a427799ec442dca2ab046/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}