GRASP: Plan-Guided Graph Retrieval with Adaptive Fusion and Reranking on Semi-Structured Knowledge Bases

The gist: GRASP is a three-stage SKB retrieval framework that unifies plan-based graph retrieval, plan-conditioned fusion with a dense retriever, and a fine-tuned reranker over the fused candidates.

How it works

GRASP consists of three stages to address the limitations of prior hybrid systems in semi-structured knowledge base (SKB) retrieval First, Stage 1 produces a graph plan, executes it against the SKB to retrieve candidates and rescored with a dense encoder. This stage involves plan generation by an LLM converting the query into a structured plan, execution against the graph database yielding candidates and anchor scores, and dense rescoring using residual textual information. The plan generation prompt includes 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 three core slots anchors, hops, and target with residual text constraints, and a fusion-control block asking the planner to self-report a risk level.

Stage 1: Plan generation, execution, and dense rescoring

The plan execution involves three steps: Anchor linking where 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, followed by Plan compilation where the plan is compiled into a single Cypher query that expands anchors 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. Finally, Dense rescoring refines those scores by adding the cosine similarity between the embedding of relevance text and the candidate’s document embedding when relevance text is not empty.

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

In Stage 2, GRASP runs 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: Static RRF uses a global graph weight w∈[0, 1] and constant k, while Dynamic RRF computes the graph weight per query q from the planner’s (n cand, risk level) outputs. The dynamic weight is calculated as wˆgraph(q) = wbucket[b(q)] · mrisk[r(q)], where b(q)∈[[1, 10], [11, 50], [51, 100], [101, 500], >500] is the n cand bucket and r(q) is the risk level label.

Stage 3: Reranking and final fusion

In Stage 3, GRASP reranks the Stage-2 ranking with a fine-tuned LLM-based reranker and fuses it with the upstream ranking. The candidate pool for this stage consists of the top-100 candidates from the Stage-2 fused list, each 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. The fine-tuned reranker is trained with LoRA adapters under a listwise softmax loss to score each candidate using a three-turn chat involving a per-dataset system instruction, the user query, and the candidate’s serialized node document.

Results and Contributions

GRASP substantially advances the state of the art on every metric across the three STaRK benchmarks, lifting average Hit@1 from 62.0 to 73.9. The method achieves the best result on every reported metric across all three datasets. Contributions include (1) a simple but effective framework GRASP that substantially advances the previous state-of-the-art on SKB retrieval, (2) showing that results of graph and dense retrieval are complementary and can be fused to boost performance, and (3) GRASP is robust to its hyperparameter choices. The fusion with mFAR boosts Recall@20 sharply on every dataset, with gains ranging from +17.8 on Amazon to +22.2 on Prime.

Discussion and Sensitivity

The performance of GRASP is stable across reasonable choices of hyperparameters, making it easy to deploy without per-dataset hyperparameter expertise. The contribution of each stage varies by dataset: Fusion contributes the most on Amazon because the dataset is text-heavy and the graph branch alone is weak, while the graph branch contributes the most on MAG whose citation structure already provides a strong retrieval signal. Furthermore, performance improves as more stages are added, confirming that each stage contributes positively. The final analysis shows that the fused candidate pool benefits the trained reranker by providing high-quality hard negatives.

Limitations

Limitations include generalization beyond STaRK, as experiments cover only three SKB benchmarks sharing the STaRK construction protocol and a common English schema. Interpretability is limited regarding why a given top-1 prediction emerges from the interaction of all three stages. Dependence on a strong instruction-tuned LLM for plan generation means that if the schema or queries are too far from the LLM’s pretraining distribution, the planner may emit invalid or low-quality plans. The paper also notes that recovery from such failures, like retries or self-critique, was not explored.

Implementation Details

The implementation details specify the models used for each stage, such as Qwen3-Embedding-4B on Amazon and MAG, SapBERT on Prime as dense encoders. The SKB is hosted in Neo4j, and per-node embeddings are pre-computed at indexing time. The reranker is fine-tuned using LoRA adapters with rank r = 32 and scaling α = 64. Hardware for experiments included an AMD EPYC 9575F CPU and four NVIDIA RTX PRO 6000 Blackwell GPUs.

Conclusion

GRASP is a three-stage retrieval framework that converts the query into a structured plan, executes it 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. GRASP sets a new state of the art on every metric across three STaRK datasets, with average Hit@1 reaching 73.9 versus 62.0 for the strongest prior. Per-component ablations confirm 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.

Appendix Details

The appendix provides detailed prompts for Stage 1 plan generation, including dataset-specific schema extensions and retrieval modes like graph filter doc for Amazon. It also details the serialization format for Stage 3 candidate documents, which includes node type, text fields, and relation groupings. The system instructions for the Stage-3 reranker are dataset-specific, judging relevance based on whether it is a question about Amazon products or entities in an academic knowledge graph. The validation query distributions over n cand bucket × risk level provide the basis for dynamic RRF weight computation. The comparison of static and dynamic RRF strategies on the validation set shows that the choice of fusion mode is not a sensitive lever once the underlying branches are in place <ref:2605.

1. Bold header: Plan-Conditioned Graph Retrieval

This allows for a simple but effective framework GRASP that substantially advances the previous state-of-the-art on SKB retrieval by converting a query into a structured plan, which is executed against a graph database to retrieve candidates and rescored with a dense encoder.

2. Bold header: Plan-Conditioned Fusion

This improves performance by integrating structural and textual signals through plan-conditioned fusion with a dense retriever, specifically using dynamic RRF where the graph weight is computed per query from the planner’s outputs.

3. Bold header: Fine-Tuned Reranking

The system can lift the fused candidate list to top-1 by employing a fine-tuned LLM-based reranker that exploits high-quality hard negatives from the fused pool, recovering precision lost in earlier stages.