Organizations: Independent Researcher San Jose, CA, USA · The Pennsylvania State University University Park, PA, USA · Independent Researcher Sunnyvale, CA, USA
Retrieval-Augmented Generation (RAG) is increasingly served across geo-distributed cloud and edge infrastructures, where wide-area latency, cross-region egress cost, and data-residency rules compete with retrieval quality. Conventional pipelines rank by semantic similarity alone and ignore where content lives, inflating tail latency and cost. We formalize the Geo-RAG Selection Problem (GRaSP), a drop-in re-scoring layer that decays relevance by latency and adds an optional cost penalty under a cardinality budget and per-region caps, with no retraining. We first settle its complexity: the base formulation is a linear objective over a partition matroid, solved optimally by an O(N log N) greedy algorithm, rather than NP-hard as a knapsack framing suggests, with hardness entering only under an additive egress budget. On a five-node CloudLab testbed emulating a four-region WAN over the Natural Questions corpus (2.68M passages), GRaSP's benefit is placement-dependent: under uniform placement it cuts fetch latency at negligible quality cost; under topical (residency-like) placement it traces a recall-latency Pareto frontier that dominates relevance-only, nearest-k, and a latency-budgeted baseline. At a moderate latency setting, GRaSP lowers P90 fetch latency by 41% while retaining 78% of relevance-only's recall, with sub-millisecond selection overhead, stable to 200 queries/s. Findings generalize across four public BEIR benchmarks. In end-to-end question answering, GRaSP reduces context-fetch latency by 43% while remaining within 0.062 absolute EM of relevance-only retrieval.
Figures & tables
γq
Policy
Gap
Lat. (ms)
Cost
Recall
nDCG
0.003
Rel-only
0.92
122.1
0.102
0.534
0.400
0.003
Nearest- k
0.76
42.3
0.044
0.292
0.229
0.003
GRaSP-greedy
1.00
97.4
0.084
0.506
0.384
0.003
GRaSP-rat.
1.00
102.3
0.088
0.516
0.391
0.010
Rel-only
0.85
122.1
0.102
0.534
0.400
0.010
Nearest- k
0.87
42.3
0.044
0.292
0.229
Table 1. Topical placement, β=0 , k=5 . Optimality gap vs. OPT, expected worst-case fetch latency (ms), egress cost ( μ USD per query), recall@5, and nDCG@5. Values are means over 3,452 queries. (Representative rows; full sweep in the artifact.)
Figure 1. Recall@5 versus expected worst-case fetch latency as γq varies ( β=0 ). Left: uniform placement—GRaSP reduces latency at negligible recall cost. Right: topical placement—GRaSP traces a Pareto frontier between retrieval quality and latency.
L (ms)
Recall
nDCG
Mean max-RTT (ms)
1
0.000
0.000
0.0
90
0.260
0.198
52.4
115
0.432
0.324
79.8
210
0.534
0.400
122.1
Table 2. Rel@LatencyCap baseline on NQ topical placement: discard candidates with rtt>L , then select the highest-relevance feasible set.
Figure 2. Measured end-to-end retrieval latency (CDF, log- x ) under topical placement at 20 queries/s. Increasing γq shifts GRaSP’s latency distribution left of relevance-only.
Figure 3. Replication improves GRaSP’s recall–latency frontier under topical placement. Higher replication factors move the frontier toward the uniform-placement regime.
Setting
Policy
Gap
Lat. (ms)
Recall
Uncapped
Rel-only
0.85
122.1
0.534
Uncapped
GRaSP-greedy
1.00
69.5
0.419
Cr=2
Rel-only
0.97
175.3
0.392
Cr=2
GRaSP-greedy
1.00
163.3
0.374
Table 3. Effect of a residency cap ( Cr=2 ) under topical placement, γq=0.01 , β=0 . GRaSP tracks the exact optimum.
QPS
Policy
P50
P90
P99
Sel. ( μ s)
20
Rel-only
130.5
228.3
247.0
125
20
GRaSP-greedy
105.1
135.4
248.4
425
50
Rel-only
131.3
228.4
426.9
125
50
GRaSP-greedy
105.8
139.7
290.9
426
100
Rel-only
132.9
229.7
433.4
118
100
GRaSP-greedy
106.6
146.7
425.8
419
Table 4. Load stability under topical placement ( γq=0.01 , β=0 ). End-to-end latency percentiles (ms) and selection overhead ( μ s), 1,000 queries per point.
β
Latency (ms)
Cost ( μ USD)
Recall
0.0
69.5
0.095
0.419
0.5
70.2
0.051
0.339
1.0
70.8
0.036
0.279
2.0
74.3
0.024
0.210
Table 5. Decorrelated pricing (near region most expensive), topical placement, γq=0.01 . Increasing β trades latency and relevance for lower egress cost.
Figure 4. Frontier robustness to relevance normalization under topical placement. Min–max and softmax normalization shift individual operating points but preserve the overall recall–latency trade-off.
Figure 5. Under decorrelated pricing ( γq=0.01 ), increasing β reduces egress cost while latency rises. The latency and cost knobs therefore control distinct trade-offs.
Dataset
Policy
Gap
Lat. (ms)
Recall
nDCG
NQ
Rel-only
0.85
122.1
0.534
0.400
GRaSP-greedy
1.00
69.5
0.419
0.323
Nearest- k
0.87
42.3
0.292
0.229
SciFact
Rel-only
0.82
119.6
0.738
0.629
GRaSP-greedy
1.00
61.6
0.560
0.489
Nearest- k
0.85
13.3
0.276
0.240
Table 6. Generalization across datasets at γq=0.01 , β=0 , topical placement. GRaSP-greedy matches the exact optimum on every dataset.
Retrieval-augmented generation (RAG) faces a fundamental three-way tension: deeper retrieval improves factual grounding but inflates token costs and end-to-end latency. Static retrieval configurations cannot resolve this tension across heterogeneous query workloads -- simple definitional queries waste budget on unnecessary context, while complex analytical prompts are underserved by shallow retrieval. This paper introduces Cost-Aware RAG (CA-RAG), a per-query routing framework that selects from a discrete catalog of strategy bundles -- each coupling a retrieval depth (from retrieval-free direct inference to top-k=10 dense retrieval) with a fixed generation profile -- by maximizing a scalar utility that linearly combines an estimated quality prior with normalized penalties for predicted latency and total billed tokens. CA-RAG is implemented with FAISS-backed dense retrieval and OpenAI chat/embedding APIs, and evaluated on a 28-query benchmark spanning four bundles. The router dynamically exercises all bundles, achieving 26% fewer billed tokens than always-heavy retrieval and 34% lower mean latency than always-direct inference while maintaining equivalent answer quality. Per-query delta analysis reveals that savings are non-uniform and concentrated in simpler queries, motivating complexity-aware guardrails. Sensitivity analysis confirms that the same bundle catalog supports multiple cost-latency-quality operating points through weight adjustment alone. All results are generated directly from logged CSV artifacts for full reproducibility. CA-RAG provides a transparent, auditable foundation for cost-conscious LLM deployments.
Retrieval-augmented generation (RAG) typically treats context selection as ranking chunks against a single query embedding. This assumption breaks down for complex queries, such as multi-hop or ambiguous questions, where top-k selection tends to over-cover one semantic aspect while ignoring critical sub-questions. We propose GeoRAG, which recasts context selection as Information Demand Coverage Optimization. GeoRAG builds a multi-dimensional demand distribution through diverse sub-query generation and reverse-validation weighting, then selects context by minimizing the Sinkhorn-Wasserstein distance between this demand distribution and the coverage of the selected set. The resulting demand-weighted facility-location objective is monotone submodular, giving a 1−1/e greedy guarantee, which we approximate with a Sinkhorn-based marginal-gain surrogate. The method is unsupervised, training-free, and retrieval-agnostic. We further show that single-point, query-proximity scorers cannot cover multi-modal demands, exposing a structural limit of ranking-based selection. On six open-domain QA benchmarks, GeoRAG improves exact match (EM) by +6.5 to +7.5 points over top-k truncation (up to +9.7 on HotpotQA and ASQA) and outperforms strong baselines including MMR, DPP, BGE-Reranker, SMART-RAG, and AdaGReS, with stable gains across context budgets and sub-query generators.
Bingxue Zhang, Jianying Jia, Feida Zhu
University of Shanghai for Science and Technology, Shanghai, China · Singapore Management University, Singapore
Retrieval-Augmented Generation (RAG) mitigates large language models (LLMs) hallucinations, yet conventional dense retrieval struggles with the complex reasoning paths of multi-hop question answering (QA). Graph-based RAG captures multi-step relationships but suffers from severe semantic drift and high online latency due to noisy global graph traversals. Thus, we propose ISO-RAG (ISOperimetric Retrieval-Augmented Generation), a geometry-aware RAG framework. By projecting the underlying knowledge graph into a hyperbolic Poincare ball to precompute node-wise isoperimetric profiles, ISO-RAG prunes spurious edges during retrieval, restricting the search space to a strictly localized subgraph. This topological purification regulates Personalized PageRank (PPR) diffusion driving the retrieval process, ensuring exact and low-latency convergence. Experiments on multi-hop QA benchmarks demonstrate that ISO-RAG outperforms state-of-the-art baselines by average absolute gains of 10.0% in retrieval recall and 4.3% in downstream exact match, achieving a superior accuracy-efficiency trade-off by fundamentally eliminating the latency bottleneck of global traversals. Our source code is available at https://github.com/ZaiizaiZHANG/ISO-RAG.
Siyuan Zhang, Hanchen Wang, Dong Wen +2
University of Technology Sydney · University of New South Wales