Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness
This work addresses the issue of circuit bloat for researchers and practitioners in probabilistic inference, though it is incremental as it builds on existing compilation methods.
The paper tackled the problem of irrelevant subcircuits introduced by Tseitin transformations in d-DNNF Boolean circuits, resulting in an average size reduction of 77.5% when removing both Tseitin variables and artifacts, with artifacts alone reducing size by 22.2%.
Boolean circuits in d-DNNF form enable tractable probabilistic inference. However, as a key insight of this work, we show that commonly used d-DNNF compilation approaches introduce irrelevant subcircuits. We call these subcircuits Tseitin artifacts, as they are introduced due to the Tseitin transformation step -- a well-established procedure to transform any circuit into the CNF format required by several d-DNNF knowledge compilers. We discuss how to detect and remove both Tseitin variables and Tseitin artifacts, leading to more succinct circuits. We empirically observe an average size reduction of 77.5% when removing both Tseitin variables and artifacts. The additional pruning of Tseitin artifacts reduces the size by 22.2% on average. This significantly improves downstream tasks that benefit from a more succinct circuit, e.g., probabilistic inference tasks.