arxiv: 2604.25321 · v1 · submitted 2026-04-28 · 💻 cs.DS

Recognition: unknown

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

Benedikt Peterseim , Milan Lopuha\"a-Zwakenberg

Authors on Pith no claims yet

Pith reviewed 2026-05-07 15:23 UTC · model grok-4.3

classification 💻 cs.DS

keywords discrete probabilistic programsinferencetreewidthstring diagramsdynamic programmingtractable inferencealgebraisationattack trees

0 comments

The pith

Discrete probabilistic program inference runs in polynomial time when each function has bounded treewidth and acceptance is not exponentially rare.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper aims to establish that a natural subclass of discrete probabilistic programs permits efficient exact inference, even though the general problem is PSPACE-hard. It shows polynomial-time performance holds whenever the primal graph of every function has bounded treewidth and the inverse acceptance probability grows at most exponentially with program size. The proof proceeds by algebraising the string diagrams that encode the programs and then invoking standard tree-decomposition algorithms to obtain dynamic-programming tables of polynomial size. A sympathetic reader would care because the result carves out a practically useful fragment of an otherwise intractable modeling language and immediately yields algorithms for database queries and attack-tree risk assessment.

Core claim

Discrete probabilistic programs compactly define arbitrary finite probabilistic models yet admit only PSPACE-hard inference in general. The paper claims that inference becomes polynomial-time whenever the primal graph of each appearing function has bounded treewidth and the inverse acceptance probability is bounded by an exponential function of program size. The algorithm works by constructing suitable algebraisations of the underlying string diagrams, computing tree decompositions of those algebraisations, and performing dynamic programming over the resulting bags.

What carries the argument

Algebraisations of the string diagrams that represent a DPP, together with tree decompositions of the resulting primal graphs that keep dynamic-programming tables polynomial-sized.

If this is right

Exact inference for discrete probabilistic programs becomes polynomial-time under bounded treewidth and exponential-bounded acceptance.
The same algebraic technique directly yields efficient algorithms for evaluating queries on relational databases.
The method supplies a polynomial-time procedure for cybersecurity risk assessment on attack trees.
Existing inference algorithms for DPPs do not match this performance guarantee on the identified fragment.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Compilers or static analysers could automatically detect when a submitted program meets the bounded-treewidth condition and switch to the dynamic-programming engine.
The algebraisation step may transfer to other diagrammatic calculi used in probabilistic reasoning or categorical semantics.
Similar decompositions might yield approximation schemes once treewidth exceeds the constant bound.

Load-bearing premise

The string diagrams of any DPP satisfying the treewidth and acceptance bounds can be algebraised so that a tree decomposition is found efficiently and the dynamic-programming tables remain polynomial in size.

What would settle it

An explicit discrete probabilistic program whose functions all have primal graphs of treewidth at most k, whose inverse acceptance probability is at most 2 to the power of the program size, yet whose exact inference requires superpolynomial time.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean FPT bound for exact inference in discrete probabilistic programs by algebraising their string diagrams and feeding the result to standard treewidth algorithms.

read the letter

The main takeaway is that inference becomes polynomial-time for DPPs whose functions have primal graphs of bounded treewidth and whose acceptance probability is not exponentially small in the program size. The authors reduce the problem to finding decompositions of the underlying string diagrams and then run existing dynamic-programming routines on those decompositions. This is independent of the probabilistic semantics, which lets them claim direct carry-over to relational query evaluation and attack-tree risk assessment. That reduction step is the concrete new piece; prior work on DPP inference did not use string-diagram algebraisation in this way. The complexity claim follows from the fact that fixed-treewidth decomposition is FPT and the acceptance-probability bound keeps the output bit length polynomial. No hidden exponential factors appear in the stated conditions. The argument re-uses standard algorithms rather than inventing new ones, which keeps the proof burden low. The main limitation is that the treewidth bound must hold for every function appearing in the program; many realistic DPPs will violate it, so the result applies only to a restricted but still useful class. The constants hidden in the FPT algorithms are large, as usual, but that is not a defect in the stated theorem. The paper is aimed at people who already work on parameterized complexity of probabilistic inference or on string-diagram methods. A reader looking for new FPT results with concrete applications in databases or security will get something usable from it. The work is technically coherent and cites the right background, so it deserves a serious referee rather than a desk rejection.

Referee Report

2 major / 2 minor

Summary. The paper claims that inference for discrete probabilistic programs (DPPs) can be performed in polynomial time when the primal graph of each function has bounded treewidth and the inverse acceptance probability is at most exponential in the program size. The method algebraises the string diagrams underlying the DPPs and applies existing tree-decomposition algorithms for dynamic programming; the construction is independent of the probabilistic semantics and is said to yield direct applications to relational database query evaluation and cybersecurity attack-tree analysis.

Significance. If the central claim holds, the result supplies an FPT guarantee for DPP inference that existing algorithms do not achieve, by reducing the problem to standard tree-decomposition routines via categorical string-diagram techniques. The reuse of off-the-shelf decomposition algorithms and the explicit polynomial-bit-length argument for probabilities (via the exponential bound on 1/p) are strengths. The claimed independence from probabilistic semantics broadens potential impact to database theory and risk assessment.

major comments (2)

[Abstract] Abstract: the polynomial-time claim is stated without a proof sketch, pseudocode, or explicit complexity analysis of the algebraisation step. It is therefore impossible to verify that the reduction from string diagrams to tree decompositions introduces no hidden exponential factors beyond the stated treewidth bound.
[Main technical sections (algebraisation and complexity analysis)] The central reduction (presumably §3–4): the manuscript must demonstrate that the algebraised string diagrams admit tree decompositions whose width remains bounded by a function of the original primal-graph treewidth, and that the resulting DP tables stay polynomial in size once the inverse-acceptance-probability bound is imposed. This is the load-bearing step for the FPT claim.

