# model_counting_and_sampling_via_semiring_extensions__7a09026b.pdf

Model Counting and Sampling via Semiring Extensions

Andreas Goral, Joachim Giesen, Mark Blacher, Christoph Staudt, Julien Klaus

Friedrich Schiller University Jena, Germany {andreas.goral,joachim.giesen,mark.blacher,christoph.staudt,julien.klaus}@uni-jena.de

Many decision and optimization problems have natural extensions as counting problems. The best known example is the Boolean satisﬁability problem (SAT), where we want to count the satisfying assignments of truth values to the variables, which is known as the #SAT problem. Likewise, for discrete optimization problems, we want to count the states on which the objective function attains the optimal value. Both SAT and discrete optimization can be formulated as selective marginalize a product function (MPF) queries. Here, we show how general selective MPF queries can be extended for model counting. MPF queries are encoded as tensor hypernetworks over suitable semirings that can be solved by generic tensor hypernetwork contraction algorithms. Our model counting extension is again an MPF query, on an extended semiring, that can be solved by the same contraction algorithms. Model counting is required for uniform model sampling. We show how the counting extension can be further extended for model sampling by constructing yet another semiring. We have implemented the model counting and sampling extensions. Experiments show that our generic approach is competitive with the state of the art in model counting and model sampling.

Introduction

The marginalize a product function (MPF) framework was formally introduced by Aji and Mc Eliece (2000) who had observed that surprisingly many applications in signal processing (Kalman 1960; Viterbi 1967; Kschischang and Frey 1998; Aji 2000), probabilistic and causal inference (Baum 1972; Pearl 1993), and natural language processing (Sutton and Mc Callum 2012) fall within the same algorithmic message passing framework. The MPF framework is also known as algebraic model counting (Kimmig, Van den Broeck, and De Raedt 2017). The prototypical MPF query is computing marginals of discrete Markov random ﬁelds. A Markov random ﬁeld is a multivariate probability distribution p on a discrete sample space that factors as

ppx1, . . . , xnq

j 1 qjpx|Jq,

Copyright 2024, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

where x|J is the projection of px1, . . . , xnq onto its elements indexed by J Ă rns t1, . . . , nu. The marginal of p on the index set I is given by the following sum over a product of functions,

x1:x1 |I x|I

j 1 qj x1 |J .

A different, but closely related type of inference query asks for the probability of a most likely element in the sample space, that is,

j 1 qjpx|Jq,

which, as it turns out, is also an MPF query, when we replace additions by maximizations. In the MPF abstraction, computations are on semirings p S, , bq, which generalize the standard sum-product semiring p R, , q. Here, the standard sum-product semiring is used for computing marginals, and the maximization query is using the Viterbi semiring r0, 1s, max, . There are, however, problems that can not be directly solved by MPF queries. For instance, the maximization query for Markov random ﬁelds is often not the query we are most interested in. Instead of the maximum value we typically want to get a model, that is, an element x from the sample space that maximizes the function. Therefore, we want to answer the query

j 1 qjpx|Jq,

which is not an MPF query. For solving this query, the algorithms for answering MPF queries need to be adapted. The adaptions exploit the fact that the max-operation is selective, that is, it always returns one of its arguments. Here, we show that adapting the algorithms can be avoided. We present a general framework for lifting MPF queries over selective semirings into MPF queries for model counting and model sampling. The framework is sketched in Figure 1. It builds on a construction scheme for semiring extensions that combines a selective semiring on which we want to serve an MPF query with a second semiring that

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

MPF queries:

p S, , bq p S ˆ N ˆ X, , bq

black-box algorithm

solution in S solution in S model count in N model sample in X

Figure 1: A generic framework for lifting MPF queries ψ over selective semirings p S, , bq into MPF queries ψ for model counting and sampling. The lifted queries can be answered by the same black box algorithm that is used for answering the original MPF query. Only the semiring S needs to be replaced by the extended semiring p S ˆ N ˆ X, , bq.

is used to track additional information like sets of models or numbers of models. Model counting and sampling then themselves become MPF queries over extended semirings. Therefore, the algorithms for answering MPF queries can also be used for model counting and sampling without changes. The (black-box) algorithms just need to be instantiated with the appropriate semiring. For the experimental evaluation of our generic model counting and sampling framework, we have implemented the semiring extension and used it together with a vanilla tensor network contraction algorithm. With this implementation we can improve the virtual best solver on the actively researched model counting and sampling problems for the Boolean satisﬁability problem.

