Hashing and caching for LLM apps: exact-match and LRU caches
An exact-match cache hashes everything that changes the answer (model, prompt version, normalised input, parameters) and stores the response under that key, so a repeated request costs nothing and returns in milliseconds. An LRU cache, built from a hash map plus a doubly linked list, keeps memory bounded by evicting the least recently used entry. Start with exact match, measure the hit rate, and add a semantic cache only if paraphrased repeats are common and a wrong hit is acceptable.
What goes into the key
The key must include everything that can change the answer, or the cache returns a stale or wrong response.
- Model name and version
- Prompt template version
- System prompt
- Normalised user input (trimmed, lowercased where case doesn't matter, whitespace collapsed)
- Parameters like temperature and max tokens
- Tenant or user, when answers depend on permissions
Leave out anything that doesn't change the answer, like a request ID, or the hit rate drops to zero.
LRU with a TTL
import hashlib
import json
import time
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int, ttl_seconds: float):
self.capacity = capacity
self.ttl = ttl_seconds
self.items: OrderedDict[str, tuple[float, str]] = OrderedDict()
self.hits = 0
self.misses = 0
def get(self, key: str) -> str | None:
entry = self.items.get(key)
if entry is None or time.monotonic() - entry[0] > self.ttl:
self.items.pop(key, None)
self.misses += 1
return None
self.items.move_to_end(key)
self.hits += 1
return entry[1]
def put(self, key: str, value: str) -> None:
self.items[key] = (time.monotonic(), value)
self.items.move_to_end(key)
if len(self.items) > self.capacity:
self.items.popitem(last=False)
def cache_key(model: str, prompt_version: str, user_input: str, params: dict) -> str:
normalised = " ".join(user_input.lower().split())
payload = json.dumps([model, prompt_version, normalised, params], sort_keys=True)
return hashlib.sha256(payload.encode()).hexdigest()
def fake_llm(text: str) -> str:
return f"answer to: {text}"
cache = LRUCache(capacity=2, ttl_seconds=3600)
for question in ["What is the refund policy?", "what is the refund policy?", "Shipping times?", "Do you ship abroad?", "What is the refund policy?"]:
key = cache_key("model-a", "v3", question, {"temperature": 0})
answer = cache.get(key)
if answer is None:
answer = fake_llm(question)
cache.put(key, answer)
print(f"hits {cache.hits}, misses {cache.misses}, size {len(cache.items)}")
The second question hits because normalisation makes it identical to the first. The last one misses because, with capacity 2, the refund answer was evicted.
OrderedDict is a hash map plus a doubly linked list underneath, which gives O(1) lookup, move-to-front and eviction.
In production, the same structure lives in Redis with maxmemory-policy allkeys-lru and a TTL per key.
Cache layers in an LLM app
| Layer | Matches | Saves |
|---|---|---|
| Exact-match response cache | Identical normalised requests | The whole call |
| Semantic cache | Similar meaning, above a threshold | The whole call, with risk of a wrong hit |
| Provider prompt caching | Identical prompt prefix | Part of input cost and latency |
| Embedding cache | Identical text to embed | Embedding calls during re-indexing |
| Retrieval cache | Identical query and filters | Vector search |
When not to cache
- Answers that depend on live data (stock, balances, order status), unless the TTL is shorter than how often the data changes.
- Personalised answers, unless the user or tenant is part of the key.
- High-temperature creative outputs, where users expect variety.
Check your understanding
Add the tenant ID to the key and explain what would go wrong if you left it out in a multi-tenant app.
From the floor
In the AI data structures lecture, I used a hash as the example of a discrete structure: the hash of "cat" lets you find "cat" and nothing else, and that limitation is exactly what makes an exact-match cache safe, because it only returns an answer for a request that's truly the same.