acceptodds
Under review as a conference paper at ICLR 2027

Faithful Evidence by Construction for Temporal Knowledge Graph Reasoning

Abstract

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/.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Temporal knowledge graphs, Large language models, Symbolic execution

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1M3NOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes FaiTH, a training-free framework for temporal knowledge graph question answering (TKGQA). It follows a four-stage compile-ground-execute-reason pipeline and guarantees at most two LLM calls per question. The authors evaluate FaiTH on MultiTQ and two TimelineKGQA benchmarks across 11 LLM backbone configurations.

Critical strengths

S1. The paper clearly identifies and formalizes two key failure modes in TKGQA, namely unfaithful evidence and hallucination accumulation caused by multiple LLM calls, and the proposed pipeline provides targeted design responses to both. S2. The two-call LLM budget and the deterministic shortcut balance faithfulness and inference cost, making the method practically useful. S3. The experiments cover multiple benchmarks, diverse backbone configurations, and ablation settings, providing relatively strong empirical support for the effectiveness of the method.

Critical weaknesses

W1. The related work is largely enumerative, especially the Embedding and GNN methods section, and fails to clearly delineate the essential differences between this work and prior methods. W2. The explanations of key equations are insufficient. In particular, Eq. (6) is obscure in its notation, matching rules, and confidence cascade, which hurts readability. W3. The proofs of Theorem 1 and Theorem 2 mainly restate the set-membership conditions in Eqs. (8)–(12). The theoretical contribution is limited, and calling them theorems seems somewhat overstated. W4. Although the method significantly reduces the number of LLM calls, it does not report inference time, token consumption, or end-to-end latency, making it difficult to judge whether its efficiency truly improves over existing methods.

Questions for authors

D1. Provide a more detailed description of the related work, emphasizing the differences between the existing work and the work presented in this paper. D2. Please explain why the boundary tie-preserving cap is the “only” permitted source of information loss under the completeness clause of Definition 3. Also explain how ties among boundary candidates are broken, whether the tie-breaking is random, and whether it affects reproducibility. D3. The description of the formula needs to be improved for better comprehension. D4. It is necessary to add experimental descriptions of the consumption (or inference time) of the entire model, and clarify the efficiency difference between the method proposed in this paper and existing methods. D5. The paper emphasizes that multiple LLM calls lead to hallucination accumulation. It would be helpful to provide concrete failure cases alongside corresponding FaiTH examples to show how this problem is actually mitigated by the pipeline.
D6. If Theorem 1 and Theorem 2 are retained, please clarify the source of their non-triviality and discuss the limitations imposed by Assumption 1. Otherwise, they could be downgraded to propositions or consistency claims.

2 comments

Thank you for the constructive comments and for recognizing the two failure modes we formalize and the practical value of the two-call budget. The revised PDF (changes in blue) implements all six requests D1 to D6.

W1/D1. Related work. Sec. 2 now closes each family with its difference from FaiTH. Embedding and GNN methods rank the answer vocabulary with a trained scorer. Retrieve-then-reason pipelines and agents let the LLM apply temporal constraints over top-k retrieval. FaiTH executes these constraints as exact set operations before any LLM reads the evidence, and it needs no training. A new paragraph covers semantic parsing (Prog-TQA, TECQA), and App. A adds a side-by-side table (Table 5).

W2/D3. Eq. (6). We rewrote Eq. (6) and its explanation. Each rule returns the KG symbols a mention matches, with a match score that scales the rule weight. Rules are tried from the most to the least restrictive, and the first rule that fires decides. For example, "Governor of Thailand" equals no entity, and the Role (Country) rule maps it to "Governor (Thailand)". Table 7 lists the seven rules: on MultiTQ the three exact rules decide 97.58% of anchor mentions.

