1 Introduction↩︎

Many real-world queries combine free-form textual descriptions with structural constraints over typed relations. A shopper may look for “a push-along tricycle from Radio Flyer that is both fun and safe for my kid”; a medical researcher may ask “what disease is associated with the PNPLA8 gene and presents with hypotonia as a symptom?” [1]. Answering such queries requires retrieval over semi-structured knowledge bases (SKBs): collections of textual documents (e.g., product descriptions, paper abstracts, and gene/disease detail dictionaries) embedded in a richly typed graph of entities and relations. SKBs underpin a wide range of applications, including e-commerce product search, academic literature search, and precision-medicine inquiries [1]–[3], where neither pure text nor pure graph retrieval alone is sufficient: textual signals resolve free-form descriptions but ignore relational constraints, while graph traversals enforce relational constraints but cannot match nuanced textual properties. STaRK [1] formalizes three such benchmarks, i.e., Amazon for product search, MAG for academic paper search, and Prime for biomedical retrieval. Although both text-based and graph-based methods have been mature and diverse [4]–[13], STaRK shows that purely textual retrievers (sparse or dense embeddings) and purely structural retrievers (graph neural networks) leave significant headroom for improvement. This motivates hybrid retrieval systems that integrate the two signals.

Prior hybrid systems on STaRK take several forms. AvaTaR [14], KAR [15], and HybGRAG [16] layer an LLM on top of a textual retriever, using the model to expand or rewrite the query and/or to score relations. mFAR [2] trains a dense multi-field retriever that conditions on the per-document field schema. MoR [17] learns a mixture over a structural and a textual branch. GraphRAFT [18] fine-tunes a generator on graph traversals. AF-Retriever [3] pipelines a planning LLM with focused graph retrieval. None of these systems unifies a robust plan-execution backbone that admits a per-query confidence estimate, plan-conditioned fusion with a strong dense retriever, and a trained reranker that lifts the fused candidate list to top-1.

In this paper we present GRASP, an end-to-end framework that integrates all three. GRASP consists of three stages, each addressing one aspect of the prior gap. First, an LLM converts the query into a structured plan, which is executed against a graph database to retrieve candidates and rescored with a dense encoder. Second, the graph-based ranking is fused with a separately trained dense retriever via RRF [19], with fusion weights optionally conditioned on the planner’s outputs. Last, a fine-tuned LLM-based reranker scores the fused candidates and is then fused again with the upstream ranking. Overall, GRASP achieves the best result on every metric across the three STaRK datasets. Average Hit@1, Hit@5, Recall@20, and MRR improve by 11.9, 13.7, 17.2, and 12.9 absolute points over the strongest prior, respectively.

Our contributions are three-fold: (1) a simple but effective framework GRASP that substantially advances the previous state-of-the-art on SKB retrieval; (2) we show that the results of graph and dense retrieval are complementary and can be fused to boost performance, and the comprehensive fused pool benefits a subsequent fine-tuned reranker; (3) GRASP is robust to its hyperparameter choices.

2 Related Work↩︎

2.0.0.1 Textual retrievers.

Classical sparse retrieval BM25 [20] remains a competitive baseline on STaRK [1]. Dense passage retrieval DPR [21] learns query/document encoders end-to-end; commercial encoders such as ada-002 [22] provide strong off-the-shelf baselines. Recent open-source families (e.g. Qwen3-Embedding series [23]) match or exceed ada-002 on web text; in the biomedical domain, SapBERT [24] remains the standard “embedding” baseline because it has been pretrained on UMLS [25] synonyms.

2.0.0.2 Structural retrievers.

Structural retrievers reason over typed entity/relation graphs. QAGNN [26] jointly reasons over text and a sparsified subgraph. Think-on-Graph [27] uses an LLM as a beam-search controller over graph paths; it is competitive on small knowledge graphs but struggles on STaRK’s million-node graphs where the branching factor is high.

2.0.0.3 Hybrid retrievers on STaRK.

AvaTaR [14] optimizes tool-use prompts so that an LLM can interleave structural lookups with textual scoring. KAR [15] expands the query with knowledge-aware terms before a dense retriever. mFAR [2] uses a multi-field adaptive dense retriever that jointly encodes a document’s textual fields and its 1-hop neighborhood. It is the strongest dense retriever and we adopt it as the dense partner in our fusion. HybGRAG [16] routes between a structural and a textual branch. MoR [17] learns a mixture of structural and textual scoring. GraphRAFT [18] fine-tunes a generator on graph traversals using a Neo4j [28] backend. AF-Retriever [3] couples a planning LLM with focused graph retrieval and is the strongest published prior on average Hit@1.

3 Method↩︎

