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

1 Introduction

Sequence classification is a very well-known task in machine learning which can become very challenging when decisions must be made on top of complex features or without suitable priors, especially when safety, reliability and accountability are of paramount importance (autonomous driving [Roesener et al., 2016], industrial control systems [Chakraborty et al., 2022], medicine [Ivaturi et al., 2021], and others). The task can be also approached by symbolic methods exploiting grounded frameworks, such as regular expressions [Galassi and Giordana, 2005] and automata induction [Angluin, 1982], or temporal logics satisfiability [Rozier and Vardi, 2007]. However, they tend to struggle in the presence of noise [Umili and Capobianco, 2024], and may be unsuitable for open-world settings where background knowledge or inductive priors are not available at all. Neurosymbolic artificial intelligence [Besold et al., 2021] aims to get the best of both worlds, by merging neural and symbolic methods, as in DeepProbLog [Manhaeve et al., 2018], or Logic Tensor Networks [Badreddine et al., 2022]. Little has been done for sequence classification in presence of (i) "relational" and (ii) "temporal" knowledge. The former describes features within each single time-step while the latter models information along the temporal dimension. For example, consider a safety-critical system where several cameras monitor an environment, controlling the movements of automated guided vehicles. At each timestep, every vehicle has to satisfy some safety properties regarding its movements, for example to avoid collisions; in addition, at some checkpoints it is necessary to assess that some tasks have been executed in a specific order throughout the temporal sequence. Motivated by this challenging and still under-explored setting, this paper collects several contributions. (a) We propose a new benchmarking framework for sequence classification (and similar tasks) in the presence of domain knowledge that extends also over the temporal dimension. Our framework is capable of generating datasets with multi-channel sequences of arbitrary length, by sampling given image classification datasets according to user-defined temporal and relational specifications. (b) We share with the scientific community ready-to-use datasets for six challenging tasks, as well as baseline performances for neural-only and modular neurosymbolic architectures. Building on top of a neural net processing the raw data, our neuro-symbolic architecture consists of an automata-based temporal reasoner stacked on top of a relational symbolic module, both representatives of state of the art approaches in their respective categories. (c) Our detailed experimental study highlights two under-investigated problems: specific methods for temporal reasoning, highlyeffective with propositional inputs, struggle when extended to a relational setting, even when the interface is "propositionalized" by an upstream reasoner, and, conversely, relational neuro-symbolic methods present training instabilities when coupled with downstream (temporal) reasoning components.

∗ Part of the work was done while LSL was visiting KU Leuven. Supplementary material at: https://arxiv.org/abs/2505.05106

2 Background

Linear temporal logic over finite traces. A dynamic discrete system is a triple ⟨S,R, s0⟩, where S is a set of (possibly infinite) states, R is a transition relation between states, often non-deterministic, and s0 ∈ S is the initial state. An execution trace is a (possibly infinite) sequence of states (s0, s1, s2, . . . ), such that R(si-1, si), ∀i > 0. Linear Temporal Logic (LTL) [Pnueli, 1977] is a formalism for temporal reasoning over infinite execution traces of dynamic discrete systems, capable of expressing properties related to state reachability. Given a sub-formula or an atomic proposition, indicated with ϕ or ψ in the following, the next operator ⃝ models immediate future reachability, i.e., ⃝ϕ means that ϕ has to hold at the next state. Other operators model eventual reachability (finally/eventually operator, ♢ϕ, i.e., ϕ has to hold at least once in the future), invariance (globally operator, □ϕ, i.e., ϕ has to hold on the entire subsequent path) and conditional reachability (such as the binary operators until, ϕUψ, and releases, ϕRψ). The original formulation of LTL can modified in multiple ways: LTL over finite traces (LTLf ) [De Giacomo and Vardi, 2013] is a restriction which preserves the same syntax of LTL 1 but redefines its semantics, in order to be applied to execution traces of finite length. This restriction also has practical repercussions: while LTL can express ω-languages recognized by B¨uchi automata, reasoning over LTLf can be reduced to regular languages, accepted by deterministic finite state automata (DFA). In this work we convert LTLf formulas to DFAs, using flloat 2 .

