PaperlayerView exact revision on arXiv

Source-linked AI summary

STAIR: Semantic-Temporal Automaton for Interpretable Reasoning in Temporal Question Answering

Xinlong Dai, Jinchuan Zhang, Lei Gao, Xinzhe Hu, Yuefeng He, Hui Gao

arXiv:2608.16224v1cs.CLcs.AI

TL;DR

Temporal question answering requires flexible interpretation alongside exact temporal selection, a gap in prompt-based systems that rely on LLMs for both. STAIR separates semantic adaptation from deterministic execution and consistently improves over the NeSTR baseline across evaluated benchmarks and models.

  • Problem

    Temporal questions require boundary- and order-sensitive operations, while existing prompt-based systems use LLMs for semantic interpretation and exact temporal inference.

    Source: Introduction · p. 1

  • Method

    STAIR uses a rule-first architecture: an answer-free adapter maps difficult questions to executable intents, which a deterministic temporal automaton applies to canonicalized evidence.

    Source: Introduction · p. 2

  • Results

    STAIR consistently improves over the NeSTR baseline across four TQA benchmarks and the operator-supported CronQuestions subset, with gains on non-exact intervals, point-time containment, and time-anchored before/after queries.

    Source: Conclusion · p. 7

  • Takeaways & Limitations

    For automaton-resolved instances, STAIR exposes the actual computation through canonical facts, normalized intent, policy, guard outcomes, selected evidence, and answer provenance.

    Source: Introduction · p. 2

    STAIR requires canonical facts, a finite temporal intent, and directly extractable answers; it does not support phenomena such as negation, duration comparisons, or multi-hop temporal composition.

    Source: Diagnostic Analysis · p. 7

Abstract

from arXiv · show

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 \textbf{S}emantic-\textbf{T}emporal \textbf{A}utomaton for \textbf{I}nterpretable \textbf{R}easoning. 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.

Introduction

STAIR addresses temporal question answering by separating semantic normalization from deterministic temporal execution. Its rule-first design reserves LLM use for questions that cannot be mapped directly to executable intents, while making temporal decisions explicit and verifiable.

Introduction

  • Temporal questions demand boundary-sensitive interval and point-containment reasoning, order-sensitive predecessor or successor selection, and both for time-anchored before/after queries.LLMs may select an incorrect adjacent state, while strict rule matching fails when query and fact boundaries do not align.Source: Introduction · p. 1
  • Rule-only STAIR resolves 76.91% of TimeQA-Easy, 76.91% of TempReason-L2, and 91.46% of TempReason-L3, but only 27.65% of TimeQA-Hard.The lower TimeQA-Hard coverage reflects non-exact intervals, time-valued anchors, and formulations that do not directly expose an executable operator.Source: Figure 2 · p. 2, Introduction · p. 2
  • Prompting methods including NeSTR (Liang et al. 2026) and TISER (Bazaga et al. 2025) still leave decisive temporal operations and answer generation to free-form LLM output.This can yield incorrect interval boundaries, over-retrieved before/after states, or altered answer spans despite coherent reasoning traces.Source: Introduction · p. 2
  • STAIR canonicalizes facts and uses finite executable intents, explicit policies, finite control, and guarded transitions; an answer-free adapter supplies intents when rule parsing fails.Programmatic validation and constrained repair ensure adapter outputs are executable, while the automaton compares times, selects evidence, and extracts answers.Source: Introduction · p. 2
  • STAIR exposes canonical facts, normalized intents, policies, guard outcomes, selected evidence, and answer provenance as procedural interpretability.It also records rule-path failures, semantic repairs, and final-fallback invocations; evaluation spans TimeQA, TempReason, and CronQuestions, with ablations and rule-coverage diagnostics.Source: Introduction · p. 2

Related Work

Related work spans temporal question-answering benchmarks, learned and prompted TQA systems, inference-time and neuro-symbolic reasoning, and programmatic execution. STAIR distinguishes itself by limiting LLMs to semantic normalization and using an explicit temporal executor for final operations.

TQA Benchmarks and Prior Systems

  • Temporal QA benchmarks progress from TempQuestions, TimeQA, and TempReason to newer tests of event ordering, interval reasoning, and temporal generalization.TempEval instead targets temporal relations between events and time expressions.Source: Related Work · p. 2
  • Prior TQA systems use stronger reading-comprehension models, temporal pretraining, structured knowledge, prompting, or programmatic reasoning, but may require adaptation, graph construction, or LLM-mediated inference.STAIR instead targets zero-shot TQA with an explicit temporal executor.Source: Related Work · pp. 2–3

