acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
datasets and benchmarks
Keywords:
Knowledge Graph Self-Evolution, Agent Memory, Graph Retrieval-Augmented Generation, Multi-Hop Reasoning, Relation Discovery

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_tfFuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces EvoLinkBench, a synthetic multi-hop QA benchmark constructed from 10 LLM-generated narratives (359 QA pairs total), along with Evidence-Chain-Linked Relation Recovery (ECLRR) and its query-conditioned variant (Q-ECLRR). The core idea is to search 3-to-8-hop paths in an initial GraphRAG knowledge graph, prompt an LLM Generator and an LLM Judge to summarize/cluster the multi-chunk path into a shortcut edge ("hidden relation" or "retrieval-only evidence bridge"), and persistently write it back into the graph. On top of LightRAG, Q-ECLRR improves multi-hop QA accuracy from 22.98% to 28.40%, and a prompt-based "Safe Routing" switch boosts performance on Selective Forgetting questions.

While consolidating multi-hop evidence into shortcut edges/hyperedges for GraphRAG is a reasonable practical intuition, the paper wraps a heuristic prompt pipeline in grand "self-evolution" terminology without any solid mathematical foundation. Crucially, it omits any accounting of the massive token/computational overhead, fails to evaluate the full offline method it proposes, and ignores stability issues regarding query ordering, train/test splitting, and temporal invalidation. I recommend Weak Reject.

Critical strengths

1.Intuitive problem motivation: Pointing out that standard chunk-based GraphRAG misses cross-chunk multi-hop connections—and that caching verified multi-hop paths as shortcut edges/hyperedges can aid subsequent retrieval—is practically sensible.

2.Traceable provenance design: Distinguishing between semantic endpoint relations and retrieval-only evidence bridges while keeping hop-level text provenance is a useful engineering practice.

Critical weaknesses

1.Lack of Mathematical Principles Behind a Heuristic Prompt Pipeline: Despite the elaborate terminology ("evidence-based graph self-evolution", "deterministic admission gate"), the proposed ECLRR framework is essentially a heuristic path-clustering / hyperedge-closure pipeline on a GraphRAG database: it runs beam search to group entities along 3≤L≤83 \le L \le 8 hops and calls an LLM Generator + LLM Judge with a hand-crafted heuristic threshold (sjudge≥8s_{\text{judge}} \ge 8, Equations 1–7) to form a shortcut edge. The paper does not formulate or analyze the underlying graph-theoretic or mathematical principles (e.g., how path scoring interacts with graph topology, spectral/clustering properties, or error accumulation rates under recursive writeback).

2.Prohibitive Computational & Token Overhead (and Failure to Evaluate Offline ECLRR): Searching and clustering multi-hop paths over a graph incurs O(N2)O(N^2) to O(N3)O(N^3) (or O(NbL)O(N b^L) for LL-hop beam search) complexity. Indeed, in Section 3.3 and Section 5 (Limitation 3), the authors admit that full offline ECLRR was not even systematically evaluated because the graph-wide search and LLM verification costs are too high! Even after retreating to the online query-conditioned sampling variant (Q-ECLRR), each query triggers entity linking, 3–8 hop path search, chunk assembly, LLM Generator proposal, and LLM Judge verification. This incurs substantial extra token consumption and latency, yet the paper reports zero metrics on token cost, API calls, wall-clock latency, or graph edge inflation, making it impossible to judge whether the +4.4% overall accuracy gain over LightRAG is simply due to spending 5–10$\times$ more LLM tokens at query time.

3.Unaddressed Clustering Stability, Split/Order Sensitivity, and Temporal Dynamics: Because Q-ECLRR performs online persistent writeback during evaluation (writing edges discovered during query qtq_t into the graph for future queries), the evolved graph structure is inherently non-stationary and lacks stability guarantees:

Split and Order Sensitivity: Whether a hidden relation is available for a test query depends entirely on which queries were asked previously (i.e., how the query stream is split between warm-up/training and testing, and the exact permutation of test queries). The paper does not evaluate variance across random query orderings, nor does it clearly separate an evolution/training split from a held-out test split.