Related work. Generalizations of the MPF framework such as functional aggregate queries (FAQ) and aggregations and joins over annotated relations (AJAR), which use more than one aggregation operation, have been discussed by Khamis, Ngo, and Rudra (2016) and Joglekar, Puttagunta, and Ré (2016), respectively. Our selective semiring extension can be used also with selective aggregation operations in these frameworks. Other frameworks that are parameterized by semirings are path problems in networks (Baras and Theodorakopoulos 2010) and semiringbased constraint satisfaction problems (Bistarelli, Montanari, and Rossi 1997; Kohlas and Wilson 2008). Both frameworks can also be used with our selective semiring extension, when they are instantiated with a selective semiring, such as the min-norm semiring (Sanmartín, Damrich, and Hamprecht 2022) for path problems.

MPF Queries We need the following notation to formally introduce MPF queries. Throughout this article, D is a tuple pd1, . . . , dnq of natural numbers, rdis denotes the set t1, . . . , diu, and r Ds denotes the Cartesian product rd1s ˆ ˆ rdns. For a subset J Ď rns, DJ is the projection of D onto its components indexed by J. MPF queries are performed on discrete functions f : r Ds Ñ S, where p S, , bq is a commuta-

tive semiring. We call the aggregation and b the combination operation on S. A formal deﬁnition of commutative semirings is included in the supplemental material. For brevity, in the following, semiring always means commutative semiring. Deﬁnition 1 (MPF Query (Aji and Mc Eliece 2000)). Let f : r Ds Ñ S be a function that decomposes as

where each fj is a function deﬁned on a projection r DJs of r Ds and x is implicitly projected to x|J. For a non-empty subset I Ď rns and y P r Drnsz Is, a marginalize a product function (MPF) query asks to compute the aggregation

j 1 fj y, x .

Here, we only consider the case I rns, which means that the result ψ À x Âm j 1 fjpxq of the MPF query is a scalar, that is, an element in S. We also assume that the functions fj have unique domains, which is not a restriction, because if two functions have the same domain, then we can just replace them by their combination. Furthermore, we only consider selective semirings. The aggregation operation in selective semirings always satisﬁes s1 s2 P ts1, s2u. For MPF queries on selective semirings, not only the query result ψ is of interest, but also the elements in the domain r Ds on which ψ attains this value. These elements are called models. Selective MPF queries can have more than one model, which also makes model counting and model sampling interesting problems. Formally, given a selective MPF query ψ, the model count of ψ is given as

j 1 fjpxq à

where the symbol 1 rxs denotes the indicator function, which evaluates to 1 if x is a true statement, and to 0 otherwise. It is instructive to consider the example of model counting for the Boolean satisﬁability problem (SAT). A SAT instance ϕ Źm j 1 ϕj in conjunctive normal form (CNF) is a conjunction of clauses ϕj, which are disjunctions of literals. A literal is a Boolean variable or its negation. Any CNF problem can be phrased as an MPF query over the Boolean semiring, where S t0, 1u, : _, and b : , as follows

j 1 1 rϕjpxqs : ł

In this special case, the model counting problem can be directly formulated as an MPF query itself (Khamis, Ngo, and Rudra 2016), namely, as

j 1 1 rϕjpxqs

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

over the semiring p N, , q. This works, because there is only one non-zero element, namely, 1, in the Boolean semiring. In general, however, when there is more than one non-zero element, this construction does not work anymore. A proof is included in the supplemental material. In this article, we show how to formulate model counting problems and model sampling problems for general selective MPF queries again as MPF queries. For doing so, we introduce a framework for non-trivially combining a selective semiring with any other semiring into a new semiring. We call the framework the selective semiring extension.

Selective Semiring Extension The idea behind the selective semiring extension framework is to combine a selective semiring on which we want to serve MPF queries with a second semiring that is used to track additional information like partial models or the number of partial models. To that end, the ﬁrst semiring needs to share information with the second semiring. We implement this information sharing in the aggregation operation of the combined semiring. Deﬁnition 2 (Selective Semiring Extension). For a selective semiring p S, S, b Sq and a semiring p R, R, b Rq with neutral elements 0R, 1R, the selective semiring extension deﬁnes the following combination operation b on the Cartesian product S ˆ R,