Inference-Time and Neuro-Symbolic Reasoning

  • Inference-time methods use rationales, sampled paths, search, actions, or feedback; TISER and NeSTR organize temporal reasoning, but LLMs still apply relations and produce answers.STAIR restricts the LLM to semantic normalization and executes the final temporal operation programmatically, addressing the risk of incorrect interval boundaries or ordered states.Source: Related Work · p. 3

Programmatic Execution and Cognitive Perspectives

  • Program-aided language modeling, dual-process reasoning, cognitive offloading, and classical interval formalisms motivate STAIR’s constrained semantic interface and explicit temporal executor.The cited foundations include Gao et al. 2023, Kahneman 2011, Risko and Gilbert 2016, and Allen 1983.Source: Related Work · p. 3

Method

STAIR separates question interpretation from deterministic temporal execution: it builds canonical facts, attempts rule-only inference first, and invokes semantic adaptation or an LLM fallback only when needed. Its guarded automaton makes evidence selection auditable and emits answers directly from selected object spans.

Method

  • Rule-first execution handles recognizable temporal operators without an LLM, routing failures to semantic adaptation and then a four-stage fallback only if deterministic reselection still fails.A successful deterministic result cannot be overridden by the LLM.Source: Method · p. 3

Canonical Fact Construction

  • Canonical facts use normalized (s, r, o, ts, te) tuples, combining rule-based and constrained LLM parsing while preserving provenance and rejecting incomplete records.Facts with the same normalized key are merged, retaining provenance so selected evidence can be traced to its source.Source: Canonical Fact Construction · p. 3

Hard-Structure Detector and Semantic Interface

  • After rule-only failure, the detector routes non-exact intervals, time-valued anchors, unresolved dates, and unparsed questions to an answer-free adapter that proposes a validated temporal intent.Validation canonicalizes aliases and dates and rejects unsupported intents, missing arguments, invalid dates, and answer-like content; repaired outputs must also pass validation.Source: Hard-Structure Detector and Semantic… · p. 3

Temporal Automaton Selector

  • The guarded finite-state automaton audits each execution, applying point-time containment and selecting nearest predecessor or successor states for before/after queries.Failed guards return typed reasons for repair; the state chain also supports earliest/latest selection and time-valued anchors.Source: Temporal Automaton Selector · pp. 4–5

Direct Answer Emission and Fallback

  • At successful termination, STAIR copies answers from selected object spans; only after repair and deterministic reselection fail does the final LLM path generate answers for cases beyond the policy inventory.The fallback uses separate stages for symbolic representation, temporal inference, consistency checking, and reflection/final answer generation.Source: Method · p. 3, Direct Answer Emission and Fallback · p. 5

Experiments

STAIR achieves the highest average EM and F1 across the four temporal benchmarks, with results showing gains over NeSTR, benefits from semantic adaptation, and transfer to a converted CronQuestions subset. Efficiency varies by query structure: STAIR reduces computation on three benchmarks but requires more on TimeQA-Hard.

Experimental Setup

  • STAIR is evaluated on complete TimeQA-Easy, TimeQA-Hard, TempReason-L2, and TempReason-L3 test sets, using Qwen2.5-7B, Qwen3-8B, Qwen3-14B, and GPT-4o-mini.The primary comparison is NeSTR under matched model and benchmark settings; CronQuestions transfer uses an operator-supported subset.Source: Experimental Setup · p. 5

Main Results

  • 9.48 F1 points on TempReason-L2 and 9.62 on TempReason-L3 exceed gains of 1.89 on TimeQA-Easy and 3.08 on TimeQA-Hard.The larger gains align with point-time containment and entity-anchored before/after queries, while TimeQA-Hard requires semantic normalization for non-exact intervals and time-anchored queries. EM gains generally exceed F1 gains, although on TimeQA-Hard with Qwen3-14B, EM rises from 82.20 to 84.18 while F1 falls from 87.30 to 86.59.Source: Main Results · p. 5
  • Against NeSTR, average F1 gains span 2.78 points (GPT-4o-mini) to 12.71 points (Qwen2.5-7B), with EM gains spanning 5.96–17.08 points.STAIR has the highest average EM and F1 across evaluated models, improving EM in all 16 model-dataset configurations and F1 in 15; its average F1 varies by 3.07 points across models versus 13 points for NeSTR.Source: Main Results · p. 5, Table 1 · p. 6

