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:
- To isolate the Output Bottleneck:
- 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.
- Prob-Transformer: A standard Transformer modified to output a convex combination of basis distributions directly in probability space, mimicking a PC's output layer.
- To isolate the Context Encoding Bottleneck:
- 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.
- 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).
- 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.
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