Mitigating Representation Size Explosion in Logical Compilation

74 concepts63 papers

Automated reasoning relies on a fundamental trade-off between expressiveness and tractability. High-level formalisms—such as first-order logic, intuitionistic logic, and answer set programming—allow humans to specify complex constraints compactly. Conversely, modern downstream engines like Boolean Satisfiability (SAT) and Satisfiability Modulo Theories (SMT) solvers are incredibly fast but require simple, flattened inputs like Conjunctive Normal Form (CNF).

The bridge between these two worlds is translation: grounding, bit-blasting, or compiling high-level logic into primitive constraints. However, this bridge frequently encounters a severe computational bottleneck: representation size explosion. When we strip away high-level abstractions, we must explicitly enumerate implicit relationships, causing the resulting formulas, rules, or circuits to grow exponentially.

The Mechanics of Formula Bloat

Why does flattening logic cause an exponential increase in size? The explosion is primarily driven by the need to unroll high-level language features into primitive Boolean operations.

For instance, in Embedding Intuitionistic into Classical Logic, Pluska et al. demonstrate that translating intuitionistic logic into classical formats triggers an exponential size explosion when dealing with nested implications or universal quantifiers. Similarly, converting non-clausal formulas into solver-ready CNF formats forces a difficult trade-off between formula size and search space complexity, as analyzed by Navarro Pérez et al. in Generation of Hard Non-Clausal Random Satisfiability Problems.

When translating first-order logic or complex combinatorial problems into propositional clauses, a phenomenon known as "clause explosion" occurs. As Zhang observes in ModGen: Theorem Proving by Model Generation, and Zhang et al. reinforce in Improving First-order Model Searching by Propositional Reasoning and Lemma Learning, naive grounding multiplies constraints across large domains, generating a massive volume of clauses that can quickly exhaust system memory.

This issue extends to specialized theories and data structures:

Structural Loops and Framework Translations

The explosion is not merely a byproduct of domain size; it is deeply tied to the structural features of the source logic. In Answer Set Programming (ASP), converting non-tight logic programs or disjunctive rules into propositional logic requires mapping complex dependency structures.

In On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic, Lin et al. point out that this conversion often suffers from an exponential increase in rules or atoms. Lee explains the root cause in A Model-Theoretic Counterpart of Loop Formulas: the number of loops within a logic program can grow exponentially relative to its size. Translating every loop into a SAT-compatible formula causes a massive constraint explosion.

Furthermore, the authors of Eliminating Disjunction from Propositional Logic Programs under Stable Model Preservation show that eliminating disjunction from logic programs inherently risks an exponential increase in the total number of rules, highlighting a fundamental trade-off between compact representation and expressive simplicity.

The Memory Wall in Knowledge Compilation

A parallel challenge occurs in Knowledge Compilation (KC), where a static knowledge base is transformed into a "tractable" target representation (such as d-DNNFs, Sentential Decision Diagrams, or Horn approximations) to enable polynomial-time queries.

As Marquis outlines in Compile!, and Darwiche demonstrates in A Compiler for Deterministic, Decomposable Negation Normal Form, this process suffers from a worst-case exponential increase in representation size compared to the original formula. Even when compiling machine learning models into logical circuits for formal verification or explanation, Huang et al. note in Tractable Explanations for d-DNNF Classifiers that the compilation step frequently triggers an exponential increase in size.

Crucially, this explosion can happen during the compilation process itself, even if the final output is reasonably sized. In A Top-Down Compiler for Sentential Decision Diagrams, Oztok et al. identify this as intermediate size explosion. When merging small components bottom-up into a larger structure, the temporary representations can exceed memory limits and crash the compiler before it ever reaches the final, manageable form.

Algorithmic Solutions to Size Explosion

To make automated reasoning scalable, researchers have developed several distinct paradigms to bypass or mitigate formula growth.

Lazy and Hybrid Encodings

Traditional "eager" translations translate the entire problem upfront into Boolean formulas, which Lahiri et al. show can generate unsustainably large SAT problems in The UCLID Decision Procedure. Modern solvers instead adopt "lazy" reductions, as demonstrated by Nötzli et al., where complex primitives are expanded incrementally only when conflicts are detected, keeping the active formula small.

Approximation and Sampling

If exact representations are too large, we can trade absolute precision for space. In Incremental Algorithms for Approximate Compilation, Venturini et al. introduce incremental algorithms that compile only the most probable or preferred solutions, achieving massive space savings while retaining high query accuracy. Similarly, Friedman et al. integrate knowledge compilation with importance sampling in Approximate Knowledge Compilation by Online Collapsed Importance Sampling to scale exact inference to large graphical models without hitting the memory wall.

However, there are theoretical limits to this approach. In Lower Bounds for Approximate Knowledge Compilation, de Colnet proves that even if a small margin of error is allowed, certain logical functions still fundamentally require exponentially large representations, establishing a strict theoretical lower bound on approximate reasoning.

Extended Target Formalisms

Rather than forcing complex constraints into standard CNF, researchers modify the target language itself to support higher-level constructs natively. For instance, the framework introduced in Extended Conjunctive Normal Form and An Efficient Algorithm for Cardinality Constraints allows local search solvers to handle cardinality constraints natively. This completely avoids the formula bloat and auxiliary variable explosion caused by traditional encoding methods, ensuring that the underlying solver is not overwhelmed by the sheer volume of generated constraints.

Key Foundational Work

Semantical and Computational Aspects of Horn Approximations (1993) — contributed 1 concept elements to this direction.
Forming Concepts for Fast Inference (1992) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_representation_size_explosion_3b17527b,
  title = {representation size explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/representation-size-explosion/rdr_3b17527b4fd644ae9db969df3e2285ab},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_representation_size_explosion_3b17527b_v2,
  title = {representation size explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/representation-size-explosion/rdr_3b17527b4fd644ae9db969df3e2285ab/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake