CacheMind: From Miss Rates to Why - Natural-Language, Trace-Grounded Reasoning for Cache Replacement

Improving a CPU's cache replacement policy — which cached block to evict — means understanding why a policy misses, but the only way to find out was to hand-parse millions of trace entries from a simulator, getting miss-rate numbers rather than explanations; this paper (North Carolina State University — Kaushal Mhapsekar, Samira Mirbagher-Ajorpaz, and colleagues) presents CacheMind, a conversational tool that lets an architect ask plain-English questions like why a given program counter causes evictions and get answers grounded in the actual trace, by using retrieval-augmented generation to boil millions of trace entries down to a small, verifiable slice that a large language model explains — plus CacheMindBench, the first verified benchmark for LLM reasoning about cache replacement.

The argument in one glance

Problem

You can measure that a cache misses, but not easily learn why

A CPU cache holds recently used data, and when it fills up it must evict something to make room; the cache replacement policy decides which block to evict. Good replacement matters a lot for performance, and it is a hard problem, usually solved with hand-crafted heuristics that leave performance on the table. To improve a policy, an architect needs to understand why it misses — for example, why the memory accesses from a particular instruction (identified by its program counter, or PC) keep causing evictions. But the only way to investigate is to analyze cache traces: the record of every memory access a program makes, produced by simulators such as ChampSim (trace-driven) or gem5 (cycle-accurate). These traces contain millions of entries, and answering a "why" question means parsing them with manual filtering — writing scripts, slicing by PC or address, computing statistics by hand. This is slow, non-interactive, and hard to trust, and at the end it gives you miss-rate numbers, not explanations. There was a gap between the numbers you can measure and the causal understanding an architect actually needs.
What people did

Parse traces by hand, or learn a policy directly from them

Two lines of work exist. To understand behavior, architects manually inspect traces offline — filtering millions of entries, computing reuse statistics, and correlating misses with PCs and addresses using custom scripts. Separately, to improve replacement, recent work learns policies directly from traces: Hawkeye trains an online classifier on Belady-guided labels, Glider distills deep models into compact online policies, and PARROT frames replacement as imitation learning of Belady's optimal.
Why it fell short

Manual analysis does not scale, and learned policies do not explain

Neither line answers the architect's "why." Manual trace inspection is slow and non-interactive: every new question requires new filtering over millions of entries, and comparing policies across workloads becomes an exercise in bespoke scripting that is hard to reproduce and hard to trust. Learned replacement policies improve miss rates, but they are black boxes — they predict which block to evict without producing a human-readable, program-level explanation of why, so they do not help an architect reason about the cause or design a better heuristic. What was missing is an interactive way to ask arbitrary, causal questions about cache behavior in natural language — "why is this PC causing evictions?", "how do these two policies differ on this workload?" — and get answers that are grounded in the actual trace, verifiable against ground truth, and linked to program semantics. Turning raw miss statistics into trustworthy explanations, on demand, is the missing capability.
This paper's idea

Ask the trace questions in English, answered by grounded LLM retrieval

CacheMind is a conversational tool that lets an architect ask natural-language questions about cache behavior and get trace-grounded answers, using retrieval-augmented generation (RAG) with large language models (LLMs). RAG means the system does not ask the LLM to answer from memory; instead it first retrieves the relevant facts from a trusted source and gives them to the LLM to reason over. Here, a natural-language query is parsed and routed to a retriever that searches an external store of trace-derived artifacts — per-PC slices, reuse statistics, metadata, miss rates — distilled from ChampSim or gem5 traces. The retriever boils millions of trace entries down to a narrow, verifiable slice relevant to the question, applying symbolic filters (policy, workload, PC, address) and, where useful, semantic ranking, and assembles a compact context bundle. That context conditions the generator, an LLM (the authors use GPT-4o), which produces a trace-grounded, context-aware answer tied to the actual trace, which curbs hallucination and makes answers checkable. CacheMind offers two retrievers: CacheMind-Sieve, which uses symbolic plus semantic filtering, and CacheMind-Ranger, an LLM-based retriever that dynamically generates and executes the retrieval. To evaluate reasoning rigorously, the authors also build CacheMindBench, the first verified benchmark suite for LLM reasoning about cache replacement — 100 questions spanning factual retrieval, policy and workload comparison, arithmetic, adversarial trick checks, and causal reasoning, each verifiable against ground-truth traces. With Ranger, CacheMind reaches 89.33 percent on unseen trace-grounded questions and 100 percent accuracy on 4 of 6 categories, far above a standard RAG tool.

