acceptodds
Under review as a conference paper at ICLR 2027

TraceKV: Signed Error Feedback for KV-Cache Quantization

Abstract

Low-bit key-value (KV) cache quantization reduces the storage requirements of large language models, but quantization errors can alter their output distributions and generation trajectories. Because errors across tokens can cancel or reinforce one another, reducing individual reconstruction errors alone does not directly control their combined effect on generation. We propose TraceKV, a method that uses self-generated traces to guide cache reconstruction through signed error feedback while preserving the base quantizer's encoding format, bit widths, and metadata footprint. TraceKV generates a short continuation with the bfloat16 (BF16) model, then replays it to compute gradients of multi-step Kullback-Leibler (KL) divergence with respect to cached values. Within each layer and attention head, it accumulates signed projections of quantization errors onto these gradients and selects between independent quantization and residual-feedback reconstruction for each token, encouraging positive and negative contributions to offset. Trace replay then selects among the completed candidate caches. Across four quantization representations, TraceKV reduces cumulative trajectory distortion. On PatternKV and OSCAR, gains persist for 64 tokens beyond the H64 selection window; paired ablations support retaining error signs. In two evaluations with frozen data and protocols, generation restarts from the compressed prompt. With KVarN as the base quantizer, TraceKV increases the mean length of the generated prefix that exactly matches the BF16 continuation by 14.4 and 22.8 tokens over independent KVarN, respectively, with prefix length capped at 1024 tokens.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV-cache quantization, large language models, error feedback, generation fidelity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_jx5EOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

TRACEKV is a test-time controller for reconstructing quantized KV-cache values while preserving the base quantizer's code alphabet, bit widths, group shapes, metadata count, and persistent storage layout. After prefill, it generates a short greedy BF16 continuation and replays it from an independently quantized cache to obtain value gradients of one-step and cumulative KL divergence. For each token, it chooses between independent quantization and quantization with residual feedback, using a signed gradient–error ledger and a gradient-based processing order. Completed candidate caches are evaluated and selected by replaying the same trace.

The paper evaluates the controller with affine quantization, KVarN, PatternKV, and OSCAR's rotation/clipping codec, and includes composition experiments with a port of SQuat's key quantizer. It reports reductions in teacher-forced cumulative distortion and improvements in free-running prefix retention on two frozen sources. Task accuracy improves on S1, but the improvement on S2 does not meet its prespecified accuracy gate. In the evaluated KVarN decode extension, TRACEKV reconstructs the prompt cache; newly completed 128-token decode blocks are quantized independently.

Critical strengths
  1. A well-defined research question with a meaningful methodological contribution. The paper investigates whether KV-cache reconstruction can improve generation fidelity without changing the underlying quantization format, bit allocation, or retained token count. This isolates a meaningful degree of freedom complementary to existing quantization methods. The proposed signed error-feedback mechanism uses trajectory-derived gradients to guide reconstruction while preserving the base quantizer's persistent storage format and budget.

  2. Careful mechanism validation and transparent experimental reporting. The signed-versus-magnitude ablations, fresh-source replication, and processing-order comparisons provide useful evidence for the proposed mechanism. Experiments across multiple quantization representations, together with evaluations beyond the selection horizon and SQuat composition results, further support its applicability. The paper also reports per-cell results, confidence intervals, and unsuccessful accuracy confirmations rather than presenting only favorable aggregate results.

Critical weaknesses
  1. Unquantified construction overhead and unclear practical efficiency. TraceKV requires BF16 continuation generation, gradient computation, candidate construction, and repeated replay before committing the compressed cache. However, the paper does not report the corresponding construction latency or peak GPU memory. Preserving the persistent storage budget does not imply low construction overhead. Without measurements of time to first token, peak memory, and total generation latency, it is difficult to assess whether the fidelity improvements justify the additional computation compared with independent quantization.

  2. Limited evidence for robust long-horizon and downstream task improvements. Although the paper evaluates beyond the selection horizon, the reported cumulative KL ratios do not isolate improvements in the subsequent tokens. For example, D128 includes the H64 selection window, so a lower cumulative distortion does not necessarily indicate continued improvement over tokens 65–128. Moreover, the free-running generation improvements remain modest in absolute terms, with mean R1024 values of 46.6 and 60.3 tokens, and the S2 task-accuracy improvement is not statistically significant. Most representation-level experiments also involve only a few prompt–model pairs. These results leave the robustness and practical significance of the trajectory-fidelity gains insufficiently established.

Questions for authors

