acceptodds
Under review as a conference paper at ICLR 2027

ReState: Enabling Cross-Query KV Reuse for Training-Free Acceleration of BERT Rerankers

Abstract

Rerankers play a key role in retrieval-augmented generation (RAG) by refining initially retrieved rankings with models specifically trained to score query–document relevance, including commonly used BERT-based cross-encoders. However, rerankers may repeatedly encode unchanged documents across queries, making reuse of precomputed document representations a natural way to reduce redundant computation. Yet document states in BERT rerankers depend on both query interactions and query-dependent positions, preventing exact reuse across queries. But can't encoders reuse keys and values? Reranking targets relevance ordering, motivating us to rethink the need to recompute every intermediate document state. To reduce repeated encoding, we propose ReState, a training-free method for approximate reuse of document keys and values (K/V) in BERT rerankers. Our central idea is to separate full-document reading from document-state updating: query and score tokens remain active and attend to every document position, while only selected document states are updated under the current query. To reduce quality loss from query-dependent document positions, we propose Taylor-based position approximation to compensate for positional changes through precomputed correction components. To recover ranking quality with limited recomputation, we design Score-anchored restoration to select update locations using offline score-token attention, without query-time model computation. Across six benchmarks with a frozen MiniLM reranker and prepared caches, ReState uses default routing and 20% document updates to achieve a mean online pipeline speedup while retaining 96.0% of Full's mean nDCG@10.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Cross-encoder reranking, KV reuse, Efficient inference, Selective recomputation, Retrieval-augmented generation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_yaQHOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

ReState accelerates frozen BERT rerankers through approximate cross-query reuse of document K/V states. It combines position correction with selective document updates, while preserving attention to all document tokens. An optional variant uses shallow query interactions to refine update selection. Across six ranking benchmarks, the default configuration reports a 6.857× mean speedup while retaining 96.0% of Full’s mean nDCG@10, under prepared-cache conditions with candidate routing. Additional experiments examine checkpoint transfer and downstream QA.

Critical strengths
  1. The method addresses a substantive obstacle to document-state reuse in bidirectional rerankers: both query interactions and absolute positions change document representations. Combining position correction with selective updates offers a useful training-free solution without changing the checkpoint or removing document tokens from attention.
  2. The controlled experiments separate positional errors, update selection, and candidate routing. Without routing, ReState still achieves a reported 4.041× speedup at 0.474 nDCG@10 versus Full’s 0.488 (Table 4), supporting a benefit from reuse itself. Full-restoration equivalence and transfer to additional BERT checkpoints further strengthen the validation.
Critical weaknesses
  1. The main comparison uses FP32 eager Full, whereas ReState uses fused Triton attention (Appendix A.8). The SDPA control in Table 9 evaluates 100% restoration, rather than the default 20% configuration. Consequently, the acceleration attributable to reuse over an optimized implementation of the same reranker remains uncertain.
Questions for authors
  1. What speedups do the default and no-routing configurations achieve against a tuned dense SDPA implementation, using the same checkpoint, precision, inputs, batching, and timing boundaries?
3 comments

We thank the reviewer for the careful reading and constructive feedback.

Following your suggestion, we compared ReState at 20% restoration with a tuned dense Full-SDPA baseline, and ReState still delivers substantial speedups over this stronger baseline. Specifically, using the same settings, ReState achieves a 6.50× speedup with default routing and 3.57× without routing. Because both methods score all 100 candidates in the no-routing setting, the latter speedup is attributable to reuse alone.

ReState (20% restoration)ms/querynDCG@10Speedup vs. tuned dense SDPA (87.99 ms/query, nDCG@10 = 0.4875)
Default (with routing)13.540.46786.50×
No routing24.620.47423.57×

Settings.

  • Checkpoint: the same frozen MiniLM-L12-v2.
  • Precision: FP32 for both.
  • Inputs: the same tokenized inputs.
  • Batching: the same query batches.
  • Timing boundaries: the paper's prepared-host protocol, including host-to-device cache transfer and excluding offline construction and backend reads.
  • Dense baseline tuning: for each dataset, the fastest of three FP32 SDPA implementations, with CUDA Graphs and batching tuned jointly.

Thank you for your responses and clarifications. The rebuttal and discussion have addressed most of my concerns, and I will raise my score. I appreciate your efforts to address my feedback.

Your in-depth review of this paper is greatly appreciated. We are also thankful for your acknowledgement of this work.

Reviewer_snREOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

BERT cross-encoder rerankers repeatedly encode unchanged documents across queries. Exact KV reuse fails because document states depend on query interactions and query-dependent positions. The authors propose ReState, a training-free method for approximate reuse of document representation. It separates full-document reading from document-state updating. Query and score tokens attend to every document position. Only selected document states are updated under the current query. Positional changes are corrected with a Taylor-based position approximation using precomputed correction components. Update locations are selected with score-anchored restoration using offline score-token attention. Across six benchmarks with a frozen MiniLM reranker and prepared caches, ReState uses default routing and 20% document updates to reach a 6.857x mean online pipeline speedup while retaining 96.0% of Full's mean nDCG@10

