Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation

Benedikt Peterseim, Milan Lopuhaä-Zwakenberg · 2026

Read Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation by Benedikt Peterseim, Milan Lopuhaä-Zwakenberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25321.txt.

Introduction

Peterseim and Lopuhaä-Zwakenberg show discrete probabilistic program inference runs in polynomial time only for plain programs. It runs in polynomial time when each function's primal graph has bounded treewidth and the inverse acceptance chance is at most exponential in program size. Past schemes lack this pledge. Their way finds apt algebra forms of the string diagrams behind such programs, using past tree decomposition schemes. This holds for other settings too, with uses in database queries and security risk checks via attack trees.

Catalog record

CREATORBenedikt Peterseim, Milan Lopuhaä-Zwakenberg
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126479
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25321

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fixed-parameter tractable inference for discrete probabilistic programs, via string diagram algebraisation Benedikt Peterseim, Milan Lopuhaä-Zwakenberg Abstract Discrete probabilistic programs (DPPs) provide a highly expressive formalism for compactly defining arbitrary finite probabilistic models. This expressivity comes at a price: DPP inference is PSPACE-hard. In this work, we show that DPP inference only takes polynomial time for programs that are ‘structurally simple’. More precisely, inference can be performed in polynomial time when the primal graph of each function appearing in the probabilistic program has bounded treewidth, and the inverse acceptance probability is at most exponential in the size of the probabilistic program. Existing algorithms do not achieve this performance guarantee. Our method relies on finding suitable decompositions, algebraisations , of the string diagrams underlying DPPs, employing existing algorithms for tree decompositions. This is independent of the probabilistic setting of DPPs and has direct applications to many problems, such as evaluating queries on relational databases and cybersecurity risk assessment via attack trees. \lstset backgroundcolor= \lstdefinestyle sql language=SQL, basicstyle= , keywordstyle= , commentstyle= , showstringspaces=false, morekeywords=JOIN, ON, \crefalias exampleexample \crefname exampleexampleexamples \Crefname exampleExampleExamples Universiteit Twente, Enschede, the [email protected] Universiteit Twente, Enschede, the [email protected] ccs Mathematics of computing Probabilistic inference problems ccs Theory of computation Fixed parameter tractability ccs Theory of computation Categorical semantics keywords probabilistic programming, string diagrams, treewidth, fixed-parameter tractability, probabilistic inference, parameterised complexity, hypergraph categories † † runningtitle: FPT inference for discrete probabilistic programs † † runningauthor: B. Peterseim and M. Lopuhaä-Zwakenberg † † copyright: Benedikt Peterseim and Milan Lopuhaä-Zwakenberg † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction 1.1 Discrete probabilistic programs (DPPs) Probabilistic programming languages are declarative formal languages for specifying probabilistic models. We focus on discrete probabilistic programs (DPPs) as introduced in [ 14 ] , with Boolean variables. Thus we allow exactly the following constructs: 1. {\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;\!\! expressions, or assignments ; 2. the basic Boolean connectives \land,\lor,\lnot ; 3. a biased coin flip function {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(p) , for each p\in[0,1]\cap\mathbb{Q} ; 4. {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{observe}} expressions, conditioning on an event being true; 5. function definitions. Extensions to more general finite types and constructs (such as bounded iteration) can be reduced to this Boolean core [ 14 ] . An example of a DPP is given in Figure 1 . DPPs are highly expressive and include, for example, fault trees , which are ubiquitous in reliability engineering [ 30 , 32 ] , as well as Bayesian networks [ 24 , 25 ] which are used for probabilistic reasoning in many fields including healthcare [ 23 ] and cybersecurity [ 38 ] . Further applications of discrete probabilistic programming, and its role for probabilistic programming in general, are described in detail in [ 14 ] . \begin{aligned} &\hskip 9.24994pt{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{test}}(z):=\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{\top|\top}={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.99);\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{\top|\bot}={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.02);\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{TP}}}=z\land t_{\top|\top};\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{FP}}}=\lnot z\land t_{\top|\bot};\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t=t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{TP}}}\lor t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{FP}}};\\ &\hskip 9.24994pt\hskip 9.24994ptt\\ \\ &\hskip 9.24994pt{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{hasDisease}}(\,):=\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;x={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(10^{-4});\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{1}={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{test}}(x);\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;t_{2}={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{test}}(x);\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;y=t_{1}\land\lnot t_{2};\\ &\hskip 9.24994pt\hskip 9.24994pt{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{observe}}(y);\\ &\hskip 9.24994pt\hskip 9.24994ptx\end{aligned} 0.99 0.02 t_{\top|\bot} z t_{\top|\top} t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{TP}}} t_{{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{FP}}} t 10^{-4} x t_{1} t_{2} y {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{test}} Figure 1: The event that a patient has an infectious disease given one positive and one negative test result, as a discrete probabilistic program {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{hasDisease}} (left) and a hierarchical string diagram (right). The disease occurs in 10^{-4} of the population; the test has a 99% true positive rate (TP) and a 2% false positive rate (FP). 1.2 The Boolean probabilistic inference problem The main subject of this paper is probabilistic inference: given a DPP with no inputs and a single output, what is the probability that this DPP returns true ? We cannot hope to efficiently compute this exactly: there exist programs of length O(n) whose probability of returning true is 2^{-2^{n}} , which requires exponentially many digits to express; see \Cref fig:counterexample. Instead, we look at the approximate problem: Problem 1 . Given a discrete probabilistic program {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}} with no inputs and a single Boolean output, and a natural number d , compute the probability that {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}} returns true , up to d fractional binary digits. \Cref problem:boolean-probabilistic-inference is PSPACE-hard [ 14 ] , even when restricting to deterministic DPPs, showing that this specific hardness result has little to do with probability and instead stems from the expressive power of function definitions. However, without function definitions, probabilistic inference remains NP-hard even when restricted to fault trees [ 21 ] and Bayesian networks. For Bayesian networks, however, inference is known to be fixed-parameter tractable [ 19 ] , i.e. there are inference algorithms with polynomial time complexity given that a certain parameter is bounded. The relevant parameter is the treewidth of the so-called moral graph of the Bayesian network, which measures how far away the network is from being ‘tree-like’. Similar results are known for fault trees [ 21 ] and the related problem of weighted model counting [ 5 , 6 , 9 ] . However, such results do not exist for DPPs in general. {subfigure} [b]0.38 \begin{aligned} &\quad{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{0}(\,):=\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;x={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.5);\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;y={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.5);\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;z=x\land y;\\ &\quad\qquad z\\ \\ &\quad\cdots\\ \\ &\quad{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n+1}(\,):=\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;x={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n}(\,);\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;y={\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n}(\,);\\ &\quad\qquad{\color[rgb]{0.2969,0.5,0.5625}\mathsf{let}}\;z=x\land y;\\ &\quad\qquad z\\ \end{aligned} 0.5 0.5 y x y x z z z {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n} {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n-1} {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{0} (a) \phantomcaption {subfigure} [b]0.59 0.2 0.1 0.3 \circ \otimes 0.2 0.1 0.3 \otimes \otimes \circ \circ = (b) \phantomcaption Figure 2: (a) Family ({\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n}) of DPPs. The probability that {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n} returns true is doubly exponentially small in n . The weighted-model-counting-based inference algorithm of Dice requires 2^{n} fresh variables to compile {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{f}}_{n} to a weighted Boolean formula [ 14 , Section 4.3] , causing exponential blowup before any weighted model count is performed. (b) Decomposition of a dot diagram via parallel ( \otimes ) and sequential ( \circ ) composition, equivalently the term \lor\circ(\land\otimes\land)\circ({\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.1)\otimes{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{copy}}\otimes{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.3))\circ{\color[rgb]{0.1953,0.2344,0.3398}\mathtt{flip}}(0.2) . The operations \circ and \otimes correspond to matrix multiplication and Kronecker product; see \Cref sec:semantics. 1.3 Contributions Our main contribution is a fixed-parameter tractable algorithm for inference in DPPs. The key parameter is the maximal treewidth k of the so-called primal graph of the functions in the DPP. Main result 2 (Theorem 55 paraphrased) . There exists an algorithm that computes the probability that a DPP returns true up to d digits in O(2^{O(k)}d^{2}n^{3}\log^{3}(p_{\mathrm{acc}}^{-1})) time, where n measures the overall size of the DPP, 1 1 1 More precisely, n=LMN , where L is the maximum number of distinct functions called within any function, M is the number of functions in the DPP, and N is the maximum number of assignments in any function. In particular, if l is the number of lines in the DPP, then n is in O(l^{3}) , and hence, our algorithm takes polynomial time in the number of lines of the given DPP, for fixed k , d and p_{\mathrm{acc}} . and p_{\mathrm{acc}} is the acceptance probability , the probability that all {\color[rgb]{0.1953,0.2344,0.3398}\mathtt{observe}} d values are true. 2 2 2 The dependency on p_{\mathrm{acc}} can be removed, for example, if the depth of the call graph of the

Read the complete text