acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
prefix caching、KV cache、retrieval-augmented generation、LLM serving、document ordering、multi-tenant、cache hit rate、load balancing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_wPBLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies prefix-cache reuse in multi-tenant RAG serving. It orders retrieved documents by historical access frequency to encourage shared prefixes across requests, with optional Weighted Prefix Affinity routing. The experiments show substantial cache-hit improvements over unordered prompts, smaller gains over cache-dependent ordering, and limitations involving answer quality and deployment topology.

Critical strengths

Frequency ordering is a simple and inexpensive idea with practical appeal. The comparisons against fixed random and content-hash ordering provide useful evidence that frequency alignment drives the gains. Past-only controls also support the mechanism without requiring access to future requests.

I appreciate the reporting of negative quality and throughput results. Cache-hit rates alone would give an overly optimistic picture. These measurements help identify where the method may be unsuitable and show that WPA is not beneficial under every deployment configuration.

Critical weaknesses

The evaluation does not yet establish a convincing setting where the method improves serving efficiency while preserving useful answer quality. On the evaluated NQ subset, reordering the same documents reduces F1 from 42.5% to 9.9%, and no tested mitigation reaches the stated joint quality–cache target. This does not imply degradation on all RAG tasks, but leaves the practical benefit unresolved. Missing per-question artifacts also prevent auditing this unusually large drop. The throughput penalty from WPA under isolated two-GPU serving further limits the full system’s benefit.

The additional contribution over existing ordering methods appears modest. ContextPilot and CacheWeaver already study closely related context-ordering mechanisms. The main change here is replacing cache-state information with a historical frequency prior, while the matched held-out advantage is about one percentage point and narrows with longer execution. The paper acknowledges these limitations, but still needs a clearer account of when this incremental benefit is consequential.

Questions for authors
  1. Can the quality experiment be rebuilt with preserved per-question artifacts? Does the large drop persist with explicit original-rank annotations comparable to ContextPilot?

  2. With matched historical information, cache budgets, and request traces, what sustained latency or throughput advantage remains over a faithful cache-dependent ordering implementation?

  3. Is there an evaluated workload showing both serving improvements and acceptable answer quality, including the simpler frequency-plus-round-robin configuration?

Reviewer_TvMZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a stateless proxy for multi-tenant RAG serving. It sorts each request’s retrieved documents by precomputed corpus access frequency so that popular documents form shared KV-cache prefixes, and optionally routes requests with a position-weighted vote (WPA). On a 2-worker vLLM setup with synthetic Zipf workloads, it raises prefix hit rate from 48.8% to 71.8%. However, it gains only +1.1 pp over cache-dependent reordering (shrinking to +0.4 pp by 2000 requests) and cuts NQ extractive-QA F1 from 42.5% to 9.9%.

Critical strengths
  • The method is simple, stateless, sub-millisecond, engine-agnostic, and easy to deploy.
  • Content-hash and random-fixed orderings give no gain, thus supporting popularity over determinism as the lever.
  • Causal and staleness controls show that a past-only frequency table recovers most of the gain.
  • The paper discusses its limitations (quality cost, WPA throughput penalty, underpowered tests) and reports per-seed data.
  • Additionally, Appendix H cleanly separates intra-prompt ordering from inter-request prefix sorting.
Critical weaknesses
  • NQ F1 drops from 42.5% to 9.9% (77% relative), undermining practical utility. Lost per-question artifacts prevent verification.
  • Improvements over cache-aware reordering are only +1.1 pp (+1.0 pp, statistically insignificant, in the causal setting), shrinking to +0.4 pp at 2,000 requests. Most benefits occur during warmup.
  • Table 3 reports substantial F1 loss despite nearly unchanged hit rates
  • Identical retention across different memory budgets raises questions about cache eviction.
  • Reported p99 latency (0.069 ms) is below reported mean latencies (0.117–0.154 ms), suggesting inconsistent measurement or reporting.
  • Most experiments use only 3–5 seeds, while the 15-seed significance test compares against the weaker no-reordering baseline.
  • Popularity-first ordering is straightforward, and the exchange argument assumes position-independent probabilities without adequate justification.
  • Limited quality evaluation (on extractive QA, without generative QA, multi-hop reasoning, or broader RAG tasks).
  • Cross-model hit-rate consistency offers limited evidence of robustness because prefix matching primarily depends on token sequences.
  • The frequency table uses the full evaluation trace, while adaptive baselines lack equivalent historical access. Causal evaluation does not show a significant advantage.
Questions for authors
  • Experiments use synthetic Zipf workloads, two workers, 500 documents, k ≤ 5, and at most 2,000 requests. Large-scale serving and cache eviction are essential. How does the method perform?
  • Consistent hashing achieves higher hit rates, while power-of-two offers better balance. WPA reduces throughput by 20–27%, and the full system underperforms frequency ordering with round-robin routing. What advantage does WPA have over other alternatives?
Reviewer_E3zqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

In this paper, the authors propose CacheCoherent for improving prefix-cache reuse in multi-tenant RAG serving. Specifically, retrieved documents are ordered by historical access frequency, with an optional position-weighted routing strategy. Experiments on vLLM show improved cache hit rates over unordered prompts, while also revealing substantial answer-quality degradation and topology-dependent routing costs.

Critical strengths
  1. The method is simple and requires no per-request cache-state queries. The mechanism ablation usefully distinguishes frequency ordering from arbitrary deterministic ordering.

  2. The authors report important negative results, including the answer-quality loss and WPA’s throughput penalty under per-card isolation.

Critical weaknesses
  1. The practical benefit is not sufficiently established. In Table 3, full frequency ordering reduces NQ F1 from 42.5 to 9.9, and none of the tested mitigations preserves both reasonable quality and high cache reuse. Appendix I states that the per-question responses, prompts, and retrieved documents are no longer available. Consequently, this central result cannot be independently reconstructed or diagnosed. A reproducible quality–latency evaluation is necessary.

  2. The improvement over the relevant ordering baseline is limited. Frequency ordering exceeds cache-dependent ordering by 1.1% in the main experiment, narrowing to 0.4% at 2,000 requests. The held-out comparison is also small and underpowered. Moreover, the exchange argument sorts fixed position-match probabilities; it does not establish that sorting document frequencies optimizes these probabilities under correlated retrieval or outperforms adaptive ordering.

  3. The headline result uses frequencies computed from the full evaluation trace. The past-only controls are useful, but use different protocols and do not directly validate the headline configuration. Some reported “ordering gains” also compare frequency ordering plus WPA against no ordering plus round-robin, changing two components simultaneously. A unified held-out evaluation with routing fixed would make the contribution clearer.

  4. The deployment evaluation remains narrow. WPA reduces throughput by 20–27% under per-card isolation, and scaling beyond two workers is not evaluated. Longer traces and cache-capacity sweeps are also needed. Given the quality loss from reordering, comparison with position-independent cache reuse would be particularly informative.

Questions for authors
  1. Can you rerun the quality evaluation with preserved per-question artifacts and report quality and latency on the same workload?

  2. Does past-only frequency ordering provide a meaningful advantage over cache-dependent ordering under sustained eviction pressure?

  3. How does the quality–efficiency trade-off compare with position-independent cache reuse?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.