GRaSP is a latency‑aware optimization for Retrieval‑Augmented Generation (RAG) deployed across geo‑distributed cloud and edge infrastructures. It adds a drop‑in re‑scoring layer after the retrieval stage, decaying relevance scores by network latency and optionally penalizing egress cost while respecting per‑region cardinality caps and an overall budget, all without retraining the underlying model.
We first characterize the problem’s complexity: with only cardinality and per‑region caps, the objective is a linear function over a partition matroid and can be solved optimally by an O(N log N) greedy algorithm; hardness appears only when an additive egress budget is introduced, turning the problem into an NP‑hard knapsack variant.
Experiments were conducted on a five‑node CloudLab testbed emulating a four‑region WAN, using the Natural Questions corpus (2.68 M passages). Results show that GRaSP’s gains depend on document placement: under uniform placement it cuts fetch latency with negligible recall loss, while under topical (residency‑like) placement it traces a recall‑latency Pareto frontier that dominates relevance‑only ranking, nearest‑k, and a latency‑budget baseline.
At a moderate latency setting, P90 fetch latency drops 41% while retaining 78% of the relevance‑only recall; the selection overhead stays sub‑millisecond and the system remains stable up to 200 queries / s. The same trends hold across four public BEIR benchmarks. In an end‑to‑end QA scenario, GRaSP reduces context‑fetch latency by 43% with only a 0.062 absolute drop in Exact Match.
Overall, GRaSP effectively mitigates cross‑region latency and cost while preserving retrieval quality, making it a practical plug‑and‑play enhancement for existing RAG pipelines. Review