GRaSP: Latency-Aware Optimization for Geo-Distributed Retrieval-Augmented Generation

Hardik Ruparel; Raj Kumar Pandey; Pramod Kumar

cs.IROct 17, 2026

GRaSP: Latency-Aware Optimization for Geo-Distributed Retrieval-Augmented Generation

Authors: Hardik Ruparel, Raj Kumar Pandey, Pramod Kumar

Organizations: Independent Researcher San Jose, CA, USA · The Pennsylvania State University University Park, PA, USA · Independent Researcher Sunnyvale, CA, USA

Abstract

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

$\gamma_{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,

\beta{=}0

k{=}5

. Optimality gap vs. OPT, expected worst-case fetch latency (ms), egress cost (

\mu

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

\gamma_{q}

varies (

\beta{=}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

\mathrm{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

\gamma_{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
$C_{r}{=}2$	Rel-only	0.97	175.3	0.392
$C_{r}{=}2$	GRaSP-greedy	1.00	163.3	0.374

Table 3. Effect of a residency cap (

C_{r}{=}2

) under topical placement,

\gamma_{q}{=}0.01

\beta{=}0

. GRaSP tracks the exact optimum.

QPS	Policy	P50	P90	P99	Sel. ( $\mu$ 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 (

\gamma_{q}{=}0.01

\beta{=}0

). End-to-end latency percentiles (ms) and selection overhead (

\mu

s), 1,000 queries per point.

$\beta$	Latency (ms)	Cost ( $\mu$ 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,

\gamma_{q}{=}0.01

. Increasing

\beta

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 (

\gamma_{q}{=}0.01

), increasing

\beta

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

\gamma_{q}{=}0.01

\beta{=}0

, topical placement. GRaSP-greedy matches the exact optimum on every dataset.

Policy	EM	F1	Context lat. (ms)
Relevance-only	0.320	0.415	122.1
GRaSP-greedy	0.258	0.362	69.5
Nearest- $k$	0.180	0.257	42.3

Table 7. End-task NQ answer quality (500-query subset,

\gamma_{q}{=}0.01

\beta{=}0

, topical placement). GRaSP preserves most answer quality while reducing context-fetch latency.

Retrieval-Augmented Generation

Retrieval-augmented generation connects language models to external knowledge so answers can use current, domain-specific evidence.

See all 796 papers

Cost-Aware Query Routing in RAG: Empirical Analysis of Retrieval Depth Tradeoffs
Mar 26, 2026Sanjay MishraRetrieval-Augmented Generation Adaptive RAG
Raleigh, NC, USA
Covering the Unseen: Information Demand Coverage Optimization for Retrieval-Augmented Generation
Jun 28, 2026Bingxue Zhang, Jianying Jia, Feida ZhuMulti-Hop QA Retrieval-Augmented Generation
University of Shanghai for Science and Technology, Shanghai, China · Singapore Management University, Singapore
ISO-RAG: Isoperimetric Noise Control for Retrieval-Augmented Generation
Sep 1, 2026Siyuan Zhang, Hanchen Wang, Dong Wen +2Multi-Hop QA Graph Retrieval-Augmented Generation
University of Technology Sydney · University of New South Wales

Mar 26, 2026J/K move · Enter open · S save

Cost-Aware Query Routing in RAG: Empirical Analysis of Retrieval Depth Tradeoffs

Sanjay Mishra

Raleigh, NC, USA

Retrieval-Augmented Generation Adaptive RAG Cost-Aware Inference LLM Routing RAG Evaluation

Open paper AskPDF arXiv

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.

Abstract

Retrieval-Augmented Generation

Explore similar work

Cost-Aware Query Routing in RAG: Empirical Analysis of Retrieval Depth Tradeoffs

Covering the Unseen: Information Demand Coverage Optimization for Retrieval-Augmented Generation

ISO-RAG: Isoperimetric Noise Control for Retrieval-Augmented Generation