GRASP consists of three stages. Stage 1 produces a graph plan, executes it against the SKB, and rescores the executed candidates based on residual textual information. Stage 2 fuses the Stage-1 ranking with a separately trained multi-field retriever using one of two RRF variants: query-independent or -dependent. Stage 3 reranks the Stage-2 ranking with a fine-tuned LLM-based reranker and fuses it with the reranker output. Figure 1 gives an overview of GRASP with a concrete example.

3.1 Stage 1: Plan generation, execution, and dense rescoring↩︎

Stage 1 produces a graph-based ranking in three steps: a planner converts the query into a structured plan, an executor runs the plan against the SKB to obtain candidates and anchor scores, and a dense rescorer refines those scores using residual textual constraints. We use Qwen3-Embedding-4B on Amazon and MAG, and SapBERT on Prime, as the dense encoders throughout the stage.

3.1.0.1 Plan generation.

Given a query \(q\), an instruction-tuned LLM emits a single JSON plan. The prompt is composed of four shared modules: a role declaration that fixes the model as a structural parser; the KG schema, listing node and relation types available in the SKB; a plan-structure definition for the three core slots anchors (text entities mentioned in \(q\)), hops (graph walks among anchors toward the target variable T), and target (T’s possible node types and residual text constraints that the hops cannot encode); and a fusion-control block asking the planner to self-report a risk_level that governs how strongly the graph branch is mixed in Stage 2. Specifically, each plan has the form

{"anchors": [{"var", "text", "label",
              "match_mode"}, ...],
 "hops":    [{"from", "rel", "to_var",
              "to_label"}, ...],
 "target":  {"var": "T", "labels": [...],
             "relevance_text": ...},
 "risk_level": ...}

where var, from, and to_var are variable identifiers referring to anchors or the target; label and to_label take values from the SKB’s node types; labels is a list of node types; rel is one of the SKB’s relation types; relevance_text carries text constraints; and \(\texttt{risk\_level} {\in} \{\texttt{no\_trade}, \texttt{weak}, \texttt{normal}, \texttt{aggressive}\}\). On top of this shared skeleton, each dataset adds its own dataset-specific guidance, inspired by the metapath templates STaRK provides: MAG enumerates seven metapath templates as planner hints; Amazon adds six planning rules and five hand-curated (query, plan) few-shot examples; and Prime appends nineteen examples. Full prompts are provided in Appendix 8.

3.1.0.2 Plan execution.

The plan is executed in three steps. (1) Anchor linking. Each anchor’s text is embedded with the dataset’s dense encoder and looked up in a vector index over nodes of the declared type. Two lookup modes are supported: \(\texttt{match\_mode} {=} \texttt{name}\) hits a name-only index intended for short entity strings (e.g., “Sony”), while \(\texttt{match\_mode} {=} \texttt{doc}\) hits a full-document index intended for descriptive phrases (e.g., “headphones with long battery life”). The top-\(K\) matches above a per-anchor similarity threshold form the candidate bindings, each carrying its cosine score (Appendix 7). (2) Plan compilation. The plan is compiled into a single Cypher [29] query: anchors expand to UNWIND over their bindings, hops expand to undirected MATCH patterns, and the target variable is returned with a per-row anchor score equal to the sum of cosine scores along the matched path. When several paths reach the same target, we keep the maximum. (3) Cypher execution. The compiled query runs against a Neo4j backend hosting the SKB and yields one anchor score per target candidate. The candidate-set size \(\mathtt{n\_cand}\) together with \(\mathtt{risk\_level}\) are exposed to Stage 2 as the metadata for ranking fusion.

3.1.0.3 Dense rescoring.

When relevance_text is not empty, each candidate is additionally scored by the cosine similarity between the embedding of relevance_text and the candidate’s document embedding, and then added to the anchor score. The mechanism handles textual constraints the hops cannot express, for instance “at least 30 hours of battery life” on a product already constrained to brand “Sony” by a HAS_BRAND hop. When it is empty (typical when the hops alone fully specify the query), this step is skipped and candidates are ranked by the anchor score alone.

3.2 Stage 2: Plan-conditioned fusion with the multi-field dense retriever↩︎

Alongside the graph-based ranking from Stage 1, we run the multi-field dense retriever mFAR over the same corpus to produce a complementary text-focused ranking. The two rankings are then fused via one of two RRF variants: one with fixed weights and one with query-dependent weights.

3.2.0.1 Static RRF.

A standard two-input form with a global graph weight \(w {\in} [0,1]\) and RRF constant \(k\): \[\mathrm{score}(c) \;=\; \frac{w}{k + \mathrm{rank}_{g}(c)} + \frac{1-w}{k + \mathrm{rank}_{m}(c)},\] where \(c\) is a candidate and \(\mathrm{rank}_g\), \(\mathrm{rank}_m\) are its per-query ranks from the graph and mFAR branches.