Component-level Ablation

  • On TimeQA-Hard, the semantic adapter raises F1 from 72.75 to 80.91 while reducing the final fallback rate from 72.35% to 37%.The hard-structure detector alone provides little benefit; validation and repair add modest accuracy while preventing malformed intents. Policy ablations show max-overlap supports evidence selection, time-anchor typing supports deterministic execution, and the 4-stage fallback provides coverage beyond current policies.Source: Component-level Ablation · pp. 5–6, Table 2 · p. 6

Cross-source Transfer Assessment

  • 16.42 EM points and 6.60 F1 points separate STAIR from NeSTR on the converted, operator-supported CronQuestions subset.The shared evaluation subset contains 13,096 instances; the result supports transfer to that subset, not the full test split or unseen temporal operators.Source: Table 3 · p. 6, Cross-source Transfer Assessment · p. 6

Efficiency and Fallback Analysis

  • 0.21 average calls and 0.31s on TempReason-L3, down from 1 call and 3.90s, mark STAIR’s largest efficiency reduction.On TimeQA-Hard, calls rise from 1 to 2.12 and time from 3.13s to 3.61s as adaptation and repair add computation for difficult inputs.Source: Efficiency and Fallback Analysis · pp. 6–7, Table 4 · p. 7

Diagnostic Analysis

STAIR’s diagnostic analysis shows gains across boundary-sensitive and time-anchored query categories, while identifying limits imposed by its canonical-fact and finite-policy design. LLM fallback expands query coverage but loses the procedural interpretability of guarded execution.

Category-level Question Structure

  • The four diagnostic categories pair interval overlap or point containment with predecessor or successor selection for time-anchored before/after questions.Non-exact intervals and point-time questions test boundary-sensitive reasoning; time-anchored queries combine boundary-sensitive anchor interpretation with order-sensitive selection.Source: Diagnostic Analysis · p. 7

Error Analysis

  • Residual errors stem from non-canonicalizable contexts, ambiguous interval boundaries, invalid adapter outputs, and queries requiring operators outside STAIR’s predefined policy inventory.Unsupported phenomena include implicit event ordering, duration comparisons, negation, nested constraints, and multi-hop temporal composition; such cases may be rejected or routed to LLM fallback if repair fails.Source: Diagnostic Analysis · p. 7

Category-level Question Structure

  • STAIR gains 8.19 F1 points on non-exact intervals and 9.28 on point-time queries, plus 6.92 on before and 4.56 on after time-anchored queries.Non-exact intervals rely strongly on semantic adaptation, while point-time questions are handled without adapter intervention. Time-anchor after questions have a substantially higher fallback rate, indicating more frequent gaps in the semantic interface and policy inventory.Source: Table 5 · p. 7, Diagnostic Analysis · p. 7

Error Analysis

  • LLM fallback broadens query coverage but lacks the guard-level execution traces of the deterministic TAS module, reducing procedural interpretability.STAIR’s deterministic design depends on canonical facts, finite temporal intents, and directly extractable answers.Source: Diagnostic Analysis · p. 7

Conclusion … D CronQuestions Conversion and Evaluation Protocol

STAIR separates answer-free semantic interpretation from deterministic temporal execution, and experiments report consistent gains over NeSTR across benchmarks and model types. The appendices formalize its guarded policies, adapter contract, and CronQuestions conversion protocol.

Conclusion

  • STAIR consistently improves over NeSTR across four TQA benchmarks and CronQuestions’ operator-supported subset, with gains on boundary- and order-sensitive categories.The conclusion attributes improvements to semantic adaptation, time-anchor typing, guarded policies, and deterministic answer emission.Source: Conclusion · p. 7

A Formal Definition of the Temporal Automaton

  • TAS operates over validated canonical facts with normalized, ordered time boundaries, and confines deterministic before/after selection to a target subject–relation chain.Provenance is retained for auditing but is not read by transition rules.Source: A Formal Definition of the Temporal… · p. 10, §A.1 · p. 10

A.2 Intent Space

  • The intent interface represents interval, point, and before/after queries with typed temporal arguments and policies; validation rejects unsupported, ill-typed, or answer-like adapter outputs.The semantic adapter and deterministic query grammar target the same intent space, so the adapter proposes an interface rather than selecting evidence or answers.Source: §A.2 · p. 10

A.3 Automaton Definition

  • TAS is a guarded finite-state automaton that advances from raw input through canonical facts, validated intent, local-chain selection, and answer emission; failed guards record typed failure.When selection yields no answer or multiple distinct normalized spans where one answer is required, execution fails rather than letting an LLM resolve ambiguity implicitly.Source: §A.3 · p. 11, §A.4 · p. 11

