Research map / Learning theory and algorithms / Combinatorial and search optimization
Model Counting and Sampling via Semiring Extensions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Lifts selective MPF queries over semirings into MPF queries that compute model counts and uniform model samples via a semiring extension, solved by generic tensor network contraction (MCSSE).
Problem
Model counting and uniform model sampling for selective MPF queries (e.g., #SAT and discrete optimization), which are not directly expressible as MPF queries over the original semiring.
Approach
A selective semiring extension combines a selective semiring with a second semiring (counting or set-of-partial-states) so that model counting, model set, and uniform model sampling become MPF queries over the extended semiring, solvable by unchanged generic contraction algorithms.
Key results
- On 177 non-trivial model counting instances, the direct MPF query was fastest on 18 instances and MCSSE on 4, so both improve the virtual best solver alongside SharpSAT-TD, PySDD and D4.
- For model sampling, MCSSE returned a sample faster than WAPS (including compilation) on 293 instances, averaging 49.5x faster on those instances.
- On instances where WAPS was faster, WAPS was on average 7.5 times faster than MCSSE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MCSSE semiring extension for model counting | MCSSE · 2022 Model Counting Competition CNF instances | instances faster than all three state-of-the-art counters: four | Helped |
| Use direct MPF model counting | Direct MPF model counter · 2022 Model Counting Competition CNF instances | instances faster than all three state-of-the-art counters: 18 | Helped |
| Use MCSSE instead of WAPS for sampling | CNF model sampling · CNF sampling dataset | sampling time relative to WAPS: 49.5 times faster; 7.5 times faster | Mixed |
Surprising findings
- The naive MPF model counting over the Boolean semiring with (N, +, ×) is not correct in general when the semiring has more than one non-zero element; the extension is needed.
Limitations
- Slower than state-of-the-art on many small instances due to tensor network setup overhead.
- Large dense intermediate tensors on larger instances; sparse tensor einsum not established.
- Only consistent selective semirings are covered; the extension is a semiring only under consistency.
Experimental setup
Datasets: 2022 Model Counting Competition CNF benchmarks (200 problems) 773 CNF formulas constructed by Gupta et al. (2019)
Benchmarks: 2022 Model Counting Competition CNF instances 773-instance CNF sampling set from Gupta et al. 2019
Metrics: runtime number of instances solved time to one sample speedup factor
Baselines: SharpSAT-TD PySDD D4 WAPS direct MPF model counting
Builds on: marginalize a product function (Aji and McEliece 2000) algebraic model counting functional aggregate queries
Closest papers by meaning
- Maximum Model Counting (AAAI 2017 · similarity 0.90)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.87)
- Towards Real-Time Approximate Counting (AAAI 2025 · similarity 0.85)
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.85)
- An Approximate Skolem Function Counter (AAAI 2024 · similarity 0.84)
- Towards Projected and Incremental Pseudo-Boolean Model Counting (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.