3.2.0.2 Dynamic RRF.

The graph weight is computed per query \(q\) from the planner’s \((\texttt{n\_cand}, \texttt{risk\_level})\) outputs: \[\begin{align} \hat{w}_{\mathrm{graph}}(q) &= \mathbf{w}_{\mathrm{bucket}}[b(q)] \cdot \mathbf{m}_{\mathrm{risk}}[r(q)],\\ \mathrm{score}(c) &= \frac{\hat{w}_{\mathrm{graph}}(q)}{k + \mathrm{rank}_g(c)} + \frac{1}{k + \mathrm{rank}_m(c)}, \end{align}\] where \(b(q) {\in} \{[1,10], [11,50], [51,100], [101,500], {>}500\}\) is the n_cand bucket, \(r(q)\) is the risk_level label, and \(\mathbf{w}_{\mathrm{bucket}}\), \(\mathbf{m}_{\mathrm{risk}}\) are lookup vectors tuned on validation. When \(\hat{w}_{\mathrm{graph}} {=} 0\), the score collapses to pure mFAR, giving the planner a built-in opt-out for unreliable graph rankings.

For each dataset, we grid-search the hyperparameters of both variants over the ranges in Appendix 7 and select the one with the highest validation Hit@1. In practice, Amazon and Prime select dynamic RRF, while MAG selects static RRF (Table 2); the per-query \((\texttt{n\_cand}, \texttt{risk\_level})\) distribution and chosen weights are shown in Figure 2.

3.3 Stage 3: Reranking and final fusion↩︎

For each training query, the candidate pool consists of the top-100 candidates from the Stage-2 fused list. Each query’s training record stores all of its positives in the pool together with the top-30 hardest negatives. Each candidate is serialized into a single text document containing (i) the node’s type and dataset-specific text fields, and (ii) its 1-hop neighbors grouped by relation type, with a per-relation cap of 10 neighbors (formatting details in Appendix 8.6). At each training step, the listwise collator builds a group of \(G{=}24\) candidates by uniformly sampling one positive and 23 hard negatives from the query’s stored set. Sampling is independent per step, so each positive is paired with a different negative subset on every visit, which acts as a mild stochastic regularizer.

We fine-tune an LLM-based reranker with LoRA adapters under a listwise softmax loss. The reranker emits one logit per candidate; the loss is the cross-entropy of identifying the positive position among the \(G\) logits, which pulls the positive’s score up while pushing all 23 sampled negatives down. Training details are in Appendix 7.

At inference, the trained reranker scores the top-100 candidates of the Stage-2 fused list, and its output is fused with the Stage-2 ranking via static RRF with \((w, k)\) tuned on validation. We also report a variant that uses the base non-fine-tuned reranker, which serves as a zero-shot version of GRASP and isolates the effect of fine-tuning.

4 Experiments↩︎

4.1 Datasets and metrics↩︎

We evaluate on the three STaRK datasets: Amazon (product search), MAG (academic paper search), and Prime (precision-medicine queries). Dataset statistics are summarized in Table 3. The SKBs of these datasets vary dramatically in graph density and in the relative importance of textual versus relational information [1]. Amazon’s is the most textual, with product nodes carrying rich content from product descriptions, customer reviews, and Q&A data, while its relational structure is limited to a few types such as also_bought and has_brand. Prime’s is the most relational and graph-heavy, with ten entity types and eighteen relation types spanning diseases, drugs, genes, and pathways, but with comparatively sparse text. MAG’s sits in between: its paper nodes carry titles and abstracts, while the graph is dominated by high-cardinality cites and writes relations. These differences make the three datasets a natural testbed for studying when graph structure helps over text alone. For evaluation, we report Hit@1, Hit@5, Recall@20, and MRR, all in percent.

4.2 Baselines and variants↩︎

We consider baselines across three categories (textual, structural, and hybrid) and two settings (zero-shot and supervised).

4.2.0.1 Textual (zero-shot).

BM25 [20]; ada-002 and multi-ada-002 [22]; DPR (with RoBERTa, [21]); and Qwen3/SapBERT, using Qwen3-Embedding-4B [23] on Amazon/MAG and SapBERT [24] on Prime.

4.2.0.2 Structural (zero-shot).

QAGNN [26] and ToG [27].

4.2.0.3 Hybrid.

AvaTaR (supervised, [14]); KAR (zero-shot, [15]); mFAR (supervised, [2]); HybGRAG (zero-shot, [16]); MoR (supervised, [17]); GraphRAFT (supervised, [18]); and AF-Retriever (zero-shot, [3]). We additionally report mFAR\(^*\), our re-run of mFAR as the dense partner in Stage-2 fusion.

