Stochastic Weighted Caching with Per-Request Predictions
summary
The gist
Stochastic Weighted Caching with Per-Request Predictions studies how combining input stochasticity and per-request predictions can reduce the competitive ratio for weighted caching from a logarithmic…
In short
This research combines input randomness and per-request predictions to improve weighted caching performance. The goal is to reduce the competitive ratio from a logarithmic bound ($\Omega(\log k)$) to a constant factor ($O(1)$) using an efficient deterministic policy. The main result shows that with perfect predictions, the system achieves 15.75-competitive performance.
Key concepts
- Weighted Caching
- A caching problem where fetching a specific page $p$ has a cost $w_p$. This cost reflects real-world differences, like pages being stored in different parts of a storage hierarchy. The algorithm must balance the cost of fetching against the benefit of having the page cached.
- Per-Request Predictions (PRP)
- The ability to predict which page will be requested next for every individual request. This prediction information is used by the caching algorithm to make smarter decisions about which pages to keep in memory, guiding it toward an optimal or near-optimal choice.
- Competitive Ratio
- A measure of how close the performance of an online algorithm is to the best possible offline (optimal) solution. A ratio of 1 means perfect performance; a higher ratio indicates poorer performance relative to the optimum.
Terminology used across episodes
This episode discusses
- Stochastic Weighted Caching with Per-Request Predictions · Paper Radio
- Learning-Augmented Online Caching: New Upper Bounds
The paper
Stochastic Weighted Caching with Per-Request Predictions · Read on arXiv
University of Texas at Austin
Both the unweighted and weighted variants of caching are cornerstone problems in competitive analysis, with tight randomized competitive ratios of Θ(k), where k is the cache size. We study weighted caching with per-request predictions, where each page request is accompanied by a prediction of the next arrival time of the same page. For unweighted caching, such perfect predictions suffice to implement Belady's offline optimal rule. For weighted caching, however, previous work shows that a logarithmic lower bound persists even with perfect predictions on adversarial request sequences. Stochastic assumptions alone are also insufficient: the classical caching lower bounds already apply to uniform independent requests. In this work, we ask whether combining these two sources of additional information can overcome this barrier, and answer this question affirmatively. Specifically, we develop an efficient cache eviction policy that achieves a competitive ratio of 15.75 using perfect per-request predictions when page requests are drawn independently from an arbitrary, known static distribution in every step, and page costs are arbitrary. Underlying our analysis is a novel lower bound on the optimal cost obtained through an ex-ante relaxation of the cache's covering constraints. Our algorithm's performance degrades gracefully under erroneous predictions: we prove a bound of O(1+E, k) on the competitive ratio, where E aggregates each page's average prediction error, and may be unknown to the algorithm.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Stochastic Weighted Caching with Per-Request Predictions".
Jane: Here's the gist of the paper. Stochastic Weighted Caching with Per-Request Predictions studies how combining input stochasticity and per-request predictions can reduce the competitive ratio for weighted caching from a logarithmic lower bound to a constant factor using an efficient deterministic policy.
Tom: Caching is a foundational problem in online algorithms and competitive analysis.
Jane: In the weighted version, fetching page p incurs a page-specific cost wp ≥ 0 modeling differences in retrieval cost arising, for example, from where pages reside in a storage hierarchy.
Tom: For unweighted caching, such perfect predictions suffice to implement Belady’s offline optimal rule.
Title and authors: Tom: The title itself, "Stochastic Weighted Caching with Per-Request Predictions," tells you right away that they are adding two things: randomness in requests and predictions about future requests for the same page.
Jane: So, if we just have random requests for pages, we get one result; but when we add those per-request predictions—knowing what's coming next—does that fundamentally change how good our caching policy can be?
Lu: Exactly. The authors are arguing that this combination allows us to overcome a barrier where previous work showed even perfect predictions couldn't help with weighted caching under certain conditions.
Meng: So, is the main idea that these predictions give us a deterministic way to evict things, instead of relying on luck or complex randomized choices?
Lalam: That's right. They develop an efficient, deterministic cache eviction policy that achieves a competitive ratio of fifteen point seven five when you have perfect per-request predictions for this stochastic weighted caching problem <ref:2610.16045#pg1,develop an efficient, deterministic cache eviction policy that achieves a competitive ratio>.
Tom: fifteen point seven five is a specific number, which is good because it’s not just some abstract 'better than log k' statement; it’s a concrete performance guarantee.
Jane: That sounds like they found a way to make the system reliable even when requests are random and the costs aren't uniform.
Lu: They achieve this by using an efficient deterministic policy, which is what makes this result interesting because it moves us away from the (k) lower bound.
The paper's summary: Tom: So, if we break down what they’re actually doing, they start by looking at the lower bounds for the optimal rate, which helps guide how they design their policy.
Jane: That sounds like setting up a hurdle first. What is that hurdle trying to tell us about what's possible with this caching setup?
Lu: For optional admission, they establish a lower bound L opt(S, S - k) based on finding certain fractions f p that satisfy some probability condition and minimize the cost rate.
Meng: Those fractions sound like constraints we have to satisfy just to even consider putting a page in the cache. Is that how they handle mandatory admission?
Lalam: For mandatory admission, they derive a stronger lower bound L man(S, S - k) by looking at contracted instances and balance constraints.
Tom: So they spend time figuring out the theoretical limits first, which lets them design the policy around those specific constraints rather than just guessing.
Jane: And then, they actually build some specific deterministic policies for optional admission that manage to hit a competitive ratio of forty-two in that setting <ref:2610.16045#pg2>.
Lu: That's interesting because it shows how partitioning pages into structured components and running Guarded Eviction on each component helps achieve that performance.
The paper's improvements: Tom: One major part of this paper is dealing with prediction errors, where the predictions aren't perfect anymore, which is a very realistic scenario for any real system.
Jane: If the predictions are slightly wrong, how does that mess up the performance? Does it just get worse linearly?
Lu: No, the analysis shows a graceful degradation. Theorem one point two proves that any instance admits a policy that is O((one + E, k)) -competitive, where E is the aggregate error for each page <ref:2610.16045#pg2>.
Meng: So if we have high prediction error E, our performance degrades toward the k bound again, but as long as the error isn't too big compared to that log term?
Lalam: That’s what they prove. They achieve this robustness by combining prediction-based policies with prediction-free alternatives using a deterministic combiner.
Tom: So, even when the predictions are noisy, they still have a fallback mechanism that keeps the competitive ratio bounded. That's a key detail for production deployment because we can't always guarantee perfect input.
Jane: It sounds like they didn't just solve the perfect prediction case; they made it practical by addressing what happens when our AI guesses wrong sometimes.
Conclusion: Tom: So to wrap up, the main result of "Stochastic Weighted Caching with Per-Request Predictions" is Theorem one point one, which states that any instance of SWC admits an efficient deterministic online caching policy that is fifteen point seven five-competitive when supplied with perfect per-request predictions <ref:2610.16045#pg2>.
Jane: That fifteen point seven five figure shows the real power of combining input stochasticity with these per-request predictions to get a constant competitive ratio instead of a logarithmic one <ref:2610.16045#pg1>.
Lu: And they proved robustness too, showing that against prediction errors E, you can still achieve O((one + E, k)) -competitiveness through their deterministic combiner approach <ref:2610.16045#pg2>.
Meng: From a deployment perspective, knowing that we can hit fifteen point seven five under ideal conditions is useful for setting targets, but the error term matters most when we talk about real traffic where those predictions might be shaky <ref:2610.16045#pg1>.
Lalam: The implication is that stochasticity and predictions together are enough to break the k barrier entirely for weighted caching, which was a significant result in this area of competitive analysis.
Tom: This paper, "Stochastic Weighted Caching with Per-Request Predictions," gives us a very specific, efficient deterministic policy when we have those per-request predictions available.
Jane: It’s a solid piece of work that moves the theory from just saying what's possible to actually giving us how to build it robustly.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game