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

Zhiyu Zhao, Xuejie Liu, Muhan Zhang, Anji LiuarXiv 2026 · arXiv

TL;DR

While Probabilistic Circuits (PCs) excel at exact and efficient mathematical inference, they lag significantly behind Transformer-based Large Language Models (LLMs) in autoregressive language modeling. This paper identifies two fundamental architectural bottlenecks causing this expressivity gap: a restrictive output parameterization in probability space and a rigid, fixed context-routing structure. By systematically isolating these factors, the authors demonstrate how bridging these structural mismatches can drastically improve PC performance.

What Problem Does This Paper Address?

In the generative AI landscape, Transformer-based LLMs dominate sequence modeling but act as "black boxes" when it comes to complex probabilistic reasoning. If you want to compute exact marginal probabilities, condition on arbitrary subsets of variables, or perform structured inference, Transformers require expensive approximations.

Probabilistic Circuits (PCs) are an alternative class of deep generative models designed from the ground up to support these exact queries efficiently. However, they perform poorly on standard language modeling benchmarks compared to LLMs. This paper investigates the root causes of this expressivity gap by casting both model classes under a unified autoregressive framework.

Methods

The authors analyze the models by viewing both PCs and LLMs as context-conditioned encoders ($\theta_t = \text{Encoder}(x_{<t})$) that map a prefix sequence to the predictive parameters of the next token. To isolate the architectural differences, they introduce two sets of controlled model variants:

  1. To isolate the Output Bottleneck:
  2. Logit-HMM: A variant of a Hidden Markov Model (a simple PC) that extracts a latent feature vector and passes it through an unconstrained linear layer to generate logits, rather than operating directly in probability space.
  3. Prob-Transformer: A standard Transformer modified to output a convex combination of basis distributions directly in probability space, mimicking a PC's output layer.
  4. To isolate the Context Encoding Bottleneck:
  5. The authors use Separation Rank—a mathematical measure of how deeply a function couples interactions across input partitions—to theoretically compare how Transformers and structured-decomposable PCs route information.

Datasets

The hypotheses were validated across several synthetic and real-world datasets:

  • Simple Word: A character-level English word dataset designed to induce sparse, sharply peaked next-token distributions.
  • Real-World Language Modeling Benchmarks: The Penn Treebank (PTB) and a subset of WikiText-103, both tokenized using the GPT-2 tokenizer.
  • Synthetic Topology Datasets: Local-copy (purely local token dependencies), Induction-style prefix-copy (long-range dependencies), and Mixed-topology ($D_{\text{mix}}$, combining both local and long-range tasks).
  • UD English-ATIS: A treebank dataset used for sentence-level autoregressive language modeling.

Key Insights and Ideas

  • The Geometry of Output Spaces Matters: Standard PCs parameterize predictions as convex combinations directly in probability space. This forces next-token predictions to lie within a strict geometric hull, making it incredibly difficult to capture the highly sparse, low-entropy (sharp) distributions typical of natural language. Transformers, by contrast, project into unconstrained logit space before applying a softmax, which is geometrically much more flexible.
  • The Cost of Structural Commitment: Transformers use self-attention to dynamically route information based on the specific input sequence. Structured PCs rely on a fixed tree structure (a vtree) determined at design time. The authors prove that while a PC can match a Transformer's expressivity if its tree structure perfectly aligns with the data's dependency topology, it degrades severely when forced to handle heterogeneous or mixed dependencies.

Key Results

  • Alleviating the Output Bottleneck: Across all datasets, switching to a logit-space parameterization significantly narrowed the performance gap. On the Penn Treebank dataset, the Logit-HMM achieved validation losses comparable to a standard Transformer, proving that the output space geometry is a massive constraint for standard PCs.
Figure 1: Impact of output parameterization on modeling performance. Lower validation loss is better. Across all datasets, logit-space variants improve over their probability-space counterparts within the same model family: Logit-HMM improves over HMM, and Transformer improves over Prob-Transformer. This supports the hypothesis that probability-space convex combinations impose a stronger geometric constraint than logit-space projections under a limited latent dimension.
  • The Necessity of Topology Alignment: On synthetic datasets, when the PC's internal tree layout was perfectly matched to the data's dependency structure (local vs. distant), its negative log-likelihood (NLL) approached that of a Transformer (~3.14 vs ~3.02). However, when mismatched, performance degraded catastrophically (~6.29).
Table 1: Performance of structured-decomposable PCs with two different vtree layouts and a Trans- former baseline on the local-copy and induction-style prefix-copy datasets. The standard layout is aligned with local dependencies and the shifted-induction layout is aligned with nonlocal prefix- copy dependencies. A matched layout achieves performance close to the Transformer, while a mis- matched layout degrades substantially, consistent with Theorem 1 and Proposition 1.
  • Dynamic Routing is Essential for Mixed Data: When evaluated on mixed-topology data, a standard vanilla Transformer significantly outperformed fixed-routing Transformer variants, confirming that committing to any single fixed routing structure inherently limits sequence modeling performance.
Table 2: Validation NLL of Transformers with different attention routing structures trained on the mixed-topology dataset. Vanilla denotes a standard causal Transformer with unconstrained self- attention. Adj Attn and Dist Attn denote Transformers with fixed tree-structured attention masks aligned with local and induction-style dependencies respectively. The vanilla Transformer maintains strong performance across both validation sets, while fixed-routing variants degrade on the topology mismatched with their attention layout, demonstrating that structural commitment to a fixed routing pattern incurs a performance cost under mixed dependency topologies regardless of model family.

Limitations and Future Work

While the authors proved mathematically that relaxing structured decomposability to general decomposability (by mixing components with different tree structures) makes PCs strictly more expressive, realizing this advantage in practice remains an open challenge. On real-world datasets like PTB, the initialized mixtures barely improved over single-vtree baselines. The authors note that developing advanced optimization and structure-learning algorithms capable of effectively training these broader classes of decomposable PCs is a vital direction for future work.

Summary updated

Abstract

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.
BibTeX
@misc{zhao2026expressivity,
  author = {Zhiyu Zhao and Xuejie Liu and Muhan Zhang and Anji Liu},
  title = {{The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models}},
  year = {2026},
  eprint = {2605.12940},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.12940},
}
Figure