ZerdaZerda

cache.policy_learner

On this page

Overview

Implements a self-improving cache policy using Thompson Sampling (Bayesian multi-armed bandit), where each cache entry is its own bandit arm. The module docstring explains the design rationale directly: no state-space explosion (entries are independent), natural exploration/exploitation balance, O(1) numerically-stable posterior updates, and good behavior under the sparse feedback typical of LLM pipelines — as opposed to, e.g., Q-learning.

FeedbackSignal

Python · 8 lines
@dataclass
class FeedbackSignal:
    entry_id:   str
    tenant_id:  str
    positive:   bool
    magnitude:  float = 1.0
    source:     str   = "user"
    timestamp:  float = field(default_factory=time.time)

Represents one external judgment about a cached entry's quality — "the cached answer was correct" or "incorrect" — emitted by callers via CacheManager.feedback(). source is a free-form string; the docstring suggests "user", "llm_eval", or "auto" as conventional values, but nothing in the code validates or branches on it.

EvictionCandidate

Python · 5 lines
@dataclass
class EvictionCandidate:
    entry_id:  str
    key:       str
    score:     float

The return element type of eviction_ranking(). Lower score = higher eviction priority (i.e. the entry is more expendable).

CachePolicyLearner

Python · 2 lines
class CachePolicyLearner:
    def __init__(self, config: RLConfig) -> None

Construction

Initializes a threading.RLock, two global counters (_total_positive, _total_negative), and a rolling _feedback_log list capped at 10,000 entries (trimmed back to the most recent 10,000 whenever it exceeds that, inside record_feedback).

record_feedback(self, entry: IntelligentCacheEntry, signal: FeedbackSignal) -> None

Overview

Applies one feedback signal to an entry's bandit arm and recomputes its composite confidence score.

When to use it: whenever you have ground truth (explicit user rating, a downstream LLM evaluator, or an automated heuristic) about whether a cached answer was actually good.

Algorithm

Text · 6 lines
reward = signal.magnitude * (
    config.positive_feedback_reward if signal.positive
    else config.negative_feedback_penalty
)
entry.record_hit(positive=signal.positive, reward=reward)
entry.confidence_score = self._compute_confidence(entry)

Also increments the appropriate global counter and appends to the rolling feedback log, all under self._lock.

Side Effects

  • Mutates entry.bandit_arm and entry.confidence_score in place (the caller is responsible for persisting the entry afterward — CacheManager.feedback() does this by calling self._storage.set(entry_id, entry, ttl_s=entry.ttl_s) immediately after).
  • Appends to and potentially truncates _feedback_log.
  • Logs at DEBUG level.

Thread Safety

Thread-safe for its own internal counters/log (protected by self._lock). Not an atomic guarantee for the passed-in entry object itself if the same entry is being mutated concurrently by another code path outside this method's lock.

Example

Python · 7 lines
from zerda.cache.policy_learner import CachePolicyLearner, FeedbackSignal
from zerda.cache.config_cache import RLConfig

learner = CachePolicyLearner(RLConfig())
signal = FeedbackSignal(entry_id="abc", tenant_id="acme", positive=True, magnitude=0.8)
learner.record_feedback(entry, signal)
print(entry.confidence_score, entry.bandit_arm.expected_reward)

rank_candidates(self, candidates: List[Tuple[str, float, IntelligentCacheEntry]]) -> List[Tuple[str, float, IntelligentCacheEntry]]

Overview

Re-ranks a list of (entry_id, similarity, entry) semantic-search candidates by combining cosine similarity with a Thompson-sampled reward draw and the entry's confidence score, returning the same tuple shape sorted descending by composite score.

Algorithm

For each candidate:

Text · 6 lines
ts_reward = entry.bandit_arm.sample_reward()     # fresh Beta-distribution draw
composite = (
    similarity
    + config.similarity_bonus_scale * ts_reward
    + 0.1 * entry.confidence_score
) / (1 + config.similarity_bonus_scale + 0.1)

The denominator normalizes the composite back toward the similarity's original scale, assuming ts_reward and confidence_score are both in [0, 1] (true for ts_reward, which is a Beta-distribution draw, and for confidence_score, which _compute_confidence clips to [0, 1]).