Neuro-symbolic integration of logic formulas. The main challenge of neuro-symbolic integration [Besold et al., 2021] consists in providing an interface between two components: learning by means of neural networks, which requires representations in a continuous space, and reasoning, which often benefits from discrete representations of symbols. A popular approach for the integration of logic knowledge, known as the model-theoretic approach [Marra et al., 2024], is to relax truth assignments, in a way which extends Boolean algebra in a continuous and differentiable space. Fuzzy logic [Badreddine et al., 2022] extends interpretations in the continuous range [0, 1] and replaces Boolean conjunction with a tnorm. 3 The obtained expressions are equivalent to the original Boolean formula at boundary values, but allow differentiability by means of a progressive transition between truth values, which can constrain the learning procedure [Gnecco et al., 2015]. Different choices of t-norms are possible, each characterized by different advantages and drawbacks. An alternative framework for model-theoretic neuro-symbolic integration, overcoming some issues with differentiable fuzzy logics [van Krieken et al., 2022], is based on probabilistic inference. In this framework, with strong theoretical and computational foundations in statistical and relational artificial intelligence [De Raedt et al., 2016], Boolean propositions are seen as Bernoulli random variables and logic connectives are interpreted as set operators. Weighted model counting (WMC) is a general framework for probabilistic inference. Algebraic model counting (AMC) [Kimmig et al., 2017] extends WMC by replacing Boolean operators with elements of an algebraic semiring, allowing to solve a plethora of probabilistic tasks within a single framework. WMC and AMC are in general #P-COMPLETE [Chavira and Darwiche, 2008], however they become tractable when logic formulas possess a specific structure. Knowledge compilation [Darwiche and Marquis, 2002] amortizes execution time by converting input formulas into equivalent target normal forms, on top of which clausal inference (and possibly other classes of tasks) can be executed in polynomial time. In this context, we mention sd-DNNF, the smooth and decomposable deterministic negated normal form, a popular knowledge compilation target language, which guarantees correct model counting in polynomial time, also in the presence of neutral and disjoint sums.

1 LTLf , introduces an additional operator, weak next, Wϕ, to deal with last state semantics in finite traces.

2 https://github.com/whitemech/flloat

3 In propositional logic, every other operator is constructed by exploiting the definition ¬p = 1 - p and equivalence axioms.

3 RelatedWorks

Neuro-symbolic temporal reasoning. Neuro-symbolic temporal reasoning has been employed for temporal formula induction, approximate satisfiability and sequence classification driven by background knowledge. [Camacho and McIlraith, 2019] address formula induction in a symbolic fashion, by building a vocabulary of subformulas which are converted to alternating finite automata, and then composed to discover the target formula from positive and negative examples, while [Walke et al., 2021] propose the use of specialized recurrent layers for sequence classification, which can collectively be interpreted as an LTLf formula, by extracting a truth table from discretized weights. Finally, [Umili and Capobianco, 2024] attempt to learn DFA transition matrices from examples, by discretizing a recurrent neural network, regularized during training to produce discrete activations. Exact LTL satisfiability is PSPACE-COMPLETE. However, recently, several approaches based on neural networks have been proposed to approximate satisfiability in polynomial time: [Xie et al., 2021] employ message passing graph neural networks to learn embeddings for a DFA equivalent to the target LTLf formula; [Mukherjee et al., 2022] exploit graph isomorphism networks to perform approximate model checking; [Luo et al., 2022; Luo et al., 2024] use recursive neural networks to generate explanations as traces satisfying the given formulas.

