Research map / Large language models / Language, safety and interpretability

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

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Pruning and circuits in LLMs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Compares probabilistic circuits (PCs) with Transformer LLMs under a unified autoregressive view, identifying an output (probability-space convex combination) bottleneck and a context-encoding (fixed routing/vtree) bottleneck behind the PC expressivity gap.

Problem

Probabilistic circuits lag behind Transformer LLMs in autoregressive language modeling; the paper asks what structural causes explain this expressivity gap.

Approach

Casts PCs and Transformers as context-conditioned encoders producing next-token distributions, then isolates an output bottleneck (probability-space convex combinations vs logit-space softmax) and a context-encoding bottleneck (fixed vtree routing), proving a separation-rank bound for structured-decomposable PCs and a strict expressivity separation of decomposable over structured-decomposable PCs.

Key results

• On the synthetic mixed-topology dataset, the Init Mix decomposable PC reaches test NLL 5.431 vs 6.219 for the best single structured-decomposable PC.
• Structured-decomposable PC with vtree aligned to data topology achieves NLL 3.158 on adjacent data (Transformer 3.018), while a mismatched layout degrades to 6.283.
• Logit-space variants consistently outperform probability-space counterparts (HMM vs Logit-HMM, Prob-Transformer vs Transformer) across Simple Word, PTB, and WikiText; on PTB the Logit-HMM is comparable to the Transformer.

Surprising findings

• On PTB, the Logit-HMM achieves performance comparable to the Transformer, suggesting the output parameterization alone can close much of the gap in that setting.
• Relaxing to decomposable mixtures gives gains that diminish with task complexity; on PTB the initialized mixture barely improves over the single-vtree baseline.

Limitations

• Separation rank results characterize worst-case expressivity gaps rather than practical performance.
• Context-encoding bottleneck is primarily validated on synthetic datasets with controlled dependency topologies.
• Realizing the expressive advantage of decomposable PCs over structured-decomposable ones in practice remains an open optimization challenge.

Experimental setup

Datasets: Simple Word dataset Penn Treebank WikiText-103 UD-ATIS synthetic local-copy dataset synthetic induction-style prefix-copy dataset

Benchmarks: Penn Treebank WikiText-103 UD-ATIS synthetic mixed-topology dataset

Metrics: validation NLL test NLL separation rank

Baselines: HMM Transformer Prob-Transformer Standard causal Transformer Best single structured-decomposable PC

Builds on: Probabilistic circuits Structured decomposability Separation rank analysis of Transformers Softmax bottleneck

Closest papers by meaning

• On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.90)
• On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.88)
• Sum of Squares Circuits (AAAI 2025 · similarity 0.88)
• A Probabilistic Perspective on Unlearning and Alignment for Large Language Models (ICLR 2025 · similarity 0.87)
• Scaling Probabilistic Circuits via Monarch Matrices (ICML 2025 · similarity 0.87)
• Probabilistic Neural Circuits (AAAI 2024 · similarity 0.87)