RPB turns trust in a prediction into an explicit resource. A prediction-guided eviction is allowed only when the algorithm has earned enough budget relative to an optimally robust online baseline. This simple design principle yields optimal behavior with perfect advice and near-optimal robustness when advice is arbitrary.
1. The decision problem
A cache stores at most \(k\) pages. Requests \(\sigma=\langle p_1,\ldots,p_n\rangle\) arrive online. A miss costs one unit and may force an eviction. Belady's rule evicts the page requested farthest in the future, but it requires perfect knowledge of the request sequence.
Classical randomized paging achieves the optimal competitive ratio \(H_k=\sum_{i=1}^{k}1/i\). A learning-augmented method should approach OPT when predictions are accurate while retaining a comparable bound when they are wrong.
Three guarantees, not one
Consistency
With perfect predictions, the ratio should be as small as possible. RPB-OM achieves \(1\), so it is offline optimal in this regime.
Robustness
With arbitrary predictions, cost must remain bounded by a competitive online baseline. RPB-OM achieves \(H_k+O(1)\).
Smoothness
For intermediate error \(\eta_1\), performance should deteriorate gradually. RPB-OM obtains \(O(1+\log(\eta_1/\operatorname{cost}(\mathrm{OPT})))\).
The tension
Every prediction-based eviction can improve consistency, but it can also move the cache away from a robust baseline. The algorithm must account for that divergence.
2. Why earlier trust rules leave a gap
Prior algorithms also limit prediction use, but their accounting is too coarse. Global switching compares cumulative costs and can miss locally useful advice. Fixed eviction-chain thresholds either spend too much trust under severe error or stop too early when predictions remain useful.
- Prediction quality is local. A predictor may be excellent for one eviction chain and poor for the next. One global score cannot express this variation.
- Trust should be relative. The meaningful reference is not elapsed time, but the progress that a robust baseline would have made in the same state.
- Every deviation needs payment. A prediction-driven decision can increase the distance from the baseline cache, so it must consume a resource that appears in the analysis.
3. Relative prediction budget
RPB is built on ONOPT, a class of paging algorithms that maintains a valid cache configuration through the work-function layer structure. Its efficient instance, OnlineMin (OM), samples the same distribution as an optimally competitive randomized algorithm and updates each request in \(O(\log k)\) time.
The key state variable is a nonnegative budget \(B\). A request to the zero layer \(L_0\) represents maximal uncertainty. At such a miss, RPB follows the prediction and resets \(B\) to a constant \(\tau\). On later lazy-adversary misses, it compares the effectiveness of previous evictions with OM and decides whether more budget has been earned.
\(U(\omega)\leq\)
\((Y+2)/e-2\).
Why the gate uses unrevealed layers
Let \(U(\omega)=k-|R(\omega)|\) be the number of unrevealed work-function layers. As lazy requests reveal layers, OM's potential drops by at least a harmonic amount. The gate tests whether enough of this baseline progress has accumulated to pay for another prediction-based deviation. This creates a fine-grained connection between advice effectiveness and robust progress without simulating OM's full cache distribution.
4. The proof mechanism
The proof does not analyze prediction cost in isolation. It combines three quantities in one potential:
Here, \(\phi\) is OM's remaining adversarial cost, \(D\) is the expected cache difference between RPB-OM and OM, and \(B\) is unspent prediction budget.
At an \(L_0\) miss, the algorithm may increase both cache divergence and budget, but the increase is only \(O(1)\) beyond OM's \(H_k-1\) potential change. During later lazy requests, a prediction-based miss spends budget, while an OM-based miss reduces cache divergence. In both cases, the amortized cost is nonpositive. Summing these inequalities gives the worst-case theorem.
5. What the experiments establish
The evaluation combines synthetic log-normal noise with two real predictors, PLECO and POPU, on SPEC CPU 2006 memory traces. The table below reports averages from the paper. Lower cost ratio and higher hit ratio are better.
| Method | PLECO | POPU | ||
|---|---|---|---|---|
| Cost ratio | Hit ratio | Cost ratio | Hit ratio | |
| BlindOracle | 1.404 | 15.92 | 1.261 | 21.75 |
| BlindOracle & LRU | 1.286 | 20.53 | 1.230 | 23.10 |
| ONOPT-OM | 1.253 | 22.42 | 1.237 | 23.76 |
| RPB-OM, \(\tau=1\) | 1.249 | 22.75 | 1.220 | 24.34 |
| RPB-OM, \(\tau=2\) | 1.252 | 22.70 | 1.215 | 24.49 |
| RPB-OM, \(\tau=4\) | 1.254 | 22.64 | 1.213 | 24.55 |
Synthetic-noise experiments answer a different question: prediction-only methods can deteriorate sharply as noise grows, while RPB-OM stays controlled. Together, the two evaluations show that the guarantee is not merely defensive. The algorithm still extracts measurable value from realistic predictors.
6. The broader idea
The most reusable contribution is an accounting principle: learned advice should earn the right to influence an online system through measurable progress against a safe baseline. The same pattern can guide scheduling, admission control, resource allocation, and other online systems where predictions are useful but failure cannot be unbounded.