🤖 AI

Enhancing Query Efficiency for d-DNNF Representations Through Preprocessing

This paper demonstrates that while non-equivalence-preserving preprocessors are unsuitable for model access tasks on CNF formulas, those preserving model counts can significantly enhance the efficiency of uniform sampling, direct model access, and model enumeration when compiled into d-DNNF representations, provided the necessary preprocessing information is retained.

Original authors: Jean Marie Lagniez, Emmanuel Lonca

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean Marie Lagniez, Emmanuel Lonca

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, tangled ball of yarn representing a complex logic puzzle. Your goal is to find specific patterns in the knots, count how many patterns exist, or pull out a random knot without looking. This is what computer scientists call "querying" a formula. The paper by Lagniez and Lonca is like a guidebook for untangling that yarn before you try to find your patterns, making the whole job much faster.

The Big Idea: Cleaning the House Before the Party

The authors discovered that how you tidy up your logic puzzle before you start working on it makes a huge difference. They tested a specific way of organizing these puzzles called d-DNNF (think of it as a super-organized, step-by-step instruction manual for the puzzle).

Their main finding is a bit of a "do this, not that" lesson:

The "Don't" List: They explicitly argue against using the most popular cleaning tools (preprocessors) that are great for just checking if a puzzle has any solution. Why? Because those tools often throw away pieces of the puzzle that change the total number of solutions. If you throw away a piece, you might think there are 5 solutions when there are actually 10. For tasks like counting solutions or picking a random one, this is a disaster. The paper shows that these "equivalence-breaking" tools are generally unsuitable for these specific jobs.
The "Do" List: Instead, they found that you can use powerful cleaning tools, but only if you keep a secret map of the pieces you removed. Specifically, if a tool removes a variable (a piece of the puzzle) because it's completely determined by other pieces, you must remember how it was determined. If you keep that map, you can clean the puzzle up, solve the easy version, and then use your map to reconstruct the answer for the original, messy version.

The Experiment: A Race Against Time

To prove this, the authors set up a massive race. They took 1,425 different logic puzzles from various real-world domains and ran them through a computer pipeline.

The Setup: They used a compiler called d4 to turn the messy puzzles into the super-organized d-DNNF format.
The Strategies: They tested four different ways to clean the puzzles first:
- No cleaning: Just run the compiler on the raw mess.
- Safe cleaning: Only remove things that definitely don't change the solution count (like removing duplicate instructions).
- Aggressive cleaning: Remove defined variables but without a strict order.
- Aggressive cleaning with a map: Remove defined variables but force the computer to follow a specific order so the "map" works perfectly.

The Results: Speeding Up by a Factor of Ten

The results were clear and measured in real time.

The "Safe cleaning" method barely helped. It only allowed the computer to solve 8 more puzzles than doing nothing at all.
The "Aggressive cleaning with a map" method was a game-changer. It allowed the computer to solve 47 more puzzles than the uncleaned version.
When it came to actually answering the questions (like finding a specific solution or picking a random one), the aggressive methods were often 10 times faster (an order of magnitude) than the safe methods.

For example, when they tried to pick 10,000 random solutions, the aggressive method hit memory limits (ran out of RAM) on only 1 puzzle, whereas the safe method ran out of memory on 15 puzzles. The aggressive method also reduced the number of times the computer gave up (timed out) from 391 down to 173.

The Catch: You Need the Right Order

There is a tiny catch for the "Direct Access" task (finding the k-th solution in a specific list). The paper explains that if you remove a piece of the puzzle, you can't just put it back in any order; you have to make sure the "map" (the logic that defines the removed piece) is built from pieces that come earlier in your list. If you don't follow this rule, the map breaks, and you can't find the right solution. The authors showed that if you plan your list order carefully (a "compatible order"), you can still use the aggressive cleaning and get the right answer.

The Bottom Line

The paper doesn't claim to have solved the unsolvable, but it provides a very strong, measured recommendation: Don't just clean your logic puzzles to make them smaller; clean them in a way that preserves the count of solutions, and keep a detailed map of what you threw away. If you do this, you can make your computer 10 times faster at finding, counting, and sampling solutions. It's like realizing that if you want to find a specific needle in a haystack, it's better to remove the hay and keep a list of where the needles were, rather than just burning the hay and hoping you remember where the needles were.

Technical Summary: Enhancing Query Efficiency for d-DNNF Representations Through Preprocessing

Problem Statement

The paper addresses the computational challenges associated with querying propositional formulas encoded in Conjunctive Normal Form (CNF). Specifically, it focuses on three fundamental tasks: uniform sampling, direct model access (retrieving the $k$ -th model under a lexicographical order), and model enumeration. These tasks are often #P-complete, making them computationally expensive on raw CNF formulas.

To mitigate this, the authors investigate the use of preprocessing techniques to transform CNF formulas into more efficient representations before compiling them into d-DNNF (Deterministic Decomposable Negation Normal Form) or decision-DNNF. The core problem is determining which preprocessing techniques are suitable for these specific queries. The authors note that while many state-of-the-art preprocessors are effective for SAT solving or model counting, they may alter the solution space in ways that render them unsuitable for tasks requiring exact model counts or specific model ordering, such as direct access and uniform sampling.