4.2.0.4 GRASP ablations.

We report full GRASP and three ablations: w/o RR f.t. replaces the fine-tuned reranker with its zero-shot base; w/o RR removes the reranker stage entirely (Stage-2 output); and w/o RR & FS additionally removes the fusion with mFAR, leaving only the graph branch (Stage-1 output). The Qwen3/SapBERT baseline can also be viewed as an extreme ablation that shares GRASP’s dense encoders but ignores the graph entirely.

Results for BM25, ada-002, multi-ada-002, DPR, and QAGNN are taken from the STaRK paper; ToG is taken from the MoR paper; AvaTaR, KAR, mFAR, HybGRAG, MoR, GraphRAFT, and AF-Retriever are taken from their original papers. GRASP (full and ablations), Qwen3/SapBERT, and mFAR\(^*\) are from our own runs.

4.3 Main results↩︎

Table 1 reports performance across all three datasets. GRASP achieves the top result on every reported metric, with average Hit@1 reaching \(73.9\) versus \(62.0\) for the strongest prior, a gain of \(+11.9\) points. Averaged across datasets, Hit@1, Hit@5, Recall@20, and MRR improve by \(+11.9\), \(+13.7\), \(+17.2\), and \(+12.9\) absolute points, respectively, over the strongest prior on each metric. GRASP also achieves the best average performance over zero-shot baselines alone. These results establish GRASP as the new state of the art on SKB retrieval by a large margin.

The per-dataset breakdown shows that GRASP delivers consistent improvements regardless of each SKB’s textual-versus-relational character. On Amazon, gains on all four metrics are roughly \(+10\) points each (\(+10.0\), \(+13.1\), \(+10.0\), \(+11.4\)), confirming that GRASP excels on text-heavy SKBs by leveraging both the dense partner and the trained reranker. On Prime, the gains on Hit@1 (\(+4.1\)) and MRR (\(+7.9\)) are smaller, while Hit@5 (\(+12.6\)) and Recall@20 (\(+11.7\)) remain above \(+10\), showing that GRASP handles relation-heavy SKBs well, with the bulk of its advantage in expanding the relevant candidate pool. On MAG, the gap is the tightest (\(+4.2\), \(+3.7\), \(+2.4\), \(+4.3\)), which may be because MAG appears the easiest of the three, and its citation structure suits graph-walking pipelines like GraphRAFT and AF-Retriever. Yet, GRASP still surpasses them on every metric, and extends the lead substantially on broader candidate retrieval (\(+22.8\) Recall@20 over the best zero-shot system).

The advantage widens further on the human-curated test subset (Table 4), a more authentic probe of real-world queries. Averaged across the three datasets, GRASP’s gains over the strongest prior reach \(+17.3\), \(+23.7\), \(+18.1\), and \(+20.0\) absolute points on Hit@1, Hit@5, Recall@20, and MRR, respectively, substantially larger than on the synthesized test set. This demonstrates that GRASP’s design transfers especially well to real-world query distributions, beyond the synthesized benchmark used for training.

4.4 Ablation study↩︎

The lower block of Table 1 reports the three GRASP ablations defined in Section 4.2. Reading them bottom-up builds GRASP back up one component at a time: graph-only (\(\text{w/o RR \& FS}\)) \(\to\) +fusion (\(\text{w/o RR}\)) \(\to\) +zero-shot reranker (\(\text{w/o RR f.t.}\)) \(\to\) +trained reranker (full GRASP). We focus on Hit@1 and Recall@20, since Hit@5 and MRR track Hit@1 closely.

4.4.0.1 Graph and dense are complementary, and their fusion boosts performance.

Adding the mFAR fusion to the graph branch lifts Recall@20 sharply on every dataset: \(+17.8\) on Amazon, \(+5.9\) on MAG, and \(+22.2\) on Prime. The Hit@1 lift follows the same pattern but with dataset-specific magnitude (\(+14.0\), \(+2.7\), \(+16.4\), respectively), reflecting how much new information the dense branch contributes once the graph branch has filtered the search space. The gain is largest where the two branches are least correlated: on Amazon, the graph alone is weak (Hit@1 \(37.2\)) because the dataset is heavily text-leaning, so the dense branch carries most of the new evidence; on Prime, the graph alone already covers \(62.0\%\) of relevant candidates, but the dense branch surfaces another \(22.2\) points of recall, indicating that the two branches retrieve substantially different candidates. MAG is the only dataset where the graph branch already secures a high recall pool (\(82.2\)), leaving less room for fusion to help on Recall@20.

4.4.0.2 The fused pool benefits the trained reranker.