Neuro-symbolic finite state automata. There is a strong link between inference in DFA and recurrent neural networks, as the former performs trace acceptance using a state transition matrix and the latter updates an internal state according to a deterministic function. On the other hand, the discrete nature of DFAs is particularly amenable to be encoded by (sets of) Boolean formulas, which, in turn, can be subject to neuro-symbolic integration. Starting from this consideration, [Umili et al., 2023] exploit background knowledge in the form of LTLf formulas to learn symbolic labels from sequence labels, by performing distant supervision [Manhaeve et al., 2018]. The transition matrix is converted into a disjunction of Horn clauses and the entire logic program is finally encoded into a Logic Tensor Network [Badreddine et al., 2022] that can be trained end-to-end on sequence labels, by means of binary cross-entropy or a proposed semantic loss penalizing discordance between ground truth labels and the observed final state. [Manginas et al., 2024] highlight the shortcomings of this method, by identifying a general failure on more complex datasets, consisting of larger DFAs, longer temporal horizons or more complex transition guards, and pinpointing the cause on the fuzzy encoding. In their extension, each transition guard is compiled into an sd-DNNF, and the automaton is given probabilistic semantics, by means of AMC on the probability semiring, largely improving scalability.

Relationships to this paper. We take inspiration both from [Umili et al., 2023] and [Manginas et al., 2024], however we allow transition labels to contain constraints (i.e., first order predicates of known semantics, applied to terms which represent objects in finite domains). This distinction places our work closer to symbolic automata [Veanes et al., 2010; Veanes, 2013; D'Antoni and Veanes, 2017], and it is characterized by additional challenges. We address these challenges in a straight-forward manner, by decoupling reasoning in two components: relational and temporal inference. In this way, temporal inference is reduced to the propositional case, decoupling the additional challenges provided by a first order setting, from those posed by more complex temporal behaviors. From a neuro-symbolic perspective, our decoupling approach also provides benefits in terms of knowledge injection: as the semantics of states is defined over constraint satisfaction problems, background knowledge is richer and more structured (i.e., constraints act as relations between concepts, while propositional formalisms are limited to assignments).

4 Sequence Classification with Relational and Temporal Knowledge

Problem definition. Let S = ([xt0 , . . . , xtN-1 ])T-1 t=0 be a sequence of length T that consists, for each time step t, of N perceptual stimuli belonging to as many perceptual domains Xj: xtj ∈ Xj. Each xtj is associated to a symbol yt j that belongs to a symbolic domain yt j ∈ Yj. As an example, X0 and X1 could be the domain of MNIST digits [LeCun, 1998] and Fashion-MNIST articles [Xiao et al., 2017], respectively, whereas Y0 and Y1 the corresponding sets of (symbolic) classes. To avoid confusing the stimulus/domain index with the time index, we will sometimes use letter subscripts in place of numbers (e.g., A, B in place of 0, 1) to refer to different stimuli, symbols, and domains (e.g., xtA, xtB , ytA, ytB , XA, XB, YA, YB, etc.). We consider the problem of learning a binary classifier f : S ↦→ {0, 1} which maps the input sequence to the positive class if and only if S |= T , where T is a temporal specification that consists in an LTLf formula whose atomic symbols are first order relations grounded over symbolic domains Yj. Intuitively, this means that the sequence classification task consists in assessing whether two sets of properties jointly hold or not: (i) instantaneous relations among the N symbolic domains which may or may not hold for any t ("relational"), and (ii) meta-relations about the validity of each instantaneous property over time ("temporal"). The reasoning process in such setting can be reduced to querying the validity of each instantaneous property to build a trace of truth values, and then checking whether the trace satisfies the temporal specification. In order to preserve LTLf conciseness and readability, we encode "relational" (i.e., instantaneous) properties as constraints over finite domains [Nethercote et al., 2007], which allow to express arithmetic, identity-based, ordering-based, lexicographic, etc., relations with well-codified, compact, and efficient to compute constructs, known as global constraints. To further aid readability, we collect (i) relational properties into a set of constraints C, separately from the (ii) "temporal" formula in F. It is important to note that, in our setting, it is the joint effect of the LTLf formula and the properties with which its symbols are grounded (i.e., the complete background knowledge is T = C ∪ F), which acts as decision rule. As an example, let us consider two popular digit classification datasets, MNIST and SVHN [Netzer et al., 2011], where class names can be also interpreted as class indices. Suppose that we have a sequence S where, at each time instant, we are given N = 3 stimuli (xtA, xtB , xtC ), xtA ∈ XA, xtB ∈ XB, with XA = XB = MNIST digits, while xtC ∈ XC = SVHN digits. Let us consider the case in which the N perceptual stimuli are mapped to N symbols (ytA, ytB , ytC ), belonging to domains YA = YB = [0, 9], and YC = [2, 8] (integer). As "relational" knowledge we assume that two properties can potentially hold: yA + yB = yC and yA ̸= yB ∧ yB ̸= yC ∧ yC ̸= yA, 4 where we compactly indicate the latter with all different(yA, yB, yC). We then introduce some "temporal" knowledge: in even timesteps the sum constraint is expected to hold, while all different is expected to hold for odd steps. The goal is to learn a binary classifier, distinguishing knowledge-coherent sequences from incoherent ones. The properties of our problem can more formally and concisely be defined as the quadruple ⟨X , Y, C, F⟩ where X and Y are the unions of all the perceptive and symbolic domains, respectively; C is the set encoding the relational knowledge; F is the temporal formula. We have:

Therefore, a sequence of triples such as ([ , , ] , [ , , ] , [ , , ] , [ , , ]), corresponding to the trace ([p, ¬q] , [¬p, q] , [p, q] , [¬p, q]), will be accepted by a knowledge-driven sequence classifier, while ([ , , ], [ , , ], [ , , ], [ , , ]), corresponding to the trace ([p, ¬q], [¬p, q], [¬p, q], [¬p, q]) will not, as ¬p (bold) violates the temporal property.

The LTLZinc Framework. LTLZinc 5 is a benchmarking framework for temporal reasoning tasks, capable of generating sequences from user-defined constraint specifications, involving relational and temporal knowledge. LTLZinc receives as input the quadruple ⟨X, Y, C,F⟩, as well as additional options, and produces an output depending on either of two modes: (i) sequential and (ii) incremental. In (i) sequential (which could informally be categorized as "learning about time"), the output will be a dataset of densely annotated sequences, which can be used for binary classification, and other temporal-related tasks. In (ii) incremental mode (which could informally be classified as "learning over time"), LTLZinc outputs a single sequence of datasets, to be used in incremental/continual [Wang et al., 2024] and curriculum learning settings. As LTL is strictly more expressive than current definitions of incremental learning in the literature, it is straight-forward to encode class-incremental, task-incremental and domain adaptation settings with LTLZinc. Internally, LTLZinc converts the temporal specification F into a DFA annotated with constraints, and solves a collection of MiniZinc programs, corresponding to the subset of C satisfying each of the transition guards, caching every solution found. Then, (positive/negative) sequences of userspecified length are generated by random walks along the automaton, where at each transition one solution of the corresponding problem is randomly sampled. Annotations contain the background knowledge, consisting of the user specification (the quadruple ⟨X , Y, C, F⟩) and the generated automaton, sequence-level binary labels, the trace of traversed states during generation, the trace of constraint truth values, and the trace of image labels for each stimulus of the N-uple).

