Tight weighted paging with delay via mirror descent

arXiv:2610.24655 · cs.DS · Submitted 2026-10-17 · Read on arXiv

Listen

Radio episode about this paper

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: "Tight weighted paging with delay via mirror descent".

Jane: Here's the gist of the paper. Tight weighted paging with delay via mirror descent gives an O(log k)-competitive randomized algorithm for weighted paging with delay that does not depend on the number of pages n and matches the lower bound of Θ(log k) from classical paging.

Tom: Algorithm Overview The paper presents an O(log k)-competitive randomized algorithm, PMD (Preemptive Mirror Descent), for weighted paging with delay that achieves a tight competitive ratio matching the lower bound of Θ(log k).

Jane: This result improves upon previous O(log k log n)-competitive algorithms by removing the dependence on the number of pages n.

Tom: The algorithm combines mirror descent, used for weighted paging without delay, with preemptive service to handle the delay cost introduced in paging with delay.

Title and authors: Tom: So we're looking at this paper now, "Tight weighted paging with delay via mirror descent," and the title itself tells you a lot about what they're trying to achieve. It suggests they've found a way to handle weighted paging with delay in a very tight way.

Jane: It sounds like they are aiming for an optimal competitive ratio that matches what we know is the lower bound for this kind of problem, which is log k. That’s pretty significant because it means their algorithm is as good as the best possible one we could hope for in this setting.

Lu: The authors are combining a couple of established techniques here: they're using mirror descent, which they mention was used before for weighted paging without delay, with preemptive service, which is something introduced to handle the extra cost that comes with having delay.

Meng: Combining those two sounds complicated when you think about how it actually runs on a real system. I wonder how they manage that transition from simple weighted paging to this more complex version with delay?

Lalam: I'm seeing the core idea is using a fractional state, let's call it x, where xi is the fraction of page i that isn't cached. They are trying to control this state over time.

Tom: So they’re not just looking at a static cache size; they’re tracking these fractions online and using that information to make decisions about which pages to fetch when there's a delay involved.

Jane: And the real punch here, as the abstract says, is that this approach doesn't depend on the number of pages n. That takes away a whole layer of complexity from what we usually see in these types of algorithms.

Lu: Right, they’re bypassing that n dependence by focusing their analysis on the structure of mirror descent paths and how they interact with the potential function, which is defined using a weighted entropy function called the mirror map.

Meng: Bypassing n dependence sounds great for scaling up to massive caches, but I worry about the computational cost of tracking these fractional states if n gets really huge.

Lalam: The paper shows that this fractional state transformation into a randomized integral algorithm works with only a constant loss when you use the standard online rounding technique from classical paging.

The paper's summary: Tom: To summarize what the paper is doing, they’ve developed an algorithm for weighted paging with delay that achieves an O of log k competitive ratio without depending on n. They are essentially building on prior work by combining mirror descent for the no-delay version and preemptive service to deal with the delay cost.

Jane: So, when you think about it, they’re taking a known good tool for one problem—weighted paging—and adding a clever mechanism to handle the second part of the problem—the delay. It's like patching an existing system rather than building something completely new from scratch.

Lu: The summary points out that the analysis hinges on bounding costs by combining bounds on fractional fetch and delay costs, showing that they stay within a bound of twenty-three times Opt plus some constant term c prime <ref:2610.24655#pg2>.

Meng: Bounding the total cost like that is crucial for production systems, because we need to know how much overhead this adds compared to just running the no-delay version. What does that constant term c prime look like in practice?

Lalam: The paper uses Lemma three to bound the length of critical services, which helps them control the total excess term. They show that this excess is bounded by something proportional to Ccrit fetch plus a term involving X i wi.

Tom: So they are showing that even with delay, the total cost doesn't explode wildly; it stays controlled because they can bound those critical service lengths using their mirror descent paths.

Jane: And the final result is that when you transform these fractional states online using a fixed map, you get an integral algorithm that serves every request with probability one. This means it’s a reliable method for actual deployment.

Lu: The key mechanism they leverage is how the mirror descent path reduces the antimass at a specific requested page p while increasing it everywhere else, and then they concatenate these paths for each request to form the full execution.

Meng: That sounds like a lot of dynamic path calculations happening in real time. I hope that concatenation step isn't too slow when we have high request rates.

