acceptodds
Under review as a conference paper at ICLR 2027

SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval

Abstract

Knowledge graphs (KGs) offer a rich representation for relational knowledge, but their irregular structure makes retrieval challenging: ego-graph expansion grows rapidly, and dense embedding methods struggle with multi-hop compositional queries. Several approaches use LLM agents to explore the KG, analyze candidate nodes, and decide where to explore next. While expressive, these approaches can incur substantial computational and memory costs. On the other side, we show theoretically that dense embeddings pre-calculated for nodes in graphs, even with augmented structure and neighborhood-aware features, can require embeddings of dimension of the graph to be able to answer families of knowledge graph queries. This limitation can be solved with query-adaptive embeddings under certain conditions, and there are graph neural network (GNN) variants that can do that. However, processing the whole graph with a GNN can also incur large amount of memory/computation, and besides that it requires dense ground truth answers, knowing for each node if they are an answer to query or not. Straightforward k-hop selection around some anchor nodes can also be problematic since small k would limit the number of nodes we are seeing and even with small k values such as three and four the k-hop subgraph can grow substantially. In this work, we devise a new approach using Graph Transformers and Reinforcement Learning that is much less memory and computation demanding, at inference time can be even ran on a CPU as a first stage retrieval, and in training requires feedback on only small number of nodes at a time. We show that this method is competetive with methods that finetune LLMs to retrieve information from KGs. We call our method (Seed-Expand-Retrieve), and position it primarily as a first stage retrieval that can be ran using small computational resources.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Knowledge Graphs, Retrieval, Graph Transformers, Biomedical Knowledge Graphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_HkDvOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

SEEDER is a first-stage KG retriever. It seeds nodes by entity matching and similarity, expands them into a candidate subgraph of at most 500 nodes, and encodes it with a query-conditioned sparse Graph Transformer; a REINFORCE-trained policy head selects up to 20 answers and a BPR head ranks them. A theory section separates query-independent dense retrieval from query-conditioned message passing. On three STaRK graphs with three encoders, SEEDER beats same-encoder dense and k-hop baselines.

Critical strengths
  1. The seed-expand-select design fits multi-hop KG retrieval.
  2. Gains are consistent across all graphs and encoders, with mean and std over five seeds in Table 1.
Critical weaknesses
  1. The released configs do not match the main table. prime_ada.yaml uses PCA 256, VN only and three hops, and prime_qwen.yaml enables the virtual node the paper turns off.
  2. Sparse feedback is a central motivation, but every experiment trains on the full answer sets losses() in seeder/training.py, and the feedback ratio is never varied.
Questions for authors
  1. Could you release configs for all nine rows? Was the validation split used for both hop-quota search and checkpoint selection?
  2. Could you simulate partial feedback on fixed candidate graphs?
4 comments

Thank you for taking the time to carefully review our work and code. Below, we address each of your points.

W1. The released configs do not match the main table ...

Thank you for catching this mistake in the submitted code. We checked the saved configurations and test results for all five seeds of both STaRK-PRIME runs. Appendix Tables 7 and 8 accurately describe the configurations that produced Table 1; the two YAML files in the supplement contain earlier settings, and were incorrectly labeled as the main-table configurations.

PRIME encoderPCA dimensionVirtual nodeExpander cyclesGated hop embeddingsDropoutTest Recall@20
ada-002512On5On073.5%
Qwen3-4B512Off5On079.4%

The submitted code supports both configurations through the YAML files; we will include the exact configurations used for each Table 1 result in the public release.

W2. Sparse feedback is a central motivation ...

We agree that the recall as used in the submission requires knowing the number of correct answers. We thus conducted experiments that instead use the number of correct answers divided by the total number of returned nodes (20), which is the precision, and does not require this knowledge. The performance is similar; we will report these results in the revised paper.

