[Paper] Inferring Causal Relationships to Improve Caching for Clients with Correlated Requests: Applications to VR

Source: arXiv - 2512.08626v1

Overview

Edge caching is a cornerstone for low‑latency services such as VR, but classic policies like LRU and LFU assume that client requests are independent. This paper shows that when requests are correlated—for example, users sharing a virtual environment—the usual policies can be far from optimal. The authors introduce a new model for grouped client requests, prove when LRU or LFU is theoretically best, and present LFRU, an online algorithm that learns causal relationships on the fly and dramatically improves hit rates.

Key Contributions

• Grouped client request model: Extends the classic Independent Reference Model to capture temporal and contextual correlations among users.
• Theoretical cache‑size regimes: Shows LFU is optimal for small‑to‑moderate caches, while LRU overtakes LFU only when the cache is large enough.
• LFRU algorithm: A lightweight, online caching policy that infers causal dependencies between objects and prioritizes evictions accordingly.
• Near‑optimal performance: In structured correlation scenarios, LFRU approaches the offline optimal Belady policy.
• VR‑focused evaluation: Builds realistic VR request traces and demonstrates up to 2.9× improvement over LRU and 1.9× over LFU.

Methodology

1. Modeling correlated demand – The authors define “groups” of clients that share a latent context (e.g., the same VR scene). Within a group, the request for one object raises the probability of a follow‑up request for related objects.
2. Analytical cache analysis – Using stochastic analysis, they derive the expected miss rate of LRU under the grouped model and compare it to LFU, identifying the cache‑size threshold where each policy is optimal.
3. Design of LFRU –
   • Follow‑Score: For each cached object, maintain a lightweight counter of how often it has been followed by another request within a short time window.
   • Least Following: Objects with the lowest follow‑score are evicted first (they are less likely to be part of a causal chain).
   • Recently Used tie‑breaker: Among objects with equal follow‑scores, fall back to standard LRU ordering.
     The algorithm runs entirely online, requiring only O(1) per‑request updates.
4. Dataset creation – Synthetic and trace‑based VR workloads are generated, simulating groups of users moving through shared virtual spaces, with realistic bandwidth and latency constraints.
5. Benchmarking – LFRU is compared against LRU, LFU, and the offline optimal (Belady) across multiple cache sizes and correlation strengths.

Results & Findings

• Correlation matters: When groups request sequences like “scene → avatar → texture”, LFRU learns the chain and keeps the next‑in‑line objects in cache.
• Robustness: Even when correlation strength is weakened, LFRU never underperforms LRU or LFU.
• Overhead: The follow‑score counters add < 2 % memory overhead and negligible CPU cost.

Practical Implications

• Edge servers for VR/AR: Deploying LFRU can cut perceived latency by keeping the next‑most‑likely assets (e.g., upcoming scene tiles) resident, improving user immersion.
• Content Delivery Networks (CDNs): For live events or collaborative apps where users consume a shared stream of assets, LFRU can reduce backhaul traffic without extra hardware.
• IoT and collaborative robotics: Devices that act in coordinated swarms often request correlated firmware or map updates; LFRU can keep those updates locally, saving bandwidth.
• Easy integration: LFRU builds on existing LRU implementations; the only addition is a small per‑object counter and a modified eviction routine, making it a drop‑in upgrade for most cache libraries.

Limitations & Future Work

• Assumption of short‑term causality: LFRU relies on a bounded time window to infer follow relationships; long‑range dependencies (e.g., weekly patterns) are not captured.
• Static group definitions: The model treats groups as fixed; dynamic group formation (users joining/leaving a VR session) could affect accuracy.
• Evaluation scope: Experiments focus on VR workloads; broader validation on web traffic, video streaming, or edge AI inference would strengthen generality.
• Future directions: Extending the follow‑score to multi‑step chains, incorporating machine‑learning predictors for longer horizons, and testing LFRU in production edge platforms.

Authors

• Agrim Bari
• Gustavo de Veciana
• Yuqi Zhou

Paper Information

• arXiv ID: 2512.08626v1
• Categories: cs.NI, cs.SE
• Published: December 9, 2025
• PDF: Download PDF