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:
- Evidence Entanglement: When an agent searches for multiple facts in a single reasoning context, evidence from different event histories gets interleaved, leading to confusion.
- Distractor Interference: Irrelevant but similar facts (like other UK Prime Ministers) can easily derail a single agent's search.
- 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.
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.
Datasets
The model was evaluated on three major TKGQA benchmarks:
- MultiTQ: Focuses on various temporal granularities (day, month, year).
- TimelineKGQA-CronQuestion: Based on the CronQuestions dataset, categorized by the number of supporting facts (Simple, Medium, Complex).
- 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.
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