W3/D6. Theorems. We agree and renamed them Propositions, and App. B.6 now states their scope. They are short by design, because the operators are written to coincide with Definitions 1-2. Their value is that faithfulness becomes a set property that can be checked fact by fact and holds for every backbone. It is also testable: an exhaustive check over 38,182 questions with one executed relation finds no consistent fact missing (App. C.17). Their limits are their premises: a wrongly grounded mention or a wrongly compiled constraint makes the engine execute a wrong specification faithfully. Assumption 2 therefore makes correct compilation explicit. App. C.9 attributes 4.05% of errors to failed groundings, and 97.11% of specifications pass all checks of new App. C.15.

W4/D4. Time, tokens and latency. App. C.3 now reports them. We priced and timed FaiTH and RTQA on the same API model (deepseek-flash), replaying RTQA's own prompts. RTQA's calls and tokens come from our DS-V3.2 re-run, where its released code makes one decomposition call plus up to three per node (its paper reports 3.96, still 2.9x FaiTH's 1.35).

Table R1. Cost per MultiTQ question (off-peak list price, FaiTH latency on 300 stratified questions)

Per questionFaiTHRTQARatio
LLM calls1.35 (max 2)6.034.47x
All tokens (uncached prompt)5,502 (264)7,899 (2,615)1.44x (9.90x)
Cost (CNY x 1e-3)0.6715.9188.82x
Sequential latency1.54 s11.33 s (7.29 s parallel)7.35x (4.73x)

FaiTH's compile-prompt prefix is shared by all questions, so 95% of its prompt tokens hit the prefix cache. Stages 2-3 take 5.56 ms on average. For reference, TECQA issues 4 LLM calls per question.

D2. The cap, ties and reproducibility. Your question led us to remove this exception. Definition 3 now states soundness and completeness on the complete evidence set, and Eq. (12) has no cap. The bound is an evidence budget for Stage 4 (per benchmark: App. B.3). On MultiTQ it only limits how many facts the optional reason call reads: candidates, tie groups and every shortcut answer use the complete set. This corrects the description, and no reported number changes. On ties: most boundaries hold a single candidate (83.17% of ordering-directed MultiTQ entity questions). The reported runs ordered a tie group by the full timestamp and broke equal timestamps arbitrarily. Two arbitrary orders change the number of correct shortcut answers by 24 (0.044 points), a small effect on score reproducibility. The revision breaks equal timestamps by subject, relation and object, so tie-breaking now involves no randomness.

D5. Concrete multi-call failures. New App. C.19 pairs FaiTH (DS-V4-Flash) with our RTQA re-run (DS-V3.2) on MultiTQ under the same scoring code. On the 20,119 questions RTQA decomposes, FaiTH scores 70.86 vs 42.01, with 1.24 vs 9.50 LLM calls. When RTQA's first sub-answer comes from its closed-book branch (no retrieved facts), its final Hits@1 drops from 44.25 to 12.55. One of two appendix cases from a random sample of ten questions RTQA misses and FaiTH answers:

  • Q: Who suffered from the conventional military forces of the Russian military after Iraq? (gold: France, Combatant (Jabhat al-Nusra))
  • RTQA: step 1 dates the Iraq event correctly (2015-11-05). Step 2 retrieves both gold facts, but its arbitration call keeps the closed-book guess "Syrian rebels (and ISIS)" as the final answer.
  • FaiTH: one specification (anchor Military (Russia), relation Use conventional military force, after the Iraq event) returns exactly these two facts and answers correctly.

Table 4 agrees: forcing a reason call on every question lowers MultiTQ from 0.826 to 0.789 and TL-ICEWS from 0.696 to 0.456.

We welcome further questions.

Dear Reviewer 1M3N,

Thank you again for your constructive comments. We would like to gently mention that our response is posted above, and that the revised PDF, with changes marked in blue, implements your six requests D1 to D6. These include the reworked related work and Eq. (6), the report on cost and latency, and the concrete failure cases of multi-call pipelines. If any point needs more explanation, we would be glad to provide it while the discussion is open.

Thank you very much for your time.

Reviewer_b3xPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents FaiTH, a TKGQA framework. A single LLM call compiles a question into a dataset-agnostic constraint specification; a deterministic cascade performs entity and relation grounding; a symbolic engine runs role-aware retrieval, granularity-aware temporal filtering, event alignment, and multi-event composition, producing an evidence set that is provably faithful in both structure and time; answers are then generated adaptively with zero or one additional LLM call. The evaluation covers three benchmarks, eleven backbone configurations, and nine base models, reaching 0.852 Hits@1 on MultiTQ. The paper also supplies the theorems and proofs, component ablations, error attribution, evidence coverage, API cost, and a recovery subroutine.

Critical strengths
  1. Faithfulness is formalized for the first time and guaranteed by construction. Definitions 1–2 (structural and temporal consistency) and Theorems 1–2 provide a checkable evidence-level guarantee. The ablations support this: removing role constraints or temporal filtering causes a large drop (0.716 to 0.152 on multi-constraint questions), directly showing that the symbolic components are needed. Error attribution finds that grounding failures account for only 4.05% and that retrieval misses are the main error source, which is honest and traceable.
  2. The empirical work is substantial and the system is practical. The comparison spans three benchmarks, eleven backbones, and nine base models, and on MultiTQ multi-constraint questions it scores 0.722 against the prior best of 0.550. It uses at most two LLM calls per question, costs under 30 dollars across all three test sets, and the quantized model is competitive with cloud models.
Critical weaknesses
  1. The methodological novelty is limited and largely combinatorial. Constraint decoding and graph-constrained faithful reasoning already exist; the increment here is mainly the temporal formalization and engineering integration. TECQA at ACL 2026 also builds “temporal evidence chains” through structure-guided retrieval and reports state-of-the-art results on MultiTQ and CronQuestions, but it is neither cited nor compared.
  2. The faithfulness guarantee covers soundness but not completeness. Evidence coverage is only 88.2%, and about 11.8% of questions have no answer in the evidence set, with retrieval misses accounting for 37.83% of all errors. The title “faithful by construction” is easily misread as guaranteeing answer correctness.
Questions for authors
  1. Could you add a comparison with TECQA (ACL 2026) under the same protocol? What is the fundamental difference between the symbolic specification and temporal-evidence-chain retrieval?
  2. For the 11.8% of questions whose evidence set contains no answer, how can completeness be improved without breaking faithfulness? Have you considered controlled evidence expansion?
  3. Why are the time answers worse than TimeR4/Temp-R1? Is it the temporal compilation granularity, boundary extraction, or the ranking module?
2 comments

Thank you for recognizing the formalization of faithfulness, its supporting ablations, and the breadth of the evaluation. The revised PDF marks changes in blue.

Q1/W1. TECQA and the fundamental difference. As you suggested, the revised PDF now cites TECQA (ACL 2026) and compares with it (Sec. 2 and 5.2, new App. A.4 and C.13). TECQA reports Hits@1 on the same MultiTQ test set, the benchmark both papers share, for ten backbones: non-reasoning (0.571 to 0.774) and reasoning models (0.806 to 0.854). Table R1 shows three, App. C.13 all ten.

Table R1. TECQA vs FaiTH on MultiTQ (TECQA: its Table 4, FaiTH: Table 1)

System (LLM)OverallMultipleEntityTime
TECQA (DeepSeek-v3-0324, non-reasoning)0.7740.4250.7050.926
TECQA (Qwen3-8B thinking, main)0.8110.6160.7530.939
TECQA (Gemini-3-Pro-Preview, best)0.8540.6890.8030.968
FaiTH (DS-V3.2)0.8260.7160.8170.847
FaiTH (GPT-5.4)0.8520.7220.8300.908

FaiTH runs every backbone without thinking mode, with 1.34 to 1.35 LLM calls per question against TECQA's 4 (its App. F). With GPT-5.4 it is on par with TECQA's best backbone overall (0.852 vs 0.854), and both FaiTH rows are ahead of all ten TECQA backbones on Multiple and entity answers. Without a thinking mode, TECQA scores 0.231 to 0.425 on Multiple (4 backbones) and FaiTH 0.611 to 0.725 (11 backbones, Table 13). TECQA is ahead on time answers (Q3).

The difference lies in who applies the temporal constraints. TECQA retrieves by structure, keeps the facts nearest to anchor dates, and lets its LLM apply the constraints. FaiTH executes the compiled constraints exactly over the whole KG, including first and last boundaries. TECQA's truncation case illustrates this (its Table 10, "In which month did the African Union last ask Ethiopia?"). Its chain ends at 2007-06, and it answers 2006-12. FaiTH takes the boundary over the complete consistent set and returns the gold 2008-12 with one LLM call.

On novelty, constrained decoding and graph-constrained reasoning restrict what an LLM may generate along KG paths. They leave open when timestamped facts satisfy the temporal constraints of a question. Definitions 1-3 answer this at the evidence level, to our knowledge for the first time in TKGQA. Stage 3 enforces them, so filtering and sorting by time happen before the LLM reads the evidence, and after the compile call the engine answers about two thirds of questions (Sec. 5.2).

W2/Q2. Completeness and controlled expansion. We agree on the scope and on the risk of misreading. The guarantee concerns the evidence for the compiled specification, as the abstract, introduction and limitations now state. A correct answer also needs correct compilation and grounding, and Sec. 4.3 adds a compilation assumption. Completeness has two readings. Against the specification it is part of the guarantee: Definition 3 now names a soundness and a completeness clause, and an exhaustive check over 38,182 questions finds no consistent fact missing (App. C.17). Against the gold answer it is the 88.2% you cite, and the uncovered questions mostly trace back to the specification:

Table R2. Why the gold answer is missing from the rendered evidence (81.93% run, % of uncovered)

CauseShare (%)
Specification matches no fact38.5
Wrong relation, role, window, anchor or reference17.1
First candidate relation executed, gold under another14.8
Evidence budget of the reason call14.0
Reference-event dating9.0
Other6.6

Rows 1 and 2 arise before the engine. Naming KG relations at compile time (V1, App. C.16) lowers empty evidence from 5.57% to 3.34% of questions and gains 5.30 points of Hits@1 in paired deepseek-flash runs. For row 3, the controlled expansion you suggest helps. A second, labeled tier adds the facts of the other probed candidate relations under the same role and window. Tier 1 remains the faithful set, so the guarantee is unchanged. In such paired runs Hits@1 rises from 81.22 to 81.96 on the full test set (p = 5.7e-25, same LLM calls) and from 72.51 to 81.18 on the 4,267 questions with a non-empty tier 2.

Q3. Time answers. We tested your three hypotheses (new App. C.18). Together they explain about 15% of the 2,068 wrong time answers of the Table-1 run:

Table R3. Wrong time answers by first cause

CauseShare (%)
Compiled granularity0.3
Boundary extraction10.8
Ranking (relation order)4.1
Specification matches no fact52.3
Named participant dropped11.4
Other specification fields21.1

The gap lies mainly upstream of the engine. When the specification matches no fact, exact execution returns no evidence, while a top-k retriever always returns facts. Surface-cue repairs with no LLM call, designed on a different run, raise time Hits@1 from 86.98 to 89.11.

We welcome further questions.

Dear Reviewer b3xP,

Thank you again for your thoughtful review. This is a short and friendly note that our response is posted above, together with a revised PDF in which the changes are marked in blue. As you suggested, the revision now cites TECQA and compares with it, and it also covers your points on completeness and on time answers. We would be happy to answer any further question while the discussion is open.

With sincere thanks for your time and consideration.

Reviewer_6VdnOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes FaiTH, a training-free framework for temporal knowledge graph question answering (TKGQA) consisting of four stages: compile, ground, execute, and reason. The experiments are conducted on MultiTQ and two TimelineKGQA benchmark. FaiTH achieves Hits@1/10 scores comparable to or higher than the best previously published results.

Critical strengths
  1. Substantial improvements on multi-constraint questions. On the Multiple category of MultiTQ, FaiTH achieves scores of 0.699–0.722 across multiple backends (0.550 for Temp-R1). This gap supports the claim that explicit temporal constraint execution is effective for compositional questions.
  2. Controllable costs and LLM call counts. Each question consumes at most two LLM calls by construction. No training or fine-tuning is required.
  3. Thorough and transparent empirical analysis. The evaluation includes main results, ablation studies, robustness tests, etc.
Critical weaknesses

Major:

  1. The practical guarantees of the faithfulness theorems are limited and do not match the claims in the main text. Faithfulness is defined relative to the compiled specification C^q\hat{C}_q rather than original question qq. Assumption 1 only assumes correct grounding; it does not assume correct compilation. Therefore, claims such as “provably faithful evidence set” seems suggest stronger guarantees than the theoretical results actually establish.
  2. The Relationship to Program Generation and Semantic Parsing Approaches in TKGQA Is Not Clearly Established. Several existing works have explored semantic parsing-based approaches [1-2] or incorporated temporal scorer [3].
  3. Experiment settings. All baseline results are taken from the original papers, as indicated in the captions of Tables 1 and 2. These methods use early models, whereas FaiTH uses newer and more powerful models. Appendix C.2 indicates that the correctness is determined by type-aware string matching (string containment), however, some entities in the dataset may be prefixes of other entities.
  4. The Stage 1 prompt explicitly enumerates the six question types in MultiTQ. The Stage 2 rule tables for MultiTQ are all tailored to specific datasets.

Minor:

  1. How many questions in the test sets undergo the recovery procedure in Appendix B.5? What is the accuracy on these questions?
  2. Could the authors rerun a strong baseline using at least one shared backend, such as DS-V4, and the same answer-matching rules?
  3. What's the results of recent semantic parsing approaches like Prog-TQA on MultiTQ?

[1] Temporal Evidence Chain for Temporal Knowledge Graph Question Answering with Large Language Models

[2] Self-Improvement Programming for Temporal Knowledge Graph Question Answering

[3] Temporal knowledge graph question answering via subgraph reasoning

Questions for authors

See above.

3 comments

Thank you for the careful review and for recognizing the multi-constraint gains, the bounded LLM calls, and the transparent analysis. The revised PDF marks changes in blue.

M1. Faithfulness is relative to the compiled specification. We agree. The abstract and conclusion now read "provably faithful to the compiled specification", and the introduction states this scope. Theorems 1-2 are now Propositions 1-2 and certify the evidence against the grounded specification under Assumption 1. A new Assumption 2 states correct compilation, and Sec. 4.3 says the propositions carry over to the question only when it holds as well. The engine cannot certify either assumption, so we measure both. App. C.9 attributes 4.05% of errors to failed groundings, and M4 quantifies the choice of the relation. For compilation, new App. C.15 runs necessary checks on every specification:

Table R1. Specification vs annotations and question cues (Table-1 run, DS-V4-Flash, n = 54,584)

CheckAgree (%)
Answer type / granularity100.00 / 99.98
Ordering / window bounds99.94 / 99.99
Window type / named participants97.77 / 99.34
All checks pass97.11

Hits@1 is 82.39 when all checks pass and 58.44 otherwise.

M2 and m3. Semantic parsing and program generation. The revised PDF cites all three papers you list and relates FaiTH to each (Sec. 2, App. A.1, new App. A.4, Table 5). Prog-TQA [2] executes generated KoPL programs. FaiTH also executes a compiled form symbolically. It differs in its target, a closed, typed specification that needs no fine-tuning, and in its output, an evidence set with stated soundness and completeness. TECQA [1] lets an LLM apply the temporal constraints over a subgraph pruned by temporal proximity, whereas FaiTH applies them in the engine, over the complete consistent set. SubGTR [3] fuses a trained semantic score with temporal activation scores, whereas FaiTH executes the constraints exactly and needs no training. For m3, Sec. 5.2 and new App. C.13 give the published MultiTQ results of [1] and [2] ([3] reports none), with all ten TECQA backbones:

Table R2. Published MultiTQ Hits@1 (FaiTH: Table 1)

Method (LLM)OverallMultiple
Prog-TQA (13B LLM), in-context only0.5830.379
Prog-TQA, fine-tuned (LoRA, 100k)0.7970.750
TECQA (DeepSeek-v3-0324, non-reasoning)0.7740.425
TECQA (Qwen3-8B thinking, main)0.8110.616
TECQA (Gemini-3-Pro-Preview, best)0.8540.689
FaiTH (DS-V3.2)0.8260.716
FaiTH (GPT-5.4)0.8520.722

FaiTH needs neither training nor a thinking mode. With GPT-5.4 it is on par with TECQA's best backbone overall, with 1.35 LLM calls against 4, and has the highest Multiple score of the training-free rows. Prog-TQA is higher on Multiple after fine-tuning (0.750). Without fine-tuning it reaches 0.379, and all eleven FaiTH backbones, eight of them local, score 0.611 to 0.725 (Table 13).

M3 and m2. Shared backend and matching. We re-ran the official RTQA code with DS-V3.2 and scored both systems with the same code (new App. C.14). With this shared backbone FaiTH reaches 82.60 Hits@1 against 69.98 for RTQA (76.5 in its paper, with GPT-4o-mini and DeepSeek-V3). Table R3 adds strict top-1, which normalizes both systems alike, keeps the first answer, and requires equality with a gold answer.

Table R3. Strict matching (same scoring code, MultiTQ test, n = 54,584)

System (backbone)Hits@1Strict top-1
RTQA re-run (DS-V3.2)69.9867.55
FaiTH (DS-V4-Flash)81.7079.11

Both systems lose about 2.5 points (FaiTH 0.5 on Multiple), so the margin stays. The prefix case you describe, another KG entity whose name contains the gold string, credits 82 questions (0.15 points).

M4. Dataset-specific prompt and tables. New App. C.16 removes or replaces them step by step in paired runs.

Table R4. Paired new runs (deepseek-flash, n = 54,539 distinct questions)

VariantHits@1Multiple
Standard pipeline81.2169.90
No question types in the prompt81.7769.88
V1: KG relation names, no relation table86.5175.98
V2: also LLM-generated entity tables85.4274.36

In V1 the compiler copies relation names from the KG relation list in the prompt. V2 uses no handcrafted synonym or entity table. Each variant gains over the standard pipeline (McNemar p < 1e-8). A generic prompt with 8 synthetic examples and no MultiTQ type or example gains 0.85 points on 6,000 stratified questions (p = 0.013). These runs are variants, and the main tables are unchanged.

m1. Recovery (App. B.5). On the Table-1 run, 2,832 questions (5.19%) enter recovery. It finds evidence for 1,495 of them, which reach Hits@1 54.72. Over all 2,832 it is 28.88, so recovery adds 1.50 points. On TL-ICEWS and TL-Cron, 12 and 19 questions enter it, and none is answered correctly.

We welcome further questions.

Dear Reviewer 6Vdn,

Thank you again for your careful review. We know this is a busy period, so this is only a gentle note that our response is posted above and that a revised PDF is uploaded, with changes marked in blue. Together they address the scope of the faithfulness guarantee, the three related papers you listed, the comparison under a shared backbone with strict matching, and the dataset-specific components. If anything remains unclear, we would be glad to clarify while the discussion is open.

Thank you for your time.

Thanks for the additional experiments. I will raise the score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.