Absence of True Temporal Invalidation ("Safe Routing" is Benchmark Gaming): Because the clustered shortcut edges lack genuine temporal dynamics or automatic dependency invalidation, Q-ECLRR fails on Selective Forgetting (improving by only 0.45 pp, from 52.38% to 52.83% in Table 4). To fix this, Section 4.5.1 introduces "Safe Routing," which literally scans the question text for deletion/negation/reversal cues and turns off Q-ECLRR (reverting to vanilla LightRAG). Relying on question-text cues to bypass stale memory is a benchmark-specific shortcut rather than a principled solution to temporal graph maintenance.

4.Tiny Synthetic Benchmark Scale and Anomalous Baseline Numbers: As noted in Limitation 2, EvoLinkBench consists of only 10 synthetic texts and 359 questions (only 25 single-hop and 63 selective-forgetting instances, where 1 question = 4% or 1.6% accuracy). Furthermore, several baseline results in Table 2 are puzzling and unanalyzed (e.g., with GPT-6-Luna, Dense RAG gets 10.00% on Single-hop while Mem0 gets 76.00%, whereas on Multi-hop MemOS jumps to 36.60% while GraphRAG collapses to 3.32%).

Questions for authors

1.What is the exact token consumption (prompt + completion tokens), number of LLM calls, and wall-clock latency of LightRAG + Q-ECLRR compared to vanilla LightRAG across the 359 questions? How does Q-ECLRR compare against a compute-matched query-time baseline (e.g., LightRAG with iterative multi-step retrieval using the same token budget)?

2.Since Q-ECLRR writes edges back into the graph persistently as queries arrive, how sensitive is the final accuracy to the ordering of the 359 queries or the train/test split of queries? What is the mean and standard deviation across random permutations of the query stream?

3.In Section 4.5.1, Safe Routing detects deletion/negation cues in the question text to disable hidden-relation injection. In a realistic agent memory setting where facts are updated in the document stream without the user explicitly hinting in the question that a fact was reversed, how does Q-ECLRR avoid retrieving stale shortcut edges?

Reviewer_DmKNOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes EvoLinkBench, a benchmark and framework to address the limitation that knowledge graphs in retrieval-augmented generation and memory-augmented agent systems remain static and struggle to discover hidden relations inferred from multiple text chunks located far apart. The paper introduces a latent-graph-driven construction approach to generate source texts and multi-hop reasoning questions grounded in explicit evidence chains. Furthermore, it proposes Evidence-Chain-Linked Relation Recovery (ECLRR) and its query-conditioned variant (Q-ECLRR), which search for candidate paths, recover hop-level source evidence, independently verify proposed relations, and persistently write verified hidden relations back to the graph. It provides several sperated experiments on benchmarks and various models.

Critical strengths
  • The paper addresses an underexplored and meaningful problem by enabling knowledge graphs to proactively reorganize and self-evolve via cross-chunk hidden relation discovery rather than remaining entirely static.
Critical weaknesses
  • The paper fails to effectively motivate ECLRR or explain its problem-solving mechanism, suffers from undefined abbreviations and a missing conclusion in the abstract, and exhibits a clear disconnect between the introduction's core questions and the subsequent methodology.
  • It suffers from poor overall logical flow and missing introductory references, treats figures as detached text commentaries rather than visual aids, and retains unnecessary background information in Section 3.1.1.
  • The text lacks transparency regarding how latent graph-driven construction handles distant case relation chunks, how "gold graphs" differ from general knowledge graphs in Section 3.1.2, and how gold answers are defined and generated.
  • Figures 2 and 3 feature text that is excessively small and difficult to read.
  • The evaluation fails to provide sufficient, convincing performance analysis on the proposed EvoLinkBench benchmark.
