Hyperbolic Caching

Goal

Combine recency and frequency in a compact, practical scoring model with good hit-rate behavior under skewed and shifting workloads.

Core Idea

Each resident entry gets a score that decays with age and increases with frequency. A common formulation is proportional to:

• score = freq / age

Where:

• freq: access count or weighted access signal
• age: time or logical ticks since insertion/update

Eviction removes the smallest score, so stale/low-value entries fall out first.

Core Data Structures (Typical)

• Hash index K -> EntryMeta
• Per-entry counters: freq, last_touch (or logical timestamp)
• Victim selector:
  • exact ordered structure by score, or
  • approximate buckets/periodic rescoring for lower overhead

Complexity & Overhead

• Exact score ordering is often O(log n) per score-changing update
• Approximate variants trade precision for lower CPU cost
• Metadata is moderate: one frequency counter + age/timestamp per entry

Notes For CacheKit

• Good candidate when plain LRU underperforms and full ML-style policies are too heavy.
• Prefer monotonic logical clocks and integer math on hot paths.
• Benchmark against LRU, Heap-LFU, S3-FIFO, and TinyLFU/W-TinyLFU.

References

• Blankstein et al. (2017): “Hyperbolic Caching: Flexible Caching for Web Applications”, USENIX ATC 2017.
• Wikipedia (taxonomy context): https://en.wikipedia.org/wiki/Cache_replacement_policies