Pith. sign in

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 →

arxiv 2412.07331 v2 pith:JBKECDYG submitted 2024-12-10 cs.AI cs.LG

classification cs.AIcs.LG MSC 68Q4568T27
keywords neurosymbolicAIsymbolicautomatasequenceclassificationtaggingprobabilisticsemanticsknowledgecompilationweightedmodelcountingweaksupervision
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proposes NeSyA, a neurosymbolic model for sequence classification and tagging that couples a neural network perceiving each time step with a symbolic automaton whose transitions are propositional logic formulas. The central claim is that giving the automaton clean probabilistic semantics, so that each transition probability is a weighted model count and the state distribution follows an HMM-style forward recursion, makes the whole system end-to-end differentiable and efficient to train from sequence-level labels only. The authors argue this combination scales better than prior neurosymbolic systems on temporal problems and is more accurate than a fuzzy-logic alternative on a synthetic driving benchmark, and that the injected symbolic knowledge improves generalization over purely neural sequence models on a real-world event-recognition task. A sympathetic reader would take the paper's contribution to be a reusable recipe: compile the temporal knowledge into a symbolic automaton, compile each logical transition into a tractable circuit, and run matrix-based forward inference.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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)
  1. [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.
  2. [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)
  1. [Section 3.1] There is a typo in the running example: 'We is is α2 = ...' should read 'We then compute α2 = ...'.
  2. [Appendix A] The word 'interptetaion' in the proof of Theorem 1 should be 'interpretation'.
  3. [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.
  4. [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

1 steps flagged · score 6.0 of 10

CAVIAR 'real-world generalization' claim is circular: the SFA that generates the labels is the same SFA embedded in NeSyA.

  1. 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 3 free parameters · 5 assumptions · 0 invented entities

The model introduces no new physical or ontological entities. It uses standard automata, propositional logic, and neural networks. The main assumptions are the independence factorization of symbol probabilities, the determinism of the automaton, the correctness of the hand-coded SFA for CAVIAR, and the standard WMC machinery.

free parameters (3)
  • Neural network weights f_theta = learned via gradient descent on the training loss
    All three models (NeSyA, CNN-LSTM, CNN-Transformer) depend on these weights; the comparison is between training procedures, not a derivation.
  • Learning rate = 0.001, 0.0001, 0.00001 (CAVIAR); 0.001 (synthetic)
    Selected by hand because the dataset is too small for a validation split; results vary considerably with this choice.
  • Training epochs / early stopping patience = 100 epochs (synthetic); patience 10 (CAVIAR)
    Set by the authors; affects convergence and reported test metrics.
assumptions (5)
  • domain assumption Independence of proposition variables: P(omega|p) = product over symbols (Eq. 1).
    The neural network emits a probability per symbol and the model treats them as independent, which makes WMC tractable. Real perception outputs are often correlated, so this is a simplification.
  • domain assumption Determinism of the SFA: for every state and interpretation, exactly one outgoing transition is satisfied (Section 2.2).
    Guarantees that transition matrices are row-stochastic. In CAVIAR, a self-loop is added when no transition matches, which is a relaxation not covered by the definition.
  • domain assumption The SFA is a correct specification of the target temporal pattern (Section 4.2, CAVIAR).
    The paper assumes perfect knowledge of the event calculus rules from Artikis et al. and uses SFA-generated labels as ground truth. If the rules are wrong, the evaluation is invalid.
  • standard math Weighted model counting via knowledge compilation is exact and differentiable (Section 2.3).
    The paper relies on the correctness of WMC and d-DNNF compilation as established in the literature.
  • domain assumption Conditional independence over time given the state sequence (graphical model in Figure 3).
    The forward recursion factorizes the joint probability as a product over time, assuming the observations do not directly depend on past observations beyond the state. This is the standard MEMM assumption.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2412.07331 by the authors.

Figure 1
Figure 1. Symbolic automata (middle) are used to reason over se [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Graphical model for NESYA. Following the approach used in [McCallum et al., 2000], it resembles a Hidden Markov Model with the arrows between states and observations reversed. The ran￾dom variables qt take values from Q, the state space of the SFA, and the random variables ot take values from high-dimensional continu￾ous spaces. the observation ot. The neural network is used to bridge be￾tween the discrete represent… view at source ↗
Figure 4
Figure 4. Scalability results for NESYA (solid) and DEEP￾STOCHLOG (dashed) for each of the three patterns tested.The y-axis represents the update time for a single batch of 16 sequences in log￾arithmic scale and the x-axis the sequence length. The systems were benchmarked for three different patterns of varying complexity both in terms of symbols, as well as states of the automaton. A, then P π|=A P(π|p1, p2, . . . , pt) is c… view at source ↗
Figures from the paper (1 more)
Figure 6
Figure 6. Figure 6: The SFA used for the CAVIAR experiments. It defines [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. LTLZinc: a Benchmarking Framework for Continual Learning and Neuro-Symbolic Temporal Reasoning

    cs.AI 2025-07 conditional novelty 7.0 of 10

    LTLZinc generates image-based temporal reasoning and continual learning benchmarks from LTLf formulas over MiniZinc constraints, and experiments show existing methods often fail.

  2. Defining neurosymbolic AI

    cs.AI 2025-07 conditional novelty 7.0 of 10

    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.

  3. A Neuro-Symbolic Framework for Sequence Classification with Relational and Temporal Knowledge

    cs.AI 2025-05 conditional novelty 6.0 of 10

    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.

  4. Neuro-Symbolic Predictive Process Monitoring

    cs.AI 2025-08 conditional novelty 5.0 of 10

    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

28 extracted references · 23 canonical work pages · cited by 4 Pith papers

  1. [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

  2. [2]

    u diger Ehlers, Bettina K \

    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

  3. [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

  4. [4]

    Logic tensor networks

    Samy Badreddine, Artur d'Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence , 303:103649, 2022

  5. [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

  6. [6]

    A knowledge compilation map

    Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research , 17:229--264, 2002

  7. [7]

    Decomposable negation normal form

    Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM) , 48(4):608--647, 2001

  8. [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

Show all 28 references
  1. [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

  2. [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

  3. [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

  4. [12]

    Long short-term memory

    S Hochreiter. Long short-term memory. Neural Computation MIT-Press , 1997

  5. [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

  6. [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...

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [22]

    Attention is all you need

    A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems , 2017

  15. [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

  16. [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

  17. [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...

  18. [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...

  19. [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

  20. [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 '...

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.