Questions for authors
  • Could you explicitly clarify how the latent-graph-driven construction mechanism maps and distributes distant, cross-chunk relation facts into coherent natural language narratives
  • How you guarantee that no individual text chunk accidentally reveals or shortcuts the target hidden relation?
  • Could you define Q-ECLRR upon its first appearance in the abstract or introduction, elaborate on the formal distinction between your proposed "gold graph" and a standard knowledge graph in Section 3.1.2, and explain how the "gold answer" is deterministically derived and verified from the evidence chains?
Reviewer_NqLVOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes EVOLINKBENCH, a benchmark designed to evaluate evidence-grounded, self-evolving graph memory for LLM-based agents. The benchmark aims to assess how agents discover, update, and utilize relational knowledge over time.

Critical strengths

The paper addresses a relevant research problem and introduces a relatively straightforward benchmark comprising 359 question-answer pairs. It also provides preliminary experimental results involving two LLM-based agents.

Critical weaknesses
  1. Severely insufficient literature review and inadequate positioning with respect to existing benchmarks.

The paper's discussion of related work is substantially incomplete, and several of its motivating claims are insufficiently supported by the existing literature. Notably, the introduction makes broad assertions about the limitations of current memory benchmarks without providing adequate citations or engaging with closely related studies.

For example, MEME: Multi-entity & Evolving Memory Evaluation (Jung et al., 2026) explicitly introduces six memory evaluation tasks, including dependency propagation (Cascade), state invalidation (Absence), and deletion. These tasks directly assess whether memory systems can correctly maintain and update dependent information under evolving conditions.

This work substantially challenges the paper's characterization of existing benchmarks as being primarily limited to factual retention, retrieval, or isolated question answering.

More concerningly, the introduction's discussion of the state of the art provides virtually no supporting references for several of its central claims. This lack of scholarly grounding raises serious concerns about the authors' understanding of the existing literature and the validity of the proposed research gap.

  1. Factually inaccurate claims regarding the inability of existing benchmarks to detect error propagation.

The paper's suggestion that existing benchmarks primarily evaluate final-answer correctness and therefore cannot adequately identify error propagation is inaccurate.

For instance, MemDerive: A Diagnostic Benchmark for Agent Memory over Evolving Data (Gao et al., 2026) goes substantially beyond final-answer evaluation. In addition to providing ground-truth answers, MemDerive incorporates gold derivation directed acyclic graphs (DAGs) for individual queries, enabling the diagnosis of intermediate reasoning failures and the analysis of how errors propagate through dependent states.

This is directly relevant to the limitations that EVOLINKBENCH claims to address.

Consequently, the paper's novelty claims require substantial reconsideration. The authors should clearly explain how their proposed evaluation differs from these existing diagnostic and evolving-memory benchmarks, rather than relying on an overly broad and potentially misleading characterization of prior work.

  1. Serious misalignment between the paper's stated objectives and its experimental evaluation.

The experimental section is insufficiently aligned with the paper's title, motivation, and claimed contributions.

Despite positioning EVOLINKBENCH as a benchmark for evidence-grounded graph-memory evolution, the evaluation involves only a very limited number of LLM-based agents. Such restricted experimental coverage is inadequate to establish the benchmark's generality, discriminative capability, or practical relevance.

Furthermore, the experimental comparison places considerable emphasis on RAG-based methods. While RAG can serve as a useful baseline, conventional retrieval-augmented generation does not necessarily perform persistent graph construction, relational discovery, or graph-memory evolution. The paper does not sufficiently justify how these comparisons substantiate its central claims about evolving graph memory.

Overall, the experimental design appears disconnected from the core capabilities that the benchmark is intended to measure.

  1. Insufficient benchmark diversity and inadequate evaluation dimensions.

The benchmark consists of only 359 question-answer instances, raising concerns about its scale, coverage, and ability to represent the complexity of long-term graph-memory evolution.

More importantly, the evaluation appears to rely predominantly on a limited set of QA annotations and conventional metrics, such as F1. Although these metrics may be appropriate for measuring answer-level performance, they are insufficient on their own to characterize the reliability of graph-memory evolution.

In particular, the evaluation does not convincingly establish how the benchmark distinguishes among relational discovery, evidence-grounded memory updates, structural consistency, error propagation, and long-term downstream utility.

