STARC: Selective Token Access with Remapping and Clustering for Efficient LLM Decoding on PIM Systems

Zehao Fan, Yunzhen Liu, Garrett Gagnon, Zhenyu Liu, Yayue Hou, Hadjer Benmeziane and 2 others

Processing-in-memory chips compute attention right where the KV cache lives, dodging the memory wall that throttles LLM decoding — but they can only read memory a whole row at a time, so the usual speed trick of attending to just the few important tokens fails, because those tokens are scattered across many rows and the hardware still hauls in everything; this paper (RPI, IBM Research — Zehao Fan, Liu Liu, and colleagues) presents STARC, which clusters semantically similar KV entries and stores each cluster contiguously in a memory row, so a query picks whole relevant rows by matching cluster centroids — cutting attention-layer latency and energy by up to 78 and 65 percent versus token-wise sparsity while keeping accuracy.

The argument in one glance

Problem

LLM decoding is starved for memory bandwidth, and PIM only reads whole rows

When an LLM generates text, it does so one token at a time, and each new token must attend over the Key-Value (KV) cache — the key and value vectors of every earlier token. As context lengths grow into the hundreds of thousands, that cache grows with them, and attention during decoding becomes memory-bound: it does little arithmetic per byte but reads enormous amounts of data, so the compute cores sit idle waiting for memory. Processing-in-memory (PIM) is a natural fix. Instead of shipping the KV cache to a distant processor, PIM puts compute units right next to the memory banks, so attention runs with the memory's huge internal bandwidth rather than the narrow external bus. PIM-enabled systems therefore offload the memory-bound attention to PIM while keeping other work on the GPU or NPU. But PIM has a hard constraint: it reads and computes a whole memory row at a time — a row holds several token vectors together — because that is what makes its bandwidth advantage real. Current PIM attention designs assume dense attention, where every token is used, so reading full rows wastes nothing. The trouble starts when you try to make attention sparse.
What people did

Only attend to the important tokens, as sparse attention already does

Attention scores in LLMs are highly skewed: for any given query, only a small subset of past tokens matter, and the rest receive near-zero weight. Sparse attention exploits this by retrieving only the important KV pairs and skipping the rest, which on a normal processor cuts both memory traffic and computation. Two flavors exist. Token-wise sparsity scores individual tokens (by query-key similarity) and selects the top ones — the most accurate, because it picks exactly the relevant tokens. Page-wise sparsity groups tokens into fixed-size "pages" by their position in the sequence and selects whole pages, which is coarser but simpler.
Why it fell short

Fine-grained sparsity fights PIM's row granularity, and coarse sparsity loses accuracy

Neither kind of sparsity fits PIM well, and the reason is a granularity mismatch. Token-wise sparsity picks the exact right tokens, but those tokens are scattered across the memory — the top tokens for a query end up in many distant rows. Because PIM must read and compute an entire row whether or not its tokens were selected, a scattered selection forces the hardware to activate nearly as many rows as dense attention and compute over mostly-unwanted data: the sparsity is real logically but yields almost no speedup physically, because you cannot skip a row that holds even one selected token. Page-wise sparsity has the opposite problem. Pages are defined by token position, so they align neatly with memory rows and are hardware-friendly — but position has nothing to do with relevance, so a selected page typically contains only one or two tokens that actually matter and many that do not, wasting bandwidth and degrading accuracy. So the field was stuck between accurate-but-PIM-hostile and PIM-friendly-but-inaccurate. What was missing was a way to make the tokens that get selected together also live together in memory.
This paper's idea

Cluster similar KV pairs and store each cluster in its own contiguous rows