After fusion, the candidate pool has high Recall@20 on every dataset (\(63.1\) Amazon / \(88.1\) MAG / \(84.2\) Prime), which gives the reranker enough relevant candidates to re-order. The zero-shot reranker, however, leaves most of this potential untapped: it adds only \(+6.2\), \(+3.4\), and \(+0.0\) Hit@1 on Amazon, MAG, and Prime, with the Prime case being a clean failure (the validation grid for the zero-shot reranker collapses to pure fused, \(w{=}0\)). The trained reranker recovers the missing precision: \(+13.8\), \(+13.5\), and \(+7.6\) Hit@1 over the zero-shot reranker on the three datasets, respectively, while changing Recall@20 only marginally (\(+2.3\), \(+3.0\), \(+3.9\)). The contrast confirms two things at once: a high-recall fused pool is what makes top-rank precision recoverable, and fine-tuning is what actually recovers it, by utilizing the high-quality hard negatives the pool supplies.

4.4.0.3 All three stages are necessary.

On one hand, the two paragraphs above show that performance improves as we add stages, confirming that each stage contributes positively. On the other hand, the dominant contributor stage differs by dataset. Fusion contributes the most on Amazon: the dataset is text-heavy and the graph branch alone is weak, so the dense partner brings in most of the new evidence. The graph branch contributes the most on MAG, whose citation structure already provides a strong retrieval signal on its own. Fusion and the trained reranker share the load on Prime, where domain-specific fine-tuning is essential because the base reranker lacks biomedical knowledge. Hence, GRASP needs all three stages to perform best.

4.5 Hyperparameter sensitivity↩︎

GRASP exposes a small number of hyperparameters (fusion mode, fusion weights, reranker training budget), and we check that the final performance is robust to reasonable choices on each, which makes GRASP easy to deploy without per-dataset hyperparameter expertise. All sensitivity studies are reported on the validation split, with the chosen operating point then frozen for test.

4.5.0.1 Fusion mode is not a sensitive choice on most datasets.

Table 2 compares static against dynamic RRF for fusing the graph branch with mFAR. On Amazon and Prime, the two variants are within \(1.5\) points of each other, meaning the choice of fusion mode is not a sensitive lever once the underlying branches are in place. MAG is the only exception, where static RRF wins by more than 2 points; the asymmetry is explained by the bucket/risk distribution (Figure 2b): most MAG queries fall into the same \((\text{bucket}, \text{risk})\) cell, so dynamic weighting reduces to a near-constant and adds noise. We therefore freeze static for MAG and dynamic for the other two; in all cases, the wrong choice would still likely keep GRASP ahead of prior baselines.

4.5.0.2 Static RRF \((w, k)\) has a broad flat region.

Figure 4 shows the Hit@1 heatmap over the static-RRF grid \((w, k)\) for fusing the trained reranker with the Stage-2 fused ranking. The best \((w, k)\) per dataset is \((0.65, 2)\) on Amazon, \((0.50, 5)\) on MAG, and \((0.50, 2)\) on Prime, but the high-performance region is broad rather than peaked: Hit@1 stays within \(1\) point of the optimum across a wide range of \((w, k)\) values around the maximum on every dataset. The shape of the optimum has a sensible interpretation: Amazon’s higher \(w\) reflects that its Stage-2 upstream is the weakest of the three, so the reranker carries more weight.

4.5.0.3 Reranker fine-tuning is robust to the training budget.

Figure 3 reports metrics over the reranker fine-tuning steps. The curves rise monotonically on Amazon, peak then plateau on MAG, and rise smoothly without a clear plateau on Prime. In every case, performance is substantially above the zero-shot base by the midpoint of training, and the gap between any late-training checkpoint and the chosen one is small. These indicate that our fine-tuning recipe is both robust and effective. The Amazon curve is still rising at the final step, suggesting that further training would help; we hold the budget fixed across datasets for fairness rather than chase additional gains.

5 Discussion↩︎

5.0.0.1 When does graph structure help?

We isolate graph structure’s contribution with a controlled diagnostic: a single dense embedder run over the full corpus, with no plan, no graph walk, no fusion, and no reranker (the Qwen3/SapBERT row of Table 1). Since GRASP’s graph branch uses the same encoder, the gap between the two isolates what the graph adds. On Amazon, the embedding-only Hit@1 (\(44.6\)) is even higher than that of the graph branch (\(37.2\)), which may be because product descriptions dominate the query semantics, and the graph walk often discards relevant candidates the text encoder could have surfaced. On MAG, the graph branch lifts Hit@1 from \(32.6\) (embedding-only) to \(63.2\), supplying the relational signal (writes, cites) that text cannot recover. On Prime, the graph branch lifts Hit@1 from \(9.0\) to \(43.8\), since its SKB’s biomedical relations carry most of the signal and the encoder was not pretrained for long-document biomedical retrieval.

