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

• URL: http://arxiv.org/abs/2605.12940v1
• Date: Wed, 13 May 2026 03:22:10 GMT
• Title: The Expressivity Boundary of Probabilistic Circuits: A Comparison with Large Language Models
• Abstract summary: In autoregressive language modeling, Probabilistic Circuits (PCs) lag behind Transformer-based large language models (LLMs)<n>We show that structured-decomposable PCs can match Transformer separation rank on vtree-aligned partitions, but that this capacity is limited to partitions aligned with the fixed routing structure.<n>We further prove that decomposable PCs are strictly more expressive than structured-decomposable ones, though effectively optimizing them remains an open challenge.
• Score: 49.67598869075125
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Scaling Interpretable Transformers with Parity Bottleneck Layers [0.0]
  We introduce a GPT-2-scale architecture whose intermediate representations are efficient and wide / sparse by design.<n>A Deep Parity Bottleneck (DPB) replaces a learned over-complete basis with a parameter-free algebraic dictionary.<n>The ParityTransformer's features are native to the model's forwards pass by construction, addressing the question of whether SAEs probe features the model actually uses during computation.
  arXiv  Detail & Related papers  (2026-07-22T18:25:16Z)
• Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
  Existing locally constrained decoding approaches enforce constraints by myopically masking out next tokens.<n>Recent work uses sequential Monte Carlo methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge.<n>We propose a generic approach to construct proposals and potentials for SMC sampling from $p_mathrmlm( cdot mid mathrmconstraint)$.
  arXiv  Detail & Related papers  (2026-06-01T08:58:18Z)
• ABLE: Representing and Mapping LLMs via Attribution-Based Large-model Embedding [23.27523995613204]
  We propose ABLE (Attribution-Based Large-model Embedding), a framework that leverages the interpretability space to construct model representations.<n>By aggregating gradient-based feature attributions via a tokenizer-agnostic word-level alignment, ABLE captures model-specific input-sensitivity patterns.<n>Our training-free approach achieves competitive or superior performance in relation prediction, model routing, and benchmark score prediction.
  arXiv  Detail & Related papers  (2026-04-20T04:55:11Z)
• Breaking the Factorization Barrier in Diffusion Language Models [59.946071582340146]
  "Factorization barrier" impedes efficient parallel generation of diffusion language models.<n>We propose Coupled Discrete Diffusion to replace the fully-factorized output distribution.<n>We show that CoDD seamlessly enhances diverse diffusion language model architectures with negligible overhead.
  arXiv  Detail & Related papers  (2026-02-09T08:36:39Z)
• Scaling Probabilistic Circuits via Monarch Matrices [109.65822339230853]
  Probabilistic Circuits (PCs) are tractable representations of probability distributions.<n>We propose a novel sparse and structured parameterization for the sum blocks in PCs.
  arXiv  Detail & Related papers  (2025-06-14T07:39:15Z)
• On the Hardness of Approximating Distributions with Tractable Probabilistic Models [2.9726600487327093]
  We study approximating distributions with probabilistic circuits with guarantees based on $f$-divergences.<n>We show that approximating an arbitrary distribution with bounded $f$-divergence is $mathsfNP$-hard for any model that can tractably compute marginals.
  arXiv  Detail & Related papers  (2025-06-02T03:35:07Z)
• Structural Entropy Guided Probabilistic Coding [52.01765333755793]
  We propose a novel structural entropy-guided probabilistic coding model, named SEPC.<n>We incorporate the relationship between latent variables into the optimization by proposing a structural entropy regularization loss.<n> Experimental results across 12 natural language understanding tasks, including both classification and regression tasks, demonstrate the superior performance of SEPC.
  arXiv  Detail & Related papers  (2024-12-12T00:37:53Z)
• Sum of Squares Circuits [8.323409122604893]
  Probabilistic circuits (PCs) offer a framework where this tractability-vs-expressiveness trade-off can be analyzed theoretically.<n>We show that squared PCs encoding subtractive mixtures via negative parameters can be exponentially more expressive than monotonic PCs.<n>We formalize a novel class of PCs -- sum of squares PCs -- that can be exponentially more expressive than both squared and monotonic PCs.
  arXiv  Detail & Related papers  (2024-08-21T17:08:05Z)
• Scaling Up Probabilistic Circuits by Latent Variable Distillation [36.60818788233396]
  We show that latent variable distillation substantially boosts the performance of large PCs compared to their counterparts without latent variable distillation.<n>In particular, on the image modeling benchmarks, PCs achieve competitive performance against some of the widely-used deep generative models.
  arXiv  Detail & Related papers  (2022-10-10T02:07:32Z)
• HyperSPNs: Compact and Expressive Probabilistic Circuits [89.897635970366]
  HyperSPNs is a new paradigm of generating the mixture weights of large PCs using a small-scale neural network. We show the merits of our regularization strategy on two state-of-the-art PC families introduced in recent literature.
  arXiv  Detail & Related papers  (2021-12-02T01:24:43Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.