Critical strengths
  • The paper addresses an important and difficult efficiency bottleneck. Document KV reuse is established for causal rerankers but hard for bidirectional BERT, and the paper shows novelty in making training-free cross-query KV reuse work across all layers of a frozen query-first BERT reranker. The two obstacles of position shift and missing query interaction are cleanly separated and studied.
  • The Taylor-based position correction is a good technical contribution and mathematically sound. It uses offline-tabulated components to match target-position re-encoding quality without online differentiation or redundant cache copies.
  • Evaluation is comprehensive, covering six diverse retrieval benchmarks, isolating the individual contributions of routing versus reuse, verifying full-recompute numerical equivalence. Experiment rigor is good.
  • ReState beats all training-free baselines on mean nDCG and stays close to the training-required ones while being much faster.
  • The paper is honest about its own limits. It states that the storage cost is large, that the timing excludes backend reads, that the default operating point was not validated on held-out data, and that rotary transfer is architecture-specific.
Critical weaknesses
  • The method trades computation for storage but the cache footprint is massive and the evaluation ignores the storage I/O needs. Caching FP16 states requires 4.5 MiB per 256-token document, scaling to 4.292 TiB per million entries and 265.6 GiB for the evaluation pools. This is a huge requirement for a 33M-parameter MiniLM model requiring only about 130 MB in memory. This big a cache cannot realistically sit in a RAM. However, the reported 6.857x speedup measures execution only after caches are already packed in host memory, completely omitting disk reads and cache retrieval. Calling this an online pipeline speedup is misleading when the storage transfer that would dominate real deployment is never timed.

  • The 6.857x speedup relies heavily on candidate routing rather than KV reuse. Default routing filters out half the candidates using simple token matching, speeding up the dense baseline by 1.808x by itself. Without routing, the speedup from KV reuse drops to 4.041x (Table 4).

  • The Taylor position approximation breaks down at depth. Appendix A.7 acknowledges that this deep-layer correction is only a heuristic surrogate rather than a true derivative of the encoder blocks. Because error accumulates across layers, the model would retain more accurate states in its top layers without any Taylor correction.

  • The training-free claim breaks down on modern rotary architectures like ModernBERT. Training-free reuse causes big quality drops on ModernBERT such as falling from 0.639 to 0.601 nDCG@10 on DL19 (Table 19). The authors have to train adapters on MS MARCO queries to recover this performance contradicting the training-free premise on newer models.

Questions for authors

Material to Assessment

Can you report an end-to-end serving speedup that includes backend reads of the KV cache from a realistic storage tier? Given 4.3 TiB per million entries how does the speedup change once the cache does not fit in RAM and must be read per query?

1 comment

Thank you for the careful reading and constructive feedback. In this response, we report throughput with storage reads included, separate the contributions of routing and KV reuse, and clarify the limits of the deep-layer position correction and the scope of the training-free claim.

W1 and Q1. We appreciate this suggestion. Following it, we evaluated throughput with backend reads included. Even in the worst case, with a 0% host cache hit rate and every document state fetched from persistent storage, ReState sustains a 3.496× throughput gain over Full.

Host K/V cache hit rateSteady-state throughput vs. Full
0%3.496×
50%4.368×
90%5.719×
100%6.322×

We will include these results in the revised manuscript.

W2. We agree that routing contributes to the default speedup. However, KV reuse drives most of the gain: with routing disabled, ReState still achieves a 4.041× speedup, compared with 1.808× from routing alone. Routing is an optional component that adds further speedup on top of KV reuse.

W3. We agree that the deep-layer correction is only a heuristic surrogate, and its error can accumulate across layers and move cached K/V away from their target values. Nevertheless, ReState retains 96.0% of Full’s mean nDCG@10 overall. Efficiently correcting deep positional errors without training remains an open problem.

W4. ReState is a training-free method for frozen BERT rerankers with learned absolute position embeddings. ModernBERT is an exploratory extension to rotary position encoding. If ff is the frozen reranker and xx its input embeddings, a position shift adds a known offset Δe\Delta e and changes the output from f(x)f(x) to f(x+Δe)f(x+\Delta e). ModernBERT applies rotations inside each attention layer, which calls for a different correction.

On DL19, Full, training-free transfer, and transfer with the optional trained adapter scored 0.639, 0.601, and 0.610 nDCG@10, respectively. The adapter gave no mean gain across datasets. A training-free correction tailored to rotary attention is a direction we would like to explore.

