Let the Agent Search: Autonomous Exploration Beats Rigid Workflows in Temporal Question Answering

Xufei Lv, Jiahui Yang, Haoyuan Sun, Xialin Su, Zhiliang Tian, Yifu Gao, Linbo Qiao, Houde Liu

TL;DR

AT2QA is a training-free, autonomous LLM agent framework for Temporal Knowledge Graph Question Answering (TKGQA) that ditches rigid, human-designed reasoning workflows in favor of iterative, self-correcting exploration. By equipping an off-the-shelf LLM with a structured temporal search tool and a novel training-free experience mining strategy, it achieves new state-of-the-art performance across multiple benchmarks without any parameter updates.

What Problem Does This Paper Address?

Temporal Knowledge Graphs (TKGs) map real-world facts that change over time by structuring data as quadruples: <subject, relation, object, timestamp>. Answering natural language questions over these graphs (TKGQA) is highly challenging because it requires multi-hop reasoning while satisfying complex, multi-granular temporal constraints (e.g., figuring out what happened before, during, or after specific events).

Current approaches generally fall into two categories, both with significant drawbacks:

  1. Traditional embedding-based methods: These map facts into low-dimensional vector spaces but struggle to capture the complex semantics of natural language temporal constraints.
  2. LLM-based workflows: These rely on rigid, human-designed pipelines (like fixed question decomposition) or computationally expensive post-training (Supervised Fine-Tuning or Reinforcement Learning).

Because these rigid pipelines separate reasoning from graph exploration, they suffer from cascading errors. If an early retrieval step fails or returns noisy facts, the error propagates through the entire workflow without any mechanism for self-correction, ultimately leading to an incorrect final answer.

Methods

The authors propose AT2QA (Autonomous and Training-free Agent for TKG Question Answering), a framework that treats the LLM as an active agent interacting with the TKG environment rather than a passive pipeline component.

  • Tool-Augmented Autonomous Reasoning: AT2QA equips an off-the-shelf LLM with a generic, structured temporal search tool. The tool handles semantic ranking (via dense retrieval embeddings) and symbolic filtering (by time windows, entities, and relations). Instead of following a hard-coded path, the LLM autonomously decides what to search for next, evaluates the retrieved evidence, and dynamically reformulates its queries if it encounters contradictions or insufficient data.
  • Training-Free Experience Mining: To boost the agent's performance without expensive gradient updates, the authors introduce a trajectory optimization strategy inspired by Group Relative Policy Optimization (GRPO). They sample multiple interaction traces via stochastic decoding, filter for successful trajectories using rule-based rewards (exact match), and use the LLM to rank them by instructional value. The top-performing trajectories are distilled into a compact, high-value few-shot demonstration library ($K=3$) used during test-time inference.

Datasets

The framework was evaluated on three challenging TKGQA benchmarks:

  • MultiTQ: A large-scale dataset (~500K question-answer pairs) spanning multiple temporal granularities (years, months, days) and featuring both single- and multiple-answer questions.
  • Timeline-CronQuestion: A benchmark focused on timeline-centric temporal reasoning, temporal arithmetic, and semantic operations over intervals.
  • Timeline-ICEWS-Actor: An event-centric dataset focusing on political interactions, actor positions, and temporally evolving relations.

Key Insights and Ideas

  • LLMs are naturally proficient planners: The authors discover that modern off-the-shelf LLMs are already smart enough to navigate complex temporal constraints independently. The bottleneck in prior work wasn't the model's reasoning capacity, but rather the lack of an appropriate interface allowing the model to exercise autonomy.
  • Eliciting latent capabilities beats fine-tuning: Through a Pass@k analysis, the authors show that for difficult queries where the model initially fails, repeated sampling ($k=10$) successfully retrieves the correct answer. This indicates that the correct reasoning paths already exist within the model's latent space; they just need to be stably triggered using optimized few-shot prompts rather than costly parameter updates.