The paper's improvements: Tom: The main improvement they highlight is moving from an O of log k log n competitive ratio, which was what Gupta, Kumar, and Panigrahi showed before, to a tighter O of log k that doesn't have the n dependency. That’s a big win because it means the performance doesn't degrade as our cache size grows.

Jane: It’s like they found a way to keep the performance flat no matter how many pages are in the system, which is exactly what we want when designing systems that need to be robust.

Lu: They achieve this by choosing a specific threshold delta equal to one over two k plus one, and they say this minimizes the factor L of one over delta, which is a key part of their potential argument.

Meng: Choosing that specific value for delta sounds like they spent a lot of time tuning parameters just to make the theoretical bound cleaner. Does that choice limit us in practical scenarios?

Lalam: The paper says that this choice of delta is motivated because it minimizes L, which is inherent to the potential argument they are using. It’s not just an arbitrary number; it comes from minimizing a specific factor related to the analysis structure.

Tom: And they tie this back into the competitive ratio being tight because they can't improve on that log k bound by changing delta anymore. The factor log n from earlier approaches is completely circumvented here.

Jane: It really suggests that weighted paging with delay is fundamentally as hard to solve as the no-delay version, up to some constant factors, which feels like a very strong statement about the inherent difficulty of this problem.

Lu: And they prove this by showing that the total expected cost is bounded by three times the delay cost, which comes from bounding those overshoot terms in their analysis.

Conclusion: Tom: So to wrap up, this paper on "Tight weighted paging with delay via mirror descent" gives us an O of log k competitive ratio for weighted paging with delay that doesn't depend on the number of pages n. It matches the lower bound from classical paging.

Jane: It really shows that we can combine mirror descent with preemptive service to handle the delay in a way that keeps the performance tight, and it does this without needing to scale up or down our analysis based on n.

Lu: The main implication is that they’ve shown that weighted paging with delay is as hard as without delay, up to constant factors, and they achieved this by cleverly using mirror descent paths guided by a specific threshold delta.

Meng: From a deployment standpoint, if we can get those fractional states tracked online reliably, this method seems viable for real-world systems where the performance guarantee doesn't degrade with cache size. But I still have to see how stable those path calculations are under heavy load.

Lalam: I'm pretty sure the core result is that they’ve established a randomized algorithm with expected cost bounded by O of log k times Opt plus O of log k X i wi, which means it’s efficient in terms of the optimal cost.

Tom: That's the gist: they managed to get rid of the n dependency and matched the lower bound. It’s a solid result that shows we can tackle this problem with a method that keeps things tight.

Jane: And that's what we have here for today on "Tight weighted paging with delay via mirror descent." We’ll be back next time to another paper from arXiv.

Technical University Darmstadt

cs.DS

Submitted: 2026-10-17

Updated: 2026-10-31

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 85/100

The gist: Tight weighted paging with delay via mirror descent gives an O(log k)-competitive randomized algorithm for weighted paging with delay that does not depend on the number of pages n and matches the…

Key concepts

Fractional State x
A fractional state $x otin [0, 1]^n$ where $x_i$ represents the fraction of page $i$ that is not cached. This state guides the algorithm's decisions by indicating which pages need more attention based on their current caching status.
Mirror Descent
This technique is used to determine the optimal way to serve a critical page. It involves following a specific path $ u$ that reduces the 'antimass' (a measure of unserved demand) at the requested page while adjusting other pages according to differential inclusion rules.
Preemptive Service
This mechanism manages delay costs by allowing the system to serve other pending requests when serving a critical page. The budget for this service is derived from the mirror descent path, ensuring that delay penalties are managed effectively without sacrificing overall performance.

Terminology

Summary

Tight weighted paging with delay via mirror descent gives an O(log k)-competitive randomized algorithm for weighted paging with delay that does not depend on the number of pages n and matches the lower bound of Θ(log k) from classical paging. p. 1

Where the paper says it

Together with the lower bound of Ω(log k) from classical paging [Fia+91], this gives a tight bound on the competitive ratio of randomized weighted paging with delay and deadlines. We obtain this result by combining the mirror descent technique from [Bub+18] for classical paging with a preemptive service approach typical for online service with delay [Aza+21].

Algorithm Overview