5.0.0.2 Case studies.

To illustrate how each stage contributes, we show one query per dataset, annotated with the (mFAR, graph-only)\(\to\)+fusion\(\to\)+zero-shot reranker\(\to\)+trained reranker rank progression of the gold answer.

Amazon (multi-attribute product search). Query: “Looking for unique and eye-catching golf club headcovers; endearing, made from durable, colorfast fabric, with good quality stitching.” Gold: Butthead Golf Club Headcovers. Rank progression: \(\mathbf{(19, 17) \to 13 \to 10 \to 1}\). mFAR alone matches generic quality terms (“durable”, “colorfast”) against thousands of premium-branded headcovers; the distinctive “endearing” is too weak alone. The graph branch anchors to “headcovers” via category edges but has no notion of brand character. Fusion averages the two failure modes; the zero-shot reranker recognizes the cross-field alignment between “endearing/eye-catching” in the query and humor-themed feature/review text in the gold; fine-tuning teaches the reranker to weight distinctive-brand cues over generic premium ones.

MAG (shared-author + topic constraint). Query: “Look for papers with shared authors to Longitudinal study of retinal degeneration in a rat using spectral domain optical coherence tomography, focusing on the same area, retinal imaging, and discuss the use of a multi-modal retinal imaging system.” Gold: Multispectral scanning laser ophthalmoscopy combined with optical coherence tomography for simultaneous in vivo mouse retinal imaging. Rank progression: \(\mathbf{(8, 9) \to 6 \to 4 \to 1}\). mFAR matches topic terms but has no representation of “shared authors”. The graph branch returns co-authored papers but cannot separate topic-aligned from topic-unrelated ones. Fusion intersects co-authorship (graph) with topic (dense). The zero-shot reranker reads each candidate’s 1-hop neighbors (author overlap with the seed, field-of-study tags), making the joint constraint explicit in the input; fine-tuning teaches it to weight (co-author overlap, topic overlap) as a joint feature.

Prime (gene-disease relation + phenotype filter). Query: “What disease is linked to the B3GALT6 gene, often presenting as focal epilepsy in a person’s teens?” Gold: Ehlers-Danlos syndrome with periventricular heterotopia. Rank progression: \(\mathbf{(64, 9) \to 2 \to 2 \to 1}\). mFAR has no awareness of gene-disease links and matches only on the thin phenotype clause. The graph branch executes the gene-disease hop but cannot disambiguate among several diseases linked to B3GALT6. Fusion gives a small high-precision pool where even a weak dense signal can favor the disease whose detail dictionary mentions epilepsy/teen-onset terms. The zero-shot reranker does not help (domain-blind on biomedical entities); the trained reranker reads the candidate’s serialized 1-hop [ASSOCIATED WITH] line listing gene neighbors (including B3GALT6), and learns to align this structural signal with the phenotype clause, a feature pure dense matching cannot recover.

5.0.0.3 Per-query metadata explains where dynamic RRF helps.

The dynamic RRF weight \(\hat{w}_{\mathrm{graph}}(q)\) is computed from each query’s \((\text{bucket}, \text{risk})\) metadata; Figure 2 reports the validation distribution over this metadata. On MAG, \(73\%\) of queries fall in a single bucket and \(98\%\) are labeled risk_level=normal, so dynamic weighting reduces to a near-constant and adds noise relative to static RRF; static therefore wins by \(+2.6\) Hit@1. On Prime, both axes are genuinely heterogeneous and the per-query weighting compensates for highly variable plan quality, where dynamic wins by \(+1.3\) Hit@1. Amazon is in between and the two variants tie within noise. The \(\mathbf{m}_{\mathrm{risk}}[\texttt{no\_trade}] {=} 0\) entries on Amazon and MAG also mean that queries the planner self-flags as unreliable collapse to pure mFAR, giving the planner a built-in opt-out.

6 Conclusion↩︎

GRASP is a three-stage retrieval framework for semi-structured knowledge bases. It converts the query into a structured plan, executes the plan against a graph database with dense rescoring, fuses with a separately trained multi-field retriever via plan-conditioned RRF, and reranks the fused top candidates with a fine-tuned reranker that is again fused with the upstream. On STaRK, GRASP sets a new state of the art on every metric across three datasets, with average Hit@1 reaching \(73.9\) versus \(62.0\) for the strongest prior. Per-component ablations show that the graph and dense branches are complementary, and that the fused candidate pool supplies high-quality hard negatives that a downstream reranker can exploit to push top-rank precision substantially higher. The headline performance of GRASP is stable across reasonable choices of hyperparameters, making it easy to deploy without per-dataset hyperparameter expertise.