Q1. Construction overhead and practical efficiency. Could the authors report the construction latency and peak GPU memory of BF16 trace generation, gradient computation, candidate construction, and replay selection? How do time to first token and total generation latency compare with independent quantization across different prompt and generation lengths? These measurements would help establish whether the fidelity improvements justify the additional computation.

Q2. Out-of-window effectiveness. Although the paper evaluates beyond the selection horizon, cumulative KL ratios do not isolate improvements on subsequent tokens. Could the authors report incremental KL over non-overlapping windows, such as D64 − D32 and D128 − D64? How does the benefit evolve during longer free-running generation, especially when newly generated KV blocks are quantized independently?

Q3. Robustness and downstream task performance. The S2 accuracy improvement is not statistically significant, and the results vary across models. Could the authors explain why improved BF16 prefix retention does not consistently translate into better task accuracy? Could they also evaluate more distinct prompts and report uncertainty estimates to establish the robustness of the observed gains?

Q4. Methodological choices and comparison with existing methods. The processing-order ablations do not consistently favor the default gradient-based path over temporal ordering. Could the authors clarify its advantages and provide sensitivity analyses for the feedback gain, block size, and selection threshold? Additionally, could they compare TraceKV with a suitable output-aware or sensitivity-aware method, such as OptR, at a comparable effective storage budget, with construction costs reported separately?

2 comments
AuthorsOpenReview ↗

Response to Reviewer jx5E (1/2): Q1–Q2

Thank you for your careful review, because your four questions are clear, direct, and address the key issues in our work. We also appreciate how these questions have helped us think more deeply about our method and better understand its behavior.

Q1. Construction overhead and practical efficiency

We measured the complete construction cost, including trace generation, gradient computation, candidate reconstruction, and selection. The results for 1,024-token inputs are:

ModelMethodTTFT (s)Total time, 512 output tokens (s)Peak memory (GiB)
Qwen3-4BIndependent KVarN0.389.068.28
Qwen3-4BTraceKV6.1014.779.66
DeepSeek-8BIndependent KVarN0.4010.1415.63
DeepSeek-8BTraceKV5.6615.3916.86

Measurements use an RTX 6000D, batch size 1, and BF16 eager QDQ. TTFT includes the entire controller, and peak memory includes model weights. The additional peak memory is relatively modest in this setting: 1.38 GiB for Qwen and 1.23 GiB for DeepSeek, while persistent KV storage remains unchanged.

The additional latency comes from computing input-specific sensitivities and evaluating candidate caches. This computation occurs only once per input. Subsequent decoding does not repeat tracing, backpropagation, or candidate selection; newly completed 128-token KV blocks are quantized independently.

Post-first-token decoding time therefore differs from independent quantization by approximately 0.2% or less. Across 1,024- and 2,048-token inputs, the total-time ratio decreases from 2.96–3.61× for 128 output tokens to 1.52–1.71× for 512 tokens. At 2,048 input tokens, TraceKV’s TTFT is 7.51 s for Qwen and 7.59 s for DeepSeek. These measurements identify a one-time startup cost whose relative contribution decreases with longer generation.

As a practical optimization, the 32 tokens generated for tracing can be streamed to the user as they are produced, reducing user-visible TTFT; overlapping trace generation with controller construction can also partially reduce the waiting time before token 33, although this remaining pause still requires further optimization.

Q2. Effectiveness beyond the selection window

To isolate the benefit beyond the construction window, we use only steps 1–32 for gradient computation, cache reconstruction, and candidate selection. We then separately evaluate incremental KL over steps 33–64 and 65–128, corresponding to D64−D32D_{64}-D_{32} and D128−D64D_{128}-D_{64}.

ModelKL ratio, steps 33–64KL ratio, steps 65–128
Qwen3-4B0.6801.048
DeepSeek-8B0.8580.998

Diagnostic setup: native chat templates, 24 mathematical prompts per model, and a shared greedy BF16 reference history. Values are geometric-mean ratios relative to independent KVarN; lower is better.

In this diagnostic, the benefit extends into the first subsequent window, reducing KL by 32.0% for Qwen and 14.2% for DeepSeek. Since this window excludes the construction steps, the improvement cannot be inherited from lower distortion within steps 1–32.

The benefit attenuates by steps 65–128. This is consistent with the finite-horizon design: the short trace captures local sensitivities, whose relevance can change as the generated context evolves. Nevertheless, the separate full MATH-500 evaluation below records accuracy gains of 2.2 and 1.8 percentage points under the original S2 settings, providing downstream benefits alongside the local fidelity improvements.