The paper presents an O(log k)-competitive randomized algorithm, PMD (Preemptive Mirror Descent), for weighted paging with delay that achieves a tight competitive ratio matching the lower bound of Θ(log k). This result improves upon previous O(log k log n)-competitive algorithms by removing the dependence on the number of pages n. p. 0

Where the paper says it

This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Θ(log k), and since the lower bound carries over, our bound is tight.

The algorithm combines mirror descent, used for weighted paging without delay, with preemptive service to handle the delay cost introduced in paging with delay. p. 0
Where the paper says it

Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al.

Technique and Analysis

The technique involves designing a fractional algorithm that maintains a fractional state x ∈ [0, 1]n where xi represents the fraction of page i that is not cached. This fractional state is then transformed online into a randomized integral paging algorithm realizing the state as its marginal probabilities. p. 1

Where the paper says it

Throughout the execution, we maintain that the fractional state satisfies P i xi ≥ n − k, meaning that the total cached mass is at most k. Bansal, Buchbinder, and Naor showed for classical paging that the state x of a fractional algorithm can be transformed online into a randomized integral paging algorithm realizing the state as its marginal probabilities, i.

The core of the analysis relies on mirror descent paths to reduce antimass at requested pages. p. 2
Where the paper says it

Intuitively, x ′ is defined to reduce the antimass at p (via the term −1p), while being forced into the possible state space S (via the term −NS(x(t))), and following some distortion defined by Φ. It can be shown that this mirror descent path indeed reduces the antimass at p, while increasing the antimass at all other pages.

Bounding Costs

The total cost is bounded by combining bounds on fractional fetch and delay costs, showing that Cfetch + Cdelay ≤ 23ρ · Opt + c'. The analysis involves bounding the length of critical services using Lemma 3, which leads to the bound Xν∈Scrit λ(ν) ≤ 3 · Ccrit fetch + 3Xiwi. p. 9

Where the paper says it

3, where we also define the correct notion. Writing Cfetch and Cdelay for the fractional fetch and delay costs of PMD, defined below, we formally show Cfetch ≤ C crit fetch + X ν∈Scrit |λ (ν) | and Cdelay ≤ Cfetch + 5 X ν∈Scrit |λ (ν) |, (7) and Lemma 3 converts the lengths into fetch cost of critical services.

Rounding and Final Result

The fractional states of PMD are transformed online using a fixed map to yield a randomized integral algorithm that serves every request with probability 1. This yields the desired O(log k)-competitive randomized algorithm with expected cost at most O(log k) · Opt + O(log kXiwi). p. 5

Where the paper says it

An algorithm is ρ-competitive if, for every input σ, its cost satisfies Alg(σ) ≤ ρ · Opt(σ) + c, where Opt(σ) is the cost of the optimal offline algorithm on σ, and c is a constant that is independent of the input sequence. A randomized algorithm is ρ-competitive if its expected cost satisfies E[Alg(σ)] ≤ ρ · Opt(σ) + c, where the expectation is taken over the algorithm’s random choices.

Why the Gains Come From

The competitive ratio is tight because the factor log n from the LP-based approach of Gupta, Kumar, and Panigrahi is circumvented by this algorithm. The choice of threshold δ = 1/(2k + 1) is motivated because it minimizes the factor L = log 1/δ, which is inherent to the potential argument. p. 3

Where the paper says it

To optimize the competitive guarantee, we choose δ maximal such that we can define a transformation mapping mass δ to 0 with bounded derivative. The optimal choice turns out to be δ := 1/(2k + 1) (see also Section B), giving the mirror map Lipschitz factor L = log 1 δ = log(2k + 1) and competitive guarantee O(log(k)).

The rule for turning a page critical depends on both its weight and delay cost, as shown in Example 34. p. 6
Where the paper says it

However, if many light pages are simultaneously pending and the cache is filled with heavy pages, following this rule for each page individually means that we let each pending request incur a very large delay cost. Displacing a heavy page to serve all light pages may be much cheaper than waiting for each light page to accumulate sufficient delay to warrant evicting a heavy page on its own (Example 35).

Pruning Redundant Reasoning Tokens

The analysis shows that the total excess term Exc is bounded by O(L) · Opt + O(LXiwi). This bound is achieved by charging the excess of timely services to Opt's delay cost. The total excess is further bounded by relating it to the total budget spent in early parts of periods. p. 3