Without sufficiently targeted metrics and diagnostic analyses, it is difficult to determine whether the benchmark genuinely evaluates graph-memory evolution or merely measures conventional question-answering performance in a graph-memory setting.

This discrepancy significantly weakens the paper's central contribution.

  1. Overall assessment and concerns about research maturity.

Taken together, these issues raise fundamental concerns about the paper's research maturity, technical soundness, and contribution to the field.

The insufficient engagement with closely related work, the questionable characterization of existing benchmarks, the limited experimental validation, and the lack of alignment between the stated research objectives and the actual evaluation protocol collectively undermine the paper's central claims.

In my assessment, these are not merely presentation issues or minor experimental omissions. They concern the fundamental motivation, novelty, and validity of the proposed benchmark.

I therefore believe that the paper, in its current form, falls substantially below the standard expected of an ICLR submission, and I strongly recommend rejection.

[1] Jung et al. (2026). MEME: Multi-entity & Evolving Memory Evaluation. arXiv:2605.12477. https://arxiv.org/abs/2605.12477

[2] Gao et al. (2026). MemDerive: A Diagnostic Benchmark for Agent Memory over Evolving Data. arXiv:2610.25373. https://arxiv.org/abs/2610.25373

Questions for authors

How does EVOLINKBENCH fundamentally differ from existing evolving-memory benchmarks such as MEME and MemDerive, particularly regarding dependency propagation, intermediate-state diagnosis, and error propagation?

Why does the experimental evaluation cover such a limited number of agents? How can the authors establish the benchmark's generality and discriminative capability under this setting?

What is the justification for emphasizing RAG-based comparisons when the central contribution concerns persistent graph-memory evolution?

How can the proposed QA-based evaluation and conventional F1 metrics adequately capture relational discovery, graph writeback correctness, structural consistency, and long-term memory utility?

What evidence supports the claim that the existing benchmark landscape fails to evaluate these capabilities, given the closely related studies discussed above?

Reviewer_BhxYOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates knowledge graph self-evolution in memory-augmented agents, focusing on discovering and integrating hidden relations supported by evidence distributed across multiple text chunks. The authors introduce EvoLinkBench, a latent-graph-driven benchmark comprising 10 synthetic documents and 359 questions covering single-hop reasoning, multi-hop reasoning, and selective forgetting. They also propose ECLRR, a framework that recovers evidence chains, generates and verifies candidate relations, and persistently writes validated relations back to the graph, along with a query-conditioned variant, Q-ECLRR.

Critical strengths
  1. The core idea is compelling. it is an very interesting angel that treating graph memory like human memory during sleep—proactively reorganizing and consolidating distributed facts into persistent "hidden relations" offline.
  2. EvoLinkBench is a much-needed evaluation tool. Building the benchmark backwards from a latent graph to guarantee that evidence is strictly distributed across chunks (and testing "selective forgetting") is a very clean way to isolate this exact problem, avoiding the messiness of standard Wikipedia datasets.
Critical weaknesses

1.The benchmark is just too small to draw strong conclusions. 10 texts and 359 questions is barely a pilot study. It’s hard to trust the statistical significance of the improvements (like the ~5% overall accuracy bump) or know if this will hold up on diverse, real-world documents. 2.The method seems incredibly expensive and brittle. Running beam search over the whole graph, generating relations, and then doing independent LLM verification for every candidate path sounds like a massive compute sink. Plus, relying on an LLM "Judge" with arbitrary hardcoded thresholds (like sjudge >= 8) to decide what gets written back to the persistent graph feels risky for hallucination propagation.

Questions for authors

1.Given the limited scale and synthetic nature of EvoLinkBench, how well do the benchmark and the proposed method generalize to real-world scenarios? Is there additional evidence supporting their robustness beyond the current evaluation setting? 2.Graph contamination and relation maintenance. How does the proposed framework handle incorrect or outdated relations after persistent writeback? While Safe Routing mitigates some risks at query time, it remains unclear how invalid relations are identified and removed from the graph.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.