DatasetTraining rewardHit@1Hit@5MRRRecall@20
PRIMERecall46.06 ± 1.3874.34 ± 0.5558.30 ± 0.9779.43 ± 0.27
PRIMEPrecision46.53 ± 2.4573.67 ± 1.1658.55 ± 1.8379.04 ± 0.91
MAGRecall56.29 ± 0.3675.45 ± 0.3764.67 ± 0.2275.13 ± 0.16
MAGPrecision55.75 ± 0.9175.16 ± 0.3164.38 ± 0.5175.19 ± 0.26
AMAZONRecall46.76 ± 0.5171.99 ± 0.2158.07 ± 0.4462.33 ± 0.24
AMAZONPrecision46.33 ± 1.1571.47 ± 1.2957.60 ± 1.0261.75 ± 0.38

Q1. Could you release configs for all nine rows? ...

Yes, we will release them. The ones in the paper are accurate; we will update the code too. And yes, we have used the validation set for this purpose.

Q2. Could you simulate partial feedback on fixed candidate graphs?

Yes, see above.

the feedback ratio is never varied.

We did another study to address the varying feedback ratio part of this comment. For each 20-node proposal during the training process, we randomly get labels for only 2, 5, 10, or 20 nodes. The reward is correct judged nodes / number of judged nodes, so it does not require the full answer count. The auxiliary ranking loss uses only judged nodes.

Feedback per proposalHit@1 (%)Hit@5 (%)MRR@20 (%)Recall@20 (%)
10% (2/20)32.99 ± 1.0562.43 ± 1.5345.80 ± 1.2370.59 ± 1.85
25% (5/20)41.18 ± 1.5469.75 ± 0.7853.73 ± 1.2576.76 ± 0.51
50% (10/20)45.16 ± 0.9073.22 ± 0.8857.45 ± 0.6778.62 ± 0.40
100% (20/20)46.15 ± 0.8073.58 ± 0.8458.10 ± 0.6678.72 ± 0.50

Using feedback on half of each selected set gives almost the same Recall@20 as full feedback (78.62% vs. 78.72%). With feedback on only one-quarter, Recall@20 is still 76.76%. These results show that SeedER can learn well from partial feedback.

Thanks for the follow-up. Checking the saved configs and adding the partial-feedback experiment (with 2, 5, 10, and 20 judged nodes) answers my two main questions.

For the revised version, please include all yaml configs in the code release. Also, please clarify whether those judged nodes are picked fresh for each proposal during training or fixed once per query.

I will keep my positive score.

Thank you for reviewing our work and rebuttal and for your thoughtful feedback. We are glad our results addressed your questions. We will provide clean code and all finalized YAML configs with the revised paper.

Judged nodes are sampled randomly afresh for each proposal on every training visit. Our RL update learns from reward differences across the eight proposals for each query. Over the full 15 epochs (120 proposals per query), the median numbers of unique judged nodes per query were 72, 107, 136, and 163 for the 2/20, 5/20, 10/20, and 20/20 settings, respectively. We will clarify this in the revision.

Reviewer_yL3AOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces SEEDER, a highly efficient three-stage retrieval framework, which is designed to overcome the representational capacity bottlenecks of dense retrievers and the severe computational costs of LLM agents for complex KG queries. It constructs a bounded candidate subgraph using a non-learned, similarity-filtered expansion algorithm K-HOP-WITH-FILTERING via a query-adaptive sparse Graph Transformer. STaRK-Prime, STaRK-MAG, and STaRK-Amazon demonstrate that SEEDER achieves competitive or superior retrieval accuracy compared to other baselines with a fraction of the latency and memory.

Critical strengths
  1. SeedER uses a small model and encodes a bounded subgraph of at most 500 nodes once per query. Under the same encoder, it clearly outperforms dense retrieval and heuristic graph expansion on all three STaRK datasets and with all three embeddings (MiniLM, ada-002, Qwen). It shows that query-conditioned graph encoding over a bounded subgraph is a practical retrieval design that works on top of different text encoders.
  2. The paper decomposes the recall loss into three parts in Proposition D.1. It reveals where the bottleneck lies and which stage future work should improve. Also, it makes the conclusions interpretable and credible.
  3. It reveals clearly about the balance of efficiency and performance. This architectural design solves a major scalability bottleneck in current graph-RAG systems, making advanced multi-hop KG retrieval highly practical for real-world, large-scale, first-stage retrieval pipelines