ps1, r1q b ps2, r2q ps1 b S s2, r1 b R r2q,

and the aggregation operation ,

ps1, r1q ps2, r2q s1 S s2,

pr1 b R 1 rs1 s1 S s2sq

R pr2 b R 1 rs2 s1 S s2sq ,

where 1 rxs "1R : x is a true statement 0R : x is a false statement. Unfortunately, the selective semiring extension is not always a semiring itself, because the distributive law, which is exploited in efﬁcient MPF query answering algorithms, may not hold. It is, however, a semiring if the aggregation operation on the selective semiring is consistent. The concept of consistency is captured in the following deﬁnition. Deﬁnition 3 (Consistent Semirings). A semiring p S, , bq is consistent if

s1 s1 s2, if and only if s1 b s3 ps1 s2q b s3 for all s1, s2, s3 P S with s3 0, where 0 is the neutral element for . Any semiring with multiplicative inverses, such as the sum-product semiring, the Viterbi semiring, and the tropical semiring, is consistent. Examples of consistent semirings without multiplicative inverses are the Boolean semiring and the min-norm semiring (Kim and Choi 2013; Sanmartín, Damrich, and Hamprecht 2022). Consistency proofs are given in the supplement. For consistent selective semirings S and semirings R in the deﬁnition of the selective semiring extension, we can prove that the extension is again a semiring.

Theorem 1. For consistent selective semirings S, the selective semiring extension is again a semiring.

Proof. Included in the supplement.

In the following sections, we will use the selective semiring extension as a template to construct new semirings for model counting, model sets, and model sampling.

Model Counting The model counting semiring p S ˆ N, , bq is an instantiation of the abstract selective semiring extension framework. It keeps the consistent selective semiring S in Deﬁnition 2, but instantiates the semiring R by the sum-product semiring p N, , q. We will show that for a given MPF query on S, a corresponding lifted query on SˆN gives the result of the original MPF query in its ﬁrst component and the model count in its second component. The lifted query is formally deﬁned as follows.

Deﬁnition 4 (Model Counting Query). For an MPF query

on a consistent selective semiring S, the lifted query on the model counting semiring is deﬁned as

j 1 f c j pxq

with f c j : r DJs Ñ S ˆ N, z ÞÑ fjpzq, 1 .

The number of component functions fj and their domains are not affected by lifting the query. Therefore, the structure of the queries ψ and ψc is the same. In particular, the treewidth, which determines the asymptotic computational complexity of the queries, remains the same. Also, an optimal junction tree for ψ is also an optimal junction tree for ψc.

Theorem 2 (Model Counting as MPF Query). Let ψ be an MPF query on a consistent selective semiring S and let ψc be its lifting to the model counting semiring. Then the ﬁrst component of ψc is the result of ψ, that is, À x Âm j 1 fjpxq, and the second component of ψc is the corresponding model count

j 1 fjpxq ψ

Proof. By the deﬁnition of b and of the tuples f c j pxq with pf c j pxqq1 fjpxq and pf c j pxqq2 1, we have

j 1 f c j pxq ð

j 1 fjpxq, 1

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

From the deﬁnition of we get for the ﬁrst component of ψc, ð

j 1 fjpxq, 1

j 1 fjpxq ψ,

and for the second component, ð

j 1 fjpxq, 1

j 1 fjpxq ψ

The second component thus counts the x P r Ds for which Âm j 1 fjpxq ψ, that is, the model count of ψ.

In the supplement, we generalize the construction from model counting to weighted model counting.

Model Set Another instantiation of the selective semiring extension is the model set semiring, which can be used to compute the set of all models for an MPF query. An element x1 P r Ds is a model of an MPF query ψ x bm j 1 fjpxq on a selective semiring S if

j 1 fjpx1q à

Therefore, the model set for ψ, that is, the set of all its models, is given as

MSpψq ! x1 P r Ds ˇˇˇ

j 1 fjpx1q à

j 1 fjpxq ) .

To be able to construct the model set by answering an MPF query, we need to extend S by a semiring that allows us to track partial models. To that end, we ﬁrst need to construct an appropriate semiring which we then use in the selective semiring extension of S for the model set extension. We call the constructed semiring the semiring of sets of partial states.

