By leveraging large-scale pretraining, LLMs can interpret diverse temporal expressions and question formulations without task-specific training. However, existing prompt-based neuro-symbolic systems continue to rely on LLMs for both semantic interpretation and exact temporal inference. Consequently, discrete decisions regarding intervals, time anchors, and ordered states remain vulnerable to probabilistic errors and difficult to verify. We present STAIR, a Semantic-Temporal Automaton for Interpretable Reasoning. STAIR separates semantic interpretation from precise temporal inference: an answer-free LLM adapter maps complex question formulations to normalized temporal intents, while a deterministic temporal automaton with finite control and guarded transitions executes the corresponding policies over canonicalized evidence. Following a rule-first design, STAIR resolves standard questions without invoking an LLM and applies semantic adaptation only when the rule path fails to produce an executable intent. This approach reduces free-form reasoning, making temporal decisions verifiable and interpretable. Specifically, guarded execution supports precise point-time containment and before/after selection, while semantic adaptation handles non-exact intervals and time-anchored queries. Across the TimeQA-Easy, TimeQA-Hard, TempReason-L2, and TempReason-L3 datasets, STAIR consistently outperforms strong baselines in the TQA task using matched model settings, achieving average F1 improvements of 16.57% and 3.10% when utilizing the Qwen2.5-7B and GPT-4o-mini models, respectively. Furthermore, ablations and diagnostic analyses demonstrate that STAIR excels at handling both boundary-sensitive and order-sensitive queries, while its guarded execution and semantic adaptation ensure precise point-time reasoning and inexact intervals, respectively.
Figures & tables
Figure 1: TQA setting that motivates STAIR. Semantic parsing normalizes diverse temporal question forms, whereas deterministic execution performs temporal selection.
Figure 2: Routing analysis of the rule-only temporal automaton across benchmarks. Each bar decomposes the dataset into examples deterministically resolved by rule-only automaton of STAIR and examples requiring LLM intervention.
Figure 3: Overview of STAIR. The system first attempts rule-only execution. Difficult cases undergo semantic adaptation and validation before the Temporal Automaton Selector performs guarded temporal reasoning over canonical facts and exposes the activated policy, selected evidence, and emitted answer.
Model
Strategy
TimeQA-Easy
TimeQA-Hard
TempReason-L2
TempReason-L3
Avg
EM
F1
EM
F1
EM
F1
EM
F1
EM
F1
Open LLMs
Qwen2.5-7B
TISER
86.80
92.60
64.30
71.50
61.10
69.80
72.60
77.60
71.20
77.90
NeSTR
85.10
90.20
64.80
71.20
61.50
68.60
73.10
76.70
71.10
76.70
STAIR
93.27
94.25
76.94
80.91
87.61
87.72
94.90
94.77
88.18
89.41
Qwen3-8B
TISER
88.80
93.40
77.10
82.50
73.70
78.40
84.30
87.50
80.90
85.40
NeSTR
89.50
94.20
77.70
83.40
79.20
83.50
84.90
87.20
82.80
87.10
Table 1: Exact Match (EM) and token-level F1 results on four temporal reasoning benchmarks under matched model settings.All four benchmarks are evaluated on their complete test sets. NeSTR and TISER values are taken from prior work, while STAIR values are averaged over three independent runs. Boldface indicates the best result for each model and metric.
Variant
EM
F1
Adapter
Fallback (%)
STAIR-Core
68.06
72.62
–
72.35
+ hard detector
68.29
72.75
–
72.35
+ semantic adapter
74.95
80.91
35.35
37.00
+ validation/repair
75.11
81.12
35.48
36.87
STAIR complete
77.16
81.20
43.73
20.50
w/o max-overlap
74.01
80.26
43.53
20.89
Table 2: Interface ablation on TimeQA-Hard with Qwen2.5-7B. Fallback denotes the final 4-stage LLM fallback rate.
Method
Samples
EM
F1
NeSTR
13,096
72.00
81.03
STAIR
13,096
88.42
87.63
Improvement
–
+16.42
+6.60
Table 3: Cross-source transfer results on the operator-supported CronQuestions subset. All model configurations are evaluated over three independent runs.
Dataset
System
Calls
Input tok.
Output tok.
Time
TimeQA-Easy
NeSTR
1.00
548.0
288.1
2.66s
STAIR
0.64
256.0
52.9
0.82s
TimeQA-Hard
NeSTR
1.00
543.8
351.5
3.13s
STAIR
2.12
929.3
282.0
3.61s
TempReason-L2
NeSTR
1.00
689.6
462.2
3.98s
STAIR
0.89
545.8
100.4
1.44s
Table 4: Efficiency comparison between the NeSTR baseline and STAIR. Calls and token counts are reported per instance. Results from a single run of Qwen2.5-7B-Instruct.
(a) Performance by temporal category
Category
Property
n
NeSTR
STAIR
Δ
EM
F1
EM
F1
EM
F1
Non-exact interval
B
1285
68.53
75.02
78.60
83.21
+10.06
+8.20
Point-time
B
1411
62.37
69.26
74.34
78.54
+11.98
+9.28
Time-anchor before
B+O
248
76.88
80.57
87.50
87.49
+10.62
+6.93
Time-anchor after
B+O
134
65.17
73.61
73.88
78.17
+8.71
+4.56
Table 5: Single-run category-level diagnostics on TimeQA-Hard using Qwen2.5-7B-Instruct. B denotes boundary-sensitive, whereas B+O denotes both boundary-sensitive and order-sensitive. Δ is calculated as STAIR minus NeSTR.
Temporal question answering determines what happened, or what was true, at particular times by reasoning over events, intervals, and changing evidence.
Temporal Knowledge Graph Question Answering (TKGQA) is challenging because it requires multi-hop reasoning under complex temporal constraints. Recent LLM-based approaches have improved semantic modeling for this task, but many still rely on fixed reasoning workflows or costly post-training, which can limit adaptability and make error recovery difficult. We show that enabling an off-the-shelf Large Language Model (LLM) to determine its next action is already effective in a zero-shot setting. Based on this insight, we propose AT2QA, an Autonomous and Training-free Agent for TKG Question Answering. AT2QA empowers the LLM to iteratively interact with the TKG via a generic search tool, inherently enabling autonomous exploration and dynamic self-correction during reasoning. To further elicit the LLM's potential for complex temporal reasoning, we introduce a training-free experience mining mechanism that distills a compact few-shot demonstration library from successful self-generated trajectories. AT2QA also yields a transparent audit trail for every prediction. Experiments on three challenging benchmarks -- MultiTQ, Timeline-CronQuestion, and Timeline-ICEWS-Actor -- show that AT2QA achieves new state-of-the-art performance, surpassing the strongest baselines by 10.7, 4.9, and 11.2 absolute points, respectively. Our code is available at https://github.com/AT2QA-Official-Code/AT2QA-Official-Code
Xufei Lv, Jiahui Yang, Haoyuan Sun +5
Tsinghua University · National University of Defense Technology
Retrieval-Augmented Generation (RAG) has shown strong effectiveness in grounding Large Language Models (LLMs) with external knowledge. However, existing RAG and Graph RAG frameworks largely treat knowledge as static or associate time with coarse-grained timestamps or metadata, failing to capture rich temporal structures such as duration, overlap, and containment. We propose IA-RAG, a hierarchical temporal RAG framework that models knowledge as time intervals and performs retrieval under formal temporal constraints. IA-RAG represents facts as Interval Event Units (IEUs) and organizes them into a hierarchical Thematic Forest, where temporal dependencies are governed by Allen's Interval Algebra. To handle incomplete or uncertain temporal boundaries, IA-RAG further introduces a Sub-graph Time Tightening mechanism that refines fuzzy intervals through logical constraints within connected event subgraphs. In addition, IA-RAG supports implicit temporal semantic retrieval through interval-algebra-guided traversal. Experiments on multiple temporal question answering benchmarks, including TimeQA, TempReason, and ComplexTR, demonstrate that IA-RAG achieves strong temporal retrieval and reasoning performance, particularly on complex compositional temporal reasoning tasks. Our code is released at https://github.com/xiaoAugenstern/LogicalRAG_TemporalQA.
Xiaoman Wang, Yaoze Zhang, Wenzhuo Fan +7
East China Normal University · Shanghai Artificial Intelligence Laboratory · University of Shanghai for Science and Technology +1
Despite significant advances, large language models (LLMs) continue to exhibit brittle performance on complex temporal reasoning tasks. This failure mode is widely attributed to inherent deficits in autoregressive logical deduction. In this paper, we challenge this prevailing narrative, demonstrating that temporal reasoning is not the fundamental bottleneck; rather, the locus of failure lies in unstructured text-to-event representation. We introduce a novel neuro-symbolic question-answering framework governed by a Probabilistic Inconsistency Signal (PIS) that explicitly isolates perceptual errors from reasoning failures. By lifting unstructured text into explicit event graphs and interval constraints, our architecture strictly decouples semantic extraction from a symbolic reasoning engine. To robustly detect structural breaks, the PIS elegantly unifies symbolic credal intervals with epistemic neural uncertainty extracted via Evidential Deep Learning on LLM hidden states. Empirical evaluations reveal a striking paradigm shift: when provided with correct structural representations, our system's explicit proof traces achieve perfect 1.0 accuracy (4000/4000) and strictly zero false positives/negatives on temporal arithmetic benchmarks. On broader, noise-injected QA settings, the framework maintains a competitive 75.1% accuracy while enabling deterministic, step-level failure localization. Ultimately, by isolating the representation bottleneck from the reasoning substrate, this work reframes temporal QA from an algorithmic reasoning challenge to a structural alignment problem, charting a verifiable path forward for reliable neuro-symbolic AI.
Tran Quang Liem
Mathematics · VNUHCM - HIGH SCHOOL FOR THE GIFTED · Ho Chi Minh City, Vietnam