It is a process reward model that scores a reasoning trajectory by reading the KV cache the base model already built during generation, rather than re-encoding the trajectory's text. It appends a single verify token and scores that one token against the pre-existing cache, so producing a reward becomes a cache-reading operation. The paper (arXiv:2607.09153) reports the scoring cost dropping from O(L²) to O(L) — up to 5,000× fewer FLOPs, 37× lower latency, and 34× less per-sequence memory — while matching or improving a text-based PRM on MATH, GSM8K, and AIME.

Why is scoring the bottleneck in test-time scaling?

Test-time scaling — beam search, MCTS, best-of-N — generates many candidate reasoning trajectories (partial ones in beam search and MCTS, completed ones in best-of-N) and scores them to decide which to keep. So the reward model can run far more often than the base model, and when that scorer re-encodes the whole trace every time, its cost grows with the square of the trace length and can dominate the search. Making each score a single cache-read is what lets the scorer sit inside the search loop instead of gating it.

How is KV-PRM different from a text-based process reward model?

A text-based PRM treats scoring as a fresh forward pass: it re-encodes the full trajectory text, running attention over all L tokens (roughly O(L²) work) with the KV cache thrown away between passes. KV-PRM reuses the KV cache the model already materialized while generating and scores only a single appended verify token against it — one query attending to L stored entries, roughly O(L). Same input trace, same or better accuracy on MATH, GSM8K, and AIME, at a fraction of the compute and latency.

KV-PRM scores agent rollouts from the KV cache — Verify-token scoring against the KV cache

Jargon

KV cache: The keys and values the model stores for every token it has already processed, so it never has to recompute earlier tokens' keys and values. It is a byproduct of generating the trace — and here it is reused as the input the reward model reads.
Process reward model (PRM): A model that grades the reasoning itself — a step or a whole trajectory — producing a score used to rank paths. Distinct from an outcome reward model, which only grades the final answer.
Test-time scaling: Spending extra compute at inference — more samples, a wider search, longer reasoning — to get a better answer. It leans on a scorer to compare the candidates it generates.
Verify token: The single special token KV-PRM appends and scores against the existing cache. Its score is the reward, so one token's forward pass replaces a full re-encode of the trace.
Trajectory / rollout: One full chain of reasoning the model generated for a problem. Test-time scaling produces many and must rank them.
O(L²) vs O(L): Re-encoding a trace of L tokens costs on the order of L² of attention work from scratch; scoring one new token against a cache of L already-stored entries costs on the order of L.

The news. On July 13, 2026, a paper (arXiv:2607.09153) introduced KV-PRM, a process reward model that scores reasoning trajectories without re-encoding their text. During generation the base model already builds a KV cache for the trace; KV-PRM reuses that cache and scores a single "verify token" against it, turning reward scoring into a cache-reading operation. The paper reports the scoring cost dropping from O(L²) to O(L) — up to 5,000× fewer scoring FLOPs, 37× lower latency, and 34× less per-sequence memory than a text-based PRM — while matching or improving its accuracy on MATH, GSM8K, and AIME. Its framing: "By processing a single 'verify token' against the pre-existing KV cache, KV-PRM reduces the scoring cost from O(L²) to O(L)." Read the paper →

Picture a teacher grading a stack of long essays. As the model reasons through a problem, it does two things at once: it writes the essay (the reasoning trajectory) and, line by line, it leaves margin notes — its own running annotations on everything it has read so far. Those margin notes are the KV cache: the model builds them as a byproduct of generating, precisely so it never has to work out an earlier line again. The usual grader — a text-based reward model — ignores those notes and re-reads the whole essay from the top to assign a grade. Do that for hundreds of essays inside a search, and grading, not writing, is what eats the afternoon. KV-PRM does the obvious thing the usual grader misses: it reads the notes already in the margins, and adds a single "grade it" mark at the end.

Underneath the metaphor, "grading the reasoning" is a process reward model scoring a trajectory so a search can keep the promising ones and drop the rest. A text-PRM produces that score by re-encoding the full trajectory text — a fresh forward pass whose attention runs over all L tokens, on the order of L² of work. KV-PRM instead reuses the KV cache the base model already materialized and appends one verify token, scoring that single token against the cache: one query attending to L stored entries, on the order of L. The reward stops being a re-computation of the whole trace and becomes a single read of the cache that was already sitting there — a score drawn from work the model had already done, not a fresh pass over the text.

That matters because test-time scaling multiplies scoring. Beam search and MCTS score many partial trajectories, and best-of-N scores many completed ones — every candidate needs a score to compare it, so the reward model can run far more often than the base model, and its cost, not the model's, can set the pace. Collapsing each score to a cache-read makes the scorer cheap enough to sit inside the search loop, a cost the serving engine pays once per candidate instead of a full re-encode. And rather than trading quality for speed, the paper reports it matches or improves the text-PRM's accuracy on MATH, GSM8K, and AIME.

Where it earns its keep

Hold one trajectory fixed and walk the cost. Say a reasoning trace runs L = 2,000 tokens (illustrative length — the paper reports ratios, not this exact size). Re-encoding it, a text-PRM runs attention over all 2,000 tokens, work on the order of L² = 4,000,000 units. Scoring one verify token against the existing cache touches the L = 2,000 stored entries, work on the order of 2,000 units. That is a ~2,000× gap at this single length, and it widens as traces grow — because re-encoding scales with L² while the cache-read scales with L. The paper's own headline figures are steeper still: up to 5,000× fewer scoring FLOPs and 37× lower latency at realistic search settings (paper figures; setup-dependent).

How it scores a trajectory	What it reads	Scoring cost	Reuses the KV cache?
Outcome reward model	only the final answer	one score per finished answer	n/a
Text-based PRM	re-encodes the full trace text	~O(L²) — a fresh forward pass	no
KV-PRM	one verify token vs the existing cache	~O(L) — a single read	yes — the generation cache

Because the change lives in how the score is computed rather than in the search strategy itself, it should stack with the rest of the test-time toolkit — the same beam search or MCTS, now with a scorer that no longer dominates the bill, and the real-world gain depends on how long the traces are and how wide the search runs. The headline is not a smarter grade but a cheaper one: the reward stops being a re-read of the whole trace and becomes a single glance at the cache the model already built (reported up to 5,000× fewer FLOPs and 37× lower latency, at matched accuracy; setup-dependent).

Goes deeper in: LLM Internals → KV Cache → The KV Cache Solution

Continue in trackKV Cache — the keys and values the model keeps so it never recomputes a token twice

Related explainers

KV-PRM sits where three threads meet — reusing the cache, reading it for a second signal, and making the scorer the workhorse of test-time search:

Attention Once Is All You Need — persistent KV cache — the same core move, reuse the KV cache instead of recomputing it, applied to prefixes shared across queries rather than to scoring
SP-KV — a utility predictor for the KV cache — another read of the cache for a second decision (there, which entries to keep; here, what grade to assign)
LLM-as-a-Verifier — verification as a scaling axis — why the scorer is the workhorse of test-time scaling, the exact cost KV-PRM collapses

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based