AuthorsOpenReview ↗

Response to Reviewer jx5E (2/2): Q3–Q4

Q3. Robustness and downstream task performance

Prefix retention and answer correctness are related but not equivalent. Different wording or an alternative valid solution can break exact prefix agreement while preserving correctness. Conversely, closer agreement with an incorrect BF16 solution does not guarantee a correct answer.

To assess the accuracy gains more comprehensively, we expanded the evaluation from 100 questions to the complete MATH-500 dataset, preserving the original S2 experimental settings and scoring procedure.

ModelBF16Independent KVarNTraceKVImprovement over independent
Qwen3-4B67.8%65.0%67.2%+2.2 percentage points
DeepSeek-8B76.4%72.2%74.0%+1.8 percentage points

TraceKV improves observed accuracy in both models on this evaluation, producing 11 additional correct answers for Qwen and 9 for DeepSeek relative to independent quantization.

We also assessed fidelity across 56 distinct prompts covering mathematics, code, instruction following, and continuation:

ModelIndependent KVarNTraceKVIncrease
Qwen3-4B15.9626.82+10.86
DeepSeek-8B15.2524.88+9.63

Values are mean consecutive BF16-matching prediction positions in a diagnostic extending up to 256 steps, reported separately from the submitted R1024 metric.

These complementary evaluations show improved trajectory preservation across task types and higher observed answer accuracy on the complete mathematical benchmark.

Q4. Processing order, sensitivity, and comparison with OptR

Both gradient-based and temporal ordering are heuristics. Gradient ordering connects tokens with similar local sensitivities, while temporal neighbors can already have correlated sensitivities. Our method therefore does not require gradient ordering to be optimal on every input.

The core contribution is to exploit an additional degree of freedom: how cached values are reconstructed within a fixed quantization representation. Signed functional-error feedback accounts for cancellation and reinforcement across tokens, while trace-based selection chooses among completed candidates. Because the code alphabet, bit widths, and metadata layout remain unchanged, this approach is compatible with existing quantizers and complementary to their representation design.

We evaluated the main hyperparameters on 32 prompts per model:

ParameterTested valuesMain observation
Feedback gain0, 0.25, 0.5, 0.75, 1.0All tested nonzero gains improve construction-window KL; ratios are 0.568–0.672 for Qwen and 0.541–0.664 for DeepSeek.
Path block size16, 32, 64, 128Improvements persist across the tested sizes; ratios are 0.577–0.606 for Qwen and 0.583–0.621 for DeepSeek.
Selection tolerance1.00, 1.005, 1.01, 1.02, 1.05No selections change for DeepSeek, and at most one changes for Qwen.

These results support stability across multiple parameter choices. Moderate feedback performs best in this sweep; larger gains can introduce stronger perturbations and worsen subsequent-window distortion.

Following your suggestion, we also compared against OptR using its public calibration optimizer. The comparison uses matched K2/V2 settings and the same effective KV storage budget, including retained full-precision tokens and metadata. On 32 evaluation prompts per model, adding TraceKV with its original gain of 0.5 gives:

ModelTraceKV + OptR / OptR construction-window KLAdditional KL reductionConstruction time: OptR → TraceKV + OptR
Qwen3-4B0.86713.3%0.098 → 7.958 s
DeepSeek-8B0.82817.2%0.145 → 7.810 s

Construction times include prefill. OptR calibration is reusable offline work; TraceKV construction is performed per input.

We then selected gain=0.25 using validation prompts and evaluated 32 additional prompt instances per model, retaining gain=0.5 as a matched control:

ModelOptRTraceKV + OptR, gain=0.5TraceKV + OptR, calibrated gain=0.25Calibrated improvement over OptR
Qwen3-4B40.7250.1650.47+9.75
DeepSeek-8B54.1962.0070.13+15.94

Values are mean consecutive BF16-matching prediction positions, capped at 128. Gain is fixed before evaluation; there is no per-prompt gain search.

The additional gains are strongest for local KL and prefix retention, while later-window KL remains close to the OptR baseline. These results support complementarity: OptR improves the representation using calibration data, and TraceKV further improves reconstruction using the current input’s trajectory without increasing its persistent KV storage.

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

TraceKV uses self-generated continuations and signed error feedback to improve KV-cache reconstruction at fixed persistent storage.

Critical strengths
  • Explores a useful reconstruction strategy without increasing cache size.
  • Signed-versus-magnitude ablations directly support the central mechanism.
  • Free-running experiments show better preservation of BF16 trajectories.
