ReMindRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG
Authors: Yikuan Hu
Jifeng Zhu
Lanrui Tang
Chen Huang
Venue: NeurIPS 2025 poster ()
Keywords: Retrieval-Augmented Generation
Knowledge Graph
Large Language Models
Low-Cost Inference
Primary area: applications
TL;DR: The paper proposes  an LLM-guided knowledge graph traversal method that enhances retrieval efficiency and accuracy for complex queries while reducing costs.

Abstract: Knowledge graphs (KGs), with their structured representation capabilities, offer promising avenue for enhancing Retrieval Augmented Generation (RAG) systems, leading to the development of KG-RAG systems. Nevertheless, existing methods often struggle to achieve effective synergy between system effectiveness and cost efficiency, leading to neither unsatisfying performance nor excessive LLM prompt tokens and inference time. To this end, this paper proposes REMINDRAG, which employs an LLM-guided graph traversal featuring node exploration, node exploitation, and, most notably, memory replay, to improve both system effectiveness and cost efficiency. Specifically, REMINDRAG memorizes traversal experience within KG edge embeddings, mirroring the way LLMs "memorize" world knowledge within their parameters, but in a train-free manner. We theoretically and experimentally confirm the effectiveness of REMINDRAG, demonstrating its superiority over existing baselines across various benchmark datasets and LLM backbones. Our code is available at https://github.com/kilgrims/ReMindRAG.

REMINDRAG: Low-Cost LLM-Guided Knowledge Graph Traversal for Efficient RAG
Yikuan Hu
Jifeng Zhu 10
Lanrui Tang² Chen Huang 13+
College of Computer Science, Sichuan University, China
Schooo of Computing and Data Science, The University of Hong Kong, Hong Kong, China 3 Institute of Data Science, National University of Singapore, Singapore kilgrim&e oxmail. com ray8823@connect. .kku hk
zen1984. kr@gmail.ccoo coo
mrang_chen@nus edu.
Abstract
Knowledge graphs (KGs), with their structured representation capabilities, offer promising avenue for enhancing Retrieval Augmented Generation (RAG) systems, leading the development of KG-RAG systems. Nevertheless, existing methods often struggle to achieve effective synergy between system effectiveness and cost efficiency, leading neither unsatisfying performance tokens and inference time. To this end, this paper proposes REMINDRAG which employs an LLM-guided graph traversal featuring node exploration, node exploita- tion, and, most notably, memory replay, to improve both system effectiveness and cost efficiency. Specifically, REMINDRAG memorizes traversal experience within KG edge embeddings, mirroring the way LLMs "memorize" world knowledge within their parameters, but train-free manner. We theoretically and experi- mentally confirm the effectiveness of REMINDRAG, demonstrating its superiority over existing baselines across various benchmark datasets and LLM backbones. Our code is available at hhtpp:: // thub. com kilgr ims hellgrimm/ReMiddR... RdRAG
excessive LLM prompt
1 Introduction
Retrieval-Augmented Generation (RAG) 23 has become a prominent method for augmenting Large Language Models (LLMss) with external knowledge resources, enabling them to generate more accurate outputs and thereby expanding their practical utility [1
(2). However, conventional
RAG approaches, which primarily employ dense vector retrieval 37 20 T for identifying relevant
text segments, often exhibit limitations when confronted with intricate tasks that necessitate multi- hop inference [49] or the capture of long-range dependencies [24]. Knowledge Graphs (KGs), characterized by their structured representation of interconnected entities and relationships, present compelling alternative. Thus, research efforts increasingly focused on developing KG-RAG systems, which aims to improve RAG performance using
text representation 100 5 27
Usually, KG-RAG system operates by initially transforming source documents into graph-based F
representations] This often involves leveraging LLMs to extract entities and relationships, which then represented nodes and edges within the graph. Information retrieval is subsequently performed by traversing this graph to identify nodes relevant to the query. To achieve this, traditional graph search algorithms, like PageRank [14 99, and deep learning approaches, like GNN (53). could
be employed for traversal and answer extraction
31 26 47] these methods often fail to capture
"Corresponding author. Work done during his PhD program at Sichuan University.
Both authors contributed equally to this study.
Unlike previous work leveraging established KGs generate their knowledge graph directly from the source text, like GraphRAG []] and LightRAG (.].
this study explores KG-RAG systems that
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the nuanced semantic relationships embedded within the graph, leading to unsatisfactory system effectiveness [3] T8]. By contrast, the LLM-guided knowledge graph traversal approaches but these methods lead to substantially increased L.M invocation costs and a significant rise in irrelevant noise information. Therefore, the effective synergy between system effectiveness and cost efficiency presents a major challenge for the practical deployment and scalability KG-RAG systems.
demonstrate notable advantages 6
42 41
To this end, we propose REMINDRAG-Reiiee
and Memorize, novel LLM-guided KG- RAG system with memorization. As depicted in Figure I REMINDRAG first constructs a KG from unstructured texts and subsequently employs two key innovative modules: (1) LLL-Guided Knowledge Graph Traversal with Node Exploration and Exploitation. Beyond logical reasoning and semantic understanding capabilities of the LLM, REMINDRAG expands traversal paths using node exploration and node exploitation. This approach enables the L.MM to progressively perform single-node expansion and traversal to approximate answers, achieving high-precision retrieval with more hops without requiring large-scale searches like beam search-based [54] methods. (2) Memory Replay for Efficient Graph Traversal. It memorizes traversal experience within KG edge embeddings, mirroring the way LLMs "memorize" world knowledge within their parameters, but in a train-free manner. It efficiently stores and recalls experience, eliminating the need to consult the LLM, thus substantially improving efficiency while preserving system effectiveness. We theoretically show that for semantically similar queries, this memorization enables edge embeddings store sufficient traversal experience regarding these queries, facilitating effective memory replay.
Build
First Query
Ans
Loop Until
Get Ans Subgraph
LLM
Traversal
Get Seed Node
Chunks
Query
Enhance/Penalize
Ans
Edges
Memorize
Answer Subgraph
KG
Directly
Get Seed Node
Get Subgraph
Similar/Same Query
Subsequent Query
Figure I: Overall Workflow. REMINDRAG constructs a KG from unstructured text. memorizes LLM-guided traversal path, enabling fast retrieval when encountering similar queries subsequently.
To evaluate REMINDRAG, we conduct extensive experiments across various benchmark datasets and LLM backbones. The experimental results demonstrate that REMINDRAG exhibits clear advantage over competing baseline approaches, achieving performance gains of 5% to 10% while simultaneously reducing the average cost per query by approximately 50%. Our analysis reveals that the key strengths of REMINDRAG lie its inherent self-correction capability and robust memory retention. It can leverage LLMs to self-correct erroneous search paths while maintaining stable memory capabilities even when handling large-scale updates. To sum up, our work makes the following contributions.
We call attention the challenge of achieving effective synergy between system effectiveness and cost efficiency, hindering the practical utility of KG-RAG systems.
We introduce REMINDRAG, which employs LLM-guided KG traversal featuring node explo- ration, node exploitation, and, most notably, memory replay, to improve both system effectiveness and cost efficiency.
We theoretically and experimentally confirm the effectiveness of our graph traversal with mem- ory replay, demonstrating REMINDRAG's superiority over existing baselines across various benchmark datasets and LLM backbones.

---