Why this problem is worth solving

Cache replacement is a stubborn, high-impact microarchitecture problem, and improving it depends on understanding behavior that is buried in enormous traces.

The CPU cache is what keeps a processor fed with data; when it must evict a block to make room, the replacement policy’s choice can be the difference between a fast hit and a slow trip to memory. Decades of hand-crafted heuristics (least-recently-used and its many refinements) have chipped away at this, but they still leave performance unrealized, which is why the field keeps searching for better policies. Designing a better policy, though, requires knowing why the current one fails: which instructions generate the problematic accesses, which data has poor reuse, where a policy evicts a block it will soon need again. All of that information lives in cache traces — the complete record of memory accesses from a simulator like ChampSim or gem5 — but a trace for a real workload has millions of entries. Extracting an answer means filtering and correlating that flood of data by hand, and the result is a number, like a miss rate, not an explanation. So the very understanding needed to advance cache replacement is locked behind slow, manual, non-interactive trace analysis. Making that understanding fast, interactive, and trustworthy would directly accelerate the design of better policies, which is why bridging the gap from miss rates to why is worth doing.

The reason existing approaches leave the gap open is that they either do not scale or do not explain.

Consider the two things architects do today. To understand behavior, they inspect traces manually: write a script to slice the trace by program counter, compute reuse distances, tally evictions per address, and eyeball the correlations. This works for one question at a time, but it does not scale — every new question means new filtering over millions of entries, comparisons across workloads become brittle bespoke pipelines, and nothing about the process is interactive or easy to trust or reproduce. To improve replacement, recent research learns policies straight from traces, and these methods do raise performance: Hawkeye learns from labels derived from Belady’s optimal policy (which evicts the block reused furthest in the future), Glider compresses deep models into small online predictors, and PARROT treats replacement as imitating Belady. But a learned policy is a black box that outputs an eviction decision, not a sentence explaining why; it improves the miss rate without giving the architect any causal, program-level insight to reason about or to turn into a better design. So one path is unscalable and the other is inscrutable, and neither lets an architect simply ask, in plain language, why the cache is behaving as it does and receive a grounded, checkable answer. That interactive, explanatory capability is precisely what has been absent.

What people did before, and where it broke

Manual, script-based trace analysis. Filter millions of trace entries by PC and address, compute reuse statistics, and correlate by hand. Where it broke. It is slow and non-interactive; each new question needs new filtering, and cross-workload comparisons become brittle, hard-to-trust bespoke pipelines that yield numbers, not explanations.
Learned replacement policies (Hawkeye, Glider, PARROT). Train models on traces, often against Belady-optimal labels, to predict better evictions. Where it broke. They improve miss rates but are black boxes: they output an eviction decision, not a human-readable, causal explanation an architect can reason about or turn into a design.
Off-the-shelf retrieval-augmented generation (for example, LlamaIndex). Point a general RAG tool at the trace data and ask questions. Where it broke. General RAG is not precise enough for this domain — a standard tool retrieved the right evidence only about 10 percent of the time, far too unreliable for trustworthy cache-replacement analysis.
Rely on aggregate metrics like miss rate. Use summary statistics to judge and compare policies. Where it broke. A miss rate tells you that a policy is worse, not why; it hides the per-PC, per-address causes that would guide a fix.
The gap. No tool let an architect ask arbitrary causal questions about cache behavior in natural language and get answers grounded in the actual trace, verifiable against ground truth, and linked to program semantics.

How CacheMind works