STARC is a sparsity-optimized data mapping scheme for PIM. Its insight is to change where KV pairs are stored so that the ones likely to be selected together are physically co-located. Because sparse attention picks tokens by query-key similarity, STARC clusters the key vectors by semantic similarity (using K-means with cosine similarity) and writes each cluster into contiguous memory rows, keeping each value with its key. Now a memory row holds tokens that tend to be relevant to the same queries. At each decoding step, instead of scoring every token, STARC scores the clusters: it compares the query against each cluster's precomputed centroid, ranks the clusters, and selects the top ones until it hits the KV budget. Because a selected cluster's tokens are contiguous and mostly relevant, PIM can activate its rows with little waste and skip the rows of unselected clusters entirely — realizing the speedup of sparsity while respecting row granularity, and staying accurate because clusters group by relevance rather than position. Clustering is done online during decoding but incrementally (only newly generated tokens are clustered, and once formed clusters are not reshuffled), so it avoids costly data movement. On a simulated HBM-PIM system under constrained KV budgets, STARC cuts attention-layer latency and energy by up to 78 and 65 percent versus token-wise sparsity, and up to 93 and 92 percent versus full attention, while preserving accuracy.

Why this problem is worth solving

The bottleneck STARC targets is the defining cost of long-context LLM serving, and PIM is one of the few levers that attacks it at the root.

During generation, an LLM re-reads its entire KV cache for every single token it produces, but the amount of arithmetic per byte read is tiny — computing an attention score is a cheap dot product against a lot of fetched data. This is the definition of a memory-bound workload: performance is limited not by how fast the processor can compute but by how fast data can arrive. On a GPU, the KV cache lives in memory far from the compute cores, connected by a bus far narrower than the memory’s own internal bandwidth, so the cores stall. Processing-in-memory changes the geometry: by placing compute inside or beside the memory banks, the data barely has to move, and the abundant internal bandwidth is exposed directly to the computation. For attention decoding, whose cost is dominated by moving KV data, this is close to ideal — which is why PIM-enabled systems specifically offload attention to PIM and leave compute-heavy parts elsewhere. That makes getting attention right on PIM directly valuable: it is the operation that most needs the memory wall broken, and PIM is the hardware that can break it, so any inefficiency in how attention runs on PIM translates straight into wasted bandwidth on the workload that can least afford it.

The subtler and more general lesson is that on this kind of hardware, the layout of data in memory is as important as which data you choose.

It is easy to assume that once you know which tokens matter, the hard part is done — but on PIM the hard part is where those tokens are. The hardware’s unit of work is a memory row, not a token: it pays the same cost to touch a row whether one token in it is wanted or all of them. So the value of a sparse selection depends entirely on whether the selected items are concentrated into few rows or smeared across many. Token-wise sparsity gets the selection right but the layout wrong, so its logical savings evaporate physically. This reframes the goal: rather than only choosing better tokens, arrange memory so that tokens which get chosen together are stored together, turning an irregular, scattered access pattern into a regular, row-aligned one. That is a data-mapping problem, and it is a recurring theme wherever fine-grained software decisions meet coarse-grained hardware — caches, DRAM pages, memory banks all reward locality. STARC’s contribution is to notice that semantic similarity, which drives which tokens are selected, can also drive where they are placed, so the two align. Once relevance and location agree, the granularity mismatch that crippled sparse attention on PIM simply disappears.

What people did before, and where it broke

Dense attention on PIM. Keep the whole KV cache and read every row; PIM’s row reads waste nothing because every token is used. Where it broke. At long context this reads and computes over the entire, huge cache every step, exactly the cost sparsity is meant to avoid.
Token-wise sparse attention. Score individual tokens by query-key similarity and select the top ones. Where it broke. The selected tokens scatter across distant memory rows, and since PIM must process a full row for any selected token in it, the logical sparsity yields almost no physical speedup — the system over-fetches and over-computes.
Page-wise sparse attention. Group tokens into fixed-size pages by position and select whole pages, aligning with memory rows. Where it broke. Pages are defined by position, not relevance, so a selected page carries mostly irrelevant tokens (often only one or two that matter), wasting bandwidth and lowering accuracy.
Reordering the cache repeatedly to keep it relevant. Continuously re-arrange KV to match the current query. Where it broke. Reclustering or moving KV data every step incurs its own heavy memory-access and data-movement cost, undermining the savings.
The gap. No scheme made the tokens that are selected together also stored together, so that a relevance-based sparse selection would map onto PIM’s row-level access without wasted fetches or lost accuracy.

