CoSTA improves answering complex timeline questions on knowledge graphs
CoSTA: Co-Evolving Self-Play Timeline Agents for Complex Temporal Knowledge Graph Question Answering
Computation and Language
Summary
Answering questions about events over time can be tricky when multiple facts rely on each other and have specific time spans. The authors propose CoSTA, a method that uses multiple agents to look at different timelines separately and work together to find the best answer. These agents learn to coordinate through a training process that rewards correct final answers. CoSTA performs better than previous methods, especially on questions needing multiple facts to be combined correctly.
What this means in practice
- •For knowledge graph engineers: Improve automated reasoning over event sequences by distributing fact analysis across collaborative timeline agents.
- •For chatbot developers: Enhance temporal question answering capabilities in conversational AI by integrating co-evolving multi-agent timeline reasoning.
Authors
Haikun Liu, Zhichao Yan, Shaoru Guo, Jiawei Gu, Victor Gutierrez Basulto, Jiapu Wang, Ru Li
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.