🤖 machine learning

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

This paper identifies and analyzes the expressivity gap between Probabilistic Circuits and Large Language Models in autoregressive language modeling, revealing that while logit-space parameterization and decomposable architectures can mitigate specific bottlenecks, the fixed routing structure of structured-decomposable PCs fundamentally limits their ability to model heterogeneous dependency topologies compared to Transformers.

Original authors: Zhiyu Zhao, Xuejie Liu, Muhan Zhang, Anji Liu

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiyu Zhao, Xuejie Liu, Muhan Zhang, Anji Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach two different types of robots how to predict the next word in a sentence. One robot is a Large Language Model (LLM), like the ones powering modern chatbots. The other is a Probabilistic Circuit (PC), a type of model known for being mathematically "honest" and able to calculate exact probabilities without guessing.

For a long time, the LLM robot has been winning at language tasks, while the PC robot has been struggling. This paper asks: Why is the PC robot so much worse at language, even though it's theoretically very powerful?

The authors found that the PC robot isn't failing because it's "dumb." It's failing because of two specific bottlenecks (traffic jams) in how it thinks and speaks.

1. The "Output Bottleneck": The Paint Mixer vs. The Laser Printer

Think of the LLM as a Laser Printer. When it decides what word to say next, it shoots out a list of "scores" (logits) for every possible word in the dictionary. It doesn't care if the scores are weird numbers; it just prints them out, and a final filter (Softmax) turns them into a sharp, clear picture where one word stands out brightly and the rest fade away. This is perfect for language, where context usually points to one very specific word.

The PC robot, however, acts like a Paint Mixer. It tries to create the next word by mixing together a few pre-made "base colors" (probability distributions).

The Problem: If you need a very sharp, specific color (like a bright red that represents a single word), mixing a few base paints in a bucket often results in a muddy, blurry color. You can't easily make a "sharp" distribution by just averaging others.
The Fix: The paper shows that if you let the PC robot stop mixing paints in the bucket and instead shoot out "scores" like the Laser Printer (working in "logit space" instead of "probability space"), it suddenly gets much better at language. It narrows the gap significantly.

2. The "Context Bottleneck": The Fixed Train Tracks vs. The Dynamic Road

This is the bigger issue. Imagine the robot needs to look back at the previous words to understand the current one.

The LLM (The Dynamic Road): The LLM uses a mechanism called "Self-Attention." Imagine a GPS that can instantly draw a new road connecting any two points in the sentence, no matter how far apart. If the sentence is "The cat sat on the mat," the LLM can instantly draw a road between "cat" and "mat" even if there are 50 words in between. It adapts its connections based on what the sentence actually needs.
The PC (The Fixed Train Tracks): The PC robot is built on a rigid structure called a vtree (a fixed tree diagram). Imagine a train system where the tracks are laid down permanently before the train ever runs.
- If the sentence structure matches the tracks (e.g., local words connecting to their immediate neighbors), the PC runs smoothly and performs almost as well as the LLM.
- The Problem: If the sentence requires a connection that the tracks don't support (e.g., connecting the first word to the last word in a specific way), the PC gets stuck. It can't reroute. It's like trying to drive a car on a train track that goes the wrong way.

The paper proves that while the PC can theoretically handle complex connections, it can only do so if the "train tracks" happen to be laid out exactly right for that specific sentence. Since real language is messy and changes its structure constantly, the PC's fixed tracks are a major handicap.

The "Super-PC" Idea

The authors also tested a "Super-PC" idea. What if we let the PC robot have multiple sets of tracks and choose the best one for each sentence?

The Theory: Mathematically, this "loose" version of the PC is strictly more powerful than the rigid one.
The Reality: While it works better in simple, made-up tests, it's very hard to train these flexible models on real-world data. The paper concludes that while we know how to make them more powerful, we haven't yet figured out the best way to teach them to learn effectively.

Summary

The paper concludes that Probabilistic Circuits aren't "broken," they are just mismatched for language:

They mix paint instead of printing scores: Changing how they output predictions helps a lot.
They are stuck on fixed tracks: They can't dynamically connect words like LLMs do, which hurts them when the sentence structure gets complex.

If we can fix the "paint mixing" issue and find a way to train flexible "track-switching" models, PCs might finally catch up to LLMs in language tasks while keeping their special ability to do exact math.

Technical Summary: The Expressivity Boundary of Probabilistic Circuits

Problem Statement

Probabilistic Circuits (PCs) are a class of deep generative models distinguished by their ability to support exact and efficient probabilistic inference (e.g., marginalization and conditioning). Despite this theoretical advantage, PCs lag significantly behind Transformer-based Large Language Models (LLMs) in autoregressive language modeling tasks. While prior work has analyzed PC expressiveness in isolation or compared subclasses within the tractable family, the root causes of the performance gap between tractable PCs and dominant neural sequence models remain unclear. This paper seeks to identify the structural bottlenecks limiting the expressivity of PCs when applied to language modeling.

