An Embarrassingly Parallel Model Counter

KR2025

Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning

Melbourne, Australia. November 11-17, 2025.

Edited by

ISSN: 2334-1033
ISBN: 978-1-956792-08-9

Zhenghang Xu(School of Information Science and Technology, Northeast Normal University, Changchun, China, Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China)
Minghao Yin(School of Information Science and Technology, Northeast Normal University, Changchun, China, Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China)
Jean Marie Lagniez(Univ. Artois, CNRS, CRIL, F-62300 Lens, France)

Keywords

Model counting (also known as #SAT) is a fundamental

problem in knowledge representation and reasoning, with

applications ranging from probabilistic inference to formal

verification. However, state-of-the-art model counters are

limited by computational resources on a single machine. In

this paper, we propose a novel distributed framework for

model counting, exploiting the embarrassingly parallel

nature of the problem. By decomposing the search space into

independent subproblems and distributing them across

different computation nodes, our approach achieves

near-linear scalability on practical instances. Extensive

experiments on standard benchmarks demonstrate both the

effectiveness and efficiency of our framework.