STAR: Semantic-Tuned and Tail-Adaptive Retriever for Graph-Augmented Generation

Shuai Li; Chen Huang; Duanyu Feng; Wenqiang Lei; See-Kiong Ng

cs.IRApr 11, 2026

STAR: Semantic-Tuned and Tail-Adaptive Retriever for Graph-Augmented Generation

Authors: Shuai Li, Chen Huang, Duanyu Feng, Wenqiang Lei, See-Kiong Ng

Abstract

To augment Large Language Models (LLMs) for multi-hop question answering, a mainstream solution within Graph Retrieval Augmented Generation (GraphRAG) leverages lightweight retrievers to efficiently extract information from a given Knowledge Graph (KG). However, existing methods often overlook the inherent challenge of sparse semantic information in graphs. Specifically, our experiments reveal that these methods produce biased retrieval Semantic Shortcut Bias and Long-Tail Path Bias, leading to inadequate semantic modeling and limited GraphRAG effectiveness. To address these issues, we propose STAR, a semantic-tuned and tail-adaptive retriever for GraphRAG. STAR integrates two key learning paradigms: token-level interaction learning and path-weighted contrastive learning. The former employs a cross-attention architecture and a hard path mining mechanism to jointly model the query and path, thereby mitigating the Semantic Shortcut Bias. The latter introduces a tailored contrastive learning objective that utilizes tail-adaptive path weighting, designed to optimize the training process and ease the Long-Tail Path Bias. Extensive experiments demonstrate that STAR consistently outperforms baselines, achieving average retrieval performance gains of 1.8% and LLM QA performance improvements of 2.2% across all benchmark datasets. Our code is available at https://anonymous.4open.science/r/STAR-C583.

Figures & tables

Figure 1. Illustrations of semantic shortcut, where a retriever prefers a semantically similar but incorrect relation.

Figure 2. Long-tail distribution of path frequencies.

Figure 3. Analysis on Semantic Shortcut (Top) and Long-Tail Path Bias (Bottom) on correct and incorrect retrieval subsets. X-axis represents the ratio value (%).

Figure 4. Overview of our STAR, featuring token-level interaction learning and path-weighted contrastive learning to ease the two biases, respectively. Our cross-attentive architecture jointly models query-path pairs to capture fine-grained semantic interactions, optimized with a contrastive loss on hard-mined path samples. Simultaneously, our path-weighting scheme amplifies the learning signal from infrequent paths within the final loss $\mathcal{L}_{\text{STAR}}$ , to ensure robust performance across the entire data distribution. During inference, the trained STAR model guides a beam search to retrieve paths for final answer generation.

Dataset	#Train	#Dev	#Test	Max Hop	1-hop	2-hop	$\geq$ 3-hop
WebQSP	2,543	283	1,628	2	65.49%	34.51%	-
CWQ	26,257	1,382	3,531	4	40.91%	38.34%	20.75%
GrailQA	3,800	200	1,000	4	68.93%	25.82%	5.25%

Table 1. Statistics, distribution of path depths, and hops.

Setting	Model	WebQSP			CWQ			GrailQA
		Hits@1 (%)	F1 (%)	RT	Hits@1 (%)	F1 (%)	RT	Hits@1 (%)	F1 (%)	RT
LLM without KG	Qwen2.5-72B	58.1	39.4	3.5	32.4	27.3	4.3	24.3	18.3	4.5
	Llama3.3-70B	62.5	43.2	2.8	39.5	34.1	3.6	26.3	20.3	4.0
	DeepSeek-R1-70B	75.2	59.0	16.3	55.3	50.3	17.2	41.9	34.2	17.8
LLM-centric Retriever	RoG	87.1	71.6	1.6	83.3	64.8	1.2	73.1	63.8	2.3
	Graph CoT	85.3	73.5	123.3	66.1	61.4	513.6	78.3	73.1	168.4

Table 2. Performance comparison with different baselines on the benchmark datasets. STAR consistently outperforms all baselines across various benchmarks in retrieval performance and often demonstrates superior retrieval efficiency.

Backbone	Retriever Type	Error	Shortcut	Long-tail	Union
WebQSP
SimCSE	Similarity-based	14.8	6.8 (45.8)	7.6 (51.6)	10.4 (70.1)
	Cross-Attentive	12.6	4.6 (36.7)	6.7 (53.3)	8.4 (66.7)
	w/ HPM	12.2	3.8 (31.3)	6.5 (49.1)	7.9 (66.2)
TweetNLP	Similarity-based	16.4	4.9 (29.9)	7.0 (42.7)	9.5 (58.2)
	Cross-Attentive	12.4	4.5 (36.2)	6.3 (50.8)	7.6 (63.3)