How STARC works

From scattered token selection to clustered, row-aligned retrieval

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

The idea

Put the compute where the KV cache already lives. STARC builds on the move of running attention inside memory, so the KV data that dominates decoding barely travels and the memory’s internal bandwidth does the work. Placing transformer attention computation directly on processing-in-memory units to overcome the bandwidth wall of the KV cache is the same near-data approach the work on unleashing PIM for batched transformer generation (AttAcc) covered elsewhere on this site is built on, computing attention beside the memory instead of shipping the cache out. STARC takes that PIM-for-attention substrate as given and asks how to make sparse attention actually pay off on it.

Select by comparing against cluster summaries, not every token. Rather than score each KV entry, STARC clusters them and retrieves at cluster granularity by matching the query to precomputed centroids — a coarse, cheap proximity test that finds the relevant groups. Finding the items closest to a query by comparing against representative summaries instead of exhaustively scanning every candidate is the same approximate-nearest-neighbor idea the work on optimizing high-dimensional approximate nearest-neighbor search (Juno) covered elsewhere on this site is built on, trading exhaustive comparison for fast, clustered lookup. STARC applies that clustered-search discipline to KV selection, so choosing which tokens to attend to costs a handful of centroid comparisons.

Lay out data to match the hardware’s access granularity. STARC’s core act is a remapping: it physically co-locates each cluster in contiguous rows so that PIM’s row-level reads land on relevant, concentrated data instead of scattered tokens. Deliberately arranging where data sits in memory so that the hardware’s natural access pattern retrieves useful, co-located data is the same address-mapping-for-locality idea the work on software-defined address mapping for 3D memory (software-defined address mapping) covered elsewhere on this site pursues, choosing placement to fit the memory’s structure. STARC drives that placement from semantic similarity, so relevance and physical location line up and row granularity stops being a penalty.

Following a decoding step through STARC

From a query to a row-aligned sparse attention on PIM

A trace, drawn from the paper's Algorithm 1, of how STARC clusters KV pairs and retrieves them at cluster granularity during decoding.

Step 1 of 5

Cluster the prefill KV cache once

After the prompt is processed, STARC runs K-means (cosine similarity, K-means++ initialization, a small fixed iteration count) over all the prefill key vectors, assigning each key — and its paired value — to a cluster. This forms the initial hardware-aware groups.

Clustering is on keys only; values follow their keys into the same cluster.

Why it works

Co-location turns logical sparsity into physical skipping. Scattered selected tokens force PIM to read nearly every row → but clustering stores tokens selected together in the same rows → so unselected clusters’ rows can be skipped entirely.
Relevance-based grouping beats position-based pages. Position-defined pages carry mostly irrelevant tokens → but clusters group by semantic similarity → so each activated row is dense with tokens that actually matter, preserving accuracy.
Centroid matching makes selection cheap. Scoring every token each step is costly → but comparing the query to a few cluster centroids → so retrieval finds the relevant groups with a fraction of the comparisons.
Fixed clusters avoid data-movement overhead. Continuously reshuffling the cache to stay relevant is expensive → but forming clusters once and only appending new segments → so STARC skips the memory traffic of repeated remapping.
Keeping recent tokens whole protects accuracy. Freshly generated tokens are unclustered yet important → but always attending to them in full until they are grouped → so the newest context is never dropped from attention.

What it costs (trade-offs and scope)