Critical weaknesses
  • Task accuracy improvements are inconsistent.
  • Per-input tracing, gradient computation, and replay costs are insufficiently measured.
  • Some cross-quantizer experiments are small.
  • SQuat and OptR already consider functional quantization effects; novelty rests on the specific controller.
Questions for authors

What are the end-to-end latency and peak-memory costs of trace generation, gradient computation, and candidate selection?

1 comment
AuthorsOpenReview ↗

Response to Reviewer UFFm

Thank you for recognizing the value of reconstruction at a fixed cache size and the evidence from the signed-error ablations. Your concerns about construction cost, downstream accuracy, and existing methods help us clarify the contribution and its practical scope.

Construction overhead and practical efficiency

We measured the full construction cost, covering trace generation, gradients, reconstruction, and selection. For 1,024-token inputs:

ModelMethodTTFT (s)Total time, 512 output tokens (s)Peak memory (GiB)
Qwen3-4BIndependent KVarN0.389.068.28
Qwen3-4BTraceKV6.1014.779.66
DeepSeek-8BIndependent KVarN0.4010.1415.63
DeepSeek-8BTraceKV5.6615.3916.86

RTX 6000D, batch size 1, BF16 eager QDQ. TTFT includes the entire controller; peak allocated memory includes model weights.

The additional peak memory is relatively modest in this setting: 1.38 GiB for Qwen and 1.23 GiB for DeepSeek, while persistent KV storage remains unchanged.

The construction breakdown for the same input length is:

StageQwen time / peak (s / GiB)DeepSeek time / peak (s / GiB)
BF16 trace generation0.50 / 7.840.57 / 15.25
Gradient computation2.05 / 8.631.68 / 15.97
Cache reconstruction, including path1.83 / 9.661.78 / 16.86
Replay selection1.49 / 8.551.37 / 15.88

Reconstruction includes the independent cache, path, and feedback candidates; times sum stage medians and peaks take their maximum. End-to-end timings include prefill and cleanup.

Construction occurs only once per input. Subsequent decoding does not repeat tracing, backpropagation, or candidate selection; completed 128-token KV blocks are quantized independently. Post-first-token decoding time differs from independent quantization by approximately 0.2% or less.

Across 1,024- and 2,048-token inputs, the paired total-time ratio decreases from 2.96–3.61× for 128 output tokens to 1.52–1.71× for 512 tokens. Thus, the additional work is concentrated at startup, with a smaller relative cost for longer generation.

As a practical optimization, the 32 trace tokens can be streamed as they are generated to reduce user-visible TTFT. Overlapping trace generation with controller construction can also partially reduce the wait before token 33.

Downstream accuracy and cross-task fidelity

Prefix retention and correctness are related but not equivalent: an alternative valid solution can break exact prefix agreement, while preserving an incorrect BF16 trajectory does not ensure correctness. To assess downstream benefits more comprehensively, we expanded the S2 evaluation on MATH-500 while preserving the original settings and scoring procedure:

ModelBF16Independent KVarNTraceKVGain over independent
Qwen3-4B67.8%65.0%67.2%+2.2 pp
DeepSeek-8B76.4%72.2%74.0%+1.8 pp

Accuracy on the complete MATH-500 dataset.

TraceKV improves observed accuracy in both models. We also assessed fidelity across mathematics, code, instruction following, and continuation:

ModelIndependent KVarNTraceKV
Qwen3-4B15.9626.82
DeepSeek-8B15.2524.88

Mean consecutive BF16-matching prediction positions over 56 distinct prompts per model, evaluated up to 256 steps and reported separately from the submitted R1024 metric.

Relationship to SQuat and OptR

Our contribution is to explore an additional degree of freedom: how cached values are reconstructed within a fixed quantization representation. Signed functional-error feedback accounts for cancellation and reinforcement across tokens, while trace-based selection chooses among completed candidates. The code alphabet, bit widths, and metadata layout remain unchanged, making the controller compatible with existing quantizers, including SQuat and OptR.

We added an OptR comparison using its public calibration optimizer, with matched K2/V2 settings and the same effective KV storage budget, including retained full-precision tokens and metadata:

ModelTraceKV + OptR / OptR construction-window KLAdditional KL reductionConstruction time: OptR → TraceKV + OptR
Qwen3-4B0.86713.3%0.098 → 7.958 s
DeepSeek-8B0.82817.2%0.145 → 7.810 s

