Semantic Caching: From Exact Hits to Close Enough

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.

Paper

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}).

Key concepts

• Semantic hit — a query is a hit if some cached vector lies within D_thresh of 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 uses D_thresh ∈ {0.5, 0.7, 0.9}, corresponding to cosine similarities of approximately 0.88, 0.75, and 0.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.

Implemented policies

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.

Offline / clairvoyant heuristics

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

Novel online policies

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.

Classic policies adapted to semantic caching

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

Not wired into the paper's experiments

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.

Datasets

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.

Requirements

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.txt

requirements.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.

Quickstart

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.

Usage

Dataset preparation

python src/util/fetch_datasets.py

Runs 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.

Dataset metrics and expanded analysis (Table 1 / Table 2, Figure 7)

python src/util/analyze_datasets.py

For 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).

Running the experiment sweep

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

Plotting

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.

Configuration

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

Reproducing the paper

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 by compare_vector_stores() / compare_index_runtime() / their plot_* counterparts and requires a running Milvus standalone server — a real external dependency, not covered above.
• compare_crvb() / plot_compare_crvb()'s figures/absolute_hit_rate_comparison.pdf is exploratory (CRVB/FGRVB/RGRVB hit rate as D_thresh varies continuously) and doesn't correspond to a paper figure either.

Supplementary material

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.7 and 0.5 results (Appendix B, Figures 3–6): present. main()'s sweep already iterates all three thresholds, and this checkout's figures/ directory contains Hit Rate_0.5_*.png, Hit Rate_0.7_*.png, Mean Hit Distance_0.5_*.png, and Mean Hit Distance_0.7_*.png for every dataset, generated by the pipeline in Reproducing the paper.
• Expanded dataset analysis beyond Table 1 (Appendix C): present. python src/util/analyze_datasets.py reproduces 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 the datasets/ embedding files and the figures/ PNGs generated from it.

Repository layout

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

Extending

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.

Citation

@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}
}

License

The paper and the code in this repository are both licensed under CC BY 4.0.