# Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 25 Jul 2024.

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

- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [Semirings for Probabilistic and Neuro-Symbolic Logic Programming](https://mlsanity.com/paper/2402.13782/) (2024)
- [On Compiling DNNFs without Determinism](https://mlsanity.com/paper/1709.07092/) (2017)
- [SharpSAT-TD in Model Counting Competitions 2021-2023](https://mlsanity.com/paper/2308.15819/) (2023)

## Abstract (arXiv)

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.