Research map / Learning theory and algorithms / Combinatorial and search optimization

The Limits of Tractable Marginalization

ICML 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 0 citations (OpenAlex)

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.

Shows that tractable marginalization (PM) is strictly broader than what uniform finally multilinear arithmetic circuits (UFMACs) capture, via a parity-based separating function for Hamming weight marginalization, and proves UFMACs complete for virtual evidence marginalization in the real RAM model.

Problem

Whether all Boolean functions with polynomial-time marginalization admit succinct representations as (uniform finally multilinear) arithmetic circuits, the known unified model for tractable probabilistic and logical models.

Approach

Defines a hierarchy of marginalization queries (variable, Hamming weight, virtual evidence) and shows UFMACs support the stronger ones; uses CSP dichotomy theorems to build a function f_aff that is tractable for variable marginalization but #P-hard for Hamming weight marginalization, and proves real RAM completeness for virtual evidence marginalization.

Key results

• Shows f_aff (parity-constraint function) is in PM (tractable variable marginalization) but HMAR(f_aff) is #P-hard, so f_aff is not in PHM unless FP=#P.
• Proves MAC ⊆ PVM and PVM ⊆ PHM ⊆ PM, establishing a hierarchy of marginalization classes.
• Proves that a polynomial-time real RAM computing VMAR(f) implies a real RAM UFMAC for f (completeness for virtual evidence marginalization).

Surprising findings

• Tractable variable marginalization does not imply UFMAC representability under FP≠#P, answering the central question negatively.
• Corollary: unless PH collapses to Σ2, d-DNNF is not polynomially more succinct than EADT, partially resolving a knowledge compilation succinctness question.

Limitations

• Separation relies on complexity assumption FP≠#P; not unconditional.
• Completeness for virtual evidence is only shown in the real RAM model; the Turing machine question remains open.
• Open whether PVM ⊆ PHM is strict.

Experimental setup

Builds on: knowledge compilation CSP dichotomy theorems sum-product networks determinantal point processes

Closest papers by meaning

• On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.84)
• A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.83)
• Neural Network Approximators for Marginal MAP in Probabilistic Circuits (AAAI 2024 · similarity 0.83)
• Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses (NeurIPS 2026 · similarity 0.82)
• Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.82)
• On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.81)