Critical weaknesses
  1. The paper motivates RL by the settings where feedback is available only for a small set of proposed nodes. Although the authors acknowledge it, it is unclear why not using supervised method or others. The lower bound holds for random permutation graphs with queries of length Θ(log⁡n)\Theta(\log n), while STaRK queries are 1 to 3 hops and depend on text semantics, so I am not sure how it explains why the dense retrieval fails on STaRK.
  2. The framework is fundamentally bottlenecked by its non-learned K-HOP-WITH-FILTERING stage. The primary motivation is to overcome the limitations of dense retrieval, while the crucial expansion step relies on the same dense similarity scores to guide the frontier.
  3. Baseline comparisons seem unfair, SeedER is mostly compared with untrained heuristics. G-Retriever and SubgraphRAG are simplified retrieval-only reimplementations, and SubgraphRAG’s triple scorer is replaced by a hand-weighted similarity, so it is no longer the original method.
Questions for authors
  1. Many typos in the paper need to be improved. For example, reference ? in paper; mix use of Seed-Expand-Retrieve and Seed-and-Expand Retrieval; typo spell like competetive、retreiving.
  2. How does SeedER compare with a supervised selection head trained on the same candidate graphs, for example BCE or a listwise loss over all candidates, or the “direct BPR over all candidates” ablation mentioned in Appendix F.3.
  3. All experiments use full answer sets, and the recall reward needs ∣A(q)∣|A(q)|. The paper motivates RL with less feedback, but no settings to justify this. Can you report an experiment that simulates the sparse-feedback settings.
  4. Can you include strong trained retrievers on STaRK as baselines, such as fine-tuned dense retrievers under the same encoder where possible? Also, can you run original SubgraphRAG with its learned triple scorer?
6 comments

We thank the reviewer for their careful evaluation and constructive feedback. We address their comments point by point below:

W1. The paper motivates RL by the settings where feedback ...

Our motivation for RL beyond STaRK is that feedback may be available only for the set as a whole. There are many settings where we can see whether a downstream model answers a question with a given set of information, but since data points might be redundant (or complementary), it may be difficult to tell without extensively re-calling the model with different subsets which entries were actually useful to the answer quality. These set-level rewards are easily incorporated in an RL pipeline, but difficult to map to supervised learning. Furthermore, SeedER samples without replacement and computes the probability of each ordered draw, allowing a policy gradient to optimize the expected set reward without differentiating through top-20 selection. This lets us inspect how often a node is selected across draws given the learned probabilities, which gives a nice probabilistic character to the approach. While we have not tested downstream-answer rewards due to the added complexity of reliably evaluating these setups, we hope this clarifies what motivates the formulation beyond our empirical results on STaRK.

We agree that supervised training with the same encoder in STaRK’s clean setup is a more direct comparison. We therefore trained two supervised variants on PRIME using the same frozen Qwen embeddings, 500-node candidate pools, and an Exphormer backbone. One receives labels for all candidate nodes; the other receives labels only for its current top 20, selected before seeing the labels. Results support the use of RL for properly estimating these probabilities:

MethodHit@1Hit@5MRR@20Recall@20
Supervised, 500 candidates.3856 ± .0192.6735 ± .0161.5111 ± .0172.7473 ± .0103
Supervised, top 20.4006 ± .0197.6745 ± .0084.5199 ± .0148.7410 ± .0081
SeedER.4606 ± .0138.7434 ± .0055.5830 ± .0097.7943 ± .0027

As to the theory, we agree that the theoretical setup is not exactly applicable to the STaRK benchmarks. The most precise model would require exactly characterizing the STaRK datasets, and apply only to datasets of exactly that form. As always in theoretical results, we simplify the structure of the problem while hopefully retaining the key features that make the problem difficult.

Text semantics do substantially inform the STaRK datasets, but edge types matter too. In our response to reviewer vArq (section W1), we present an experiment showing that edge types do in fact matter to SeedER’s performance: if we shuffle the type of edges while preserving the hop and query embeddings, the Recall@20 drops from 79% to 59%. Textual features also clearly matter significantly on these datasets, and this is not modeled by our relation-tracing graphs – but that component of the problem is totally independent of the graph structure. While even the graph-only components of the STaRK datasets are clearly not exactly relation-tracing graphs, we think the relation-tracing structure is indicative of the types of failures seen in practice with dense retrievers.

