REVIEW 4 major objections 4 minor 50 references
Relational Neurosymbolic Markov Models
T0 review · 4 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read A new class of Markov models provably satisfies relational logical constraints in sequential tasks.
desk verdict Genuinely new model class with a clever RBPF, but the advertised 'exact' inference rests on an unproven and likely false cluster factorization; the paper needs major revision before its guarantees are credible. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the factorised transition in Eq. (3), written as $p_\varphi(S_0\mid N_0)p(N_0)p(Z_0\mid S_0)\prod_t p_\varphi(S_{t+1}\mid S_t,N_{t+1})p(N_{t+1})p(Z_{t+1}\mid S_{t+1})$, with $N_t$ the neural/subsymbolic part, $S_t$ the relational symbolic part, and $Z_t$ observations. Inference rests on a Rao-Blackwellised particle filter: rather than resampling, the filter computes the conditional $p_\varphi(X_{t+1}\mid x_t,Z_{t+1})$ exactly when the state is finite, and splits that conditional into independent clusters by Eq. (8), a factorisation into a product over clusters that are claimed to be conditionally independent given the observation. Exact finite probabilities make unbiased discrete gradient estimators such as RLOO applicable, while infinite-domain variables are handled by differentiable particle filtering.
What would settle it
Take the discriminative task's two-enemy setting and compute the exact joint posterior over the two enemies' locations after observing a hit. If conditioning on the hit couples the enemies, then the cluster product in Eq. (8) will not hold exactly and the filter's 'exact' local inference is approximate; the paper does not report such a check.
Extended reading notes
Core claim
The paper's central claim is that the Markovian factorisation over neurosymbolic states $X_t=(N_t,S_t)$, with transition $p_\varphi(S_{t+1}\mid S_t,N_{t+1})$ governed by relational logic and neural predicates, is the first deep sequential probabilistic model that integrates relational logical constraints and provably satisfies them. Under this factorisation, relations constrain both the inside of one time slice and the movement from one slice to the next, so a property such as "the agent is safe" can be guaranteed throughout the whole trajectory. The paper further claims that its Rao-Blackwellised particle filter, combined with cluster factorisation and state-of-the-art gradient estimation, scales inference and learning to time horizons well beyond those reachable by existing exact and approximate neurosymbolic systems, while still training neural components end to end.
Load-bearing premise
The whole inference scheme assumes that, once the observations are fixed, the symbolic state splits into conditionally independent clusters, so each cluster can be solved separately with no error.
Editorial extensions
If this is right
- Logical constraints such as safety properties can be guaranteed at every time step of a generated or classified sequence, not just in a single static inference.
- NeSy-MMs handle both generative tasks, such as producing image sequences that follow rules and actions, and discriminative tasks, such as classifying trajectories with partially unknown neural transitions.
- New constraints can be imposed at test time without retraining, so a model can refuse to enter a forbidden region mid-trajectory while still following the rest of the instructions.
- The relational symbolic state gives better out-of-distribution generalisation than transformer and deep-HMM baselines in the paper's discriminative experiments, and scales to sequence lengths where exact neurosymbolic baselines time out.
Reading between the lines
- Editorial: if the cluster-factorisation independence in Eq. (8) is not exact for a given observation model, then what the paper calls exact local inference is an approximation; an explicit check on the discriminative game task would settle this for that benchmark.
- Editorial: the same construction could be applied to neural language generation, where a relational symbolic state tracking predicates over generated tokens would let a decoder guarantee global logical constraints, provided the cluster independence holds for the constraints used.
- Editorial: one testable extension is to replace exact cluster inference with approximate inference for the continuous parts, trading the exactness guarantee for applicability to relational dynamics with many continuous variables.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces relational neurosymbolic Markov models (NeSy-MMs), a class of sequential probabilistic models that combine Markov dynamics with relational logical constraints and neural parameterizations. The model is defined by the factorization in Eq. (3), and inference is performed with a Rao-Blackwellised particle filter that conditions on observations through exact local NeSy inference, aided by a cluster factorization of the state space. The authors also propose a gradient-estimation scheme based on RLOO and report experiments on generative image-sequence modeling and discriminative trajectory classification, claiming strong guarantees, scalability beyond existing NeSy systems, and improved out-of-distribution generalization.
Significance. If the technical claims are correct, this is a valuable step toward sequential neurosymbolic models: it addresses a real scalability bottleneck, supports both discriminative and generative tasks, and demonstrates that relational constraints can be injected into deep Markov models. The paper also contributes two new benchmarks, reports hyperparameters and seeds, and states that code is provided, which are strengths for reproducibility. However, the central guarantees of exactness and unbiased learning currently rest on an unstated conditional-independence assumption and on a recursive factorization that is not generally valid, so the significance is contingent on fixing or carefully qualifying these points.
major comments (4)
- [§4.2, Eqs. (8)-(9)] The factorization p(X | Z) = ∏_i p(X_i | Z) is presented as an equality without stating the required conditional-independence assumption. In general, conditioning on a shared observation couples the variables. In the discriminative experiment (§5.2, Appendix D.2), the observation hit(T) is a logical disjunction over all enemies, so conditioning on hit=true induces dependence among enemy locations via explaining away. Concretely, with two enemies each independently at adjacent cell A or non-adjacent cell B, prior uniform, and hit = (E1=A or E2=A), the exact posterior satisfies P(E1=A, E2=A | hit) = 1/3, while the product of marginals is 4/9. Thus Eq. (9) is not a theorem in this setting. Either the factorization is an approximation, which would contradict the 'exact' wording in §4.1 and the gradient derivation in Appendix C, or the method applies only when observations decompose per cluster, which would exclude the main discriminative experiment. The authors need to state the assumption, prove it for their settings, or explicitly label the factorization as approximate and adjust the guarantee claims accordingly.
- [§4.2, Eq. (10)] The notion of 'maximal number of clusters' B is undefined, and no procedure is given for computing the clusters or for verifying that the factors in Eq. (10) are well-defined conditional distributions. Even if one takes the clusters to be connected components of some factor graph of p(X | Z), variables within a cluster need not become independent after conditioning on Z, so the refined factorization p(F_i, I_i | x_t, Z) = p(F_i | I_i, x_t, Z) p(I_i | x_t, Z) is always true, but the cross-cluster product in Eq. (9) is the nontrivial step. The paper should specify the cluster-identification algorithm and prove the factorization under explicit conditions, or state that the cluster product is an approximation.
- [Appendix C, Eqs. (16)-(17)] The recursive factorization of p(x_{0:T} | Z_{0:T}) in Eq. (16) is not generally correct. The equation writes p(x_{0:T} | Z_{0:T}) = p(x_T | x_{T-1}, Z_{t+1}) p(x_{0:T-1} | Z_{0:T-1}), but the second factor is the filtering distribution at time T-1, not the conditional distribution of the past given the full observation sequence including Z_T. The past states are generally dependent on future observations. For example, with T=1, deterministic transition x_1 = x_0, and observation z_1 = x_1, p(x_0 | z_0, z_1) differs from p(x_0 | z_0), so the product on the right-hand side is not the joint posterior. Consequently, Eq. (17), which computes log p(x_{0:T} | Z_{0:T}) as a sum of per-step proposal conditionals p(x_t | x_{t-1}, Z_t), substitutes the proposal log-density for the target log-density. The RLOO estimator in Eq. (15) then is not unbiased for the objective in Eq. (11). The authors need to derive the gradient estimator with proper importance weighting or explicitly present the method as an approximate, biased estimator.
- [Appendix D.2 and §5.1] The logic program for the generative task does not encode wall constraints. Section 5.1 states that the agent moves in a grid 'surrounded by walls', and the claims in §5.3 say that NeSy-MMs 'perfectly adhere to the mechanics of the game' and 'provably satisfy' constraints. However, the rules in Appendix D.2 move the agent by one cell for each action with no check that the target cell is inside the grid or is not a wall. As printed, the program permits moves that walk through or outside the walls. The authors should either provide the actual program including wall checks, or qualify the guarantee claim to the movement rules as written rather than the full environment mechanics.
minor comments (4)
- [§4.2, Eq. (10)] Equation (10) is missing a comma in the conditioning set: it should read p(F_i | I_i, x_t, Z_{t+1}), not p(F_i | I_i x_t, Z_{t+1}).
- [Appendix C, Eq. (16)] The first factor in Eq. (16) uses the time index Z_{t+1} although the current time is T; this should be Z_T, which would at least make the notation internally consistent.
- [§4.1] The text says the RBPF assumes p(X_{t+1} | X_t, Z_{t+1}) 'can be computed exactly' and later describes the results as 'exact local inference'. Given the cluster-factorization issue in §4.2, these statements should be qualified to avoid overclaiming.
- [§5.2 and Table 1] The class-balance percentages in Table 1 are useful, but the paper does not state how the agent death label is determined in the generated data; adding one sentence on the death condition would improve reproducibility.
Circularity Check
No significant circularity: the constraints are built into the model by design, and the inference novelty rests on component algorithms with independent published status; the main weakness is an unproved factorisation, not a circular reduction.
full rationale
The derivation chain is not circular. Eq. (3) defines NeSy-MMs as a Markov factorisation over neurosymbolic states, and the 'provably satisfy' claim is a direct property of encoding logical constraints such as `observe(safe0:T, true)` into the model: constraints are inputs, not outputs fitted to the experiments, so satisfying them is a design guarantee rather than a prediction extracted from data. The inference method combines a standard Rao-Blackwellised particle filter (Murphy and Russell 2001), exact NeSy inference from published systems (Kisa et al. 2014; De Smet et al. 2023), and the RLOO/CatLog gradient estimators (Kool et al. 2019; De Smet, Sansone, and Zuidberg Dos Martires 2023); although some of these references are self-citations, they are component methods with independent published derivations and are not invoked to forbid alternatives or to force the paper's central conclusion. The learned hit probability in the discriminative experiment is a fitted parameter, but it does not masquerade as a prediction of the main claims. The most serious flaw is elsewhere: Section 4.2, Eq. (8)-(9), asserts that p(X | Z) factorises over clusters without proving conditional independence, and conditioning on a shared observation such as the binary `hit` variable couples all enemy locations, so the 'exact' local inference is generally approximate. That is a correctness/approximation risk, not circularity, and it does not raise the circularity score.
Assumptions & free parameters
free parameters (2)
- hit success probability (learnable predicate t(_))
- enemy action policy (neural network weights)
assumptions (3)
- domain assumption Clusters of state variables are conditionally independent given observations (used in Eq. 8).
- ad hoc to paper The printed logic programs completely and correctly encode the environment dynamics.
- domain assumption Exact inference over the finite symbolic subspace is computationally feasible for the considered experiments.
Cite this review
Pith. "Pith review of Relational Neurosymbolic Markov Models." pith.science (2026). https://pith.science/paper/B2HNKGDB
@misc{pith2026241213023,
author = {Pith},
title = {Pith review of: Relational Neurosymbolic Markov Models},
year = {2026},
howpublished = {\url{https://pith.science/paper/B2HNKGDB}},
note = {Machine review of arXiv:2412.13023}
}
read the original abstract
Sequential problems are ubiquitous in AI, such as in reinforcement learning or natural language processing. State-of-the-art deep sequential models, like transformers, excel in these settings but fail to guarantee the satisfaction of constraints necessary for trustworthy deployment. In contrast, neurosymbolic AI (NeSy) provides a sound formalism to enforce constraints in deep probabilistic models but scales exponentially on sequential problems. To overcome these limitations, we introduce relational neurosymbolic Markov models (NeSy-MMs), a new class of end-to-end differentiable sequential models that integrate and provably satisfy relational logical constraints. We propose a strategy for inference and learning that scales on sequential settings, and that combines approximate Bayesian inference, automated reasoning, and gradient estimation. Our experiments show that NeSy-MMs can solve problems beyond the current state-of-the-art in neurosymbolic AI and still provide strong guarantees with respect to desired properties. Moreover, we show that our models are more interpretable and that constraints can be adapted at test time to out-of-distribution scenarios.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
D.; Ho, J.; Tarlow, D.; and Van Den Berg, R
Austin, J.; Johnson, D. D.; Ho, J.; Tarlow, D.; and Van Den Berg, R. 2021. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34: 17981--17993
2021
-
[4]
d.; Serafini, L.; and Spranger, M
Badreddine, S.; Garcez, A. d.; Serafini, L.; and Spranger, M. 2022. Logic tensor networks. Artificial Intelligence
work page 2022
-
[5]
Baum, L. E.; and Petrie, T. 1966. Statistical inference for probabilistic functions of finite state Markov chains. The annals of mathematical statistics, 37(6): 1554--1563
work page 1966
-
[6]
Bishop, C. M. 2006. Pattern recognition and machine learning. Springer google schola, 2: 645--678
work page 2006
-
[7]
Corenflos, A.; Thornton, J.; Deligiannidis, G.; and Doucet, A. 2021. Differentiable particle filtering via entropy-regularized optimal transport. In International Conference on Machine Learning, 2100--2111. PMLR
work page 2021
-
[8]
Darwiche, A. 2020. An Advance on Variable Elimination with Applications to Tensor-Based Computation. In ECAI 2020, 2559--2568. IOS Press
work page 2020
Show all 50 references
-
[9]
De Raedt, L.; Kersting, K.; Natarajan, S.; and Poole, D. 2016. Statistical relational artificial intelligence: Logic, probability, and computation. Synthesis lectures on artificial intelligence and machine learning
2016
-
[10]
De Raedt, L.; Kimmig, A.; and Toivonen, H. 2007. ProbLog: A Probabilistic Prolog and Its Application in Link Discovery. In IJCAI. Hyderabad
2007
-
[11]
De Smet, L.; Sansone, E.; and Zuidberg Dos Martires, P. 2023. Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick. In NeurIPS
2023
-
[12]
De Smet, L.; Zuidberg Dos Martires, P.; Manhaeve, R.; Marra, G.; Kimmig, A.; and De Readt, L. 2023. Neural Probabilistic Logic Programming in Discrete-Continuous Domains. UAI
2023
-
[13]
Dean, T.; and Kanazawa, K. 1989. A model for reasoning about persistence and causation. Computational intelligence, 5(2): 142--150
1989
-
[14]
Dinh, L.; Sohl-Dickstein, J.; and Bengio, S. 2016. Density estimation using real nvp. arXiv preprint arXiv:1605.08803
2016 arXiv
-
[15]
Goodfellow, I.; Pouget-Abadie, J.; Mirza, M.; Xu, B.; Warde-Farley, D.; Ozair, S.; Courville, A.; and Bengio, Y. 2020. Generative adversarial networks. Communications of the ACM, 63(11): 139--144
2020
-
[16]
Ho, J.; Jain, A.; and Abbeel, P. 2020. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33: 6840--6851
2020
-
[17]
Holtzen, S.; Van den Broeck, G.; and Millstein, T. 2020. Scaling exact inference for discrete probabilistic programs. Proceedings of the ACM on Programming Languages, 4(OOPSLA): 1--31
2020
-
[18]
Huang, J.; Li, Z.; Chen, B.; Samel, K.; Naik, M.; Song, L.; and Si, X. 2021. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. NeurIPS
2021
-
[19]
E.; and Holyoak, K
Hummel, J. E.; and Holyoak, K. J. 2003. A symbolic-connectionist theory of relational inference and generalization. Psychological review, 110(2): 220
2003
-
[20]
H.; and Rabiner, L
Juang, B. H.; and Rabiner, L. R. 1991. Hidden Markov models for speech recognition. Technometrics, 33(3): 251--272
1991
-
[21]
Khiatani, D.; and Ghose, U. 2017. Weather forecasting using hidden Markov model. In 2017 International Conference on Computing and Communication Technologies for Smart Nation (IC3TSN), 220--225. IEEE
2017
-
[22]
P.; and Ba, J
Kingma, D. P.; and Ba, J. 2015. Adam: A Method for Stochastic Optimization. In ICLR
2015
-
[23]
P.; and Welling, M
Kingma, D. P.; and Welling, M. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114
2013 arXiv
-
[24]
Kisa, D.; Van den Broeck, G.; Choi, A.; and Darwiche, A. 2014. Probabilistic sentential decision diagrams. In Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning
2014
-
[25]
Koller, D.; and Friedman, N. 2009. Probabilistic graphical models: principles and techniques. MIT press
2009
-
[26]
Kool, W.; van Hoof, H.; and Welling, M. 2019. Buy 4 reinforce samples, get a baseline for free! ICLR Deep RL Meets Structured Prediction Workshop
2019
-
[27]
Krishnan, R.; Shalit, U.; and Sontag, D. 2017. Structured inference networks for nonlinear state space models. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1)
2017
-
[28]
u ttler, H.; Nardelli, N.; Miller, A.; Raileanu, R.; Selvatici, M.; Grefenstette, E.; and Rockt \
K \"u ttler, H.; Nardelli, N.; Miller, A.; Raileanu, R.; Selvatici, M.; Grefenstette, E.; and Rockt \"a schel, T. 2020. The nethack learning environment. Advances in Neural Information Processing Systems, 33: 7671--7684
2020
-
[29]
Liu, R.; Regier, J.; Tripuraneni, N.; Jordan, M.; and Mcauliffe, J. 2019. Rao-Blackwellized stochastic gradients for discrete distributions. ICML
2019
-
[30]
Manhaeve, R.; Duman c i \'c , S.; Kimmig, A.; Demeester, T.; and De Raedt, L. 2021. Neural probabilistic logic programming in DeepProbLog. Artificial Intelligence
2021
-
[31]
Marra, G.; Duman c i \'c , S.; Manhaeve, R.; and De Raedt, L. 2024. From Statistical Relational to Neurosymbolic Artificial Intelligence: a Survey. Artificial Intelligence, 104062
2024
-
[32]
Misino, E.; Marra, G.; and Sansone, E. 2022. VAEL: Bridging Variational Autoencoders and Probabilistic Logic Programming. In NeurIPS
2022
-
[33]
Mor, B.; Garhwal, S.; and Kumar, A. 2020. A Systematic Review of Hidden Markov Models and Their Applications. Archives of Computational Methods in Engineering, 28: 1429 -- 1448
2020
-
[34]
Morettin, P.; Zuidberg Dos Martires, P.; Kolb, S.; and Passerini, A. 2021. Hybrid Probabilistic Inference with Logical and Algebraic Constraints: a Survey. In IJCAI
2021
-
[35]
Murphy, K.; and Russell, S. 2001. Rao-Blackwellised particle filtering for dynamic Bayesian networks. In Sequential Monte Carlo methods in practice, 499--515. Springer
2001
-
[36]
Nitti, D.; De Laet , T.; and De Raedt , L. 2016. Probabilistic logic programming for hybrid relational domains. Machine Learning
2016
-
[37]
Pearl, J. 1988. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann
1988
-
[38]
Reichstein, M.; Camps-Valls, G.; Stevens, B.; Jung, M.; Denzler, J.; Carvalhais, N.; and Prabhat, F. 2019. Deep learning and process understanding for data-driven Earth system science. Nature, 566(7743): 195--204
2019
-
[39]
Russell, S.; and Norvig, P. 2020. Artificial Intelligence : A Modern Approach . Hoboken: Pearson, 4th edition edition. ISBN 978-0-13-461099-3
2020
-
[40]
Samvelyan, M.; Kirk, R.; Kurin, V.; Parker-Holder, J.; Jiang, M.; Hambro, E.; Petroni, F.; Kuttler, H.; Grefenstette, E.; and Rockt \"a schel, T. 2021. MiniHack the Planet: A Sandbox for Open-Ended Reinforcement Learning Research. In Thirty-fifth Conference on Neural Informati...
2021
-
[41]
Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T.; et al. 2020. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839): 604--609
2020
-
[42]
\'S cibior, A.; Masrani, V.; and Wood, F. 2021. Differentiable Particle Filtering without Modifying the Forward Pass. In International Conference on Probabilistic Programming (PROBPROG)
2021
-
[43]
Tsamoura, E.; Carral, D.; Malizia, E.; and Urbani, J. 2021. Materializing knowledge bases via trigger graphs. Proceedings of the VLDB Endowment, 14(6): 943--956
2021
-
[44]
van Krieken, E.; Thanapalasingam, T.; Tomczak, J.; Van Harmelen, F.; and Ten Teije, A. 2024. A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36
2024
-
[45]
Van Roy, M.; Robberechts, P.; Yang, W.-C.; De Raedt, L.; and Davis, J. 2023. A Markov framework for learning and reasoning about strategies in professional soccer. Journal of Artificial Intelligence Research, 77: 517--562
2023
-
[46]
Williams, R. J. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning
1992
-
[47]
Yang, W.-C.; Marra, G.; Rens, G.; and De Raedt, L. 2023. Safe Reinforcement Learning via Probabilistic Logic Shields. In Elkind, E., ed., Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23 , 5739--5749. International Joint Conf...
2023
-
[48]
Yang, Z.; Ishay, A.; and Lee, J. 2020. Neurasp: Embracing neural networks into answer set programming. In IJCAI
2020
-
[49]
Younis, A.; and Sudderth, E. B. 2023. Differentiable and Stable Long-Range Tracking of Multiple Posterior Modes. In Thirty-seventh Conference on Neural Information Processing Systems
2023
-
[50]
Zhang, H.; Dang, M.; Peng, N.; and Van Den Broeck, G. 2023. Tractable Control for Autoregressive Language Generation. In Krause, A.; Brunskill, E.; Cho, K.; Engelhardt, B.; Sabato, S.; and Scarlett, J., eds., Proceedings of the 40th International Conference on Machine Learning...
2023
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.