Research map / Learning theory and algorithms / Combinatorial and search optimization
New Compilation Languages Based on Restricted Weak Decomposability
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.
Introduces positive and negative weak DNNF circuits (pwDNNF, nwDNNF), places them in the knowledge compilation map, and extends the Bella compiler with a isomorphism-exploiting caching scheme (Cara) for compiling CNF into these circuits.
Problem
Weak DNNF (wDNNF) circuits do not support maximum and minimum cardinality queries, which are tractable for DNNF but needed by many applications such as MPE computation; existing compilers for DNNF-like circuits produce decision-DNNF circuits that are less succinct.
Approach
Restricts weak decomposability so that variables shared among conjunction children must appear with only one polarity (positive for pwDNNF, negative for nwDNNF), which makes minimum/maximum cardinality tractable in linear time while keeping wDNNF-level succinctness; adds a caching scheme Cara that detects isomorphic residual CNFs by renaming variables via sample-moment-based sorting and copies cac
Key results
- nwDNNF circuits compiled by Bella are faster than decision-DNNF compilation by D4 on fully dense two-layer BNs (e.g., 5:5 domains with 8 nodes: 459 s vs 3296 s for D4) and have smaller circuit sizes.
- Cara speeds up compilation at the expense of larger circuits; with Cara, significantly more instances (e.g., 8 vs 10 at 60% density with domain 20) compile into nwDNNF circuits within the time limit.
- Theoretically, MinCard and MaxCard are tractable for pwDNNF/nwDNNF respectively in linear time, while wDNNF, pwDNNF and nwDNNF are shown incomparable in succinctness, with wDNNF strictly more succinct than both.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Cara caching instead of caching scheme i (ablation) | Bella compiling nwDNNF · Two-layer Bayesian networks | compilation time: 664 -> 437 | Helped |
| Use Cara caching instead of caching scheme i (ablation) | Bella compiling nwDNNF · Two-layer Bayesian networks | circuit size: 19 509 851 -> 21 705 539 | Hurt |
| Use Cara caching instead of caching scheme i (ablation) | Bella compiling nwDNNF · Two-layer Bayesian networks | compilation time: 856 -> 121 | Helped |
| Use Cara caching instead of caching scheme i (ablation) | Bella compiling nwDNNF · Two-layer Bayesian networks | circuit size: 29 159 870 -> 36 543 985 | Hurt |
| Compile into nwDNNF instead of decision-DNNF | Bella and D4 on fully dense two-layer Bayesian networks · Fully dense two-layer Bayesian networks | circuit size: 196 255.00 -> 70 503.67 | Helped |
| Increase the domain size | Bella compiling nwDNNF versus D4 compiling decision-DNNF · Fully dense two-layer Bayesian networks | compilation-time advantage: 1.007 -> 0.614; 589.727 -> 107.525 | Helped |
| Use the encoding requiring smooth decision-DNNF and weighted model counting | Bayesian-network MPE compilation · Fully dense two-layer Bayesian networks | compilation performance | Hurt |
| Use Cara caching with signed-variable renaming (ablation) | Bella compiling decision-DNNF · Two-layer Bayesian networks | circuit size | Hurt |
Surprising findings
- Cardinality queries (MinCard for pwDNNF, MaxCard for nwDNNF) are NP-hard for wDNNF circuits, despite wDNNF being more succinct than the new types.
- Caching with isomorphism (Cara) increases circuit sizes substantially for decision-DNNF but the increase is tolerable for nwDNNF circuits.
Limitations
- Experiments are limited to randomly generated two-layer BNs (DQMR-style) and the reported advantage applies mainly to that setting.
- Cara's isomorphism detection is approximate (sample-moment based) since exact isomorphism testing is not expected to be in P.
- LNV indicator variables are never chosen as decision variables in the nwDNNF encoding, which yields poorer performance on more complex topologies.
Experimental setup
Datasets: randomly generated DQMR-style two-layer Bayesian networks
Benchmarks: randomly generated two-layer BNs with large domains (DQMR-style)
Metrics: compilation time (s) circuit size number of successfully compiled instances
Baselines: D4 C2D SharpSAT-TD Bella (caching scheme i) smooth decision-DNNF encoding
Builds on: Bella compiler weak DNNF circuits DNNF circuits D4 caching scheme i MPE to weighted MaxSAT reduction
Closest papers by meaning
- A Compiler for Weak Decomposable Negation Normal Form (AAAI 2024 · similarity 0.95)
- An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.87)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.86)
- Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs (AAAI 2025 · similarity 0.85)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.84)
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.82)
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.