Methodology

The authors propose a pipeline where a CNF formula is first preprocessed, then compiled into a decision-DNNF representation using the d4 compiler, and finally queried using the decdnnf_rs tool. The study systematically evaluates various preprocessing strategies based on the type of logical equivalence they preserve:

Equivalence-Preserving Techniques: These include vivification, backbone identification, and occurrence reduction. These methods preserve the full set of models ( $Mod(\Sigma_1) = Mod(\Sigma_2)$ ) and are generally applicable to all query types.
Satisfiability-Preserving Techniques: Techniques like variable elimination and blocked clause elimination preserve satisfiability but not the number of models. The authors prove (Proposition 1) that these are unsuitable for direct access, uniform sampling, and model enumeration because they destroy the ability to retrieve the original models.
Model-Count-Preserving Techniques: The paper focuses on eliminating defined variables (variables whose values are functionally determined by others, either implicitly or explicitly). While these techniques preserve the number of models, they alter the model set itself.
- Theoretical Contribution: The authors demonstrate (Proposition 2) that simply eliminating defined variables is insufficient for direct access or uniform sampling unless the values of the eliminated variables can be reconstructed.
- Solution: They introduce the concept of a compatible evaluation function ( $f$ $f$ ) and a compatible order ( $\tau$ $τ$ ).
  - A compatible evaluation function computes the value of an eliminated variable based on the remaining variables.
  - A compatible order ensures that for any eliminated variable $o$ , all variables defining $o$ appear earlier in the lexicographical order.
- Proposition 4 establishes that if a compatible order is used, the $k$ -th model of the preprocessed formula $\Phi'$ can be mapped back to the $k$ -th model of the original formula $\Phi$ using the evaluation function.

Key Contributions

Theoretical Analysis of Preprocessing Suitability: The paper provides a rigorous classification of preprocessing techniques, proving that satisfiability-preserving methods (e.g., standard variable elimination) are incompatible with direct access and uniform sampling.
Conditions for Model-Count Preservation: The authors establish that preprocessing methods preserving model counts (specifically defined variable elimination) can be used for these tasks, provided that:
1. A compatible evaluation function is maintained to reconstruct eliminated variables.
2. A compatible variable ordering is enforced to ensure the lexicographical order of models is preserved during the query process.
Distinction Between Query Types: The paper highlights a critical distinction between complete model enumeration and partial model enumeration. While eliminating defined variables aids complete enumeration, it can create an exponential gap in the number of partial models, potentially making partial enumeration less efficient or impossible if the compact representation of the simplified formula does not encode the necessary partial information (Example 10).
Pseudo-Uniform Sampling: The authors show that their approach allows for the construction of a pseudo-uniform sampler that incorporates a seed, enabling reproducible sampling by controlling the order of model selection.

Experimental Results

The authors conducted extensive experiments on 1,425 benchmark instances across multiple domains, comparing four preprocessing strategies:

no: No preprocessing.
equiv: Equivalence-preserving techniques only.
#equiv-explicit: Equivalence-preserving + elimination of explicitly defined variables (without order constraints).
#equiv-explicit-ordered: Equivalence-preserving + elimination of explicitly defined variables + enforced compatible ordering.

Key Findings:

Compilation Efficiency: The #equiv-explicit-ordered strategy significantly improved the performance of the d4 compiler, solving 47 more instances than the non-preprocessed baseline. The #equiv-explicit strategy (without order constraints) solved even more instances (8 more than the ordered version) but is restricted to tasks not requiring strict lexicographical ordering (like standard uniform sampling).
Query Efficiency:
- Uniform Sampling: Using #equiv-explicit resulted in speedups of up to an order of magnitude compared to equiv. It also reduced memory usage, solving instances that caused memory timeouts in the equiv approach.
- Model Enumeration: #equiv-explicit provided faster enumeration times, though gains were less pronounced than in sampling because enumeration still requires generating all models.
- Direct Access / Sampling with Seed: The #equiv-explicit-ordered strategy was essential for these tasks. It significantly reduced timeouts (173 vs. 391 for equiv) and improved runtime efficiency, demonstrating that enforcing a compatible order does not negate the benefits of preprocessing for these specific queries.

Significance and Claims

The paper claims that while many standard preprocessing techniques are detrimental to model-based queries, preprocessing that preserves model counts can be highly effective if the necessary information (evaluation functions and variable ordering) is retained.

The authors emphasize that their approach offers a practical trade-off: by carefully selecting preprocessing techniques (specifically defined variable elimination with compatible ordering), practitioners can achieve substantial performance gains in direct access, uniform sampling, and model enumeration without sacrificing correctness. The work bridges the gap between preprocessing strategies used in SAT solving and the requirements of knowledge compilation for probabilistic and enumerative tasks.

The paper concludes modestly, noting that future work will explore applying these techniques to other advanced sampling methods and investigating alternative types of explicit definitions (e.g., NOR and NAND gates) beyond the current focus on equivalence, AND, OR, and XOR gates.