learning-relaxed-belady · research · also LRB

Learning Relaxed Belady

Learning Relaxed Belady is a learned cache replacement policy that predicts request-index time to the next access for sampled eviction candidates.

Relaxed Belady permits eviction beyond a future-request boundary instead of requiring the farthest future request. LRB learns this task online; it does not receive future requests at eviction time. [1]

In the pinned simulator, rank() uses LRU before a model exists, or when the oldest resident reaches the memory-window age. Otherwise it samples distinct residents, predicts their scores and chooses the highest. The default sample count is 64. [2] [3]

Training distinguishes observed reuse from timeout labels. On reuse, the distance runs from the sampling request to the later request. When nonresident metadata expires, forget() supplies twice the memory window instead. Training stores log1p(distance); the timeout value is a surrogate, not an observed return time. [2] [3]

Good decision ratio counts qualifying evictions divided by all eviction decisions, not saved bytes. Section 6.4 reports a case where a competitor has a higher ratio but worse byte miss ratio. [1]

The observed label is a residual request-index interval, computed as next request minus sample index, not a count of distinct objects or necessarily the full interval since the last access. In A B B B A, sampling A after index 2 (zero-based) gives residual 2, full interval 4 and distinct-entry distance 1. The code records sample age separately as sample index minus last access. [2] [3] [5]

With a model present and all resident ages below the window, the pinned sampler requires 64 distinct residents by default. Fewer residents cannot fill that set, so rank() cannot reach prediction. A bounded source-function probe confirms the loop boundary; capping the sample budget restores return in its fixtures. [2] [6]

Relations

related
Farthest-in-future replacement, Least Hit Density, Reuse time

Citations

  1. Song, Berger, Li and Lloyd. Learning Relaxed Belady for Content Distribution Network Caching. NSDI 2020, pp. 529-544, sections 3-4 and 6.4. (accessed 2026-11-19)
  2. LRB author simulator, lrb.cpp: lookup, forget and rank; commit 9e8b4423383c01c4528deb447f152f0437a37c3a. (accessed 2026-11-19)
  3. LRB author simulator, lrb.h: training labels, sample count and default objective; commit 9e8b4423383c01c4528deb447f152f0437a37c3a. (accessed 2026-11-19)
  4. Hesela. Constructed request-clock and sampling-origin examples, with executable source and tests. (accessed 2026-11-19)
  5. Hesela. Pinned rank() sampling-cardinality probe, fallback controls and local cap comparison. (accessed 2026-11-19)

Further reading

  1. Hesela: learning a useful victim and measuring the right objective. (accessed 2026-11-19)
Sources & caveats
  • Primary-paper/source review plus an isolated rank() probe with injected model presence and a prediction test double; no model training, full simulator replay or reproduction of CDN performance results.
  • The NSDI landing-page abstract reports 5-24% WAN reduction; the retained full-paper abstract and section 6.4 report 4-25%. No single performance range is promoted here.

JSON: /data/terms/learning-relaxed-belady.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Learning Relaxed Belady. Hesela. 2026-11-19. https://hesela.dev/terms/learning-relaxed-belady/