B Temporal Policy Details

  • TAS maps intents to deterministic policies: intervals try exact boundaries before positive-overlap selection, before/after default to nearest neighbors, and point, first, and last queries use defined selection rules.Before/after policies also support all-previous or all-following variants; point queries default to ambiguity when multiple distinct answers are selected, with options for all overlaps or latest start.Source: §B.1 · p. 12, §B.2 · p. 12

B.3 Time Normalization and Closed-Interval Comparison

  • Time keys normalize years, month-years, and full dates; temporal comparisons use closed endpoints, and only positive-overlap facts qualify for max-overlap selection.Unparseable fact boundaries are filtered or routed to failure.Source: §B.3 · p. 12

B.4 Pre-Transform and Fallback Transform Corrections

  • For hard temporal structures, transformations rewrite intents and policy descriptors—such as month-year intervals, multiple point matches, or date-anchor types—while leaving final selection to TAS.The fallback transform returns repaired intents to TAS when possible; only failed repair and reselection lead to the final LLM fallback.Source: §B.4 · pp. 12–13

C Semantic Adapter Schema

  • The semantic adapter emits answer-free JSON for hard temporal questions; validation checks supported intent structure and temporal arguments before passing intents to TAS for symbolic comparison and answer aggregation.Answer-like fields are outside the adapter schema and rejected; the adapter cannot select evidence or instantiate the answer buffer.Source: §C.1 · p. 13, §C.2 · pp. 14–15

D.1 Source Data and Temporal KG … D.5 Answer Construction

The appendix specifies how CronQuestions data are converted into temporal contexts, which question types can be processed, and how inverse queries and gold answers are handled. It also identifies missing-head cases and limits on inverse-query support.

D.1 Source Data and Temporal KG

  • The official CronQuestions test split contains 30,000 questions, and its KG contains 328,635 temporal facts, 125,726 entity labels, and 203 relation labels.Facts are interpreted as (subject, relation, object, [start, end]); QIDs and PIDs are mapped to natural-language labels before TAS context construction.Source: §D.1 · p. 15

D.2 Supported Question Types and Filtering

  • Under current TAS mode, only entity-answer questions of type simple entity, first last, or before after pass the type filter; 2,596 supported but unconverted questions are assigned to missing head.Missing head means annotation.head is absent, preventing retrieval of forward timelines by (head, relation); this is not a post-hoc filter for answer availability, missing facts or labels, or manual cleaning.Source: §D.2 · p. 15

D.3 Temporal Context Construction

  • For standard forward items, the converter retrieves all KG facts matching the head and relation, maps IDs to labels, sorts facts by time, and groups facts sharing boundaries, subject, and relation.Point-time facts use identical start and end boundaries.Source: §D.3 · p. 15
  • The materialized temporal context is a string of timeline lines formatted as “start - end : subject's relation is ( object )”; question text uses paraphrases[0] when available.Source: §D.3 · p. 15

D.4 Inverse and Before/After Queries

  • For P39 before/after questions with holder-style cues, the converter retrieves facts by relation and tail and reverses them, enabling adjacency-based policies to return the person entity.A general inverse construction for all simple entity and first last questions is not implemented, leaving some inverse items in the missing head bucket.Source: §D.4 · p. 15

D.5 Answer Construction

  • Gold answers are mapped from Wikidata IDs to labels, but the converter does not require them to appear in the constructed context; when matched facts cannot supply expected answer IDs, it retains the original IDs and writes the sample.Thus, converted-subset selection does not depend on checking whether the answer occurs in context.Source: §D.5 · p. 15

D.6 Shared Evaluation Protocol · D.7 Scope and Limitations

D.6 establishes a shared, converter-based evaluation protocol for NeSTR and STAIR; D.7 limits the evaluation to operator-supported, successfully converted CronQuestions examples rather than the complete test set.

D.6 Shared Evaluation Protocol

  • NeSTR and STAIR use the same materialized JSONL data, including identical questions, answers, contexts, sample order, prompts, and metrics, avoiding method-specific conversion or ordering differences.The shared file also contains identical question IDs.Source: §D.6 · p. 15
  • Table 7 describes deterministic filtering stages for the CronQuestions test split.Source: Table 7 · p. 16
  • Table 8 breaks down type-supported questions skipped because annotation.head is absent.Source: Table 8 · p. 16
  • The converter produces the retained and skipped counts without manual annotation.Source: §D.6 · p. 16

