SCoP: Structured Constraint Parsing for Evidence-Space Control in Temporal Knowledge Graph Question Answering

Xiaokun Guo; Zhen Xu; Dongdong Huo; Yanqiu Zhang; Dongjin Yu; Yu Wang

cs.CLSep 2, 2026

SCoP: Structured Constraint Parsing for Evidence-Space Control in Temporal Knowledge Graph Question Answering

Authors: Xiaokun Guo, Zhen Xu, Dongdong Huo, Yanqiu Zhang, Dongjin Yu, Yu Wang

Organizations: Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China · School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

Temporal Knowledge Graph Question Answering (TKGQA) requires answer inference from evidence that is both structurally valid and temporally admissible. Existing methods often leave anchor-event binding, temporal admissibility, and ordinal selection implicit in model reasoning, task-specific training, or similarity-driven retrieval, allowing locally relevant but invalid facts to enter the answer context. We formulate complex TKGQA as evidence-space control and propose SCoP (Structured Constraint Parsing), a constraint-centric framework that externalizes temporal decisions before answer inference. Instead of treating retrieved facts as admissible evidence by default, SCoP separates answer-seeking event patterns from temporal anchor events, conservatively grounds them to canonical TKG entities and relations, and translates temporal intent into executable constraints with optional ranking requirements. These constraints operate over normalized point and interval ranges, enabling deterministic filtering of structurally compatible candidates and producing a compact evidence space for generation. Experiments on MultiTQ and TimelineCronQ-R assess SCoP across timestamped point-fact and interval-oriented settings with richer temporal relations and ordering dependencies. Without task-specific parameter updates, SCoP achieves 0.825 Hits@1 on MultiTQ and 0.761 Hits@1 on TimelineCronQ-R, with gains on constraint-intensive question types. These results support explicit evidence-space control over unconstrained retrieval or implicit temporal reasoning.

Figures & tables

Figure 1. Two failure modes in TKGQA caused by implicit temporal constraints: model-internal decision errors and similarity-induced noisy evidence. Two-panel illustration using a temporal question about negotiations with Ali Jafari. The upper panel contrasts a constraint-aware reasoning path that identifies an anchor event, filters candidate events by the before relation, and selects the latest valid event with an unconstrained reasoning path that focuses on local entity relevance and returns an invalid result. The lower panel shows similarity-based top-k retrieval containing one valid candidate together with several candidates that occur after the anchor or fail the required ordering condition.

Figure 2. Overview of the SCoP framework. SCoP consists of one offline retrieval-store preparation stage, three query-time evidence-control stages, and a final answer inference stage: (I) Temporal Graph and Retrieval Store Preparation; (II) Event Triple Identification, which extracts anchor triples and an optional search triple; (III) Conservative Graph Alignment, which grounds extracted triples to canonical TKG elements; (IV) Constraint-guided Evidence Construction, which retrieves structurally compatible facts and filters them using parsed temporal constraints and ranking requirements; and (V) Answer Inference over the constrained evidence space. Pipeline diagram of SCoP with five stages. An offline temporal knowledge graph and retrieval store provide entities, relations, and timestamps. At query time, a sample question is decomposed into two anchor triples and one search triple, which are conservatively aligned to canonical graph entities and relations. Temporal constraints and a ranking requirement are then parsed and applied to structurally compatible candidate triples. The filtered and ranked evidence is finally supplied to the answer inference stage.

Field	Values	Meaning
$\alpha$	event / explicit_time / explicit_interval	Type of temporal reference used to resolve the constraint.
$\omega$	before / after / equal / inside / overlap	Temporal operator for comparing candidate and reference times.
$\eta$	anchor index / time text / interval pair	Concrete reference content used during constraint execution.
$g$	day / month / year / $\varnothing$	Granularity for equal .
$\delta$	positive days / $\varnothing$	Day offset for relative time.
$\rho$	$(\text{asc},k)$ , $(\text{desc},k)$ , or $\varnothing$	Post-filter ordinal ranking.

Table 1. Structured temporal constraint and ranking schema.

Dataset	Knowledge Graph				Question-Answer
Dataset	Fact	Ent.	Rel.	Time.	Train	Val	Test
MultiTQ	461,329	10,488	251	4,017	386,787	57,979	54,584
TCronQ-R	328,635	122,569	203	12,191	16,639	2,080	2,080

Table 2. Statistics of KGs and QA datasets. TCronQ-R denotes TimelineCronQ-R.

TKG Embedding-based Methods
Method	Overall	Question Type		Answer Type
Method	Overall	Single	Multiple	Entity	Time
EmbedKGQA	0.206	0.235	0.134	0.290	0.001
CronKGQA	0.279	0.337	0.134	0.328	0.156
MultiQA	0.293	0.347	0.159	0.349	0.157
Fine-tuning-based LLM Methods

Table 3. Performance comparison on the MultiTQ dataset. Results are reported as Hits@1. The best results are highlighted in bold, and the second-best results are underlined.

Static Single-turn Retrieval
Method	Overall	Question Level
Method	Overall	Simple	Medium	Complex
RAG	0.515	0.840	0.498	0.209
RAG ${}_{\text{+Filter}}$	0.575	0.840	0.584	0.300
Query Transformation Enhancement
HyDE	0.494	0.801	0.485	0.197

Table 4. Performance comparison on TimelineCronQ-R. Results are reported as Hits@1. Baseline methods are evaluated both in their standard form and with a post-retrieval filter (

{}_{\text{+Filter}}

) to analyze the impact of noise reduction. The best results are highlighted in bold, and the second-best results are underlined.