Figure 3: Pass@k analysis of our method. In a zero-shot setting, our method achieves >84% Pass@1 accuracy. For difficult queries that initially fail, repeated sampling (k = 10) successfully retrieves the correct answer, sug- gesting the reasoning capability is present but dormant.
  • Emergence of Self-Correction and Self-Validation: Trajectory logs reveal that in ~32% of successful complex queries, the correct "gold fact" isn't surfaced until the latter half of the interaction rounds. This proves the agent actively recognizes early retrieval failures and adjusts its search constraints rather than hallucinating an answer based on noisy context.

Key Results

AT2QA achieves remarkable performance gains over existing state-of-the-art (SOTA) methods, despite being entirely training-free:

  • MultiTQ: Achieves an overall accuracy of 88.7%, outperforming the previous best fine-tuned model (Temp-R1) by 10.7 absolute points. On complex multiple-answer questions, it beats the baseline by a staggering 20.1 points (75.1% vs 55.0%).
  • Timeline-CronQuestion & Timeline-ICEWS-Actor: Reaches 75.4% accuracy on both datasets, outperforming Temp-R1 by 4.9 and 11.2 absolute points, respectively.
Figure 2: Performance comparison on the MultiTQ benchmark. In a zero-shot setting, the autonomous LLM agent surpasses existing baselines, highlighting the effi- cacy of unlocking the model’s inherent decision-making capabilities.

Ablation studies confirm that autonomy is the primary driver of these improvements: simply switching from a rigid workflow to an autonomous agent framework yields a +7.7 point boost, while the mined few-shot demonstrations add an extra +4.3 points.

Limitations and Future Work

  • Efficiency and Latency: Because AT2QA allows up to $T_{max} = 20$ interaction turns to ensure robust self-correction, it inherently increases latency and API inference costs compared to single-pass RAG or fixed pipelines.
  • Exploration Instability: Granting full autonomy can occasionally cause the LLM to enter redundant exploration loops or become distracted by ambiguous queries.
  • Future Directions: The authors suggest exploring more efficient indexing methods (such as Approximate Nearest Neighbors) and developing smarter turn-level early stopping policies to optimize the trade-off between accuracy and computational overhead.

Summary updated

Abstract

Temporal Knowledge Graph Question Answering (TKGQA) is challenging because it requires multi-hop reasoning under complex temporal constraints. Recent LLM-based approaches have improved semantic modeling for this task, but many still rely on fixed reasoning workflows or costly post-training, which can limit adaptability and make error recovery difficult. We show that enabling an off-the-shelf Large Language Model (LLM) to determine its next action is already effective in a zero-shot setting. Based on this insight, we propose AT2QA, an Autonomous and Training-free Agent for TKG Question Answering. AT2QA empowers the LLM to iteratively interact with the TKG via a generic search tool, inherently enabling autonomous exploration and dynamic self-correction during reasoning. To further elicit the LLM's potential for complex temporal reasoning, we introduce a training-free experience mining mechanism that distills a compact few-shot demonstration library from successful self-generated trajectories. AT2QA also yields a transparent audit trail for every prediction. Experiments on three challenging benchmarks -- MultiTQ, Timeline-CronQuestion, and Timeline-ICEWS-Actor -- show that AT2QA achieves new state-of-the-art performance, surpassing the strongest baselines by 10.7, 4.9, and 11.2 absolute points, respectively. Our code is available at https://github.com/AT2QA-Official-Code/AT2QA-Official-Code
BibTeX
@misc{lv2026let,
  author = {Xufei Lv and Jiahui Yang and Haoyuan Sun and Xialin Su and Zhiliang Tian and Yifu Gao and Linbo Qiao and Houde Liu},
  title = {{Let the Agent Search: Autonomous Exploration Beats Rigid Workflows in Temporal Question Answering}},
  year = {2026},
  eprint = {2603.01853},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.01853},
}
Figure