From a natural-language question to a trace-grounded answer

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Bring natural-language LLM reasoning to a problem that was numbers-only. CacheMind’s founding move is to let architects interrogate cache behavior in plain English, using an LLM to turn a domain that required hand-written scripts into a conversation. Applying large language models to a low-level systems and hardware task that was previously the province of expert manual effort is the same shift the work on fuzzing compilers with large-language-model-generated mutations covered elsewhere on this site represents, putting an LLM to work inside a systems-tooling loop. CacheMind aims that capability at cache-trace analysis, so a question that once meant writing a filtering pipeline becomes a sentence.

Replace hand-crafted heuristics with data-driven understanding of the memory system. The broader thrust is to move cache and memory-system design away from fixed, hand-tuned heuristics and toward learning directly from observed behavior — CacheMind on the analysis side, and the learned policies it complements on the decision side. Learning the memory system’s behavior from real access patterns instead of relying on a static, hand-crafted rule is the same principle the work on practical real-time learning for data prefetching covered elsewhere on this site is built on, letting observed behavior drive the policy. CacheMind contributes the explanatory half: it helps architects see, in program terms, what the data actually says.

Turn raw traces into causal, human-readable explanations. At its core CacheMind answers “why,” converting a mountain of low-level trace events into a grounded account of what caused a behavior — the same jump from symptoms to root cause that trace analysis aims for elsewhere. Reasoning over voluminous execution traces to explain why something happened, rather than merely reporting that it did, is the same goal the work on a trace-based root-cause analysis system for large-scale microservices covered elsewhere on this site pursues, distilling traces into a diagnosis. CacheMind does this for cache replacement, with retrieval-augmented generation grounding every explanation in the trace so it can be verified.

Following a question through CacheMind

Asking why one instruction keeps causing evictions

A trace, drawn from the paper, of how CacheMind answers a causal question with grounded evidence.

Step 1 of 5

The architect asks a plain-English question

Instead of writing a script, the architect types: "Why is the memory access associated with PC X causing more evictions?" CacheMind parses this natural-language query and routes it to a retriever.

The question is causal and specific to a program counter, the kind manual analysis handles poorly.

Why it works

Retrieval grounds the answer in real trace data. An LLM asked to answer from memory would hallucinate about a specific trace → but retrieval-augmented generation feeds it the actual retrieved facts → so the explanation is tied to ground truth and can be verified.
Filtering makes millions of entries tractable. An LLM cannot ingest millions of trace entries in its limited context → but the retriever boils them down to a narrow, relevant slice → so only the evidence that matters for the question reaches the model.
Symbolic filters give precision a generic RAG lacks. General retrieval matched the right evidence only about 10 percent of the time → but symbolic filters on policy, workload, PC, and address pinpoint the relevant slices → so CacheMind’s retrievers reach far higher precision (Ranger about 90 percent).
Natural language makes analysis interactive. Each manual question needed a fresh filtering script → but a parsed English query is routed and answered on the spot → so architects can explore per-PC, per-address behavior conversationally.
A verified benchmark keeps the reasoning honest. LLM answers can sound right while being wrong → but CacheMindBench scores answers against ground-truth traces across factual, comparative, and causal categories → so accuracy is measured rather than assumed.

What it costs (trade-offs and scope)

It analyzes and explains; it does not directly run a new cache in hardware. CacheMind is a reasoning and analysis tool over simulator traces (ChampSim, gem5), aimed at helping architects understand behavior and find actionable insights; it complements learned replacement policies rather than being a deployed hardware policy itself.
Answer quality depends on the retriever and the model. Accuracy varies with which retriever is used — Ranger reaches 89.33 percent on trace-grounded questions where Sieve reaches 66.67 percent — and on the underlying LLM (GPT-4o); a weaker retriever or model, or questions outside the artifact store, would yield worse or ungrounded answers.
It requires pre-processing traces into an artifact store. The speed comes from distilling traces into per-PC slices, reuse statistics, and metadata ahead of time; questions must be answerable from those artifacts, and building and schema-designing the store is upfront work per workload and simulator.
Grounding reduces but does not eliminate LLM error. Retrieval curbs hallucination by tying answers to evidence, but the LLM still interprets that evidence, so answers can be wrong (the benchmark exists precisely to measure this), and adversarial “trick” questions are included because such systems can be fooled.
The results are on this benchmark and setup. The reported accuracies and the comparison to a general RAG tool (about 10 percent retrieval success) are on CacheMindBench with the authors’ artifacts and models; other question sets, workloads, or tools could shift the numbers.