Model	MultiTQ		TimelineCronQ-R
Model	Sing.	Mult.	Simp.	Med.	Comp.
Qwen2.5-14B-Inst	0.892	0.648	0.815	0.795	0.673
GPT-3.5-Turbo	0.903	0.822	0.825	0.892	0.759
DeepSeek-V3	0.916	0.767	0.844	0.874	0.702
Gemini-3-Flash	0.952	0.778	0.860	0.854	0.759

Table 5. Detailed performance comparison (Hits@1) across distinct question complexity levels.

MultiTQ					TimelineCronQ-R
Type	Count	Init. Evid.	Final Evid.	ECR(%)	Type	Count	Init. Evid.	Final Evid.	ECR(%)
equal	17212	747.00	3.58	99.52%	interval_relation	21	16.57	1.52	90.81%
equal_multi	3207	519.98	5.39	98.96%	quantitative_temporal	234	60.07	2.00	96.67%
before_after	11031	146.37	9.93	93.22%	relative_temporal	155	52.23	2.54	95.13%
before_last	6112	570.93	4.41	99.23%	temporal_operation	455	8.60	5.81	32.45%
after_first	6262	633.19	3.87	99.39%	temporal_order	336	45.26	7.46	83.53%

Table 6. Candidate-space control across question types on MultiTQ and TimelineCronQ-R.

Figure 3. Effect of different backbone models on the overall Hits@1 performance of SCoP. Horizontal bar chart comparing SCoP with four backbone models on MultiTQ and TimelineCronQ-R. All three alternative backbones improve over Qwen2.5-14B-Instruct in overall Hits@1. Gemini-3-Flash achieves the highest result on MultiTQ, while GPT-3.5-Turbo and Gemini-3-Flash achieve the highest overall results on TimelineCronQ-R.

Level	Gold Event		Gold Answer
Level	Any Ret.	Full Ret.	Any Ret.	Full Ret.
Simple	84.3%	84.0%	87.1%	86.6%
Medium	90.2%	84.4%	89.6%	82.2%
Complex	82.6%	76.4%	74.7%	72.4%
Overall	85.7%	81.6%	84.9%	81.3%

Table 7. Gold-event and gold-answer retention in the final evidence space on TimelineCronQ-R .

Model Variant	MultiTQ		TimelineCronQ-R
Model Variant	Hits@1	$\Delta$	Hits@1	$\Delta$
Full	0.825	–	0.761	–
w/o triple	0.517	-37.3%	0.420	-44.8%
w/o alignment	0.463	-43.9%	0.721	-5.3%
w/o constraint	0.449	-45.6%	0.541	-28.9%

Table 8. Ablation study of SCoP under the Overall Hits@1 metric.

\Delta

denotes the relative performance change compared with the full model.

Explore similar work

ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Generation
Jul 16, 2026Xuemeng Liu, Zhengpin Li, Wanpeng Tang +2Synthetic Benchmark Generation Temporal KGs
Peking University Beijing, China · Shanghai University of Finance and Economics Shanghai, China
SABET-QA: Temporal Knowledge Graph Question Answering
Aug 20, 2026Brahim Touayouch, Mirette Moawad, Dmitry AkulovKnowledge Graph Question Answering Temporal QA
QuickSort Research, Paris, France · ENS Paris-Saclay, École Polytechnique, France
Temporal-Aware Heterogeneous Graph Reasoning with Multi-View Fusion for Temporal Question Answering
Feb 23, 2026Wuzhenghong Wen, Bowen Zhou, Jinwen Huang +5Knowledge Graph Question Answering Temporal QA
School of Internet of Things, Nanjing University of Posts and Telecommunications · Faculty of Medicine & Health, University of New South Wales, Sydney, Australia · Beijing Information Science and Technology University +2

Jul 16, 2026J/K move · Enter open · S save

ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Generation

Xuemeng Liu, Zhengpin Li, Wanpeng Tang, Haotong Xie+1

Peking University Beijing, China · Shanghai University of Finance and Economics Shanghai, China

Synthetic Benchmark Generation Temporal KGs

Open paper AskPDF arXiv

Knowledge graph question generation (KGQG) aims to generate natural-language questions from structured graph evidence. Existing KGQG benchmarks, however, are mostly built on static knowledge graphs and do not encode the temporal scopes of graph facts. As a result, they cannot evaluate whether generated questions faithfully preserve temporal validity, event ordering, and answer-determining temporal constraints. In this paper, we study temporal knowledge graph question generation (TKGQG), where a generated question must be faithful to both the support subgraph and the temporal constraints required to identify the target answer. We propose ChronoQG, the first temporally expressive and hop-bounded benchmark construction framework for TKGQG. ChronoQG integrates a comprehensive temporal-constraint taxonomy, topology-temporal subgraph sampling, and trace-grounded question generation to construct temporally faithful questions. The framework produces four benchmark datasets from heterogeneous temporal knowledge graphs, totaling 16,011 verified questions. We evaluate representative LLM-based KGQG methods and prompting baselines across diverse TKGQG settings, including temporal-constraint counts, topological templates, and temporal-constraint types. The results show that existing methods struggle to preserve temporal constraints, especially under multi-constraint settings and harder temporal-constraint types. These findings reveal a clear gap between static KGQG and TKGQG, and establish ChronoQG as a challenging testbed for temporally faithful question generation.

Abstract

Explore similar work

ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Generation

SABET-QA: Temporal Knowledge Graph Question Answering

Temporal-Aware Heterogeneous Graph Reasoning with Multi-View Fusion for Temporal Question Answering