Where the paper says it

In our case, most cost is already covered through the Bregman potential, and the quantity to be bounded is instead the excess term R 1 ⊤ p Opt(t)dt. When a page is fetched due to high delay cost, we measure the length of the mirror descent path it follows and declare this amount as a budget for preemptive service to pending requests.

How the Training Signal is Built

The training signal for the randomized integral algorithm is built by applying a transformation zi:= max(0, 2ui - 1) to the fractional antimass states. This transformation maps antimass δ to cached mass 0, ensuring every page with antimass δ is fully cached. p. 5

Where the paper says it

Because we define the randomized algorithm after applying a transformation that maps δ to 0 (Proposition 30), every realization of the randomized algorithm has p cached with probability 1 at time τr. In case a page’s antimass is strictly positive, it may be cached even before this time in some realizations of the algorithm.

Where the Gains Come From

The competitive ratio O(log k) is achieved because the analysis of PMD cannot be improved by choosing a different δ. The total expected cost is bounded by 3Cdelay, which is derived from bounding the overshoot terms. p. 8

Where the paper says it

4 Reducing to fetch cost of critical service The aim of this section is to show that it suffices to analyze the fetch cost C crit fetch = P ν∈Scrit fetch(λ (ν) ) of critical services of PMD, where Scrit is the set of critical steps and λ (ν) is the path of the critical service performed in step ν (Section 4. More precisely, we define the fractional fetch and delay costs of PMD, show that their sum corresponds to the expected cost of the randomized algorithm that PMD is transformed into, and prove that all costs incurred by PMD are bounded by a constant multiple of C crit fetch + X i wi , i.

The final expected cost is O(log k) · Opt + O(log kXiwi). p. 5
Where the paper says it

An algorithm is ρ-competitive if, for every input σ, its cost satisfies Alg(σ) ≤ ρ · Opt(σ) + c, where Opt(σ) is the cost of the optimal offline algorithm on σ, and c is a constant that is independent of the input sequence. A randomized algorithm is ρ-competitive if its expected cost satisfies E[Alg(σ)] ≤ ρ · Opt(σ) + c, where the expectation is taken over the algorithm’s random choices.

The Gist

Tight weighted paging with delay via mirror descent gives an O(log k)-competitive randomized algorithm for weighted paging with delay that does not depend on the number of pages n and matches the lower bound of Θ(log k) from classical paging.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI system can perform weighted paging with delay by maintaining a fractional state x in [delta, 1]n where antimass xi represents the fraction of page i not cached, ensuring that a requested page is cached almost surely at its serving time tau r when xp = delta.

  2. The system incorporates mirror descent to determine how to serve a critical page p by following a path lambda, which reduces the antimass at p while increasing it at all other pages based on the differential inclusion (1).

  3. It employs preemptive service, where when serving a request, an increase in mirror descent potential is offset by serving other pending requests with a budget derived from the mirror descent path to manage delay cost.

  4. The system uses online rounding based on Bansal, Buchbinder, and Naor's approach combined with a fixed transformation to convert the fractional states into a randomized integral algorithm that serves every request with probability 1 and realizes the fractional fetch cost up to a constant factor.

  5. The system can estimate the competitive ratio for weighted paging with delay as O(log k) by combining mirror descent for classical paging with preemptive service, matching the lower bound of log k from classical paging and showing that weighted paging with delay is as hard as without delay, up to constant factors.

Abstract

We give an O(log k)-competitive randomized algorithm for weighted paging with delay. This improves upon the O(log k log n)-competitive algorithm of Gupta, Kumar, and Panigrahi (STOC 2020, SICOMP 2022) by removing the dependence on the number n of pages. Without delay, the optimal competitive ratio of randomized algorithms is Theta(log k), and since the lower bound carries over, our bound is tight. Our algorithm is fractional and combines mirror descent, used by Bubeck et al. (STOC 2018) for weighted paging without delay, with preemptive service, introduced by Azar et al. (STOC 2017) for online service with delay: when a request is served, an increase in the mirror descent potential is offset by preemptive service to other pending requests, with a budget derived from the mirror descent path. To obtain a randomized algorithm, we use the online rounding of Bansal, Buchbinder, and Naor (FOCS 2007) from classical paging.

Sources

Related papers