The other major point is that the STaRK queries are of bounded length, rather than logarithmic in the size of the graph. Setting aside the technical objection that the size of the graph is also fixed and so we do not know the “true” asymptotic relation, this is true; we also do not know the value of the constant CBC_B from Friedman et al. (1998), and so do not know if Theorem C.5 applies for datasets of this particular size. It is worth noting, however, that Theorem C.2 does not have this restriction. For an LL-hop relation tracing problem with kk edge types, it shows that the required query embedding size is Ω(kLlog⁡(n/k))\Omega(k^L \log(n/k)), while a query-conditioned GNN needs embedding size only O(kL)O(k L). On StaRK-PRIME, L=3L = 3 and k=18k = 18; the difference between 183=5,83218^3 = 5,832 and 18⋅3=5418 \cdot 3 = 54 is already fairly large. We will clarify this in Section 4.

In all, we would like to emphasize that we do not claim that our theorems prove meaningful lower bounds for the particular STaRK datasets. Instead, they illustrate how dense retrievers must fail at certain reasonable KG retrieval tasks, while query-conditional graph retrievers such as the one used in SeedER can easily solve these same tasks. We think the structure of the argument is indicative of behavior on real datasets, and helps explain why we see such better performance from SeedER than real dense retrievers, even if the theorems do not literally prove that the dense retrievers must fail on these particular datasets.

W2. The framework is fundamentally bottlenecked ...

We agree that the filtering stage – which is not explicitly learned, although it does use learned representations – gives a bottleneck on the performance of the full system. We can, however, easily check how bad that bottleneck is on real experiments; we did so in Figure 5(a). For one representative example, on STaRK-PRIME with Qwen, the 500 nodes obtained from the filtered expansion step have 88.4% recall, i.e. this stage achieved 88.4% Recall@500. The final SeedER output had 79.4% test Recall@20.

Avoiding the filtering stage would not necessarily yield a better model. We experimented with an alternative model using BPR ranking loss on all candidate nodes, which for STaRK-PRIME is the whole graph. This requires substantially more memory at both training and inference time; training took around 2.5 hours per epoch. After 10 epochs, this model reached 73.11% Recall@20. For the same number of training epochs (taking much less time and memory), SeedER achieved most of its final performance with 77.54% Recall@20.

While the filtering stage does use dense similarity scores, it does so differently from a dense retriever. At each hop, it considers neighbors of the current frontier and scores them using the query’s similarity to the source node, the connecting relation, and the neighbor. A node with low global similarity can still enter the frontier if its edge is relevant. Combined with the use of the graph structure, the filtering stage chooses a substantially different candidate subgraph than just choosing the top BB nodes by cosine similarity.

The retrieval budget also matters here. For a dense retriever that scores each node independently, our lower bound on the bits required per node weakens as the number of returned nodes BB increases. Even a dense retriever can therefore be useful as a candidate generator: an answer ranked 200th counts toward Recall@500, though not toward Recall@20. Our goal is to close that gap by using the graph to select 20 answers from a high-recall candidate set.

W3. Baseline comparisons

With respect to the retrieval-only form of G-Retriever and SubgraphRAG, we followed the convention used in the GraphFlow paper. As you pointed out, however, this could be misleading relative to the original models. In the revised manuscript, we renamed the two rows to PCST subgraph and triple retrieval. The first uses G-Retriever’s prize-collecting Steiner tree formulation, omitting its trained GNN–LLM. The second follows SubgraphRAG’s idea of scoring triples, but replaces its learned scorer with a hand-weighted similarity function. We credit both papers and clarify the differences. We compare further here with the original methods.

For a SubgraphRAG trained retriever: we ran the authors’ MLP triple scorer, directional encodings, and shortest-path supervision on STaRK-PRIME. Both methods used the same frozen Qwen3 embeddings. We tried a few configurations; since we do not use LLMs for reranking, we tried a few extra steps to improve the results with cosine reranking and fused approaches to improve the results. (Reciprocal rank fusion combines the SubgraphRAG and cosine rankings, not raw scores; 25/75 gives cosine weights three times the weight of SubgraphRAG.) We did not find any variation that came at all close to SeedER’s performance.