The evaluation

Answering why a cache behaves as it does

Property	Manual trace analysis	Off-the-shelf RAG (LlamaIndex)	CacheMind (Ranger)
Ask questions in natural language
Answers grounded in the actual trace
Retrieval success (finding the right evidence)
Interactive and reproducible
Reasoning accuracy (CacheMindBench)

A comparison of ways to understand cache behavior. CacheMind uses domain-specific retrieval-augmented generation to answer natural-language questions with trace-grounded evidence, reaching about 90 percent retrieval success and 89.33 percent accuracy on unseen trace-grounded questions with the Ranger retriever, versus about 10 percent retrieval success for a general RAG tool, evaluated on the verified CacheMindBench suite.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (arXiv:2602.12422). The mechanism described is the paper’s: CacheMind is a conversational tool that uses retrieval-augmented generation (RAG) and large language models (LLMs) to enable semantic, trace-grounded reasoning over cache traces for the cache replacement problem. A natural-language query is parsed and routed to a retriever that searches an external store of trace-derived artifacts (per-PC slices, reuse statistics, metadata, miss rates) distilled from ChampSim or gem5 traces, applies symbolic filters (policy, workload, PC, address) and semantic ranking to assemble a compact context bundle, and conditions a generator LLM (GPT-4o) to produce a trace-grounded answer. It provides two retrievers, CacheMind-Sieve (symbolic plus semantic filtering) and CacheMind-Ranger (LLM-guided generation and execution), and the authors introduce CacheMindBench, described as the first verified benchmark suite for LLM-based reasoning about cache replacement, spanning factual retrieval, policy and workload comparison, arithmetic, adversarial checks, and causal reasoning. Reported results include: with Sieve, 66.67 percent on 75 unseen trace-grounded questions and 84.80 percent on 25 unseen policy-specific reasoning tasks; with Ranger, 89.33 percent and 64.80 percent respectively, plus 100 percent on 4 of 6 categories in the trace-grounded tier; and retrieval success of about 60 percent (Sieve) and 90 percent (Ranger) versus about 10 percent for LlamaIndex. The paper also reports actionable insights such as identifying bypass candidates and stable low-reuse-distance PCs. Exact schemas, prompts, workloads, and full results should be read from the paper.

Background

Why systems research is starting to talk to its own data

It helps to see CacheMind as an early example of a broader change: using large language models not to write programs but to help experts understand systems. Computer architecture and systems generate staggering volumes of low-level data — traces, counters, logs, simulator output — that hold the answers to why a design behaves as it does, but extracting those answers has always demanded painstaking manual analysis by specialists. Retrieval-augmented generation offers a new interface to that data: instead of the model guessing, it retrieves the relevant ground-truth facts and reasons over them, which is what makes its answers checkable rather than fabricated, a crucial property when the stakes are a hardware design decision. The pattern — distill the raw data into an indexed store, retrieve a small verifiable slice per question, and let a language model explain it — is likely to recur across performance debugging, security analysis, and design-space exploration, wherever the bottleneck is human understanding of huge low-level datasets. The broader move to turn mountains of execution data into actionable, human-readable guidance for the engineer is the same undertaking the work on guiding memory optimization for GPU-accelerated applications covered elsewhere on this site pursues, converting profiling data into direction rather than raw numbers. CacheMind brings that spirit to cache replacement and, with CacheMindBench, insists on measuring whether the reasoning is actually correct.

If you remember only three things

