TRACE: Tracing Temporal Constraints for Complex Temporal Knowledge Graph Question Answering

Abstract

Complex temporal knowledge graph question answering (TKGQA) requires composing multiple time-dependent facts under constraints such as validity intervals, temporal ordering, overlap, and set-style operations. Recent LLM-based approaches improve temporal reasoning through retrieval, decomposition, or planning, but the temporal constraints produced during intermediate reasoning are often left implicit: retrieved evidence may be temporally invalid, intermediate answers may be propagated without verification, and deterministic temporal operations may still be handled by free-form generation. We propose TRACE, a temporal-constraint-aware recursive framework that traces temporal constraints across retrieval, answer verification, constraint propagation, and execution. TRACE grounds temporal anchors and operators from sub-questions and intermediate answers, performs operator-aware temporal retrieval, verifies child-derived answers using grounding, bridge evidence, and operator consistency, and invokes symbolic temporal execution when root-level temporal operations are deterministically resolvable. Experiments on MultiTQ and TimelineKGQA show that TRACE improves multi-step and operator-sensitive temporal reasoning under the evaluated settings. Detailed analyses further show that verified answer propagation reduces error accumulation, while symbolic temporal execution is particularly effective for compositional temporal relations such as intersection and union. These results demonstrate that complex TKGQA benefits not only from retrieving or decomposing temporal questions, but also from explicitly tracing, verifying, and executing temporal constraints throughout the reasoning process.