MethodHit@1 (%)Hit@5 (%)MRR@20 (%)Recall@20 (%)
Trained SubgraphRAG, original scorer (LR 0.001)9.5931.4619.5738.68
SubgraphRAG + post-PCA L2 normalization (LR 0.001)10.0831.8219.9538.62
SubgraphRAG + post-PCA L2 normalization (LR 0.0003)10.5332.2620.3839.27
Reciprocal rank fusion: 25% SubgraphRAG / 75% cosine13.3439.2224.9648.91
Reciprocal rank fusion: 50% SubgraphRAG / 50% cosine12.4938.3824.7054.55
SeedER, matched features and candidates46.43 ± 0.9573.47 ± 0.8358.26 ± 0.9078.85 ± 0.54

For G-Retriever with a trained GNN–LLM: while this is substantially more expensive than the approaches to which we compare, luckily there is an NVIDIA blog post reporting results for full training of this model on STaRK-Prime with ada-002 embeddings. Here are the results from their Table 1, along with SeedER results using the same embeddings. Again, SeedER still substantially outperforms the full model.

MethodHit@1 (%)Hit@5 (%)MRR (%)Recall@20 (%)
G-Retriever32.27 ± 0.337.92 ± 0.234.73 ± 0.327.16 ± 0.1
G-Retriever NVIDIA pipeline32.0948.3438.4847.85
SeedER, ada-002, top 2043.2 ± 0.867.6 ± 0.653.9 ± 0.673.5 ± 0.5

The submitted Table 1 includes a range of baselines, from untrained graph-search methods to dense retrievers and LLM-based systems. Methods such as beam search and personalized PageRank show how much retrieval quality graph traversal alone can provide. The trained comparisons include DPR and ANCE (which fine-tune RoBERTa on each STaRK dataset), QAGNN (which trains a GNN on two-hop subgraphs), as well as supervised LLM fine-tuning, process reward models, and GraphFlow.

Following your suggestion, we will also add two additional comparisons on STaRK-PRIME: a fine-tuned MiniLM dense retriever using the same encoder checkpoint as SeedER (below), and SubgraphRAG’s learned triple scorer using the same Qwen embeddings and candidate graphs (above).

Q1. Many typos in the paper

Thanks for pointing this out; we’ve fixed these in the revision.

Q2. How does SeedER compare with a supervised selection ...

Provided above (under weaknesses 1 and 2).

Q3. All experiments use full answer sets ...

We agree that the recall as used in the submission requires knowing the number of correct answers. We thus conducted experiments that instead use the number of correct answers divided by the total number of returned nodes (20), which is the precision, and does not require this knowledge. The performance is similar; we reported these results in the revised paper.

DatasetTraining rewardHit@1Hit@5MRRRecall@20
PRIMERecall46.06 ± 1.3874.34 ± 0.5558.30 ± 0.9779.43 ± 0.27
PRIMEPrecision46.53 ± 2.4573.67 ± 1.1658.55 ± 1.8379.04 ± 0.91
MAGRecall56.29 ± 0.3675.45 ± 0.3764.67 ± 0.2275.13 ± 0.16
MAGPrecision55.75 ± 0.9175.16 ± 0.3164.38 ± 0.5175.19 ± 0.26
AMAZONRecall46.76 ± 0.5171.99 ± 0.2158.07 ± 0.4462.33 ± 0.24
AMAZONPrecision46.33 ± 1.1571.47 ± 1.2957.60 ± 1.0261.75 ± 0.38
Reviewer_vArqOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper retrieves answers from a knowledge graph through seed identification, bounded neighborhood expansion, and learned answer selection. A graph encoder conditions node representations on the query. Reinforcement learning encourages answer coverage, while a separate ranking objective determines answer order. The paper also studies the storage limitations of fixed node representations on relation tracing problems.

Critical strengths

s1. Keeping intermediate reasoning nodes separate from returned answers is a good design choice. A useful intermediate entity need not be an answer. Allowing it to participate in message passing without consuming the output budget fits the retrieval problem well.

s2. The theoretical analysis gives a concrete motivation for accessing graph structure at query time. Within the specified problem family, fixed node representations face a substantial information burden. Query dependent message passing offers a clear alternative.

