# The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models

arXiv: https://arxiv.org/abs/2605.12940 · HTML: https://mlsanity.com/paper/2605.12940/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Circuits and mechanistic analysis, one of 13 directions in Mechanistic interpretability.
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 13 May 2026.

## Placed in

- Mechanistic interpretability / [Circuits and mechanistic analysis](https://mlsanity.com/mechinterp/circuits-and-mechanistic-analysis/)

## Builds on (most cited first, 27 of 27)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [On the Latent Variable Interpretation in Sum-Product Networks](https://mlsanity.com/paper/1601.06180/) (2016)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [The Inductive Bias of In-Context Learning: Rethinking Pretraining Example Design](https://mlsanity.com/paper/2110.04541/) (2021)
- [SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks](https://mlsanity.com/paper/1901.03704/) (2019)
- [Strudel: Learning Structured-Decomposable Probabilistic Circuits](https://mlsanity.com/paper/2007.09331/) (2020)
- [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Lossless Compression with Probabilistic Circuits](https://mlsanity.com/paper/2111.11632/) (2021)
- [Understanding the Distillation Process from Deep Generative Models to Tractable Probabilistic Circuits](https://mlsanity.com/paper/2302.08086/) (2023)
- [On the Expressive Efficiency of Sum Product Networks](https://mlsanity.com/paper/1411.7717/) (2014)
- [Which transformer architecture fits my data? A vocabulary bottleneck in self-attention](https://mlsanity.com/paper/2105.03928/) (2021)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Lost in Backpropagation: The LM Head is a Gradient Bottleneck](https://mlsanity.com/paper/2603.10145/) (2026)
- [TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation](https://mlsanity.com/paper/2504.18535/) (2025)
- [Rethinking Probabilistic Circuit Parameter Learning](https://mlsanity.com/paper/2505.19982/) (2025)
- [On the Sample Complexity of Learning Sum-Product Networks](https://mlsanity.com/paper/1912.02765/) (2019)
- [A Tractable Inference Perspective of Offline RL](https://mlsanity.com/paper/2311.00094/) (2023)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)

## Abstract (arXiv)

Probabilistic Circuits (PCs) are deep generative models that support exact and efficient probabilistic inference. Yet in autoregressive language modeling, PCs still lag behind Transformer-based large language models (LLMs), suggesting an important expressivity gap. In this work, we compare PCs and LLMs under a unified autoregressive formulation. First, an output bottleneck: PCs parameterize predictions as convex combinations in probability space, which struggles to represent the sharp distributions typical of language; adopting a logit-space parameterization substantially narrows this gap. Second, a context-encoding bottleneck: we prove that structured-decomposable PCs can match Transformer separation rank on vtree-aligned partitions, but show, both theoretically and empirically, that this capacity is limited to partitions aligned with the fixed routing structure, leading to severe degradation when the data exhibits heterogeneous dependency topologies. We further prove that decomposable PCs are strictly more expressive than structured-decomposable ones, though effectively optimizing them remains an open challenge.