REVIEW 2 major objections 4 minor 4 cited by
NeSyA: Neurosymbolic Automata
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read NeSyA combines neural perception with symbolic automata under probabilistic semantics to give end-to-end differentiable sequence classification that scales and generalizes better than prior neurosymbolic systems.
desk verdict Clean, useful algorithm for temporal neurosymbolic learning; the synthetic benchmark is solid, but the CAVIAR generalization claim rests on circular label generation. 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 device carrying the argument is a deterministic symbolic automaton: a finite automaton whose transitions are labeled by propositional formulas over a fixed set of symbols, with exactly one outgoing transition true for every interpretation. NeSyA treats the neural net's output at each time step as independent symbol probabilities, turns each transition formula into an arithmetic circuit via knowledge compilation, computes a transition matrix of weighted model counts per time step, and updates the state distribution by vector-matrix multiplication. This is the same forward recursion as a hidden Markov model, but with transition probabilities derived from logical formulas rather than a fixed table. The recursion is exact, differentiable, parallelizable on GPUs, and polynomial in the number of compiled-circuit nodes and automaton states, which is what gives the scalability advantage over systems that reduce the whole temporal query to a flat propositional formula.
What would settle it
A direct test is to construct a synthetic perception stack whose symbol errors are correlated, for example where two symbols are misread together far more often than independently, while the ground-truth trace distribution is known, and compare NeSyA's predicted acceptance probabilities against empirically observed acceptance frequencies. If the predictions are systematically off whenever correlations are strong, the product-form independence assumption is the cause; a variant that models joint symbol probabilities should outperform it.
Extended reading notes
Core claim
The central discovery is that deterministic symbolic automata, whose transitions are propositional formulas over a set of variables, can be composed with a neural perception network under a probabilistic semantics such that the probability of an input sequence being accepted is computed exactly and differentiably. Given a neural probability vector $p_t$ over symbols for each observation, the probability of a transition formula is the weighted model count of that formula; compiling each formula once into a d-DNNF (decomposable negation normal form) arithmetic circuit makes every transition probability linear-time, and the standard forward recursion over automaton states then yields $\alpha_t(q)$, the probability of being in state $q$ after $t$ observations. The paper proves that this recursion equals the sum over all traces that lead to state $q$, weighted by their product-of-per-step probabilities, so summing $\alpha$ over accepting states gives exactly the probability that the symbolic automaton accepts the trace. Training uses weak supervision: only sequence-level binary labels (or frame-level high-level labels) are needed, and gradients flow through the arithmetic circuits and matrix products into the neural network.
Load-bearing premise
The model assumes the symbols at each time step are perceived independently: the probability of a full interpretation is the product of per-symbol probabilities, so correlated perception errors are not modeled. If real perception outputs have such correlations, the computed acceptance probabilities will be miscalibrated and training may chase the wrong signal.
Editorial extensions
If this is right
- NeSyA lets a temporal symbolic constraint be used as a differentiable loss: a convolutional network learns symbol grounding from sequence-level labels alone, without any per-symbol annotations.
- For the tested synthetic patterns, NeSyA updates orders of magnitude faster than the stochastic logic programming and probabilistic logic programming baselines, making exact probabilistic neurosymbolic inference practical on sequences that are too long for those systems.
- Against the fuzzy-logic alternative, NeSyA's probabilistic semantics give higher accuracy, with the gap growing as sequences lengthen.
- On the CAVIAR event-recognition task, injecting the automaton's logical structure gives NeSyA competitive or better macro-F1 than recurrent and transformer sequence models while using roughly an order of magnitude fewer parameters, with smaller train-test gaps.
- The alpha-semantics theorem makes the compiled symbolic automaton a tractable device for exact queries about uncertain symbolic sequences, so it can serve as a compilation target for temporal neurosymbolic programs.
Reading between the lines
- Beyond the paper, the same construction suggests a modular route to temporal neurosymbolic AI: any high-level temporal language that compiles to a deterministic symbolic automaton inherits exact differentiable probabilistic inference, much as tractable circuit representations did for atemporal formulas.
- Beyond the paper, the independence assumption is the obvious bottleneck; a natural testable extension is to let the neural network emit a richer joint distribution over symbols per time step, or to add a learned correlation term, and measure whether the accuracy gains persist.
- Beyond the paper, because the automaton state distribution is computed per time step, NeSyA could be plugged into reinforcement-learning pipelines as a differentiable temporal constraint or reward-shaping signal, which the paper itself suggests as future work.
- Beyond the paper, the event-recognition results use a three-state automaton and simple transition logic; a reader should not generalize to complex temporal knowledge until experiments cover larger automata and longer, noisier sequences.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes NeSyA, a neurosymbolic model for sequence classification and tagging that combines symbolic automata with neural perception. It defines a probabilistic semantics via weighted model counting over transition formulas, uses knowledge compilation to make transition probabilities differentiable, and computes acceptance probabilities with a matrix-based forward recursion analogous to HMM inference. The authors prove Theorem 1 relating the forward probabilities to sums over trace probabilities, and evaluate on a synthetic driving domain against DeepStochLog, DeepProblog, and FuzzyA, and on the CAVIAR event recognition domain against CNN-LSTM and CNN-Transformer baselines.
Significance. The clean probabilistic semantics and exact, compilation-based inference for temporal neurosymbolic reasoning are valuable; Theorem 1 and the matrix-based recursion provide a solid formal foundation, and the code is released. The synthetic experiments show large scaling and accuracy margins over existing NeSy systems. However, the CAVIAR experiment does not currently support the claimed real-world generalization benefit because the high-level labels are generated by the same SFA that NeSyA uses, and the asserted equivalence with DeepStochLog is not demonstrated.
major comments (2)
- [Section 4.2 (Event Recognition)] The CAVIAR evaluation is circular for the generalization claim: the paper states that 'Using the labels generated by the SFA, we assume perfect knowledge' and that the human-annotated labels are discarded because they are noisy. Since the same SFA both generates the training targets and performs temporal decoding in NeSyA, the comparison against CNN-LSTM and CNN-Transformer does not measure real-world event recognition; it measures the benefit of injecting the exact label-generating automaton into the model. The conclusion that NeSyA 'provides benefits in terms of generalization compared to purely neural systems in a real-world event recognition task' is therefore unsupported. Please either re-run with the original human annotations and a noise-handling procedure, or clearly reframe the experiment as a study of perfect-knowledge injection and remove the real-world generalization claim.
- [Section 4.1 (Synthetic Driving)] The paper asserts without derivation that NeSyA, DeepStochLog, and DeepProblog are 'equivalent in their computation and learning setup' and therefore have identical accuracy, and it omits accuracy comparisons with those systems. This equivalence is not obvious because DeepStochLog is based on stochastic logic programs with a different inference mechanism, and DeepProblog is atemporal. Without a formal statement or a reference establishing the equivalence, the reported runtime gaps cannot be attributed solely to the inference scheme, and the accuracy claim is unverified. Please add a derivation or proof, or report accuracy results for those systems.
minor comments (4)
- [Section 3.1] There is a typo in the running example: 'We is is α2 = ...' should read 'We then compute α2 = ...'.
- [Appendix A] The word 'interptetaion' in the proof of Theorem 1 should be 'interpretation'.
- [Table 1] The table header is ambiguous: the columns 'Pattern / Sequence Length / Method' with three numeric subcolumns are difficult to parse; please restructure the table so that the three sequence lengths are clearly separate.
- [Section 2.3] The independence assumption in Eq. (1), namely that symbol probabilities factor as a product of independent per-symbol probabilities, is stated but never discussed as a limitation; a sentence on its implications for correlated perception errors would be helpful.
Circularity Check
CAVIAR 'real-world generalization' claim is circular: the SFA that generates the labels is the same SFA embedded in NeSyA.
-
self definitional
[Section 4.2, Event Recognition (paragraph after Figure 6)]
"We use the SFA to label the sequence with the current high-level event in each frame given the ground truth labels for the low level activities. ... Using the labels generated by the SFA, we assume perfect knowledge, i.e. that the symbolic component of NESYA can perfectly retrieve the high-level events, given the low-level activities."
The high-level event labels used for training and evaluation in CAVIAR are produced by the very SFA that constitutes NeSyA's symbolic component (Figure 6). Consequently, NeSyA's temporal reasoning is not learned or independently tested; it is supplied as the exact label-generating rule, so the model only needs to learn a per-frame CNN grounder for low-level activities. The CNN-LSTM and CNN-Transformer baselines, by contrast, must learn both the low-level grounding and the high-level event structure from data alone. The abstract's claim that NeSyA 'provide[s] benefits in terms of generalization compared to purely neural systems in a real-world event recognition task' therefore reduces to the construction: the target labels and the model's symbolic knowledge are the same automaton.
full rationale
The formal core of the paper is not circular: Eq. (2) and Theorem 1 follow from the definitions of the SFA, the product-form symbol probabilities in Eq. (1), and the forward recursion; the acceptance probability is a direct consequence, not a fitted quantity. The synthetic benchmark gives all NeSy systems the same symbolic rule, so the accuracy/scalability comparison there is a valid empirical comparison. The one load-bearing circularity is the CAVIAR evaluation: the paper states that the SFA generates the high-level labels and that NeSyA 'assume[s] perfect knowledge' by embedding that same SFA. Since the claimed real-world generalization benefit rests on this setup, and the label generator is identical to the model's symbolic component, that empirical claim is circular by construction. This does not invalidate the algorithmic contributions, but it removes the CAVIAR generalization result as independent support for the abstract's real-world claim.
Assumptions & free parameters
free parameters (3)
- Neural network weights f_theta =
learned via gradient descent on the training loss
- Learning rate =
0.001, 0.0001, 0.00001 (CAVIAR); 0.001 (synthetic)
- Training epochs / early stopping patience =
100 epochs (synthetic); patience 10 (CAVIAR)
assumptions (5)
- domain assumption Independence of proposition variables: P(omega|p) = product over symbols (Eq. 1).
- domain assumption Determinism of the SFA: for every state and interpretation, exactly one outgoing transition is satisfied (Section 2.2).
- domain assumption The SFA is a correct specification of the target temporal pattern (Section 4.2, CAVIAR).
- standard math Weighted model counting via knowledge compilation is exact and differentiable (Section 2.3).
- domain assumption Conditional independence over time given the state sequence (graphical model in Figure 3).
Cite this review
Pith. "Pith review of NeSyA: Neurosymbolic Automata." pith.science (2026). https://pith.science/paper/JBKECDYG
@misc{pith2026241207331,
author = {Pith},
title = {Pith review of: NeSyA: Neurosymbolic Automata},
year = {2026},
howpublished = {\url{https://pith.science/paper/JBKECDYG}},
note = {Machine review of arXiv:2412.07331}
}
read the original abstract
Neurosymbolic (NeSy) AI has emerged as a promising direction to integrate neural and symbolic reasoning. Unfortunately, little effort has been given to developing NeSy systems tailored to sequential/temporal problems. We identify symbolic automata (which combine the power of automata for temporal reasoning with that of propositional logic for static reasoning) as a suitable formalism for expressing knowledge in temporal domains. Focusing on the task of sequence classification and tagging we show that symbolic automata can be integrated with neural-based perception, under probabilistic semantics towards an end-to-end differentiable model. Our proposed hybrid model, termed NeSyA (Neuro Symbolic Automata) is shown to either scale or perform more accurately than previous NeSy systems in a synthetic benchmark and to provide benefits in terms of generalization compared to purely neural systems in a real-world event recognition task.
Figures
Forward citations
Cited by 4 Pith papers
-
LTLZinc: a Benchmarking Framework for Continual Learning and Neuro-Symbolic Temporal Reasoning
LTLZinc generates image-based temporal reasoning and continual learning benchmarks from LTLf formulas over MiniZinc constraints, and experiments show existing methods often fail.
-
Defining neurosymbolic AI
Neurosymbolic inference is defined as a Lebesgue integral over interpretations of the product of a logical selection function and a parametrized belief function, unifying many existing systems.
-
A Neuro-Symbolic Framework for Sequence Classification with Relational and Temporal Knowledge
The paper proposes LTLZinc, a generator of relational-temporal sequence classification benchmarks, and shows that current neuro-symbolic methods degrade when temporal and relational reasoning are combined.
-
Neuro-Symbolic Predictive Process Monitoring
A differentiable LTLf-based loss, using Gumbel-Softmax sampling and DeepDFA, improves rule compliance and accuracy of autoregressive suffix predictors for business process traces.
Reference graph
Works this paper leans on
-
[1]
A pseudo-semantic loss for autoregressive models with logical constraints
Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. A pseudo-semantic loss for autoregressive models with logical constraints. Advances in Neural Information Processing Systems , 36, 2024
work page 2024
-
[2]
Mohammed Alshiekh, Roderick Bloem, R \"u diger Ehlers, Bettina K \"o nighofer, Scott Niekum, and Ufuk Topcu. Safe reinforcement learning via shielding. In Proceedings of the AAAI conference on artificial intelligence , volume 32, 2018
work page 2018
-
[3]
An event calculus for event recognition
Alexander Artikis, Marek Sergot, and Georgios Paliouras. An event calculus for event recognition. IEEE Transactions on Knowledge and Data Engineering , 27(4):895--908, 2014
work page 2014
-
[4]
Samy Badreddine, Artur d'Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence , 303:103649, 2022
work page 2022
-
[5]
On probabilistic inference by weighted model counting
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence , 172(6-7):772--799, 2008
2008
-
[6]
A knowledge compilation map
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research , 17:229--264, 2002
2002
-
[7]
Decomposable negation normal form
Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM) , 48(4):608--647, 2001
work page 2001
-
[8]
Linear temporal logic and linear dynamic logic on finite traces
Giuseppe De Giacomo, Moshe Y Vardi, et al. Linear temporal logic and linear dynamic logic on finite traces. In Ijcai , volume 13, pages 854--860, 2013
work page 2013
Show all 28 references
-
[9]
Neurosymbolic markov models
Lennert De Smet, Gabriele Venturato, Luc De Raedt, and Giuseppe Marra. Neurosymbolic markov models. In ICML 2024 Workshop on Structured Probabilistic Inference \ & \ Generative Modeling , 2024
2024
-
[10]
Neurosymbolic ai: The 3 rd wave
Artur d’Avila Garcez and Luis C Lamb. Neurosymbolic ai: The 3 rd wave. Artificial Intelligence Review , 56(11):12387--12406, 2023
2023
-
[11]
Efficient solution algorithms for factored mdps
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research , 19:399--468, 2003
2003
-
[12]
Long short-term memory
S Hochreiter. Long short-term memory. Neural Computation MIT-Press , 1997
1997
-
[13]
Using reward machines for high-level task specification and decomposition in reinforcement learning
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning , pages 2107--2116. PMLR, 2018
2018
-
[14]
Safe Reinforcement Learning Using Probabilistic Shields
Nils Jansen, Bettina K\" o nighofer, Sebastian Junges, Alex Serban, and Roderick Bloem. Safe Reinforcement Learning Using Probabilistic Shields . In Igor Konnov and Laura Kov\' a cs, editors, 31st International Conference on Concurrency Theory (CONCUR 2020) , volume 171 of Lei...
2020
-
[15]
A logic-based calculus of events
Robert Kowalski and Marek Sergot. A logic-based calculus of events. New generation computing , 4:67--95, 1986
1986
-
[16]
Deepproblog: Neural probabilistic logic programming
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural information processing systems , 31, 2018
2018
-
[17]
Maximum entropy markov models for information extraction and segmentation
Andrew McCallum, Dayne Freitag, Fernando CN Pereira, et al. Maximum entropy markov models for information extraction and segmentation. In Icml , volume 17, pages 591--598, 2000
2000
-
[18]
Deepdfa: Automata learning through neural probabilistic relaxations
Elena Umili and Roberto Capobianco. Deepdfa: Automata learning through neural probabilistic relaxations. In ECAI 2024 , pages 1051--1058. Ios Press, 2024
2024
-
[19]
Visual reward machines
Elena Umili, Francesco Argenziano, Aymeric Barbin, Roberto Capobianco, et al. Visual reward machines. In Neural-Symbolic Learning and Reasoning 2022 , volume 3212, pages 255--267. 2023
2022
-
[20]
Grounding ltlf specifications in image sequences
Elena Umili, Roberto Capobianco, and Giuseppe De Giacomo. Grounding ltlf specifications in image sequences. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning , volume 19, pages 668--678, 2023
2023
-
[21]
The complexity of enumeration and reliability problems
Leslie G Valiant. The complexity of enumeration and reliability problems. siam Journal on Computing , 8(3):410--421, 1979
1979
-
[22]
Attention is all you need
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems , 2017
2017
-
[23]
Deepstochlog: Neural stochastic logic programming
Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. Deepstochlog: Neural stochastic logic programming. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 36, pages 10090--10100, 2022
2022
-
[24]
A semantic loss function for deep learning with symbolic knowledge
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. A semantic loss function for deep learning with symbolic knowledge. In International conference on machine learning , pages 5502--5511. PMLR, 2018
2018
-
[25]
Neurasp: Embracing neural networks into answer set programming
Zhun Yang, Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer set programming. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20 , pages 1755--1762. International Joint C...
2020
-
[26]
Safe reinforcement learning via probabilistic logic shields
Wen-Chi Yang, Giuseppe Marra, Gavin Rens, and Luc De Raedt. Safe reinforcement learning via probabilistic logic shields. In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23 , pages 5739--5749. Internatio...
2023
-
[27]
Tractable control for autoregressive language generation
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference on Machine Learning , pages 40932--40945. PMLR, 2023
2023
-
[28]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence '...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.