4 In MiniZinc [Nethercote et al., 2007] enumerations are integers, allowing arithmetic expressions also for categorical symbols.

5 https://github.com/continual-nesy/LTLZinc

5 Methodology

We model the whole sequence classification task by a multistage pipeline composed of the following sub-tasks, also sketched in Fig. 1: (IC) image classification, mapping data from each Xi to the corresponding Yi; (CC) constraint classification, leveraging "relational" knowledge; (NSP) next state prediction, leveraging "temporal" knowledge; (SC) sequence classification, i.e., the binary classification problem. LTLZinc provides annotations for each of these sub-tasks, so that we can evaluate performance both in isolation for each component, and jointly in an end-to-end fashion, while also being able to define multiple training objectives, applied at different stages. We address the following research questions.

• Q1: Can neural-only methods solve the proposed tasks? Given enough training capacity, can a neural network successfully perform sequence classification, without background knowledge?
• Q2: How do neural-only and neuro-symbolic methods compare? Can background knowledge mitigate error amplification issues along multiple stages? Are neuro-symbolic methods more prone to training instability than neural-only approaches?
• Q3: What is the effect of upstream noise on exact symbolic methods? Do wrong, but confident, predictions of symbols yi's affect downstream accuracy more than correct predictions associated with lower confidence? How is noise propagated?
• (IC) Image classification. The first stage corresponds to a traditional neural-based image classification task, estimating the probability of the class assignment [yt0 , . . . , ytN-1 ], i.e., PIC([yt0 , . . . , ytN-1 ] | [xt0 , . . . , xtN-1 ]). Our implementation is based on a convolutional architecture (details in Appendix B.1), for each perceptual domain (e.g., for the example of Section 4, we have two instances of the same architecture: one to predict symbols yA, yB (MNIST categories) and another one for symbols yC (SVHN categories), see Fig. 1).
• (CC) Constraint classification. The set of all the image classes predicted by the IC module, is mapped to |C| validity values, each of them indicated with βi, one for each of the constraints defined in the relational knowledge C. This stage estimates PCC([βt0 , . . . , β t |C|-1 ] | [yt0 , . . . , ytN-1 ]). Our experiments focus on tasks characterized by constraints which can be expressed in Datalog. Hence, we chose Scallop [Li et al., 2023], a neuro-symbolic engine capable of probabilistic reasoning over Datalog programs, supporting inference over multiple provenance semirings [Green et al., 2007]. 6 Scallop programs are differentiable end-to-end, however they do not possess trainable parameters. To increase module flexibility, we augment our architecture with an optional set of additional learnable calibration parameters (enabled by a "calibrate" hyper-parameter in the experiments of Section 6), which independently apply temperature rescaling to both input and output probabilities. Learning takes place jointly with the IC module, and it allows us to control both the entropy of the distributions and the confidence of prediction, while preserving the argmax. We compare Scallop with two fully-learningbased approaches: a small multi-layer perceptron with limited capacity (8 hidden neurons, MLP-S) and a larger one (64 hidden neurons, MLP-L), see Appendix B.2.

