Implementation:LMCache LMCache LFU Cache Policy

Knowledge Sources	LMCache
Domains	Cache Eviction, Storage Backend
Last Updated	2026-02-09 00:00 GMT

Overview

LFUCachePolicy implements a Least-Frequently-Used cache eviction strategy with FIFO ordering for entries of equal frequency.

Description

This class extends BaseCachePolicy using a SortedDict from the sortedcontainers library to maintain frequency-ordered buckets. Each frequency level maps to a dictionary of keys (used as an ordered set). A separate key_to_freq dictionary tracks the current frequency of each key. On cache hit, the key's frequency is incremented and it is moved to the appropriate bucket. On put, new keys start at frequency 1. On force eviction, the key is removed from both tracking structures. The get_evict_candidates method iterates from the lowest frequency bucket upward, selecting evictable entries (those with can_evict == True) in FIFO order within each frequency level. This is a best-effort approach where fewer candidates may be returned than requested.

Usage

Use this policy when frequently accessed cache entries should be retained longer. It is more sophisticated than FIFO but requires additional memory for frequency tracking. Suitable for workloads with significant access frequency variation.

Code Reference

Source Location

• Repository: LMCache
• File: lmcache/v1/storage_backend/cache_policy/lfu.py
• Lines: 1-105

Signature

class LFUCachePolicy(BaseCachePolicy[KeyType, dict[KeyType, Any]]):
    def __init__(self): ...

    def init_mutable_mapping(self) -> dict[KeyType, Any]: ...
    def update_on_hit(self, key: KeyType, cache_dict: dict[KeyType, Any]) -> None: ...
    def update_on_put(self, key: KeyType) -> None: ...
    def update_on_force_evict(self, key: KeyType) -> None: ...
    def get_evict_candidates(self, cache_dict: dict[KeyType, Any], num_candidates: int = 1) -> list[KeyType]: ...

Import

from lmcache.v1.storage_backend.cache_policy.lfu import LFUCachePolicy

I/O Contract

Inputs

Name	Type	Required	Description
key	KeyType	Yes	Cache entry key for frequency tracking
cache_dict	dict[KeyType, Any]	Yes	The cache dictionary containing current entries
num_candidates	int	No	Maximum number of eviction candidates to return (default 1)

Outputs

Name	Type	Description
init_mutable_mapping	dict	An empty Python dictionary for cache storage
get_evict_candidates	list[KeyType]	Up to num_candidates keys with lowest access frequency, FIFO within same frequency

Internal Data Structures

Structure	Type	Purpose
freq_to_keys	SortedDict[int, dict[KeyType, None]]	Maps frequency to ordered set of keys at that frequency
key_to_freq	dict[KeyType, int]	Maps each key to its current access frequency

Usage Examples

from lmcache.v1.storage_backend.cache_policy.lfu import LFUCachePolicy

policy = LFUCachePolicy()
cache = policy.init_mutable_mapping()

# Store entries
cache["key1"] = some_value
policy.update_on_put("key1")

cache["key2"] = some_value
policy.update_on_put("key2")

# Access key1 multiple times (increases frequency)
policy.update_on_hit("key1", cache)
policy.update_on_hit("key1", cache)

# Get eviction candidates (least frequently used first)
candidates = policy.get_evict_candidates(cache, num_candidates=1)
# candidates == ["key2"] (frequency 1 vs key1's frequency 3)