# Enhancing Query Efficiency for d-DNNF Representations Through Preprocessing

arXiv: https://arxiv.org/abs/2607.11492 · HTML: https://mlsanity.com/paper/2607.11492/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 31 references that are in the map.
- First posted on arXiv 13 Jul 2026.

## Builds on (most cited first, 5 of 5)

- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [A Scalable and Nearly Uniform Generator of SAT Witnesses](https://mlsanity.com/paper/1304.1584/) (2013)
- [Arjun: An Efficient Independent Support Computation Technique and its Applications to Counting and Sampling](https://mlsanity.com/paper/2110.09026/) (2021)
- [Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries](https://mlsanity.com/paper/2012.11965/) (2020)
- [Tight Fine-Grained Bounds for Direct Access on Join Queries](https://mlsanity.com/paper/2201.02401/) (2022)

## Abstract (arXiv)

In this paper, we investigate preprocessing techniques aimed at improving the efficiency of accessing models of propositional formulas represented in conjunctive normal form (CNF). We focus on three fundamental tasks: uniform sampling, direct model access, and model enumeration. Our analysis reveals that most state-of-the-art preprocessors, when they do not preserve formula equivalence, are generally unsuitable for these tasks. In contrast, we demonstrate that preprocessors which preserve model counts can be effectively leveraged, provided relevant preprocessing information is maintained. To validate our approach, we perform extensive experiments on a diverse suite of benchmarks from multiple domains. The experimental results show that our preprocessing methods are both efficient and robust, yielding significant performance improvements for model access queries when CNF formulas are compiled into d-DNNF representations.