Methodology

The authors establish a unified autoregressive framework to enable a direct, head-to-head comparison between PCs and LLMs. Both model classes are cast as context-conditioned encoders that map a prefix $x_{<t}$ to predictive parameters $\theta_t$ for the next token $X_t$ .

The analysis decomposes the expressivity gap into two structural bottlenecks:

The Output Bottleneck: Investigating how internal representations are translated into vocabulary distributions. LLMs operate in logit space (unconstrained vectors normalized by softmax), whereas standard PCs operate in probability space (convex combinations of basis distributions).
The Context-Encoding Bottleneck: Analyzing the capacity of encoders to fuse information across context variables. LLMs use dynamic self-attention, while structured-decomposable PCs rely on fixed routing structures defined by a vtree (a binary tree governing variable scope splits).

The study employs a combination of theoretical proofs (using separation rank as a complexity measure) and controlled empirical experiments. The experiments involve:

Comparing standard Hidden Markov Models (HMMs, a PC subclass) and Transformers against modified variants: Logit-HMM (PCs with logit-space output) and Prob-Transformer (Transformers with probability-space output).
Evaluating performance on synthetic datasets with manipulated dependency topologies (local vs. induction-style) and real-world benchmarks (Penn Treebank, WikiText-103, UD-ATIS).
Testing the relaxation of structured decomposability to general decomposability to assess the impact of fixed routing.

Key Contributions and Results

1. The Output Mismatch

The paper demonstrates that the geometric domain of the output parameterization significantly impacts performance.

Finding: Natural language distributions are often sharp (low-entropy). Representing these as convex combinations in probability space (standard PCs) imposes stricter geometric constraints than unconstrained linear mappings in logit space (Transformers).
Evidence: In controlled experiments, Logit-HMMs (PCs using logit-space outputs) substantially outperform standard HMMs and narrow the gap with Transformers. Conversely, forcing a Transformer to use probability-space outputs (Prob-Transformer) degrades its performance.
Conclusion: Adopting a logit-space parameterization for PCs substantially narrows the expressivity gap, suggesting that the standard probability-space constraint is a primary bottleneck.

2. The Routing Mismatch (Context Encoding)

The paper analyzes the capacity of structured-decomposable PCs to capture dependencies using separation rank.

Theoretical Result (Theorem 1): Structured-decomposable PCs can match the separation rank of Transformers, but only on partitions of variables that are aligned with the circuit's fixed vtree.
Empirical Evidence: On synthetic datasets, a PC achieves Transformer-level performance when its vtree layout matches the data's dependency topology (e.g., local vs. induction). However, performance degrades severely when the layout is mismatched.
Generalization: This limitation is not unique to PCs; Transformers with fixed attention masks (simulating fixed routing) also fail on mixed-topology data where a single fixed structure cannot capture both local and long-range dependencies simultaneously.
Conclusion: The rigidity of fixed routing structures is a fundamental bottleneck for data with heterogeneous dependency topologies.

3. Relaxing Structured Decomposability

The authors investigate whether moving from structured-decomposable PCs (fixed vtree) to general decomposable PCs (flexible routing) resolves the issue.

Theoretical Result (Theorem 2): Decomposable PCs are strictly more expressive than structured-decomposable ones; there exist functions representable by polynomial-sized decomposable PCs that require exponential size in structured-decomposable form.
Empirical Reality: While fusing multiple structured components (a mixture of specialists) improves performance on synthetic data, the gains diminish on real-world datasets (PTB, UD-ATIS).
Conclusion: While the theoretical expressivity gap is clear, effectively optimizing and constructing decomposable PCs to leverage this advantage on real-world distributions remains an open challenge.

Significance and Claims

The paper claims to characterize the expressivity gap between PCs and LLMs not as a single failure, but as a decomposition into two specific structural mismatches:

Output Space: The constraint of probability-space convex combinations versus logit-space projections.
Routing Flexibility: The limitation of fixed vtree structures versus dynamic, input-dependent routing.

The authors assert that these findings provide concrete directions for future work:

Exploring output parameterizations beyond probability-space convex combinations (e.g., logit-space) to better model sharp distributions.
Developing learning algorithms capable of effectively optimizing the broader class of decomposable PCs to overcome the fixed-routing bottleneck.

The paper maintains a modest stance regarding the "context-encoding bottleneck," noting that while theoretical bounds are established, the practical realization of decomposable PC advantages on complex, real-world distributions is not yet fully achieved. The analysis is primarily validated on synthetic datasets with controlled topologies and standard language modeling benchmarks, acknowledging that the separation rank results characterize worst-case expressivity gaps.