D.7 Scope and Limitations

  • The evaluation is not a complete CronQuestions test-set evaluation; it covers only the operator-supported and successfully converted subset.Source: §D.7 · p. 16
  • Time-answer questions, time join, unsupported operators, and general inverse timelines remain outside the evaluation’s current scope.Source: §D.7 · p. 16

E Additional Main Result Details

Table 9 presents reproduced baseline results alongside three-run STAIR statistics in the main result table’s layout, with reproduced NeSTR results serving as a consistency check.

  • Table 9 aligns reproduced baseline results and three-run STAIR statistics with the main result table’s layout, and reproduces NeSTR (repr.) under the pipeline as a consistency check.Source: E Additional Main Result Details · p. 16

F Full Experimental Configuration … H.2 Hard Non-Exact Interval Match

The experimental appendices document shared runtime settings and prompt templates, then illustrate rule-based exact-interval matching and semantic adaptation for a month-level query over year-level evidence.

F Full Experimental Configuration

F.1 Shared Settings

G Prompt Templates

  • The prompt-only baseline uses one NeSTR-style prompt, while STAIR reserves the same prompt family as a four-call fallback after TAS and validated semantic repair fail.The fallback separates symbolic representation, constrained inference, consistency checking, and final reflection and answer emission.Source: G Prompt Templates · p. 16
  • Prompts preserve entity spelling, accents, and encoding; adapter prompts remain answer-free, and only the residual fallback may emit a final answer.Source: G Prompt Templates · p. 16

H Case Study

  • The case study presents compact TAS traces to illustrate its behavior and one boundary limitation, rather than adding quantitative analysis.Source: H Case Study · p. 16

H.1 Regular Interval Match

  • For the 1985–1989 question, TAS parses an exact-interval intent, selects both facts with matching boundaries, and emits the gold answer without LLM temporal inference.The answer is Port F.C and Thailand national football team.Source: §H.1 · p. 16

H.2 Hard Non-Exact Interval Match

  • For a month-level July–September 1997 query against year-level facts, the semantic adapter only rewrites the temporal interface; TAS applies overlap selection, retaining 1997–1998 and returning Conservatives.Source: §H.2 · p. 17

H.3 Year-Boundary Ambiguity

STAIR’s selector can make a deterministic but incorrect choice when a month-level query falls on a year-level boundary. The proposed extension would retain both adjacent candidates for finer-grained resolution.

H.3 Year-Boundary Ambiguity

  • For Oliver Bulleid’s Feb 1908 employer query, TAS returns Great Northern Railway although the gold answer is Westinghouse Electric Corporation.The temporal context places the employer change at the shared 1908 boundary.Source: §H.3 · pp. 17–18
  • Because facts give year-level boundaries but the question asks for a month-level point, TAS maps Feb 1908 to the preceding interval, excluding adjacent 1908–1912 although the gold annotation treats it as valid.The intent is point(time = Feb 1908, policy = single_or_ambiguous).Source: §H.3 · p. 18
  • A boundary-uncertain state could retain both adjacent candidates when a month-level query falls on a shared year boundary, then resolve ambiguity with a finer-grained rule or validated semantic normalizer.Source: §H.3 · p. 18

I Executor Ablation Details

Executor-local ablations show that deterministic answer construction and before/after adjacency are more consequential than the fact-source choice. Removing answer construction causes measurable F1 declines, while adjacency preserves ordered predecessor/successor constraints.

I Executor Ablation Details

  • Removing deterministic answer construction decreases F1 by 4.47 points for GPT-4o-mini and 12.54 points for Qwen2.5-7B.Table 11 isolates STAIR-Core executor design choices, omitting the hard detector and semantic adapter.Source: I Executor Ablation Details · p. 18, Table 11 · p. 18
  • Removing before/after adjacency causes a substantial decline, whereas changing the fact source has a smaller effect.The results indicate that deterministic selection and direct answer emission drive the executor’s main gains.Source: I Executor Ablation Details · p. 18
  • Without direct answer construction, generative verbalization can introduce avoidable aggregation errors; without adjacency, entity-anchored questions lose the ordered-chain constraint.The constraint distinguishes a predecessor or successor from any temporally compatible fact.Source: I Executor Ablation Details · p. 18
  • Fact-source variants show that deterministic policy is decisive once an admissible local chain is available.Source: I Executor Ablation Details · p. 18

Related papers

Loading 2608.16224v1…