The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models
Identifies fundamental expressivity limitations of probabilistic circuits for language modeling, providing theoretical and empirical insights for researchers working on generative models.
Probabilistic Circuits (PCs) lag behind Transformer-based LLMs in language modeling due to two bottlenecks: an output bottleneck from parameterizing predictions in probability space (mitigated by logit-space parameterization) and a context-encoding bottleneck where structured-decomposable PCs are limited to fixed routing structures, causing degradation on heterogeneous dependencies. Decomposable PCs are theoretically more expressive but hard to optimize.
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.