In automated reasoning, we frequently need to query complex logical formulas or probabilistic models in real time. Doing this directly on raw representations—such as an arbitrary Conjunctive Normal Form (CNF) formula—is typically NP-hard or worse. To bypass this online computational bottleneck, the paradigm of Knowledge Compilation shifts the heavy lifting to an offline phase, transforming the knowledge base into a target language that guarantees polynomial-time responses for specific queries.
However, this shift reveals a fundamental conflict: succinctness versus tractability. As Pierre Marquis notes in Compile!, languages that compress information highly efficiently often make reasoning computationally expensive, while languages that guarantee fast, polynomial-time queries frequently suffer from an exponential explosion in physical size.
The Knowledge Compilation Map
To navigate this landscape systematically, Adnan Darwiche et al. introduced a formal framework known as A Knowledge Compilation Map. This map evaluates target languages along two primary axes:
- Succinctness: The relative ability of a language to compactly represent a given piece of knowledge. If language $A$ can always represent any formula within a size polynomial to its representation in language $B$, but the reverse is not true, $A$ is strictly more succinct than $B$.
- Tractability: The set of queries (e.g., consistency, model counting) and transformations (e.g., conditioning, forgetting) that the language can execute in polynomial time.
As the authors emphasize in their updated review, Knowledge compilation, there is no single universally optimal language. For instance, while standard CNF is highly succinct, it supports very few tractable queries. Conversely, Decomposable Negation Normal Form (DNNF) or Ordered Binary Decision Diagrams (OBDDs) offer strong tractability guarantees but require significantly more memory.
This trade-off is a mathematical reality rather than an engineering limitation. As shown by Goran Gogic et al. in The Comparative Linguistics of Knowledge Representation, formalisms with identical expressive power can vary exponentially in their physical size. The choice of logic dictates storage efficiency independently of its mathematical reach.
Proving Succinctness Separations
Understanding where a language sits on the Pareto frontier requires rigorous mathematical proofs of succinctness separations and lower bounds. Without these tools, it is impossible to know whether a representation will scale or suffer from a catastrophic memory explosion.
Adnan Darwiche et al. addressed this in A Lower Bound on the Size of Decomposable Negation Normal Form by introducing "X-decompositions," providing a generalized technique to prove when certain structured representations will inevitably experience exponential growth. Similarly, Paul Beame et al. leveraged communication complexity in New Limits for Knowledge Compilation and Applications to Exact Model Counting to demonstrate that increasing the generality of a format does not guarantee smaller sizes. For certain database queries, simpler Free Binary Decision Diagrams remain polynomial while more complex Sentential Decision Diagrams (SDDs) explode exponentially.
Conversely, proving that a language is strictly more succinct requires showing it can compress functions that cause other languages to fail. For example, Simone Bova proved a long-standing conjecture in SDDs Are Exponentially More Succinct than OBDDs, establishing that SDDs provide a fundamentally more compact representation than classic OBDDs while maintaining similar tractability properties.
The Operational Cost of Compactness
Why does greater succinctness often destroy tractability? The answer usually lies in the lack of closure under basic logical operations like conjunction (AND) or disjunction (OR).
If a language is highly succinct, combining two compact formulas using an operation can cause the resulting formula's size to explode exponentially. For instance, Stefan Mengel demonstrated in No Efficient Disjunction or Conjunction of Switch-Lists that while switch-lists are compact and support fast consistency checks, combining them via disjunction or conjunction results in an exponential size increase. This makes them unsuitable for general-purpose incremental reasoning.
A similar bottleneck occurs with transformations like variable forgetting (existential quantification) or conditioning. Hélène Fargier et al. explored this in Knowledge Compilation Properties of Trees-of-BDDs, Revisited. They showed that while generalizing OBDDs into Trees-of-BDDs improves spatial compactness, it sacrifices the tractability of variable forgetting. When a representation is highly compressed, the structural properties that allow a solver to "forget" a variable locally are broken, forcing a global restructuring that causes an exponential size explosion.
Expanding the Frontier: Structural Restrictions and Hybrid Formats
To circumvent these hard limits, researchers continuously design new languages that introduce subtle structural constraints, aiming to capture the best of both worlds.
One prominent strategy is structured decomposability. Knot Pipatsrisawat et al. showed in New Compilation Languages Based on Structured Decomposability that by enforcing a shared variable tree (v-tree) across a circuit, one can enable a polynomial-time conjunction operation—a feat previously impossible for general DNNFs—allowing for efficient, incremental compilation.
Other approaches exploit structural symmetries or alternative algebraic properties to push the boundary further:
- Variable Shifting: Kengo Nakamura et al. introduced Variable Shift SDDs in Variable Shift SDD: A More Succinct Sentential Decision Diagram, which allow sub-structures to be shared across different variables if they represent identical functional templates, significantly increasing succinctness without breaking polynomial-time guarantees for model counting.
- Signed Edges: Ryoma Onaka et al. proposed an And-Sum circuit with signed edges in An And-Sum Circuit with Signed Edges That Is More Succinct than SDD, expanding the succinctness of decision diagrams by allowing negative weights/edges while preserving tractability for complex queries.
- Restricted Weak Decomposability: Petr Illner introduced pwDNNF and nwDNNF in New Compilation Languages Based on Restricted Weak Decomposability, bridging the gap between highly compact but less functional weak DNNFs and fully functional DNNFs to enable polynomial-time cardinality and optimization queries.
Application-Driven Trade-Offs
Ultimately, the choice of where to sit on the succinctness-tractability curve depends entirely on the application. In model-based diagnosis, Jinbo Huang et al. demonstrated in On Compiling System Models for Faster and More Scalable Diagnosis that moving from OBDDs to the more succinct DNNF format unlocked massive scalability gains.
This improvement occurred because diagnostic tasks do not require the full suite of tractable queries that OBDDs provide. By matching the representation's tractability precisely to the queries needed by the task, practitioners can minimize memory overhead and maximize performance.
Key Foundational Work
A Knowledge Compilation Map (2002) — contributed 3 concept elements to this direction.
The Comparative Linguistics of Knowledge Representation (1995) — contributed 2 concept elements to this direction.
Knowledge Compilation Using Theory Prime Implicates (1995) — contributed 1 concept elements to this direction.