StepKV: Step-Aware KV Cache Compression for LLM Agents

# StepKV: Step-Aware KV Cache Compression for LLM Agents
Source: [https://arxiv.org/html/2609.22158](https://arxiv.org/html/2609.22158)
Boyu Feng1, Jiahong Liu1, Yifan Li1, Wenhao Yu1, Zexuan Qiu1, Yuliang Sun1, Ming Shen1, Xiang Li2, Quanyu Dai2, Irwin King1 1The Chinese University of Hong Kong 2Huawei Technologies Co\., Ltd

© none

###### Abstract\.

Key\-value \(KV\) caching is essential for efficient autoregressive large language model \(LLM\) inference, but the cache grows linearly with the accumulated context and increases the amount of KV data that must be stored and read during decoding\.KV cache compressionmitigates this cost by retaining only a subset of cached tokens\. This problem becomes especially important in multi\-step LLM agents, where a user query expands into a trajectory of intermediate reasoning, tool interactions, and retrieved observations\. Existing pruning methods usually treat the cache as a flat token stream and rank tokens by recency or attention\-based saliency\. This creates a mismatch between the unit of compression and the unit of reasoning: token\-level pruning removes individual cache entries, whereas useful information in multi\-step agents is often organized by reasoning steps whose importance is uneven and delayed\. As a result, an early observation or intermediate decision may receive little recent attention but become necessary for later evidence synthesis\. This failure mode is termed*Reasoning Continuity Disruption*\. These observations motivate KV cache compression that operates jointly at the token and reasoning\-step levels\.StepKVaddresses this goal by treating reasoning steps as first\-class retention units\. Instead of allocating cache budget only among isolated tokens, the framework associates cache entries with their generating steps, estimates step utility fromtrajectory\-derived signals, and combines this utility with token\-level saliency\. The resulting score globally ranks all prunable tokens, from which StepKV retains the top\-scoring entries under the target budget\. More broadly, StepKV provides astep\-centric perspectivefor agent KV cache compression\.Across agent multi\-hop QA and long\-horizon web reasoning tasks, StepKV sustains accuracy under low KV budgets where token\-level baselines degrade sharply, offering a more robustefficiency–accuracy trade\-offfor multi\-step agent inference\.

††footnotetext:E\-mail:\{fengboyu, jhliu\}@link\.cuhk\.edu\.hk\. Corresponding author: Jiahong Liu\.![Refer to caption](https://arxiv.org/html/2609.22158v1/case-final.png)Figure 1\.Comparison of StepKV and token\-level KV cache pruning in preserving critical reasoning steps\.## 1\.Introduction

Key\-value \(KV\) caching is a standard mechanism for efficient autoregressive large language model \(LLM\) inference\([Vaswani et al\., 2017](https://arxiv.org/html/2609.22158#bib.bib19);[Pope et al\., 2022](https://arxiv.org/html/2609.22158#bib.bib15)\)\. By storing the keys and values of previous tokens, the model avoids recomputing past hidden states when generating each new token\. This acceleration, however, comes with a growing memory and data\-movement cost: the cache expands with the accumulated context, and decoding must repeatedly read historical KV entries\.KV cache compressiontherefore becomes a practical tool for reducing memory footprint and improving the efficiency of long\-context inference\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25);[Li et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib11);[Xiao et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib21)\)\.

This need is amplified inLLM agents\([Yao et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib23);[Schick et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib17);[Nakano et al\., 2022](https://arxiv.org/html/2609.22158#bib.bib14);[Shinn et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib18)\)\. Unlike single\-pass generation, agentic inference often expands one user query into a trajectory of intermediate reasoning, tool interactions, and retrieved observations\. In multi\-hop question answering and web\-based information seeking, these trajectories can contain evidence collected at different stages of the process\. Compression must therefore reduce the cache while preserving information that later reasoning steps may still need\.

Existing KV cache pruning methods usually treat the cache as aflat token stream\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25);[Ge et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib4);[Li et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib11);[Wu et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib20)\)\. They score individual tokens by recency, accumulated attention, or related saliency signals, then keep the tokens that appear locally important\. This token\-level view is effective in many long\-context settings, but it does not explicitly model the structure that produced the cache\. In step\-structured agents, theunit of compression can diverge from the unit of reasoning: useful information is often introduced and reused at the level of a reasoning step, not only at the level of isolated tokens\.

The resulting failure mode is*Reasoning Continuity Disruption*\. Under tight KV budgets, token\-level pruning may remove early observations or intermediate decisions before their later reuse\. The agent can then lose evidence needed to connect later observations, causing repeated tool calls, missing evidence, or incorrect final answers\. This points to KV cache compression for multi\-step agents that preserves trajectory structure rather than only locally salient tokens\.

To address the mismatch between existing KV cache compression methods and the structured nature of agent reasoning,StepKVintroduces reasoning\-step importance into token\-level cache selection through astep\-aware token scoring mechanism\. Unlike conventional autoregressive generation, agent reasoning is typically composed of multiple consecutive reasoning steps, where different steps may serve distinct functions, such as information acquisition, hypothesis formation, intermediate derivation, and final decision making\. Therefore, different reasoning steps contribute unequally to future inference and final outcomes, and estimating importance solely from individual tokens may overlook intermediate steps with long\-term impacts on the reasoning trajectory\.

Figure[1](https://arxiv.org/html/2609.22158#S0.F1)presents an example to illustrate the mismatch between token\-level importance estimation and reasoning\-step\-level importance in agent inference\. The upper part of Figure[1](https://arxiv.org/html/2609.22158#S0.F1)illustrates an important phenomenon observed during agent reasoning: different reasoning steps contribute unequally to the final outcome\. Some steps provide critical intermediate information that directly affects subsequent reasoning, while others mainly contain redundant exploration or auxiliary content\. However, existing token\-level importance metrics, such as attention\-based scores, may not fully capture this semantic difference between reasoning steps\. As shown in the upper part of Figure[1](https://arxiv.org/html/2609.22158#S0.F1), tokens from less critical steps may still receive considerable attention or importance scores due to their local relevance, causing token\-level compression methods to preserve locally salient but globally less useful information\. Meanwhile, tokens that are essential for maintaining future reasoning dependencies may be mistakenly discarded\.

The lower part of Figure[1](https://arxiv.org/html/2609.22158#S0.F1)demonstrates how StepKV alleviates this issue\. By incorporating step\-level importance into token selection, StepKV can distinguish the different contributions of reasoning steps and adjust cache retention accordingly\. Tokens belonging to high\-utility reasoning steps receive higher priority during cache selection, while redundant information from less important steps can be removed more effectively\. This case demonstrates that reasoning\-step awareness provides complementary information beyond token\-level scoring and enables more effective KV cache management for long\-horizon agent reasoning\.

Based on this observation,StepKVdoes not treat reasoning steps as coarse\-grained retention units\. Instead, it utilizes step\-level utility to guide token\-level importance estimation\. The final cache selection jointly considers local token saliency and the global contribution of the corresponding reasoning step, allowing critical tokens from important steps to receive higher retention priority while maintaining the flexibility of token\-level compression\. This step\-aware perspective better aligns KV cache management with the trajectory structure of agent reasoning and effectively mitigatesReasoning Continuity Disruptionin long\-horizon inference\. Overall, our contributions can be summarized as follows:

- •A trajectory\-aware view of KV cache compression for LLM agents\.The paper reframes KV cache compression as a problem of preserving useful reasoning trajectories under fixed cache budgets\.
- •A reasoning\-continuity\-preserving compression framework\.StepKV provides a step\-aware cache allocation strategy that protects cross\-step dependencies while retaining token\-level selectivity\.
- •Empirical support for trajectory\-aware KV compression\.Experiments show that trajectory\-aware compression provides a strongerefficiency–accuracy trade\-offthan token\-level pruning under tight KV budgets\.

## 2\.Related Work

### 2\.1\.LLM Agents

LLM agents extend single\-pass generation into multi\-step trajectories that interleave reasoning, tool use, and environmental feedback\([Yao et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib23);[Schick et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib17);[Nakano et al\., 2022](https://arxiv.org/html/2609.22158#bib.bib14);[Shinn et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib18)\)\. Unlike conventional generation, agent inference continuously accumulates thoughts, actions, observations, and retrieved evidence, whose utility may emerge only in later steps\. Most existing studies focus on planning, tool use, retrieval, and memory design, while recent work has begun to manage the inference context or KV cache according to model directives, trajectory structure, or user intent\([Kariyappa and Suh, 2026](https://arxiv.org/html/2609.22158#bib.bib10);[Ma et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib13);[Li et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib12)\)\. StepKV complements these efforts by addressing fine\-grained retention within a fixed KV cache budget\. It explicitly models the semantic boundaries and utility of reasoning steps while retaining salient tokens within each step, thereby preserving reasoning continuity under aggressive cache compression\.

### 2\.2\.KV Cache Management

Long\-context inference has been optimized through architectural changes, sparse attention, and explicit KV cache compression\. GQA and MLA reduce the memory footprint of KV representations\([Ainslie et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib1);[DeepSeek\-AI, 2024](https://arxiv.org/html/2609.22158#bib.bib3)\), while sparse\-attention and state\-space architectures reduce the computation required for long\-range dependency modeling\([Yuan et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib24);[Gu and Dao, 2024](https://arxiv.org/html/2609.22158#bib.bib5);[Yang et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib22)\)\. These approaches primarily optimize how contextual representations are computed or stored\. Decode\-stage cache management instead determines which historical KV entries to retain as generation proceeds\. Representative methods estimate token importance from accumulated attention statistics\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25);[Liu et al\., 2023b](https://arxiv.org/html/2609.22158#bib.bib8)\), query\-aware attention\([Oren et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib7);[Li et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib11)\), or structural signals\([Hongthai and Chuangsuwanich, 2025](https://arxiv.org/html/2609.22158#bib.bib9);[Xiao et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib21)\)\. Recent methods further incorporate redundancy\- or reasoning\-aware signals into cache reduction\([Cai et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib2);[Hu et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib6);[Zhang et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib26);[Ramachandran et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib16);[Kariyappa and Suh, 2026](https://arxiv.org/html/2609.22158#bib.bib10)\)\. However, these methods still primarily operate at the token level and overlook the structured nature of agent reasoning trajectories\. StepKV introduces step\-aware cache allocation for agent reasoning, preserving critical agent trajectories while removing redundant context\. For detailed discussion of related works, please refer to Appendix[B](https://arxiv.org/html/2609.22158#A2)\.

## 3\.Problem Formulation

Given a user queryqqand an external environment, letStepk\\mathrm\{Step\}\_\{k\}denote thekk\-th completed interaction step of an LLM agent\. After stepttis completed, the finalized steps are indexed by𝒮\(t\)=\{1,…,t\}\\mathcal\{S\}^\{\(t\)\}=\\\{1,\\ldots,t\\\}and form the text trajectoryτ\(t\)=\(q,\{Stepk\}k∈𝒮\(t\)\)\\tau^\{\(t\)\}=\(q,\\\{\\mathrm\{Step\}\_\{k\}\\\}\_\{k\\in\\mathcal\{S\}^\{\(t\)\}\}\)\. At stepkk, the model generates the*Thought*and*Action*fields, executes the*Action*in the environment, and appends the returned*Observation*to the context\. We writeThk\\mathrm\{Th\}\_\{k\},Actk\\mathrm\{Act\}\_\{k\}, andObsk\\mathrm\{Obs\}\_\{k\}for these three fields, respectively\.

Cache compressionoperates on the tokenized trajectory after steptthas been appended\. Letℐ\(t\)=\{1,…,Nt\}\\mathcal\{I\}^\{\(t\)\}=\\\{1,\\ldots,N\_\{t\}\\\}index the prunable trajectory tokens, excluding protected prompt/query tokens\. Each completed step occupies a contiguous span inℐ\(t\)\\mathcal\{I\}^\{\(t\)\}\. Let𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}denote the KV cache at this post\-step pruning boundary\. It consists of protected entries𝒞prot\\mathcal\{C\}\_\{\\mathrm\{prot\}\}and prunable trajectory entries𝒞traj\(t\)\\mathcal\{C\}\_\{\\mathrm\{traj\}\}^\{\(t\)\}, where𝒞traj\(t\)​\[i\]\\mathcal\{C\}\_\{\\mathrm\{traj\}\}^\{\(t\)\}\[i\]is the KV entry for tokeni∈ℐ\(t\)i\\in\\mathcal\{I\}^\{\(t\)\}\. Thus,τ\(t\)\\tau^\{\(t\)\}is the text trajectory, whereasℐ\(t\)\\mathcal\{I\}^\{\(t\)\}is the token\-index set over that trajectory\. Given a keep ratioρ\\rho, online cache compression selects a retained index set𝒦\(t\)⊆ℐ\(t\)\\mathcal\{K\}^\{\(t\)\}\\subseteq\\mathcal\{I\}^\{\(t\)\}under a fixed budget\. We use∥\\\|to denote cache concatenation, and𝒞traj\(t\)​\[𝒦\(t\)\]\\mathcal\{C\}\_\{\\mathrm\{traj\}\}^\{\(t\)\}\[\\mathcal\{K\}^\{\(t\)\}\]to denote the trajectory\-cache entries selected by𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}:

\(1\)𝒞\(t\)\\displaystyle\\mathcal\{C\}^\{\(t\)\}=𝒞prot\|𝒞traj\(t\)\(full KV\),\\displaystyle=\\mathcal\{C\}\_\{\\mathrm\{prot\}\}\\;\\\|\\;\\mathcal\{C\}\_\{\\mathrm\{traj\}\}^\{\(t\)\}\\quad\\text\{\\footnotesize\{\\color\[rgb\]\{0\.35,0\.35,0\.35\}\(full KV\)\}\},𝒦\(t\)\\displaystyle\\mathcal\{K\}^\{\(t\)\}⊆ℐ\(t\),\|𝒦\(t\)\|≤Bt=max\(1,⌊ρNt⌋\),\\displaystyle\\subseteq\\mathcal\{I\}^\{\(t\)\},\\qquad\|\\mathcal\{K\}^\{\(t\)\}\|\\leq B\_\{t\}=\\max\(1,\\lfloor\\rho N\_\{t\}\\rfloor\),𝒞^\(t\)\\displaystyle\\widehat\{\\mathcal\{C\}\}^\{\(t\)\}=𝒞prot\|𝒞traj\(t\)​\[𝒦\(t\)\]\(compressed KV\)\.\\displaystyle=\\mathcal\{C\}\_\{\\mathrm\{prot\}\}\\;\\\|\\;\\mathcal\{C\}\_\{\\mathrm\{traj\}\}^\{\(t\)\}\[\\mathcal\{K\}^\{\(t\)\}\]\\quad\\text\{\\footnotesize\{\\color\[rgb\]\{0\.35,0\.35,0\.35\}\(compressed KV\)\}\}\.The compression objective is to choose𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}so that𝒞^\(t\)\\widehat\{\\mathcal\{C\}\}^\{\(t\)\}satisfies the target cache budget while preserving the agent’s task\-level performance relative to full\-cache inference with𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}\.In other words, under a fixed keep ratio, the compressed agent aims to maintain the final answer quality or task success of the original full\-cache run as closely as possible\.

![Refer to caption](https://arxiv.org/html/2609.22158v1/Evicted_at_ReAct_step.png)\(a\)Evicted tokens by originating step\.
\(b\)Remaining step cohorts\.\(c\)Performance under step removal\.
Figure 2\.Motivation for reasoning continuity under KV cache pruning\. Panels \(a\)–\(b\) trace a representative rollout after prompt prefill: \(a\) groups evicted tokens by their source step, showing that pruning spans the preceding trajectory, and \(b\) tracks each cohort’s remaining fraction, showing that even recently completed steps can be rapidly depleted\. Panel \(c\) reports EM and F1 under controlled history removal\.lag\-1andlag\-2remove the completed step one or two positions before the current step, respectively, whilewindow\-2retains the two most recent completed steps and removes all earlier ones\. Every removal setting degrades performance, but the magnitude depends strongly on which part of the trajectory is removed\.
## 4\.Motivating Observation: Reasoning Continuity Disruption

The problem formulation exposes a structural tension between the unit of pruning and the unit of reasoning\. KV cache compression selects individual cache entries, but an agent trajectory is produced through completed reasoning steps, each containing intermediate decisions, tool calls, and observations\. Therefore, the relevant question is not only whether high\-saliency tokens are retained, but whether the retained cache still contains a usable trace of the steps that later reasoning may need\. Figure[2](https://arxiv.org/html/2609.22158#S3.F2)highlights two observations behind this mismatch\.

Motivation experiment\.To make these observations visible, Figure[2](https://arxiv.org/html/2609.22158#S3.F2)combines a trace diagnostic with a controlled step\-removal study\. For Figures[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(a\)](https://arxiv.org/html/2609.22158#S3.F2.sf1)\) and \([2\(b\)](https://arxiv.org/html/2609.22158#S3.F2.sf2)\), a representative agent rollout is instrumented at the token and step levels\. Each generated token after prompt prefill is assigned to its source step; H2O and TOVA are then applied online under the same target cache budget, and every pruning decision records which step each retained or evicted token came from\. Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(c\)](https://arxiv.org/html/2609.22158#S3.F2.sf3)\) reruns agent inference under otherwise identical settings while removing the step at lag one or lag two, or deleting all history older than the two most recent completed steps\. The trace diagnostic first identifies which step context token\-level methods actually remove; the controlled removal then tests whether losing such context directly changes downstream EM and F1\.

Observation 1: Token\-level pruning discards both early and recent step context\.H2O and TOVA make retention decisions from attention\-derived importance at the token level; neither method explicitly tracks whether a completed reasoning step remains sufficiently represented after eviction\. We analyze how these methods evict tokens across completed steps as an agent trajectory unfolds\.First, early\-step information is easily discarded\.Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(a\)](https://arxiv.org/html/2609.22158#S3.F2.sf1)\) shows that evictions repeatedly span earlier steps as the trajectory advances, leaving only fragmented traces of their reasoning, actions, and observations\.Second, recently completed steps can be depleted almost immediately\.In Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(b\)](https://arxiv.org/html/2609.22158#S3.F2.sf2)\), a new step cohort can lose a large fraction of its tokens after only one or two subsequent steps\. Token\-level pruning can therefore remove both long\-range evidence from early steps and the nearby context required for the next reasoning transition, even while satisfying the global cache budget\.

Observation 2: Loss of step context directly degrades downstream reasoning\.Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(c\)](https://arxiv.org/html/2609.22158#S3.F2.sf3)\) verifies that the deletion behavior in Figures[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(a\)](https://arxiv.org/html/2609.22158#S3.F2.sf1)\) and \([2\(b\)](https://arxiv.org/html/2609.22158#S3.F2.sf2)\) is not a benign reduction of redundant tokens\. Every controlled removal setting underperforms Full KV\.window\-2removes all but the two most recent completed steps and still reduces both EM and F1, showing that earlier steps continue to supply useful evidence\. Removing the immediately preceding step withlag\-1causes the largest degradation, while removing the step two positions back withlag\-2is also substantially worse than retaining both recent steps\. The step context fragmented by token\-level eviction therefore directly affects downstream task quality\. Moreover, the unequal drops show that the required context changes with the trajectory: a new step can be critical to the next transition, while an older step remains important when its evidence is reused later\.

These observations identify*Reasoning Continuity Disruption*: token\-only importance can satisfy the cache budget while breaking the step structure required by downstream reasoning\. The missing signal is astep scorethat assigns shared retention importance to tokens from the same completed step\. Because the usefulness of a step changes as later dependencies emerge, this score also needs to be initialized from the completed step and updated as subsequent trajectory content reuses its information\. Section[5](https://arxiv.org/html/2609.22158#S5)instantiates this step\-level signal while preserving token\-level selectivity\.

Figure 3\.Overview of StepKV\. \(a\) The integration of StepKV into the LLM agent inference framework\. \(b\) The StepKV pipeline\.
## 5\.Methodology: Step\-Aware KV Cache Compression

With the cache layout and step spans defined in Section[3](https://arxiv.org/html/2609.22158#S3), StepKV addresses the granularity mismatch between KV cache compression and step\-structured agent reasoning\. Instead of making retention decisions solely at the token level, StepKV introduces a trajectory\-level utility signalSkS\_\{k\}for each completed step and updates it when later reasoning reveals additional dependencies\. Meanwhile, token saliencyTiT\_\{i\}preserves fine\-grained selection within each step\. These two signals jointly determine the retention priorityPiP\_\{i\}of each token, and the topBtB\_\{t\}tokens form the retained set𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}\.

The key design is to allocate cache based on completed reasoning steps while maintaining token\-level selectivity\. When a new step completes, its immediate contribution initializes the step utility \(Phase 1\)\. As the trajectory evolves, later reuse updates previous step utilities through delayed dependency signals \(Phase 2\)\. Finally, the step utility is combined with token saliency for cache selection \(Phase 3\)\. This design enables cache compression to follow the evolving dependency structure of agent reasoning rather than relying only on instantaneous token\-level signals\.

Design Rationale\.The step utility is motivated by the temporal dependency of agent reasoning\. The value of an intermediate step is not always observable when it is generated: some steps provide immediate useful evidence, while others become important only when later steps reuse their information\. Therefore, StepKV decomposes step utility into an immediate contribution termrkr\_\{k\}and a delayed reuse accumulatorckc\_\{k\}\.In addition, they provide a trajectory\-level retention signal that complements token saliency and captures both newly introduced information and future dependencies\. Additional analysis of these signals is provided in Appendix[C](https://arxiv.org/html/2609.22158#A3)\.

### 5\.1\.Step Utility Scoring

A useful reasoning step contributes meaningful evidence to the trajectory, and its importance may increase when later reasoning depends on that evidence\.This follows directly from Section[4](https://arxiv.org/html/2609.22158#S4): reasoning steps contribute unequally, while the value of early information may become apparent only after subsequent tool calls\. Step importance therefore cannot be determined once and then kept fixed\. StepKV models this evolving importance through two complementary operations\.*New\-step scoring*estimates the immediate progress made by a newly completed step, whereas*previous\-step updating*revises an earlier step when its evidence is reused\. These operations produce a completion scorerkr\_\{k\}and a reuse accumulatorck≥0c\_\{k\}\\geq 0, which are combined into the step utilitySkS\_\{k\}\.

#### 5\.1\.1\.New\-step Scoring \(rkr\_\{k\}\)

When stepkkis finalized, only its immediate contribution is observable\. Rather than treating the completed step as undifferentiated text, StepKV distinguishes the roles of the*Thought*,*Action*, and*Observation*fields as reasoning intent, environment interaction, and returned evidence, respectively\. These roles yield three field\-level signals\.

\(1\)Observation validity\.The validity of the returned observation is defined as:

validk=\{1,ifObskis usable,0,otherwise\.\\mathrm\{valid\}\_\{k\}=\\begin\{cases\}1,&\\text\{if $\\mathrm\{Obs\}\_\{k\}$ is usable\},\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}Remark:An empty, invalid, or error\-returningObsk\\mathrm\{Obs\}\_\{k\}is considered unusable and therefore contributes no positive evidence to the new\-step score\.

\(2\)Evidence gain\.Letsim⁡\(a,b\)\\operatorname\{sim\}\(a,b\)denote overlap\-based textual similarity\. Evidence gain compares the concatenated Thought–Observation content of the current step with that of each previous step:

gaink=1−max1≤u<ksim\(Thk∥Obsk,Thu∥Obsu\),gain1=1\.\\mathrm\{gain\}\_\{k\}=1\-\\max\_\{1\\leq u<k\}\\operatorname\{sim\}\\\!\\left\(\\mathrm\{Th\}\_\{k\}\\\|\\mathrm\{Obs\}\_\{k\},\\mathrm\{Th\}\_\{u\}\\\|\\mathrm\{Obs\}\_\{u\}\\right\),\\qquad\\mathrm\{gain\}\_\{1\}=1\.Remark:The maximum identifies the closest earlier step, so the score is high when the current reasoning and evidence differ from what has already appeared\. Observation validity and evidence gain are computed independently and enterrkr\_\{k\}as separate signals\.

\(3\)Action redundancy\.Action redundancy is computed as:

redk=max1≤u<k⁡sim⁡\(Actk,Actu\),red1=0\.\\mathrm\{red\}\_\{k\}=\\max\_\{1\\leq u<k\}\\operatorname\{sim\}\(\\mathrm\{Act\}\_\{k\},\\mathrm\{Act\}\_\{u\}\),\\qquad\\mathrm\{red\}\_\{1\}=0\.Remark:The score compares the current Action with all earlier actions and uses the strongest match as its redundancy penalty\. Thus, repeated tool calls lower the contribution of a step unless they return useful evidence captured by the positive terms\.

The three signals are combined into the initial score of stepkk:

\(2\)rk=validk\+gaink−λ​redk\.r\_\{k\}=\\mathrm\{valid\}\_\{k\}\+\\mathrm\{gain\}\_\{k\}\-\\lambda\\,\\mathrm\{red\}\_\{k\}\.The positive terms reward usable and relevant evidence, whileλ\\lambdacontrols the penalty for repeated interaction\.

#### 5\.1\.2\.Previous\-step Updating \(ckc\_\{k\}\)

The completion score cannot capture dependencies that emerge after a step is produced\. StepKV therefore maintains areuse accumulatorckc\_\{k\}for each completed step to record how strongly its evidence is reused later\.When stepkkis first completed,ckc\_\{k\}is initialized to zero; it is updated as subsequent steps reveal delayed relevance\.After stepttis completed, StepKV compares the new observationObst\\mathrm\{Obs\}\_\{t\}with each previous observationObsk\\mathrm\{Obs\}\_\{k\}and updates as:

\(3\)ck←ck\+min⁡\(1,η​sim⁡\(Obst,Obsk\)\),1≤k<t\.c\_\{k\}\\leftarrow c\_\{k\}\+\\min\\\!\\left\(1,\\;\\eta\\,\\operatorname\{sim\}\(\\mathrm\{Obs\}\_\{t\},\\mathrm\{Obs\}\_\{k\}\)\\right\),\\qquad 1\\leq k<t\.Remark:A previous step gains reuse credit only when its observation reappears later; zero overlap leavesckc\_\{k\}unchanged, whileη\\etaand the cap control each increment\.

#### 5\.1\.3\.Step Utility \(SkS\_\{k\}\)

The utility of stepkkcombines the completion scorerkr\_\{k\}from new\-step scoring with the reuse accumulatorckc\_\{k\}from previous\-step updating:

\(4\)Sk=clip⁡\(wr​clip⁡\(rk,rmin,rmax\)\+wc​log⁡\(1\+ck\),0,Smax\),S\_\{k\}=\\operatorname\{clip\}\\\!\\left\(w\_\{r\}\\,\\operatorname\{clip\}\(r\_\{k\},r\_\{\\min\},r\_\{\\max\}\)\+w\_\{c\}\\log\(1\+c\_\{k\}\),\\,0,\\,S\_\{\\max\}\\right\),Here,clip⁡\(z,a,b\)\\operatorname\{clip\}\(z,a,b\)truncateszzto\[a,b\]\[a,b\]\. The completion term captures the step’s immediate contribution, whereaslog⁡\(1\+ck\)\\log\(1\+c\_\{k\}\)adds delayed credit as later observations reuse its evidence\. The weightswrw\_\{r\}andwcw\_\{c\}balance these two signals; the inner clip and logarithm control their scales, and the outer clip constrainsSkS\_\{k\}to\[0,Smax\]\[0,S\_\{\\max\}\]\.

### 5\.2\.Token Saliency and Cache Selection

StepKV complements step utility with a token saliency scoreTiT\_\{i\}, which estimates the local importance of each prunable KV entry\. Token saliency keeps the selector sensitive to model\-level evidence, whileSkS\_\{k\}preserves trajectory\-level structure\. This component is modular:TiT\_\{i\}can be supplied by existing token\-level KV importance estimators or selection rules\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25);[Ge et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib4);[Li et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib11);[Wu et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib20)\)without changing the step\-utility computation\. Each token inherits the utility of its source step\. For tokeniiproduced by stepkk, the retention priority is:

\(5\)Pi=α​Ti\+β​Sk\.P\_\{i\}=\\alpha T\_\{i\}\+\\beta S\_\{k\}\.Tokens in the same step share the sameSkS\_\{k\}but may differ inTiT\_\{i\}, allowing locally salient tokens to survive even within a low\-utility step, and high\-utility steps to lift their entire span\.

The final selector globally ranks tokens byPiP\_\{i\}and retains the topBtB\_\{t\}\. Step utility raises the priorities of tokens from important steps, while token saliency preserves within\-step selectivity\. No step is permanently protected: its tokens can still be evicted asTiT\_\{i\}is recomputed andNtN\_\{t\}grows under a fixed keep ratio\.

## 6\.Experiments

We organize the evaluation around four research questions:RQ1: Does StepKV preserve reasoning accuracy under tight KV budgets?\(Section[6\.2](https://arxiv.org/html/2609.22158#S6.SS2)\);RQ2: Does StepKV reduce practical cost in long\-horizon agent reasoning?\(Section[6\.3](https://arxiv.org/html/2609.22158#S6.SS3)\);RQ3: How does reasoning depth affect compressed\-cache performance?\(Section[6\.4](https://arxiv.org/html/2609.22158#S6.SS4)\); andRQ4: Do step\-level signals explain the gains of StepKV?\(Section[6\.5](https://arxiv.org/html/2609.22158#S6.SS5)\)\.

Table 1\.Main results under different KV cache budgets\. Full KV and ReAct are reference settings; bold numbers indicate the best compressed result for each model, budget, dataset, and metric\.### 6\.1\.Experimental Setup

Datasets\.We evaluate StepKV on four representative agent reasoning benchmarks, including HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2609.22158#bib.bib29)\), 2WikiMultihopQA\([Ho et al\., 2020](https://arxiv.org/html/2609.22158#bib.bib30)\), MuSiQue\([Trivedi et al\., 2022](https://arxiv.org/html/2609.22158#bib.bib31)\), and BrowseComp\-Plus\([Chen et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib32)\)\. HotpotQA, 2WikiMultihopQA, and MuSiQue are used to evaluate basic multi\-hop agent question answering, where performance is measured by Exact Match \(EM\) and token\-level F1\. BrowseComp\-Plus is a challenging long\-horizon web reasoning benchmark whose reasoning trajectories can exceed 100K tokens\. On this benchmark, we additionally report inference latency and the final KV cache size to evaluate efficiency under extremely long\-context reasoning\.

Baselines\.We compare StepKV with three representative KV cache compression methods: H2O\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25)\), TOVA\([Oren et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib7)\), and TokenSkipping\([Hongthai and Chuangsuwanich, 2025](https://arxiv.org/html/2609.22158#bib.bib9)\), together with the Full KV and ReAct baselines\. Specifically, we categorize existing decoding\-stage KV cache management approaches into three representative paradigms\. H2O represents*accumulated score\-based*methods, which retain tokens according to accumulated attention statistics; TOVA represents*online attention\-based*methods, which perform dynamic eviction based on attention scores during decoding; and TokenSkipping represents*heuristic\-based*methods, which reduce cache usage through predefined token\-skipping rules\. Together, these methods cover three representative paradigms of existing KV cache management during decoding\.

Implementation detailsare provided in Appendix[D](https://arxiv.org/html/2609.22158#A4)\.

### 6\.2\.Performance under Tight KV Budgets \(RQ1\)

StepKV preserves multi\-hop QA accuracy much more reliably than token\-level pruning under constrained cache budgets\.Table[1](https://arxiv.org/html/2609.22158#S6.T1)compares Full KV and ReAct reference settings with H2O, TOVA, TokenSkipping and StepKV across three agent multi\-hop QA datasets and two backbone models, Qwen2\.5\-7B\-Instruct\([Yang et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib28)\)and Llama\-3\.1\-8B\-Instruct\([Grattafiori et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib27)\)\.

The improvement is consistent across models, datasets, and metrics\.In Table[1](https://arxiv.org/html/2609.22158#S6.T1), StepKV is the best compressed method for every model\-budget\-dataset combination, as indicated by the bolded EM and F1 values\. This pattern holds on both backbones and all three multi\-hop QA datasets, suggesting that the gain is not tied to a single model or benchmark\.

The advantage becomes largest when the KV budget is most restrictive\.At the 20% budget in Table[1](https://arxiv.org/html/2609.22158#S6.T1), H2O, TOVA, and TokenSkipping frequently degrade to near\-zero EM and very low F1, especially on HotpotQA and 2WikiMultihopQA\. Through further analysis, we attribute this severe performance degradation to*Reasoning Continuity Disruption*\. When critical intermediate information is aggressively removed, the agent loses awareness of previously generated reasoning context and may repeatedly generate similar tokens or redundant reasoning patterns, preventing effective progress toward the final answer\.

In contrast, StepKV consistently maintains usable performance across all datasets\. We attribute this robustness to two key designs\. First, StepKV adopts astep\-wise generation before compressionstrategy, which allows the agent to complete an entire reasoning step before performing KV eviction\. Unlike token\-only compression methods that prune tokens within an ongoing reasoning step, this design preserves the internal coherence and information flow of the current reasoning process\. Second, StepKV introduces astep\-aware scoring mechanismto estimate the importance of each reasoning step and combines it with token\-level importance for cache selection\. By assigning higher retention priority to tokens belonging to critical reasoning steps, StepKV preserves essential reasoning trajectories while effectively removing redundant information\.

Figure 4\.Performance–cost trade\-off on BrowseComp\-Plus for Qwen2\.5\-7B\-Instruct \(left\) and Llama3\.1\-8B\-Instruct \(right\)\. Lower normalized cache and time values indicate lower cost\.Moderate compression can preserve much of the full\-cache behavior when allocation is step\-aware\.At the 50% budget, StepKV substantially narrows the gap to Full KV and sometimes approaches the reference results, whereas Token\-only methods still lose large portions of the QA accuracy\. This shows that the benefit is not merely a rescue effect at extreme budgets; it also improves the practical operating range of cache compression\.

Figure 5\.Comparison of inference latency and final KV cache size under different KV cache strategies\.The advantage extends to substantially more challenging and long\-horizon agent trajectories\.Figure[4](https://arxiv.org/html/2609.22158#S6.F4)evaluates StepKV on BrowseComp\-Plus, a challenging long\-horizon web reasoning benchmark with interaction histories exceeding 100K tokens\. Such extremely long trajectories pose significant challenges for KV cache management, as redundant historical context may interfere with subsequent reasoning\. As shown in Figure[4](https://arxiv.org/html/2609.22158#S6.F4), StepKV substantially reduces KV cache size and inference latency while even improving EM and F1 over Full KV under compressed settings\. This demonstrates that ultra\-long agent trajectories contain redundant information and that StepKV can effectively identify low\-utility tokens while preserving critical reasoning dependencies\. The significant latency reduction further verifies the scalability of StepKV for long\-context agent inference\.

### 6\.3\.Practical Cost in general Agent Reasoning \(RQ2\)

StepKV turns cache reduction into a usable cost\-quality trade\-off rather than a pure memory\-saving heuristic\.Figure[5](https://arxiv.org/html/2609.22158#S6.F5)compares peak KV cache statistics and inference latency across Full KV, token\-only methods, and StepKV under the same budget settings, while Table[1](https://arxiv.org/html/2609.22158#S6.T1)provides the corresponding task\-quality evidence for compressed QA inference\.

Cache savings are meaningful only when reasoning continuity is preserved\.As shown in Figure[5](https://arxiv.org/html/2609.22158#S6.F5), compressed settings generally reduce KV cache size compared with Full KV\. However, token\-only methods may fail to achieve the expected reduction under the same compression ratio\. Aggressive token pruning can disrupt the reasoning trajectory, causing the agent to lose critical intermediate information and generate longer, redundant reasoning sequences\. As a result, the final KV cache can exceed the expected budget despite applying the same compression ratio\.

StepKV effectively avoids this reasoning overhead by preserving reasoning continuity\.Unlike token\-only compression methods that perform eviction directly at the token level during generation, StepKV preserves the integrity of each reasoning step and prioritizes tokens from important reasoning steps through step\-aware scoring\. As a result, StepKV achieves substantially lower inference latency and smaller KV cache usage while maintaining higher EM and F1 under the same budgets\. These results demonstrate that effective KV cache compression requires not only reducing stored tokens, but also preserving the critical reasoning trajectory, enabling StepKV to approach Full KV performance with significantly fewer cached tokens\.

Table 2\.Detailed component ablation of Step Score in StepKV on MuSiQue\.Table 3\.Component ablation of StepKV on three benchmarks\.
### 6\.4\.Reasoning Depth and Compressed\-Cache Performance \(RQ3\)

Compression becomes harder as reasoning trajectories grow deeper\.Figure[6](https://arxiv.org/html/2609.22158#S6.F6)groups samples by reasoning\-step count; deeper bins show lower EM/F1, especially under tighter budgets\.

The depth effect reflects cross\-step dependence rather than only longer token sequences\.In Figure[6](https://arxiv.org/html/2609.22158#S6.F6), deeper samples require earlier evidence across more later decisions, matching the continuity\-disruption analysis in Section[4](https://arxiv.org/html/2609.22158#S4)\.

![Refer to caption](https://arxiv.org/html/2609.22158v1/stepwise.png)Figure 6\.Accuracy grouped by the number of reasoning steps\.![Refer to caption](https://arxiv.org/html/2609.22158v1/hyperparameter_analysis.png)Figure 7\.Influence of the step score hyperparameter on model performance\.
### 6\.5\.Contribution of Step\-Level Signals \(RQ4\)

Step\-level utility is most effective when paired with token saliency\.Figure[7](https://arxiv.org/html/2609.22158#S6.F7)varies the relative weight ofSkS\_\{k\}in the weighted token\-step ranking; intermediate values perform best\.

StepKV maintains a more balanced cache across prior and newly completed steps\.Figure[8](https://arxiv.org/html/2609.22158#S6.F8)decomposes the retained cache at each reasoning boundary into tokens from prior steps and tokens from the current step\. Under H2O and TOVA, the retained fraction of prior\-step tokens drops sharply or fluctuates as token\-wise saliency reallocates the budget\. StepKV instead maintains a larger and more stable share of prior\-step context through the early and middle stages of the trajectory, while continuing to retain tokens from the newly completed step\. The balance still changes across boundaries, indicating utility\-sensitive allocation rather than uniform protection of every step\.

This allocation directly addresses the two continuity failures observed in Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\.In Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(b\)](https://arxiv.org/html/2609.22158#S3.F2.sf2)\), StepKV preserves early step cohorts across later reasoning stages, while H2O and TOVA rapidly discard them\. Meanwhile, the nonzero current\-step allocation in Figure[8](https://arxiv.org/html/2609.22158#S6.F8)prevents historical retention from overwhelming recent context\. As shown in Figure[2](https://arxiv.org/html/2609.22158#S3.F2)\([2\(a\)](https://arxiv.org/html/2609.22158#S3.F2.sf1)\), StepKV performs more selective eviction across source steps instead of fragmenting the reasoning trajectory\. These results demonstrate that step utility maintains coherent step context, delayed reuse restores the importance of previously useful steps, and token saliency provides fine\-grained selection within each step\.

Figure 8\.Retained\-cache composition across reasoning steps for H2O \(top\), TOVA \(middle\), and StepKV \(bottom\)\. Filled regions separate prior\-step and current\-step cache populations; marker lines report kept\-token counts, and dotted or dash\-dotted lines report the corresponding retained percentages\.Step utility and token saliency provide complementary evidence for cache selection\.Table[3](https://arxiv.org/html/2609.22158#S6.T3)compares the full method with variants that remove either signal\. Removing the step score causes the larger and more consistent degradation across models and benchmarks, while removing token saliency also hurts most settings, especially MuSiQue\. The full method therefore benefits from modeling trajectory\-level importance without discarding token\-level evidence\.

Each field\-level signal makes a distinct contribution to the step score\.Table[2](https://arxiv.org/html/2609.22158#S6.T2)shows that removing observation validity, evidence gain, action redundancy, or delayed reuse reduces both EM and F1 on MuSiQue\. No single cue accounts for the full improvement, supporting the use of immediate step quality together with relevance revealed later in the trajectory\.

## 7\.Conclusion

We proposeStepKV, a step\-aware KV cache compression framework tailored for LLM agents\. Traditional token\-centric methods often degrade agent reasoning by ignoring its structured nature and dropping crucial context prematurely\. To address this, StepKV introduces astep\-level perspectivethat effectively captures the structured reasoning trajectories of agents and the delayed reuse of intermediate steps\. Byjointly optimizing step\-level utility and token\-level saliency, StepKV preserves essential reasoning paths while drastically reducing KV cache memory and computational overhead\. Extensive experiments show that StepKV achieves superior performance and a markedly better accuracy–efficiency trade\-off across complex tool\-use multi\-hop QA and long\-horizon web search tasks\.

## References

- J\. Ainslie, J\. Lee\-Thorp, M\. de Jong, Y\. Zemlyanskiy, F\. Lebrón, and S\. SanghaiGQA: training generalized multi\-query transformer models from multi\-head checkpoints\.External Links:2305\.13245,[Link](https://arxiv.org/abs/2305.13245)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Caiet al\.\(2026\)Z\. Cai, W\. Xiao, H\. Sun, C\. Luo, Y\. Zhang, K\. Wan, Y\. Li, Y\. Zhou, L\. Chang, J\. Gu, Z\. Dong, A\. Anandkumar, A\. Asi, and J\. HuR\-KV: redundancy\-aware KV cache compression for reasoning models\.External Links:2505\.24133,[Link](https://arxiv.org/abs/2505.24133)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Chenet al\.\(2025\)Z\. Chen, X\. Ma, S\. Zhuang, P\. Nie, K\. Zou, S\. Sharifymoghaddam, A\. Liu, J\. Green, K\. Patel, R\. Meng,et al\.Browsecomp\-plus: a more fair and transparent evaluation benchmark of deep\-research agent\.InFirst Workshop on Multi\-Turn Interactions in Large Language Models,Cited by:[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p1.1)\.
- DeepSeek\-AI \(2024\)DeepSeek\-AIDeepSeek\-V2: a strong, economical, and efficient mixture\-of\-experts language model\.External Links:2405\.04434,[Link](https://arxiv.org/abs/2405.04434)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Geet al\.\(2024\)S\. Ge, Y\. Zhang, L\. Liu, M\. Zhang, J\. Han, and J\. GaoModel tells you what to discard: adaptive KV cache compression for LLMs\.External Links:2310\.01801,[Link](https://arxiv.org/abs/2310.01801)Cited by:[§1](https://arxiv.org/html/2609.22158#S1.p3.1),[§5\.2](https://arxiv.org/html/2609.22158#S5.SS2.p1.1)\.
- Grattafioriet al\.\(2024\)A\. Grattafiori, A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Vaughan,et al\.The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§D\.1](https://arxiv.org/html/2609.22158#A4.SS1.p1.1),[§6\.2](https://arxiv.org/html/2609.22158#S6.SS2.p1.1)\.
- Gu and Dao \(2024\)A\. Gu and T\. DaoMamba: linear\-time sequence modeling with selective state spaces\.External Links:2312\.00752,[Link](https://arxiv.org/abs/2312.00752)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Hoet al\.\(2020\)X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. AizawaConstructing a multi\-hop qa dataset for comprehensive evaluation of reasoning steps\.InProceedings of the 28th International Conference on Computational Linguistics,pp\. 6609–6625\.Cited by:[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p1.1)\.
- Hongthai and Chuangsuwanich \(2025\)N\. Hongthai and E\. ChuangsuwanichTokenSkipping: a practical and robust kv cache pruning method for long\-context llm inference\.InProceedings of the 13th International Conference on Information Technology: IoT and Smart City,pp\. 195–200\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1),[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p2.1)\.
- Huet al\.\(2025\)J\. Hu, W\. Huang, W\. Wang, Z\. Li, T\. Hu, Z\. Liu, X\. Chen, T\. Xie, and Y\. ShanRaaS: reasoning\-aware attention sparsity for efficient LLM reasoning\.External Links:2502\.11147,[Link](https://arxiv.org/abs/2502.11147)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Jianget al\.\(2023\)H\. Jiang, Q\. Wu, C\. Lin, Y\. Yang, and L\. QiuLlmlingua: compressing prompts for accelerated inference of large language models\.InProceedings of the 2023 conference on empirical methods in natural language processing,pp\. 13358–13376\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p3.1)\.
- Jianget al\.\(2024\)H\. Jiang, Q\. Wu, X\. Luo, D\. Li, C\. Lin, Y\. Yang, and L\. QiuLongllmlingua: accelerating and enhancing llms in long context scenarios via prompt compression\.InProceedings of the 62nd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 1658–1677\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p3.1)\.
- Kariyappa and Suh \(2026\)S\. Kariyappa and G\. E\. SuhSideQuest: model\-driven KV cache management for long\-horizon agentic reasoning\.External Links:2602\.22603,[Link](https://arxiv.org/abs/2602.22603)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p3.1),[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Liet al\.\(2026\)J\. Li, J\. Lou, and J\. LiIntentKV: cross\-turn intent\-aware KV cache pruning for agent inference\.External Links:2606\.09916,[Link](https://arxiv.org/abs/2606.09916)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p3.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Liet al\.\(2024\)Y\. Li, Y\. Huang, B\. Yang, B\. Venkitesh, A\. Locatelli, H\. Ye, T\. Cai, P\. Lewis, and D\. ChenSnapKV: LLM knows what you are looking for before generation\.External Links:2404\.14469,[Link](https://arxiv.org/abs/2404.14469)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p6.1),[§1](https://arxiv.org/html/2609.22158#S1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1),[§5\.2](https://arxiv.org/html/2609.22158#S5.SS2.p1.1)\.
- Liuet al\.\(2023a\)N\. F\. Liu, K\. Lin, J\. Hewitt, A\. Paranjape, M\. Bevilacqua, F\. Petroni, and P\. LiangLost in the middle: how language models use long contexts\.arXiv preprint arXiv:2307\.03172\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p3.1)\.
- Liuet al\.\(2023b\)Z\. Liu, A\. Desai, F\. Liao, W\. Wang, V\. Xie, Z\. Xu, A\. Kyrillidis, and A\. ShrivastavaScissorhands: exploiting the persistence of importance hypothesis for llm kv cache compression at test time\.Advances in Neural Information Processing Systems36,pp\. 52342–52364\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p5.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Maet al\.\(2026\)B\. Ma, J\. Eitzinger, and H\. KöstlerLeyline: KV cache directives for agentic inference\.External Links:2606\.01065,[Link](https://arxiv.org/abs/2606.01065)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p3.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Nakanoet al\.\(2022\)R\. Nakano, J\. Hilton, S\. Balaji, J\. Wu, L\. Ouyang, C\. Kim, C\. Hesse, S\. Jain, V\. Kosaraju, W\. Saunders, X\. Jiang, K\. Cobbe, T\. Eloundou, G\. Krueger, K\. Button, M\. Knight, B\. Chess, and J\. SchulmanWebGPT: browser\-assisted question\-answering with human feedback\.External Links:2112\.09332,[Link](https://arxiv.org/abs/2112.09332)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Orenet al\.\(2024\)M\. Oren, M\. Hassid, N\. Yarden, Y\. Adi, and R\. SchwartzTransformers are multi\-state rnns\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,pp\. 18724–18741\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p6.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1),[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p2.1)\.
- Packeret al\.\(2023\)C\. Packer, V\. Fang, S\. Patil, K\. Lin, S\. Wooders, and J\. GonzalezMemGPT: towards llms as operating systems\.\.Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p2.1)\.
- Parket al\.\(2023\)J\. S\. Park, J\. O’Brien, C\. J\. Cai, M\. R\. Morris, P\. Liang, and M\. S\. BernsteinGenerative agents: interactive simulacra of human behavior\.InProceedings of the 36th annual acm symposium on user interface software and technology,pp\. 1–22\.Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p2.1)\.
- Popeet al\.\(2022\)R\. Pope, S\. Douglas, A\. Chowdhery, J\. Devlin, J\. Bradbury, A\. Levskaya, J\. Heek, K\. Xiao, S\. Agrawal, and J\. DeanEfficiently scaling transformer inference\.External Links:2211\.05102,[Link](https://arxiv.org/abs/2211.05102)Cited by:[§1](https://arxiv.org/html/2609.22158#S1.p1.1)\.
- Ramachandranet al\.\(2026\)A\. Ramachandran, M\. Neseem, C\. Sakr, R\. Venkatesan, B\. Khailany, and T\. KrishnaThinKV: thought\-adaptive KV cache compression for efficient reasoning models\.External Links:2510\.01290,[Link](https://arxiv.org/abs/2510.01290)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Raposoet al\.\(2024\)D\. Raposo, S\. Ritter, B\. Richards, T\. Lillicrap, P\. C\. Humphreys, and A\. SantoroMixture\-of\-depths: dynamically allocating compute in transformer\-based language models\.arXiv preprint arXiv:2404\.02258\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1)\.
- Schicket al\.\(2023\)T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, L\. Zettlemoyer, N\. Cancedda, and T\. ScialomToolformer: language models can teach themselves to use tools\.External Links:2302\.04761,[Link](https://arxiv.org/abs/2302.04761)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Shinnet al\.\(2023\)N\. Shinn, F\. Cassano, E\. Berman, A\. Gopinath, K\. Narasimhan, and S\. YaoReflexion: language agents with verbal reinforcement learning\.External Links:2303\.11366,[Link](https://arxiv.org/abs/2303.11366)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Sukhbaataret al\.\(2019\)S\. Sukhbaatar, E\. Grave, P\. Bojanowski, and A\. JoulinAdaptive attention span in transformers\.InProceedings of the 57th Annual Meeting of the Association for Computational Linguistics,pp\. 331–335\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1)\.
- Tanget al\.\(2024\)J\. Tang, Y\. Zhao, K\. Zhu, G\. Xiao, B\. Kasikci, and S\. HanQuest: query\-aware sparsity for efficient long\-context llm inference\.arXiv preprint arXiv:2406\.10774\.Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p6.1)\.
- Trivediet al\.\(2022\)H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. SabharwalMuSiQue: multihop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics10,pp\. 539–554\.Cited by:[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p1.1)\.
- Vaswaniet al\.\(2017\)A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. PolosukhinAttention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30,Red Hook, NY, USA,pp\. 5998–6008\.External Links:[Link](https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html)Cited by:[§1](https://arxiv.org/html/2609.22158#S1.p1.1)\.
- Wuet al\.\(2025\)J\. Wu, Z\. Wang, L\. Zhang, Y\. Lai, Y\. He, and D\. ZhouSCOPE: optimizing key\-value cache compression in long\-context generation\.External Links:2412\.13649,[Link](https://arxiv.org/abs/2412.13649)Cited by:[§1](https://arxiv.org/html/2609.22158#S1.p3.1),[§5\.2](https://arxiv.org/html/2609.22158#S5.SS2.p1.1)\.
- Xiaoet al\.\(2024\)G\. Xiao, Y\. Tian, B\. Chen, S\. Han, and M\. LewisEfficient streaming language models with attention sinks\.External Links:2309\.17453,[Link](https://arxiv.org/abs/2309.17453)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§1](https://arxiv.org/html/2609.22158#S1.p1.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Yanget al\.\(2024\)A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. QiuQwen2\.5 technical report\.arXiv preprint arXiv:2412\.15115\.Cited by:[§D\.1](https://arxiv.org/html/2609.22158#A4.SS1.p1.1),[§6\.2](https://arxiv.org/html/2609.22158#S6.SS2.p1.1)\.
- Yanget al\.\(2025\)S\. Yang, J\. Kautz, and A\. HatamizadehGated delta networks: improving mamba2 with delta rule\.External Links:2412\.06464,[Link](https://arxiv.org/abs/2412.06464)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Yanget al\.\(2018\)Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. ManningHotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p1.1)\.
- Yaoet al\.\(2023\)S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. CaoReAct: synergizing reasoning and acting in language models\.External Links:2210\.03629,[Link](https://arxiv.org/abs/2210.03629)Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p2.1),[§2\.1](https://arxiv.org/html/2609.22158#S2.SS1.p1.1)\.
- Yuanet al\.\(2025\)J\. Yuan, H\. Gao, D\. Dai, J\. Luo, L\. Zhao, Z\. Zhang, Z\. Xie, Y\. X\. Wei, L\. Wang, Z\. Xiao, Y\. Wang, C\. Ruan, M\. Zhang, W\. Liang, and W\. ZengNative sparse attention: hardware\-aligned and natively trainable sparse attention\.External Links:2502\.11089,[Link](https://arxiv.org/abs/2502.11089)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p2.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Zhanget al\.\(2025\)H\. Zhang, H\. Zhang, X\. Ma, J\. Zhang, and S\. GuoLazyEviction: lagged KV eviction with attention pattern observation for efficient long reasoning\.External Links:2506\.15969,[Link](https://arxiv.org/abs/2506.15969)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p7.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1)\.
- Zhanget al\.\(2023\)Z\. Zhang, Y\. Sheng, T\. Zhou, T\. Chen, L\. Zheng, R\. Cai, Z\. Song, Y\. Tian, C\. Ré, C\. Barrett, Z\. Wang, and B\. ChenH2\{\}\_\{2\}O: heavy\-hitter oracle for efficient generative inference of large language models\.External Links:2306\.14048,[Link](https://arxiv.org/abs/2306.14048)Cited by:[§B\.2](https://arxiv.org/html/2609.22158#A2.SS2.p5.1),[§1](https://arxiv.org/html/2609.22158#S1.p1.1),[§1](https://arxiv.org/html/2609.22158#S1.p3.1),[§2\.2](https://arxiv.org/html/2609.22158#S2.SS2.p1.1),[§5\.2](https://arxiv.org/html/2609.22158#S5.SS2.p1.1),[§6\.1](https://arxiv.org/html/2609.22158#S6.SS1.p2.1)\.
- Zhonget al\.\(2024\)W\. Zhong, L\. Guo, Q\. Gao, H\. Ye, and Y\. WangMemorybank: enhancing large language models with long\-term memory\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 19724–19731\.Cited by:[§B\.1](https://arxiv.org/html/2609.22158#A2.SS1.p2.1)\.

## Appendix ANotation Summary

Table 4\.Notation used in the problem formulation and methodology\.
## Appendix BRelated Work

### B\.1\.LLM Agents

LLM agents extend language\-model inference from single\-pass generation to interactive trajectories\. Agent frameworks such as ReAct interleave reasoning and tool use through repeated Thought, Action, and Observation steps\([Yao et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib23)\), while related systems leverage external tools, web interaction, reflection, or self\-improvement mechanisms to enhance task completion over multiple interactions\([Schick et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib17);[Nakano et al\., 2022](https://arxiv.org/html/2609.22158#bib.bib14);[Shinn et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib18)\)\.

Beyond tool use and planning, recent studies have emphasized the importance of long\-term context management and memory mechanisms for agent systems\. MemGPT\([Packer et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib34)\)views LLMs as systems with hierarchical memory, where information is selectively managed across different memory tiers\. Generative Agents\([Park et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib35)\)and MemoryBank\([Zhong et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib36)\)further explore how agents maintain, retrieve, and reuse historical experiences during extended interactions\. These works highlight an important property of agent trajectories: the value of intermediate information is not always observable when it is generated, and may only emerge when later interactions depend on previously acquired knowledge\.

This setting changes the role of context in LLM inference\. Rather than conditioning only on a fixed prompt and a generated answer prefix, an agent continuously accumulates intermediate observations, retrieved evidence, and decisions whose usefulness may appear at different stages of reasoning\. Most agent research focuses on planning, tool selection, retrieval, memory design, and task performance, while the KV cache is often treated as an underlying inference mechanism\. Recent work has started to investigate cache management for agentic inference, including model\-driven, directive\-based, and intent\-aware approaches that determine which parts of an interaction trajectory should be retained\([Kariyappa and Suh, 2026](https://arxiv.org/html/2609.22158#bib.bib10);[Ma et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib13);[Li et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib12)\)\.

StepKV is complementary to these directions\. Instead of designing an additional external memory module or changing the agent framework, StepKV focuses on fine\-grained retention within the KV cache and allocates a fixed cache budget using both token\-level saliency and step\-level utility\. This distinction is important because agent trajectories contain semantic step boundaries that are not explicitly represented in a flat token stream, and preserving information aligned with these boundaries can help maintain reasoning continuity under aggressive cache compression\.

### B\.2\.KV Cache Management

A broad line of research seeks to reduce the memory, bandwidth, and computational costs of long\-context LLM inference through architectural changes, context compression, selective attention, and explicit KV cache management\.

Architecture\- and attention\-level optimization\.Architecture\-level approaches reduce the cost of representing or processing long contexts\. Grouped\-Query Attention \(GQA\)\([Ainslie et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib1)\)and Multi\-Head Latent Attention \(MLA\)\([DeepSeek\-AI, 2024](https://arxiv.org/html/2609.22158#bib.bib3)\)reduce the memory footprint of KV representations by modifying the attention architecture, while Native Sparse Attention\([Yuan et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib24)\)reduces long\-context computation by selectively activating relevant tokens\. State\-space and hybrid architectures, such as Mamba\([Gu and Dao, 2024](https://arxiv.org/html/2609.22158#bib.bib5)\)and Gated Delta Networks\([Yang et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib22)\), further reduce reliance on full attention for modeling long\-range dependencies\. Beyond architectural optimization, adaptive computation methods dynamically allocate resources according to input characteristics\. Adaptive Attention Span\([Sukhbaatar et al\., 2019](https://arxiv.org/html/2609.22158#bib.bib37)\)learns different attention ranges for different tokens, while Mixture\-of\-Depths\([Raposo et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib38)\)dynamically allocates computation across tokens during inference\. Although these approaches improve long\-context efficiency, they mainly optimize how contextual representations are computed or stored and do not explicitly determine which historical KV entries should be retained as an agent trajectory evolves\.

Long\-context compression\.Another line of work focuses on removing redundant contextual information before or during inference\. LLMLingua\([Jiang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib39)\)and LongLLMLingua\([Jiang et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib40)\)compress input contexts by identifying less informative tokens, improving efficiency in long\-context scenarios\. Meanwhile, Lost in the Middle\([Liu et al\., 2023a](https://arxiv.org/html/2609.22158#bib.bib41)\)demonstrates that LLMs may struggle to effectively utilize information distributed across long contexts, suggesting that retaining all historical information does not necessarily lead to better reasoning\. These studies motivate selective context retention strategies that preserve useful information while reducing unnecessary context\.

Decode\-stage KV cache management\.In contrast to input compression, decode\-stage KV cache management selectively retains historical KV states as the cache grows during autoregressive generation\. Existing approaches commonly estimate the importance of individual tokens using several types of signals\.

First,accumulated\-importance methodsuse historical statistics collected throughout generation\. H2O\([Zhang et al\., 2023](https://arxiv.org/html/2609.22158#bib.bib25)\)identifies heavy\-hitter tokens according to accumulated attention scores, while Scissorhands\([Liu et al\., 2023b](https://arxiv.org/html/2609.22158#bib.bib8)\)studies persistent token importance across generation steps\. These methods effectively capture long\-term relevance but primarily rely on token\-level historical statistics\.

Second,recent\-attention methodsestimate cache importance from current or recent attention distributions\. TOVA\([Oren et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib7)\)performs online eviction by retaining tokens that receive higher attention from recent queries; SnapKV\([Li et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib11)\)analyzes local attention patterns and preserves representative tokens from important attention regions; and Quest\([Tang et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib33)\)improves cache selection through query\-aware importance estimation\. However, attention patterns at the current decoding stage may not fully reflect the future contribution of tokens in long\-horizon reasoning\.

Third,heuristic and reasoning\-aware methodsreduce KV cache size using predefined rules, structural assumptions, or additional reasoning signals\. TokenSkipping\([Hongthai and Chuangsuwanich, 2025](https://arxiv.org/html/2609.22158#bib.bib9)\)periodically removes tokens using heuristic skipping strategies, whereas StreamingLLM\([Xiao et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib21)\)preserves attention\-sink tokens and recent context based on observed attention behavior\. Recent reasoning\-oriented methods, including R\-KV\([Cai et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib2)\), RaaS\([Hu et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib6)\), LazyEviction\([Zhang et al\., 2025](https://arxiv.org/html/2609.22158#bib.bib26)\), ThinKV\([Ramachandran et al\., 2026](https://arxiv.org/html/2609.22158#bib.bib16)\), and SideQuest\([Kariyappa and Suh, 2026](https://arxiv.org/html/2609.22158#bib.bib10)\), further explore redundancy\-aware or reasoning\-aware cache reduction\.

Nevertheless, most existing methods remain predominantly token\-centric or do not explicitly model the semantic utility of complete reasoning steps\. In contrast, StepKV introduces step\-aware cache allocation for agent reasoning: rather than treating all tokens independently, it combines step\-level utility with token\-level saliency to preserve critical reasoning trajectories while removing redundant context\.

## Appendix CAnalysis of Step\-aware Score Scaling

### C\.1\.Step Score

##### Definition of step utility\.

Let𝒮\\mathcal\{S\}denote the set of reasoning steps generated during agent inference\. Instead of assigning importance solely from individual tokens, StepKV introduces a step\-level utility function:

\(6\)U:𝒮→\[0,Umax\],U:\\mathcal\{S\}\\rightarrow\[0,U\_\{\\max\}\],
whereUsU\_\{s\}represents the contribution of reasoning stepssto the overall reasoning trajectory\.

The step utility is computed based on two complementary signals: the immediate progression signal and the delayed reuse signal:

\(7\)Us=clip⁡\(wr​Rs\+wc​log⁡\(1\+Cs\),0,Umax\),U\_\{s\}=\\operatorname\{clip\}\\left\(w\_\{r\}R\_\{s\}\+w\_\{c\}\\log\(1\+C\_\{s\}\),0,U\_\{\\max\}\\right\),
wherewr,wc≥0w\_\{r\},w\_\{c\}\\geq 0are weighting coefficients\.

The progression signal is defined as:

\(8\)Rs=succs\+novs−λ​reps,R\_\{s\}=\\mathrm\{succ\}\_\{s\}\+\\mathrm\{nov\}\_\{s\}\-\\lambda\\mathrm\{rep\}\_\{s\},
wheresuccs∈\{0,1\}\\mathrm\{succ\}\_\{s\}\\in\\\{0,1\\\}indicates whether the step produces valid progress,novs∈\[0,1\]\\mathrm\{nov\}\_\{s\}\\in\[0,1\]measures the novelty ratio of the step, andreps≥0\\mathrm\{rep\}\_\{s\}\\geq 0denotes the repetition degree\.

Since the maximum positive contribution of the progression term is bounded by:

\(9\)succs\+novs≤2,\\mathrm\{succ\}\_\{s\}\+\\mathrm\{nov\}\_\{s\}\\leq 2,
the progression signal satisfies:

\(10\)Rs∈\(−∞,2\]\.R\_\{s\}\\in\(\-\\infty,2\]\.
To capture whether information from an earlier step is reused by later reasoning steps, we accumulate the delayed reuse signal:

\(11\)Cs\(t\)=Cs\(t−1\)\+Δ​Cs→t,C\_\{s\}^\{\(t\)\}=C\_\{s\}^\{\(t\-1\)\}\+\\Delta C\_\{s\\rightarrow t\},
where:

\(12\)0≤Δ​Cs→t≤1\.0\\leq\\Delta C\_\{s\\rightarrow t\}\\leq 1\.
Therefore:

The logarithmic transformation prevents long reasoning trajectories from causing unbounded growth of the reuse signal\. After applying clipping, the final step utility is guaranteed to satisfy:

\(14\)Us∈\[0,Umax\]\.U\_\{s\}\\in\[0,U\_\{\\max\}\]\.

##### Combination with token\-level importance\.

For each tokeni∈𝒯i\\in\\mathcal\{T\}, lets⁡\(i\)s\(i\)denote its corresponding reasoning step\. StepKV combines token\-level importance and step\-level utility as:

\(15\)Scorei=α​Hi\+β​Us⁡\(i\),\\mathrm\{Score\}\_\{i\}=\\alpha H\_\{i\}\+\\beta U\_\{s\(i\)\},
whereHiH\_\{i\}represents the token\-level importance score obtained from attention statistics, andα,β≥0\\alpha,\\beta\\geq 0control the contribution of each component\.

Assuming the token importance is normalized as:

\(16\)Hi∈\[0,Hmax\],H\_\{i\}\\in\[0,H\_\{\\max\}\],
the token score has the following range:

\(17\)Scorei∈\[0,α​Hmax\+β​Umax\]\.\\mathrm\{Score\}\_\{i\}\\in\[0,\\alpha H\_\{\\max\}\+\\beta U\_\{\\max\}\]\.

##### Rationale of score range design\.

The step utility is designed as a bounded auxiliary signal rather than a replacement for token\-level importance\. The objective is to introduce reasoning\-level awareness while preserving the fine\-grained discrimination ability of token scores\.

Specifically, the contribution of the step utility is bounded by:

\(18\)0≤β​Us⁡\(i\)≤β​Umax\.0\\leq\\beta U\_\{s\(i\)\}\\leq\\beta U\_\{\\max\}\.
Therefore, the step\-level component mainly affects tokens with similar token\-level importance scores\. For two tokensiiandjj, the token from a more important reasoning step is preferred when:

\(19\)α⁡\(Hi−Hj\)<β⁡\(Us⁡\(j\)−Us⁡\(i\)\)\.\\alpha\(H\_\{i\}\-H\_\{j\}\)<\\beta\(U\_\{s\(j\)\}\-U\_\{s\(i\)\}\)\.
However, when a token has substantially higher intrinsic importance, the token\-level score can overcome the step\-level preference:

\(20\)α⁡\(Hi−Hj\)\>β⁡\(Us⁡\(j\)−Us⁡\(i\)\)\.\\alpha\(H\_\{i\}\-H\_\{j\}\)\>\\beta\(U\_\{s\(j\)\}\-U\_\{s\(i\)\}\)\.
This property prevents the step utility from dominating cache selection\. Instead, StepKV follows a hierarchical importance principle: the step utility provides global reasoning\-level guidance by protecting valuable reasoning steps, while the token\-level score preserves critical tokens within or across different steps\.

Consequently, StepKV can retain important reasoning trajectories without sacrificing the ability to select highly salient individual tokens\.

### C\.2\.Time Complexity Analysis

At the pruning boundary after steptt, new\-step scoring and previous\-step updating compare the current fields with at mostt−1t\-1earlier steps\. Because each field uses a fixed cap of 64 evidence cues, each overlap computation is bounded, yieldingO⁡\(t\)O\(t\)step\-level overhead\. Given token saliency scores, combiningTiT\_\{i\}with its source\-step utility addsO⁡\(Nt\)O\(N\_\{t\}\)work\. In our implementation,TiT\_\{i\}is collected during the existing observation prefill and requires no additional model pass\.

The selector globally ranksNtN\_\{t\}token scores, with a worst\-case cost ofO⁡\(Nt​log⁡Nt\)O\(N\_\{t\}\\log N\_\{t\}\)\. Therefore, StepKV addsO⁡\(Nt​log⁡Nt\+t\)O\(N\_\{t\}\\log N\_\{t\}\+t\)time per pruning boundary, dominated by token ranking\. Since every completed step contributes at least one trajectory token,t≤Ntt\\leq N\_\{t\}, and the worst\-case overhead simplifies toO⁡\(Nt​log⁡Nt\)O\(N\_\{t\}\\log N\_\{t\}\)\.

### C\.3\.StepKV Pseudocode

Algorithm[1](https://arxiv.org/html/2609.22158#algorithm1)summarizes the overall procedure of StepKV\. After each reasoning step is completed, StepKV first computes the step utility, then updates previous\-step utilities based on later reuse signals\. Finally, it combines step\-level utility with token\-level saliency to rank candidate tokens and retain the top tokens under the target cache budget\.

Algorithm 1StepKVInput:Prunable indices

ℐ\(t\)\\mathcal\{I\}^\{\(t\)\}, finalized steps

𝒮\(t\)\\mathcal\{S\}^\{\(t\)\}, keep ratio

ρ\\rho
Output:Selected set

𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}with

\|𝒦\(t\)\|=Bt\|\\mathcal\{K\}^\{\(t\)\}\|=B\_\{t\}
// Phase 1 \(new\-step scoring\)

Compute

validt\\mathrm\{valid\}\_\{t\},

gaint\\mathrm\{gain\}\_\{t\}, and

redt\\mathrm\{red\}\_\{t\}from

Tht\\mathrm\{Th\}\_\{t\},

Actt\\mathrm\{Act\}\_\{t\}, and

Obst\\mathrm\{Obs\}\_\{t\}; compute

rtr\_\{t\}via Equation \([2](https://arxiv.org/html/2609.22158#S5.E2)\)

Set

ct←0c\_\{t\}\\leftarrow 0and compute

StS\_\{t\}via Equation \([4](https://arxiv.org/html/2609.22158#S5.E4)\)

// Phase 2 \(previous\-step updating\)

foreach*previous step1≤k<t1\\leq k<t*do

Update

ckc\_\{k\}via Equation \([3](https://arxiv.org/html/2609.22158#S5.E3)\) and recompute

SkS\_\{k\}via Equation \([4](https://arxiv.org/html/2609.22158#S5.E4)\)

// Phase 3 \(score and select\)

Bt←max⁡\(1,⌊ρ​\|ℐ\(t\)\|⌋\)B\_\{t\}\\leftarrow\\max\(1,\\lfloor\\rho\|\\mathcal\{I\}^\{\(t\)\}\|\\rfloor\)

For each token

iiproduced by step

kk, compute

PiP\_\{i\}via Equation \([5](https://arxiv.org/html/2609.22158#S5.E5)\)

Select the top

BtB\_\{t\}tokens by

PiP\_\{i\}as

𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}
return*𝒦\(t\)\\mathcal\{K\}^\{\(t\)\}*

## Appendix DImplementation Details

### D\.1\.Experiments Details\.

We use Qwen2\.5\-7B\-Instruct\([Yang et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib28)\)and Llama3\.1\-8B\-Instruct\([Grattafiori et al\., 2024](https://arxiv.org/html/2609.22158#bib.bib27)\)as backbone models\. Full KV retains the complete cache without compression and serves as the 100% cache reference, while ReAct denotes the original reasoning framework without KV cache budget constraints\. All compressed methods use identical prompts, tools, decoding settings, maximum reasoning steps, pruning schedules, cache budgets, and random seeds to ensure a fair comparison\. Field similarity is computed based on the overlap of up to 64 extracted evidence cues\. Each experiment is repeated with three random seeds \(233, 42, and 3407\), and all reported results are presented as the mean±\\pmstandard deviation\. Unless otherwise specified, StepKV uses the default hyperparameters listed in Table[5](https://arxiv.org/html/2609.22158#A4.T5)\.

### D\.2\.Prompt Template

ReAct Prompt TemplateInstructionSolve a question answering task with interleaving*Thought*,*Action*, and*Observation*steps\.*Thought*can reason about the current situation, and*Action*can be three types:\(1\) Search\[entity\], which searches Wikipedia and returns the first paragraph if it exists\.\(2\) Lookup\[keyword\], which returns the next sentence containing keyword\.\(3\) Finish\[answer\], which returns the final answer and terminates the task\.Few\-shot ExampleQuestion: Musician and satirist Allie Goertz wrote a song about Milhouse, who was he named after?Thought 1: I should search Milhouse\.Action 1: Search\[Milhouse\]Observation 1: Milhouse is a character in The Simpsons\.Thought 2: I should look up naming origin\.Action 2: Lookup\[named after\]Observation 2: Milhouse was named after Richard Nixon\.Action 3: Finish\[Richard Nixon\]

Table 5\.Implementation hyperparameters and default settings for StepKV\.

## Appendix EAdditional experiments analysis

Step\-aware retention changes the retained context at both aggregate and trajectory levels\.Figure[9](https://arxiv.org/html/2609.22158#A5.F9)\([9\(a\)](https://arxiv.org/html/2609.22158#A5.F9.sf1)\) visualizes the HotpotQA token\-retention structure associated with the aggregate gains in Table[1](https://arxiv.org/html/2609.22158#S6.T1)\. Figure[9](https://arxiv.org/html/2609.22158#A5.F9)\([9\(b\)](https://arxiv.org/html/2609.22158#A5.F9.sf2)\) then shows the same mechanism in an individual trajectory: token\-level pruning removes intermediate evidence required by later reasoning, whereas StepKV preserves the relevant spans and completes the task successfully\.

![Refer to caption](https://arxiv.org/html/2609.22158v1/figure/hot.png)\(a\)Aggregate HotpotQA retention pattern\.
![Refer to caption](https://arxiv.org/html/2609.22158v1/figure/base_fail_our_run.png)\(b\)Baseline failure and StepKV success\.

Figure 9\.Step\-aware retention at two levels of analysis\. Panel \(a\) shows the aggregate token\-retention structure under cache compression, while panel \(b\) compares a baseline failure with a successful StepKV trajectory\.Aggregate and trajectory\-level analyses of how StepKV changes retained context\.Estimated step importance aligns with answer\-relevant evidence\.Figure[10](https://arxiv.org/html/2609.22158#A5.F10)compares high\-scoring, low\-scoring, and random steps using answer\-relevant keyword overlap\. High\-scoring steps contain more answer\-relevant content, supporting the design choice of assigning different retention pressure to different reasoning steps\.

![Refer to caption](https://arxiv.org/html/2609.22158v1/figure/offline.png)Figure 10\.Offline analysis of step contribution using answer\-relevant keyword overlap\.The step\-score weight changes the retained trajectory structure, not only the final metric\.Figure[11](https://arxiv.org/html/2609.22158#A5.F11)visualizes token\-retention patterns under different mixing weights, showing that the hyperparameter alters which parts of the trajectory remain available during decoding\. This explains why the performance sensitivity in Figure[7](https://arxiv.org/html/2609.22158#S6.F7)is tied to a real change in cache contents\.

![Refer to caption](https://arxiv.org/html/2609.22158v1/figure/beta.png)Figure 11\.Token\-retention patterns under different step\-score mixing weights\.
## Appendix FLimitations

Our current implementation estimates step utility using lightweight trajectory\-derived signals, which provides an efficient and training\-free solution but may introduce estimation uncertainty in challenging scenarios\. For example, the quality of these signals can be affected when action\-observation grounding is incomplete, tool responses are noisy, or important information is implicitly expressed and difficult to extract\. Moreover, our evaluation is conducted on a limited range of model scales and agent benchmarks\. Future work will extend the evaluation of StepKV to larger\-scale language models and more diverse agent tasks to further investigate its generalization and scalability\. Another promising direction is to develop more accurate and effective step utility estimation methods by exploiting richer internal signals, such as step\-level representations, hidden states, or other model\-intrinsic information, which may provide a more precise measurement of reasoning\-step importance beyond external trajectory signals\.