In the world of automated reasoning, there is a standard "tax" that most systems pay: the conversion to Conjunctive Normal Form (CNF). To use the powerful SAT and resolution solvers developed over the last few decades, we typically take complex, hierarchical logical formulas and flatten them into a long list of simple clauses.
While this flattening makes the underlying algorithms easier to implement, it comes at a steep cost. Research spanning five decades suggests that by destroying the original "shape" of a problem, we lose the very structural cues that make efficient reasoning possible.
The CNF Tax: Exponential Blow-up and Information Loss
The most immediate problem with clausal conversion is size. As Neil V. Murray and Erik Rosenthal noted in their work on Path Dissolution, converting logic into CNF often triggers an exponential explosion in the number of literals. A compact formula that fits on a napkin can turn into a multi-gigabyte file once normalized.
But the deeper cost is semantic. Mark E. Stickel argued as early as 1982 in A Nonclausal Connection-Graph Resolution Theorem-Proving Program that reasoning directly on general formulas preserves the "pragmatic structure" and intent of the original rules. When you flatten a formula like If (A and B) then (C or D), you lose the directional "if-then" relationship that guides human-like deduction. Arthur J. Nevins echoed this, noting that maintaining the original structure preserves the heuristic information used by experts to navigate search spaces.
Why Structure Matters for Search
If you treat a logic problem as a flat list of constraints, the solver has to rediscover the relationships between variables from scratch. If you preserve the structure, the solver can "see" the hierarchy.
- Structural Pruning: In Exploiting QBF Duality on a Circuit Representation, Alexandra Goultiaeva and Fahiem Bacchus showed that by using a circuit-based representation instead of CNF, a solver can identify "don't care" variables—parts of the logic that cannot affect the final outcome. This allows the solver to prune entire branches of the search tree that a CNF-based solver would be forced to explore.
- Symmetric Learning: Lintao Zhang demonstrated in IQTest that maintaining both Conjunctive and Disjunctive forms (CCDNF) allows a solver to treat conflicts and satisfactions symmetrically. This structural awareness helps the solver recognize when a sub-problem is already satisfied, preventing redundant work.
- Targeted Interventions: When a search hits a dead end, a structural solver can trace the failure back to a specific quantifier or sub-formula. Sunil Issar developed path-focused duplication to exploit this, duplicating only the specific parts of a formula causing an impasse rather than expanding the entire problem globally.
Preserving Domain Physics
The benefits of structural preservation are most visible in specialized domains like hardware verification and planning.
In bit-vector arithmetic, "bit-blasting" (converting everything to individual bits) destroys the high-level arithmetic relationships. Susmit Jha and Sanjit A. Seshia showed with the Beaver solver that non-clausal solvers can significantly outperform CNF-based ones by keeping word-level information intact. Similarly, Andreas Fröhlich and Armin Biere developed BV-SLS, which searches for solutions at the "word level," exploiting the actual math of the problem rather than just the bits.
In automated planning, Guillem Francès and Hector Geffner found that retaining first-order structural information allows planners to better understand "domain physics." By not flattening the problem into simple propositions, the planner can use more informed heuristics to find better plans faster.
Modern Resurgence: LLMs and Symbolic Layers
The drive to preserve structure has found new life in the era of Large Language Models (LLMs). Researchers are finding that converting natural language reasoning into rigid formal logic or vector embeddings can strip away critical semantic context.
Jay Vaghasiya and colleagues introduced CoreThink, a symbolic reasoning layer that keeps reasoning within a structured natural language framework. By avoiding the "lossy" conversion to intermediate formalisms, they maintain the nuanced linguistic distinctions necessary for long-horizon tasks. Similarly, the SCOPE framework by Huimin Xu preserves non-mathematical logical transitions during reasoning compression, ensuring that the "proof-like coherence" of a solution isn't lost when optimizing for efficiency.
Conclusion
The recurring lesson across these papers—from the early work of Richard Fikes to modern SMT solvers—is that representation is not neutral. When we force logic into a flat, clausal format, we are not just changing the syntax; we are throwing away the map of the search space. By reasoning directly on the "natural" non-clausal structure of a problem, we allow our algorithms to see the shortcuts, dependencies, and symmetries that make complex reasoning tractable.