(NSP) Next state prediction. The temporal reasoning component is rooted on the definition of a discrete space of M elements, each consisting of a state of the DFA equivalent to F, based on the observed validity values of relational constraints, βt i 's. In this way, temporal reasoning is reduced to to a next-state prediction problem, i.e., a recurrent classification problem where αt ∈ [0,M - 1] is the predicted class/nextstate, with probability PNSP(αt | [βt0 , . . . , β tV-1 ], αt-1 ). 7 We compare four learning-based approaches (two MLP's, namely MLP-S and MLP-L, and two gated recurrent units, GRU-S, GRU-L, with 8 and 64 hidden/state neurons, respectively), and four symbolic approaches. GRUs are augmented with a simple encoder-decoder, to convert the continuous hidden state into M discrete classes. For the symbolic approaches, we encode the ground truth DFA, following [Umili et al., 2023] and [Manginas et al., 2024]. Such automaton is a set of propositional formulas as PREV STATE ∧ TRANS LABEL → NEXT STATE, encoded by logic tensor networks [Badreddine et al., 2022] (here named Fuzzy) and sd-DNNF [Darwiche and Marquis, 2002], respectively. To assess the effect of numerical stability, we performed computations both in probability space and log-probability space (suffixes -P and -LP, respectively). As in the CC module, automata-based NSP's predictions are optionally temperature-calibrated.