1. Improving CPU cache replacement — which block to evict — requires understanding why a policy misses, but the only way to investigate was to hand-parse cache traces (millions of memory-access entries from simulators like ChampSim or gem5) with manual filtering. That process is slow, non-interactive, and yields miss-rate numbers, not explanations; and learned replacement policies improve miss rates but are black boxes that do not explain why. There was no way to ask, in plain language, why a given program counter or access pattern causes evictions and get a trustworthy, trace-grounded answer.
2. CacheMind is a conversational tool that uses retrieval-augmented generation (RAG) with an LLM (GPT-4o) to reason over cache traces. A natural-language query is routed to a retriever that searches an external store of trace-derived artifacts (per-PC slices, reuse statistics, metadata), applies symbolic filters and semantic ranking to boil millions of entries into a small verifiable slice, and conditions the LLM to produce a human-readable, trace-grounded answer that curbs hallucination and is checkable. It offers two retrievers — Sieve (symbolic plus semantic) and Ranger (LLM-guided) — and the authors build CacheMindBench, the first verified benchmark for LLM reasoning about cache replacement.
3. With Ranger, CacheMind reaches 89.33 percent on unseen trace-grounded questions and 100 percent accuracy on 4 of 6 categories, with about 90 percent retrieval success versus about 10 percent for a general RAG tool, on the 100-question CacheMindBench suite; it also surfaces actionable insights like bypass candidates and stable low-reuse-distance PCs. It is an analysis and explanation tool (complementing learned policies, not a deployed hardware policy), its accuracy depends on the retriever and model, and it requires pre-processing traces into an artifact store.

Check yourself

Check your understanding

1. Why was understanding cache-replacement behavior so hard before CacheMind?
2. How does CacheMind answer natural-language questions about cache behavior?
3. What is CacheMindBench, and why does the paper introduce it?
4. Predict: someone points a general-purpose retrieval-augmented-generation tool (like LlamaIndex) at the same cache traces and asks CacheMind's questions. How well should it do, and why?

Sources

The paper is “CacheMind: From Miss Rates to Why - Natural-Language, Trace-Grounded Reasoning for Cache Replacement” by Kaushal Mhapsekar, Azam Ghanbari, Bita Aslrousta, and Samira Mirbagher-Ajorpaz (North Carolina State University), published at ASPLOS 2026, DOI 10.1145/3779212.3790136. It is licensed CC BY.

This explainer is written from the paper’s full text (arXiv:2602.12422). Cache replacement is a challenging CPU-microarchitecture problem, often addressed with hand-crafted heuristics, and understanding cache behavior requires parsing millions of trace entries with manual filtering, making the process slow and non-interactive. CacheMind is a conversational tool that uses retrieval-augmented generation (RAG) and large language models (LLMs) to enable semantic, trace-grounded reasoning over cache traces: a natural-language query is parsed and routed to a retriever that searches an external store of trace-derived artifacts (per-PC slices, reuse statistics, metadata, miss rates) distilled from ChampSim or gem5 traces, applies symbolic filters (policy, workload, PC, address) and semantic ranking to assemble a compact context bundle, and conditions a generator LLM (GPT-4o) to produce a trace-grounded, verifiable answer. It provides two retrievers, CacheMind-Sieve (symbolic plus semantic filtering) and CacheMind-Ranger (LLM-guided generation and execution). The authors also present CacheMindBench, described as the first verified benchmark suite for LLM-based reasoning about cache replacement, with 100 questions spanning factual retrieval, policy and workload comparison, arithmetic, adversarial checks, and causal reasoning. Reported results: with Sieve, 66.67 percent on 75 unseen trace-grounded questions and 84.80 percent on 25 unseen policy-specific reasoning tasks; with Ranger, 89.33 percent and 64.80 percent respectively, and 100 percent on 4 of 6 categories in the trace-grounded tier; retrieval success of about 60 percent (Sieve) and 90 percent (Ranger) versus about 10 percent for LlamaIndex; plus actionable insights such as identifying bypass candidates and stable low-reuse-distance program counters. No numbers beyond the paper’s own have been introduced; exact schemas, prompts, workloads, and full results should be confirmed in the paper.