Semiring of Sets of Partial States The model set is a subset of the domain r Ds of the product function Âm j 1 fj. We also call the domain r Ds the set of states. The factors fj of the product function are deﬁned on projections r DJs of the domain r Ds. We call the elements of projected domains partial states. The set Ť IĎrns r DIs contains all possible partial states, and the semiring of sets of partial states is deﬁned on the power set of this set. That is, the semiring is deﬁned on

IĎrns r DIs ,

where r DIs is r DIs, with the only difference that each element in r DIs also has a reference to the index set I, which we call axis identiﬁer. That is, the axis identiﬁer of x P r DIs refers the index set I. The model set is an element MSpψq P XD that only contains states x P r Ds, but

not partial states. However, while computing the model set, we need to track sets of partial models, that is, sets of partial states in XD. In the following, whenever the set D is clear from the context, we omit the subscript D. We need some additional notation, especially for the deﬁnition of the combination operation on X P X. Partial states xi, xj P X can have different axis identiﬁers, and only share the axes in the intersection of the axis identiﬁers. Two partial states xi and xj are called compatible, if they coincide on the intersection I X J of their axis identiﬁers, that is, if xi|IXJ xj|IXJ. Remember that x|K denotes the projection of x P r DIs onto its elements indexed by K Ď I, that is, x|K pxk | k P Kq. If I X J H, then xi and xj are always compatible. For deﬁning a combination operation on X, we ﬁrst deﬁne a fusion operation on X. The fusion of compatible models xi P r DIs and xj P r DJs is the unique partial state

z xi d xj P r DIYJs

with z|I xi and z|J xj. Since the fusion operation works on partial states, but not on sets of partial states, it is not yet a combination operation on X. However, the fusion operation can be used to deﬁne a combination operation on X. This leads us to the following deﬁnition. Deﬁnition 5 (Semiring of Partial States). The semiring of partial states p X, X, b Xq is given by the aggregation operation

X : X ˆ X Ñ X, p X1, X2q ÞÑ X1 Y X2,

and the combination operation b X : X ˆ X Ñ X,

p X1, X2q ÞÑ x1 d x2 | x1 P X1, x2 P X2 compatible ( .

Of course, we need to prove that p X, X, b Xq is a semiring, which we do in the following theorem. Theorem 3. p X, X, b Xq is indeed a semiring with neutral elements 0X H and 1X tpqu, where pq P r DHs is the empty tuple.

Proof. Included in the supplement.

Model Set Semiring The model set semiring is now just the selective semiring extension of a consistent selective semiring p S, , bq, where the second semiring R is instantiated by the semiring p X, X, b Xq of partial states. Similar to the model counting extension, we can again lift an MPF query ψ on S to the model set extension. Deﬁnition 6 (Model Set Query). For an MPF query

on a consistent selective semiring S, the lifted query on the model set semiring is deﬁned as

j 1 f s j pxq

with f s j : r DJs Ñ S ˆ X, z ÞÑ fjpzq, tzu .

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

With this deﬁnition, we can prove that the lifted MPF query does indeed provide the answer to the original MPF query and the corresponding model set.

Theorem 4 (Model Set Construction as MPF query). Let ψ be an MPF query on a consistent selective semiring S and let ψs be its lifting to the model set semiring. Then the ﬁrst component of ψs is the result of ψ, that is, À x Âm j 1 fjpxq, and the second component of ψs is the corresponding model set ! x P r Ds ˇˇˇ

j 1 fjpxq ψ ) .

Proof. Included in the supplement.

As for the model counting query, the structure of the query ψ is unchanged by lifting it to the model set semiring. However, when there are many models, tracking the model set quickly dominates the computation. In the next section, we tackle this issue by sampling only one model uniformly at random instead of constructing the full model set.

Model Sampling The model set of a selective MPF query can be so large that enumerating all models explicitly can be computationally infeasible. Therefore, instead of computing the full model set, we compute an element from the model set uniformly at random. For sampling uniformly we need information about the model count and the model set. To this end, we ﬁrst combine the model counting and the model set extensions into a single extension, which we call the sampling semiring.

Model Sampling Semiring The model sampling semiring is just the selective semiring extension of a consistent selective semiring S and the product of the sum-product semiring p N, , q and the semiring of sets of partial states p X, X, b Xq. That is, R in the definition of the selective semiring extension (Deﬁnition 2) is the product semiring of p N, , q and p X, X, b Xq. Therefore, the combination operation b on the model sampling semiring is deﬁned as