Complexity

  • Time: O(n log n) — a linear pass to compute composite scores plus a sort.
  • Space: O(n) for the intermediate scored list.

Thread Safety

No locking — this is a pure function of its inputs plus a numpy random draw per candidate (np.random.beta uses the global NumPy random state, which is not thread-safe against concurrent draws from multiple threads without independent generators — see Known Issues).

Example

Python · 5 lines
ranked = learner.rank_candidates([
    ("id1", 0.91, entry1),
    ("id2", 0.88, entry2),
])
best_id, best_sim, best_entry = ranked[0]

eviction_ranking(self, entries: List[Tuple[str, IntelligentCacheEntry]], n_to_evict: int) -> List[EvictionCandidate]

Overview

Selects up to n_to_evict entries that are the best candidates for removal, called from CacheManager._evict_cycle() during the periodic background eviction pass.

Algorithm

For each (key, entry):

  • Fast path: if entry.bandit_arm.expected_reward < config.min_reward_to_keep (default 0.05), assign it score = -1.0 — guaranteeing it sorts to the very front of the ascending-sorted list (i.e. evicted first), bypassing the full composite calculation.
  • Otherwise: compute entry.eviction_score(decay=config.usage_decay) (see IntelligentCacheEntry.eviction_score), using that method's own default weights (reward_w=0.50, usage_w=0.30, recency_w=0.20) — the EvictionConfig's corresponding weight fields are not passed through here.

Sorts ascending by score (lowest/most-expendable first) and returns the first n_to_evict candidates.

Complexity

O(n log n) for the sort, O(n) for scoring.

Example

Python · 5 lines
candidates = learner.eviction_ranking(
    entries=[("key1", entry1), ("key2", entry2), ("key3", entry3)],
    n_to_evict=1,
)
worst = candidates[0]   # EvictionCandidate(entry_id=..., key=..., score=...)

auto_decay(self, entries: List[IntelligentCacheEntry]) -> None

Overview

Applies time-based multiplicative decay to every entry's bandit arm, shrinking both alpha and beta back toward their configured priors. Intended to be called periodically (the module docstring suggests every 5 minutes) so that old, hot entries don't permanently dominate on the strength of stale evidence.

Algorithm

Text · 4 lines
excess_alpha = arm.alpha - config.prior_alpha
excess_beta  = arm.beta  - config.prior_beta
arm.alpha = config.prior_alpha + excess_alpha * decay
arm.beta  = config.prior_beta  + excess_beta  * decay

where decay = config.usage_decay (default 0.995). This shrinks the excess above the prior geometrically, rather than the raw values, so alpha/beta asymptotically approach (but never go below) the prior.

Side Effects

Mutates every entry's bandit_arm in place, under self._lock. Called from CacheManager._evict_cycle() on every entry that survived the eviction pass — but note that _evict_cycle does not persist these decayed values back to storage afterward (see Known Issues).

get_stats(self) -> Dict[str, object]

Returns {total_feedback, positive_feedback, negative_feedback, positive_rate, recent_signals}, where recent_signals is simply len(self._feedback_log) (capped at 10,000).

_compute_confidence(self, entry: IntelligentCacheEntry) -> float (private)

Text · 3 lines
usage_credibility = min(1.0, log1p(usage_count) / log1p(50))
raw = 0.40*expected_reward + 0.25*similarity_score + 0.25*quality_score + 0.10*usage_credibility
confidence = clip(raw, 0.0, 1.0)

Combines four signals into one number: how well the bandit arm has performed, how similar the query was at insertion time, an externally supplied quality score, and how much usage history backs the estimate (log-scaled, saturating around 50 uses).

Thread Safety Summary

MethodThread-safe?
record_feedbackYes (own state); entry mutation itself isn't separately locked
rank_candidatesYes for its own logic; relies on global NumPy RNG state, which is not independently thread-isolated
eviction_rankingYes (pure computation over provided data)
auto_decayYes (own state via self._lock)
get_statsYes (own state via self._lock)

Related pages