S kew R oute: Training-Free LLM Routing for Knowledge Graph Retrieval-Augmented Generation via Score Skewness of Retrieved Context (2025)

Abstract: Large language models excel at many tasks but often incur high inference costs during deployment. To mitigate hallucination, many systems use a knowledge graph to enhance retrieval-augmented generation (KG-RAG). However, the large amount of retrieved knowledge contexts increase these inference costs further. A promising solution to balance performance and cost is LLM routing, which directs simple queries to smaller LLMs and complex ones to larger LLMs. However, no dedicated routing methods currently exist for RAG, and existing training-based routers face challenges scaling to this domain due to the need for extensive training data. We observe that the score distributions produced by the retrieval scorer strongly correlate with query difficulty. Based on this, we propose an extremely simple yet effective routing framework, the first specifically designed for KG-RAG that efficiently balances performance and cost in a plug-and-play manner. It delivers over 3x higher routing effectiveness while reducing runtime to less than 0.001x compared to existing methods. Our code is available at https://github.com/hrwang00/SkewRoute.

## introduction large language models (llms) @xcite @xcite exhibit remarkable capabilities across a wide range of tasks. however, llms often hallucinate due to a lack of up-to-date or domain-specific knowledge @xcite . to mitigate this, llms are often augmented with retrieved external knowledge @xcite @xcite during application. notably, many methods use externally structured knowledge graphs (kgs) as external bases, retrieving query-relevant context to enhance subse-* equal contribution. given the autoregressive nature of llms, inference costs are directly proportional to the number of tokens @xcite . while kg-rag mitigates hallucinations and improves generation quality, it dramatically expands input tokens due to the increased retrieved context. as shown in figure 2a , answering a question directly with an llm requires 62 tokens per question. however, retrieving 100 triples using subgraphrag increases this to 1873 tokens per question, resulting in an over 30x increase in input token consumption. this significant overhead hinders practical llm application. to reduce llm inference costs in applications, recent studies have focused on llm routing @xcite @xcite , routing simple questions to smaller llms and complex questions to larger llms. this is primarily because the performance benefits of increased model scale exhibit diminishing returns; for example, qwen2.5-14b-instruct incurs less than twice the inference cost of qwen2.5-7b-instruct while delivering a 7.45% performance increase. in contrast, qwen2.5-72b-instruct requires almost 7x the inference cost of qwen2.5-14b but only achieves a 2.12% improvement, as illustrated in figure 2b . however, while recent routing methods have been explored in direct llm qa applications, their application and extensibility to rag domains is limited, primarily due to two reasons: these challenges highlight the significant hur-dles of effective routing llms in rag scenarios, which raises a critical question: can we develop a training-free routing method, specifically tailored for rag, that routes by focusing target reasoning on external knowledge sources? by analyzing the score distribution of retrieved contexts in kg-rag, we surprisingly find significant differences for different queries, as shown in figure 1 . the score distribution for some queries exhibits high skewness, characterized by powerlaw behavior,which is widely observed across many fields. foot_0 @xcite @xcite . a handful of contexts dominate with high scores, leaving a long tail of many lower-scoring ones. this indicates that only a few knowledge contexts are highly relevant to the query, while the majority are not. however, other queries show a distinctly different, low skewness distribution, where a substantial portion of the contexts exhibit high relevance scores. this skewness variation is strongly correlated with the difficulty of reasoning over external knowledge. for instance, simple questions may require only simple matching within a single context, while difficult questions often demand multi-hop reasoning across multiple knowledge contexts. thus, the varying skewness of the score distribution may serve as an indicator of query difficulty. inspired by the score skewness of retrieved information in kg-rag, we first investigate the correlation between skewness patterns and query difficulty. building on this insight, we propose the first training-free routing framework to address the existing routing challenges in kg-rag scenarios. this framework employs a lightweight and efficient workflow, as shown in figure 1 , that leverages the skewness pattern of the retrieved context scores to dynamically route queries. simpler queries are assigned to smaller llms, while more difficult queries are routed to larger llms, effectively balancing performance and cost. our main contributions are summarized as follows: ## preliminaries power-law. power-law @xcite , ubiquitous in nature, reveals an inverse relationship between scores and their descending ranks: s(n) = c n α . in this formulation, n denotes the rank and s(n) is the corresponding score. in log-log space, logs(n) against log(n) approximates a straight line with slope -α. while in linear space, it appears as a few high scores followed by a long tail of lower ones. in kg-rag, we observe that for certain queries, the scores of retrieved contexts also follow this power-law behavior. kg-rag. rag integrates contexts retrieved from external knowledge bases to enhance llms. in kg-rag, the knowledge bases are kgs, and the retrieved contexts take the form of triples {τ = (h, r, t)}. existing research on kg-rag generally involves two stages: retrieval and generation. for example, the state-of-the-art kg-rag method, subgraphrag trains a scorer r to select a subset of triples @xmath0, τ 2 , . . . , τ k } by their scores @xmath1, s 2 , ..., s k } relevant to q from g in the retrieval phase. and then feeds q, an instruction i, and t to a generator g (typically an llm) to produce the final answer: g(i, t, q) → a, where @xmath2. knowledge graph question answering (kgqa) is often used to evaluate kg-rag, aiming to obtain answers from kgs given query q, where @xmath3. llm route. based on scale, llms are broadly categorized as larger llms and smaller ones. given a query @xmath4, a larger llm is formally represented as a function f l (i, t, q) = a, mapping the query q and retrieved information t to an answer a, while a smaller llm is denoted as f s (i, t, q) = a. larger llms deliver high quality with significant cost. in contrast, smaller llms are less capable but substantially reduce overhead. for queries that smaller llms fail but larger llms handle correctly, using the larger llms boosts performance. however, for queries both llms answer correctly, relying on the larger llms incurs a substantial extra cost. unlike previous works @xcite @xcite that train a binary classifier to route between smaller llms and larger llms, we design trainingfree router l on the scores w of retrieved contexts for given query q, l : @xmath5, f l }, where w is the space of possible w and θ is a threshold. the kg-rag method typically trains a scorer that assigns higher scores to contexts relevant to the query and lower scores to irrelevant ones. based on these scores, the top-k contexts are selected to enhance llm generation, making the quality of this selection directly affect the final answer quality. in reality, queries can be categorized as simple or difficult @xcite @xcite . simple queries often require only single-hop information matching within one knowledge context to find the answer, while difficult queries usually need multihop reasoning across multiple knowledge contexts. to explore this, we visualize the score distributions assigned by the scorer across different queries and find significant differences that strongly correlate with the query difficulty. figure 3 presents two typical examples of the top-100 context score distributions for different queries, showing clear and significant differences. power-law distribution is highly skewed with longtail. in figure 3a and figure 3c , the distribution exhibits power-law behavior and approximates a straight line at the loglog scale: only a few contexts are relevant to the question, while most score below 0.1 and are irrelevant. by contrast, figure 3b and figure 3d show lower skewness, with a large portion of contexts clearly relevant-100% contexts have scores above 0.1. this difference in skewness intuitively corresponds well with the query difficulty: difficult queries naturally require reasoning across more knowledge contexts, resulting in lower skewness. ## related works knowledge graph question answering (kgqa) serves as a crucial application for evaluating kg-rag, which requires precise answers from structured kgs. these kg-rag methods are primarily divided into two categories: decoupled retrieval methods and integrated retrieval methods based on whether llms dynamically participate in the retrieval process on kgs. the integrated retrieval methods @xcite @xcite exemplified by tog, enable the llms to interactively explore related entities and relations on kgs and perform reasoning based on the retrieved knowledge. however, this tight coupling requires frequent llm calls, leading to substantial inference overhead. the decoupled retrieval methods @xcite @xcite @xcite focus on distilling prior knowledge from kgs into llms. for instance, rog fine-tunes llms to generate relation paths as faithful plans that are then used to retrieve valid paths from kgs. however, this method incurs substantial computational expense due to finetuning and processing latency, which can amount to thousands of seconds per query. in contrast, subgraphrag, demonstrates superior effective and efficient results by integrating a lightweight multilayer perceptron (mlp) with structural and semantic information. accordingly, all our subsequent experiments are conducted based on it. ## conclusion in this paper, we present the first llm routing framework tailored for kg-rag in a plug-andplay manner. this is motivated by the observation that the skewness of retrieval score distributions naturally reflects query difficulty in reasoning over external knowledge, aligning well with the rag paradigm. by exploiting this skewness, our method dynamically routes queries among llms of different scales, achieving an effective trade-off between performance and cost. this simple yet robust solution also overcomes prior methods' dependence on costly training data and generalizes well across datasets and model sizes. extensive experiments validate the effectiveness of our method. we offer a new perspective for efficient rag deployment by reducing costs through llm routing. future work will focus on extending this training-free routing paradigm to broader rag settings, including textbased and multimodal scenarios.