Reviewer_HzXMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents ReState, a training-free method for accelerating BERT rerankers through cross-query reuse of cached document keys and values. The main idea is to separate access to full-document information from document-state updates: query and score tokens can still attend to every document position, while only selected document tokens are updated online. The remaining positions provide precomputed K/V. To address discrepancies between cached states and online joint encoding, the authors introduce Taylor-based position approximation and Score-anchored restoration, which selects update locations using offline score-token attention. ReState-H additionally uses shallow joint encoding to incorporate query-dependent selection signals. On six datasets, the propsoed ReState achieves good performance.

Critical strengths
  • The problem is relevant. The paper distinguishes positional discrepancies from missing query interactions and addresses them through position correction and selective updates, respectively. Preserving full-document attention while reducing state updates provides a reasonable approach to approximate cache reuse in frozen bidirectional encoders.

  • The ablations are reasonable and demonstrate the benefits. The authors separately examine position correction, update-location selection, restoration ratios, and candidate routing.

Critical weaknesses
  • The baseline comparisons do not establish superiority at matched quality levels. SEE and PRISM are primarily evaluated at fixed thresholds, without quality-latency curves comparable to those provided for ReState. Some baselines also use different models or input limits. The main Full reference uses eager attention, motivating comparisons against an optimized dense execution baseline.

  • A few related work is missing, including DC-BERT, DeFormer, EPIC, Cache-Craft. They should be cited and compared.

[1] DC-BERT: Decoupling Question and Document for Efficient Contextual Encoding,SIGIR 2020 [2] DeFormer: Decomposing Pre-trained Transformers for Faster Question Answering,ACL 2020 [3] EPIC: Efficient Position-Independent Caching for Serving Large Language Models,ICML 2025 [4] Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation,SIGMOD 2025

Questions for authors
  • After accounting for cache construction, persistent-storage reads, and bounded host-cache capacity, how many reuses per document are needed to break even? How do the speedups change with cache hit rate?

  • At matched quality-retention levels or latency budgets, does ReState consistently outperform threshold-tuned SEE and PRISM and an optimized Full baseline? Can the authors provide complete quality-latency curves?

  • Can the authors discuss DC-BERT, DeFormer, EPIC, and Cache-Craft, and add static selection baselines, such as document-initial, boundary, and uniformly spaced positions, under matched update budgets to establish the distinctive value of Score-anchored restoration?

1 comment

Thank you for the thoughtful review and helpful suggestions. In this response, we quantify the break-even cost, compare ReState with SEE and PRISM at matched quality, and evaluate static selection baselines and related methods.

Q1. Our break-even analysis on all six datasets shows that ReState recovers the cost of cache construction after only a few reuses, which is readily met since popular documents recur across queries. Specifically, ReState breaks even after 2.7 reuses per document when K/V entries are cached in host memory, and after 5.2 reuses when every entry is read from persistent storage. After break-even, every additional reuse yields a 3.496× to 6.322× throughput gain over Full, depending on the host cache hit rate.

The speedup changes with the host cache hit rate as follows.

Host K/V cache hit rateSteady-state throughput vs. Full
0%3.496×
50%4.368×
90%5.719×
100%6.322×

We will include these results in the revised manuscript.

W1 and Q2. Following your suggestion, we swept the SEE and PRISM thresholds using the same frozen checkpoint and input length limit as ReState. ReState had the lowest latency at the matched quality level. At a fixed latency budget, it also achieved the highest nDCG@10 among the measured settings.

Methodms/query at nDCG@10 ≈0.467Best nDCG@10 within 47.12 ms/query
ReState45.680.4674
SEE166.370.3168
PRISM219.71Over budget (minimum 101.47 ms/query)

We will include the full quality–latency curves in the revision. Against tuned dense Full-SDPA, ReState achieved a 6.50× speedup with default routing and a 3.57× speedup without routing. Dense Full retained the highest mean nDCG@10.

ReState (20% restoration)ms/querynDCG@10Speedup vs. tuned dense SDPA (87.99 ms/query, nDCG@10 = 0.4875)
Default (with routing)13.540.46786.50×
No routing24.620.47423.57×

W2 and Q3. ReState achieved the highest mean nDCG@10 among the selection rules and frozen adaptations we evaluated. Following your suggestion, we compared the static rules with the same routed candidates and update budget.

Selection at 20% restorationMean nDCG@10Paired advantage of ReState
Score-anchored restoration0.4678—
Document-initial (EPIC rule)0.4515+0.0164
Both boundaries0.4470+0.0208
Uniform spacing0.4346+0.0333
Cache-Craft, offline prefix attention0.4541+0.0137

For DeFormer and DC-BERT, we tested how well separate query and document encoding transfers to a frozen checkpoint. The best DeFormer adaptation scored 0.3051 mean nDCG@10 with three lower layers run separately. The best DC-BERT adaptation scored 0.2063 with one interaction layer after separate encoding. Both original methods train their decoupled architectures. We will cite and discuss all four works in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.