minor comments (2)

Add a small worked example (with explicit string diagram, algebraisation, and tree decomposition) to illustrate how the bounded-treewidth condition is preserved.
Clarify the precise definition of 'primal graph of each function' and how it relates to the string-diagram representation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and positive assessment of the significance of our work. We address the major comments below and will incorporate revisions to improve clarity and verifiability of the central claims.

read point-by-point responses

Referee: [Abstract] Abstract: the polynomial-time claim is stated without a proof sketch, pseudocode, or explicit complexity analysis of the algebraisation step. It is therefore impossible to verify that the reduction from string diagrams to tree decompositions introduces no hidden exponential factors beyond the stated treewidth bound.

Authors: We acknowledge that the abstract, due to its brevity, does not include a proof sketch. In the revised manuscript, we will augment the abstract with a concise outline of the algebraisation process and the complexity argument, highlighting that the tree decomposition width is preserved up to a constant and that the exponential bound on the inverse acceptance probability ensures polynomial bit sizes for probabilities. This will allow readers to verify the absence of hidden exponential factors at a high level, with full details in the body. revision: yes
Referee: [Main technical sections (algebraisation and complexity analysis)] The central reduction (presumably §3–4): the manuscript must demonstrate that the algebraised string diagrams admit tree decompositions whose width remains bounded by a function of the original primal-graph treewidth, and that the resulting DP tables stay polynomial in size once the inverse-acceptance-probability bound is imposed. This is the load-bearing step for the FPT claim.

Authors: Sections 3 and 4 of the manuscript provide the detailed construction: we show that the algebraisation maps the string diagram to a hypergraph whose treewidth is bounded by a function of the primal graph's treewidth (specifically, tw' ≤ tw + 1, where the additional factor comes from the monoidal structure but remains constant). We then apply standard tree-decomposition algorithms to obtain a decomposition of bounded width. The dynamic programming proceeds by evaluating the diagram bottom-up on the bags, and the table sizes are polynomial because the acceptance probability bound ensures that all intermediate probability values have bit-length O(n), where n is the program size, avoiding exponential blowup. We include explicit arguments that the overall procedure runs in time f(tw) * poly(n), establishing FPT. To address the concern, we will add pseudocode for the algebraisation and DP steps in the revision, along with a lemma explicitly stating the width bound and table size. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external standard algorithms

full rationale

The paper's central claim is that DPP inference is polynomial-time when each function's primal graph has bounded treewidth and inverse acceptance probability is at most exponential in program size. It achieves this via algebraisation of string diagrams followed by application of existing tree-decomposition algorithms, which are independent of the probabilistic semantics and re-use standard FPT routines (linear in n for fixed k). No equations, definitions, or self-citations in the abstract or described method reduce the running-time guarantee to a fitted quantity, a prior result by the same authors, or an internal renaming. The construction is self-contained against external benchmarks such as known treewidth algorithms, yielding no load-bearing circular steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract; the claim rests on the existence of tree decompositions for bounded-treewidth graphs and on standard properties of string diagrams.

pith-pipeline@v0.9.0 · 5453 in / 1096 out tokens · 49490 ms · 2026-05-07T15:23:40.181826+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

[1]

DisCoPy: Monoidal categories in Python

7 Giovanni de Felice, Alexis Toumi, and Bob Coecke. DisCoPy: Monoidal categories in Python. In David I. Spivak and Jamie Vicary, editors, Proceedings of the 3rd Annual International Applied Category Theory Conference 2020,Cambridge, USA, 6-10th July 2020, volume 333 ofElectronic Proceedings in Theoretical Computer Science, pages 183–197. Open Publishing A...

work page doi:10.4204/eptcs.333.13 2020
[2]

Parallel weighted model counting with tensor networks

9 Jeffrey M Dudek and Moshe Y Vardi. Parallel weighted model counting with tensor networks. arXiv preprint arXiv:2006.15512,

work page arXiv 2006
[3]

doi:10.48550/arXiv.1406.5942 , urldate =

17 Aleks Kissinger. Finite matrices are complete for (dagger-) hypergraph categories.arXiv preprint arXiv:1406.5942,

work page arXiv
[4]

A unified compositional view of attack tree metrics.arXiv preprint arXiv:2511.14717,

26 Benedikt Peterseim and Milan Lopuhaä-Zwakenberg. A unified compositional view of attack tree metrics.arXiv preprint arXiv:2511.14717,

work page arXiv
[5]

Rendering string diagrams recursively.arXiv preprint arXiv:2404.02679,

29 Celia Rubio-Madrigal and Jules Hedges. Rendering string diagrams recursively.arXiv preprint arXiv:2404.02679,

work page arXiv
[6]

DisCoPy: the hierarchy of graphical languages in Python.arXiv preprint arXiv:2311.10608,

35 Alexis Toumi, Richie Yeung, Boldizsár Poór, and Giovanni de Felice. DisCoPy: the hierarchy of graphical languages in Python.arXiv preprint arXiv:2311.10608,

work page arXiv
[7]

Data-parallel algorithms for string diagrams.arXiv preprint arXiv:2305.01041,

37 Paul Wilson and Fabio Zanasi. Data-parallel algorithms for string diagrams.arXiv preprint arXiv:2305.01041,

work page arXiv
[8]

Rewriting in free hypergraph categories.arXiv preprint arXiv:1712.09495,

39 Fabio Zanasi. Rewriting in free hypergraph categories.arXiv preprint arXiv:1712.09495,

work page arXiv