Semantic caching answers a new query from a cache of past (query, response) pairs whenever some cached query is "close enough" in embedding space — not just on exact string match. This repository is the code artifact behind the paper below: nine unified query workloads, an embedding pipeline, three interchangeable vector-index backends, three offline (clairvoyant) cache-replacement heuristics, seven novel online policies, and seven classic cache-replacement policies adapted to semantic caching.
The paper's two headline results, both reproducible from this code (see
Reproducing the paper): computing the semantic
analogue of Belady's OPT (termed VOPT) is NP-hard and inapproximable
within a factor better than 1 - 1/e unless P = NP; and among online
policies, frequency-based schemes dominate these workloads, with the paper's
novel SphereLFU achieving the lowest mean hit distance on seven of the
nine datasets.
The offline heuristics (CRVB, FGRVB, RGRVB) consistently beat every online policy on hit rate, which the paper reads as room left for future online policy design, not as a ceiling this code has reached.
ELI5 at D_thresh = 0.9: offline heuristics (top band, left) dominate hit
rate, but SphereLFU (pink, right) has the lowest mean hit distance of any
policy — generated by this repo's own pipeline (see
Reproducing the paper) and shipped in figures/
alongside the code.
Semantic Caching: From Exact Hits to Close Enough Dvir David Biton and Roy Friedman, Technion – Israel Institute of Technology CIKM '26, November 7–11, 2026, Rome, Italy doi:10.1145/3799682.3840580 · local copy
The paper defines a semantic cache by (Dim, N, D_thresh), shows that the
offline-optimal semantic policy (VOPT) is NP-hard to compute or closely
approximate via a reduction from Maximum Coverage, proposes three
polynomial-time clairvoyant heuristics (CRVB, FGRVB, RGRVB) as practical
stand-ins, and evaluates them alongside seven classic and seven novel online
policies on nine real-world query datasets at three semantic thresholds
(D_thresh ∈ {0.5, 0.7, 0.9}).
- Semantic hit — a query is a hit if some cached vector lies within
D_threshof it (as opposed to exact-match caching, where only identical keys hit). D_thresh— the L2-distance admission threshold. For unit-normalized embeddings, L2 distance and cosine similarity are related by a monotonic transform; the paper usesD_thresh ∈ {0.5, 0.7, 0.9}, corresponding to cosine similarities of approximately0.88,0.75, and0.60(strict near-duplicate, balanced semantic equivalence, and high-recall topical relevance, respectively).- Hit rate — fraction of queries answered from the cache.
- Mean hit distance (MHD) — average L2 distance between a query and the cached vector that answered it, on hits only; lower means the cached answer was more precisely relevant, not merely "close enough."
- Offline / clairvoyant vs. online — offline policies (VOPT and its heuristics CRVB/FGRVB/RGRVB) see the entire future request sequence and serve as an upper bound; online policies decide with only past information, as a real cache must.
Every row names the class actually used by the experiment driver
(src/processor.py::_run_single_worker's caches dict), not just a class
that happens to exist in the file.
There is no VOPT class — Theorem 5.1 in the paper proves computing it
exactly is NP-hard, so the repo ships three polynomial-time heuristics
instead.
| Policy | Description | Class | File |
|---|---|---|---|
| CRVB | Clustered Relaxed Vector Belady — greedily extracts maximal cliques from the semantic intersection graph (DSATUR on the complement graph was tried and found impractical at this graph density), then runs exact-match Belady on cluster IDs | ClusterOPT |
src/caches/OPT.py |
| FGRVB | Frequency Greedy Relaxed Vector Belady — evicts the cached vector with the fewest future requests it uniquely covers (greedy maximum-coverage) | FGRVB |
src/caches/OPT.py |
| RGRVB | Recency Greedy Relaxed Vector Belady — evicts the cached vector whose next covered future request is furthest away, admitting a candidate only if its next hit isn't already served by something else in the cache | OPT |
src/caches/OPT.py |
| Policy | Description | Class | File |
|---|---|---|---|
| SphereLFU | Online kernel-density-style LFU: a query distributes fractional "responsibility" mass across all cached vectors within D_thresh, weighted by a Gaussian-like kernel, instead of incrementing one counter per hit |
SphereQueryLFU |
src/caches/cache.py |
| MissLFU | LFU that skips inserting a new vector if a semantically-identical one is already cached | MissLFU |
src/caches/cache.py |
| ClusterLFU | Greedy online clustering; LFU counters and eviction operate per-cluster instead of per-vector | ClusterLFU |
src/caches/cache.py |
| ClusterLRU | Same online clustering as ClusterLFU, LRU instead of LFU per cluster | ClusterLRU |
src/caches/cluster_lru.py |
| DistanceLFU | LFU counter increment weighted by 1 - dist / D_thresh instead of a flat +1 |
DistanceLFU |
src/caches/cache.py |
| Surprisal | Evicts by linguistic surprisal alone (no frequency signal) | Surprisal |
src/caches/cache.py |
| SurprisalLFU | LFU; ties among least-frequent items are broken by highest surprisal | SurprisalLFU |
src/caches/cache.py |
Surprisal is computed from the wordfreq
library's "large" English wordlist (100M-word frequency table with a floor for
unseen tokens) — see src/util/surprisal.py — not from an
LLM, as the paper states.
| Policy | Description | Class | File |
|---|---|---|---|
| LRU | LRU |
src/caches/cache.py | |
| LFU | LFU |
src/caches/cache.py | |
| FIFO | FIFO |
src/caches/cache.py | |
| LFUDA | LFU with dynamic aging | DynamicAgingLFU |
src/caches/cache.py |
| LRU-K | K-th-most-recent-access recency; driver uses K=2 |
LRUK |
src/caches/lru_k.py |
| ARC | Adaptive Replacement Cache (self-tuning T1/T2/B1/B2 lists) | ARC |
src/caches/arc.py |
| RAP | Randomized Admission Policy; replaces the least-used item with probability 1/(C+1) |
RAP |
src/caches/cache.py |
The codebase has several additional cache classes not part of the paper and
not registered in the experiment driver's caches dict: RR (random
replacement), LIFO, SamplingMetaCache (a shadow-cache policy selector),
Dummy, FixedRadius, PCA/BetterTinyLFU/TinyLFU (TinyLFU-style
sketches), CountChars/CountWords, SphereDistanceQueryLFU, and the
LRFU/HillClimbingLRFU/DeltaLRFU family
(src/caches/lrfu.py). src/caches/dist_cache.py's
Distribution cache is a no-op stub. src/caches/cache_kmeans.py has a
broken import (from cache import Cache instead of from caches.cache import Cache) and will not import as-is. src/caches/OPT.py also defines
RelaxedOPT, ClusterRelaxedOPT, and a RelaxedLearnedOPT that trains an
XGBoost regressor (RLB_Reg) to predict time-to-next-hit — an experimental
learned-Belady approach the paper doesn't discuss.
All nine datasets are downloaded via the HuggingFace datasets library and
converted into one canonical HDF5 layout — see Requirements
for the caveat that these files use a .pkl extension despite being HDF5. Only
query text is embedded; answers and supporting documents are discarded.
| Dataset | Source | Queries | Prepared by |
|---|---|---|---|
| ELI5 | sentence-transformers/eli5 (HF) |
Short, colloquial "Explain Like I'm 5" questions | build_eli5() |
| WildChat | allenai/WildChat-1M (HF) |
Real ChatGPT user turns, grouped by session | build_wildchat() |
| NaturalQuestions | nq_open (HF) |
Open-domain Wikipedia QA | build_nq() |
| MS MARCO | ms_marco v2.1 (HF) |
Bing search queries | build_msmarco() |
| StackOverflow | pacovaldez/stackoverflow-questions (HF, from Google BigQuery) |
Programming question titles | build_stackoverflow() |
| Quora Question Pairs | quora (HF) |
User questions, duplicate-annotated | build_quora() |
| MMLU | cais/mmlu config "all" (HF) |
57-subject exam questions | build_mmlu() |
| HotpotQA | hotpot_qa config "distractor" (HF) |
Multi-hop reasoning questions | build_hotpotqa() |
| TriviaQA | mandarjoshi/trivia_qa config "rc" (HF) |
Trivia questions | build_triviaqa() |
All builders and the packing pipeline live in
src/util/fetch_datasets.py. Every dataset is
capped at the first 100,000 queries; NaturalQuestions naturally yields only
91,535 after filtering empty questions (confirmed against the shipped
datasets/embeds_nq.pkl, which has exactly that many rows). A build_qrecc()
function for the QReCC dataset also exists but is unused — it's never called
from fetch_datasets.py's __main__ block and isn't one of the nine
datasets in dataset_filenames.
No Python version is pinned anywhere in the repo (no pyproject.toml,
setup.py, or .python-version); the committed __pycache__ bytecode was
compiled under 3.12, so treat that as the closest thing to a supported
version.
pip install -r requirements.txtrequirements.txt covers everything imported under src/ — verified by
grepping every import/from in the tree, which is how h5py,
scikit-learn, networkx, and seaborn (used by src/processor.py,
src/util/fetch_datasets.py, src/util/analyze_datasets.py,
src/util/reduce_dim.py, src/caches/OPT.py, and src/main.py) ended up
listed alongside the rest.
requirements.txt also lists lightgbm and xgboost, which the paper never
mentions. xgboost is used, but only inside RLB_Reg/RelaxedLearnedOPT
in src/caches/OPT.py — an experimental learned-Belady
predictor that is not registered in processor.py's caches dict and is
never exercised by any driver in src/main.py. lightgbm is imported
(import lightgbm as lgb) in the same file but lgb is never referenced
anywhere — a dead import. Neither package is needed to reproduce anything in
the paper.
FAISS flat is the paper's stated default (Section 7.1), but the actual
sweep in main() (src/main.py) — which regenerates Figures 1 and 2 — sets
the index backend to "HotSwap", i.e. NaiveVectorStore
(src/vector_stores/naive_interface.py),
a pure-NumPy brute-force flat-L2 reimplementation, not FAISS's IndexFlatL2.
Both are exact flat L2 indices, so results should be numerically equivalent,
but be aware the code and the paper's text name different backends for the
same experiment.
Milvus (any "milvus-*" index key) and hnswlib are optional alternates,
selectable only by editing the faiss_indices_names set in the driver
function you run in src/main.py. Milvus requires either a running
standalone server at http://localhost:19530 or the embedded milvus-lite
variant (a local .db file); hnswlib needs no external service.
Resource costs, measured against this checkout:
- Embedding: each dataset is encoded once with SBERT
all-MiniLM-L6-v2(CPU-capable, faster with a GPU); a full 100K-query batch takes a while but is a one-time cost per dataset. - Disk: the nine cached embedding files (
datasets/embeds_*.pkl, actually HDF5) total 4.5 GB on disk (276 MB–1.6 GB each, WildChat being the largest). - Index memory: a flat L2 index over 100,000 × 384 float32 vectors is ≈150 MB in memory; negligible next to the embedding files themselves.
There is no CLI or argparse anywhere in this repo — every entry point is a
plain script invoked as python <path>, with behavior selected by editing
which line is uncommented in its if __name__ == "__main__": block. This is
the smallest command that runs one dataset through one policy at one cache
size end-to-end, confirmed to run against the datasets/embeds_eli5.pkl file
already produced by this checkout:
import sys; sys.path.append("src")
from caches.cache import LFU
from vector_stores.naive_interface import NaiveVectorStore
from util.fetch_datasets import load_embeds
embeds, texts = load_embeds("ELI5", 2000) # first 2000 ELI5 queries
cache = LFU(same_embed_distance=0.9) # D_thresh = 0.9
cache.initialize(capacity=200, index=NaiveVectorStore(dim=384))
hits = 0
for i in range(len(embeds)):
iter_hits, _ = cache.cache(embeds[i:i+1], [i], count_nn=1, texts=[texts[i]])
hits += int(iter_hits[0] > 0)
print(f"hit rate: {hits / len(embeds):.3f}")hit rate: 0.026
This requires datasets/embeds_eli5.pkl to already exist — see
Usage: dataset preparation if it doesn't.
python src/util/fetch_datasets.pyRuns all nine build_*() functions unconditionally (no flags), downloading
each dataset via HuggingFace datasets, embedding queries with SBERT, and
writing datasets/embeds_<name>.pkl. Each dataset is skipped if its output
file already exists (pack_and_dump's writer() context manager). Expect
network access to HuggingFace, several GB of downloads, and — per the 4.5 GB
figure above — several GB of local output.
python src/util/analyze_datasets.pyFor each of the nine datasets: prints a LaTeX table of the Table 1/2 metrics
(cosine similarity avg/std, L2 mean/std, PCA entropy, cluster avg/std at
D_thresh=1, Hopkins statistic) to stdout, and writes
<Dataset>_point_density_distances.png plus density_legend.png to the
repository root (Figure 7 / Appendix C.2's point-density-vs-rank plots across
distance thresholds 0.5–1.4).
python src/main.py # with main() uncommented, plot() commented, in __main__main() sweeps D_thresh ∈ {0.5, 0.7, 0.9} × all nine datasets × 17 cache
policies × 7 cache sizes (steps of num_samples * 0.1 / 8, i.e. roughly
1,250–8,750 for the 100K-query datasets) using 8 parallel processes
(NUM_PROCS = 8 at the top of the file), and appends one JSON record per run
to results_many.json. Other driver functions in the same file follow the
same edit-and-run pattern:
| Function | Purpose |
|---|---|
main() |
The full hit-rate/MHD sweep behind Figures 1, 2, and 8 |
recall() |
Recall@K sweep over a smaller cache-size range, writes results-recall.json |
compare_crvb() |
CRVB/FGRVB/RGRVB hit rate vs. D_thresh (not a numbered paper figure), writes results-crvb.json |
compare_vector_stores() |
Throughput vs. batch size / NN count / cache size across all index backends, writes results_vector_stores.json |
compare_index_runtime() |
Throughput vs. cache size for {HotSwap, faiss, milvus-standalone} — broken: "milvus-standalone" is not a key in the indices dict in src/processor.py (only "milvus-standalone-flat"/"-ivf"/"-hnsw" exist), so this raises KeyError if run as-is |
python src/main.py # with plot() uncommented, in __main__Reads results_many.json and writes one PNG per (metric, D_thresh, dataset) combination to figures/, plus a shared figures/legend.png.
Companion plotting functions (plot_compare_vector_stores(),
plot_compare_index_runtime(), plot_compare_crvb()) follow the same
uncomment-and-run pattern against their respective results_*.json files.
| Parameter | Where it's set | Default |
|---|---|---|
D_thresh (same_embed_distance) |
Positional constructor arg to every Cache subclass |
None — required; drivers sweep {0.5, 0.7, 0.9} |
Cache size N (capacity) |
cache.initialize(capacity, index) |
None — required; main() sweeps ~1,250–8,750 |
| Embedding model | embed_strings(model_name=...) in src/util/fetch_datasets.py |
"all-MiniLM-L6-v2" |
| Index backend | Key into the indices dict in src/processor.py |
Driver-dependent; main() uses "HotSwap" |
| Cache policy | Key into the caches dict in src/processor.py |
Driver-dependent |
| Dataset | Key into dataset_filenames in src/util/fetch_datasets.py |
n/a |
SphereLFU alpha |
SphereQueryLFU.update_counters |
1e-3 (matches the paper) |
SphereLFU kappa |
Same method, derived if unset | 2 / D_thresh² (matches the paper) |
SphereLFU decay (gamma) |
halve_counters() halves all counters once accumulated hits reach capacity |
γ=1 — no decay, matching the paper's evaluation setting |
LRU-K's K |
caches["LRUK"] tuple in _run_single_worker |
2 |
LFUDA half_life |
DynamicAgingLFU.__init__ |
Accepted (driver passes 32) but unused — the docstring says LFUDA doesn't use exponential decay; the real mechanism is the L dynamic-aging counter |
| ARC / RAP hyperparameters | None — ARC self-tunes p; RAP's admission probability is fixed at 1/(C+1) |
n/a |
| Artifact | What it shows | Command | Output | Runtime |
|---|---|---|---|---|
| Table 1 / Table 2 (dataset metrics) | Cosine sim avg/std, L2 mean/std, PCA entropy, cluster avg/std at D_thresh=1, Hopkins statistic, per dataset |
python src/util/analyze_datasets.py |
LaTeX table on stdout | Minutes per dataset (pairwise cosine/L2 over 100K×100K is the dominant cost) |
| Figure 7 / Appendix C.2 (point density vs. rank, per-dataset "expanded analysis") | Point-density-vs-rank curves at distances 0.5–1.4, per dataset | python src/util/analyze_datasets.py (same run as above) |
<Dataset>_point_density_distances.png, density_legend.png at repo root |
Same run as Table 1 |
Figures 1, 2, 8 (hit rate / mean hit distance / throughput vs. cache size, D_thresh ∈ {0.5, 0.7, 0.9}) |
Offline-vs-online hit rate and MHD bands per dataset; throughput per policy | 1) uncomment main() in src/main.py's __main__, run it to produce results_many.json; 2) uncomment plot() instead, run again |
figures/{Hit Rate,Mean Hit Distance,Throughput,...}_{0.5,0.7,0.9}_{Dataset}.png, figures/legend.png |
Full grid: 3 thresholds × 9 datasets × 17 policies × 7 cache sizes ≈ 3,200 runs over up to 100K queries each. Not benchmarked in this README — expect hours on a multi-core CPU, dominated by FGRVB's per-eviction marginal-gain computation (the paper's own Appendix A calls FGRVB the slowest policy) |
Not reproducible from this repo as shipped:
- The paper's Appendix A absolute throughput (OPS) numbers are hardware-specific to the original authors' machine; only relative trends (FGRVB slowest, throughput dominated by NN-search latency) are expected to reproduce.
figures-milvus/(Recall@K, index-runtime, and throughput comparisons across Milvus/hnswlib/FAISS backends) isn't tied to any numbered figure or table in the paper. It's produced bycompare_vector_stores()/compare_index_runtime()/ theirplot_*counterparts and requires a running Milvus standalone server — a real external dependency, not covered above.compare_crvb()/plot_compare_crvb()'sfigures/absolute_hit_rate_comparison.pdfis exploratory (CRVB/FGRVB/RGRVB hit rate asD_threshvaries continuously) and doesn't correspond to a paper figure either.
The paper (Section 4, Section 7) cites this repository as the home for three
things beyond the code: results at D_thresh = 0.7 and 0.5, the complete
unprocessed data, and an expanded dataset analysis beyond Table 1.
D_thresh = 0.7and0.5results (Appendix B, Figures 3–6): present.main()'s sweep already iterates all three thresholds, and this checkout'sfigures/directory containsHit Rate_0.5_*.png,Hit Rate_0.7_*.png,Mean Hit Distance_0.5_*.png, andMean Hit Distance_0.7_*.pngfor every dataset, generated by the pipeline in Reproducing the paper.- Expanded dataset analysis beyond Table 1 (Appendix C): present.
python src/util/analyze_datasets.pyreproduces Table 1/2 and additionally generates the point-density-vs-rank plots behind Figure 7 and Appendix C.2's discussion of MMLU/WildChat's long-tail structure. - Complete unprocessed data: present.
results_many.json— the raw per-run JSON that every figure above is computed from — is shipped in this repository alongside the code, together with thedatasets/embedding files and thefigures/PNGs generated from it.
paper.pdf # the paper (CC BY 4.0)
requirements.txt
src/
main.py # experiment/plotting entry point; edit __main__ to select a driver
processor.py # parallel run harness; owns the `caches` and `indices` registries
caches/
cache.py # Cache base class + most policies (LFU family, LRU, FIFO, RAP, SphereLFU, ...)
OPT.py # offline heuristics: OPT(=RGRVB), ClusterOPT(=CRVB), FGRVB, + experimental learned/relaxed variants
arc.py # ARC
cluster_lru.py # ClusterLRU
lru_k.py # LRU-K
lrfu.py # LRFU family — not used by any driver
cache_kmeans.py # broken import; unused
dist_cache.py # no-op stub; unused
vector_stores/
naive_interface.py # NaiveVectorStore — pure-NumPy flat L2, the "HotSwap" backend actually used by main()
hnswlib_interface.py # hnswlib-backed ANN index
milvus_interface.py # Milvus-backed index (needs a server, or milvus-lite)
util/
fetch_datasets.py # dataset builders + HDF5 packing (dataset_filenames, load_embeds)
analyze_datasets.py # Table 1/2 metrics + point-density figures
surprisal.py # wordfreq-based surprisal scoring
online_clusters.py # greedy online clustering used by ClusterLFU/ClusterLRU
reduce_dim.py # clustering helpers used by CRVB (greedy maximal-clique extraction)
density_estimator.py # KDE-style density estimator (used by analyze_datasets' compare_density_estimator)
hill_climber.py # 1D hill-climbing optimizer used by HillClimbingLRFU (unused driver path)
datasets/ # embeds_<name>.pkl are HDF5, not pickle, despite the extension
figures/ # PNGs from main.py's plot()
figures-milvus/ # vector-store comparison PNGs
New cache policy — subclass Cache in
src/caches/cache.py, implementing:
def initialize(self, capacity: int, index): ...
def cache(self, embeds, embeds_ids, count_nn=1, texts=[]): ...embeds/embeds_ids/texts are always batches (a batch of one is a normal
single query). Use self.get_closest_stored_embeds(...) for a k-NN query and
self.get_in_range_stored_embeds(...) for a range query (SphereLFU's
approach); call self.add_with_ids(...) / self.remove_ids(...) to keep the
backing index in sync. Register the class under a new key in the caches
dict inside _run_single_worker() in
src/processor.py to make it selectable by the drivers in
src/main.py.
New index backend — implement the four methods used throughout the
codebase: add_with_ids(x, ids), remove_ids(ids), search(xq, k), and
range_search(xq, radius, limit=None), matching the shapes and squared-L2
convention in src/vector_stores/naive_interface.py
(the simplest reference implementation). Add a constructor function and a key
in the indices dict in _run_single_worker().
New dataset — add a build_<name>() -> (texts, meta) function to
src/util/fetch_datasets.py returning a flat list
of query strings, call pack_and_dump(...) on it from the module's
__main__ block, and add the output path to dataset_filenames.
@inproceedings{biton2026semantic,
author = {Biton, Dvir David and Friedman, Roy},
title = {Semantic Caching: From Exact Hits to Close Enough},
booktitle = {Proceedings of the 35th ACM International Conference on
Information and Knowledge Management (CIKM '26)},
year = {2026},
address = {Rome, Italy},
publisher = {ACM},
numpages = {11},
isbn = {979-8-4007-2539-5},
doi = {10.1145/3799682.3840580}
}The paper and the code in this repository are both licensed under CC BY 4.0.