EvoLinkBench: A Benchmark and Framework for Knowledge Graph Self-Evolution in Memory-Augmented Agents

Agent memory is evolving from transient, one-off contexts toward continuously updatable long-term memory. Existing research on self-evolving memory primarily focuses on how systems distill and update experiences, reflections, and strategies from interaction trajectories. In contrast, graph-based memory that stores factual and semantic knowledge often remains relatively static after initialization, and whether its internal structure can be actively reorganized based on existing evidence remains underexplored. Specifically, local graph construction methods struggle to uncover implicit relations that can only be inferred by jointly reasoning over multiple distant text chunks, causing breaks in multi-hop evidence chains and ultimately leading to question-answering failures. We argue that knowledge graphs should likewise support self-evolution by reorganizing their existing structures and persistently writing back verified relations inferred across text chunks, thereby improving relational coverage and evidence connectivity. To study this problem, we introduce EvoLinkBench, a benchmark for evaluating graph self-evolution. EvoLinkBench employs a latent-graph-driven construction process to generate source texts and multiple categories of cross-chunk questions that require reasoning over implicit evidence chains, enabling the evaluation of both relation discovery and its impact on downstream question-answering performance. Building on this benchmark, we propose Evidence-Chain-Linked Relation Recovery (ECLRR). Given an initial static graph, ECLRR searches for candidate paths that satisfy predefined type constraints and assembles the original textual evidence associated with each hop. It then generates candidate relations, subjects them to independent verification, and writes the verified implicit relations back into the graph. Experimental results demonstrate that ECLRR effectively discovers implicit relations supported by long-range evidence chains and improves the performance of graph-augmented systems on downstream multi-hop question answering and implicit-relation reasoning tasks.