Limitations↩︎

6.0.0.1 Generalization beyond STaRK.

Our experiments cover three SKB benchmarks (Amazon, MAG, Prime) that share the STaRK construction protocol and a common English schema. Transfer to other SKBs (e.g., industrial product catalogs, non-English biomedical KGs, or KGs with substantially deeper relation hierarchies) remains untested; we expect plan generation to be the component most sensitive to such shifts, since it relies on the LLM recognizing the dataset schema in-context.

6.0.0.2 Interpretability.

While our ablations attribute performance to specific stages (plan, fusion, reranker) and our case studies illustrate how each stage helps on individual queries, we do not provide a systematic account of why a given top-\(1\) prediction emerges from the interaction of all three stages. Mapping each retrieval decision back to a chain of (plan, fusion weight, reranker score) interactions is left to future work.

6.0.0.3 Dependence on a strong instruction-tuned LLM.

Plan generation is zero-shot prompting of a frontier LLM; if the schema or the queries are too far from the LLM’s pretraining distribution, the planner may emit invalid or low-quality plans more often than the \(1\%\)–\(2\%\) rate we observe on STaRK. Recovery from such failures (retries, self-critique, ensembling) is a natural follow-up we did not explore.

7 Implementation Details↩︎

7.0.0.1 Models.

Stage 1 plan generation uses Qwen3-27B-Instruct [23]. The trained reranker is Qwen3-Reranker-0.6B [23]. The SKB is hosted in Neo4j [28]; per-node embeddings are pre-computed at indexing time with doc_max_len 512 (Amazon, MAG) or 256 (Prime). The top-\(K\) matches whose cosine similarity is at least \(\tau\) times the top-1’s similarity become candidate bindings for that anchor variable, each with its cosine score; we use \((K, \tau) = (5, 0.95)\) for name-mode and \((10, 0.90)\) for doc-mode, identical across the three datasets.

7.0.0.2 Fusion sweeps.

Static RRF: \(w {\in} \{0, 0.05, \ldots, 1\}\) and \(k {\in} \{1, 2, 5, 10, 20, 40, 60, 80, 100\}\). Dynamic RRF: \(k {\in} \{5, 10, 20, 40, 80, 150, 300\}\), \(\mathbf{w}_{\mathrm{bucket}}\) (in the order \([1,10], [11,50], [51,100], [101,500], {>}500\)) lies in \(\{1.0, 1.2, 1.4, 1.6, 2.0\} {\times} \{0.8, 1.0, 1.2, 1.4\} {\times} \{0.2, 0.4, 0.6, 0.8\} {\times} \{0, 0.05, 0.1\} {\times} \{0, 0.05, 0.1\}\), and \(\mathbf{m}_{\mathrm{risk}}\) (in the order \(\texttt{no\_trade}, \texttt{weak}, \texttt{normal}, \texttt{aggressive}\)) lies in \(\{0, 0.25, 0.5, 0.75\} {\times} \{0.5, 0.75, 1.0, 1.25\} {\times} \{0.75, 1.0, 1.25, 1.5\} {\times} \{1.0, 1.25, 1.5, 2.0\}\).

7.0.0.3 Reranker training.

LoRA adapters with rank \(r=32\) and scaling \(\alpha=64\) attached to all linear layers. Schedule: 2 epochs of cosine LR decay from \(3{\times}10^{-5}\), warmup 5%, global batch 16. Max sequence length is 1024 for Amazon and MAG and 2048 for Prime (its detail dictionaries are longer); per-field truncation max_text_field_tokens is 300 (Amazon, Prime) and 512 (MAG).

7.0.0.4 Hardware.

All experiments were conducted on a Linux server equipped with an AMD EPYC 9575F CPU (16 cores), 128 GB of RAM, and four NVIDIA RTX PRO 6000 Blackwell GPUs (96 GB VRAM each).

8 Prompts↩︎