ps1, w1, X1qbps2, w2, X2q s1bs2, w1 w2, X1b X X2 ,

and the aggregation operation on the model sampling semiring is deﬁned as

ps1, w1, X1q s2, w2, X2q ps1 s2, w, X ,

w w1 1N rs1 s1 s2s w2 1N rs2 s1 s2s

X X1 1X rs1 s1 s2s Y X2 1X rs2 s1 s2s .

As we have done before for the model counting semiring and the model set semiring, we can lift an MPF query on a consistent selective semiring S to the model sampling semiring S ˆ N ˆ X.

Deﬁnition 7 (Lifted Model Sampling Query). For an MPF query

on a consistent selective semiring S, the lifted query on the model sampling semiring S ˆ N ˆ X is deﬁned as

j 1 f j pxq

with f j : r DJs Ñ S ˆ N ˆ X, z ÞÑ fjpzq, 1, tzu . It follows directly from Theorems 2 and 4 that the model sampling query ψ computes the result of the original MPF query in its ﬁrst component, the model count in its second component, and the model set in its third component.

Uniform Model Sampling For sampling uniformly at random from the model set, we need to specify the algorithm for evaluating ψ . Therefore, we introduce a sampling representation of the elements of the semiring p X, X, b Xq of sets of partial states. From the sets X P X we only consider one representative element x P X. In the sampling representation, we need to adapt the combination and aggregation operations. The adapted operations work on the representative elements, and compute representative elements of the results of the corresponding operations on the sets of partial states. This can be accomplished as follows: either one of the representative elements xi P Xi and xj P Xj is a representative element of Xi X Xj. If xi and xj are compatible, then xi d xj is a representative element of the combination Xi b X Xj. As we have pointed out in the proof of Theorem 4 (see the supplement), when evaluating the lifted MPF query ψs, we only combine different projections tx|Ju of the same element x P r Ds, which are always compatible. This observation also holds for ψ , and therefore, the requirement of compatibility in the deﬁnition of the combination operation on X is not a restriction when evaluating model sampling queries. Thus, we can always choose a representative element of the aggregation and combination operations from the representative elements of their arguments. In the supplemental material, we provide a formal proof of this claim. Working with representative elements has the advantage that it grants us the freedom to choose them. Here, we want to choose representative elements such that we can make sure to sample models from the model set uniformly at random. This can be achieved through the following probabilistic implementation of the combination and aggregation operations: In the implementation of the combination operation, the two representative elements x1 P X1 and x2 P X2 are simply fused into a representative of X1 b X X2. The implementation of the aggregation operation is more interesting, where a representative x P tx1, x2u of X1 X X2 is chosen at random depending on the result of the aggregation of s1, s2 in S. In the case s1 s2 we always want x xi if si s1 s2 since in accordance with the selective semiring extension, the aggregation only keeps the set Xi that corresponds to the selected element si. The interesting case is

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

when s1 s2, where x is chosen with probability proportional to the cardinalities w1, w2 of X1 and X2. Therefore, we have for i P t1, 2u,

ppx xiq "1N rsi s1 s2s if s1 s2 wi{pw1 w2q if s1 s2.

Now, when we use representative elements instead of the sets of partial states, the model sampling query computes in its third element only one representative element of the model set, that is, only one model x P MSpψq. Using the probabilistic implementation of the aggregation operation on X, the lifted model sampling query returns a model from the model set that is chosen uniformly at random. We formalize this claim in the following theorem.

Theorem 5 (Uniform Model Set Sampling). Let ψ be an MPF query on a consistent selective semiring S and let ψ be its lifting to the model sampling semiring S ˆ N ˆ X. Using the probabilistic implementation of the aggregation operation on X, the third component of ψ is an element x P r Ds such that for all x P r Ds holds

ppx xq "1{MCpψq if x is a model of ψ 0 otherwise.

That is, x is drawn uniformly from all models of ψ.

Proof. We prove by induction over the size of the domain r Ds that x is drawn uniformly at random from the model set of ψ, which is subset of r Ds. For the base case, assume that r Ds has only one element z (with n components). The lifted query ψ evaluates to

ps , w , x q ð

j 1 f j pxq ð

j 1 f j pxq