2
Related Works
Leveraging explicit semantic relations among entities via graph-based text representation. KG- RAG systems often improve overall RAG performance [11]
10
15
48 [2]. In these systems,
information retrieval is typically performed by traversing the graph to identify nodes relevant the query. While traditional graph search algorithms and deep learning approaches employ methods such Personalized PageRank [14], Random Walk with Restart 45 and Graph Neural Networks
(GNNs) [53] [6] for traversal and answer extraction [31 8 22) 47). these methods often struggle
to capture the nuanced semantic relationships embedded within the graph [33] TO 18, leading to unsatisfactory system effectiveness. In contrast, L.MM-uudeed graph traversal methods, which prompt the L.LM to make decisions about which node visit next by virtue of their deep parsing of
semantic information and flexible decision-making capabilities in the graph 4 have demonstrated
effective performance 66 42 25]. However, this approach necessitates repeated calls to the
LLM, significantly increasing prompt token consumption and inference time, thus hindering practical deployment [31 [5]. Moreover, recent benchmarks also indicate that their performance remains limited in complex semantic scenarios [24] Therefore, the trade-off between system effectiveness and cost efficiency presents a major challenge for the practical deployment and scalability of KG-RAG.
To this end, we propose a novel approach that leverages LLM-guided graph traversal with node ex- ploration, node exploitation, and, most notably, memory replay, to improve both the effectiveness and cost efficiency of KG-RAG. Furthermore, by introducing a training-free memorization mechanism, we achieve a significant advancement in graph traversal. In contrast, existing query retrieval methods confined to traditional graph pruning [10 5 15 or path planning 44 41 13 [8]
with the
former risking information loss and the latter offering limited efficiency gains.
Method
3.1 LLM-Guided Knowledge Graph Traversal with Node Exploration and Exploitation
KG Construction. Building on prior works 111 [3], we begin by partitioning unstructured text into discrete chunks. Subsequently, we ex- tract named entity triples from these chunks and construct a heterogeneous knowledge graph. This graph comprises two node types: entities and chunks. It also contains two edge types: entiry- chunk edges (i.e., entity-to-its soit---oo-------eeeeeee (ttrcccurc-hhhkk and entity-entity edges (extracted triples). For specific details knowledge graph construction, please refer to Appendix|A A
Algorithm 1 LLM-Guided KG Traversal 1: Input: Query q, KG G. Seed Count k. LLM
2: // Subgraph Initialization
3: S + top-k nodes in G by similarity to
4: 11 Path Expansion Loop
5: repeat
// Node Exploration
Graph Traversal. As illustrated in Figure RE- MINDRAG first identifies set of entity nodes the knowledge graph that exhibit the highest se- mantic relevance to the query based on embedding similarity, marking them as seed nodes. These seed nodes further form the initial subgraph S, which begins with no edges between them. To fa- cilitate effective graph traversal that balances both exploration and exploitation, REMINDRA AG iter- atively executes two key operations for traversal path expansion: Node Exploration and Node Ex- ploitation. The iteration continues until the LLM
7: + LLM selects most answer-relevant
node S
8:
// Node Exploitation
S. < {p edge p) G.p $ S}
10:
+ LLM chooses optimal expansion
node p E Sa
11:
S+ SUp
12:
S+SU ((a,p))
13:
until LLM confirms answer is in S
14: Output:
determines that subgraph S contains sufficient information address the query. Refer to Algorithm D and Appendix B for details.
Node Exploration Strategy. This strategy prioritizes exploring potential nodes likely to lead to the answer, ensuring the graph traversal process is not confined to deep exploration of a single path. Instead, it achieves globally optimal search over the entire KG at low computational cost, thereby increasing the likelihood of obtaining the global optimal solution. To achieve this, during each
3

---

Node Exploitation: Choosing the Optimal Expansion Node
Subgraph
Answer Node
Subgraph Initialization
Seed Node
Node Exploration:
Selecting Most Answer wwwpswerrreeevattt...
Subgraph
The Loop Step of Path Expansion
Figure 2: Illustration of LLM-Guided KG traversal in REMINDRAG, It iteratively expands the subgraph towards answer nodes through process that combines node exploration and exploitation.
iteration, the LLM evaluates all nodes in subgraph and selects the target node a E S deemed most likely lead to the answer.
Node Exploitation. This focuses on exploiting previously explored nodes and expanding the path along those nodes approach the answer. Specifically, given the previously selected node E S, the LLM selects the optimal expansion node from the adjacent node set S. node a, considering p to be the most likely lead to the answer. At the end of the current iteration, the expansion node p and its connecting path to a are added to subgraph for subsequent traversal. This leverages the LLM's semantic understanding and reasoning capabilities for effective graph traversal.
3.2 Memory Replay for Efficient Graph Traversal
which refers to the recall of valuable past memories to facilitate current tasks, we design memory replay for efficient graph traversal. However, our approach diverges from prior work that typically involves recalling explicit samples. Instead, our 'memory' is embedded as weights within the KG, and it is these weights that are exclusively utilized to guide L.LM inference and graph traversal. In particular, we design RE.INNDR AG to memorize LLM's traversal experience within the KG. Consequently, when processing identical, similar and subtly different queries, this memorized experience can be recalled before the LLM-Gudded KG Traversal process, reducing the number of LLM calls and significantly enhancing the efficiency while maintaining system effectiveness.
Following previous works regarding memory replay
3.2.1 Memorizing the Traversal Experience within the KG
What to Memorize. In our work, both effective traversal paths, which lead to the correct answer, and ineffective paths are valuable, as they can provide positive and negative reinforcement, respectively, to guide the LLM's future traversal decisions. Given that the final subgraph S contains mix of both, we employ a filtering operation: For effective paths, first use the L.M to identify the edges and chunks that contributed to generating the answey"] and then use Depth-Fires Search (DFS) 44 algorithm to extract these paths. The remaining paths are then classified as ineffective.
2
Weight Function: 8(x)
| 5(v)
π
Enhance Effective Path:
q
(I)
||1112
Penalize Ineffective Path: è 8( v
v q
|
|
How to Memorize. We propose train-free memorization method to further improve efficiency, This is achieved by memorizing traversal experiences within the KG, which are formalized as edge embeddings and updated using closed-form equations. In particular, after the LLM produces an
'We do not provide the ground truth answer to the LLM during this process. The answer here is the one produced by the LLM itself.

---

answer for query, we update the edge embedding for each edge in the final subgraph s Formally, let E R denote the edge embedding, initialized as zero vector, where is the vector dimension. For edges belonging to effective paths within S, we update in the direction of the query embedding generated by the L.LM. Conversely, for edges belonging to ineffective paths, we reduce the component of along the query embedding q (As shown in Figure 3 Equation (T details the update rules, where represents the updated edge embedding and is the update weight function, which is essentially a cosine function based on the vector's norm.
Query Embedding
+++1
TE 2
Dos
Edge Embedding
Damped Update
Enhance
Penalize
Fast Wakeup
Understanding Fast Wakeup & Damped Update via weight function
Figure 4:
Figure 3: Schematic Diagram of Memorizing.
Intuitions Behind Memorizing Process. Our closed-form memorization rules, outlined in Equation (T. exhibit two key characteristics: rapid learning of traversal experiences and sustained stability across multiple memorization events. These characteristies are achieved through the Fast Wakeup and Damped Update, respectively.
Fast Wakeup. When the norm of the edge embedding v small (typically the initial all-zen all-zero state), it indicates that retains little memorized information. In this state, we aim for the edge embedding to rapidly learn the traversal experience with only a few updates. As shown in Figure 4 when the norm is small, the J function induces substantial directional update to the edge embedding, thus enabling Fast Wakeup.
Damped Update. Once the edge embedding v has learned substantial information (i.e., the norm of is large), objective is to maintain the stability of the edge embedding, preventing it from casily losing its learned information due to subsequent updates. As illustrated in Figure 4 the function induces only minor updates when the norm is large, exhibiting resistance change while retaining the ability to correct errors through gradual forgetting.
3.2.2 Efficient Subgraph Expansion via Memory Replay
To enhance traversal efficiency, the memory replay mechanism enriches the initial subgraph S prior to the LLM-guided path expansion (detailed in Algorithm [T.. This mechanism achieves rapid subgraph expansion by incorporating potentially relevant nodes and edges from historical traversal experiences, thereby reducing reliance on iterative L.M calls.
Formally, let represent user query and G denote a knowledge graph, where each edge Eab connecting nodes a and 6 possesses an associated, updatable embedding vector Vas. We define emb(; as the text embedding function and sim(.)) as the node embedding similarity function. The Subgraph Initialization, detailed in Algorithm [ begins by generating a graph comprising only seed nodes. From each seed node, a recursive Depth-Fire First Search (DFS) is performed to expand the subgraph by adding traversed nodes and edges. This DFS operation proceeds as follows: For given current node Ntrm and its unvisited neighbor No. the system assesses N 's relevance to both Nirom the query estimating its potential contribution to the final answer. If this relevance surpasses a predefined threshold X, No and connecting edge are incorporated into subgraph S, and the DES process is recursively invoked on No. The relevance metric NN. defined in this work. consists of two
'Each edge in KG has an associated embedding vector, which is subject to updating if that edge is included in the final subgraph.
5

---

components: (1) the semantic relevance between nodes Nuom and N₂ and (2) the alignment of traversing the edge with satisfying query 9, which constitutes REMINDRAG's core memory function. The hyperparameter a adjusts the relative importance of these two terms.
emb(q) UN yNorom |
UNoro = a sim (eemeeeerrrrm) emb((Noo)) (enn)(()))))
+ (1 aa)
(2)
After subgraph expansion via memory replay, the subgraph is expected to contain sufficient infor- mation for answering the imput query. However, if the LLM judges that the expanded subgraph still lacks sufficient information, REMINDRAG continues the Path Expansion Loop, a process that can be regarded as verifying and correcting memorized information.
Theoretical Analysis
Our theoretical analysis (cf. Appendix for a detailed proof) of the memory capacity demonstrates that, given set of queries exhibiting some degree of semantic similarity, memorization rules in Equation (1) enable edge embeddings to memorize these queries and store sufficient information, thereby enabling effective memory replay. Formally, when the embedding dimension d is sufficiently large, given the threshold À in Section 3.2.2] for any given edge, when the maximum angle A between all query embedding pairs within query set satisfies Equation the edge effectively memorize the semantic information within that query set.
(V3 sin sin(arccos(()))
0 < lim
2 aresin
d=+00
Remark To satisfy the storage requirement the theoretical upper bound for X determined to be 0.775. This determination aligns with existing research [37y, which establishes cosine similarity threshold of 0.6 as the criterion for assessing semantic similarity.
6
Remark 2 Our assumption that the embedding dimension is infinitely large is based on the fact
that linear embedding models do have very high dimensions. For the function / d+1 2d when is greater than around 100 (currently, the embeddings of LLM often exceed 100 dimensions), it can actually be approximated to 1. empirical experiments in Section 5.3.2
2. This approximation thus holds significant practical utility. See our
Experimental Analysis
5.1 Experiment Setup
We conduct extensive experiments across various benchmark datasets and LLM backbones. For implementation details and additional analysis, refer to Appendix DDand Appendix E. respectively.
Tasks & Datasets. To comprehensively evaluate the performance of the proposed REMINDR AG, we follow previous works [13 24] and conduct experiments on three benchmark tasks: Long Dependency QA, Multi-Hop QA, and Simple QA. This enables systematic assessment of retrieval effectiveness and efficiency across various scenarios. Refer Appendix C for details.
Long Dependency QA: We resort to the LooGLE dataset [24]. requires the system to identify implicit relationships between two distant text segments, testing the RAG system's 's long-range semantic retrieval capability. The long-dependency QA task in the LooGLE dataset (with evidence fragments spaced at least 5,000 characters apart) effectively evaluates the long-range dependency capture performance of RAG solutions in single-document scenarios.
'This component enables user control over REMINDRAG'S memory sensitivity.
'While this provides solution under theoretical conditions for parameter configuration, practical applications require consideration of multiple factors when setting parameters. Additional details are in Appendix D.4

---

2) Multi-Hop QA: We resort to the HotpotQA dataset [49]. It focuses on complex question- answering scenarios requiring multi-step reasoning, demanding the model chain scattered information through logical inference.
3) Simple QA: This task leans towards traditional retrieval tasks, emphasizing the model's ability to extract directly associated information from local contexts. We adopt the Short Dependency QA from the LooGLE [24] dataset as representative example.
Evaluation Metrics. (1) Effectiveness evaluation. Following the evaluation protocol of recent benchmark (24), for each question, we employ LLM-as-judgmentt (GPT-40) [52] to determine the answer accuracy: whether the model-generated answer adequately covers the core semantic content of the ground truth through semantic coverage analysis. Refer to Appendix D.6 for more details. (2) Cost-efficiency evaluation. We use the average number of tokens consumed by the LLM per query during traversal as our cost-efficiency metric.
Baselines. We consider following baseline ] (1) Traditional retrieval methods: BM25 38 and
AG [23] (2) KG-RAG systems using graph search algorithms: GraphRAG 9 LightRAG 11 and HippoRAG2 13. (3) -.g.Med KG-RAG system: Plan-on-Graph [6]
Backbone. We employed two backbones: (I) GPT-4o-mini 34], a highly cost-effective and currently the most popular backbone. (2) Deepseek-V. V3 (28). the latest powerful open-source dialogue model.
5.2
Understanding the Effectiveness and Cost-Efficiency of REMINDRAG
5.2.1 System Effectiveness Evaluation
As shown in Table REMINDRAG AG consistently outperforms the baselines across different LLM backbones, with performance fluctuations confined to small range. Particularly noteworthy is the significant performance improvement achieved on Long Dependency QA and Multi-Hop QA tasks (+ (+12.08% and +10.31 % over the best baseline average), while simultaneously maintaining high accuracy on Simple QA tasks (44.66%% over the best baseline on average). This phenomenon indicates that REMINDRAC AG not only exhibits strong fundamental retrieval capabilities but also effectively addresses long-range information retrieval and multi-hop reasoning challenges. This advantage primarily stems from two factors: (1) By leveraging the reasoning capabilities of LLMs, the system can perform semantic-driven active reasoning on KGs, enabling more precise answer retrieval. (2) The balanced node exploration and exploitation strategy employed during LLM-guided KG traversal allows for the achievement of both globally and locally optimal search results.
QA Type
Long Dependency QA
Multi-Hop QA
Simple QA
Backbone
Deepseek GPT-4o-mini
GPT-4o-mini
Deepseek V3
GPT-4o-mini
Deepseek V3
REMINDRAG (Ours)
57.04%
59.73%
74.22%
79.38
76.67%
77.01 %
Plan-on-Graph G
27.78%
19.46%
58.51%
47.87%
38.26%
32.89%
HippoRAG2
RR
39.60%
38.26%
68.04%
64.95%
73.08%
71.28%
LightRAG 11
37.58%
53.02%
45.36%
53.60%
49.49%
62.82%
GrapRRAG
26.03%
9.86%
58.70%
22.95%
21.96%
7.20%
NaiveRAG 23
36.91% %
46.98%
58.76%
56.70%
47.95%
66.41%
BM25 X8
22.82%
33.56%
50.52%
54.64%
43.13%
52.56%
LLM Only (w/o RAG)
16.
29.53%
40.21%
54.64%
18.21%
30.00%
Table 1: Effectiveness Performance (i.e., Answer Accuracy).
5.2.2 Evaluation on System Cost-Efficiency and Memorization
Setups. To evaluate the cost efficiency (along with its effectiveness) REMINDRAG, we conducted multiple sets of comparative experiments under identical conditions. Here, given dataset A containing documents and user queries, we consider three setups: (1) Same Query: The model initially has already been evaluated on dataset A and has memorized information from A and is
For additional analysis baselines, please refer to Appendix E.2
7

---

subsequently re-evaluated again on the same dataset. (2) Similar Query: The model is re-evaluated again on a dataset A' whose queries are semantically equivalent paraphrases of those in A (cf. Appendix C.3 for inplementation). (3) Different Query: The model is re-evaluated again on a dataset A" whose queries are distinct from those in A but share similar questions (ef. Appendix [.4 for implementation). Importantly, of all the datasets we tested, only the Multi- QA dataset satisfies the criteria for the Different Query setup P Additionally, to evaluate the memorization capability of REMINDRAG comprehensively, we further consider multi-turn memorization. This involves initially evaluating REMINDRAG on the same dataset A multiple times (i.e., memorizing A multiple times).
As shown in Table 2 REMINDRAG demonstrates significant cost reduction when utilizing memory replay. Furthermore, after the multiple-tun memorization, REMINDRAG achieves a 58.8% reduction in token consumption compared to the initial trial, on average. These optimizations are primarily due to REMINDR AG's ability to learn and memorize traversal experiences via dense embedding techniques. When encountering identical or semantically similar queries, SEMINDRAG can rapidly identify relevant structures based on its memories to initialize the subgraph S. thereby reducing the frequency of LLM calls and significantly lowering costs. Additionally, we observe that when handling multiple distinct questions pertaining to the same underlying document (i.e., the Different Query scenario), REMINDRAG effectively stores and utilizes traversal knowledge acquired from various queries. This observation aligns with our theoretical findings presented in Section 4 which state that given set of queries exhibiting semantic similarity. our memorization rules enable edge embeddings to effectively memorize these queries and store sufficient information, thereby enabling effective memory replay.
Long Dependency QA
Multi-Hop QA Similar Query
QA Type
Same Query
Similar Query
Same Query
Different Query
Methods
Accuracy
Tokens
Accuracy
Tokens
Accuracy
Tokens
Aocuracy
Tokens
Accuracy
Tokens
REMINDRAG
33 tumn Menurization
60.31%
6.71K
57.25%
7,02K
87.62%
5.89K
78.72%
6.02K
77.66%
9.76K
2 tum Menorization
58.01% %
7,55K
54.96%
9.85K
84.04%
6.56K
73.40%
9.34K
74.47%
9.50K
-1 tum Memorization
56.48%
9.68K
55.03%
13.98K /
79.78%
7.73K
75.53%
9.88K /
72.34% /
10,57K /
.No Memorization
57.04%
14.91K
/
74,22%
10.16K
/
Plan-on-Graph
27.78%
30.29K
30.87%
39.08K
58.51%
5.53K
61.19%
7.01K
62.67%
5.45K
HippoRAG2
39.60%
37.58%
68. 68.04%
63.91%
/
69.44%
Table 2: Evaluation on System Cost-Efficiency and Memorization under three query types and multi-turn memorization: GPT-4o-mini is used as the backbone. "Tokens" here refer to the average number of tokens consumed by the LLM per query during traversal.
5.3 Understanding the Characteristics of REMINDRAG
This section explores features of REMINDRAG, including its self-correction capabilities and memory stability. For more in-depth analyses concerning graph construction efficiency. the effect of contextual data, and the influence of varying max hop counts, please refer to Appendix E.1
5.3.1 Self-Correction of REMINDRAG
As shown in Table 2 REMINDRAG achieves a 5%-10% performance improvement after multi-turn memorization, revealing the potential for self-correction in graph traversal. For a better understanding of this behavior, we provide case study 2 presented in Figure 5 The case study demonstrates that when REMINDRAG initially provides an incorrect answer subgraph, the system can still penalize irrelevant nodes in the knowledge graph based on the memorization rules (Equation (3) without explicitly receiving the correct answer. In subsequent queries, REMINDRAS AG switches to traversing the memory-optimizzed subgraph, thereby achieving self-correction of errors. Furthermore, Figure showcases REMINDR AG's ss robust self-correction in the "Different Query" setting. When handling queries that are embedding-simie retrieved via similarity matching fail to address the current query. In such cases, REMINDRAL AG fully leverages the deep semantic understanding capabilities of LLMs to identify mismatches between the
but fundamentally distinct, the candidate answer subgraphs
'We use the "hotpot_dey lel__dde____e_eee distractor" version, which contains intentionally designed distractors. Demonstration screenshots from our operational web interface available in Appendix G.2
8

---

candidate answer subgraphs and the given query, and then autonomously triggers the LLM-basel graph traversal mechanism re-execute the reasoning process. REMINDRAG still demonstrates excellent performance and remarkable cost reduction on these challenging problems.
Were Scott Derrickson and Ed Wood of the same nationality? Wrong
First Query
Scrtt
Second Query
Right
Seed amds
Amerionn
charkz
nationaity
Alemary from the Former query
Dericcen's actionaltty
DERector
Scott
Diracter
troverzel
Woad
Calfamis
Writer
Ed Woed
Screan
Chunko
Peralize
notionaliyy
Weod's
Enfence
Futtonaliy
Weed's
Figure 5: The case of memory replay under the Same Query setting. In the first search, relevant info about 'Ed Wood' is found, but instead some unrelated details about 'Scott Derrickson' appear. After the search, the system enhances useful paths and penalizes irrelevant ones. The second search then focuses on the subgraph with the correct info about 'Scott Derrickson', achieving self-correction.
5.3.2 Memory Stability
This section aims to evaluate the mem- ory stability REMINDRAG in more complex scenarios.
REMINDRAN AG w/ multi-tum memo.
QA Type
Accuracy
Tokens
-S-uumn Memorization
Different
77.66%
6,33K
Impact of Distinct Queries. Unlike
4-turn Memorization
Origin
80.85%
5.72K
the multi-turn memorization task de-
3-turn Memorization
Different
76.60%
6.75K
2-turn Memorization
Origin 78.72%
6.91K
scribed in Section [52.22 (where RE-
I-turn Memorization
Different
72.34%
10.57K
MINDRAG repeatedly memorizes the same dataset), this experiment re-
Memorization
Origin
74.22%
10.16K
quires REMINDRAG to alternately process and memorize heteroge- neous datasets associated with dis- tinct queries. The alternating update procedure frequently involves cyclic operations of enhancing and penal- izing specific edges, rigorously val- idating REMINDRAG's memory stability under extreme conditions. As shown in Table B Re- MINDR AG demonstrates sustained promising performance and cost reduction, which is direct result of our designed "Fast Wakeup" and "Damped Update" mechanisms detailed in Section 3.2 During multi-round memorization, REMINDR AG demonstrates rapid content memorization while preserving stability in retaining effective memories, highlighting its potential for handling dynamic update patterns in complex scenarios.
Table 3: Accuracy of REMINDRAG under complex multi-
turn memorization settings (Multi-Hop QA & GPT-4o-mini). "Origin" represents the original question, while "Different" denotes the modified question (as shown in Setup (3) in Section 5.2.2).
Original Query
Subtle Differences Query
Were Scott Derrickson and Ed Wood of the same nationality?
Were Scott Derrickson and Conrad Brooks of the same nationality?
Memory quary
Apsericon Dincstar
Amseicoa
Cormeleza
ChuneiD
froversol
Nationltty of Scott
Gonrad
Chaskti
Nationaity Scott
Seed nods
Netionalty of Ed Woed
Seed mode
chai
Nativaliy of Coered Brooks
Figure 6: The of memory replay under the Different Query setting. In this case, person's 's name replaced in the second query, resulting in different answer subgraphs. However, the L.MM is able to detect the incompleteness of the candidate answer subgraph and restart the traversal process. A complete demonstration of the entire process can be found in Appendix G.I

---

Dimension
768
384
192
96
-No Memorization
57.04%
56.37%
55.36%
54.69%
54.36%
52.78%
52.08%
-1-iurn Memorization
56.48%
52.34%
54.03%
53.02%
52.97%
52.95%
52.55%
-2-uun Memorization
58.01% %
57.71 %
55.03%
53.35%
53.28%
53.42%
53.15%
Table 4: Dimensional Truncation Experiment. The horizontal axis represents the dimension truncation ratio. The vertical axis denotes the number of updates. The values in the table correspond to the answer accuracy, and all experiments were conducted with the same default parameters.
Impact of Embedding Dimensions Memory Capacity. While our theoretical analysis in Section 4 estabbishes REMINDRAG's memory capacity, it hinges on an approximation where the LLM's embedding dimension approaches infinity (details in Appendix F.) Although Appendix [D argues this approximation remains practically useful for large dimensions (c.g., 100), this section empirically demonstrates the robustness of our memory capacity even with varied, truncated dimensions. As detailed in Table [ experiments with reduced embedding dimensions show negligible impact on the overall system. We hypothesize this resilience stems from the embedding model's Matryoshka Representation Learning [21]. allowing normal operation even at low dimensions.
6 Conclusion
In this paper, we introduce REMINDRAG, a novel approach that leverages LLM-guided knowledge graph traversal featuring node exploration, node exploitation, and, most notably, memory replay, to improve both the effectiveness and cost efficiency KG-RAG. We theoretically demonstrate that the memorization capability of REMINDR AG is strong- It could store sufficient information enable effective memory replay. Our experimental results show that REMINDR AG achieves promising performance compared to baselines across multiple benchmark datasets and L.LM backbones. In- depth analysis reveals that REMINDRAN AG effectively memorizes the L.M''s traversal experience, reducing costs and enhancing efficiency in subsequent queries under various query settings (i.c., Same, Similar, and Different). Going forward, while the initial graph traversal of REMINDR still requires multiple LLM calls, we plan initialize the model with pre-existing, well-curated FAQS specific to the deployment domain or scenario. This will provide the model with a strong baseline memory, capable of handling common situations and accelerating the graph traversal process.
10

---

References
[1] Sanjeev Arora, Yingyu Liang, and Tengyu Ma. simple but tough-to-beat baseline for sentence embeddings. In International conference learning representations, 2017.
[2] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247-1250, 2008.
[3] Antoine Bosselut, Hannah Rashkin, Maarten Sap, Chaitanya Malaviya, Asli Celikyilmaz, and Yejin Choi. Comet: Commonsense transformers for automatic knowledge graph construction. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics,
pages 4762-4779, 2019.
[4] Chi-Min Chan, Chunpu Xu, Ruibin Yuan, Hongyin Luo, Wei Xue, Yike Guo, and Jie Fu. Rq-rag: Learning to refine queries for retrieval augmented generation. arXiv preprint arXiv:2404.00610 2024.
[5] Hanzhu Chen, Xu Shen, Qitan Lv, Jie Wang. Xiaoqi Ni, and Jieping Ye. Sac-kg: Exploiting large language models as skilled automatic constructors for domain knowledge graph. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics 2024.
(Volume 1: Long Papers), pages
[6] Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. Plan-on- graph: Self-correcting adaptive planning of large language model on knowledge graphs. In The eight Annual Conference on Neural Information Processing Systems.
[7] B. V. Dekster. The jung theorem for spherical and hyperbolic spaces. Acta Mathematica Hungarica, 67:315-331 3311, 1995.
[8] Wentao Ding, Jinmao Li, Liangehuan Luo, and Yuzhong Qu Enhancing complex question answering over knowledge graphs through evidence pattern retrieval. In Proceedings of the ACM Web Conference 2024, pages 2106-2115, 2024.
[9] Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. From local to global: graph rag approach to query-focused summarization. arXiv preprint arXiv:2404. 16/30, 2024.
[10] Zengyi Gao, Yukun Cao, Hairu Wang, Ao Ke, Yuan Feng, Xike Xie, and S Kevin Zhou. Frag:
A flexible modular framework for retrieval -rugeeel-augmentedd generation based on knowledge graphs arXiv preprint arXiv:2501 00955799977...........991.001071 2025.
[11] Zirui Guo, Liannhho Xia, Yanhua Yu, Tu Ao, and Chao Huang. Lightrag: Simple and fast retrieval-augmmented generation. arXiv e-prints, pages arXiv-2410, 2024.
[12] Bernal Jiménez Gutiérrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. Hipporag: Neurobiologically inspired long-term memory for large language models. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
[13] Bernal Jiménez Gutiérrez, Yiheng Shu, Weijian Qi. Sizhe Zhou, and Yu Su. From rag to memory: Non-parametric continual learning for large language models. arXiv preprint arXiv:2502.1445 14802. 2025.
[14] Taher H Haveliwala. Topic-sensitive pagerank. In Proceedings of the I 11th international conference World Wide Web, pages 517-526, 2002.
[15] Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-retriever: Retrieval-augmmnted generation for textual graph understanding and question answering. Advances in Neural Information Processing Systems, 37:132876-132907 2024.
[16] Chen Huang, Haoyang Li, Yifan Zhang, Wenqiang Lei, and Jiancheng Lv. Cross-space adaptive filter: Integrating graph topology and node attributes for alleviating the over-smoothing problem. In Proceedings of the ACM Web Conference 2024, WWW '24, page 803-814, New York, NY, USA, 2024. Association for Computing Machinery.

---

[17] Lei Huang, Weijiang Yu. Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qiang- long Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, al. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Transactions on Information Systems, 43(2):1-55, 2025.
[18] Boran Jiang, Yuqi Wang, Yi Luo, Dawei He, Peng Cheng, and Liangeai Gao. Reasoning on efficient knowledge paths: knowledge graph guides large language model for domain question answering. In 2024 IEEE International Conference on Knowledge Graph (ICKG), pages 142-149. IEEE, 2024.
[19] Heinrich WE Jung. Über den kleinsten kreis, der eine ebene figur einschließt. 1910.
[20] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen Tau Yih. Dense passage retrieval for open-domain question answering. In 2020 Conference Empirical Methods in Natural Language Processing, EMNIP 2020, pages 6769-6781. Association for Computational Linguistics (ACL), 2020.
[21] Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ra- manujan, William Hloward-Snyder Kaifeng Chen, Sham Kakade, Pratcek Jain, et al. Matryoshka representation learning. Advances in Neural Information Processing Systems, 35:30233-30249, 2022.
[22] Yunshi Lan, Gaole He, Jinhao Jiang, Jing Jiang, Wayne Xin Zhao, and Ji-Rong Wen. Complex knowledge base question answering: A survey, IEEE Transactions on Knowledge and Data Engineering,
2022.
[23] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et detrieval-augmente generation for snowledge-intensive nlp tasks. Advances in neural information processing systems, 33:9459-9474, 2020.
[24] Jiaqi Li, Mengmeng Wang, Zilong Zheng, and Muhan Zhang. Loogle: Can long-con long-context language models understand long contexts? In Proceedings of the 62nd Anmual Meeting of the Association for Computational Linguisties (Volume 1: Long Papers), pages 16304 16333, 2024.
[25] Qianlong Li, Chen Huang, Shuai Li, Yuanxin Xiang, Deng Xiong, and Wenqiang Lei. GraphOT- TER: Evolving LLM-based graph reasoning for complex table question answering. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al- Al-Khal, Barbara Di Eugenio, and Steven Schockaert, editors, Proceedings of the 31 International Conference on Computational Lin- guisties, pages 5486-5506, Abu Dhabi, UAE January 2025. Association for Computational Linguistics.
[26] Zhuoqun Li, Xuanang Chen, Haiyang Yu, Hongyu Lin, Yaojie Lu, Qiaoyu Tang, Fei Huang, Xianpei Han, Le Sun, and Yongbin Li. Structrag: Boosting knowledge intensive reasoning of Ilms via inference-ting hybrid information structurization. arXiv preprint 5:X00:2410.08875. 2024.
[27] Lei Liang, Mengshu Sun, Zhengke Gui, Zhongshu Zhu, Zhouyu Jiang, Ling Zhong, Yuan Qu, Peilong Zhao, Zhongpu Bo, Jin Yang, et al. Kag: Boosting lmss in professional domains via knowledge augmented generation. arXiv preprint arXiv:2409. 13731, 2024.
[28] Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412. 19437, 2024.
[29] Ruishan Liu and James Zou. The effects of memory replay in reinforcement learning. In 2018 56th annual allerton conference communication, control, and computing (Allerton), pages 478-485. 485. IEEE, 2018
[30] LINHAO LUO, Yuan-Fang Li, Reza Haf, and Shirui Pan. Reasoning graphs: Faithful and interpretable large language model reasoning. The Twelfth International Conference on Learning Representations.
12

---

[31] Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv preprint 201.9,, 2024.
[32] Cheng Niu, Yuanhao Wu, Juno Zhu, Siliang Xu, Kashun Shum, Randy Zhong, Juntong Song, and Tong Zhang. Ragtruth: A hallucination corpus for developing trustworthy retrieval- augmented language models. In Proceedings of the 62nd Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 10862-10878, 2024.
[33] Zach Nussbaum and Brandon Duderstadt. Training sparse mixture of experts text embedding models. arXiv preprint arXiv:2502.07972 2025.
[34] OpenAI. Gpt-4o mini: advancing cost-efficient intelligence, 2024.
[35] OpenAL. Hello GPT-4o, May 2024.
[36] Hongjin Qian, Peitian Zhang, Zheng Liu, Kelong Mao, and Zhicheng Dou. Memorag: Moving towards next-gen rag via memory-inspiree knowledge discovery. arXiv preprint arXiv:2409005591, 2024.
[37] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3982-3992, 2019.
[38] Stephen Robertson, Hugo Zaragoza, et al. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends@ in Information Retrieval, 3(4):333-389, 2009.
[39] Spurthi Setty, Harsh Thakkar, Alyssa Lee, Eden Chung, and Natan Vidra. Improving retrieval for rag based question answering models on financial documents. arXiv preprint arXiv:240.007221, 2024.
[40] Karen Sparck Jones. A statistical interpretation of term specificity and its application in retrieval. Journal of documentation. 28(1):11-21, 1972.
[41] Yuan Sui, Yufei He, Nian Liu, Xiaoxin He, Kun Wang, and Bryan Hooi. Fidelis: Faithful reasoning in large language model for knowledge graph question answering. arXiv preprint 1.Xiv:2405.13873, 2024.
[42] Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung- Yeung Shum, and Jian Guo. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfih International Conference on Learning Representations.
[43] Xiaojuan Tang, Zilong Zheng, Jiaqi Li, Fanxu Meng, Song-Chun Zhu, Yitao Liang, and Muhan Zhang. Large language models are in-context semantic reasoners rather than symbolic reasoners. arXiv preprint arXiv:2305. 14825, 2023.
[44] Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972.
[45] Hanghang Tong, Christos Faloutsos, and Jia- Yu Pan. Fast random walk with restart and its applications. In Sixth international conference on data mining (ICDM'06 pages 613-622.
IEEE, 2006.
[46] Liyuan Wang. Xingxing Zhang, Kuo Yang, Longhui Yu, Chongxuan Li, Lanqing HONG, Shifeng Zhang, Zhenguo Li, Yi Zhong, and Jun Zhu. Memory replay with data compression for continual learning. In International Conference on Learning Representations, 2022.
[47] Mingyan Wu. Zhenghao Liu, Yukun Yan, Xinze Li, Shi Yu, Zheni Zeng, Yu Gu. and Ge Yu. Rankcot: Refining knowledge for retrieval-aus -uggeeene generation through ranking chain-of- thoughts. arXiv preprint arXiv:2502. 17888, 2025.
[48] Yuan Xie, Yumeng Liu, Xu Zhou, Yifang Yin, Kenli Li, and Roger Zimmermann. Pbsm: Pre- dictive bi-preference stable matching in spatial crowdsourcing. In 2025 IEEE 4/ International Conference Data Engineering (ICDE), pages 765-778. IEEE, 2025.
13

---

[49] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov. and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2369-2380, 2018.
[50] Liang Yao, Chengsheng Mao, and Yuan Luo. Kg-bert: Bert for knowledge graph completion. arXiv preprint arXiv:1909.033/99 2019.
[51] Jihao Zhao, Zhiyuan Ji, Yuchen Feng, Pengnian Qi, Simin Niu, Bo Tang, Feiyu Xiong, and Zhiyu Li. Meta-chunking: Learning efficient text segmentation via logical perception. arXiv preprint arXiv:2410. 12788, 2024.
[52] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595 46623, 2023.
[53] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[54] Rong Zhou and Eric A Hansen. Beam-stack search: Integrating backtracking with beam search.
In ICAPS, pages 90-98, 2005.
14

---

A Heterogeneous Knowledge Graph in REMINDRAG
A.1 Heterogeneous Knowledge Graph Formalization
in the auto- mated knowledge graph construction framework, designed heterogeneous knowledge graph sists an entity node set E, an anchor node set A (storing text chunk titles), text chunk set C, and relational connections. The subgraph formed by entity nodes is composed of "entity-relation- entity" triples extracted by the large language model (LLM). Each anchor node A; serves as a summary of the corresponding text chunk C,, form- ing a one-to-one mapping relationship: 1) (.A,, C,) vi E {1, 2, 2,....... n.. When an entity node & ap- pears in a certain text chunk Cj. the corresponding anchor node Aj establishes connection with & Meanwhile, anchor nodes construct the Contextual Skeleton Network through ordered chain connections, with directed edges defined as: 2) (Ai, A.t1) for i = 1, 1.2.3..... as shown in Figure 7 This backbone network with chain connections anchor nodes explicitly models the contextual dependencies among text chunks C, preserving document context relationships the graph and providing support for subsequent LLM traversals. The chunk-anchor mapping designed to reduce computational costs during the Memorize Recori process. This architecture allows REMINDRAG to leverage contextual linkage relationships without requiring a chunk to be included in the enhanced answer subgraph. For ablation studies on contextual linking mechanism. see Appendix E.
Inspired by prior works 3 50
Entity
Anchor
Chunk
Figure 7: Illustration Our KG.
..... n (for text chunks), forming chain structure Ai + A2 + ... ++ An.
A.2 Automated Knowledge Graph Building
Our knowledge graph extraction pipeline follows the conventional workflow: (1) Text Chunking, (2) Named Entity Recognition, (3) Relation Triple Extraction, and (4) Knowledge Graph Building. The examples of our KG are illustrated in Figure 16
Text Chunking. Our implementation supports multiple text chunking methods, including the basic laken-count-based chunking, meta chunking (31), and LLM-based chunking [39]. For consistent evaluation, uniformly employ the basic token-count-basse chunking.
Named Entity Recognition. use the prompt shown Table 18 to extract entities from each text chunk.
Relation Triple Extraction. We apply the prompt presented in Table T9 extract relations from text chunks after entity extraction.
Knowledge Graph Building. We create chunk node and anchor node for each text chunk. For each entity, we establish a separate node. When the embedding similarity between two entities exceeds our predefined threshold (0.7), consider them synonyms and merge them. Each chunk connects to its corresponding anchor. Anchor nodes of text chunks from the same paragraph connect via the Contextual Skeleton Network. Entities link to the chunks where they occur. Related entities connect through relation edges.
B LLM-Guided Knowledge Graph Traversal with Node Exploration, Node Exploitation and Memory Replay
Overview. Our entire LLM-Guided Knowledge Graph Traversal can be divided into the following
steps: (1) Pre-query question processing; (2) Fast subgraph extraction using Memory Replay; (3)
LLM-Guided KG traversal (optional, only if the subgraph obtained in step 2 cannot answer the question); (4) Memorizing I..M-Guided KG traversal (optional, only if step was executed); (5)
Generating the answer using the obtained results. As depicted in Figure g
15

---

city captital china?"
Split Query:
User Input
Find seed
information sets:
seed entity
entiches
query
entity
chunk
query
entity
chunk
seed entity
entlity
chunk
query
Initial:
wighest
triple
cs: chunk summary
Similarity Enhedding
G0 Forward or Baackwrrd Node
triple
chunk sumnary
Update
Current
triple
sumnary
whether enough
Not Fnough
infomatiin
Enough
use information generate response: "Beijing is the capital city of china."
Generator
Figure 8: LLM-Based Knowledge Graph Traversal Process
B.1 Pre-query Question Processing
When user inputs a request I, our model first queries the large language model (LLM) to determine whether external knowledge in the knowledge graph (KG) is required respond. (Determine whether is necessary to conduct search process). If affirmative, the model decomposes the input into several subqueries Q = [ 92...... Jn SplitQuery (I). For consistency with baseline comparisons,
query decomposition was disabled during experiments shown in Section 5
B.2 Fast subgraph extraction using Memory Replay
Then every subquery is matched with the KG by embedding similarity to identify the top-K seed entities. Starting from these seed entities, we perform thresholded DFS-based subgraph expansion (as shown in Section 3.2.2) governed by edge embedding WA.B and hyperparameter threshold X. This traversal initializes three information sets:
N [ei, 62,...... Cb, c,,..., cp]: Entities and chunks in Subgraph. Cs [51 .2....,... sp]: Semantic summaries of the chunks in N.
T = [1, 12, l2,..., bm]: Triples (edges) in Subgraph.
B.3 LLM-Guided KG Traversal
The seed entity with the highest similarity is designated as the initial nodec. We iteratively ask the LLM assess whether the current information Cs, T contain sufficient information. If inadequate, the L.M prompted either as Table 12
node node from linked nodes of nodeş, node is added N. If it is a chunk, the summary processed and added to Cs. The corresponding knowledge triple connecting node, to nodenexi is added to T. Backward: to select an encountered node N. No previously collected elements in N, Cs, or T removed.
Forward: to select
This step essentially combines the "Node Exploration" and "Node Exploitation" " from Section 3.1 into single LIM call reduce costs. When the LLM selects "forward," it essentially treats the most answer-relevant node as node, and then chooses the optimal expansion node. When the L.M selects "backward," it updates the current node, to new most answer-relevant node.
16

---

origin Data
Random choice
origin Query
Answer
Mu Multiple-choice Data
RAG
Answer
Query
True False
Compare
Rewri Answer
Generated Answer
Rewrite te
Figure 9: LooGLE Test Pipeline
B.4
Memorizing LLM-Guided KG Traversal
After the query concludes, we use Table 13 to select the nodes edges in the answer subgraph that contribute the answer. We then perform a DFS search to enhance the paths leading to these nodes edges while penalizing other paths. The detailed process is shown in Section 3.2
B.5 Generating the Answer Using the Obtained Results
Finally, once the information is deemed sufficient, the LLM generates a response to the user query based on the information in Css and T.
Our framework utilizes ensemble of prompt instructions. Due space constraints, focus specifically on illustrating the fundamental 'node selection (LLM-Guiddd KG Traversal) prompt (Table [2). with the complete of supplementary prompts available in open-source code repository.
C Experimental Dataset
The QA pairs in the Free-response Question format of the original LooGLE dataset suffer from substantial semantic coverage bias issues. Specifically, when generated answer contains more comprehensive information than the reference answer, the GPT-4 discriminator in LooGLE (which relies on semantic equivalence) frequently marks the question as incorrect, because the real answers LooGLE rarely achieve complete semantic coverage of the generated answers-even when generated answers are substantively correct. Therefore, we have reformatted these questions into a multiple-choice pattern using LLMs: first, the original question provided to the RAG system, and based its returned content and the reformatted multiple- -ciiicce-cciceeeeec questions, GPT-4o is used for selection. This approach avoids information leakage while ensuring the objectivity of answer evaluation (see Appendix C.I for the dataset reformatting methodology). Some dataset samples can be found in Appendix C.2 Meanwhile, the rewriting process for the "Similar" and "Different" fields in Section 5.2 is also demonstrated in Appendix C.3 and Appendix C.4
C.1 Dataset Transformation Methodology
The standardized experimental pipeline employed in this study is illustrated in Figure 9 For each question in the LooGLE dataset (24). we process the original data through the following procedure: The "question", "answer". and "evidence" fields from the raw data are provided as input to the GPT--0o 35 model, which is instructed to generate multiple-choice question with four options. The correct option is derived from the given answer, while three plausible distractors are constructed based on the "evidence" field. The specific prompt template for question transformation can be found in Table [4
17

---

To prevent potential information leakage and ensure fair evaluation, we implement a two-stage processing strategy: First, the original question is fed into the retrieval system: subsequently, GPT-4o selects the most appropriate answer from the generated options based on the retrieval results (with the option to abstain if confidence is insufficient). The detailed prompt template for option selection is provided in Table This design maximizes the objectivity and scientífic rigor of the evaluation process. Some dataset samples are illustrated Appendix
C.2 Multiple-Choice Format of the LooGLE Dataset
This section presents several examples from the multiple-choice version of the LooGLE dataset for reference. As shown in Figure TOa for the original question, both DEMINDRAG and other baseline methods face challenges in evaluation because all four options are presented in a (number-number) pair format. Consequently, when verifying answers, LLMs struggle to determine whether the model's response refers to an option or the actual answer.
Additionally, as illustrated in Figure T0b we observe that nearly all methods incorporate the evidence "but available second-hand." into their responses. However, during answer verification, the model lacks awareness of whether this information is factually correct. Since the LooGLE reference answer does not include this detail, such responses are incorrectly judged. These cases are uncommon, which motivated our modifications to the dataset.
Title José Luis Picardo
Origin Query
Answer
Title José Luis Picardo
Picardo created lots of illustrations for a book named &Dibujos de Jose Luis Picardo in 1960,
The book is long out of print and virtually unknown in Spain, and not at all elsewhere.
Origin Query
Answer
How many people in Picardo's family when was twelve?
where is this original book kept now?
3
seven 2. 3. five 4.
Evidence
Evidence
[ ("The book is long out of print and virtually unknown in Spain, and not at all elsewhere, available second- hand.")
["His father was Alvaro Picardo de Celis and his mother's family Castellón. He had four brothers, of brothers died in infancy.", "His father died 1929 when Picardo was ten years old."]
Rewritten Query
Where the original {Diibujos de Jose Luis Picardo created 1960, currently kept?
Rewritten Query
A. In the National Library of Spain
How many people were Picardo's family when he was twelve?
B. In major European art museum C. It is long out of print and virtually unknown in Spain, and not at all elsewhere
A. Seven B. Five C. Six D. Four
D. In private collection in South America
(a) Ambiguous Answer Reference
(b) Insufficient Answer Information
Figure 10: LooGLE Dataset Samples
C.3 Similar Question Rewriting Details
For questions "Long Dependency QA" and "Hotpot QA", we employed the prompt templates from Table 15 to rewrite them. While preserving the essence of each question, we aimed to maximize the surface-level differences between the rewritten and original versions. A concrete example of such rewriting is provided in Figure I1
18

---

ORIGIN QUESTION:
Among 10 districts of Barcelona, Which district has the highest population density?
SIMILAR QUESTION:
Which district in Barcelona has the greatest population density among its 10 districts?
Figure 11: An Example of Similar Question in LooGLE
ORIGIN QUESTION:
What science fantasy young adult series, told first person, has set of companion books narrating the stories of enslaved worlds and alien species?
SUBTLE DIFFERENCE QUESTION:
Which young adult science fantasy series, narrated from multiple perspectives, includes companion books detailing the histories of enslaved worlds and alien species?
Figure 12: An Example of Subtle Difference Question in Hotpot QA
C.4 Subtle Differences Question Rewriting Details
For questions in "Hotpot QA", we used the prompt templates from Table to rewrite them. While maintaining as much semantic similarity as possible, we altered the questions so that their answers differed from the original versions. specific rewriting example shown Figure
D Implementation Details
D.1 Experimental Configuration
To ensure the reproducibility of our experiments, all tests were conducted with consistent parameter configurations. The random seed for the large language model was fixed 123, and the temperature parameter was set to to eliminate randomness in the generation process. Additionally, GPT- 4o is employed our LLM-based evaluator. Furthermore, all dense embedding computations employed the "nomic-ai/nomie hataaaaaiiiiiimeeeddeeeeeee -emmeedtext--2-mmee model [33] as the foundational embedding model. For tokenization operations, we uniformly adopted the coomic-a/nomic-mmee--eeee
moe" as tokenizer, with all token-based chunks standardized to 750 tokens in length. For detailed parameter settings of other experiments, please refer to Appendix D.4
D.2 Compute Resources
In our experiments, we employed GPT-4o-mini 34] and Deepseek-V3 (88 as the underlying large language models (LLMs). (All operations utilizing large language models (GPT-4o, GPT-4o-mini, V33 are completed by invoking APIs). Notably, the proposed experiments can be readily replicated ordinary machines, ensuring broad accessibility and reproducibility for the research community. Experiments were executed on a dedicated research workstation configured with an AMD Ryzen 7 7800X3D 8-Core Processor, NVIDIA GeForce RTX 4070 Ti SUPER GPU, and 64 GB of DDR5 RAM.
D.3 Evaluation Metries
Our efficiency is quantified in our paper through token consumption. Our decision not to use and can not use precise wall-clock time latency as a direct metric stems from two key reasons: (1) the strong correlation between L.M inference time and the number of output tokens, and (2) the inherent uncertainties and fluctuations caused by network latency during API calls LLMss, which would introduce inaceuracies into direct time measurements.
19

---

D.4 Parameter Configuration
The system involves the following key parameters:
Node Correlation Weight (o): This parameter adjusts the system's reliance on edge embedding for determining strong links. Experimental validation suggests setting a within the range of 0.1-0.2. In this study, we adopt 0.1.
typically set it value below 0.775, but this is only under thcoretical conditions. In practice, various factors should be comprchensively considered-scttineg
Strong Connection Threshold (A): As discussed in Section 4
too low may lead to increased retrieval costs due to lower memory threshold outweighing the noise reduction, while setting too high may result in reduced memory capacity. Through empirical testing, consider values between 0.5 and 0.75 to be reasonable. In the experiments of this paper, we select this value as 0.55.
Other critical parameters include:
Synonym Similarity Threshold:
Used during knowledge graph construction to merge entities whose embedding similarity exceeds this threshold. This value should be adjusted according to the specific embedding model characteristics. Our experiments employ 0.7 as the default value.
Maximum Hop Count:
Controls the maximum number of nodes (hops) during subgraph expansion for word queries. We set this parameter to 10 to balance computational efficiency and information completeness. For other baselines with similar configurations, we uniformly apply the same setting for fair comparison.
Question Decomposition Limit: Determines the maximum number of sub-questions for semantic decomposition of user queries. To maintain comparability with baseline methods, set this to 1 (i.e., preserving the original question without decomposition).
Initial Seed Node Count: Specifies the number of seed nodes in the query initialization phase. We configure this as 2 seed nodes (selecting the two most query-relevant nodes), consistent with relevant baseline studies.
D.5
Implementation of Baselines
Traditional retrieval methods:
BM25 38 A classic information retrieval algorithm improving on TF-IDF 40, it estimates
document-query relevance via probabilistic framework. It effectively handles long documents and short queries by integrating term frequency (TF), inverse document frequency (IDF), and document length normalization to calculate relevance scores, enhancing retrieval accuracy through adaptive term weighting. Following its principles, we have realized the algorithm.
The NaiveRAG paradigm, an early "Retrieve-Read framework, involves indexing muuli--orrma data into vector- vector-encoded chunks stored in database, retrieving top-K similar chunks via query vector similarity, and generating responses by prompting large language models with queries and selected chunks. We have developed the corresponding code based on its principles.
NaiveRAG (23).
Traditional KG-RAG systems:
This framework enhances retrieval-augmented generation (RAG) to mimic human long-term memory, addressing factual memory, sense-making, and associativity. It uses offline indexing to build knowledge graph (KG) with triples extracted by an LLM, integrating phrase nodes (concepts) and passage nodes (contexts) via synonym detection. Online retrieval links queries to KG triples using embeddings, filters irrelevant triples with an LLM (recognition memory), and applies Personalized PageRank (PPR) on the KG for context-aware passage retrieval. Improvements include dense- rense-sparse integration, deeper query-to turry-to- contextualization. and effective triple filtering.
HippoRAG2 13
LightRAG [ This method addresses limitations of existing RAG systems (e.g., flat data rep- resentations, insufficient contextual awareness) by integrating graph structures into text indexing and retrieval. It employs a dual-level retrieval paradigm: low-level retrieval for specific entities/re- lationships and high-level retrieval for broader themes, combining graph structures with vector
20

---

representations to enable efficient keyword matching and capture high-order relatedness. The framework first segments documents, uses LLMs to extract entitess/elationshiss, and constructs a knowledge graph via L.L profiling and deduplication for efficient indexing.
This approach aims to enable large language models (LLMs) to perform query- focused summarization (QFS) over large private text corpora, especially for global sensemaking queries that require understanding of the entire dataset. It constructs knowledge graph in two stages: first, an LLM extracts entities, relationships, and claims from source documents to form graph where nodes represent key entities and edges represent their relationships. Second, community detection algorithms partition the graph into a hierarchical structure of closely related entity communities. The LLM then generates bottom-up community summaries, with higher-level summaries recursively incorporating lower-level ones. Given a query, GraphRAG uses map- reduce process: community summaries generate partial answers in parallel (map step), which then combined and summarized into final global answer (reduce step).
GraphRAG [9]
For these three baselines, we use their default hyperparameters (except for chunk size, which uniformly set to 750, consistent with REMINDRAG) and prompts.
LLM-guided KG-RAG system:
Plan-on-Graph (PoG) [6]. This paradigm aims to address the limitations of existing KG- augmented LLMs, such as fixed exploration breadth, irreversible paths, and forgotten conditions. To achieve this, it decomposes the question into sub-objectives and repeats the process of adaptive reasoning path exploration, memory updating, and reflection on self-correcting erroneous paths until the answer is obtained. PoG designs three key mechanisms: 1) Guidance: Decomposes questions into objeettjessves with conditions to guide flexible exploration. 2) Memory: Records subgraphs, reasoning paths, and sub-objective statuses to provide historical information for reflec- tion. 3) Reflection: Employs LLMS to decide whether to self-correct paths and which entities to backtrack to based memory. We adapt their code from their GitHub repository [TO to use the KG constructed by REMINDRAG (More details can be seen at Appendix E.2.1)
For all methods described above, the 'nomicai/nomic--mbeed wew.-eeewweeeee-ee--eeeee-e----e text-v2-moe" model is uniformly used as the embedding model. Methods incorporating knowledge graph memory functionality utilize ChromaDB for knowledge graph storage.
D.6
Implementation of LLM--a-judgmment
Followed previous work 24 We employ the prompt shown in Table II to conduct LLM-as-judge
(GPT-4o) based answer evaluation.
D.7
Additional Experiments on More Baseline Models
For better understanding, we consider an additional baselines MemoRAG [3). This framework enhances RAG to tackle long-context processing, overcoming conventional RAG's reliance explicit queries and well-structured knowledge. Inspired by human cognition, it uses a dual-system architecture: light long-range system builds global memory (via configurable KV compression) optimized by RLGF (rewarding clues that boost answer quality), and an expressive system generates final answers. For tasks, the light system produces draft clues to guide retrieving relevant evidence from long contexts, then the expressive system outputs the final answer. It outperforms advanced RAG methods (c.g.. GraphRAG (9] and long-context LLMs in both QA and non-QA QA tasks, with balanced inference efficiency.
Experimental Setup. Given MemoRAG [6''s 's capability manage memory for ultra-long texts, we focused our evaluation on the LongDependency(K task of the LooGLE dataset [24] in this experiment; for the baseline configuration, the model employed is gpt-4o-mini, the embedding_ model is uniformly set to pomiccalnomii--embeleeeett all other parameters adhere to MemoRAG's default pettings-includin which adopts its default value of -aaoorrg-mmttal--b--nae The pre-trained weights of memorag- mistral-7b-ins were obtained from the Hugging Face Hub, and we verified the model's license
(consistent with our experimental setup), and
the mem_ modee parameter,
21

---

agreement (Apache 2.0) on its official Hugging Face Model Card to ensure compliance with research usage requirements, avoiding potential issues related intellectual property or usage restrictions.
Methods
Baseline Model
Task (%)
MemoRAG
gpt-4o-min.
46.97
HippoRAG2
gpt-4o-mini
39.60
REMINDRAG
gpt-4o-mini
57.04
Table 5: Performance on Long-Dependency- Task (Accuracy f).
Experimental Results. As shown in Table 5 MemoRAG indeed demonstrates strong performance in long-dependency tasks: its 46.97% accuracy on the poRAG2's 39.60% by 7.37 percentage points, result supported by its dual-system architecture that efficiently builds global memory and optimizes clue selection via RLGF. However, it still lags significantly behind our REMINDRAG method-ou approach achieves 57.04% accuracy, 10,07- percentage-poie lead over MemoRAG, as MemoRAG's KV compression may lose fine-grained long-range information, while REMINDRAG better captures dynamic, long-distance associations critical to the task.
Task outperforms Hip-
E
Additional Experiment Analysis
E.1
Additional Analysis on REMINDRAG
Contextual Information Capture Capability. We designed ablation ex- periments to investigate the impact of Contextual Skeleton Network RE- MINDRAG'S knowledge graph vari- ants on performance, with results shown in Table 6 The experimental results demonstrate that removing the Contextual Skeleton Network leads to a slight performance degradation in REMINDRAG (no effect was ob- served in Multi-Hop question scenar- ios since the input data inherently consists of discrete single documents without multi-chunk cases within individual documents). Through in-depth analysis, we identify that this performance decline may stem from the following mechanism: The token-based chunking strategy may forcibly segment semantically coherent text, thereby compromising textual integrity. For instance, when the referent entity text fragment appears as pronoun, the knowledge graph typically fails to establish direct associations between this entity and the text fragment. In contrast, large language models (LLMs) can actively access relevant contextual information through the chain connections of the Contextual Skeleton Network, thereby compensating for this deficiency.
Methods
Long
Multi-Hop
Simple
REMINDRAG
57.04%
74.22%
76.67%
-w/o CS
51.01% %
74.22%
73.07%
HippoRag2 13
38.06%
68.04%
73.08%
Table 6: Ablation Study (Accuracy f). "CS" denotes the Con- textual Skeleton Network in the Knowledge Graph. Using "GPT-4o-mini" as the backbone.
The Impact of Different Hop Count Settings. We investigate the influence of various hop count configurations on system performance. Specifically, through experiments, we analyze the effect of the Maximum Hop Count parameter in the RE- MINDRAG model (the relevant parameter definitions are detailed in Appendix D.4). As illustrated in Figure
Methods
Avg. API Calls
Token Ratio
Total Tokens
REMINDRAG
2.64
1.25M
GraphRAG 9
14.73
15.42
7.31M
HippoRag2 13
3.91
1.87M
Table 7: Graph Building Comparative Experiment.
13 the experimental results demonstrate a significant positive correlation between model performance and hop count settings: as the Maximum Hop Count value increases, the classification accuracy of the system exhibits monotonically increasing trend. This finding aligns with the
22

---

60%
100%
50%
80%
Accuracy
Accuracy
40%
60%
30%
40%
20%
10%
20%
0%
0%
2
10
6
Max Hop Count
Max Hop Count
(a) Performance on Long Dependency QA.
(b) Performance on Multi-Hop QA.
Figure 13: The Impact of Different Hop Count Settings.
fundamental principle of the LLM-Guuded Knowledge Graph Traversal in REMINDRAG, where larger hop count enables nodes access broader neighborhood information, thereby enhancing their informatiion-gatheiing capability.
Cost Analysis of Graph Building. We compare the graph building costs between REMINDRAG and other baselines. As shown in Table[7] experimental results on the LooGLE dataset demonstrate that method achieves significantly lower ratio of consumed tokens to souree text tokens during the construction process compared to high-overhead systems like GraphRAG 20 competitive performance against other baseline approaches.
while maintaining
Analysis on Path Consistency. To demonstrate that semantically similar queries correspond to similar graph paths, we design experiment quantify the similarity between search paths of an original problem and similar problem. We model the search paths as sets of edges, where an "edge" refers to a direct connection between two nodes. Let E represent the set of edges in the original problem's search path, and Eg represent the set edges in the similar problem's search path.
The similarity S between Ej and Eg is defined as the ratio of the number of identical edges (intersec- tion of the two sets) to the total number of unique edges (union the two sets after deduplication). Formally, this is expressed as:
F1 0 F22 s
E U Egl
Here, E,, O E2| denotes the cardinality of the intersection (i.e., the count of edges shared by both search paths), and EE U E2| denotes the cardinality of the union (i.e., the total count of distinct edges present either search path). A S value closer indicates higher overlap between the search paths (implying more similar underlying logic), while a value closer to 0 indicates greater divergence.
To obtain comprehensive measure, define the aggregated similarity Sayg the average of all individual similarity values from multiple calculations:
1 n
L>s, S. n
Sag
where n the total number of similarity calculations performed, and S; is the similarity from the i-th calculation. We first ran the original problems and then the corresponding similar problems. Taking the base model GPT-4o-mini as an example, the experimental results for similarity are presented in T From these experimental results, it is evident that semantically similar queries induce similar graph paths.
Task
Savg
LongDependency(A
53.78%
Table 8: Similarity results for the base model GPT-4o-mini.
23

---

Query Order Impact. To evaluate whether the order of questions (introduced via random shuffling) affects the system's performance. we designed an experiment where questions in the dataset were randomly shuffled before each system update, with three accuracy measurements taken to assess the system's robustness to input order variations.
Specifically,, we integrated random question shuffling module into our codebase. The experiment proceeded in three stages: For Update times We first randomly shuffled the questions and measured the system's 's accuracy without any prior updates; - For Update times = 1: After the first system update, we re-randomly shuffled the questions (generating a new order distinct from the first) and measured accuracy; For Update times 2: After the second system update, we again re-randomly shuffled the questions (generating& a third unique order) and measured accuracy.
For each stage, we also recorded the original accuracy (i.e., accuracy with unshuffled questions) for comparison. The experimental results are summarized in Table 9
Update times
Accuracy (With Re-shuffled Questions)
Original Accuracy (Unshuffled)
0
56.37% %
57. .7.04%
1
55. %
56.48%
2
57.71 %
58.01 %
Table 9: System accuracy on Long-Dependency-Te with re-randomized question orders before each update (with original accuracy for comparison). A new shuffled order was used for each update stage.
From Table we observe that even with a fresh random shuffle of questions before each update, the system's accuracy remains consistently close to the original accuracy (with unshuffled questions) across all stages. Specifically, at Update times = O, the shuffled accuracy (56.37%) is comparable to the original (57. 67.0%%);; after the first re-shuffle and update (Update times 1), the gap remains minimal (55. 75% vs. 56. 48%) and after the second re-shuffle and update (Update times = 2). the trend persists (57.71% vs. 58.01%). These results confirm that repeated random shuffling of question order- even before each system update- has negligible impact on performance, demonstrating the system's 's strong robustness to input order variations.
E.2
Additional Analysis on Baselines
E.2.1
Analysis of PoG
In the field of KGQA (Knowledge Graph Question Answering). we select the latest method PoG (a self-correcting adaptive planning paradigm for KG-augmented LLMs) as a representative. Since the original method is exclusively designed for the Freebase knowledge graph (2]. we modify the source code of PoG (the revised code is open-sourced on GitHub) to adapt it to our own knowledge graphs, allowing traversal of nodes in our constructed knowledge graphs. (As PoG only handles node-level processing, the knowledge graph provided to PoG excludes the chunk component.) We greatly appreciate their open-source contribution.
We retain PoG's implementation methodology and prompts, only altering the output examples in parts of the prompts to adapt the format; code differences can be viewed 4open science/r/PoG_.tet adapted- aatoo__ddpteddCCCC.. The accuracy rates show that the method of conducting Large Lan- guage Model (LLM) traversal search solely the nodes of the knowledge graph, which lacks all textual information, significantly reduces the search accuracy. Compared with our method, PoG's performance on each dataset drops significantly.
QA Type
GPT-4o-mini
DeepSeek-V3 V3
Long Dependency QA Multi-Hop QA
30.29K
25.88K
5.53K
6.96K
https:///aony:::
Simple QA
27.11K
21.21K
Table 10: Comparison of the Average Token Consumption of the PoG Method across Different QA Types
24

---

Additionally, DeepSeek- V3 exhibits a more pronounced inclination toward conservative strategy. leading a higher search depth and greater token consumption compared GPT-40-mini, It frequently outputs null answers due to perceived lack of sufficient information, which is also clearly evident in GraphRAG (Appendix F.2.2).
Since the source code of PoG mentions that the maximum search depth is set to 4, in the case of knowledge graph relying on long-text associations (the revised code we wrote sets the maximum depth to 10, which is consistent with our method), the performance is poor, and the consumption of tokens has significantly increased compared with ours, as shown in Table IO However, for the simple multi-hop dataset of HotPotQA, which extracts information from Wikipedia and has extremely limited information volume, token consumption more optimized than ours. We believe that such simple question -aneeionnn dataset cannot well represent the real-world scenarios, and many questions still require complex information extraction. Therefore, the efficiency optimization searching in complex datasets is of greater application value. For other methods, since they do not involve L.M traversal, comparing token consumption is of little significance.
E.2.2 Analysis of GraphRAG
Based the feedback similar issues from GitHub users, hereby analyze the reasons for the relatively poor performance of GraphRAG In order to aim for a low hallucination rate, GraphRAG often outputs responses like "More information needed." " For example, Figure 14 showss a question and its generated answer.
Title
José Luis Picardo
Query
Generated Response
How many years did Picardo work on Parador projects
don't have access to enough specific data tables or records that would contain information about Picardo's employment timeline with Parador or the dates of Parador's projects bankruptcy. supporting data, cannot provide an accurate answer to this question.
before the chain's bankruptcy?
A. Fifteen years
Twenty-one years
the
Twenty-five years
D. Twenty-nine years"
if you provide the relevant data tables containing: 1. Picardo's 'ss employment records with parador parador projects worked on 3. date of parador's bankruptcy would able analyze this information and give you precise answer about the duration his employment. without might provide would be speculative rather than evidence-based
Answer
D. Twenty-nine years
2.
any number
Figure 14: Comparative Illustration Subtle Difference Questions in the Knowledge Graph.
Deepseek-V V3 is more inclined to provide conservative outputs compared to GPT-4o-mini (often requesting more information from users instead of providing direct answers), so accuracy rate has dropped significantly. We have also found that, unlike other methods, GraphRAG is more effective at retrieving for -ongdeeendencc question-answerinn tasks, while its retrieval ability for short-dependency question-answering tasks has declined.
F Theoretical Analysis
This section presents theoretical analysis of the memory capacity of REMINDRAG. We demonstrate that, given set of queries exhibiting some degree of semantic similarity, our memorization rules in Equation (1) enable edge embeddings memorize these queries and store sufficient information, thereby enabling effective memory replay. Formally, for any given edge, when the maximum angle between all query embedding pairs within query set satisfies Equation 4). the edge can effectively memorize the semantic information within that query set.
(vi sin sin(arccos(A))) Finiam(rrooo ]
lim d do
2 arcsin
(4)
25

---

Assumption For typical path A - B in the knowledge graph where E E, we define that this path "remembers" [12 query q when q e We assume that the input query embedding
normalized, i.e. |ggl
Proposition 1 For set of query embeddings Q Rh, we have
Vqn, 92 Q: (1a,,,10 42) S arcsin
3n E (21.01...
02. 02.... E Q",
such that Efmal = (fan .... o (0) satisfies Vq E Q efiial > A
Q can be represented sphere Sd-1, i.e., there exists a bijective mapping 4 Q N N (0, for all E Q.
Proof 1 Each query embedding
point the d-dimensional unit
Assuming 4q1, E Q, their angle satisfies Z(q1. 92) < 0, the corresponding point set N satisfies VP1,P2 E N, dga-1 (P),P2) < 0, where dg--1 denotes the geodesic distance on Sd-1
According to Jung's Theorem on Spheres 19 in Sd-1, there exists ball P TBd-1(cpp)) Tp)
containing N whose geodesic radius satisfies:
(Verd sin(rs)) 2d
(V3
8 2 2 arcsin
doo0
0 2 arcsin
Since typically deal with very high embedding dimensions in practice, we can approximate + co.
From Jung's 's Theorem, the center cp of the covering ball P lies within the convex hull of N. Therefore, the unit vector =-== (cp) satisfies:
1) bq E Q./(c,9) STp = (c, 1) 2 cos(rr).
2) There exist coefficients (17, (i CR+ with Σ = 1 such that c == Eis Tkl..
From (2), it follows that there exists an update sequence (4i, (m S Q such that:
lim (fa... o...o fu., (0)
Efinal
Since (xx aresin (v sin(rp)) is monotonically decreasing:
(Vi (im 20 -
A S cos(Tr)
= 2 aresin
= bq E Q, (Efonnt 9) 2 X
which satisfies the proposition's requirements.
G More Detailed Case Study
G.1
An Example of Complete Retrieval Process
In Figure 15 we present complete example of our retrieval process. This essentially illustrates the detailed procedure of the earlier Case Study in Figure
G.2 WebUI Screenshots
As shown in Figure I6 we present screenshots of REMINDRAG's web interface, which essentially correspond to the content of the earlier Case Study in Figure
We ignore the first term in Equation 2 it mainly serves to adjust the system's 's sensitivity to memorized data and is multiplied small coefficient, rendering its overall impact the final result relatively minor.
26

---

Query: Were Scott Derrickson and Conrad Brooks born in the same country?
Step Subgraph Initialization
( Derrickson), Brooks]
Step 2: Memory Replay
Initial Subgraph:
Scott Derrickson anchor-2 -> chunk-2
Subgraph Info Enough? False
Step 3: Path Expansion Loop (LLM-Guided KG traversal)
Loop: 1
Add Node: : anchor-2 > California
Expand Subgraph:
Derrickson
chunk-2
foriio
Conrad Brooks
Subgraph Enough?
Loop: :2
Add Node: Conrad Brooks anchor-9
Expand Subgraph:
Derrickson
L california
Conrad Brooks >> anchor-9
Subgraph Info Enough? False
Loop: :3
Add Node anchor-9 > chunk-g
Expand Subgraph:
Scott Derrickson anchor-2 +> chunk-2
Ly califomia
Brooks anchor-9
Subgraph Info Enough? True
Step 4 Memorizing LLM-Guided KG Traversal
Filter Path
Enhance Path:
berricksor anchor-2 chunk
Conrad Brooks anchor-9 chunk-9
Penalize Path:
Step 5: Generate Answer
Response: Yes, Scott Derrickson Conrad Brooks were born the United States.
Figure 15: An Example of Complete Retrieval Process
27

---

OMR
Crock
Aperan boky
concer
oder
ypercal
Comerite
(a) KG For First Query
(b) KG For Second Query
Figure 16: WebUl Screenshots
H Broader Impact & Limitations
Currently, large language models (LLMs) face two typical challenges stemming from the Transformer architecture: limited context window capacity and the hallucination problem. Retrieval-augmented techniques offer viable solution to these critical issues and have gained popularity in various application scenarios. The proposed REMINDRAG achieves high-precision retrieval in diverse complex scenarios, thereby driving comprehensive improvements in human-computer interaction. It enables AI systems to provide more accurate and stable services to society, facilitating the broader integration of AI technologies into daily life.
However, REMINDRAG still exhibits the following limitations: (1) For extremely large documents, constructing knowledge graph requires substantial time and computational resources; however, still much faster than GraphRAG. (2) While the initial retrieval process with I.LM- --giddddd knowledge graph traversal leads to significant accuracy improvements, substantial computational resource consumption remains. Our efficiency enhancements focus on subsequent searches; however, further optimization is needed to address the high computational overhead resulting from multiple LLM calls during initialization.
28

---

The Answer Evaluation Prompt
Given one question, , there is groundtruth and predict answer. Please decide whether they the not in semantic. Please only output True or False. Question: (question)
groundtruth pneference_answen predicted answer [generated_outtpu)
Only output one word(True or False), without any additional content.
Table 11: The Answer Evaluation Prompt
29

---

The Node Selection Prompt
You comprehensive analysis expert currently executing search in knowledge graph, evaluating the current search path and determining the next search node.
The knowledge graph we ve've constructed is structured as follows: Entities are divided into two types: one can be called a general ** entity**, and the other, more specific, is referred to an **anchor
Chunks are connected through anchors to achieve contextual linkage. Users search by querying general entity nodes until they reach an anchor node, thereby accessing the corresponding chunks. Anchors connect to both general entities and other anchors (and may also link to chunks), while queryable entities can only connect to other queryable entities or anchors.
You are currently at node **{c_node)=*. Based on the current search path and the conditions for determining the next search node, combined with the information suitable next search node.
the knowledge graph, please provide the
The already traversed path is composed of: =*(entity_list)*. List of entities visited.
**{chunk, List of chunks accessed.
**(edge_list)*x List of edges traversed. The adjacency relations of the current node **[c_node)*x are: *x(relattion.cnode)*: Relations leading to the next searchable entity nodes.
cetpanectionccoodea_ee Relations leading the next anchor nodes connected chunks.
Your visit history: (c_node_list), please avoid repeatedly accessing the same node multiple times.
Additionally, I will provide you with summary information of the chunks bound to the anchors you have traversed and may potentially traverse for reference: Consider the following two types of information:
1. The semantic relationship between the already queried path, the summarized *"(chunk_sumarryhl
and the original query **(query)**
2. The edge weights of the nodes connected the current node (in **{ relation_cnodell
and [ecoomectionnccooeee+:a indicates greater importance.
A higher weight
Determine the most suitable nert node (which can be either anchor node).
searchable entity node If the current node has no unexplored adjacent nodes, then based on (1), select the most suitable node from the already traversed path each node in the path may still have unexplored connections. For example, in A -> -> C, if has (1) and decide whether returning your task is simply to return B).
node, you need to evaluate B the best choice. In this case
Note that you should never select a chunk that has already been selected.
Anchor nodes original document. If you need to access contextual information from section, you can traverse through these anchors.
connected
their contextual anchor nodes in the
Please first analyze the above steps, then derive your answer At the end of your response, provide the ansver in the specified format the node type (either **entity** or **chunk**) followed by its ID, without additional explanatory text.
Table 12: The Node Selection Prompt
30

---

The Knowledge Graph Filtering Prompt
Now, have completed search knowledge graph database.
The structure of the constructed knovledge graph is as follous: Entities divided into two types: one can be called general ** **anchor
entity**, and the other, **.
specific, is referred
Chunks are connected through anchors to achieve contextual linkage.
Users search by querying general entity nodes until they reach an anchor node, thereby accessing the corresponding chunks.
Anchors can connect both general entities and other anchors (and may also link to chunks), while queryable entities can only connect to other queryable entities or anchors.
Please assist with the following analysis:
Based on the given search path, chunk summaries, and query, analyze which edges and chunks contain valuable information for answering the current query.
The current query is **(quer)***, and relationship edges the search path are [[tedge_list)+e which consists of nodes and chunks. The chunk summaries are
1. General Judgment Criteria*t: Based the summary text and previous responses, determine whether they are directly relevant to the current query.
**eeevant Criteria*: Can directly support/refute the conclusion of the question provide key evidence.
**Irrelevant Criteria*:: Redundant information, off off-topic, replaced by more accurate data.
2. **Chunk Relevance Assessment**: Apply the above criteria to each
chunk in the summary.
3. Edge Relevance :ssessment**: Apply the above criteria each edge.
The output should include your thought process followed by a JSDN formatted result. Refer to the example provided. Please that the chunk_id must be single positive integer only. For example, "chunk:1" is an incorrect chunk ID, while "1" is correct. Also, please prioritize selecting valid information from the chunk whenever possible, as the chunk always contains the most complete information.
**Dupuu Format**: (Your thought process in here) cot
{{
"edges": [list of useful edges (using edge IDs)], "chunks": [list of useful chunks (using chunk IDs)]
}
Table 13: The Knowledge Graph Filtering Prompt
31

---

Table 14: The Question Transformation Prompt The Question Transformation Prompt
I'm going give you question, the correct answer, supporting evidence.
Based on this information, please rewrite the question as a multiple- choice question with four options. In the multiple-choite question you create, the option should (new-ans).
When creating the incorrect options (distractors), make sure they are plausible based on the question and evidence, so test-takers can't easily guess the right answer
Question: fquery)
Correct answer: {ans}
Supporting evidence: {evidence)
When you output the question, provide only the question and its options (A, B, C, D).
Here 's an example of the expected output format:
Example Output:
What is the capital of the United States?
A. New York
B. Washington
C. San Francisco
D. Los Angeles
The Similar Questions Rewriting Prompt
Now I'll give you question, and want you rewrite different question that means the same thing but phrased differently.
Original question: (query)
Example:
Original question: Is Beijing the capital China?
Your Output: Is the capital of the People's 's Republic of China Beijing?
When you respond, just give your rewritten question.
Table 15: The Similar Questions Rewriting Prompt
32

---

The Subtle Difference Questions Rewriting Prompt
Question Rewrite
Now I'1l give you a question, and want you to rephrase it way that remains as similar as possible to the original but may yield a different answer.
Please that your rephrased question must be answerable based the reference material.
Original question: {query} Reference Material: (context)
Example:
Original question: Are both Beijing and Shanghai cities China?
Your output: Are both Beijing and Chengdu cities in China?
When responding, just provide your rephrased question.
Answer Rewrite
Now I'1l give you a question, and want you to answer based on the reference material.
Please note that your answer must come from the reference material. Question: {query} Reference Material: {context)
Example:
Original question: Are both Beijing and Shanghai cities in China?
Your output: Yes
When responding, just provide your answer
Table 16: The Subtle Difference Questions Rewriting Prompt
The Option Selection Prompt
Instruction: Given question and an original answer, please revrite the original
If the original ansver is not related to any option in the question, output "I don't knos". Otherwise, rewrite the ansver to only contain the actual response to the question without any related analysis references.
If the Original answer outputs "I don't know", directly output "I don t know".
Please output the rewritten answer directly.
Question {question)
Original answer (generated-
Table 17: The Option Selection Prompt
33

---

The Entity Extract Prompt
Extract entities and entity relationships from the following text, then output the complete merged statements of entities and entity relationships.
An entity should be a simple and easy-to-understadd word or phrase. An entity should be a meaningful word or phrase. For example, in the sentence "David is seventeen years old," "David" is meaningful entity, but "seventeen years old" is not.
An entity a persistent concept with broad significance, not temporary one. For example, "twenty years old," "one hundred dollars," or "building collapse" cannot be entities.
At the same time, an entity typically refers to specific thing concept with clear identity or definition. For example, in the sentence "The distance betveen New York and Boston not far," "New York" and "Boston" are entities, but "distance" is not. When extracting entities, this process should be precise and deliberate, not arbitrary Entity types include organizations, people, geographical locations, events, objects, professional concepts, etc.
careless.
An entity relationship is simply predicate statement that describes the subject, object, and their relationship.
Please note that the entities you extract conjunctions like 'or' or 'thd' should precise standalone.
include
The output format is follows: ["entity_1", "entity_2",
"entity_n"]
Example 1:
Given text: This travel guide is very detailed, including introductions to popular attractions, reconmendations for local delicacies, and practical transportation guides.
Output:
["travel guide", "attractions introduction", "food recommendations", transportation guide"]
Example
Given text: In this world, police are supposed to catch thieves.
Output: ["police", "thieres"]
Please note: Your final output must strictly follow the required JSON format and should not include any additional content.
Table 18: The Entity Extract Prompt
34

---

The Relation Extract Prompt
For the chunk text I'm about input, it contains the following named entities: (entity.list). Please extract the relationships between these named entities. Each relationship should be predicate phrase describing the connection between the subject and the object.
For example, in "Tom" "raises" "dog", "raises" is the relationship After extracting relationship, combine it with the subject and object to form complete sentence.
Your final output should contains three elements:
JSON formatted list where each sub-list
[The subject of the relationship, The complete relationship sentence, The object of the relationship]
I'1l provide some examples next for your reference when generating the output.
Example
Given text: This travel guide is very detailed, including introductions to popular attractions, recommendations for local delicacies, and practical transportation guides. Output
["travel guide", "travel guide includes attractions introduction.", "attractions introduction")
["travel guide", "travel guide includes food recommendations." food recommendations"),
["travel guide", "travel guide includes transportation guide.", transportation guide")
]
Example
Given text: In this world, police are supposed to catch thieves. Output:
["police", "police supposed to catch thieves.", "thieves") ]
Please note: Your final output must strictly follow the required JSON format and should not include any additional content.
Table 19: The Relation Extract Prompt
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions and scope of the paper described in the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We examine the limitations of our system in Appendix H
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

We conduct theoretical analysis of our system and provide complete assump- tions and proofs in Section 4 and Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All information required to replicate the main experimental findings provided in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
37

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will confidentially submit all code and data to the reviewers and subse- quently release them under on Github.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We present complete details of our experimental setup Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Given that training has been conducted, our results are close determin- istic as possible under the given dataset and hyperparameters. The only potential source of randomness stems from the internal mechanisms of the large language model's API, since we set the temperature to 0 and seed to 123, as detailed in Appendix D.I
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Appendix D.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We ensure that our work adheres the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please see Appendix
H
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
39

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have properly cited all existing assets used in this work and complied with their respective license terms.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification: All newly introduced assets and their accompanying documentation will anonymously shared with reviewers during the peer-review process and subsequently submitted to GitHub.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
41

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification:
We describe our LLM usage in Section 5.1
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httto:///eerrrpe.cc/////ffeerrre for what should or should not be described.
42


Reviews:
[{"review_id": "G7Y7NT90YG", "reviewer": "Reviewer_ntvy", "summary": "The paper introduces ReMindRAG, a novel LLM-guided knowledge graph traversal approach aimed at enhancing the efficiency and accuracy of RAG systems. By using techniques such as node exploration, node exploitation, and memory replay, ReMindRAG improves both the effectiveness of the system and its cost-efficiency. The system constructs a knowledge graph from unstructured text, guiding the traversal process with an LLM to progressively explore and exploit nodes for precise answer retrieval. Memory replay is employed to store and recall traversal experiences, reducing reliance on repeated LLM calls and thus cutting down on the cost. The paper demonstrates that ReMindRAG outperforms existing methods, achieving notable improvements in accuracy while reducing the token consumption by about 50%.", "questions": "1. Could the authors explore the scalability of ReMindRAG in environments where knowledge graphs are constantly evolving or highly dynamic? How does the system handle real-time updates to the graph?\n\n2. Could the author compare the method's time cost with other RAG methods, which will be beneficial to explain the efficiency of the proposed method.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The use of memory replay for efficient graph traversal is a novel and highly effective approach. It offers a significant reduction in LLM costs while maintaining high retrieval accuracy.\n\n2. The memory replay mechanism significantly reduces token consumption, especially for repeated queries, demonstrating strong cost-efficiency without sacrificing performance.\n\n3. The paper presents a comprehensive experimental setup, including multiple benchmark datasets and LLM backbones, which solidly demonstrates the effectiveness of ReMindRAG over various baselines.\n\n4. The explanation of the LLM-guided traversal, along with the theoretical and practical aspects of memory replay, is well-articulated and detailed, aiding in understanding the approach.\n\n**Weaknesses:**\n\n1. While the method reduces token consumption in certain scenarios, further evaluation is needed to assess how well the system scales with very large or noisy datasets and in real-time applications.\n\n2. The overall system, while efficient, involves several intricate mechanisms (e.g., memory replay, node exploration/exploitation), which may introduce complexity in real-world applications or during deployment.\n\n3. My main concern of the usefulness of this method is the reliance on high-quality KGs, which limits the value of the method in real-world scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ntvy,\n\nThank you for your insightful comments and the valuable perspectives you’ve shared. Regarding the weaknesses in our paper that you have pointed out and your questions, we hereby provide a detailed response to each point, hoping to clarify our work further and address your concerns adequately.\n\n### **Weaknesses**  \n\n1. **how well the system scales with very large or noisy datasets**\n\n   In fact, the LooGLE Dataset utilized for our evaluation is already of considerable size. However, addressing noisy datasets and KGs, though a valuable direction, lies beyond the current research scope of our paper and the design of our baselines. While we fully respect your concern, we believe that existing KG-RAG methods are broadly susceptible to noise unless specifically engineered for robustness against it, a focus not within our current work. Additionally, our KG construction method follows established practices (Line 92-102 and Appendix A) and does not introduce any unique steps that would make it more susceptible to noise.\n\n2. **Complexity in deployment.**\n\n   Our open-source code repository has well-encapsulated our system, allowing you to build a ReMindRAG system with just a few lines of code. Additionally, we support high customizability: you can use your own components such as LLM model, Embedding model, and Chunk model by simply inheriting from the abstract classes in our library. For more details, please refer to the README.md of our open-source repository.  \n\n3. **reliance on high-quality KGs**\n\n   Our Knowledge Graph (KG) is constructed automatically from unstructured continuous text, with the methodology further elaborated in Appendix A. For this purpose, we leverage the Large Language Model. This approach facilitates a convenient construction process that guarantees a high standard of quality without requiring manual oversight or optimization. We concur with your concern that models reliant on specific, high-quality knowledge graphs may lack generalizability. The comparative PoG method we reference is a case in point, as it is restricted to a certain knowledge graph (Freebase). In contrast, our proposed model is designed to overcome this very drawback.\n\n   Many existing methods necessitate high-quality source texts or high-performance LLMs to construct high-quality KGs; however, investigating the construction of high-quality KGs falls outside the scope of our current work.\n\n### **Questions**  \n\n1. **Evaluation on evolving or highly dynamic KG**\n\n   We would like to highlight that we and our baselines are not designed for noisy KGs or evolving KGs, which are not our research task and scope. However, to address your concern, it's conceptually possible to add new content to the KG at any time without affecting existing data. Such newly added content could undergo automated operations, like integration with synonyms, to be properly incorporated. Crucially, during LLM inference, we ensure the KG remains static (i.e., it is treated as a non-evolving KG). In such scenarios, when newly added nodes or edges are not equipped with memory/weights, the LLM's inference for those specific elements would then depend on its own capabilities. \n\n2. **Could the author compare the method's time cost with other RAG methods, which will be beneficial to explain the efficiency of the proposed method.**\n\n   Both the KG construction process and the subsequent LLM-Guided Traversal need to be completed using LLM, which involves time cost. However, since our KG construction method aligns with that of the baselines, the time cost associated with this phase is consistent across all evaluated methods. Therefore, the critical time cost for comparison lies in the LLM-Guided Traversal, which is quantified in our paper through token consumption (detailed in Table 2 and Table 3). Our decision not to use precise wall-clock time as a direct metric stems from two key reasons: (1) the strong correlation between LLM inference time and the number of output tokens, and (2) the inherent uncertainties and fluctuations caused by network latency during API calls to LLMs, which would introduce inaccuracies into direct time measurements. Consequently, we kindly refer you to our reported token consumption as the robust and reliable indicator of time cost. \n\n\n\nWe hope our responses have effectively addressed your concerns. Going forward, we will further refine our paper in light of your comments."}, {"review_id": "qBHxlBZevu", "reviewer": "Reviewer_fchT", "summary": "This paper proposes ReMindRAG, a Retrieval-Augmented Generation (RAG) framework. ReMindRAG employs LLM-guided traversal of document-level knowledge graphs, then stores successful and failed traversal paths within edge embeddings. These embeddings are updated using closed-form rules (\"Fast Wakeup & Damped Update\") to enable future similar queries to be answered with fewer LLM calls. Experiments across three QA settings (long-dependency, multi-hop, simple) demonstrate that ReMindRAG achieves higher accuracy compared to a set of strong baselines while reducing token costs by approximately 50%. By storing traversal experiences in edge embeddings mimicking LLM parametric memory, it reduces LLM overhead by 50% for recurring queries while improving accuracy by 5–12%.", "questions": "- ReMindRAG reduces token usage by about 50%, but is compared to PoG without memory replay (Table 2). Can you provide more direct comparisons with the original PoG configuration?", "limitations": "Please refer to Strengths And Weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- ReMindRAG introduces an innovative combination of LLM-guided graph traversal with node exploration, node exploitation, and memory replay. This approach aims to improve both effectiveness and cost efficiency in Knowledge Graph Retrieval-Augmented Generation (KG-RAG) systems.\n\n- By targeting reduced LLM invocation costs and inference time, ReMindRAG addresses a practical concern for deploying KG-RAG systems at scale, making it relevant for real-world applications.\n\n- The authors demonstrated the effectiveness of ReMindRAG through experiments and theoretical analysis.\n\nWeaknesses:\n- Section 4 refers to “Equation (4)” as the storage condition, but the last numbered formula in the section is (3); there is no (4)?\n\n- There are still a lot of errors in the paper, which makes it difficult to read (there are quite a few). For example, in the appendix there is: \"illustrated in Figure ??\".\n\n- Graph construction still calls LLM for NER and relation extraction; Table 5 shows token counts but not latency. A better comparison on speed can be done with other methods.\n\n- The paper alternates between \"ReMindRAG\" and \"REMINDRAG,\" suggesting a lack of consistency in naming the proposed method.\n\n- Terms like \"memory replay\" and \"node exploitation\" are introduced without clear definitions in the provided text, causing confusion.\n\n- Omits comparison with parametric memory-augmented RAG (e.g., MemoRAG, HippoRAG).\n\n- Table 1 reports the accuracy of Plan-on-Graph (PoG), but does not explain how PoG is adapted to the KG structure of ReMindRAG (Appendix E.2.1). If PoG's original optimization for Freebase is lost, it may lead to an unfair comparison.", "was_revised": true, "final_justification": "The author made changes to the questions I raised, and I increased my rating.", "rebuttal": "Dear Reviewer fchT,\n\nThank you for your feedback. **We will proofread the paper to improve our writing in the revision. Beyond the writing aspects, we address your remaining concerns in the following**. Some concerns are closely related, we will response to them together.\n\n### Weaknesses   \n\n**3. Table 5 shows token counts but not latency. A better comparison on speed can be done with other methods.**\n\nBoth the KG construction process and the subsequent LLM-Guided Traversal need to be completed using LLM, which involves time cost. However, since our KG construction method aligns with that of the baselines, the time cost associated with this phase is consistent across all evaluated methods. Therefore, the critical time cost for comparison lies in the LLM-Guided Traversal, which is quantified in our paper through token consumption (detailed in Table 2 and Table 3). Our decision not to use precise wall-clock time as a direct metric stems from two key reasons: (1) the strong correlation between LLM inference time and the number of output tokens, and (2) the inherent uncertainties and fluctuations caused by network latency during API calls to LLMs, which would introduce inaccuracies into direct time measurements. Consequently, we kindly refer you to our reported token consumption as the robust and reliable indicator of time cost. \n\n**5.Definitions of \"memory replay\" and \"node exploitation\"** \n\nOur definition of 'memory replay' aligns with its standard usage in the AI field [1-2]. It refers to the recall of valuable past memories to facilitate current tasks. However, our approach diverges from prior work that typically involves recalling explicit samples. Instead, our 'memory' is embedded as weights within the KG, and it is these weights that are exclusively utilized to guide LLM inference and graph traversal. Additionally,  we have provided detailed explanations of node exploitation in Section 3.1 (Line 122-127), and we will further clarify them in the revision.\n\n**6.Comparison with parametric memory-augmented RAG (e.g., MemoRAG, HippoRAG)**\n\nOur baselines are selected to represent a diverse set of KG-RAG methods, including the reviewer-suggested ones, though it's impractical to evaluate every single approach. For example, our experiments already incorporate Hippo2, the upgraded version of Hippo. Note that Memo, which is not a KG-RAG method, was initially excluded. However, at your suggestion, we still performed additional experiments including 'MemoRAG'\n\n- **Setup**. Due to MemoRAG's characteristic of handling memory for ultra-long texts and time constraints, we focused on evaluating LongDependencyQA of the LooGLE dataset here. The baseline model uses gpt-4o-mini, the embedding_model is uniformly adopted as nomic-ai/nomic-embed-text-v2-moe with ours, and other parameters are all MemoRAG's default parameters, including mem_mode using its default memorag-mistral-7b-inst. We downloaded its pre-trained weight files from Hugging Face. \n- **Results**. The results in the following table still show our superiority\n\n| Model           | Baseline Model | Evaluation Task      | Result |\n| --------------- | -------------- | -------------------- | ------ |\n| MemoRAG         | gpt-4o-mini    | Long-Dependency-Task | 46.97% |\n| HippoRAG2       | gpt-4o-mini    | Long-Dependency-Task | 39.60% |\n| REMINDRAG(Ours) | gpt-4o-mini    | Long-Dependency-Task | 57.04% |\n\n**7. Implementation details of PoG**\n\nIn Appendix D.4 (Lines 673-682), we detail our use of PoG and have attached the corresponding code. While a complete re-description of PoG's intricate implementation details is omitted from the Appendix, our provided code clearly demonstrates that we have fully retained all core methodologies of PoG, including its two-stage LLM-based relation pruning, LLM-based entity pruning, iterative graph traversal and reasoning, and memory updates during reasoning. Only the processing part for the specific format and rules of the Freebase dataset was removed because it is incompatible with our dataset format. Additionally, the interaction method with the knowledge graph was modified: SPARQL was replaced by an in-memory index. Our knowledge graph is much smaller than the ultra-large Freebase dataset, so in-memory lookup optimization can instead improve PoG's performance. Therefore, we have retained all of PoG's optimization schemes in terms of both accuracy and token consumption.    \n\n### Question   \n\n**Q1. Comparisons with the original PoG configuration**\n\nAs mentioned earlier, our modified PoG method has been fully open-sourced (available at the link in Section E.2.1 of the paper). It can be seen from the code that we have not modified any of PoG's methods; the changes we made are as explained in point 7 above. PoG itself does not have our memory replay function, which is one of our innovations. You may have confused it with PoG's proposed \"Memory Updating\": *The information stored in memory provides historical retrieval and reasoning information for reflection. After a two-step exploration, we dynamically update the searched subgraph GSub, reasoning paths P, and sub-objective status S in memory based on the ongoing reasoning process* (Quoted from the original PoG paper) . Its memory mechanism is only for a single retrieval. The original PoG configuration relies on knowledge graphs composed solely of nodes (e.g., Freebase). In terms of heterogeneous graphs, it lacks chunk processing capability, making it more suitable for simple question-answering tasks but less effective in scenarios relying on contextual text processing (in practice, it is difficult to fully represent a piece of text in the form of a node graph, which severely damages the intrinsic semantic information).\n\n\n\nWe hope our responses have effectively addressed your concerns. Going forward, we will release the supplementary code for the experiments conducted in support of this rebuttal as open-source, and further refine our paper in light of your comments.\n\n**Reference**\n\n1. The Effects of Memory Replay in Reinforcement Learning\n2. MEMORY REPLAY WITH DATA COMPRESSION FOR CONTINUAL LEARNING"}, {"review_id": "10Lw6dMtZr", "reviewer": "Reviewer_mgBN", "summary": "This paper introduces ReMindRAG, a KG-RAG system designed to improve both performance and cost-efficiency. It employs an LLM-guided traversal strategy for complex information retrieval and introduces a “memory replay” mechanism to reduce costs for subsequent, similar queries. The authors provide a theoretical analysis of the memory's capacity and demonstrate the system's effectiveness and cost savings across three QA tasks against several baselines.", "questions": "1) Given the high initial traversal cost, what is the typical \"break-even\" point for ReMindRAG? How many similar queries are required on average to offset the high initial cost of graph traversal compared to simpler RAG methods or dense retriever? How does this affect its viability in domains with diverse query patterns?\n2) The “Damped Update” is designed for stability by making it harder to alter “memories” that have been reinforced. If the initial queries lead to flawed LLM judgements, could this mechanism become prematurely locked in “toxic” memories (incorrect traversal paths), making it difficult for subsequent, correct updates to overcome the initial bias?\n3) Could the authors elaborate on how the memory capacity would be impacted by a significantly lower embedding dimension $d$, for example, in a resource-constrained setting?", "limitations": "Yes, the authors acknowledge the primary limitations in Appendix H. The discussion would be strengthened by a quantitative exploration of the cost-benefit trade-off (per the question above) and a deeper analysis of the system's resilience to its backbone LLM's inherent fallibility.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength\n- The core idea of creating a persistent, training-free “memory” within the KG’s edge embeddings to improve efficiency is interesting. It tackles a practical challenge in mitigating the high cost of LLM API calls in existing KG-RAG systems.\n-  The paper is technically sound and well written. The memory replay part is well motivated and reasoned with theoretical analysis.\n- The experimental setup is comprehensive that considering three types of QA tasks with various query scenarios.\n\nWeakness\n- The system's primary benefit is for subsequent queries, leaving the high \"cold start\" cost of the initial traversal as a significant practical barrier, especially in domains with non-repetitive queries.\n- The memory update loop relies entirely on the LLM’s own fallible judgment, creating a risk that flawed reasoning or hallucinations could be reinforced over time.\n- The claim on “self-correction” capability should be more accurately described as learning between queries rather than correcting an error within a single query’s execution.\n- The theoretical analysis for memory capacity relies on an approximation of the embedding dimension $d$ approaching infinity. This simplification obscures the fundamental dependency on dimensionality, which could limit the method's applicability in resource-constrained settings.", "was_revised": true, "final_justification": "The author provided a detailed rebuttal and new results. The updated results of the dimensionality test the system's performance in the resource-constrained setting. However, I find that some critical issues regarding the system's practical viability remain unresolved, especially new concerns on complexity surfaced during rebuttal (token / API call cost).", "rebuttal": "Dear Reviewer mgBN,\n\nThank you for your feedback. We address your concern in order as follows. Some concerns are closely related, we will response to them together.\n\n\n\n### Weaknesses  \n\n1. **Cold start for non-repetitive queries.**\n\n   As discussed in our Conclusion section, this challenge can be effectively mitigated by initializing our model with pre-existing, well-curated FAQs relevant to the deployment domain. This approach provides a robust baseline memory, enabling efficient handling of common scenarios and accelerating the graph traversal process.\n\n2. **Memory update loop relies entirely on the LLM’s own fallible judgment, creating a risk that flawed reasoning or hallucinations may occur**\n\n   Thank you for your feedback. However, we are quite confused about the precise nature of your concern. We interpret your comment in one possible way and address them below. Please do not hesitate to correct us if our interpretation is inaccurate.\n\n   - **Regarding Memory Updates:** If your concern is that our memory updates might suffer from \"flawed reasoning or hallucinations\" due to LLM judgment, we wish to clarify that this is not the case. Our memory, stored as weights on the Knowledge Graph's edges, is updated using **LLM embeddings**, not LLM-prompted judgments or generated text. This distinction is crucial, as updates based on numerical embeddings inherently do not introduce the type of flawed reasoning or hallucinations associated with direct LLM text generation.\n   - **Regarding LLM-Guided Traversal and Inference:** If your concern pertains to the potential for inaccurate LLM performance during the graph traversal and subsequent inference, you are correct that this is a possibility. When LLMs are used for navigation and reasoning on the graph, their inherent inaccuracies can indeed impact the overall inference quality. However, it is important to note that this is a **common challenge across all LLM-based KG-RAG methods** and represents an inherent characteristic of current LLM capabilities. Addressing this fundamental limitation of LLMs is beyond the scope of our current research, as our work focuses on the architecture and benefits of the ReMindRAG system itself.\n\n3. **self-correction capability should be more accurately described as learning between queries rather than correcting an error within a single query’s execution**\n\n   Thank you for your suggestion. We will clarify this in the revision \n\n4. **Dependency on dimensionality, which could limit the method's applicability in resource-constrained settings**\n\n   Our assumption that the embedding dimension is infinitely large is based on the fact that linear embedding models have very high dimensions. For the function $\\sqrt{\\frac{d + 1}{2d}}$, when d is greater than around 100 (currently, the embeddings of an LLM often exceed 100 dimensions), it can actually be approximated to $\\frac{1}{2}$. This approximation thus holds significant practical utility. \n\n### Questions  \n\n1. **\"break-even\" point. How many similar queries are required on average to offset the high initial cost of graph traversal compared to simpler RAG methods or dense retriever? How does this affect its viability in domains with diverse query patterns?**  **\n\n   Our total cost consists of two aspects: KG construction and LLM-guided traversal. As our KG construction method aligns with that of the baselines, the time cost for this phase is consistent across all evaluated methods. Consequently, the critical cost for comparison lies in the LLM-guided traversal. In this regard, our token consumption analysis (detailed in Table 2 and Table 3) provides insights into the 'break-even' point of query costs. Specifically, this break-even point is generally achieved after approximately two queries.\n\n2. **If the initial queries lead to flawed LLM judgements, could this mechanism become prematurely locked in “toxic” memories**\n\n   No, \"Damped Update\" is designed to prevent changes in memory content caused by random errors of large models or uncommon queries. Such toxic memories can be solved by our memory Self-Correction process. Specifically, for memory correction, it usually involves several consecutive damped updates. As shown in Figure 4, consecutive corrections typically require at most 2 iterations to correct the memory. We will incorporate this into the revision.  \n\n3. **How the memory capacity would be impacted by a significantly lower embedding dimension**\n\n|      | 1/1    | 1/2    | 1/4    | 1/8    |\n| ---- | ------ | ------ | ------ | ------ |\n| 2    | 58.01% | 57.71% | 55.03% | 53.35% |\n| 1    | 56.48% | 52.34% | 54.02% | 53.02% |\n| 0    | 57.04% | 56.37% | 55.36% | 54.69% |\n\nWe performed dimensionality reduction on the embedding model, with specific data as above (The X-axis represents the code truncation ratio; 1/8 means selecting the first eighth of the dimensions, 1/4 means selecting the first quarter, 1/2 means selecting the first half, and the Y-axis represents the number of updates. The data in the table represent the answer accuracy rate.) It can be seen that the impact on the entire system is negligible. We speculate that this may be due to the Matryoshka Representation Learning technology it applies, which enables effective dimension truncation [1].\n\nWe hope our responses have effectively addressed your concerns. Going forward, we will release the supplementary code for the experiments conducted in support of this rebuttal as open-source, and further refine our paper in light of your comments.\n\n\n\n**Reference**\n\n[1] Kusupati, Aditya, et al. \"Matryoshka representation learning.\" *Advances in Neural Information Processing Systems* 35 (2022): 30233-30249."}, {"review_id": "qJozCnQKVU", "reviewer": "Reviewer_mkn9", "summary": "This paper proposes ReMindRAG, a method that simultaneously improves both effectiveness and cost efficiency of KG-RAG systems by adding memory replay functionality. The system employs systematic LLM-guided graph traversal through node exploration and exploitation, along with train-free updates that store LLM-guided traversal experiences in edge embeddings, enabling fast retrieval by loading stored subgraphs through memory replay when similar queries arise. It demonstrated an average of 50% reduction in token consumption and 5-10% performance improvement. Through extensive experiments and detailed experimental procedures, the paper validates the effectiveness and reproducibility of the method.", "questions": "1. While the paper presents efficiency analysis primarily in terms of token consumption, it would also be helpful to understand how the proposed method compares to other baselines in terms of latency. Could you provide a comparison of inference latency across different memorization steps or against other methods?\n2. Could you provide memory hit rates (percentage of edges retrieved from memorized vs. newly traversed) for each query type?\n3. The paper emphasizes the self-correction mechanism, and performance improves as the number of memorization steps increases. What is the proportion of cases where previously incorrect answers are corrected, and cases where previously correct answers become incorrect as memorization steps increase?\n4. A missing figure exists. In line 486. Appendix A.2: There is no Figure explaining automated knowledge graph building.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths \n1. Cost-Effectiveness Optimization: Across diverse benchmarks the method improves accuracy by 5–10 percentage points while reducing LLM token cost by roughly 50 %, proving superior cost-effectiveness.\n2. Training-Free Memory Storage via Memory Replay: Traversal paths are instantly written into edge embeddings, enabling broad reconstruction of the initial sub-graph for later similar or identical queries without invoking the LLM\n3. Self-correction capability: Even when an incorrect path is taken, memory re-weighting and penalties correct the mistake, allowing the system to rapidly return to the proper path on subsequent queries.\n\n### Weaknesses\n1. The experimental results suggest that this method is both effective and efficient compared to other approaches, and the efficiency aspect is well supported. However, it is not clearly shown whether the method is also more effective than existing LLM-guided knowledge graph traversal approaches in particular, or how it achieves such effectiveness.\n2. The experimental evaluation shows promising memory efficiency gains in controlled settings where identical queries are repeated, achieving approximately 50% token savings. However, real-world scenarios typically involve diverse, non-repetitive query patterns. Therefore, it remains questionable whether memory replay would occur sufficiently in practice to provide substantial token savings.", "was_revised": true, "final_justification": "The paper makes a solid technical contribution through its novel memory replay mechanism for KG-RAG systems. The authors have been highly responsive to the reviewers' feedback, providing substantial additional experiments. Therefore, I decided to maintain my current score.", "rebuttal": "Dear Reviewer mkn9,\n\nThank you for recognizing our work—we truly appreciate it. We also value the time and effort you’ve dedicated to reviewing our paper; your feedback both validates our work and highlights areas needing clarification. Regarding the weaknesses in our paper that you have pointed out and your questions, we hereby provide a detailed response to each point, hoping to clarify our work further and address your concerns adequately.\n\n### Weaknesses  \n\n1. **Why more effective than baselines**\n\n   Thank you for your feedback. We contribute our effectiveness to the use of KG for LLM inference.\n\n   Unlike methods like PoG and ToG, which introduce LLM traversal for the Freebase database (Freebase itself is a massive knowledge base consisting of entities (nodes) and clearly defined relationships (edges) with a relatively fixed structure), we have not yet found relevant articles similar to ours that introduce LLM traversal for RAG processing of complex texts. We believe their methods have very limited applications because they cannot be separated from the Freebase database, and this approach of fully relying on graphs largely damages the intrinsic semantic information of texts. The heterogeneous knowledge graph we constructed is not an independent database separated from texts, but a dynamic representation tightly coupled with the original texts. Therefore, in our comparisons, we adapted the PoG code to our own text-constructed knowledge graph while fully retaining its original methods, and included it as a comparative model in the paper. This is a compromise made because we did not find methods similar to ours that combine LLM traversal with heterogeneous knowledge graphs formed by text processing.  \n\n2. **How to deal with non-repetitive query.**\n\n   As discussed in our Conclusion section, this challenge can be effectively mitigated by initializing our model with pre-existing, well-curated FAQs relevant to the deployment domain. This approach provides a robust baseline memory, enabling efficient handling of common scenarios and accelerating the graph traversal process.\n\n### Questions  \n\n1. **Inference latency across different memorization steps**\n\n   Our efficiency is quantified in our paper through token consumption (detailed in Table 2 and Table 3). Our decision not to use and can not use precise wall-clock time latency as a direct metric stems from two key reasons: (1) the strong correlation between LLM inference time and the number of output tokens, and (2) the inherent uncertainties and fluctuations caused by network latency during API calls to LLMs, which would introduce inaccuracies into direct time measurements. Consequently, we kindly refer you to our reported token consumption as the robust and reliable indicator of time cost. \n\n2. **More analysis on memory hit rate**\n\n   We sincerely apologize that we are unable to complete this additional experiments within the limited timeframe of this rebuttal period. However, we attach great importance to your valuable suggestions and are fully committed to conducting these experiments and incorporating them into revisions\n\n3. **success rate of self-correction**\n\n   We recorded the questions answered correctly and those answered incorrectly in each experiment. We conducted three experiments on  the LongDenpendencyQA datasets. (i.e., we updated it twice based on the first experiment), and the resulting data are as follows:\n\n   To rigorously evaluate the model's performance changes, we define the following notations: Let the complete set of test cases be $S = \\{q_1, q_2, \\dots, q_N\\}$, where $N = |S|$ is the total number of cases. For the $i$-th experiment ($i \\in \\{1, 2, 3\\}$), the result of each case $q_k$ is denoted by $R_i(q_k)$, where $R_i(q_k) = 1$ for a correct answer and $R_i(q_k) = 0$ for an incorrect answer.\n\n   Based on this, we define the metrics for evaluating changes in consecutive experiments ($i$ vs. $i-1$) as well as the overall change between the third and first experiments ($3$ vs. $1$).\n\n   Proportion of Corrected Cases in Consecutive Experiments:  $$    P_{\\text{fix}, i} = \\frac{|\\{q_k \\in S \\mid R_{i-1}(q_k) = 0 \\land R_i(q_k) = 1\\}|}{N}    $$\n\n   Proportion of Regressed Cases in Consecutive Experiments:$$    P_{\\text{regress}, i} = \\frac{|\\{q_k \\in S \\mid R_{i-1}(q_k) = 1 \\land R_i(q_k) = 0\\}|}{N}    $$\n\n   Proportion of Corrected Cases (3rd vs. 1st Experiment):$$    P_{\\text{fix}, 3 \\text{ vs } 1} = \\frac{|\\{q_k \\in S \\mid R_1(q_k) = 0 \\land R_3(q_k) = 1\\}|}{N}    $$\n\n   Proportion of Regressed Cases (3rd vs. 1st Experiment):$$    P_{\\text{regress}, 3 \\text{ vs } 1} = \\frac{|\\{q_k \\in S \\mid R_1(q_k) = 1 \\land R_3(q_k) = 0\\}|}{N}    $$\n\n   The Net Improvement Rate (P_net) is defined as the \"Proportion of Corrected Cases\" minus the \"Proportion of Regressed Cases\", i.e., $P_{net} = P_{fix} - P_{regress}$\n\n   |                        | Fix                                         | Regress                                          | $$P_{net}$$ |\n   | ---------------------- | ------------------------------------------- | ------------------------------------------------ | ----------- |\n   | 1-turn Memorization    | $$P_{\\text{fix}, 2}$$ = 3.36%               | $$P_{\\text{regress}, 2}$$ = 4.69%                | -1.34%      |\n   | 2-turn Memorization    | $$P_{\\text{fix}, 3}$$ = 10.74%              | $$P_{\\text{regress}, 3}$$ = 5.37%                | +5.37%      |\n   | 3rd vs. 1st Experiment | $$P_{\\text{fix}, 3 \\text{ vs } 1}$$ = 8.72% | $$ P_{\\text{regress}, 3 \\text{ vs } 1}$$ = 5.37% | +4.03%      |\n\n   Due to time constraints, we only conducted experiments on a subset of the LongDenpendencyQA datasets.\n\n\n\nWe hope our responses have effectively addressed your concerns. Going forward, we will release the supplementary code for the experiments conducted in support of this rebuttal as open-source, and further refine our paper in light of your comments."}, {"review_id": "N1gvXNHpcO", "reviewer": "Reviewer_7sXk", "summary": "The paper introduces KG-RAG, a retrieval-augmented generation system that (i) builds a heterogeneous knowledge graph from documents, (ii) lets an LLM decide which node to expand while answering a query, and (iii) stores the successful traversal as an edge-level memory so that similar future queries can be served with fewer LLM calls. Experiments on three QA benchmarks show higher answer accuracy and lower token consumption than several graph-based RAG baselines.", "questions": "### Questions\n\n1.1 Why doesn’t the paper follow the evaluation protocol used in HippoRAG and HippoRAG2, such as reporting Recall@5 and Exact Match? Given that HippoRAG2 is the main competitor, this seems like a natural baseline.\n1.2 If the QA datasets have already been transformed into multiple-choice format, why rely on GPT-4o as a judge for evaluation? Why not directly compare the selected answer with the ground truth?\n2.Please include an experiment to test how different permutations of question order affect overall performance.\n3. please run an experiment to verify whether semantically similar queries in your dataset actually lead to similar graph paths.\n\n### Format issues\n- line 486: Figure ?? \n- figure 11, 12: ORINGIN\n- Table 2: Long Denpendency\n- Line 47: It efficiently store and recall experience\n- “LLM-as-judgment” & “LLM-as-a-judge” used interchangeably, pick one only", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strength \n1. The paper is generally well written and has clear motivation. The paper explains the cost–coverage trade-off in graph-based RAG and positions its contribution well.\n2. Memory replay is efficient as shown in their experimental section.\n\n### Weakness\n\n1. The only evaluation of effectiveness relies on LLM-as-a-judge, using GPT-4o as the backbone. This is quite problematic, as the evaluation model may share biases with the smaller generation model (GPT-4o mini). Moreover, there are alternative ways to evaluate against ground truth (see Question 1), which the paper does not explore.\n\n2. The paper claims that the results are nearly deterministic, with the only source of randomness being the LLM’s API. However, it overlooks the randomness introduced by the order in which queries enter the system. Since the method depends on remembering the path of previously answered queries, this order can significantly impact outcomes (see Question 2).\n\n3. The memory replay mechanism could become extremely ineffective when semantically similar queries follow entirely different graph paths.", "was_revised": true, "final_justification": "In the rebuttal phase, the authors provide clarification and additional experiments that mostly address my concerns. Reflecting these changes, I raised the score from 3 to 4.", "rebuttal": "Dear Reviewer 7sXk,\n\nThank you for your detailed feedback and the effort you’ve put into refining your comments on our paper. Regarding the weaknesses in our paper that you have pointed out and your questions, we hereby provide a detailed response to each point, hoping to clarify our work further and address your concerns adequately.\n\n### Weaknesses\n\n1. Please refer to Answer 1.2.  \n2. Your point is well-founded, and we have overlooked this issue. However, in actual query processes, the probability that two different questions from our dataset follow the same path is extremely low, so the impact of their order is not significant for our system.  \n3. Please refer to Answer 3.  \n\n### Questions\n\n1.1 **Why doesn’t the paper follow the evaluation protocol used in HippoRAG and HippoRAG2, such as reporting Recall@5 and Exact Match? Given that HippoRAG2 is the main competitor, this seems like a natural baseline.**\nDue to time constraints, we applied the LooGLE dataset to both REMINDRAG and HippoRAG 2, and the following are the recall results we obtained. (Base model: gpt-4o-mini)  \n\nOur recall rate calculation is entirely based on whether the evidence sentences provided by the test dataset are present in the traversed chunks. If all evidence sentences are hit, the recall rate for this sample is 100%.\n\n|                  | HippoRAG2 | REMINDRAG |\n| ---------------- | --------- | --------- |\n| LongDependencyQA | 36.58%    | 60.44%    |\n\n\nWe believe that recall rate does not fully reflect the success of a system. In essence, during the LLM-guided traversal and search process, the correct answer can often be inferred without all the evidence. Therefore, we consider accuracy to be a more scientific metric than recall rate for evaluating the effectiveness of a model system.  \n\n1.2  **If the QA datasets have already been transformed into multiple-choice format, why rely on GPT-4o as a judge for evaluation? Why not directly compare the selected answer with the ground truth**\nThis is because, to compare with other RAG systems, their outputs may include a large amount of additional information besides the options. Having the large model determine whether the correct answer is included is a very simple task for it (for current large models, such a straightforward semantic coverage judgment task is almost error-free). This simplifies the evaluation process while maintaining fairness.  \n\n\n2.   **Please run an experiment to verify whether semantically similar queries in your dataset actually lead to similar graph paths.**\n\n| Update  times | Accuracy |\n| ------------- | -------- |\n| 0             | 56.37%   |\n| 1             | 55.78%   |\n| 2             | 57.71%   |\n\n\nWe greatly appreciate your valuable feedback. We have incorporated the handling of random shuffling of questions in the code and conducted three consecutive experiments, with the results presented in the table above. It can be seen that random shuffling has almost no impact on our system. In this experiment, the questions in each iteration were also randomly shuffled, which indicates that the shuffling of question order likewise has almost no impact on the system's memory capability.\n\n3. **Please run an experiment to verify whether semantically similar queries in your dataset actually lead to similar graph paths.**\n\nWe only use Memory Reply before LLM-Guided Traversal. For similar queries (i.e., those with similar embeddings), they will inevitably point to the same Seed Nodes and, through Memory, obtain the same graph paths. The entire process is derived through purely mathematical methods without involving any LLM. Therefore, in summary, we can theoretically conclude that similar queries point to similar graph paths.\n\nBelow is our experiment to demonstrate this point:\n\nTo calculate the similarity between the search paths of an original problem and a similar problem, we first model their search paths as sets of \"edges\" (here, \"edges\" refer to direct connections between two nodes). Let  $$E_1$$ represent the set of edges in the original problem's search path, and $$E_2$$ represent the set of edges in the similar problem's search path.   \n\nThe similarity $$ S $$ is defined as the ratio of the total number of identical edges in both searches to the total number of unique edges (after deduplication) across both searches. The formula is:   $$S = \\frac{|E_1 \\cap E_2|}{|E_1 \\cup E_2|}$$   \n\nHere,  $$|E_1 \\cap E_2|$$ denotes the size of the intersection of the two edge sets (i.e., the number of edges shared by both search paths), and $$|E_1 \\cup E_2|$$ denotes the size of the union of the two edge sets (i.e., the total number of distinct edges present in either search path).   A value of \\( S \\) closer to 1 indicates a higher overlap between the two search paths, meaning their underlying logic is more similar. Conversely, a value closer to 0 indicates greater divergence between the paths.\n\nThe final result $$S_{\\text{all}}$$ is defined as the average of all similarities, i.e.:\n\n$$S_{\\text{all}} = \\frac{1}{n} \\sum_{i=1}^{n} S_i$$\n\nwhere $$n$$ is the total number of similarities calculated, and $$S_i$$ is the search path similarity obtained from the i-th calculation.\n\nWe first ran the original problems, and on this basis, ran the similar problems; the final results are as follows: (Base model: gpt-4o-mini)  \n\n|                  | Similarity ($$S_{\\text{all}}$$) |\n| ---------------- | ------------------------------- |\n| LongDependencyQA | 53.78%                          |\n\nFrom the experimental results, it can be seen that semantically similar queries indeed lead to similar graph paths.\n\n\n\nWe hope our responses have effectively addressed your concerns. Going forward, we will release the supplementary code for the experiments conducted in support of this rebuttal as open-source, and further refine our paper in light of your comments."}]

Author rebuttal:

Meta-review: This paper proposes ReMindRAG, a knowledge graph–based RAG framework that enhances both accuracy and cost-efficiency through LLM-guided graph traversal and memory replay. It explores and exploits nodes to retrieve precise answers, while storing traversal experiences in edge embeddings to reduce repeated LLM calls. This train-free update mechanism, inspired by parametric memory, enables fast reuse of successful paths for similar queries. Across multiple QA tasks, ReMindRAG achieves 5–12% accuracy gains and reduces token consumption by about 50%, demonstrating consistent improvements over strong baselines.

Strengths:
1. Most reviewers find the integration of LLM-Guided Traversal and a Memory Replay mechanism novel and interesting.
2. This paper has provided theoretical justifications
3. Comprehensive experiments have been provided to demonstrate the effectiveness of the method.

Weakness:
Some questions have been raised regarding the complexity of the proposed method, the faithfulness of the memory update loop and evaluation details.

During the rebuttal, the authors provided:
1. Additional evaluations to demonstrate the method’s effectiveness and robustness, including new baselines, shuffled query experiments, , path similarity analyses for consistency verification, and reliance in memory updates & "toxic memory" risk.
2. Clarification on the evaluation details.

Most reviewers agree that the authors have addressed their concerns and have given the paper positive scores, with only one raising questions about the method’s practical viability. I consider this a minor issue in light of the overall contributions, and therefore recommend acceptance.
Decision: Accept (poster)