Original gain=0.5; 32 evaluation prompts per model. Construction times include prefill. OptR calibration is reusable offline work; TraceKV construction is performed per input.

These results support complementarity: OptR calibrates the representation; TraceKV improves reconstruction using the current input's trajectory, without increasing persistent KV storage. The additional KL gains are strongest within the construction window.

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

This paper presents TraceKV, a method that uses self-generated traces and signed error feedback to improve KV-cache reconstruction under quantization. While preserving the base quantization format and storage budget, it derives gradient information related to output distributions from a short model-generated continuation, guides cache reconstruction, and selects candidate reconstructions through trace replay. The central idea is to coordinate quantization-error contributions across tokens to mitigate their impact on generation. Experiments across multiple quantization representations show reduced cumulative trajectory distortion and improved consistency with the BF16 reference during free-running generation. Ablation studies further support the role of signed error feedback.

Critical strengths
  1. A valuable reconstruction perspective under a fixed storage budget. The paper identifies a useful opportunity to improve KV-cache quantization through reconstruction choices. Keeping the underlying format unchanged makes this contribution complementary to advances in quantized representations and precision allocation.

  2. Balanced and transparent experimental reporting. The paper presents detailed results and uncertainty estimates alongside outcomes that did not confirm the expected accuracy gains. This helps readers assess the evidence and understand the scope of the reported improvements.

Critical weaknesses
  1. Insufficient evidence of practical efficiency. TraceKV introduces several computation stages before the compressed cache is ready for use, yet their runtime and temporary memory requirements are not quantified. The unchanged persistent cache size therefore provides only a partial picture of resource usage, leaving it unclear under which workloads the fidelity gains justify the additional preparation cost.
Questions for authors
  1. Could the authors quantify the cost of preparing and using the reconstructed cache? A breakdown of time and peak GPU memory for trace generation, gradient computation, candidate construction, and selection would be helpful. Please also compare time to first token and total generation time with independent quantization across different prompt and output lengths, to clarify when the added preparation cost becomes a substantial part of overall inference.
1 comment
AuthorsOpenReview ↗

Response to Reviewer fn6B

Thank you for recognizing the reconstruction perspective at a fixed storage budget and the value of reporting both confirmed and unconfirmed gains. Your request for a complete cost breakdown is helpful because persistent cache size alone does not capture the resources needed to construct it.

Construction overhead and practical efficiency

We measured the complete construction cost, including trace generation, gradient computation, candidate reconstruction, and selection. The results for 1,024-token inputs are:

ModelMethodTTFT (s)Total time, 512 output tokens (s)Peak memory (GiB)
Qwen3-4BIndependent KVarN0.389.068.28
Qwen3-4BTraceKV6.1014.779.66
DeepSeek-8BIndependent KVarN0.4010.1415.63
DeepSeek-8BTraceKV5.6615.3916.86

Measurements use an RTX 6000D, batch size 1, and BF16 eager QDQ. TTFT includes the entire controller, and peak memory includes model weights. The additional peak memory is relatively modest in this setting: 1.38 GiB for Qwen and 1.23 GiB for DeepSeek, while persistent KV storage remains unchanged.

The construction breakdown for the same input length is:

StageQwen time / peak (s / GiB)DeepSeek time / peak (s / GiB)
BF16 trace generation0.50 / 7.840.57 / 15.25
Gradient computation2.05 / 8.631.68 / 15.97
Cache reconstruction, including path1.83 / 9.661.78 / 16.86
Replay selection1.49 / 8.551.37 / 15.88

Reconstruction includes the independent cache, path, and feedback candidates; times sum stage medians and peaks take their maximum. End-to-end timings include prefill and cleanup.

The additional latency comes from computing input-specific sensitivities and evaluating candidate caches. This computation occurs only once per input. Subsequent decoding does not repeat tracing, backpropagation, or candidate selection; newly completed 128-token KV blocks are quantized independently.

Post-first-token decoding time therefore differs from independent quantization by approximately 0.2% or less. Across 1,024- and 2,048-token inputs, the total-time ratio decreases from 2.96–3.61× for 128 output tokens to 1.52–1.71× for 512 tokens. At 2,048 input tokens, TraceKV’s TTFT is 7.51 s for Qwen and 7.59 s for DeepSeek. These measurements identify a one-time startup cost whose relative contribution decreases with longer generation.

As a practical optimization, the 32 tokens generated for tracing can be streamed to the user as they are produced, reducing user-visible TTFT; overlapping trace generation with controller construction can also partially reduce the waiting time before token 33.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.