Section 3.1 describes the four-module structure of the Stage-1 plan-generation prompt (role, KG schema, plan-structure definition, fusion-control block) and the dataset-specific extensions layered on top. This appendix reproduces the runtime prompts verbatim. Each prompt is built by concatenating (a) a dataset-specific static system prompt body, (b) the shared fusion-control block (appended by _fusion_system_prompt(); the literal heading inside is ## Fusion overlay allocator), and (c) a per-query user message whose preamble differs slightly per dataset but whose final risk-level paragraph is shared verbatim. The two truly shared pieces are listed once below; the dataset-specific parts then follow.

8.1 Common building blocks↩︎

The two pieces below are identical across all three datasets. Everything else (role description, schema, examples, user-message preamble) differs per dataset and is reproduced verbatim in Appendices 8.2–8.4.

8.1.0.1 Fusion-control block (appended to every system prompt).

8.1.0.2 risk-level addendum (appended to every per-query user message).

8.2 Amazon↩︎

The Amazon Stage-1 plan prompt is composed of the static body below plus the fusion-control block from Appendix 8.1 appended at runtime.

8.2.0.1 Amazon-specific schema extensions.

Amazon extends the common plan schema (Section 3.1) with a top-level retrieval_mode field that classifies how strongly the graph branch should engage for a given query, taking one of four values described below. This reflects Amazon’s text-heaviness (textual \(>\) relational) relative to MAG and Prime: the planner needs an explicit way to declare “no graph entity anchors apply” or “use product-product co-occurrence edges”.

The four retrieval_mode values span a spectrum of graph engagement. doc_search is the degenerate case where the query has no named entity to anchor on; the planner falls back to a single doc-mode anchor with the query text, zero hops, and a dense rescore over the full product corpus — effectively pure dense retrieval, which suffices on Amazon since its product fields already carry most of the signal. graph_filter_doc is the canonical hybrid: a name-mode brand/category/color anchor plus a hop to T plus a non-empty relevance_text (the worked example in Section 3.1 is of this shape), analogous to what the MAG and Prime planners do implicitly. graph_expand exploits Amazon’s product-behaviour edges (ALSO_BUY, ALSO_VIEW) to expand a seed product into related items — this is the natural mode for “similar to / bought with \(X\)” queries and is the only mode without a direct analogue in the MAG / Prime prompts (whose graphs lack analogous user-behaviour edges). graph_strict is, schematically, graph_filter_doc with relevance_text set to empty, asserting that the graph hop alone is restrictive enough; in practice our planner never selects it and we keep it in the schema for completeness. The realised distribution on the Amazon test split (1,642 queries) is \(44.2\%\) doc_search, \(33.6\%\) graph_filter_doc, \(21.5\%\) graph_expand, \(0\%\) graph_strict, and \(0.7\%\) skip (an emergency fallback emitted when the planner cannot produce a usable plan; treated as risk_level=no_trade downstream).

8.2.0.2 System prompt (static body).

8.2.0.3 Per-query user message.

(followed by the risk-level addendum from Appendix 8.1.)

8.3 MAG↩︎

The MAG Stage-1 plan prompt is composed of the static body below plus the fusion-control block from Appendix 8.1.

8.3.0.1 System prompt (static body).

8.3.0.2 Per-query user message.

(followed by the risk-level addendum from Appendix 8.1.)

8.4 Prime↩︎

The Prime Stage-1 plan prompt is composed of the static header below, 19 worked-example (query, plan) pairs appended at module load time, and the fusion-control block from Appendix 8.1.

8.4.0.1 System prompt (static header).

8.4.0.2 19 worked examples (appended to the system prompt).

The 19 examples cover 19 distinct metapath templates from STaRK Appendix A.4 (template ids 2, 3, 4, 6–8, 11–13, 15, 17, 18, 21–23, 25–28). Each query text is a real STaRK PrimeKG training query (each shipped with a qid); the plans are hand-curated and verified to retrieve the gold answer in the top-10. We show one demo in full below; the query texts of the remaining 18 are listed after.

Query texts of the remaining 18 demos:

8.4.0.3 Per-query user message.

(followed by the risk-level addendum from Appendix 8.1.)

8.5 Stage-3 reranker scoring prompts↩︎

The Stage-3 reranker (Section 3.3; concrete checkpoint and LoRA configuration in Appendix 7) scores each (query, candidate) pair using a three-turn chat: a per-dataset system instruction, the user query, and the candidate’s serialized node document. The model outputs a single binary yes/no token; we take the softmax probability of yes as the relevance score. The three system instructions are:

8.5.0.1 Amazon.

8.5.0.2 MAG.

8.5.0.3 Prime.

8.6 Stage-3 candidate serialization format↩︎

Each candidate node from the Stage-2 top-100 is serialized into a plain key/value-line document that becomes the third turn of the reranker chat (after the system instruction in Appendix 8.5 and the user query). The template, applied identically at training and inference time, is:

The text-field set is dataset-specific (name, details for MAG and Amazon; name, details, source for Prime); each field is independently truncated to max_text_field_tokens tokens (Appendix 7). Every 1-hop neighbor is grouped by relation type and capped at \(\texttt{max\_neighbors\_per\_relation}{=}10\) names per relation; we treat all SKB relations as undirected following STaRK and union the two storage directions before grouping. Names are taken from the neighbor’s name or title property.

For example, the MAG case-study gold (Section 5) is serialized roughly as:

The Amazon case-study gold:

The Prime case-study gold:

References↩︎