Table 3. Ablation analysis (%) on STAR’s token-level interaction learning to mitigate Semantic Shortcut Bias. Error percentages are shown outside parentheses, with the relative contribution to total errors inside.

Objective	Error	Shortcut	Long-tail	Union
WebQSP
Contrastive Loss	12.6	4.6 (36.7)	6.7 (53.3)	8.4 (66.7)
w/ Weight	11.9	4.0 (33.3)	5.8 (49.1)	7.9 (66.2)
STAR	11.3	3.7 (32.7)	5.8 (51.1)	7.4 (65.1)
CWQ
Contrastive Loss	14.8	7.0 (47.2)	3.8 (25.9)	10.0 (67.6)

Table 4. Ablation analysis (%) on STAR’s path-weighted contrastive learning. Error percentages are shown outside parentheses, with the relative contribution to total errors inside.

Model	WebQSP	CWQ	GrailQA
LLaMA3.3-70B	75.3 (+35.9)	69.7 (+42.4)	77.2 (+58.9)
Qwen2.5-72B	72.3 (+29.1)	68.8 (+34.7)	76.7 (+56.4)
DeepSeek-R1-70B	86.3 (+27.3)	70.0 (+19.7)	78.2 (+44.0)

Table 5. F1 (%) performance of STAR with different LLM answer generators. Performance improvements over their respective counterparts in Table 2 are highlighted in brackets.

Dataset	$K$ =1	$K$ =3	$K$ =5	$K$ =7
WebQSP	88.7	93.9	95.0	95.2
CWQ	86.4	87.3	89.0	89.4
GrailQA	80.1	86.5	89.8	89.8

Table 6. Hits@1 (%) of STAR under different top-

K

settings.

Figure 5. Cross-Attention Visualization. Darker color indicates stronger attention. STAR assigns the highest score to the logically correct path place_of_death by aligning logically relevant tokens such as town and assassinated .

Explore similar work

Efficient Retrieval-Augmented Generation via Token Co-occurrence Graphs
Jun 29, 2026Gianluca Bonifazi, Christopher Buratti, Michele Marchetti +5Multi-Hop QA Graph Retrieval-Augmented Generation
aUniversità Politecnica delle Marche, Ancona, Italy · bUniversità di Modena e Reggio Emilia, Modena, Italy
S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering
Mar 5, 2026Rong Fu, Yemin Wang, Tianxiang Xu +5Knowledge Graph Question Answering Multi-Hop QA
University of Macau · Xiamen University · Peking University +3
GraphRAG-Router: Learning Cost-Efficient Routing over GraphRAGs and LLMs with Reinforcement Learning
Mar 31, 2026Dongzhe Fan, Chuanhao Ji, Zimu Wang +2LLM Routing Graph Retrieval-Augmented Generation
Department of Computer Science, New York University (Shanghai) · Department of Computer Science, University of Liverpool

Jun 29, 2026J/K move · Enter open · S save

Efficient Retrieval-Augmented Generation via Token Co-occurrence Graphs

Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano+4

aUniversità Politecnica delle Marche, Ancona, Italy · bUniversità di Modena e Reggio Emilia, Modena, Italy

Multi-Hop QA Graph Retrieval-Augmented Generation Graph-Based Retrieval

Open paper AskPDF arXiv

Retrieval-Augmented Generation (RAG) mitigates hallucinations in Large Language Models (LLMs) by grounding the generation process on external knowledge. However, standard RAG approaches struggle with multi-hop reasoning. While recent graph-based RAG methods improve the retrieval of interconnected chunks, they often rely on computationally expensive and error-prone LLM-based extraction pipelines. To address these issues, we propose TIGRAG (Token-Induced GraphRAG), an efficient graph-augmented RAG framework based on a token co-occurrence Knowledge Graph. TIGRAG directly models topological relationships between tokens using sliding-window co-occurrence statistics, thus enabling scalable graph construction. During inference, it combines graph-based semantic expansion and neural reranking to retrieve interconnected evidence for multi-hop reasoning. Specifically, it introduces an iterative entity-driven retrieval strategy that progressively expands the query using bridging entities extracted from previously retrieved contexts. We evaluated TIGRAG on three widely adopted multi-hop Question Answering (QA) benchmarks. Experimental results demonstrated that our framework consistently outperforms dense retrieval and graph-based RAG methods in both retrieval and downstream QA tasks, while substantially reducing indexing time, inference latency, and prompt footprint.

Abstract

Explore similar work

Efficient Retrieval-Augmented Generation via Token Co-occurrence Graphs

S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering

GraphRAG-Router: Learning Cost-Efficient Routing over GraphRAGs and LLMs with Reinforcement Learning