CoSTA: Co-Evolving Self-Play Timeline Agents for Complex Temporal Knowledge Graph Question Answering

Haikun Liu, Zhichao Yan, Shaoru Guo, Jiawei Gu, Victor Gutierrez Basulto, Jiapu Wang, Ru LiarXiv 2026 · arXiv

TL;DR

CoSTA (Co-Evolving Self-Play Timeline Agents) is a new multi-agent framework for answering complex temporal questions by organizing knowledge graph facts into navigable timelines. By training a shared policy for both "Coordinator" and "Worker" roles through co-evolving self-play, the system avoids the "reasoning entanglement" that causes single-agent models to fail on multi-fact temporal dependencies.

What Problem Does This Paper Address?

Temporal Knowledge Graph Question Answering (TKGQA) requires reasoning over facts that are only valid during specific time intervals. While simple questions might only need one fact, complex questions involve dependencies—for example, "When were Stalin, Roosevelt, and the UK PM immediately preceding Attlee all heads of government?"

Existing single-agent methods struggle with these because:

  1. Evidence Entanglement: When an agent searches for multiple facts in a single reasoning context, evidence from different event histories gets interleaved, leading to confusion.
  2. Distractor Interference: Irrelevant but similar facts (like other UK Prime Ministers) can easily derail a single agent's search.
  3. Coordination Failure: Decomposing a question, investigating subtasks, and synthesizing evidence are interdependent. If these roles aren't trained to work together, the system fails to find the precise intersection of time intervals.
Figure 1: Motivating comparison of (a) Traditional TKGQA, (b) Single-agent TKGQA, and (c) Our proposed CoSTA, which coordinates separate timeline investigations and co-evolves the coordinator and workers through self-play.

Methods

The authors propose CoSTA, which treats TKGQA as a coordination problem between a Coordinator and several Workers.

  • Timeline-Centric Collaboration: Instead of a flat search, CoSTA organizes the knowledge graph into chronologically ordered timelines. Workers use "semantic retrieval" to find an entry point and "timeline reading" to move forward or backward in time to find specific neighbors (like a predecessor).
  • Role-Conditioned Distillation: The system uses a single shared policy (an LLM like Llama-3 or Qwen-3) to play both roles. It is first initialized by distilling successful "demonstrations" generated by a larger teacher model.
  • Co-Evolving Self-Play: To optimize the system, the agents play against themselves. Using a reinforcement learning technique called Leave-One-Out PPO (LOOP), the model receives a reward only if the final answer is correct. Because the Coordinator and Workers share the same policy, they "co-evolve"—the Coordinator learns better delegation strategies based on Worker performance, and Workers learn to provide more useful evidence for the Coordinator.
Figure 2: The framework of CoSTA, which initializes a shared policy for the coordinator and workers from teacher demonstra- tions and optimizes it through self-play over timeline-centric collaboration (①–④), enabling the two roles to co-evolve. The reward curve is illustrative.

Datasets

The model was evaluated on three major TKGQA benchmarks:

  1. MultiTQ: Focuses on various temporal granularities (day, month, year).
  2. TimelineKGQA-CronQuestion: Based on the CronQuestions dataset, categorized by the number of supporting facts (Simple, Medium, Complex).
  3. TimelineKGQA-ICEWS-Actor: Based on the Integrated Crisis Early Warning System (ICEWS) data, also categorized by complexity.

Key Insights and Ideas

  • Contextual Isolation is Key: By giving each Worker its own separate context window for investigation, CoSTA prevents the "entanglement" of facts. The Coordinator only sees the final timestamped reports, keeping its reasoning space clean.
  • Original Evidence vs. Summaries: A critical finding was that Workers must return original tool observations (timestamps) rather than just natural language summaries. Summaries often lose the precision needed for the Coordinator to perform interval arithmetic (e.g., intersecting three different time ranges).
  • The "Dance" of Co-Evolution: Training the roles together is significantly more effective than training them independently. As shown in Figure 6, a Coordinator trained via self-play performs best when paired with Workers also trained via self-play, proving that the roles adapt to each other's specific strengths and weaknesses.
Figure 6: Hits@1 (%) on TimelineKGQA when the subtasks and worker messages of each training stage (columns) are synthesized by the coordinator of each stage (rows).

Key Results

CoSTA achieved state-of-the-art (SOTA) results across all benchmarks, with the most dramatic improvements seen in complex, multi-fact questions.

  • Beating the Giants: Compact open-source variants (Qwen-4B and Llama-8B) outperformed massive closed-source models like GPT-6 Astra on all three benchmarks. For instance, on MultiTQ, CoSTA (Llama-8B) reached 89.5% Hits@1, compared to 82.2% for GPT-6 Astra.
  • Complexity Gains: On the most difficult questions (ICEWS-Actor Complex), CoSTA (Qwen-4B) achieved 75.1%, a massive jump over the previous best RL-based agent, Temp-R1, which scored 59.5%.
  • Efficiency: The gains aren't just from "thinking longer." CoSTA outperformed "voting" methods (running a single agent multiple times) while using fewer total tokens, because it spends its "token budget" on distinct subtasks rather than repeating the same global search.

Limitations and Future Work

  • Sparse Rewards: Currently, CoSTA relies on a binary final-answer reward. This "all-or-nothing" feedback can be difficult to scale to extremely long reasoning chains where a single early mistake ruins the whole trajectory.
  • Sample Efficiency: While self-play is powerful, it requires many iterations. Future work could explore incorporating intermediate "process rewards" or step-specific feedback to speed up training without introducing the biases of a human judge.

Summary updated

Abstract

Complex Temporal Knowledge Graph Question Answering (TKGQA) involves more than retrieving facts: the timestamp or validity interval of one fact can constrain the search for another, while multiple intervals may jointly determine the answer. Existing single-agent TKGQA methods typically investigate these facts within a single reasoning context, where evidence from different event histories can become interleaved and distractors can misdirect subsequent retrieval. Distributing investigations across agents can separate event-specific evidence into distinct contexts, but effective collaboration must still be learned because question decomposition, subtask investigation, and evidence synthesis are interdependent. To address these limitations, we propose \textbf{Co}-Evolving \textbf{S}elf-Play \textbf{T}imeline \textbf{A}gents (CoSTA), which organizes facts into navigable timelines, delegates investigations to workers, and uses a coordinator to synthesize their original timestamped observations. CoSTA initializes a shared policy through role-conditioned distillation and jointly optimizes both roles through co-evolving self-play with final-answer rewards. Across three benchmarks, CoSTA achieves state-of-the-art overall performance, with particularly strong gains on complex multi-fact questions, while its compact variants outperform the evaluated closed-source LLM agents.
BibTeX
@misc{liu2026costa,
  author = {Haikun Liu and Zhichao Yan and Shaoru Guo and Jiawei Gu and Victor Gutierrez Basulto and Jiapu Wang and Ru Li},
  title = {{CoSTA: Co-Evolving Self-Play Timeline Agents for Complex Temporal Knowledge Graph Question Answering}},
  year = {2026},
  eprint = {2610.38450},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38450},
}
Figure