An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs

Kuldeep S. Meel, Alexis de Colnet

TL;DR

Researchers have developed the first Fully Polynomial Randomized Approximation Scheme (FPRAS) for counting the models of non-deterministic read-once branching programs (nFBDDs). By moving away from the traditional requirement for independent samples and instead rigorously bounding sample dependence through "derivation paths," the authors turned a previously quasi-polynomial problem into a provably polynomial-time one.

What Problem Does This Paper Address?

In computer science, we often need to represent complex Boolean functions (logic statements that are either true or false). Branching Programs are a standard way to do this. A specific, highly flexible version is the non-deterministic free binary decision diagram (nFBDD). Unlike their more rigid "ordered" cousins (OBDDs), nFBDDs allow variables to appear in different orders along different paths, making them much more compact (succinct) for representing complex data.

However, this flexibility comes at a cost: Model Counting (#nFBDD). This is the task of calculating exactly how many different assignments of variables make the function "True." This problem is #P-hard, meaning an exact answer is computationally out of reach for large systems. Until now, the best we could do was a "quasi-polynomial" approximation—an algorithm that is faster than brute force but still slows down significantly as the problem grows. The gap was the lack of an FPRAS: an algorithm that provides a $(1 \pm \epsilon)$ approximation in time that is strictly polynomial relative to the input size and the desired accuracy.

Methods

The authors propose an algorithm called approxMCnFBDD. It operates using a bottom-up approach through the graph of the branching program, starting from the "sinks" (the final 0 or 1 outcomes) and working up to the "root."

The core innovation lies in how they handle sampling. Usually, to get a good approximation, you need independent samples. In the context of nFBDDs, generating truly independent samples is what caused previous algorithms to spiral into quasi-polynomial time.

The New Approach: Embracing Dependence Instead of fighting to keep samples independent, the authors allow them to be dependent but use a novel analysis technique to bound that dependence. They introduce:

  1. Derivation Paths: A way to map every valid assignment (model) to a unique, canonical path through the branching program.
  2. Probabilistic Filtering (reduce): A method to keep or discard samples based on calculated probabilities at each node.
  3. Median of Means: A statistical technique used at "OR" nodes ($\lor$-nodes) to keep the variance of their estimates under control.

By tracking where these "derivation paths" diverge (the Last Common Prefix Node), they proved that the variance of their estimator remains low enough to guarantee a polynomial runtime.

Datasets

As this is a theoretical paper in computational complexity, no empirical datasets were used. The "data" consists of the formal mathematical structures of nFBDDs and the proofs of the algorithm's performance guarantees.

Key Insights and Ideas

  • The Death of Self-Reducibility: Previous breakthroughs in model counting relied on a property called "self-reducibility union." The authors highlight that nFBDDs do not have this property, which is why previous methods failed.
  • The "Aha" Moment on Dependence: The most significant insight is that you don't need independent samples for an FPRAS. If you can mathematically prove that the samples aren't "too" dependent (specifically, by bounding the covariance using the structure of the branching program), you can still achieve a polynomial-time approximation.
  • Succinctness vs. Tractability: The paper reinforces the trade-off in knowledge compilation: nFBDDs are exponentially more compact than OBDDs, but they are significantly harder to query. This paper shows that while they are harder, they aren't intractably harder for approximate counting.

Key Results

  • The First FPRAS: The paper provides the first-ever algorithm that approximates #nFBDD in guaranteed polynomial time.
  • Complexity Bound: The algorithm approxMCnFBDD runs in $O(n^{11}|B|^{10}\epsilon^{-4}\log(\delta^{-1}))$ time, where $n$ is the number of variables and $|B|$ is the size of the branching program.
  • Theoretical Convergence: The authors prove that their estimate est will fall within $(1 \pm \epsilon)$ of the true count with a probability of at least $1 - \delta$.

Limitations and Future Work

  • High Exponents: While the algorithm is "polynomial," the exponents ($n^{11}$ and $|B|^{10}$) are very high. In its current form, the algorithm is a major theoretical milestone but is likely too slow for practical, real-world engineering use on large datasets.
  • Practical Adoption: The authors explicitly note that a promising direction for future work is to improve the complexity (lower those exponents) to enable practical adoption in fields like database query evaluation and artificial intelligence.
  • Generalization: The techniques developed here for bounding dependence might be applicable to even more general logic representations, such as d-DNNFs (decomposable negation normal forms).

Summary updated

Abstract

Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for representing Boolean functions. In this paper, we focus on #nFBDD, the problem of model counting for non-deterministic read-once branching programs. The #nFBDD problem is #P-hard, and it is known that there exists a quasi-polynomial randomized approximation scheme for #nFBDD. In this paper, we provide the first FPRAS for #nFBDD. Our result relies on the introduction of new analysis techniques that focus on bounding the dependence of samples.
BibTeX
@inproceedings{meel2025fpras,
  author = {Kuldeep S. Meel and Alexis de Colnet},
  title = {{An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs}},
  booktitle = {ICDT},
  year = {2025},
  url = {https://openreview.net/forum?id=y7pif9oYev},
}
Figure