• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Projected Model Counting: Beyond Independent Support.
Jiong Yang, Supratik Chakraborty and Kuldeep S. Meel.
In Proceedings of International Symposium on Automated Technology for Verification and Analysis (ATVA), October 2022.
The past decade has witnessed a surge of interest in practical techniques for projected model counting. Despite significant advancements, however, performance scaling remains the Achilles' heel of this field. A key idea used in modern counters is to count models projected on an independent support that is often a small subset of the projection set, i.e. original set of variables on which we wanted to project. While this idea has been effective in scaling performance, the question of whether it can benefit to count models projected on variables beyond the projection set, has not been explored. In this paper, we study this question and show that contrary to intuition, it can be beneficial to project on variables beyond the projection set. In applications such as verification of binarized neural networks, quantification of information flow, reliability of power grids etc., a good upper bound of the projected model count often suffices. We show that in several such cases, we can identify a set of variables, called upper bound support (UBS), that is not necessarily a subset of the projection set, and yet counting models projected on UBS guarantees an upper bound of the true projected model count. Theoretically, a UBS can be exponentially smaller than the smallest independent support. Our experiments show that even otherwise, UBS-based projected counting can be more efficient than independent support-based projected counting, while yielding bounds of very high quality. Based on extensive experiments, we find that UBS-based projected counting can solve many problem instances that are beyond the reach of a state-of-the-art independent support-based projected model counter.
@inproceedings{YCM22,
title={Projected Model Counting: Beyond Independent Support},
author={Yang, Jiong and Chakraborty, Supratik and Meel, Kuldeep S.},
bib2html_pubtype={Refereed Conference},
year={2022},
month=oct,
booktitle=ATVA,
bib2html_rescat={Counting},
bib2html_dl_pdf={../Papers/atva22.pdf},
abstract={
The past decade has witnessed a surge of interest in practical techniques
for projected model counting. Despite significant advancements, however,
performance scaling remains the Achilles' heel of this field. A key idea
used in modern counters is to count models projected on an independent
support that is often a small subset of the projection set, i.e. original
set of variables on which we wanted to project. While this idea has been
effective in scaling performance, the question of whether it can benefit to
count models projected on variables beyond the projection set, has not been
explored. In this paper, we study this question and show that contrary to
intuition, it can be beneficial to project on variables beyond the
projection set. In applications such as verification of binarized neural
networks, quantification of information flow, reliability of power grids
etc., a good upper bound of the projected model count often suffices. We
show that in several such cases, we can identify a set of variables, called
upper bound support (UBS), that is not necessarily a subset of the
projection set, and yet counting models projected on UBS guarantees an upper
bound of the true projected model count. Theoretically, a UBS can be
exponentially smaller than the smallest independent support. Our experiments
show that even otherwise, UBS-based projected counting can be more efficient
than independent support-based projected counting, while yielding bounds of
very high quality. Based on extensive experiments, we find that UBS-based
projected counting can solve many problem instances that are beyond the
reach of a state-of-the-art independent support-based projected model
counter.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21