Research map / Learning theory and algorithms / Sample complexity
Smoothing Structured Decomposable Circuits
Andy Shih, Guy Van den Broeck, Paul Beame, Antoine Amarilli
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the near-linear structured-decomposable smoothing algorithm instead of naive quadratic smoothing | Hand-crafted circuits · Hand-crafted circuits, sizes 40k–8,500k | smoothing time: 0.82 ± 0.01 -> 0.04 ± 0.01; 50 ± 0.3 -> 0.31 ± 0.01; 293 ± 2 -> 0.74 ± 0.04; 6050 ± 20 -> 4.13 ± 0.09 | Improved |
| Replace the original All-Marginals subroutine with the linear-time algorithm | Collapsed sampling on Segmentation-11 · Segmentation-11, sizes 100k–400k | All-Marginals operations: 28,494 ± 598 -> 20,207 ± 411; 55,875 ± 1,198 -> 36,101 ± 1,522; 86,886 ± 6,330 -> 56,094 ± 817 | Improved |
| Replace the original All-Marginals subroutine with the linear-time algorithm | Collapsed sampling on DBN-11 · DBN-11, sizes 100k–400k | All-Marginals operations: 172,610 ± 1,821 -> 26,807 ± 644; 344,748 ± 3,881 -> 51,864 ± 851; 626,235 ± 9,985 -> 99,567 ± 697 | Improved |
| Replace the original All-Marginals subroutine with the linear-time algorithm | Collapsed sampling on CSP-13 · CSP-13, sizes 100k–400k | All-Marginals operations: 36,531 ± 1,484 -> 20,814 ± 619; 90,352 ± 3,593 -> 38,670 ± 1,438; 122,208 ± 9,971 -> 55,269 ± 1,819 | Improved |
Closest papers by meaning
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.87)
- On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.87)
- Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.85)
- The Limits of Tractable Marginalization (ICML 2025 · similarity 0.83)
- The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models (NeurIPS 2026 · similarity 0.83)
- Sum of Squares Circuits (AAAI 2025 · similarity 0.83)
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.
