ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Generation Xuemeng Liu∗
Zhengpin Li∗
Wanpeng Tang
Nankai University Tianjin, China [email protected]
Peking University Beijing, China [email protected]
University of Electronic Science and Technology of China Chengdu, China [email protected]
Haotong Xie
Wentao Zhang
Shanghai University of Finance and Economics Shanghai, China [email protected]
Peking University Beijing, China [email protected]
arXiv:2607.14770v1 [cs.LG] 16 Jul 2026
Abstract 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 temporalconstraint 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. The code and benchmarks are available at https://anonymous.4open.science/r/ChronoQG-AB85. ∗ Both authors contributed equally to this research.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX
ACM Reference Format: Xuemeng Liu, Zhengpin Li, Wanpeng Tang, Haotong Xie, and Wentao Zhang. 2018. ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Generation. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 13 pages. https://doi.org/XXXXXXX.XXXXXXX
1
Introduction
Knowledge graph question generation (KGQG) is a core task for converting structured graph evidence into natural-language question– answer pairs. Given a support subgraph and a target answer, KGQG aims to generate a question that is answerable from the provided graph and grounded in the specified answer. Such generated questions provide scalable supervision for training and evaluating question answering systems [15, 24, 26], and also support the construction of question-asking dialogue agents [41]. Early KGQG methods typically rely on graph-to-sequence architectures that encode graph structures and decode natural-language questions [3, 7, 11, 32]. More recently, large language models (LLMs) have been adopted to serialize graph contexts into prompts and leverage instructionfollowing capabilities for generating more fluent and diverse questions with minimal task-specific supervision [16, 20, 26, 44]. Despite this progress, KGQG is still predominantly evaluated on static benchmarks, such as SimpleQuestion [4], WebQuestions [2], and PathQuestions [46]. These benchmarks model facts as timeless triples and omit temporal scopes, such as timestamps and validity intervals. Consequently, they cannot test whether a generation method faithfully expresses temporal validity, event ordering, fact evolution, or answer-determining temporal constraints. This limitation motivates temporal knowledge graph question generation (TKGQG), where the input consists of a time-aware support subgraph and a target answer, and the generated question must preserve both the graph structure and the temporal constraints required to identify the answer. A natural way to construct a TKGQG benchmark is to extend a conventional KGQG pipeline: sample a subgraph and a target answer from a temporal knowledge graph (TKG), serialize the temporal facts, and ask a model to generate a natural-language question. However, temporal benchmark construction requires more than
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
1 Limited Temporal Relations played for
2 Decoupled Hop-Temporal Constraint Two-Hop Temporal Knowledge Subgraph
Existing Temporal QA David Beckham
Trovato et al.
Manchester United
Alex Ferguson
coached
[1986, 2013]
Manchester United
played for [1996, 2009]
David Beckham
[1992, 2003] played for
David Beckham
England national team
[1996, 2009]
!
Problem: Temporal relation coverage is incomplete for overlaps, meeting and other relation.
Timeline 1992
1996
2003 2009
Manchester United [1992–2003]
overlaps England National Team [1996–2009]
Hop-aware Only Q1: Which person played for the team coached by Alex Ferguson during 1996 and 2013? Q2: Which person played for the team coached by Alex Ferguson? Ans: David Beckham
Problem: Removing the time constraint leads to the same answer.
Temporal-aware Only Q:Who was Manchester United’s coach in 1999? Q:Who played for Manchester United in 2000?
Problem: Only single-hop questions are available.
3
Semactic Shift Original Question
Which person played for the team coached by Alex Ferguson during an overlapping period between 1996 and 2013 LLM-based Rewrite
Which person played for Alex Ferguson's team between 1996 and 2013? Problem: Fluent rewriting could lead to semantic shift.
Figure 1: Limitation illustration. adding timestamps to static graph evidence. As illustrated in Figure 1, directly adapting ordinary KGQG construction to TKGs leads to three major limitations in benchmark construction. First, temporal constraints are incompletely modeled [33, 37]. Existing construction strategies typically rely on a small set of coarse temporal expressions, such as before, after, and during. However, real TKG facts exhibit richer temporal interactions, including interval overlap, boundary contact, containment, and dependencies between point-valued and interval-valued facts. For example, two football-team membership facts may overlap in time, but this relation cannot be represented if a benchmark only supports coarse temporal operators. Without a comprehensive temporal-constraint space, the benchmark cannot systematically test whether generation methods preserve fine-grained temporal semantics. Second, graph topology and temporal constraints are often not coupled. A reliable TKGQG benchmark should ensure that the target answer is identified only through the joint effect of subgraph structure and temporal constraints. However, direct construction pipelines typically sample a support subgraph first and then attach temporal expressions during question realization [8, 43]. This can produce temporal phrases that are syntactically present but semantically unnecessary: removing the temporal condition may leave the answer unchanged. Conversely, a pipeline may create multi-hop graph questions and temporal questions as separate cases, without requiring temporal filters to operate over the candidate set induced by the same hop-bounded subgraph. Such instances fail to test whether a generation method can preserve the coupling between structural reasoning and answer-determining temporal constraints in candidate space. Third, natural-language generation may introduce semantic shift. Template-based construction can preserve topology-temporal semantics, but the resulting questions are often rigid and unnatural. LLM-based rewriting improves fluency, but may alter the intended meaning. For example, a question asking which person played for the team coached by Alex Ferguson during a specific temporal overlap may be rewritten as “Who played for Alex Ferguson’s team between 1996 and 2013?”, drifting the temporal constraint
from an overlap to a simple between. Although fluent, the rewrite changes the temporal binding and weakens the intended reasoning semantics. Without verification, such shifts can silently enter the benchmark and reduce its reliability. To address these limitations, we propose ChronoQG, a benchmark construction framework for TKGQG. Given a TKG, ChronoQG constructs temporally expressive and hop-bounded benchmark instances through three components. First, ChronoQG defines a com! prehensive taxonomy of temporal constraints by integrating Allen’s interval algebra [1] with point algebra [39]. The taxonomy covers interval–interval, point–interval, interval–point, point–point, and ordinal constraints, providing a unified operator space for constructing fine-grained temporal questions. Second, ChronoQG performs topology-temporal subgraph sampling. Rather than sampling a subgraph and attaching temporal phrases afterward, it maintains a shared candidate answer space and progressively applies structural traversals, structural filters, and temporal filters. Each accepted action must update or shrink the candidate set, ensuring that the final answer is determined by the joint effect of hop-bounded subgraph topology and temporal constraints. Third, ChronoQG conducts trace-grounded question generation. It first constructs a template question from the accepted sampling trace, then rewrites the template into fluent natural language through verifier-guided agentic rewriting. Failed rewrites are repaired or discarded, reducing semantic shift and answer leakage during benchmark construction. Using ChronoQG, we construct a new TKGQG benchmark from two heterogeneous source TKGs with different temporal granularities. We instantiate ChronoQG on CronKG [33], a year-level TKG, and EventKG [13, 14], a day-level event-centric TKG. This yields four verified benchmark splits: ChronoQG-Cron-S, ChronoQGCron-M, ChronoQG-Event-S, and ChronoQG-Event-M, where “S” denotes single-constraint questions and “-M” denotes multiconstraint questions. In total, the benchmark contains 16,011 verified questions after redundancy removal, covering diverse topological templates, temporal-constraint types, and temporal-constraint counts. We evaluate representative LLM-based KGQG methods
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
adapted to temporal inputs, together with direct prompting baselines, on the proposed benchmark. The results show that existing static KGQG methods struggle to preserve temporal constraints, especially under multi-constraint settings and harder temporalconstraint types. Moreover, adding temporal constraints causes performance degradation comparable to increasing graph hops, indicating that temporal-constraint count is a key difficulty dimension for TKGQG. These findings reveal a clear gap between static KGQG and TKGQG, and demonstrate that ChronoQG provides a challenging and diagnostic benchmark for temporally faithful question generation.
2 Related Work 2.1 Temporal Knowledge Graphs Temporal knowledge graphs (TKGs) extend conventional knowledge graphs (KGs) by associating facts with temporal scopes, such as timestamps or validity intervals [19, 25]. These temporal annotations allow TKGs to represent when facts hold, thereby supporting fact evolution modeling, temporal validity reasoning, event ordering, and other time-sensitive applications. Several large-scale temporal knowledge resources have been constructed for these purposes [19, 28]. For example, Wikidata-derived TKGs such as CronKG [33] provide year-level temporal annotations, while EventKG [13, 14] primarily focuses on a large number of day-level eventcentric facts and integrates information from multiple sources, including DBpedia, YAGO, and Wikidata. Built on these resources, many temporal question answering (QA) datasets have been proposed to evaluate time-aware reasoning over structured knowledge. TempQuestions [17] categorizes temporal questions into explicit temporal, implicit temporal, temporalanswer, and ordinal-constraint questions. CronQuestions [33] constructs temporal questions over a TKG and covers simple-time, simple-entity, before/after, first/last, and time-join questions. MultiTQ [9] introduces multi-granularity temporal questions, supporting reasoning over temporal information at different granularities. MusTQ [43] studies multi-step temporal reasoning and derives reasoning types from measure-theoretic operations over time. More recent datasets further incorporate relation-level temporal modeling. TimelineKGQA [37] uses Allen-style interval relations during temporal QA-pair generation, while TDBench [18] compiles Allen relations into temporal SQL predicates to evaluate temporal reasoning over databases. These datasets provide important foundations for temporal reasoning, but they are designed primarily for answering temporal questions. In contrast, TKGQG requires generating questions from TKG evidence while preserving both the subgraph and the answer-determining temporal constraints.
2.2
Knowledge Graph Question Generation
Knowledge graph question generation (KGQG) aims to generate natural-language questions from structured graph evidence and a target answer. Existing methods can be broadly categorized into template-based, neural, and large language model (LLM)-based approaches. Template-based methods use hand-crafted question patterns and graph matching rules to transform KG structures into questions [34, 35]. Neural methods learn graph-to-question
mappings from annotated graph-question pairs, typically by encoding the input graph and decoding the corresponding question [5, 7, 11, 22, 32]. A typical example is Graph2Seq [40], an end-to-end model with an improved graph neural network and attention mechanism to map graph-structured inputs to sequences. More recently, LLM-based methods have improved fluency and diversity by linearizing graph contexts into prompts and leveraging instruction-following capabilities [16, 20, 26, 44]. Representative methods include KQG-CoT+ [20], which prompts LLMs with chainof-thought decomposition; SGSH [16], which uses skeleton-guided heuristics; RoleAgent [44], which formulates KGQG as a multi-role editorial workflow; R2DQG [32], which balances diversity and quality via template-guided draft generation and semantic refinement. KGQG benchmarks have played an important role in driving method development by providing standardized graph-question pairs. Early benchmarks such as WebQuestions [2] and SimpleQuestion [4] focus on relatively simple graph patterns, while later datasets introduce controllable difficulty through longer paths and more complex graph structures [46]. These benchmarks support evaluation of whether KGQG methods can preserve graph structure, ground questions in the target answer, and produce fluent natural-language questions. However, they are built on static KGs, where facts are modeled as timeless triples. As a result, they cannot evaluate whether generated questions preserve temporal validity, event ordering, or answer-determining temporal constraints. This gap motivates TKGQG, where questions are generated from timeaware graph evidence and must remain faithful to both the support subgraph and the temporal constraints.
3
Preliminaries
Knowledge Graph. Let E and R denote the sets of entities and relations, respectively. A knowledge graph (KG) is defined as G = (E, R, F ), where F is a set of relational facts [42]. Each fact is represented as a triple (𝑒𝑠 , 𝑟, 𝑒𝑜 ), where 𝑒𝑠 , 𝑒𝑜 ∈ E are the subject and object entities, and 𝑟 ∈ R is the relation connecting them. Given a subset of facts, we use S (𝑖 ) ⊆ F to denote a support subgraph sampled from G. In conventional KGQG benchmarks, such facts are treated as timeless triples, and the generated question is expected to preserve the structural reasoning pattern in the support subgraph. Temporal Knowledge Graph. Temporal knowledge graphs (TKGs) extend KGs by associating facts with temporal scopes, such as timestamps or validity intervals [6, 14, 19, 42]. A temporal knowledge graph (TKG) is defined as G𝑇 = (E, R, T , F𝑇 ), where F𝑇 is a set of temporal facts [6, 14, 19]. Each temporal fact is represented as (𝑒𝑠 , 𝑟, 𝑒𝑜 , 𝜏), where 𝑒𝑠 , 𝑒𝑜 ∈ E are the subject and object entities, 𝑟 ∈ R is the relation, and 𝜏 ∈ T denotes its temporal annotation. In this work, 𝜏 can be either a point timestamp 𝑡 or an interval [𝑡𝑠 , 𝑡𝑒 ] with start time 𝑡𝑠 and end time 𝑡𝑒 . A point fact can be viewed as a special interval with 𝑡𝑠 = 𝑡𝑒 . Given a subset of temporal facts, we use S𝑇(𝑖 ) ⊆ F𝑇 to denote a temporal support subgraph. KGQG Benchmark. Knowledge graph question generation (KGQG) aims to generate a natural-language question from structured graph evidence and a target answer. A KGQG benchmark is defined as
D𝐾𝐺𝑄𝐺 =
n
S (𝑖 ) , 𝑎𝑖 , 𝑞𝑖
o 𝑁 , 𝑖=1
(1)
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY Seed Space Construction
DBLP YAGO
Steven Jobs
2010 iPhone 4
employed_by
Jony Ive
Tim Cook
Tim Cook
2025 iPhone 17
Apple Inc.
iPhone 4
eS
produced
eS
employed_by
e1
iPhone 17
eS
A. Temporal Knowledge Graph Pair-wise Augmentation
1997~2011
Interval-Point
employed_by （Interval）
r1 r1
Apple Inc.
Hop Increasing
e1 r2
e1 eS e1
r2 r2
produced
IBM
produced (Point)
temporal_filter
iPhone 17 2025 ∈ [2011, 2026]
C0= {Compaq, IBM, Apple Inc.} e2
C1= {Macbook Air 1, iPhone 4, iPhone 17}
e2 e2
r3
P-inside-I
C2= {iPhone 17}
e3
P-before-I,P-at-start-I,Pinside-I,...
Point-Point
P-before-P,P-equals-P,...
employed_by（Interval） start_rank, end_rank, ...
Tim Cook
B. Taxonomy of Temporal Constraints
produced（Point）
Apple Inc.
Rewrite
iPhone 4 produced
Raw Question: Which product has the produced relation with the company that Tim Cook has the employed_by relation with, where the product time point is inside Tim Cook's employed_by time interval at that company?
1992~2019 2011~2026
r1
Compaq employed_by
produced
I-before-I,I-meets-I,Ioverlaps-I,...
Point-Interval
Ordinal Comparison
Tim Cook
Macbook Air 1
employed_by
C. Topology-Temporal Subgraph Sampling
Interval-Interval
I-covers-P,I-after-P,...
Allen's Interval Algebra
r1
Raw Question: Which product ... Answer：iPhone 17.
structural_filter
employed_by
Hop-Bounded Template Selection
produced produced
Candidate Space Search
located_in
iPhone 4 ...
Macbook Air 1
employed_by
Wikipedia
Apple Inc.
Tim Cook 2011~2026
iPhone 17
D. Trace-to-Template Construction
Verify
John Ive 1992~2019 Steven Jobs 1997~2011 2008 Macbook Air 1
Trovato et al.
Question 1: Which product was produced by Apple? Question 2: Was iPhone 17 produced by Apple during Tim Cook's time there? Question 1 fails because it losts time constraint. Validity Check Question 2 fails because it causes answer leakage.
Final Question:
Which product was produced by Tim Cook's employer during the period when he worked there?
E. Agentic Refinement
Figure 2: Overview of ChronoQG. Given heterogeneous temporal knowledge graphs, ChronoQG first defines a comprehensive temporal-constraint taxonomy over point- and interval-valued facts. It then performs topology-temporal subgraph sampling, where hop-bounded templates and temporal filters jointly narrow a shared candidate answer space. Finally, ChronoQG constructs trace-grounded template questions and applies verifier-guided agentic rewriting to obtain fluent questions. where S (𝑖 ) is a support subgraph sampled from a knowledge graph G, 𝑎𝑖 is the target answer, and 𝑞𝑖 is the reference question. A valid instance requires 𝑞𝑖 to be answerable from S (𝑖 ) with answer 𝑎𝑖 , i.e., Ans(𝑞𝑖 , S (𝑖 ) ) = 𝑎𝑖 . Existing KGQG benchmarks mainly focus on static graph, where facts are modeled as timeless triples and the generated question is expected to preserve the structural reasoning pattern that connects the support subgraph to the target answer. TKGQG Benchmark. Temporal knowledge graph question generation (TKGQG) extends KGQG from static graph evidence to time-aware graph evidence. A TKGQG benchmark is defined as n o 𝑁 D𝑇 𝐾𝐺𝑄𝐺 = S𝑇(𝑖 ) , 𝑎𝑖 , Γ𝑖 , 𝑞𝑖 , (2)
taxonomy of temporal constraints over point- and interval-valued facts, providing the operator space for temporally fine-grained benchmark construction. Second, it performs topology-temporal subgraph sampling, where hop-bounded templates and temporal operators are applied over a shared candidate answer space so that the final answer is jointly determined by subgraph topology and temporal constraints. Third, it conducts trace-grounded question generation: ChronoQG first constructs a template question from the accepted sampling trace and then rewrites it into fluent natural language through verifier-guided agentic rewriting. Figure 2 summarizes the overall construction process.
𝑖=1
4.1 where S𝑇(𝑖 ) is a temporal support subgraph, 𝑎𝑖 is the target answer, Γ𝑖 is the set of temporal constraints that determine the answer, and 𝑞𝑖 is the corresponding natural-language question. A valid TKGQG instance must satisfy two requirements. First, the question should be structurally grounded: it must reflect the graph reasoning structure in S𝑇(𝑖 ) . Second, it should be temporally faithful: it must preserve the temporal constraints in Γ𝑖 such that Ans(𝑞𝑖 , S𝑇(𝑖 ) , Γ𝑖 ) = 𝑎𝑖 . Therefore, a TKGQG benchmark should evaluate not only whether a generated question is fluent and graph-grounded, but also whether it faithfully expresses the temporal conditions.
4
Benchmark Design
In this section, we introduce ChronoQG, a benchmark construction framework for TKGQG. As discussed in Sec. 1, directly adapting conventional KGQG construction pipelines to TKGs is insufficient [13, 14, 33]. A reliable TKGQG benchmark must support fine-grained temporal constraints, couple hop-bounded topological reasoning with temporal filtering, and preserve graph-temporal semantics during question generation. To this end, ChronoQG consists of three components. First, it defines a comprehensive
A Comprehensive Taxonomy of Temporal Constraints
A TKGQG benchmark requires a temporal operator space that can uniformly characterize temporal dependencies among heterogeneous facts. In real-world TKGs, facts may be annotated with either point timestamps, such as birth dates, or interval timestamps, such as office terms and memberships. As a result, coarse temporal operators such as before, after, and during are insufficient for generating temporally fine-grained questions [23, 33]. ChronoQG therefore introduces a comprehensive taxonomy of temporal constraints by integrating Allen’s interval algebra [1] with point algebra [39]. Allen’s interval algebra defines 13 mutually exclusive and collectively exhaustive relations between two intervals: before, meets, overlaps, finished-by, contains, starts, equals, started-by, during, finishes, overlapped-by, met-by, and after. However, Allen’s algebra only models interval–interval relations. To support point-valued facts, we further incorporate point algebra, which defines three primitive relations between time points: before, equal, and after. Based on the temporal type of each fact, each pairwise temporal constraint in ChronoQG falls into one of the following four families:
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
Table 1: Temporal taxonomy used by ChronoQG. Family
Number
Operators
Interval–Interval (I–I)
13
I-before-I, I-meets-I, I-overlaps-I, I-finished-by-I, I-contains-I, I-starts-I, I-equals-I, I-started-by-I, I-during-I, I-finishes-I, I-overlapped-by-I, I-met-by-I, and I-after-I
Point–Interval (P–I)
5
P-before-I, P-at-start-I, P-inside-I, P-at-end-I, and P-after-I
Interval–Point (I–P)
5
I-before-P, I-ends-at-P, I-covers-P, I-starts-at-P, and I-after-P
Point–Point (P–P)
3
P-before-P, P-equals-P, and P-after-P
Ordinal
3
start_rank, end_rank, and duration_rank
• Interval–Interval (I–I). This family follows Allen’s interval algebra and models temporal constraints between two interval-valued facts. It contains the 13 interval relations: I-before-I, I-meets-I, I-overlaps-I, I-finished-by-I, I-containsI, I-starts-I, I-equals-I, I-started-by-I, I-during-I, I-finishes-I, I-overlapped-by-I, I-met-by-I, and I-after-I. • Point–Interval (P–I). This family specifies the position of a point-valued fact with respect to an interval-valued fact. It includes P-before-I, P-at-start-I, P-inside-I, P-at-end-I, and P-after-I. • Interval–Point (I–P). This family specifies the position of an interval-valued fact with respect to a point-valued fact. It includes I-before-P, I-ends-at-P, I-covers-P, I-starts-at-P, and I-after-P. • Point–Point (P–P). This family models ordering and equality constraints between two point-valued facts. It includes P-before-P, P-equals-P, and P-after-P. The four families above define pairwise temporal constraints between two facts. However, benchmark instances in TKGQG may also involve temporal comparisons over a set of candidate facts, rather than a single pair. Pairwise constraints cannot express questions that require identifying the earliest, latest, or 𝑘-th fact satisfying a temporal condition. To support such cases, ChronoQG further introduces three ordinal operators: start_rank, end_rank, and duration_rank. These operators rank a candidate set by start time, end time, or duration, and then select the candidate at the required rank. Overall, the taxonomy contains 26 pairwise temporal relations and 3 ordinal operators. This taxonomy defines the temporal operator space used by ChronoQG for constraint sampling and benchmark construction. Table 1 summarizes the operator families.
4.2
Topology-Temporal Subgraph Sampling
Given the temporal-constraint taxonomy, ChronoQG constructs benchmark instances through topology-temporal subgraph sampling. The goal is to generate reasoning traces in which subgraph topology and temporal constraints jointly determine the target answer. Instead of first sampling a subgraph and then attaching temporal expressions afterward [8], ChronoQG maintains a shared candidate answer space throughout the sampling process. Each structural traversal or temporal condition is accepted only when it contributes to narrowing this space. The procedure consists of three stages: seed space construction, hop-bounded template selection, and candidate space search.
4.2.1 Seed Space Construction. ChronoQG first constructs a temporally valid seed space from the source TKG. Each relation is assigned one of three temporal types: Point, Interval, or Deleted. Relations marked as Deleted are either semantically ambiguous or associated with facts that mix point and interval timestamps, and are therefore excluded from sampling. ChronoQG also removes invalid temporal facts, including facts with inconsistent timestamps where 𝑡𝑠 > 𝑡𝑒 for the interval [𝑡𝑠 , 𝑡𝑒 ] and facts attached to deleted relations. This step ensures that subsequent temporal constraints are applied only to facts with well-defined temporal semantics. After temporal annotation, ChronoQG samples a root seed from the remaining temporally valid facts. A root seed consists of an anchor entity and a directed relation, and is used to retrieve the initial candidate answer set. For example, given the seed (educated_at, University of Calgary) in the inverse direction, ChronoQG retrieves all entities whose educated_at relation points to University of Calgary. Formally, this seed defines the initial candidate set as 𝐶 0 = {𝑒 | (𝑒, educated_at, University of Calgary, 𝜏𝑒 ) ∈ F𝑇 } ,
(3)
where 𝜏𝑒 ∈ T denotes the timestamp associated with the fact. ChronoQG keeps only seeds satisfying |𝐶 0 | ∈ [5, 50]. This range provides enough candidates for composing structural and temporal constraints, while avoiding overly broad candidate spaces that make controlled instance construction difficult. 4.2.2 Hop-Bounded Template Selection. After selecting a root seed, ChronoQG chooses a topological template that specifies how the reasoning structure expands from the root. A template abstracts the structure of a sampled reasoning subgraph: each node denotes an entity variable, and each directed edge denotes a relation. ChronoQG considers the following representative hop-bounded templates: 𝑒𝑎 → 𝑒𝑏 ,
𝑒𝑐 ← 𝑒𝑎 → 𝑒𝑏 ,
𝑒𝑎 → 𝑒𝑏 → 𝑒𝑐 ,
𝑒𝑎 → 𝑒𝑏 → 𝑒𝑐 → 𝑒𝑑 . (4)
Here, each 𝑒𝑖 denotes an entity variable, and 𝑒𝑖 → 𝑒 𝑗 means that there exists a relation from 𝑒𝑖 to 𝑒 𝑗 in the TKG. The template 𝑒𝑎 → 𝑒𝑏 represents one-hop reasoning from the root to candidate answers. The template 𝑒𝑐 ← 𝑒𝑎 → 𝑒𝑏 represents a branching structure, where candidates are further constrained by another relation incident to the root. The templates 𝑒𝑎 → 𝑒𝑏 → 𝑒𝑐 and 𝑒𝑎 → 𝑒𝑏 → 𝑒𝑐 → 𝑒𝑑 capture two-hop and three-hop chain reasoning respectively. ChronoQG does not use longer templates because temporal filtering already increases reasoning difficulty, and long relational chains substantially reduce answerability after candidate
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
filtering. For fine-grained TKGs such as EventKG [13], longer templates are harder to instantiate after candidate filtering. ChronoQG therefore allocates a larger sampling budget to multi-hop templates to maintain sufficient coverage of complex reasoning cases.
4.2.3 Candidate Space Search. Starting from 𝐶 0 , ChronoQG expands the selected template while progressively updating the candidate answer space. Let 𝐶𝑡 denote the candidate set after the 𝑡-th sampling step. At each step, the sampler applies one action to either extend the sampled structure or impose a temporal condition, producing a new candidate set 𝐶𝑡 +1 . The process stops once the candidate set contains only a single entity, i.e., |𝐶𝑡 +1 | = 1, which is used as the target answer. The sampler supports three types of candidate-space updating actions. First, forward_transition follows a relation traversal specified by the selected template. For a chain template such as 𝑒𝑎 → 𝑒𝑏 → 𝑒𝑐 , after candidates for 𝑒𝑏 are obtained, the sampler follows the next relation and replaces each candidate 𝑒𝑏 with the reachable entities that can instantiate 𝑒𝑐 . This action extends the reasoning trace along the selected structure while updating the candidate answer set. Second, structural_filter adds an additional edge constraint and removes candidates that do not satisfy it. For example, consider the branching template 𝑒𝑐 ← 𝑒𝑎 → 𝑒𝑏 . If the root seed fixes 𝑒𝑏 as University of Calgary and retrieves candidates for 𝑒𝑎 through the inverse direction of educated_at, then 𝐶 0 contains people educated at University of Calgary. To instantiate the other branch, the sampler may fix 𝑒𝑐 as University of Alberta and require each candidate 𝑒𝑎 to also satisfy the edge 𝑒𝑎 → 𝑒𝑐 through educated_at. The candidate set is then reduced to people who attended both universities. Third, temporal_filter imposes a temporal constraint on facts already associated with the sampled structure. Under the same branching template, the sampler compares the timestamp of (𝑒𝑎 , educated_at, 𝑒𝑏 , 𝜏𝑏 ) with that of (𝑒𝑎 , educated_at, 𝑒𝑐 , 𝜏𝑐 ). According to the temporal types of 𝜏𝑏 and 𝜏𝑐 , it selects a compatible operator from the taxonomy and retains only candidates whose timestamps satisfy the constraint. For example, the sampler may require the University of Calgary education period to start before and overlap with the University of Alberta education period. The progressive construction above enforces constraint necessity during sampling. In this way, ChronoQG filters out the pseudotemporal conditions [8], namely those whose removal leaves the correct answers unchanged. This prevents temporal expressions from being added as decorative constraints to a pre-sampled subgraph, and ensures that they are genuinely involved in determining the final answer. For instances with multiple temporal constraints, ChronoQG further checks whether the constraints are mutually non-redundant. For example, “after 2000” becomes unnecessary once “between 2005 and 2010” is imposed, because the latter already implies the former. ChronoQG detects such cases by comparing the candidate sets induced by temporal constraints over the same original candidate pool. If one constraint yields a proper subset of another, the weaker constraint is removed. Instances that no longer satisfy the required constraint setting after this removal are discarded.
Trovato et al.
{
}
"id": "85", "graph_structure": "C <- A -> B", "hop_count": 2, "space_search_process": [ "root: educated at -> University of Calgary | 26 candidates", "structure_filtering: also educated at -> University of Alberta | 4 candidates", "temporal_filtering: overlaps(Calgary period, Alberta period) | 1 candidate" ], "temporal_constraints": [ "overlaps: Calgary period starts earlier and overlaps the Alberta period" ], "temporal_constraint_count": 1, "raw_question": "Which entity has the relation "educated at" to University of Calgary and also has the relation "educated at" to University of Alberta where the Calgary period started earlier and overlapped with the Alberta period for some years?", "final_question": "Who attended the University of Calgary before also studying at the University of Alberta, with their time at Calgary overlapping with some of their years at Alberta?", "answer": "Vikram Sabhaney",
Figure 3: Instance of sampling record.
4.3
Trace-Grounded Question Generation
After topology-temporal subgraph sampling, each instance is represented by a reasoning trace, which records how the initial candidate answer set is progressively narrowed by structural traversals, structural filters, and temporal constraints. ChronoQG converts this trace into a benchmark question in two steps. It first constructs a template question that preserves the sampled semantics, and then rewrites it into a natural question under verifier guidance. 4.3.1 Template Construction from Sampling Traces. ChronoQG first serializes each accepted sampling trajectory into an intermediate benchmark record. Each record stores the topological template, hop count, temporal-constraint count, ordered sampling steps, temporal constraints, support facts, target answer, and a template question. The ordered sampling steps describe how the candidate answer set is reduced during sampling. The template question deterministically verbalizes the accepted structural and temporal constraints. Figure 3 clearly illustrates this process with a concrete instance (id: 85). The instance follows the branching template 𝑒𝑐 ← 𝑒𝑎 → 𝑒𝑏 . The root seed fixes 𝑒𝑏 as University of Calgary and retrieves candidate entities 𝑒𝑎 whose educated_at relation points to this university, yielding an initial candidate set of 26 entities. The sampler then instantiates the other branch by fixing 𝑒𝑐 as University of Alberta and requiring the same candidates to also satisfy the relation 𝑒𝑎 → 𝑒𝑐 through educated_at. This structural filter reduces the candidate set from 26 to 4. Since multiple candidates still satisfy the sampled topology, the sampler further applies a strict temporal constraint between the two education facts. Specifically, it requires the Calgary education period to start earlier and overlap with the Alberta education period. This temporal filter reduces the candidate set to a unique answer, Vikram Sabhaney. Based on this trace, ChronoQG constructs a template question by concatenating the corresponding constraint fragments. In this example, the template asks which entity has the educated_at relation to both University of Calgary and University of Alberta, where the Calgary education period starts earlier and overlaps with the Alberta education period. The template is semantically faithful because every fragment is derived from an accepted sampling step and grounded in the support facts. However, such templates are often rigid and verbose, since they directly expose KG-style relations and concatenate constraint descriptions [9, 27, 43]. ChronoQG therefore uses the template as a semantic scaffold for later rewriting, rather than directly admitting it into the benchmark.
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
Table 2: Verifier accuracy (%) stratified by relation category. I and P denote interval and point temporal expressions, respectively. Each row group contains 500 samples. Category
(a) Cron-S
(c) Event-S
(b) Cron-M
(d) Event-M
Figure 4: Word count distributions of raw and final questions across four benchmark datasets.
4.3.2 Verifier-Guided Agentic Rewriting. Given a template question, ChronoQG invokes an LLM rewriter to produce a fluent naturallanguage question. The rewriting prompt requires the model to preserve all structural and temporal constraints. It also explicitly forbids reversing temporal directions, dropping constraints, revealing the answer, or copying KG-style relation labels verbatim. We use GPT-4o-mini [29] as the default rewriter. As shown in Figure 4, this step substantially shortens the questions and removes redundancy introduced by literal template concatenation. The rewritten question is then checked by an independent verifier. The verifier receives the support subgraph, the target answer, and a structure hint derived from the reasoning trace. It answers the rewritten question using only the provided evidence. ChronoQG compares the verifier prediction with the gold answer using fuzzy matching. If the predicted answer is equivalent to the gold answer, the rewrite is regarded as semantically faithful. Since the verifier directly affects benchmark quality, we select it empirically. Specifically, we evaluate four candidate models on 500 stratified template questions, whose semantics are reliable by construction, and choose the model with the best cost–accuracy tradeoff. We observe in Table 2 that GPT-5-mini [36] achieves 92.0% overall accuracy and use it as the default verifier. For the samples that failed this round, ChronoQG have arranged for the error analysis agent to analyze the causes of the failure or to determine whether the verifier mistakenly killed the correct samples. The second rewriter is given the original template question, the failed rewrite, the verifier’s predicted answer, the failure reason, and the support facts. It is then asked to generate a corrected rewrite. The repaired question is verified again under the same procedure. If it passes verification, it is admitted into the benchmark; otherwise, the instance is discarded. Before admitting a verified question, ChronoQG applies an answer-leakage filter as a final safeguard. A verified rewrite may still be unsuitable if it directly mentions the target answer. For each accepted question, ChronoQG scans the question for the gold
GPT-4o-mini
GPT-4o
GPT-5-mini
GPT-5
I–I P–I I–P P–P
52.5 60.0 76.0 66.9
75.4 67.5 84.0 78.8
88.7 100.0 88.0 96.7
90.1 100.0 100.0 98.0
Overall
58.6
76.2
92.0
93.8
answer string and its surface aliases appearing in the support subgraph. If an answer mention appears in the question, the question is rejected and sent to one additional rewrite attempt that explicitly forbids answer leakage. If the repaired version still leaks the answer, the instance is discarded. This filter ensures that verification success comes from reasoning over topology-temporal evidence rather than from trivial answer extraction. Finally, ChronoQG categorizes verified questions according to their temporal-constraint count. Instances with a single temporal constraint are treated as single-constraint cases, while those with multiple temporal constraints are treated as multi-constraint cases. This categorization supports separate evaluation of different temporal reasoning complexities.
5 Experiments 5.1 Experimental Setup 5.1.1 Dataset. We use two source TKGs with different temporal granularities and schema characteristics. CronKG [33] is a Wikidata-derived TKG with year-level temporal annotations and 202 relations. EventKG [13, 14] is a day-level, event-centric multilingual KG with 662 relations, integrating events from largescale knowledge graphs such as DBpedia, YAGO, and Wikidata. From these two sources, ChronoQG constructs four benchmark splits: ChronoQG-Cron-S, ChronoQG-Cron-M, ChronoQG-EventS, and ChronoQG-Event-M, where “-S” denotes single-constraint instances and “-M” denotes multi-constraint instances. The two source TKGs differ in temporal granularity, relation inventory, and schema design, allowing us to evaluate whether ChronoQG can construct TKGQG benchmarks across heterogeneous temporal knowledge sources. Table 3 reports the statistics of the four splits. 5.1.2 Evaluation Metrics. Consistent with previous studies on static KGQG, we evaluate generated questions using BLEU-4 [31], ROUGE2, and ROUGE-L [21]. BLEU measures 𝑛-gram precision between a generated question and the reference question, while ROUGE captures recall-oriented lexical overlap based on longest common subsequences and bigram matching. These metrics provide a standard automatic evaluation protocol for comparing different baselines. 5.1.3 Baselines. We evaluate three groups of baselines. The first group consists of prompting baselines designed for TKGQG. Given the serialized temporal subgraph, target answer, reasoning path, and temporal constraints, zero-shot prompting asks the model to generate the question in a single step. Zero-shot CoT first instructs the model to decompose the topological and temporal requirements, and then merge them into a natural-language question. Few-shot
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Trovato et al.
Table 3: Statistics of the proposed benchmark datasets. Dataset
Source
#Entity #Relation Avg. Hops Avg. Temporal Constraint
#I-I #P-I #I-P #P-P Total
Cron-S Cron-M
CronKG CronKG
34,306 26,929
88 72
1.50 1.46
1.00 2.64
2,924 433 1,780 213
Event-S EventKG Event-M EventKG
48,641 24,504
84 80
1.49 1.53
1.00 2.34
3,006 164 1,561 1,460 6,191 1,051 53 1,039 1,247 3,390
412 41
1,444 5,213 1,162 3,196
Table 4: Main results on the four ChronoQG-generated benchmark splits. Best results are boldfaced. Cron and Event denote the source TKGs, and S/M denote single-constraint and multi-constraint splits. Cron-S Base LLM
Cron-M
Event-S
Event-M
Method BLEU-4 ROUGE-2 ROUGE-L BLEU-4 ROUGE-2 ROUGE-L BLEU-4 ROUGE-2 ROUGE-L BLEU-4 ROUGE-2 ROUGE-L
GPT-4o-mini
Zero-shot Zero-shot CoT Few-shot
0.458 0.373 0.368
0.577 0.499 0.504
0.666 0.591 0.587
Close-source LLMs 0.288 0.404 0.502 0.254 0.376 0.472 0.231 0.353 0.443
0.410 0.334 0.375
0.541 0.476 0.520
0.631 0.569 0.602
0.328 0.269 0.282
0.456 0.412 0.427
0.545 0.501 0.502
GPT-4o
Zero-shot Zero-shot CoT Few-shot
0.398 0.424 0.404
0.527 0.550 0.541
0.631 0.650 0.628
0.245 0.267 0.260
0.471 0.490 0.472
0.348 0.346 0.376
0.496 0.485 0.520
0.612 0.598 0.602
0.274 0.273 0.284
0.417 0.419 0.429
0.521 0.520 0.516
Zero-shot Few-shot
0.368 0.435 0.369
0.494 0.550 0.485
0.620 0.660 0.602
0.366 0.359 0.338
0.500 0.489 0.487
0.611 0.600 0.589
0.204 0.237 0.217
0.337 0.362 0.349
0.459 0.489 0.473
DeepSeek-V3
Zero-shot Zero-shot CoT Few-shot
0.292 0.350 0.363
0.425 0.480 0.492
0.525 0.579 0.587
0.271 0.388 0.517 0.318 0.440 0.568 0.294 0.414 0.547 Open-source LLMs 0.179 0.294 0.390 0.219 0.342 0.435 0.208 0.330 0.428
0.271 0.293 0.360
0.419 0.442 0.505
0.526 0.546 0.583
0.216 0.228 0.253
0.346 0.366 0.396
0.444 0.467 0.479
GLM-4.6
Zero-shot Zero-shot CoT Few-shot
0.266 0.292 0.339
0.364 0.400 0.432
0.496 0.533 0.547
0.197 0.211 0.280
0.290 0.309 0.374
0.421 0.453 0.496
0.236 0.239 0.238
0.344 0.350 0.347
0.473 0.480 0.477
0.152 0.188 0.216
0.248 0.304 0.315
0.377 0.443 0.444
Qwen2.5-32B
Zero-shot Zero-shot CoT Few-shot
0.405 0.419 0.401
0.534 0.545 0.534
0.635 0.646 0.623
0.238 0.257 0.242
0.367 0.379 0.364
0.466 0.475 0.456
0.340 0.348 0.361
0.485 0.488 0.510
0.593 0.601 0.586
0.261 0.268 0.265
0.402 0.406 0.416
0.505 0.508 0.490
– –
G2S-AE G2S-AE-RL
0.494 0.523
0.569 0.606
Full Training KGQG Methods 0.685 0.335 0.384 0.516 0.717 0.351 0.399 0.526
0.424 0.467
0.523 0.565
0.635 0.675
0.344 0.391
0.404 0.470
0.523 0.584
KQG-CoT SGSH RoleAgentQG R2DQG
0.417 0.346 0.264 0.199
0.544 0.453 0.388 0.293
0.637 0.552 0.509 0.426
LLM-based KGQG Methods 0.262 0.396 0.486 0.238 0.349 0.439 0.184 0.295 0.410 0.167 0.266 0.385
0.249 0.263 0.241 0.138
0.396 0.403 0.383 0.237
0.502 0.508 0.508 0.370
0.188 0.306 0.169 0.128
0.334 0.425 0.300 0.226
0.449 0.520 0.418 0.348
Gemini-3.1-pro-preview Zero-shot CoT
GPT-4o-mini
prompting further provides demonstrations retrieved by matching the temporal-constraint type from our taxonomy. We evaluate these prompting strategies with both closed-source LLMs, including GPT-4o-mini [29], GPT-4o [30], and Gemini-3.1-pro-preview [12], and open-source LLMs, including DeepSeek-V3 [10], GLM-4.6 [45], and Qwen2.5-32B [38]. In all prompting baselines, the reasoning path is included to make the support topology explicit. The second group includes full-training KGQG methods G2S-AE and G2S-AERL [40]. To adapt them to TKGQG, we augment the serialized graph input with temporal annotations and temporal-constraint information. The third group adapts representative LLM-based static KGQG methods to temporal inputs. KQG-CoT [20] performs chainof-thought decomposition before question generation. SGSH [16]
0.371 0.397 0.383
predicts a question skeleton and uses an LLM to realize the final question. RoleAgentQG [44] formulates KGQG as a multi-role editorial workflow. R2DQG [32] generates questions through relationaware decomposition. For all adapted static-KGQG methods, we attach event start and end times to the serialized facts and add the temporal-constraint sequence to the input prompt.
5.2
Main Results
Table 4 reports the main results on the four ChronoQG-generated benchmark splits. We make three observations. Observation 1. LLM prompting baselines generally outperform adapted LLM-based static methods. Across the four splits, zero-shot, zero-shot CoT, and few-shot prompting with general-purpose LLMs
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
multi-constraint splits. Similarly, the best LLM prompting baselines still obtain limited BLEU-4 scores on Cron-M and EventM, indicating that current LLMs do not reliably preserve answerdetermining temporal constraints. Overall, these results demonstrate that ChronoQG exposes a clear gap between static KGQG and TKGQG: existing methods, whether prompt-based, adapted from static KGQG, or fully trained, still struggle to generate questions that are faithful to both topology and temporal constraints. (a) ChronoQG-Cron
(b) ChronoQG-Event
5.3 Figure 5: A heatmap illustrating performance variations with respect to hop count and temporal-constraint count under the zero-shot prompting strategy using GPT-4o-mini. Cases with temporal constraint number larger than 2 are merged.
Table 5: EventKG results of adapted LLM-based KGQG methods with different LLM backbones. Event-S Method
Event-M
Backbone BLEU-4
ROUGE-2
ROUGE-L
BLEU-4
ROUGE-2
ROUGE-L
SGSH
GPT-4o-mini GPT-4o
0.263 0.320
0.403 0.469
0.508 0.579
0.306 0.308
0.425 0.434
0.520 0.536
KQG-CoT
GPT-4o-mini GPT-4o
0.249 0.318
0.396 0.460
0.502 0.570
0.188 0.257
0.334 0.399
0.449 0.499
RoleAgentQG
GPT-4o-mini GPT-4o
0.241 0.226
0.383 0.377
0.508 0.504
0.169 0.193
0.300 0.334
0.418 0.450
usually achieve higher BLEU-4, ROUGE-2, and ROUGE-L scores than KQG-CoT, SGSH, RoleAgentQG, and R2DQG. This strongly suggests that explicitly providing the temporal subgraph, target answer, reasoning path, and temporal constraints is a strong formulation for TKGQG. Among prompting baselines, closed-source LLMs tend to perform better than open-source LLMs. For example, GPT-4o-mini, GPT-4o, and Gemini-3.1-pro-preview consistently achieve competitive results across the four splits, while DeepSeekV3, GLM-4.6, and Qwen2.5-32B show larger performance variation. In contrast, adapted static KGQG methods are generally less effective because their skeletons, decomposition strategies, or editorial workflows are designed for timeless graph triples and do not explicitly model temporal validity, temporal-constraint types, or their attachment to specific graph relations. Observation 2. Multi-constraint splits are consistently harder than single-constraint splits. Across most backbones and methods, performance drops from the ‘-S” splits to the corresponding ‘-M” splits. For instance, GPT-4o-mini with zero-shot prompting drops from 0.458 to 0.288 BLEU-4 on Cron and from 0.410 to 0.328 BLEU-4 on Event. Similar degradation is also observed for ROUGE-2 and ROUGE-L. This confirms that temporal-constraint count is a meaningful difficulty dimension: adding temporal constraints requires the model to preserve more fine-grained temporal semantics and to bind them correctly to the support subgraph. Observation 3. Even the strongest methods still leave substantial room for improvement. Although full-training KGQG methods such as G2S-AE-RL achieve the best scores in several settings, their performance remains far from saturated, especially on the
Benchmark Analysis
5.3.1 Topology-temporal influence. Figure 5 analyzes how two factors, graph hop count and temporal-constraint count, affect generation difficulty under zero-shot prompting with GPT-4o-mini. We first examine the effect of hop count. When the temporal-constraint count is fixed, increasing the hop count generally leads to lower BLEU-4 scores. On ChronoQG-Cron, under one time constraint, performance drops from 0.547 for one-hop questions to 0.356 for two-hop questions and 0.307 for three-hop questions. A similar pattern appears on ChronoQG-Event, where the score decreases from 0.500 to 0.320 and then to 0.278. This shows that longer reasoning chains make question generation harder, since the model must preserve more relations and bind the target answer to a larger support structure. We then further examine the effect of temporal-constraint count. When the hop count is fixed, adding more temporal constraints also reduces performance. On ChronoQG-Cron, one-hop questions drop from 0.547 BLEU-4 with one temporal constraint to 0.443 with two temporal constraints, and further to 0.238 with three or more temporal constraints. The same trend holds for two-hop questions, where the score decreases from 0.356 to 0.275 and then to 0.185. ChronoQG-Event shows a consistent but milder trend: for two-hop questions, BLEU-4 decreases from 0.320 with one temporal constraint to 0.310 with two temporal constraints and 0.233 with three or more temporal constraints. These results indicate that temporal constraints introduce an additional source of difficulty beyond graph topology, because the model must not only accurately verbalize the support subgraph but also preserve the temporal conditions attached to specific facts. 5.3.2 Backbone influence. Table 5 examines whether the weakness of adapted static KGQG methods can be mitigated by using a stronger LLM backbone. Replacing GPT-4o-mini with GPT-4o generally improves SGSH and KQG-CoT on both Event-S and Event-M. For example, KQG-CoT increases from 0.249 to 0.318 BLEU-4 on Event-S and from 0.188 to 0.257 on Event-M. SGSH also improves on Event-S and achieves a slight gain on Event-M. However, the overall performance remains unsatisfactory. Even with GPT-4o, these adapted KGQG methods still do not consistently surpass the simple prompting baselines reported in Table 4, and their scores remain especially limited on the multi-constraint split. This result suggests that the main bottleneck is not merely the language modeling capability of the backbone, but the mismatch between static KGQG method designs and the requirements of TKGQG. Methods such as SGSH, KQG-CoT, and RoleAgentQG were originally designed for timeless graph triples, where question generation mainly requires preserving graph structure and
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Trovato et al.
Figure 6: BLEU-4 by temporal-relation type. Scores are aggregated over both source TKGs and the single-/multi-constraint splits. Colors indicate temporal-relation families. Table 6: API cost in USD for running all four datasets.
Method
GPT-4o-mini
GPT-4o
Zero-shot Zero-shot CoT Few-shot
2.30 2.45 6.73
38.34 40.79 112.17
SGSH KQG-CoT RoleAgentQG
17.16 23.15 20.94
286.03 385.84 349.10
answer grounding. In TKGQG, however, the model must additionally preserve temporal validity, temporal-constraint types, and the attachment between each temporal constraint and its corresponding graph fact. Simply replacing the backbone with a stronger LLM improves surface realization, but does not fundamentally solve this topology-temporal binding problem. Therefore, the results further confirm that TKGQG requires methods specifically designed for temporally constrained graph evidence, rather than direct adaptations of static KGQG pipelines. 5.3.3 Model cost. Table 6 compares the estimated API cost of different generation strategies. Existing LLM-based KGQG methods incur substantially higher costs than simple prompting baselines. On GPT-4o-mini, zero-shot prompting costs only 2.30 for all four released datasets, while SGSH, KQG-CoT, and RoleAgentQG require 17.16, 23.15, and 20.94, respectively. The gap becomes even larger with GPT-4o, where zero-shot prompting costs 38.34, but the adapted KGQG methods cost between 286.03 and 385.84. This overhead mainly comes from their multi-stage designs, such as skeleton prediction, decomposition, and multi-role editing, which require multiple LLM calls for each instance. However, as shown in Table 4, these additional calls do not translate into better TKGQG performance. In contrast, direct LLM prompting achieves stronger results with much lower cost by explicitly conditioning on the temporal subgraph, target answer, reasoning path, and temporal constraints in a single generation step. These results suggest that current KGQG pipelines are not only less effective for TKGQG, but also less cost-efficient than simpler LLM prompting formulations.
Table 7: Human evaluation of generated questions. Fluency measures linguistic naturalness, faithfulness measures whether the question preserves the given graph and temporal constraints, and answerability measures whether the question can be answered from the provided evidence. Dataset
Fluency
Faithfulness
Answerability
Cron-S Cron-M
4.85 4.71
4.83 4.81
4.86 4.65
Event-S Event-M
4.84 4.59
4.71 4.69
4.85 4.72
5.3.4 Temporal taxonomy. Figure 6 analyzes performance across different temporal-constraint types. The results show that generation difficulty varies substantially across constraint families, indicating that TKGQG cannot be fully characterized by hop count or temporal-constraint count alone. Interval–interval constraints exhibit large internal variation: boundary-sensitive relations such as meets, starts, and finishes are generally harder than more intuitive ordering or containment relations, because the model must verbalize precise interval boundaries rather than coarse temporal order. Point–interval and interval–point constraints are also challenging, especially when the generated question needs to attach a point event to the start, end, or interior of an interval-valued fact. In contrast, point–point constraints are relatively easier, since they often correspond to familiar temporal expressions such as before, after, or same year. Ordinal constraints show consistently lower performance, suggesting that ranking-based temporal reasoning is difficult for current models: the model must not only express temporal order, but also preserve the selection criterion over a candidate set. Overall, the results demonstrate that temporal-constraint type is an important diagnostic dimension of ChronoQG. Different temporal operators impose different realization and grounding requirements, and existing models remain sensitive to these finegrained temporal semantics. 5.3.5 Human evaluation. To assess the quality of the generated questions, we conduct a human evaluation on four dataset splits. For each dataset, we randomly sample 500 generated questions from
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
Golden Question
Missing Constraint
Who received the Commander of the Order for Merits to Lithuania after Jerzy Bahr but before Krzysztof Krajewski?
Wrong Constraint
Unnecessary Constraint
Supporting Facts
Model Output
Failure Type
Who received the Gran Cross of the Order of James I the Conqueror after Joan Lerma but before Adela Cortina?
Who received the Commander of the Order for Merits to Lithuania after Jerzy Bahr? [Missing temporal constrainst “before”]
Who received the Gran Cross of the Order of James I the Conqueror after Joan Lerma and Adela Cortina? [Wrong time relation with Adela Cortina]
Who received the Medal for outstanding service to Bavaria in a Who received the Medal for outstanding united Europe in the same year as Kai service to Bavaria in a united Europe in Frobel but not in the same year as the same year as Kai Frobel? Caroline Link?
Target Answer
(Missing)
2009
2019
2005 Jerzy Bahr (award received)
Valentyn Krzysztof Nalyvaichenko Krajewski (award received) (award received)
Target Answer (Wrong) 2008
2014
Joan Lerma (award received)
2017
Adolfo Suárez Adela Cortina (award received) (award received)
Target Answer
2015
2015
Kai Frobel (award received)
Nora-Eugenie Gomringer (award received)
(Unnecessary) 2008
[Unnecessary constraint]
Caroline Link (award received)
Figure 7: Failure cases of TKGQG. the final verified set. The sampled questions are evaluated by human annotators with background knowledge in knowledge graphs and question answering, so that they can judge not only surface fluency but also whether the generated question is consistent with the underlying graph evidence and temporal constraints. Each annotator is provided with the generated question, the target answer, the supporting facts, and the corresponding temporal constraints. We ask the annotators to rate each question along three dimensions using a 1–5 Likert scale, where 5 indicates the best quality. Fluency measures whether the question is grammatically correct and linguistically natural. Faithfulness measures whether the question preserves the given graph structure, supporting facts, target answer, and temporal constraints. Answerability measures whether the question can be answered from the provided evidence without requiring external knowledge. The final score for each dimension is computed as the average over the 500 sampled questions. As shown in Table 7, the generated questions achieve consistently high scores across all four datasets. Fluency scores are above 4.69 for all splits, indicating that the rewriting process produces natural and readable questions. Faithfulness scores are also high, showing that most generated questions preserve the intended graph and temporal semantics. Answerability remains high across all datasets, demonstrating that the generated questions can generally be answered using the provided supporting facts. Overall, the human evaluation confirms that our framework produces questions that are not only fluent, but also faithful to temporal KG evidence and answerable from the given context. 5.3.6 Rewriting performance. Table 8 compares the raw template questions with the final rewritten questions across four datasets. Here, Δlen measures the relative reduction in question length after rewriting, and Preservation measures the percentage of entities appearing in the raw question that are retained in the rewritten question. Overall, the rewriting process simplifies the original
Table 8: Comparison between raw and final questions across four datasets. Δlen denotes the relative reduction in question length after rewriting. BLEU-4 is computed between raw and final questions to quantify surface-form divergence. Preservation measures the percentage of entities in the raw question that are retained in the final question. Dataset
Δlen (%)
BLEU-4
Preservation (%)
Cron-S Cron-M Event-S Event-M
49.8 62.1 52.6 63.1
0.10 0.08 0.09 0.06
98.0 94.4 94.1 92.1
Avg.
59.6
0.08
94.7
template-style questions, with an average length reduction of 56.9%. The reduction is consistent across all datasets, ranging from 49.8% on Cron-S to 63.1% on Event-M, showing that the rewriting step effectively removes rigid and verbose template expressions. Despite this large compression, the rewritten questions preserve most of the semantic content. Entity preservation remains above 92% for all datasets, with an average of 94.7%, indicating that the rewriting process largely retains the entities required to express the original graph and temporal constraints. Meanwhile, the BLEU-4 scores between raw and rewritten questions are low, with an average of 0.083. This does not indicate poor quality; rather, it shows that the final questions are not lexical copies or minor edits of the templates. Instead, the model substantially changes the surface form, producing more natural questions while preserving the key entities and intended semantics. These results suggest that our rewriting process achieves high-quality naturalization: it greatly simplifies the
Conference acronym ’XX, June 03–05, 2018, Woodstock, NY
Trovato et al.
Rewriting Agent
Table 9: Average number of root-seed candidates before progressive constraint application.
System: You are rewriting a machine-generated temporal knowledge-graph question into a fluent, natural-sounding English question that reads like something a human would actually ask. Core goal: produce a question indistinguishable from human-written text. Rules: 1. The rewritten question must have the same unique answer as the original.
# Root Seed
2. Do NOT reveal the answer in the question.
Dataset 1-Hop
2-Hop
3-Hop
Cron-S Cron-M
12.93 13.18
11.79 11.36
14.01 9.04
Event-S Event-M
5.56 5.34
13.11 12.17
20.30 9.52
3. Do NOT use any internal labels (tr-1, tp-26, "current step", etc.). 4. CRITICAL — preserve temporal direction exactly. If the original says A happened BEFORE B, your rewrite must keep A before B. Never reverse "before/after", "starts/ends", "during/contains", or any temporal ordering. 5. CRITICAL — use ONLY natural human language. Absolutely forbidden: - KG jargon: "entity", "relation", "linked from", "connected to", "current step period", "candidate's period", "the period for that relation" - Quoted relation names: do NOT write "member of sports team" or "position held" in quotes — instead say "played for", "served as", "worked at", etc., using the natural verb for that relationship - Template phrases: "Which entity has the relation X to Y where..." 6. For multi-hop questions ("Following the unique entity via..."), merge both hops into one seamless natural-language question. For example, "Who coached the team that [person] played for before [year]?" instead of "Following the
expression, departs from template-like wording, and still maintains the essential semantic content of the original question.
unique entity via 'head coach', which next entity?". 7. Output exactly one rewritten English question and nothing else. User: Original question: {original_question} Subgraph facts (use these to understand the domain and pick natural verbs): {facts}
5.3.7 Constraint contribution. Table 9 reports the average number of root-seed candidates before progressive constraint application. Across the four datasets, the initial candidate sets are non-trivial, ranging from 5.34 to 20.30 on average, indicating that the root relation alone usually cannot determine a unique answer. This confirms the necessity of progressive sampling: starting from a relatively broad candidate set, our method incrementally applies structural hops and temporal constraints, and each accepted constraint must reduce the remaining candidates. As a result, the sampling process effectively turns ambiguous root seeds into well-constrained question instances. The larger candidate sets in multi-hop settings, especially Event-S at 3-hop, further show that graph traversal can expand the search space, making progressive temporal filtering essential for controlling answer ambiguity and producing questions with unique, verifiable answers.
Target answer (do NOT include in your question): {target_answer}
Figure 8: Prompt of rewriting agent. Revising Agent System: A previously rewritten temporal question failed verification — an LLM could not arrive at the correct answer from the subgraph using the rewritten question. This likely means the rewrite introduced semantic drift. Your task: diagnose what went wrong and produce a corrected question. Rules: 1. The corrected question MUST have the same answer as the original. 2. Do NOT reveal the answer in the question. 3. Do NOT use internal labels (tr-1, tp-26, etc.). 4. CRITICAL — preserve temporal direction: if the original says event A happened BEFORE event B, your rewrite must keep A before B. The most common failure is reversing "before/after" or swapping which event is the reference. Double-check that your corrected question preserves the exact temporal ordering from the original. 5. Make the question concise and natural. 6. Output exactly one corrected English question and nothing else. User: Original (template) question: {original_question}
5.4
Failed rewrite: {failed_rewrite}
Case Study
LLM's wrong answer to the failed rewrite: {wrong_answer}
Figure 7 presents three representative failure cases in TKGQG. Although the generated questions are generally fluent, they may fail to preserve the exact temporal semantics encoded in the template. The first case shows a missing-constraint error: the model removes the “before” condition and produces a question whose answer set is no longer restricted by the required temporal order. The second case illustrates a wrong-constraint error, where the model retains a temporal expression but changes its relation from the intended “after Joan Lerma but before Adela Cortina” to a different condition involving both entities, leading to an incorrect target answer. The third case shows an unnecessary-constraint error: the model introduces an additional temporal comparison that is not present in the gold question, thereby introducing a redundant constraint. These cases suggest that the main challenge is not surface-level fluency, but faithful preservation of temporal constraints during natural language realization. Even when the generated question appears grammatical and semantically plausible, small changes to temporal operators can alter the denotation of the question. This observation motivates the use of explicit verification in our framework: by checking whether the rewritten question preserves the intended supporting facts and target answer, the verifier can identify questions that are fluent but temporally inconsistent. The case study therefore complements the quantitative results by showing that temporal-relation fidelity is a critical factor for reliable TKGQG.
Correct answer (do NOT include in your question): {target_answer} Subgraph facts: {facts}
Figure 9: Prompt of revising agent.
5.5
LLM Prompt
Figures 8 and 9 show the prompts of the rewriting and revising agents, respectively. The rewriting prompt converts template questions into fluent natural-language questions while preserving the original answer and temporal meaning. The revising prompt is used to correct failed rewrites by eliminating semantic drift, especially temporal-order errors, and producing a verified natural question.
6
Conclusion
In this paper, we present ChronoQG, a framework for constructing temporally expressive and hop-bounded TKGQG benchmarks. To address the limited temporal coverage and weak constraint control of existing KGQG datasets, ChronoQG introduces a comprehensive temporal-relation taxonomy, a topology–temporal subgraph sampling strategy, and a verifier-guided rewriting pipeline to generate fluent questions that preserve the intended graph and temporal semantics. Using this framework, we construct four benchmark splits from two source TKGs, resulting in 16,011 verified questions with diverse hop structures and temporal constraint patterns. Extensive
ChronoQG: Towards a Temporally Expressive and Hop-Bounded Benchmark for Temporal Knowledge Graph Question Conference Generation acronym ’XX, June 03–05, 2018, Woodstock, NY
analyses show that current methods, including both LLM-based approaches and adapted static KGQG baselines, still struggle with temporally constrained question generation, especially as topological complexity and temporal-constraint complexity increase. This reveals a clear gap between existing KGQG techniques and the requirements of temporally faithful question generation. We hope ChronoQG serves as a useful benchmark for exposing this gap and advancing models that reason over complex temporal knowledge.
References [1] James F Allen. 1983. Maintaining knowledge about temporal intervals. Communications of the Association for Computing Machinery 26, 11 (1983), 832–843. [2] Jonathan Berant et al. 2013. Semantic parsing on freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. 1533–1544. [3] Sheng Bi, Zeyi Miao, and Qizhi Min. 2025. LEMON: A knowledge-enhanced, typeconstrained, and grammar-guided model for question generation over knowledge graphs. IEEE Transactions on Learning Technologies 18 (2025), 256–272. [4] Antoine Bordes et al. 2015. Large-scale simple question answering with memory networks. arXiv preprint arXiv:1506.02075 (2015). [5] Nicoletta Calzolari et al. 2024. Diversifying question generation over knowledge base via external natural questions. In Proceedings of the Joint 30th International Conference on Computational Linguistics and 14th International Conference on Language Resources and Evaluation. 5096–5108. [6] Wei Chen et al. 2024. Local-global history-aware contrastive learning for temporal knowledge graph reasoning. In Proceedings of the 40th IEEE International Conference on Data Engineering. 733–746. [7] Yu Chen, Lingfei Wu, and Mohammed J Zaki. 2024. Toward subgraph-guided knowledge graph question generation with graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 35, 9 (2024), 12706–12717. [8] Ziyang Chen et al. 2022. Temporal knowledge graph question answering via subgraph reasoning. Knowledge-Based Systems 251 (2022), 109134. [9] Ziyang Chen, Jinzhi Liao, and Xiang Zhao. 2023. Multi-granularity temporal question answering over knowledge graphs. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics. 11378–11392. [10] DeepSeek-AI. 2024. DeepSeek-V3 technical report. arXiv preprint arXiv:2412.19437 (2024). [11] Zichu Fei et al. 2022. LFKQG: A controlled generation framework with local fine-tuning for question generation over knowledge bases. In Proceedings of the 29th International Conference on Computational Linguistics. 6575–6585. [12] Google DeepMind. 2026. Gemini 3.1 Pro. Google release. https://blog.google/ innovation-and-ai/models-and-research/gemini-models/gemini-3-1-pro [13] Simon Gottschalk and Elena Demidova. 2018. EventKG: A multilingual eventcentric temporal knowledge graph. In Proceedings of the 15th European Semantic Web Conference. 272–287. [14] Simon Gottschalk and Elena Demidova. 2020. EventKG+BT: Generation of interactive biography timelines from a knowledge graph. In Proceedings of the 24th International Conference on World Wide Web. 91–97. [15] Shasha Guo et al. 2022. DSM: Question generation over knowledge base via modeling diverse subgraphs with meta-learner. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 4194–4207. [16] Shasha Guo et al. 2024. SGSH: Stimulate large language models with skeleton heuristics for knowledge base question generation. In Findings of 2024 North American Chapter of the Association for Computational Linguistics. 4613–4625. [17] Zhen Jia et al. 2018. TempQuestions: A benchmark for temporal question answering. In Companion Proceedings of the 27th The Web Conference. 1057–1062. [18] Soyeon Kim et al. 2026. Harnessing temporal databases for systematic evaluation of factual time-sensitive question-answering in LLMs. In Proceedings of the 14th International Conference on Learning Representations. 1–34. [19] Kalev Leetaru and Philip A. Schrodt. 2013. GDELT: Global data on events, location and tone, 1979-2012. In Proceedings of the 54th Annual Convention of the International Studies Association. 1–49. [20] Yuanyuan Liang et al. 2023. Prompting large language models with chain-ofthought for few-shot knowledge base question generation. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 4329–4343. [21] Chin-Yew Lin. 2004. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out. 74–81. [22] Cao Liu et al. 2019. Generating questions for knowledge bases via incorporating diversified contexts and answer-aware Loss. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing. 2431–2441. [23] Jian Liu et al. 2024. Towards multi-relational multi-hop reasoning over dense temporal knowledge graphs. In Findings of the 62nd Annual Meeting of the Association for Computational Linguistics. 14367–14378.
[24] Jiaxiang Liu et al. 2025. Enhancing large language models with pseudo-and multisource-knowledge graphs for open-ended question answering. In Proceedings of the 41st IEEE International Conference on Data Engineering. 97–106. [25] Kangzheng Liu et al. 2023. RETIA: Relation-entity twin-interact aggregation for temporal knowledge graph extrapolation. In Proceedings of the 39th IEEE International Conference on Data Engineering. 1761–1774. [26] Ruishen Liu et al. 2025. FKQG: Few-shot question generation from knowledge graph via large language model in-context learning. Data & Knowledge Engineering 161 (2025), 102528. [27] Jannat Meem et al. 2024. PAT-Questions: A self-updating benchmark for presentanchored temporal question-answering. In Findings of the 62nd Annual Meeting of the Association for Computational Linguistics. 13129–13148. [28] S. P. O’Brien. 2010. Crisis early warning and decision support: Contemporary approaches and thoughts on future research. International Studies Review 12, 1 (2010), 87–104. [29] OpenAI. 2024. GPT-4o mini: Advancing cost-efficient intelligence. OpenAI release. https://openai.com/index/gpt-4o-mini-advancing-cost-efficientintelligence/ [30] OpenAI. 2024. GPT-4o system card. arXiv preprint arXiv:2410.21276 (2024). [31] Kishore Papineni et al. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. 311–318. [32] Yimeng Ren et al. 2025. R2DQG: A quality meets diversity framework for question generation over knowledge bases. In Proceedings of the 34th International Joint Conference on Artificial Intelligence. 8231–8240. [33] Apoorv Saxena, Soumen Chakrabarti, and Partha Talukdar. 2021. Question answering over temporal knowledge graphs. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing. 6663–6676. [34] Dominic Seyler, Mohamed Yahya, and Klaus Berberich. 2015. Generating quiz questions from knowledge graphs. In Proceedings of the 24th The Web Conference. 113–114. [35] Dominic Seyler, Mohamed Yahya, and Klaus Berberich. 2017. Knowledge questions from knowledge graphs. In Proceedings of the 7th ACM SIGIR International Conference on Theory of Information Retrieval. 11–18. [36] Aaditya Singh et al. 2025. OpenAI GPT-5 system card. arXiv preprint arXiv:2601.03267 (2025). [37] Qiang Sun et al. 2025. TimelineKGQA: A comprehensive question-answer pair generator for temporal knowledge graphs. In Companion Proceedings of the 34th The Web Conference. 797–800. [38] Qwen Team. 2024. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115 (2024). [39] Marc Vilain, Henry Kautz, and Peter Van Beek. 1990. Constraint propagation algorithms for temporal reasoning: A revised report. In Readings in Qualitative Reasoning About Physical Systems. Morgan Kaufmann, 373–381. [40] Kun Xu et al. 2018. Graph2Seq: Graph to sequence learning with attention-based neural networks. arXiv preprint arXiv:1804.00823 (2018). [41] Jie Zeng and Yukiko I Nakano. 2020. Exploiting a large-scale knowledge graph for question generation in food preference interview systems. In Companion Proceedings of the 25th International Conference on Intelligent User Interfaces. 53–54. [42] Jinchuan Zhang et al. 2025. Historically relevant event structuring for temporal knowledge graph reasoning. In Proceedings of the 41st IEEE International Conference on Data Engineering. 3179–3192. [43] Tingyi Zhang et al. 2024. MusTQ: A temporal knowledge graph question answering dataset for multi-step temporal reasoning. In Findings of the 62nd Annual Meeting of the Association for Computational Linguistics. 11688–11699. [44] Runhao Zhao et al. 2024. Zero-shot knowledge graph question generation via multi-agent LLMs and small models synthesis. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management. 3341–3351. [45] Zhipu AI. 2025. GLM-4.6. Zhipu AI release. https://www.zhipuai.cn/en/research/ 144 [46] Mantong Zhou, Minlie Huang, and Xiaoyan Zhu. 2018. An interpretable reasoning network for multi-relation question answering. In Proceedings of the 27th International Conference on Computational Linguistics. 2010–2022.