s3. The experimental analysis goes beyond reporting a single final score. Candidate coverage, output quality, and variation across training runs are examined separately. I found the candidate graph replacement experiment especially useful because it shows how much the upstream retrieval stage matters.

Critical weaknesses

w1. My main concern is whether the learned model is genuinely using relational structure. It already receives strong semantic features, query similarities, and hop information. Comparisons with simpler graph networks do not isolate the value of the actual graph edges. Does the improvement survive if relation types are shuffled or graph edges are removed while candidate nodes remain unchanged?

w2. The case for reinforcement learning is less clear than the case for the overall pipeline. Most policy ablations concern baselines and sampling. A direct supervised ranking model with the same encoder and judgment budget would be a stronger test. The recall reward also uses the full answer count, so the current experiments do not fully demonstrate the claimed benefit under limited feedback.

w3. The theoretical argument requires the relevant reasoning path to be present. The practical expansion procedure can discard parts of that path before learning begins. Answer coverage does not tell us whether the necessary intermediate evidence survives. Are some answers retained but stripped of the relations needed to identify them? That would be worth checking directly.

w4. The efficiency evaluation leaves out online query encoding and uses a simplified language model workload as its comparison. This limits what the reported speed difference establishes. Since low resource inference is central to the paper, I would expect complete query latency, resident graph and index memory, and actual processor only measurements.

Questions for authors

See above comments. I lean toward acceptance because the retrieval improvements are substantial and the theoretical perspective is useful. Still, the paper makes a stronger case for the complete pipeline than for the necessity of each learned component. Better controlled comparisons could change my score.

4 comments

We thank the reviewer for their careful evaluation and constructive feedback. We address their comments point by point below:

w1. My main concern is whether the learned model is genuinely using relational structure.

Thank you for suggesting this control. We held the candidate nodes, semantic features, and hop features fixed. We first modified the graph only at test time, then trained a model from scratch under each condition. For this experiment, we used the variant with both virtual nodes and expander.

Graph conditionTest Recall@20, test-time change onlyTest Recall@20, trained from scratch
Intact graph79.01%79.01%
KG edges removed, virtual-node and expander links retained48.67%65.56%
All edges removed50.18%67.40%
Relation types shuffled, edge endpoints preserved58.64%75.05%

When we shuffle relation types, we consistently map all type-A edges to type-B edges. Shuffling relation types alone leads to results closer to the main model, meaning the model can learn to properly modify the edge features beyond the initial edge features. The remaining drop suggests that the original relation types do contribute beyond graph connectivity, semantic features, and hop information. These experiments are done with a single seed (0) because of time constraints.

w2. The case for reinforcement learning ...

Our motivation for RL beyond STaRK is that feedback may be available only for the set as a whole. There are many settings where we can see whether a downstream model answers a question with a given set of information, but since data points might be redundant (or complementary), it may be difficult to tell without extensively re-calling the model with different subsets which entries were actually useful to the answer quality. These set-level rewards are easily incorporated in an RL pipeline, but difficult to map to supervised learning. Furthermore, SeedER samples without replacement and computes the probability of each ordered draw, allowing a policy gradient to optimize the expected set reward without differentiating through top-20 selection. This lets us inspect how often a node is selected across draws given the learned probabilities, which gives a nice probabilistic character to the approach. While we have not tested downstream-answer rewards due to the added complexity of reliably evaluating these setups, we hope this clarifies what motivates the formulation beyond our empirical results on STaRK.

We agree that supervised training with the same encoder in STaRK’s clean setup is a more direct comparison. We therefore trained two supervised variants on PRIME using the same frozen Qwen embeddings, 500-node candidate pools, and an Exphormer backbone. One receives labels for all candidate nodes; the other receives labels only for its current top 20, selected before seeing the labels. Results support the use of RL for properly estimating these probabilities:

MethodHit@1Hit@5MRR@20Recall@20
Supervised, 500 candidates.3856 ± .0192.6735 ± .0161.5111 ± .0172.7473 ± .0103
Supervised, top 20.4006 ± .0197.6745 ± .0084.5199 ± .0148.7410 ± .0081
SeedER.4606 ± .0138.7434 ± .0055.5830 ± .0097.7943 ± .0027

