Faithful Evidence by Construction for Temporal Knowledge Graph Reasoning

Temporal knowledge graph question answering (TKGQA) requires natural language understanding together with explicit temporal reasoning over facts annotated with timestamps or intervals. State-of-the-art methods follow a retrieve-then-reason paradigm that gathers evidence by dense retrieval and delegates reasoning to repeatedly invoked large language models (LLMs), which compounds two failure modes: structurally and temporally unfaithful evidence sets, and unbounded error amplification across multiple LLM calls. We propose FaiTH, a training-free framework organized as a four-stage compile, ground, execute, and reason pipeline. One LLM call compiles the question into a dataset-agnostic specification, a deterministic cascaded grounder resolves mentions to canonical identifiers, a symbolic engine performs role-aware retrieval, granularity-aware temporal filtering, inter-event alignment, and multi-event composition to produce a provably faithful evidence set, and an adaptive reasoner resolves residual ambiguity. Across three heterogeneous TKGQA benchmarks, FaiTH achieves state-of-the-art Hits@1 scores, reaching 0.852 on MultiTQ against 0.780 for the strongest baseline, using at most two LLM calls to answer each question. FaiTH's code and data are anonymously available at https://anonymous.4open.science/r/FaiTH-978E/.