# ExplainFuzz: Explainable and Constraint-Conditioned Test Generation with Probabilistic Circuits

arXiv: https://arxiv.org/abs/2604.06559 · HTML: https://mlsanity.com/paper/2604.06559/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 8 Apr 2026.

## Builds on (most cited first, 11 of 11)

- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024)
- [KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI](https://mlsanity.com/paper/2410.11415/) (2024)
- [On the Relationship Between Monotone and Squared Probabilistic Circuits](https://mlsanity.com/paper/2408.00876/) (2024)
- [Building Expressive and Tractable Probabilistic Generative Models: A Review](https://mlsanity.com/paper/2402.00759/) (2024)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [TRACE Back from the Future: A Probabilistic Reasoning Approach to Controllable Language Generation](https://mlsanity.com/paper/2504.18535/) (2025)
- [Parsing with CYK over Distributed Representations](https://mlsanity.com/paper/1705.08843/) (2017)
- [Tuning Random Generators: Property-Based Testing as Probabilistic Programming](https://mlsanity.com/paper/2508.14394/) (2025)
- [Scaling Probabilistic Circuits via Data Partitioning](https://mlsanity.com/paper/2503.08141/) (2025)

## Built on by (most cited first, 1 of 1)

- [Tractable Hierarchical Control of Autoregressive Language Models](https://mlsanity.com/paper/2607.20483/) (2026)

## Abstract (arXiv)

Understanding and explaining the structure of generated test inputs is essential for effective software testing and debugging. Existing approaches--including grammar-based fuzzers, probabilistic Context-Free Grammars (pCFGs), and Large Language Models (LLMs)--suffer from critical limitations. They frequently produce ill-formed inputs that fail to reflect realistic data distributions, struggle to capture context-sensitive probabilistic dependencies, and lack explainability. We introduce ExplainFuzz, a test generation framework that leverages Probabilistic Circuits (PCs) to learn and query structured distributions over grammar-based test inputs interpretably and controllably. Starting from a Context-Free Grammar (CFG), ExplainFuzz compiles a grammar-aware PC and trains it on existing inputs. New inputs are then generated via sampling. ExplainFuzz utilizes the conditioning capability of PCs to incorporate test-specific constraints (e.g., a query must have GROUP BY), enabling constrained probabilistic sampling to generate inputs satisfying grammar and user-provided constraints. Our results show that ExplainFuzz improves the coherence and realism of generated inputs, achieving significant perplexity reduction compared to pCFGs, grammar-unaware PCs, and LLMs. By leveraging its native conditioning capability, ExplainFuzz significantly enhances the diversity of inputs that satisfy a user-provided constraint. Compared to grammar-aware mutational fuzzing, ExplainFuzz increases bug-triggering rates from 35% to 63% in SQL and from 10% to 100% in XML. These results demonstrate the power of a learned input distribution over mutational fuzzing, which is often limited to exploring the local neighborhood of seed inputs. These capabilities highlight the potential of PCs to serve as a foundation for grammar-aware, controllable test generation that captures context-sensitive, probabilistic dependencies.