Clusters approximate the ideal selection. Retrieving at cluster granularity via centroids is coarser than scoring every token, so STARC trades a little selection precision for hardware efficiency; the paper reports accuracy is preserved, but it is an approximation with a budget.
Clustering has runtime cost. K-means over the KV cache, even incrementally on new segments, is real work; STARC bounds it with a small fixed iteration count and by never reshuffling existing clusters, but the overhead is not zero.
Clusters do not always fill a row exactly. A cluster may not align perfectly with an HBM row, so some over-fetch remains; STARC reduces, rather than eliminates, wasted row access.
It targets attention decoding on PIM specifically. STARC addresses the memory-bound multi-head attention offloaded to PIM; it assumes a PIM-enabled heterogeneous system and does not change QKV generation or feed-forward layers.
Results are simulated and budget-dependent. The up-to-78, 65, 93, and 92 percent reductions are on a simulated HBM-PIM system under constrained KV budgets against specific baselines; real hardware, other budgets, or other models may differ.

The comparison

Running sparse attention for LLM decoding on PIM

Property	Token-wise sparsity	Page-wise sparsity	STARC
Selection granularity
Fit with PIM row access
Relevance density per row
Selection cost
Reported outcome on PIM

A comparison of sparse-attention strategies for LLM decoding on PIM. Token-wise sparsity picks the right tokens but scatters them across rows, so PIM cannot skip work; page-wise sparsity aligns with rows but selects by position, dragging in irrelevant tokens and losing accuracy. STARC clusters KV pairs by semantic similarity, stores each cluster contiguously, and retrieves whole clusters by centroid matching — aligning relevance with row granularity to cut attention-layer latency and energy by up to 78 and 65 percent versus token-wise sparsity, and up to 93 and 92 percent versus full attention, while preserving accuracy on a simulated HBM-PIM system. Exact figures should be read from the paper.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 (the authors’ arXiv copy, 2505.05772, of the ASPLOS 2026 paper). The described system is the paper’s: STARC is a sparsity-optimized data mapping scheme for LLM decoding on processing-in-memory (PIM) architectures. It clusters semantically similar KV pairs (K-means over key vectors with cosine similarity, K-means++ initialization, a small fixed iteration count; values assigned to their keys’ clusters), co-locates each cluster in contiguous PIM rows, and retrieves at cluster granularity by comparing a query against precomputed centroids, selecting top clusters up to a KV budget. Clustering is online but incremental — recent tokens are kept in full and attended until enough accumulate to cluster as a new segment, and existing clusters are not reshuffled. The paper evaluates on a simulated HBM-PIM system (its baseline PIM attention design is AttAcc) and reports, under constrained KV budgets, up to 78 and 65 percent reductions in attention-layer latency and energy versus token-wise sparsity methods and up to 93 and 92 percent versus full attention, while preserving model accuracy; it also reports retrieval accuracy comparable to token-wise sparsity and better than page-wise. Some figures in the arXiv text are stated as ranges for particular configurations; the numbers here are the abstract’s headline maxima. Background on PIM, KV cache, attention sparsity, and K-means is standard context. The step-by-step walkthrough follows the paper’s Algorithm 1 but is an illustration, not a verbatim trace. Exact hardware modeling, the algorithm, and full results should be read from the paper.

Background

Why running LLMs keeps pushing computation into the memory

It helps to place STARC in the broader movement to serve large language models by rethinking where computation happens relative to memory. The core tension is that LLM decoding is memory-bound: the model reads far more data (the KV cache) than it computes on, so the traditional arrangement of a fast processor pulling data across a narrow bus wastes the processor. A growing body of work responds by moving computation toward the data — processing-in-memory and near-data accelerators that compute attention inside or beside the memory banks, often in heterogeneous systems that split the model between such units and a conventional accelerator. But this hardware imposes its own rules, chiefly that memory is accessed in coarse rows, and software techniques tuned for flexible processors (like fine-grained sparse attention) do not automatically translate. The recurring project, then, is to reshape the algorithm and the data layout to fit the memory’s structure. This drive to accelerate LLM inference by pairing memory-side computation with attention specifically is the same terrain the work on NPU-PIM heterogeneous acceleration for batched LLM inference (NeuPIMS) covered elsewhere on this site occupies, dividing the model across compute-near-memory and conventional units. STARC’s particular contribution is to make the sparsity that saves work on ordinary hardware also save work on PIM, by clustering the KV cache so that relevance and physical row layout finally agree.

