CACHECOHERENT: FREQUENCY-ALIGNED DOCUMENT ORDERING FOR PREFIX-CACHE-EFFICIENT MULTI-TENANT RAG SERVING

Multi-tenant retrieval-augmented generation (RAG) serving has heavy-tailed, highly reused document access, underexploited by prefix caching. We show that corpus-level document frequency is an effective, low-cost ordering prior: placing frequent documents first needs no cache-state history, giving a transient advan- tage that narrows as an adaptive orderer accumulates history. A strictly causal table retains 76% of the ordering gain under streaming re-estimation and ≈99% under a frozen past-only table. An ablation isolates the mechanism: frequency alignment drives the gain, while content-hash ordering adds nothing significant. No lookahead-free adaptive variant we test beats static frequency ordering under the non-causal protocol of that comparison, and it is indistinguishable from static at roughly ten times the ordering cost. On top of frequency ordering, position- weighted WPA routing contributes a further increment, reaching 71.8% HR over- all, a +23.1 pp headline over the no-reorder baseline (the weakest comparator); the ordering gain reproduces across model families. WPA is a balanced router, not the highest-HR one: it trades a little raw HR for load balance, though per-card isolation makes that imbalance cost 20–27% throughput. These cache gains carry a quality cost: on NQ extractive QA, F1 falls from 42.5% to 9.9% under full fre- quency ordering, and no evaluated strategy attains both acceptable F1 and HR; no generative task was measured, so the mechanism behind this task- and position- dependent trade-off is not isolated. In the evaluated settings, static historical fre- quency ordering is the primary mechanism, effective without future information and deployable independently of WPA, with topology- and task-dependent trade- offs; WPA is optional, its benefit depending on topology and load balance. In a matched held-out serving protocol, past-only frequency ordering showed a small positive mean difference over cache-dependent ordering (+1.0 pp, n= 5), but the comparison is underpowered and does not establish superiority.