We agree that the recall as used in the submission requires knowing the number of correct answers. We thus conducted experiments that instead use the number of correct answers divided by the total number of returned nodes (20), which is the precision, and does not require this knowledge. The performance is similar; we will report these results in the revised paper.

DatasetTraining rewardHit@1Hit@5MRRRecall@20
PRIMERecall46.06 ± 1.3874.34 ± 0.5558.30 ± 0.9779.43 ± 0.27
PRIMEPrecision46.53 ± 2.4573.67 ± 1.1658.55 ± 1.8379.04 ± 0.91
MAGRecall56.29 ± 0.3675.45 ± 0.3764.67 ± 0.2275.13 ± 0.16
MAGPrecision55.75 ± 0.9175.16 ± 0.3164.38 ± 0.5175.19 ± 0.26
AMAZONRecall46.76 ± 0.5171.99 ± 0.2158.07 ± 0.4462.33 ± 0.24
AMAZONPrecision46.33 ± 1.1571.47 ± 1.2957.60 ± 1.0261.75 ± 0.38

w3. The theoretical argument requires the relevant reasoning path to be present ...

Yes, it is certainly possible for filtering to leave an answer node but miss the intermediate evidence. Unfortunately, STaRK provides answer node annotations, but no annotations of “correct” seed nodes or reasoning paths. As a rough guess, then, we did a new experiment examining the shortest directed paths from any of our five retrieved seed nodes to an answer. Of the 2,801 PRIME/Qwen test queries, there are 956 query-answer pairs where the answer node was retained in the subgraph and whose shortest seed-to-answer path in the full KG was two or three hops long. Of these, 627 retained all of the shortest routes, 320 retained some, but not all of the shortest routes, and 9 lost all of their shortest routes. In those nine cases, the shortest seed-to-answer route in the subgraph was length three, rather than two. Thus, 99.1% retained at least one shortest route, although we do not know whether this is a “correct” reasoning route.

w4. The efficiency evaluation leaves out online query encoding ...

The initial query embedding and seed node finding is identical between our method and most other methods, including GraphFlow. As requested, we ran speed comparisons on the full SeedER pipeline, including embedding the query and finding seed nodes. These results are on an NVIDIA H100 80 GB HBM3 with four host CPU cores, using batch size one.

For Llama 3.1-8B, we used a cheap proxy that only checks three nodes and outputs at most 16 tokens per check; realistic reasoning setups checking more nodes would be much slower. Note that Llama timings also do not include embedding the query nor finding seed nodes, simply running the (extremely small) search process. Adding that would require additional time, as well as additional GPU memory for using both the embedding and the search models at the same time.

MethodEnd-to-end latency, mean ± SDEncoding + PCAPeak GPU memoryWarm host RAMGraph + index RAM
SeedER + MiniLM84.1 ± 65.4 ms2.7 ms0.35 GiB2.28 GiB0.68 GiB
SeedER + Qwen3-4B92.5 ± 49.0 ms23.4 ms7.90 GiB2.79 GiB0.92 GiB
Llama 3.1-8B-Instruct, three-call proxy526.2 ± 226.1 ms-15.47 GiB1.42 GiBNA

We also tried running these experiments on CPU instead, using four CPU threads on an AMD EPYC 9655.

MethodEnd-to-end latency, mean ± SDEncoding + PCAPeak GPU memoryWarm host RAMGraph + index RAM
SeedER + MiniLM96.2 ± 88.4 ms45.0 ms–1.46 GiB0.68 GiB
SeedER + Qwen3-4B602.5 ± 164.7 ms549.1 ms–8.57 GiB0.92 GiB
Llama 3.1-8B-Instruct, three-call proxy169,900 ± 148,600 ms––14.96 GiBN/A

See above comments. I lean toward acceptance

Thank you for considering the merits of our work and for recognizing both the retrieval gains and the value of the theoretical perspective. In our responses to the weaknesses you raised, we report additional controlled comparisons.

Thanks for authors' detailed response, good work, I will keep my positive score.

Thank you for carefully reviewing our paper and rebuttal and helping us improve our work. We appreciate your positive feedback and will incorporate the new experiments into the revised paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.