How Karukan's Learning Cache Eviction Works When Exceeding the Maximum Entries

When Karukan's learning cache exceeds its configured limit (default 10,000 entries), it automatically evicts the lowest-scoring entries based on a weighted combination of recency and frequency before persisting to disk.

Karukan is an open-source Japanese input method engine that tracks user-selected conversion pairs to improve prediction accuracy. The learning cache stores (reading → surface) mappings with frequency counters and timestamps, but to prevent unbounded memory growth, the system implements an intelligent eviction algorithm. This process ensures that the most relevant conversion patterns survive while pruning rarely used entries.

The Eviction Algorithm in LearningCache::evict

The eviction logic is implemented in the evict method within karukan-engine/src/learning.rs (lines 84-125). When the cache size exceeds the configured max_entries threshold, the algorithm systematically identifies and removes the lowest-value entries through a multi-phase scoring process.

Entry Scoring Based on Recency and Frequency

Each cache entry receives a composite score calculated by the score helper function (lines 127-140). The scoring formula balances two critical usage patterns:

• Recency: Calculated as 1 / (1 + age_in_days), where newer entries approach a value of 1.0 while older entries decay toward zero
• Frequency: Calculated as ln(1 + frequency_count), applying a logarithmic scale to prevent high-frequency entries from completely dominating the ranking

The final ranking score is computed as: recency * 10.0 + frequency. This weighting gives recent selections ten times more influence than historical frequency, ensuring that temporarily trending conversions are preserved while abandonning stale entries.

Sorting and Removal Process

The eviction process executes the following steps:

1. Count current entries using entry_count() to tally all stored (reading, surface) pairs across the entire cache
2. Early exit if the total count is ≤ max_entries, avoiding unnecessary computation
3. Score every entry using the timestamp and frequency data
4. Sort ascending by score into a vector where the lowest-scoring (least valuable) entries appear first
5. Calculate removal target as to_remove = total_entries - max_entries
6. Group indices by reading for the lowest-scoring entries to prepare for batch deletion
7. Execute removal by sorting each reading's index list in reverse order and removing from the inner Vec<LearningEntry>. This reverse-order deletion preserves the validity of remaining indices. Readings with empty vectors are removed from the outer HashMap

When Eviction Triggers

According to the Karukan source code, eviction does not run continuously during runtime. Instead, the evict method is invoked automatically within save() before persisting to disk. This design ensures that the serialized cache file never exceeds the 10,000-entry limit, keeping storage I/O efficient and preventing unlimited growth across application restarts.

Practical Example

The following Rust code demonstrates how the eviction algorithm behaves when inserting more entries than the configured limit allows:

use karukan_engine::learning::LearningCache;

// Create a cache with a small limit for demonstration
let mut cache = LearningCache::new(3);

// Record several entries – some will be boosted later
cache.record("a", "A");
cache.record("b", "B");
cache.record("c", "C");
cache.record("d", "D");
cache.record("e", "E");

// Boost a couple of entries so they get higher scores
cache.record("a", "A"); // frequency now 2
cache.record("a", "A"); // frequency now 3
cache.record("c", "C"); // frequency now 2

// Save triggers eviction; only the three highest‑scoring entries survive
let tmp = tempfile::NamedTempFile::new().unwrap();
cache.save(tmp.path()).unwrap();

assert!(cache.entry_count() <= 3);

In this example, entries "a" and "c" survive due to their boosted frequency scores, while the singleton entries "b", "d", and "e" are candidates for removal based on their lower composite scores.

Summary

• Location: The eviction algorithm is implemented in karukan-engine/src/learning.rs within the LearningCache::evict method (lines 84-125)
• Trigger: Eviction runs automatically when save() is called if the entry count exceeds max_entries (default 10,000)
• Scoring: Entries are ranked using recency * 10.0 + ln(1 + frequency), prioritizing recent usage over historical frequency
• Removal: The lowest-scoring entries are removed in reverse index order to maintain data structure integrity
• Safety: The algorithm includes an early-exit check to skip processing when the cache is within bounds

Frequently Asked Questions

How does Karukan decide which entries to keep during eviction?

Karukan keeps entries with the highest composite scores, calculated from a combination of recency (how recently the conversion was used) and frequency (how often it has been selected). The scoring formula recency * 10.0 + ln(1 + frequency) gives recent entries significantly more weight than older ones, ensuring that currently relevant conversion patterns are preserved while outdated entries are purged.

What is the default maximum learning cache size?

The default maximum is 10,000 entries, defined in the LearningCache constructor in karukan-engine/src/learning.rs (lines 41-48). When this limit is exceeded during the save operation, the eviction algorithm automatically removes the lowest-scoring entries to bring the count back within bounds.

Can the maximum cache size be configured?

Yes, the maximum cache size is configurable through the max_entries parameter passed to LearningCache::new(). The source code shows this is a constructor parameter (lines 41-48), allowing developers to instantiate caches with custom limits appropriate for their memory constraints or usage patterns.

Does eviction happen during runtime or only when saving?

Eviction occurs only during the save operation. The save() method calls self.evict() before writing to disk (as implemented in karukan-engine/src/learning.rs). This design means the cache can temporarily grow beyond max_entries during active use, but the persisted state will always respect the configured limit.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}