6 In initial explorations, the default top-k proofs provenance (k = 1) resulted in the best trade-off between inference time and accuracy.

7 Here and in the following, t = -1 is the initial instant, where the automaton of the NSP module is initialized to state "0".

(SC) Sequence classification. The final output αT-1 of NSP directly encodes the final state of the automaton. Hence, we can perform sequence classification in closed form: PSC(f(S) = 1 | αT-1 ) = ∑ s∈ACCEPTING P(αT-1 = s).

where P t · is the shorthand notation for the already introduced probabilities with arguments at time t. We train our multistage architectures with four loss functions, each weighted by a λ· hyper-parameter. IC and NSP (the latter conditioned on the previous state) exploit a categorical cross-entropy loss, while CC and SC a binary cross-entropy loss. For SC, we also evaluate the semantic loss proposed by [Umili et al., 2023]. Preliminary experiments demonstrated that training diverges due to extremely low initial confidence in image classification,making the optimizer unable to converge, except in very simple tasks. This behavior is well known in the literature [Manhaeve et al., 2021; van Krieken et al., 2024; Maene et al., 2024], and, in this paper, it only affects experiments aimed at investigating Q2, where we bootstrap the IC module with a 5 epochs pre-training phase, using the IC-loss only, to ensure a good starting image classification.

6 Experiments

We hereby present an experimental evaluation conducted on six LTLZinc tasks. 8 Each consists in a binary classification problem on 400 image sequences of variable length (between 10 and 20), with images sampled from MNIST [LeCun, 1998] and Fashion MNIST [Xiao et al., 2017]. Tasks are annotated with relational and temporal knowledge (see Appendix A for all the details). We address research questions of Section 5 with three distinct experimental activities, aimed to study the effect of different architectures and available knowledge. Notice that our goal is not to simply find the best performing model, but to explore different scenarios and gain insights on our challenging setting. Appendices B.4, B.5 and B.6 report values of every hyper-parameter.

Q1. To explore neural-only methods, our modular architecture is instantiated with neural components only (i.e., the convolutional backbone (IC), MLP-S/L for constraint prediction (CC), and MLP-S/L or GRU-S/L for next-state prediction (NSP), Fig. 1). Supervision is provided at every level, weighting each loss by the same positive coefficient (λ· = 1.0). Our expectations were that the neural-only pipeline would have been good in managing the IC stage, but it was not clear how it would have performed in the other ones. Results (detailed in Appendix C) confirmed that, despite their perceptual simplicity, no task can be effectively learned with sequencelevel labels alone. We experienced slow convergence and sub-optimal performance at the end of training. In fact, in spite of good overall image classification, the optimizer is often stuck in local equilibrium points, causing performance for other training objectives to plateau multiple times during training. Harder reasoning tasks exacerbate this effect.

8 LTLZinc generator, our dataset, and code for full reproducibility: https://github.com/continual-nesy/LTLZinc.

Q2. This second experimental batch aims to compare neural vs. neuro-symbolic methods, thus the effect of background knowledge over multiple reasoning steps, as well as the interaction between components. We fix a neural perceptual backbone (IC), and then build four categories by combining either Neural (red, Fig. 1) or Symbolic (green, Fig. 1) modules for constraint prediction (CC) and temporal reasoning (NSP). We will indicate each configuration with a shorthand notation, e.g., Symbolic-Neural means Symbolic CC and Neural NSP modules. The use of the semantic loss and/or of calibration (Section 5), are treated as additional hyperparameters. Training is performed in two steps: 5 pre-training epochs for the IC module, and then 20 epochs of training for the entire architecture. Overall, these experiments confront 96 combinations, across 6 tasks, each seeded 3 times.