If you remember only three things

1. LLM decoding attention is memory-bound — each generated token re-reads the whole growing KV cache while doing little arithmetic — so processing-in-memory (PIM), which computes attention right beside the memory banks, is a strong fit and is where PIM-enabled systems offload attention. But PIM reads and computes a whole memory row at a time, and current PIM designs assume dense attention. When you try to make attention sparse to save work, a granularity mismatch appears: token-wise sparsity selects the exact right tokens but they scatter across distant rows, and since PIM cannot skip a row holding any selected token, the logical sparsity yields almost no physical speedup; page-wise sparsity aligns with rows but selects by position, so each row is mostly irrelevant tokens and accuracy drops.
2. STARC is a data mapping scheme that makes the tokens selected together also stored together. It clusters KV pairs by semantic similarity (K-means with cosine similarity over the key vectors, values following their keys) and writes each cluster into contiguous PIM rows, so activating a row brings in a group of tokens likely relevant to the same queries. Retrieval happens at cluster granularity: a query is compared against precomputed cluster centroids, the top clusters are selected up to the KV budget, and PIM activates only their rows while skipping the rest — cheap to decide and dense with relevant data. Clustering runs online but incrementally, keeping recent unclustered tokens in full and never reshuffling existing clusters, so it avoids continuous data-movement overhead.
3. By aligning relevance with PIM's row-level access, STARC turns sparse attention into real hardware savings without the accuracy loss of position-based pages. On a simulated HBM-PIM system under constrained KV budgets, it reduces attention-layer latency and energy by up to 78 and 65 percent versus token-wise sparsity methods and up to 93 and 92 percent versus full attention, while preserving model accuracy. The trade-offs: cluster-granularity selection is an approximation, K-means adds bounded runtime cost, clusters do not always fill a row exactly so some over-fetch remains, and the results are from simulation under specific budgets, baselines, and models.

Check yourself

Check your understanding

1. Why is processing-in-memory (PIM) a good fit for LLM decoding attention?
2. Why does token-wise sparse attention fail to speed up attention on PIM?
3. What is STARC's core idea?
4. How does STARC keep its clustering cheap and its results accurate during decoding?

Sources

The paper is “STARC: Selective Token Access with Remapping and Clustering for Efficient LLM Decoding on PIM Systems” by Zehao Fan, Yunzhen Liu, Garrett Gagnon, Zhenyu Liu, Yayue Hou, Hadjer Benmeziane, Kaoutar El Maghraoui, and Liu Liu (Rensselaer Polytechnic Institute and IBM Research), published at ASPLOS 2026, DOI 10.1145/3779212.3790226. It is available on arXiv as 2505.05772.

This explainer is written from the paper’s full text (the authors’ arXiv copy). STARC is a sparsity-optimized data mapping scheme for LLM decoding on processing-in-memory (PIM) systems: it clusters semantically similar KV pairs (K-means over key vectors with cosine similarity, values following their keys), co-locates each cluster in contiguous PIM rows, and retrieves at cluster granularity by matching queries against precomputed centroids, selecting top clusters up to a KV budget. Clustering is online but incremental, with recent tokens kept in full and existing clusters not reshuffled. Evaluated on a simulated HBM-PIM system (baseline PIM attention design AttAcc) under constrained KV budgets, the paper reports up to 78 and 65 percent reductions in attention-layer latency and energy over token-wise sparsity, and up to 93 and 92 percent over full attention, while preserving accuracy. Some figures appear as configuration-specific ranges in the text; the numbers here are the abstract’s headline maxima. Background on PIM, KV cache, attention sparsity, and K-means is standard context. The numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.