{"id":"arxiv:2610.38450","kind":"preprint","title":"CoSTA: Co-Evolving Self-Play Timeline Agents for Complex Temporal Knowledge Graph Question Answering","authors":["Haikun Liu","Zhichao Yan","Shaoru Guo","Jiawei Gu","Victor Gutierrez Basulto","Jiapu Wang","Ru Li"],"author_count":7,"year":2026,"published":"2026-10-28","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2610.38450","nct_id":null,"source_url":"https://arxiv.org/abs/2610.38450","archive_url":"https://space-kitty.com/papers/arxiv:2610.38450","updated":"2026-10-28","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2610.38450","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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":true,"retracted":false,"peer_reviewed":false,"categories":["cs.CL"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"ai-agents","name":"LLM Agents & Tool Use","domain_slug":"ai"}],"cited_in_dossiers":[]}