- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Probabilistic neurosymbolic languages parameterize the distributions in probabilistic programming languages with neural networks. However, the probabilistic inference problem is #P-hard, limiting the scalability of these methods. The authors propose SLASH, which targets a subset of programs that are tractable, such that inference remains linear-time. They do this by relying on the decomposability and determinism properties. When not present, they use cutset sampling to approximate, and provide an error bound. They implement their language using GNN message-passing, providing GPU acceleration for inference and learning.
Critical strengths
I like the combination of exact/approximate, by e.g. solving most of the program exactly and only using sampling for an intractable core of the problem. Neurosymbolic languages are too often entirely exact, or fully approximate (e.g. by sampling everything).
Critical weaknesses
Several parts of the paper seem to have limited novelty. For example, Theorem 1 is already what PRISM was built on decades ago. (The authors also do cite this themselves.) So the linear-time exactness contributions seems overstated to me.
The GPU-based implementation also does not seem particularly novel to me, as the authors cite KLay to already do this. The paper states that “KLay accelerates a circuit ∂SLASH never builds.”, but this again overstates the difference. Both methods build circuits and accelerate them (∂SLASH uses different notation with graphs, but these are also circuits). The difference is the language built on top does not perform knowledge compilation (but that’s a difference on the language level, not on the GPU-based acceleration).
This only leaves the sampling-based approximation on non-deterministic nodes. However, this part of the contribution is poorly explained, in my opinion. There are a bunch of vague statements like “the sampling error is certified on demand, and the relaxation bias is the single remaining uncontrolled term”, but it doesn’t actually state what relaxation is used. I have to dig into the appendix to see it’s Gumbel-softmax (which is very well-known, so could’ve easily been mentioned). The rest of the paper never mentions that the approximation is biased (and not bounded).
On the language side, it was also not clear to me why a “new” language was introduced as SLASH. It seemed to me like only the inference side is different, but the language is basically the same as SLASH (with perhaps some small restrictions). I would have like the paper to give more intuition on what subset of programs the inference i linear-time (from what I know, I think this has already for negation-free programs by Winters et al. (2022), which show the correspondence between deterministic+decomposable programs and context-free grammars).
On the experimental side, I also found some results to be overly straightforward. For example, RQ4 (does the encoding matter), is of course true and well-known. (For example, Jiao et al. (2026) apply the same trick, to scale the exact same experiment to N=500.) RQ1 (does our exact method match the accuracy of other exact methods) also seems obviously true.
As a final note, I think the writing in many places is subpar, and the authors could’ve spent more effort cleaning up obvious AI artifacts to improve the presentation.
References
Winters, Thomas, et al. "Deepstochlog: Neural stochastic logic programming." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 9. 2022.
Jiao, Ying, et al. "DeepProofLog: Efficient Proving in Deep Stochastic Logic Programs." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 40. No. 27. 2026.
Questions for authors
- The treatement of negation is not fully clear to me. For example, on line 192, it states that the graph is just a probabilistic circuit, however these are NNF. But the paper also says there is stratified negation, so there should be negation present on internal edges? (On a sidenote, i also think it should be an arithmetic circuit and not a probabilistic circuit, as there are no normalized weights on the -nodes.)
- Why are the exact semantics under sampling? The relaxation uses a softened max operation, so is inference closer to MAP than marginalization?
3 comments
part 2
Q1. Negation, NNF, probabilistic vs. arithmetic circuits
Correct on the syntax: a negative literal contributes at an internal edge, so the graph is not in NNF, and NNF is only sufficient for the property we test per node instead. Our -nodes carry no weights at all. Still the reasoning graph is a probabilistic circuit rather than an arithmetic circuit, since the circuit builds a distribution over total choices via the normalized NPP leaves. All two are now stated in Sec. 2.3, Under these conditions the reasoning graph is a probabilistic circuit, with the per-node test in App. B.7.
Q2. Is this MAP rather than marginalization?
Marginalization: the pass averages the query over sampled worlds, estimating and not , and a query satisfied by disjoint worlds of probability returns here against under MAP. Inside a drawn world the values are 0/1, where is exactly, so the only error is that draws are not perfectly hard at . We think our terminology invited the question and have renamed the condition exclusiveness after PRISM; see Def. Exclusiveness in Sec. 2.3 and App. B.12 for the identity the average estimates.
Dear Reviewer,
We would like to thank you again for the insightful review. We have provided a detailed answer in the rebuttal as well as the modified paper. We hope to have resolved all your concerns and will be happy to discuss further if any concerns do remain.
Regards,
Authors
Reply to Reviewer ziMT
We thank the reviewer for a close and specific reading. The hybrid they name as a critical strength is what we take the contribution to be, and several criticisms below are fair consequences of our having framed it less directly than that.
What ∂SLASH claims. Exact DPPLs obtain weighted model counting by enumerating stable models or by knowledge compilation, so a CPU solver sits in the training loop and every gradient step stalls while it runs. ∂SLASH removes it: the program is grounded once, and from there on the reasoning graph which encodes all stable models is the weighted model count. While others pipelines compile a program using Knowledge compilation we syntactically compile the graph and then test where exactness fails and recover it via sampling.
Thm. 1 licenses that substitution, and this is why PRISM's condition matters to us: PRISM used exclusiveness to sum explanations it had already enumerated, and we use it to justify never enumerating them.
W1. Theorem 1 is PRISM's condition
Agreed, and the paper says so and cites PRISM in the same paragraph. The contribution is not the condition but what it gives us: PRISM makes exclusiveness the programmer's obligation and uses it to sum explanations it has already enumerated, whereas we decide it structurally, per node, and use it to avoid enumeration altogether. Sec. 2.3, What this buys over the distribution semantics.
W2. KLay
A fair correction, and the sentence is removed: our reasoning graph is a circuit. What we meant differs in one word, that KLay accelerates a circuit ∂SLASH never compiles — compilation being the step KLay itself amortizes and we never perform, since the graph is read off the ground program in time linear in its size. Sec. 4 now states the difference it rests on: compilation searches for decomposability and exclusiveness, we test for them per node and sample where the test fails. Further, Klay compiles for each query a separate SDD, layerizes them, and finally merges them into a single shared circuit. We ground multiple queries simultaneously and then create a single joint RG for all of them directly from the groundings.
Positioning. Sec. 2.1 says that ∂SLASH inherits SLASH's language constructs and that the fragment is a restriction, not a new language. Sec. 4 corrects the KLay sentence to the claim we meant, that KLay accelerates a circuit ∂SLASH never compiles, and states the difference it rests on: compilation searches for decomposability and exclusiveness, we test for them per node and sample where the test fails. RQ1 is relabelled a control in Sec. 3, RQ4's claim is narrowed to the VRAM budget, and DeepStochLog and DeepProofLog are cited and positioned.
W3. The relaxation, and the bias
We agree that this should have been part of the main text and move it there accordingly. A Gumbel-softmax draw taken once per NPP instance (Eq. 7), and the bias is measured rather than uncontrolled. The bias is observable and is linear in the temperature, ηbias=cτ with c∈[0.26,0.38], so at the published τ=0.1 it is at most ≈0.038 per node, and on most programs it sits under the sampling margin we already certify. We added App. C where we emperically dive into different choices of the sampling parameters.
W4. "A new language", and Winters et al. (2022)
The reading is correct, and Sec. 2.1 now says that ∂SLASH inherits SLASH's language constructs and that the fragment is a restriction; a program outside it is partially sampled, not rejected. DeepStochLog is cited in Sec. 4, and the kinship is real, but it distributes over derivations, where summation is correct by construction, and its authors say it avoids the disjoint-sum problem "by resorting to an alternative probabilistic semantics". We keep possible-worlds semantics, where that problem is the one Thm. 1 characterises, and DeepStochLog states no decomposability, exclusiveness or linear-time result.
W5. RQ1 and RQ4
RQ1: agreed, and it is relabelled a control in Sec. 3, since a method computing the same quantity as exact WMC cannot be more accurate than the solvers it replaces. The claim is on the other axis, and Fig. 2 is where it is made: ∂SLASH at the time scale of the approximate methods while remaining exact.
RQ4: We agree that this is well now and dates back to basic algorithms like Variable Elimination. The aim of this experiment was to show though, that we now see this old problem in the new dimension of VRAM which affects the scalability of GPU based methods.
On Jiao et al. (2026) the two MNIST-Addition tasks differ: their App. C.1 takes 2N images as two N-digit numbers, with Table 1's reference accuracy 0.99072N, while we sum N single-digit images. Positional addition is a carry chain of constant width where our partial sums range over [0,9N], so we draw no comparison between N=500 there and N=100 here, in either direction.