# StepCache: Step-Level Reuse with Lightweight Verification and Selective Patching for LLM Serving

arXiv: https://arxiv.org/abs/2603.28795 · HTML: https://mlsanity.com/paper/2603.28795/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 13 of its 14 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 13 of 13)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [BurstGPT: A Real-world Workload Dataset to Optimize LLM Serving Systems](https://mlsanity.com/paper/2401.17644/) (2024)
- [vCache: Verified Semantic Prompt Caching](https://mlsanity.com/paper/2502.03771/) (2025)
- [EVICPRESS: Joint KV-Cache Compression and Eviction for Efficient LLM Serving](https://mlsanity.com/paper/2512.14946/) (2025)
- [OrbitFlow: SLO-Aware Long-Context LLM Serving with Fine-Grained KV Cache Reconfiguration](https://mlsanity.com/paper/2601.10729/) (2026)
- [An MLP Baseline for Handwriting Recognition Using Planar Curvature and Gradient Orientation](https://mlsanity.com/paper/2508.11803/) (2025)
- [A Sobel-Gradient MLP Baseline for Handwritten Character Recognition](https://mlsanity.com/paper/2508.11902/) (2025)
- [Asynchronous Verified Semantic Caching for Tiered LLM Architectures](https://mlsanity.com/paper/2602.13165/) (2026)
- [Significance-Gain Pair Encoding for LLMs: A Statistical Alternative to Frequency-Based Subword Merging](https://mlsanity.com/paper/2603.19261/) (2026)

## Built on by (most cited first, 2 of 2)

- [MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization](https://mlsanity.com/paper/2609.31705/) (2026)
- [Inherit-MAS: Test-Time Evolution of Multi-Agent Systems through Workflow and Execution Inheritance](https://mlsanity.com/paper/2610.02396/) (2026)

## Abstract (arXiv)

We address LLM serving workloads where repeated requests share a common solution structure but differ in localized constraints, such as output schema, variable names, or numeric constants. Prior caching approaches typically reuse either full responses (semantic caching) or model-internal KV/prefix states, which are respectively brittle under partial changes or tightly coupled to specific backends. We present StepCache, a backend-agnostic step-level reuse layer that segments outputs into ordered steps, retrieves the best-matching cached request, verifies steps using lightweight task-aware checks, and regenerates only failing regions via selective patching. StepCache additionally supports strict structured-output enforcement for JSON, including single-step extraction, required-key constraints, and one-shot repair, as well as conservative skip-reuse fallbacks for semantic changes. For linear equations, StepCache promotes verification into correction via a bounded repair loop with a deterministic fallback that guarantees correctness when the backend model fails. In a CPU-only perturbation-heavy micro-benchmark on math and JSON variants, averaged over three seeds, StepCache reduces mean latency from 2.13 s to 0.67 s, median latency from 2.42 s to 0.01 s, and p95 latency from 3.38 s to 3.30 s. It also reduces total token usage from 36.1k to 27.3k and improves end-to-end correctness from 72.5% to 100% under task-specific checks and a stitched-output integrity check. Across requests, 79.7% take the reuse-only fast path, 5.4% require patching, and 14.9% trigger skip-reuse.