j 1 f j pzq

fjpzq, 1, z|J .

Now consider the combination. By deﬁnition, b reuses the multiplication on N in the second component, which gives w MCpψq 1, and b uses the fusion operation in the third component, which gives

Therefore, ppx zq 1 1{MCpψq, and the claim holds for the base case. For the induction hypothesis, assume that the claim holds for any query on domains r Ds with k elements, that is, for any query

x Ptz1,...,zku

j 1 f j pxq, where zi P r Ds, i P rks.

For the inductive step, let r Ds tz1, . . . , zk, zk 1u be a domain with k 1 elements. By the induction hypothesis,

x Ptz1,...,zku

j 1 f j pxq looooooooooomooooooooooon

j 1 f j pzk 1q

s1, w1, x1 ps, 1, zk 1q

where s1 is the value of the MPF query ψk on the selective semiring S, w1 MCpψkq is the corresponding model count, and, by the induction hypothesis, x1 is a sample from the corresponding model set MSpψkq that has been drawn with probability ppx k x1q 1{MCpψkq 1{w1. It remains to compute the result of the ﬁnal aggregation

ps , w , x q s1, w1, x k x1 ps, 1, zk 1q.

We distinguish the two cases s1 s and s1 s. First, let s1 s. If s s1, then the claim holds by the induction hypothesis. Otherwise, if s s, then the claim is equivalent to the base case. Therefore, the claim holds true in both cases. Second, let s1 s s . By the deﬁnition of , we have MCpψk 1q w w1 1, and

ppx zk 1q 1 w1 1 1{MCpψk 1q

ppx x1|x k x1q w1{pw1 1q.

Since ppx x1|x k x1q 0 and, by the induction hypothesis, ppx k x1q 1{w1, we have

x:x zk 1 ppx x1|x k xqppx k xq

ppx x1|x k x1qppx k x1q

w1 1 MCpψk 1q.

Therefore, we get for x P MSpψk 1q,

1{MCpψk 1q if x P MSpψkq, 1{MCpψk 1q if x zk 1, 0 otherwise,

and thus ppx xq 1{MCpψ k 1q if x P MSpψ k 1q and ppx xq 0, otherwise. Therefore, also in this case, the claim holds true, which concludes the proof.

The model sampling semiring can be adapted for weighted sampling from a discrete graphical model by implementing the probabilities similar to the variable weights in weighted model counting (Darwiche 2009). Also, the sampling semiring extends naturally to a semiring on S ˆ N ˆ X k, which can be used to compute k-many independent samples with a single MPF query.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Implementation and Experiments Here, we compare our semiring extension approach with state-of-the-art methods for the model counting and sampling problems for Boolean formulas, because for these problems, mature implementations of problem speciﬁc algorithms are publicly available. The experiments were performed on an Intel i9-10980XE 18-core processor machine running Ubuntu 20.04.1 LTS with 128 GB of RAM. Each core has a base frequency of 3.0 GHz, a max turbo frequency of 4.6 GHz, and supports the AVX-512 vector instruction set.

Implementation of MPF by Tensor Networks Aji and Mc Eliece (2000) propose a junction tree algorithm for serving MPF queries. For our experiments, however, we build on the observation that MPF queries are just tensor hypernetwork expressions, which describe the computation of a tensor from its decomposition into smaller tensors. Therefore, generic tensor network contraction algorithms can be used for answering MPF queries. Since tensor expressions are ubiquitous in modern machine learning, many programming languages and frameworks support tensor computations, among them the Python package Num Py (Harris et al. 2020) and the framework Py Torch (Paszke et al. 2019), which both provide an implementation of the einsum interface to express tensor computations. We implemented the semiring extension as a stand-alone datatype in Python 3.9 and Cython 3.0. In our implementation, tensors are represented by Num Py 1.25.1 nd-arrays, and the contraction order of the tensors is computed by opt_einsum 3.3.0 (Smith and Gray 2018). We refer to our implementation as MCSSE (model counting and sampling semiring extension). The code and more details about the experiments are provided in the supplement.

Model Counting We evaluated the performance of MCSSE on the 200 problems of the 2022 Model Counting Competition for Boolean formulas in conjunctive normal form (CNF)1. We preprocessed the problems with Arjun (Soos and Meel 2022), which renders 23 of them trivial. We compared our semiring extension to the direct MPF model counting query from the MPF queries section, and to three state-of-the-art model counting softwares, namely, Sharp SAT-TD (Korhonen and Järvisalo 2021, 2023), the Python model counter Py SDD (Darwiche 2011), and D4 (Lagniez and Marquis 2017). Sharp SAT-TD with Arjun pre-processing is the winner of the 2022 model counting competition. If applicable, we always used default settings for these softwares. The direct MPF model counting was faster on 18 of the non-trivial 177 instances than any of the three state-of-theart model counters, while our semiring extension was still faster on four instances. That is, both the direct MPF model counter and our semiring extension can improve the virtual best solver, when added to the three state-of-the-art model counters.

1https://mccompetition.org/past_iterations

Model Sampling We have evaluated the performance of MCSSE for model sampling by comparing it with the recent WAPS model sampler (Gupta et al. 2019), which builds on a connection between knowledge compilation and sampling. Another recent sampler, DPSampler (Dudek, Shrotri, and Vardi 2022), uses dynamic programming and algebraic decission diagrams, but was not available in an executable form. For the comparison we used a data set of 773 CNF formulas, which has been constructed by Gupta et al. (2019) from a wide range of publicly available benchmarks. For each CNF formula in the data set, we measured the time to get one sample. Since WAPS is based on knowledge compilation, we measured compile and sample time separately for WAPS. Out of the 773 instances, there were 583 instances where at least one of the algorithms was able to return a sample within our time limit of 30 seconds. On 293 out of the 591 instances, the time used by MCSSE to return one sample was less then the total time used by WAPS. Furthermore, on 258 out of these 293 instances, MCSSE used less time than WAPS used only for sampling. On average, MCSSE was 49.5 times faster than WAPS on these instances, which means that the compilation approach does not pay off on these instances. On the remaining instances, WAPS was on average 7.5 times faster than MCSSE.

Discussion Generic frameworks such as MPF separate the interface from algorithmic details and their implementation. This has the advantage that the same algorithm, even the same implementation, can be used directly for different applications within the same framework. However, the advantage can also be a disadvantage, because it can be difﬁcult to exploit application speciﬁc information algorithmically. Nevertheless, our generic tensor network based implementation is able to compete with application speciﬁc implementations for model counting and sampling on Boolean formulas. We observe that our prototypical implementation is slower than the state of the art on two kinds of problem instances. On many small instances the overhead of setting up the tensor network is dominating. And on larger instances, large intermediate tensors can be created during the tensor network evaluation. However, there is signiﬁcant potential to further improve the performance of MPF based model counting and sampling. The creation of large intermediate tensors can sometimes be avoided by switching to a different tensor contraction order. Moreover, large intermediate tensors tend to be sparse. In our implementation, we used a dense tensor format, because there are no established implementations of einsum for sparse tensors.

Conclusion We have extended the marginalize a product function (MPF) framework for model counting and sampling on selective semirings. Although our extension is generic, it shows competitive performance on the special case of model counting and sampling for Boolean formulas, using a non-optimized implementation.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgements This work was supported by the Carl Zeiss Stiftung within the projects Interactive Inference and A virtual Werkstatt for digitization in the sciences .

References Aji, S. M. 2000. Graphical models and iterative decoding. California Institute of Technology. Aji, S. M.; and Mc Eliece, R. J. 2000. The generalized distributive law. IEEE Trans. Inf. Theory, 46(2). Baras, J. S.; and Theodorakopoulos, G. 2010. Path Problems in Networks. Synthesis Lectures on Communication Networks. Morgan & Claypool Publishers. Baum, L. E. 1972. An Inequality and Associated Maximization Technique in Statistical Estimation for Probabilistic Functions of Markov Processes. In Shisha, O., ed., Inequalities III: Proceedings of the Third Symposium on Inequalities. University of California, Los Angeles: Academic Press. Bistarelli, S.; Montanari, U.; and Rossi, F. 1997. Semiringbased constraint satisfaction and optimization. J. ACM, 44(2). Darwiche, A. 2009. Modeling and Reasoning with Bayesian Networks. Cambridge University Press. Darwiche, A. 2011. SDD: A New Canonical Representation of Propositional Knowledge Bases. In Walsh, T., ed., IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. IJCAI/AAAI. Dudek, J. M.; Shrotri, A. A.; and Vardi, M. Y. 2022. DPSampler: Exact Weighted Sampling Using Dynamic Programming. In Raedt, L. D., ed., Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022. ijcai.org. Gupta, R.; Sharma, S.; Roy, S.; and Meel, K. S. 2019. WAPS: Weighted and Projected Sampling. In Vojnar, T.; and Zhang, L., eds., Tools and Algorithms for the Construction and Analysis of Systems - 25th International Conference, TACAS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, Part I, volume 11427 of Lecture Notes in Computer Science. Springer. Harris, C. R.; Millman, K. J.; van der Walt, S.; Gommers, R.; Virtanen, P.; Cournapeau, D.; Wieser, E.; Taylor, J.; Berg, S.; Smith, N. J.; Kern, R.; Picus, M.; Hoyer, S.; van Kerkwijk, M. H.; Brett, M.; Haldane, A.; del Río, J. F.; Wiebe, M.; Peterson, P.; Gérard-Marchant, P.; Sheppard, K.; Reddy, T.; Weckesser, W.; Abbasi, H.; Gohlke, C.; and Oliphant, T. E. 2020. Array Programming with Num Py. Co RR, abs/2006.10256. Joglekar, M. R.; Puttagunta, R.; and Ré, C. 2016. AJAR: Aggregations and Joins over Annotated Relations. In Milo, T.; and Tan, W., eds., Proceedings of the 35th ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016. ACM.

Kalman, R. E. 1960. A new approach to linear ﬁltering and prediction problems. Journal of basic Engineering, 82(1). Khamis, M. A.; Ngo, H. Q.; and Rudra, A. 2016. FAQ: Questions Asked Frequently. In Milo, T.; and Tan, W., eds., Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016. ACM. Kim, K.; and Choi, S. 2013. Walking on Minimax Paths for k-NN Search. In des Jardins, M.; and Littman, M. L., eds., Proceedings of the Twenty-Seventh AAAI Conference on Artiﬁcial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. AAAI Press. Kimmig, A.; Van den Broeck, G.; and De Raedt, L. 2017. Algebraic model counting. Journal of Applied Logic, 22: 46 62. Kohlas, J.; and Wilson, N. 2008. Semiring induced valuation algebras: Exact and approximate local computation algorithms. Artif. Intell., 172(11). Korhonen, T.; and Järvisalo, M. 2021. Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters (Short Paper). In Michel, L. D., ed., 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, volume 210 of LIPIcs, 8:1 8:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Korhonen, T.; and Järvisalo, M. 2023. Sharp SAT-TD in Model Counting Competitions 2021-2023. Co RR, abs/2308.15819. Kschischang, F. R.; and Frey, B. J. 1998. Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models. IEEE J. Sel. Areas Commun., 16(2). Lagniez, J.; and Marquis, P. 2017. An Improved Decision DNNF Compiler. In Sierra, C., ed., Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017. ijcai.org. Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Köpf, A.; Yang, E. Z.; De Vito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019. Py Torch: An Imperative Style, High-Performance Deep Learning Library. In Wallach, H. M.; Larochelle, H.; Beygelzimer, A.; d AlchéBuc, F.; Fox, E. B.; and Garnett, R., eds., Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, Neur IPS 2019, December 8-14, 2019, Vancouver, BC, Canada. Pearl, J. 1993. Belief Networks Revisited. Artif. Intell., 59(1-2). Sanmartín, E. F.; Damrich, S.; and Hamprecht, F. A. 2022. The Algebraic Path Problem for Graph Metrics. In Chaudhuri, K.; Jegelka, S.; Song, L.; Szepesvári, C.; Niu, G.; and Sabato, S., eds., International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research. PMLR.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Smith, D. G. A.; and Gray, J. 2018. opt_einsum - A Python package for optimizing contraction order for einsum-like expressions. J. Open Source Softw., 3(26). Soos, M.; and Meel, K. S. 2022. Arjun: An Efﬁcient Independent Support Computation Technique and its Applications to Counting and Sampling. In Mitra, T.; Young, E. F. Y.; and Xiong, J., eds., Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022, San Diego, California, USA, 30 October 2022 - 3 November 2022. ACM. Sutton, C.; and Mc Callum, A. 2012. An Introduction to Conditional Random Fields. Found. Trends Mach. Learn., 4(4). Viterbi, A. J. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory, 13(2).

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)