Q3. The third batch of experiments focuses on symboliconly methods, thus on the Symbolic-Symbolic (green, Fig. 1) architectures. We exploit probability calibration (Section 5) as the only form of learning, to minimize noise and precisely pinpoint the effect of variables such as upstream label uncertainty, and supervision "distance" from the reasoning component. We also consider replacing IC and CC modules with specific "oracles" returning the ground truth labels, possibly with some level of corruption. In particular, we either replace only IC or both IC and CC. An oracle is characterized by two hyper-parameters: how ground truth is corrupted before feeding the next module, and the amount of corruption in terms of noise probability p. "Flip oracles" return correct labels with probability 1 - p, and random labels with probability p, both with confidence 1.0. "Confidence oracles", on the other hand, always return correct labels with random confidence between 1 - p and 1.0, redistributing the remaining mass to other labels. When p = 0.0, both oracles yield ground truth labels with maximum confidence, referred to as "perfect oracle".

6.1 The Impact of Neuro-Symbolic Approaches

Fig. 2 highlights the trade-offs between CC and NSP, as a function of the different Neural/Symbolic implementations. Exploiting a symbolic component both for CC and NSP (Symbolic-Symbolic, brown points) allows to achieve the best trade-off for every task considered. Unlike other combinations, these approaches consistently outperform naive baselines which always return the most probable class observed in the training set, both for NSP (dashed horizontal line), and CC (not shown, outside the left boundary of plots). The additional learning capacity provided by temperature calibration (dots vs. crosses) has an overall limited effect. With the exception of tasks 1, 2 and 4, neural modules for NSP (clusters Symbolic-MLP/GRU and Neural-MLP/GRU, blue, orange, red and purple) achieve unsatisfactory performance, even when fed from highly-accurate symbolic CC predictions. These architectures, at times, perform on par with the most probable guessing baseline, and often below it. Symbolic modules for NSP are characterized by a large dispersion, due to optimization challenges: this is especially true when exploiting neural CC modules (Neural-Symbolic, green), but it can also be observed in combination with symbolic CC modules (Symbolic-Symbolic, brown). Conversely, neural NSP, even though often showing unsatisfactory performance, is characterized by a much smaller inter-experiment variance. Table 1 summarizes performance for each task. Overall, the Symbolic-Symbolic category dominates over other groups, with the exception of task 5, where it performs slightly worse than the Symbolic-Neural family. When observing constraint accuracy alone, a downstream Symbolic NSP module often negatively affects performance, with task 4 presenting the highest delta between Symbolic-Symbolic and SymbolicNeural. Conversely, when focusing on next state prediction, an upstream Symbolic CC module is beneficial to a downstream Symbolic temporal reasoning module, however this clear-cut performance improvement is flipped when the NSP module is Neural. This behavior hints at complex interactions between CC and NSP modules, where architectural choices bi-directionally affect both components. Other hyperparameters have negligible effect. Early stopping is almost always triggered near the end of training, hinting at a possibly incomplete convergence. Temperature calibration is often selected, but performance improvements are minor (cfr. with Fig. 2), and the semantic loss proposed by [Umili et al., 2023] is not significantly different than traditional binary cross-entropy in our setting. Variances across three runs for each set of hyper-parameters are low. Comparing this observation to Fig. 2 (which, instead, highlights hyper-parameterbased variance), it can be observed that convergence in multistage neuro-symbolic sequence classification is heavily dependent on architectural choices, but relatively unaffected by parameter initialization. Task 3 is an exception and it presents a failure case of the Symbolic-Symbolic family, due to training instability. When able to converge, however, it is the only approach capable of improving over random guessing for sequence classification for this task (we reported this sample result surrounding the model name with brackets).

6.2 The Impact of Oracular Predictors

