# Efficient Knowledge Compilation Beyond Weighted Model Counting

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 25 references that are in the map.
- First posted on arXiv 16 May 2022.

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

- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Clingo = ASP + Control: Preliminary Report](https://mlsanity.com/paper/1405.3694/) (2014)
- [Stable Model Counting and Its Application in Probabilistic Logic Programming](https://mlsanity.com/paper/1411.5410/) (2014)
- [SLASH: Embracing Probabilistic Circuits into Neural Answer Set Programming](https://mlsanity.com/paper/2110.03395/) (2021)
- [SMProbLog: Stable Model Semantics in ProbLog and its Applications in Argumentation](https://mlsanity.com/paper/2110.01990/) (2021)
- [MAP Inference for Probabilistic Logic Programming](https://mlsanity.com/paper/2008.01394/) (2020)

## Built on by (most cited first, 6 of 6)

- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Exploiting Uncertainty for Querying Inconsistent Description Logics Knowledge Bases](https://mlsanity.com/paper/2306.09138/) (2023)
- [Fast Inference for Probabilistic Answer Set Programs via the Residual Program](https://mlsanity.com/paper/2408.07524/) (2024)
- [Symbolic Parameter Learning in Probabilistic Answer Set Programming](https://mlsanity.com/paper/2408.08732/) (2024)
- [Probabilistic Answer Set Programming with Discrete and Continuous Random Variables](https://mlsanity.com/paper/2409.20274/) (2024)
- [Variance Computation for Weighted Model Counting with Knowledge Compilation Approach](https://mlsanity.com/paper/2601.03523/) (2026)

## Abstract (arXiv)

Quantitative extensions of logic programming often require the solution of so called second level inference tasks, i.e., problems that involve a third operation, such as maximization or normalization, on top of addition and multiplication, and thus go beyond the well-known weighted or algebraic model counting setting of probabilistic logic programming under the distribution semantics. We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems. As 2AMC is to (algebraic) model counting what forall-exists-SAT is to propositional satisfiability, it is notoriously hard to solve. First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints on the resulting circuit. However, those constraints can severely increase the circuit size and thus decrease the efficiency of such approaches. We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect. Furthermore, we introduce and implement a strategy to generate a sufficient set of constraints statically, with a priori guarantees for the performance of KC. Our empirical evaluation on several benchmarks and tasks confirms that our theoretical results can translate into more efficient solving in practice. Under consideration for acceptance in TPLP.