Research map / Probabilistic and scientific modeling / Causal discovery
A Compositional Atlas for Algebraic Circuits
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.
Proposes an algebraic, compositional framework for inference on circuits over arbitrary semirings (aggregation, product, elementwise mapping), deriving tractability and composability conditions that unify and improve known results for 2AMC, PASP, MMAP, and causal backdoor/frontdoor queries.
Problem
Determining when complex inference queries that mix semirings (e.g., marginal MAP, probabilistic answer set programming, causal adjustment) can be computed tractably on algebraic circuits, which previously required instance-specific analysis.
Approach
Views inference queries as compositions of three basic operators (aggregation, product, elementwise mapping) over commutative semirings, and gives sufficient circuit-property conditions (X-determinism, X-compatibility, X-support-compatibility) that are preserved through composition, so tractable compositions can be checked systematically.
Key results
- Shows the previously stated 2AMC algorithm (smooth, decomposable, deterministic, X-first) is incorrect, proves 2AMC is #P-hard under those conditions, and shows adding X-determinism makes all 2AMC instances tractable in O(|C|) time.
- Reduces causal backdoor adjustment on probabilistic circuits from quadratic to linear complexity when Z-determinism holds, and frontdoor from cubic to quadratic.
- Proves an exponential separation: X-deterministic smooth decomposable circuits can be exponentially smaller than X-first ones as |X| grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add Z-determinism while retaining (X ∪ Z)-determinism | Backdoor inference on probabilistic circuits · Backdoor | complexity: O(|C|^2) -> O(|C|) | Helped |
| Use support-compatibility for the inner product | Frontdoor inference on probabilistic circuits · Frontdoor | complexity: cubic -> quadratic | Helped |
| Add X-determinism to smooth, decomposable, deterministic, X-first circuits | 2AMC · 2AMC | tractability: null | Helped |
| Require only smoothness, decomposability, determinism, and X-firstness, without X-determinism | 2AMC · 2AMC | tractability: null | Hurt |
| Replace X-firstness with X-determinism | Smooth, decomposable circuits · Circuit size as |X| grows | circuit size: poly(n) -> 2^{Ω(n)} | Helped |
Surprising findings
- The previously published 2AMC algorithm requiring X-firstness returns an incorrect value (1 instead of 2) on a simple smooth, decomposable, deterministic, X-first circuit.
- X-deterministic circuits can be exponentially more succinct than X-deterministic circuits that are also X-first.
Limitations
- Conditions are sufficient but not necessary and may not be tight for specific queries on specific semirings.
- Focuses on exact inference for bounded numbers of operators; approximate algorithms (e.g., for MMAP) not covered.
Experimental setup
Baselines: 2AMC X-firstness algorithm (Derkinderen et al.) backdoor/frontdoor algorithms on probabilistic circuits (Zečević et al.)
Builds on: probabilistic circuits compatibility (Shen et al.) 2AMC algebraic model counting compositional atlas for probabilistic circuits
Closest papers by meaning
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.86)
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.86)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.85)
- Compositional Reasoning with Transformers, RNNs, and Chain of Thought (NeurIPS 2025 · similarity 0.85)
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.85)
- An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.85)
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.