Fig. 3 shows the effect on an exemplar task (Task 4) of oracular predictors on symbolic temporal reasoning modules. Figures 2, 3 and 4, in the supplementary materials, show the same plots for every task. In general, the trainable temperature parameters are quickly optimized, with curves following a mostly horizontal trend. However, flip oracles (blue, green and purple lines) are characterized both by larger variance and inter-epoch oscillations, compared to confidence oracles (orange, pink and brown), which present a remarkably stable behavior. This effect is present in every task, regardless of reasoning difficulty. Noise injection, however, affects the two oracles differently: performance for flip oracles degrades linearly when increasing noise, while confidence oracles are characterized by non-linear behavior. Small amounts of noise do not affect confidence oracles appreciably, while larger amounts tend to harm performance more than the flip oracle. This effect is more evident for harder reasoning tasks: for instance, in task 4, a noise of p = 0.1 is enough to cause random guessing performance (Fig. 5 in the Appendix). With oracles, the effect of different automata encodings is virtually nonexistent (fuzzy and sd-DNNF markers overlap almost everywhere). IC oracles are consistently more affected by noise, compared to IC/CC ones. This behavior seems counterintuitive, as the Scallop module performs near-exact inference; however, it is in line with the hypothesis of uncertainty accumulation over multiple steps of reasoning. When focusing on constraint performance (Fig. 3 in the supplementary materials), flip oracles tend to have stable performance, while confidence oracles can exploit temperature parameters to achieve a small learning capacity (slight upward trend across epochs). In general, flip oracles are more robust to noise, with confidence oracles achieving unsatisfactory performance (outside plot boundaries, see Fig. 5 in the Appendix) for harder tasks or higher (p > 0.05) degrees of uncertainty. This behavior clashes with the desirable property of predictive confidence correlating with uncertainty, which is one of the advantages of neuro-symbolic AI, compared to (uncalibrated) neural networks. Flip oracles achieving better performance than confidence oracles, for similar levels of noise, hint at the fact that an overconfidently-wrong classifier can be more successful than a reluctantly-correct one, in temporal reasoning settings.

7 Conclusions

We extended knowledge-driven sequence classification to a relational setting, introducing a novel benchmarking framework and baselines for neural-only and multi-stage neurosymbolic methods in a knowledge-driven, and long-temporalhorizon regime. Experiments outline a challenging setting, where neural networks struggle to generalize and state-ofthe-art neuro-symbolic methods fall short when stacked: temporal reasoners extended to a relational domain can fail even with full background knowledge available, and generalpurpose first-order reasoners suffer from training instabilities in recurrent settings. We argue that the proposed benchmarking framework can benefit the neuro-symbolic and temporal reasoning communities, further pushing research boundaries towards more expressive frameworks, tighter neuro-symbolic integration, and more robust time-driven approaches.

Acknowledgements

M.L. was supported by CAI4DSA actions (Collaborative Explainable neuro-symbolic AI for Decision Support Assistant), PARTENARIATO ESTESO "Future Artificial Intelligence Research - FAIR", SPOKE 1 "Human-Centered AI" Universit`a di Pisa, CUP B13C23005640006. The scholarship by L.S.L. was funded by the Italian Ministry of University and Research (DM 351/2022, PNRR). S.M. was supported by the University of Siena (Piano per lo Sviluppo della Ricerca - PSR 2024, F-NEW FRONTIERS 2024), under the project "TIme-driveN StatEful Lifelong Learning" (TINSELL) and also by the project "CONSTR: a COllectionless-based NeuroSymbolic Theory for learning and Reasoning", PARTENARIATO ESTESO "Future Artificial Intelligence Research - FAIR", SPOKE 1 "Human-Centered AI" Universit`a di Pisa, "NextGenerationEU", CUP I53C22001380006. L.S.L. scholarship was funded by the Italian Ministry of University and Research (DM 351/2022, PNRR). We kindly thank Luc De Raedt and Nikolaos Manginas for their insightful comments.