acceptodds
Under review as a conference paper at ICLR 2027

Rose-TTA: Reliable Online Structural Enhancement for Test-Time Adaptation

Abstract

Large-scale vision-language models like CLIP exhibit remarkable zero-shot generalization but suffer significant performance degradation under real-world distribution shifts. Although recent cache-based test-time adaptation (TTA) methods mitigate the issues, they are limited by: (i) unreliability in cache construction, as entropy-based sample selection is insufficient under distribution shifts; and (ii) incomplete cache information at inference, with both imbalanced category information caused by sequential online updates and insufficient sample-specific information for next online instance. To address these limitations, we propose ROSE-TTA, a unified framework that enhances both cache construction and utilization for more reliable and stable adaptation. For construction, we introduce a noise-aware uncertainty measure that combines entropy with perturbation-based prediction stability to robustly select cache entries. To complete the cache information for utilization, we develop a graph-based structural completion strategy, which effectively mitigates class imbalance and completes global information by transferring information between text embeddings and cached features. Additionally, we introduce a sample-specific refinement mechanism to dynamically update cache features and incorporate local information of each online test sample. Experiments on 15 datasets demonstrate the effectiveness of our method.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
vision-language models, CLIP, test-time adaptation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YziEOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies reliable online cache-based test-time adaptation for CLIP under distribution shift, targeting three coupled issues: entropy-only cache construction admits confident but misclassified samples, online caches become class-imbalanced, and static cached features lack sample-specific local information. ROSE-TTA introduces (i) an uncertainty-aware “doubly robust” cache update that combines entropy with noise-perturbed prediction stability, (ii) a graph-based structural completion module that uses text-embedding class semantics and cached visual evidence to alleviate class imbalance, and (iii) a sample-specific cache refinement mechanism that updates cached features via a forward pseudo-gradient without backpropagation. Experiments on 15 datasets are provided.

Critical strengths

The problem under investigation is both interesting and practically important. The proposed graph-based structural completion together with the sample-specific refinement mechanism is well-designed and closely aligned with the problem characteristics.

Critical weaknesses
  1. The motivation is insufficient. Cache imbalance and exploitation are identified as common problems in the TTA field, ranging from conventional model-updated methods to model-fixed VLM-based TTA methods. Many existing works, such as RoTTA, DLAE, and MCP, aim to tackle these problems. However, the limitations of and relationships to these prior works are missing, which results in insufficient motivation for this work.
  2. The experimental comparisons are unfair. Several existing SOTA cache-based and backpropagation-free baselines are omitted. In addition, the efficiency comparisons focused on gradient-based prompt optimization methods are also unfair. These unfair comparisons falsely exaggerate the contributions of this work.
Questions for authors
  1. The limitations of and relationships to many existing cache-based and backpropagation-free methods are missing (e.g., RoTTA, DLAE, MCP), which leads to insufficient motivation of the work.
  2. The prediction stability of a sample xx is evaluated under Gaussian noise. What about using alternative noise generators? The rationale for this design choice is unclear. Neither theoretical analysis nor supporting empirical experiments are provided.
  3. The technical section is generally readable. However, the definition of G^\hat{G} in Eq. (6) is not straightforward, which hurts the readability of this section. More detailed specifications should be provided to explain its function.
  4. In Eq. (8), I understand that fxf_x is used to update all cached features across all categories without accounting for feature quality. The rationale behind this operation is unclear. In particular, Section 3.2 aims to construct reliable, consistently stable caches. These two objectives appear contradictory.
  5. Unfair experimental comparisons against existing methods falsely exaggerate the performance of the proposed method.
  • Multiple SOTA cache-based and backpropagation-free methods are missing, including MCP, DLAE, ProtoDCS, DOTA, ADAPT, and even Zhang’s ICML’26 work that is already cited in the related work section.
  • Efficiency comparisons should focus on cache-based backpropagation-free methods (e.g., MCP, DLAE, ProtoDCS) to demonstrate efficiency, rather than prompt-based methods.
  1. As mentioned in the Introduction, the most interesting aspect of the proposed method lies in the early adaptation stage. How does graph-based structural completion improve performance when many class caches are empty or populated with unreliable features? This important investigation is absent from the current manuscript.
  2. Other minor concerns:
  • How should Figures 1(a) and 1(b) be interpreted?
  • Table 3 lacks ablation baselines. A baseline without the proposed components should be included to verify the effectiveness of each module.
15 comments

We sincerely appreciate your time and insightful comments on our manuscript. Thank you for recognizing the problem and the design of our graph and sample-specific modules. Below, we address your concerns point by point and describe the corresponding revisions.

W1: The motivation is insufficient … RoTTA, DLAE, and MCP … the limitations of and relationships to these prior works are missing … insufficient motivation for this work.

Q1: The limitations of and relationships to … cache-based and backpropagation-free methods are missing … insufficient motivation of the work.

Response: Thank you for the comment. We have added a detailed comparison with RoTTA, MCP, and DLAE to explain their limitations and relationships to ROSE-TTA:

  • RoTTA, which also addresses cache class imbalance, balances cached samples to limit frequent-class dominance, but it does not ensure sufficient cache information for classes with few or no cached samples. ROSE-TTA completes cache information by incorporating text information through graph-based structural completion.

  • MCP, which also improves cache quality, uses entropy and prototype proximity for sample selection, but does not reuse these selection scores as reliability weights in positive-cache retrieval. ROSE-TTA uses perturbation stability and entropy-based confidence in both cache construction and cache utilization, refining the cache information used for prediction.

  • DLAE improves cache coverage through logit recalibration and exploratory sample selection. However, it still leaves information gaps in the cache unresolved when suitable samples are unavailable. ROSE-TTA completes cache information through graph-based structural completion, using text relations to share existing visual evidence across classes.

We further clarify the motivation and joint design of ROSE-TTA:

  • Motivation. In streaming settings, reliable cache information can still be incomplete, while completing missing information must account for the reliability of the available information. This motivates us to jointly address cache reliability and completeness end to end, from cache construction through utilization to prediction.

  • Technical novelty. We introduce a unified framework that jointly completes and refines cache information. Uncertainty-aware cache construction favors reliable entries and passes their reliability estimates to graph-based structural completion. For reliability, these estimates give greater weight to reliable cache information. For completeness, text relations supply the global category information missing from sparse caches. Finally, the unified categorical graph G^\hat G integrates both sources to provide more reliable and complete cache information for prediction. Sample-specific refinement further injects online information from the current query to enrich cache information.

W2: The experimental comparisons are unfair … baselines are omitted … falsely exaggerate the contributions of this work.

Q5: Unfair experimental comparisons … falsely exaggerate the performance of the proposed method.

  • Multiple SOTA … methods are missing, including MCP, DLAE, ProtoDCS, DOTA, ADAPT … Zhang’s ICML’26 work … cited in the related work section.
  • Efficiency comparisons should focus on cache-based backpropagation-free methods … rather than prompt-based methods.

Response: Thank you for these suggestions. We have added accuracy comparisons under shared cache and text settings and efficiency comparisons with additional cache-based methods.

  • Accuracy comparisons. For a fair comparison,we use a total capacity of 5 cache entries per class. All methods share the same text descriptions. ROSE-TTA ranks first on both metrics across both backbones. We have added these results to Appendix D.9.

    MethodViT16 IN+OODViT16 CDRN50 IN+OODRN50 CD
    MCP66.1370.0850.2663.04
    DLAE66.1370.1450.3463.19
    ProtoDCS65.3269.0348.9761.07
    DOTA65.8268.9749.5462.01
    ADAPT66.0270.0450.1962.92
    A²Memory66.0970.1350.3663.18
    RoTTA61.9662.0145.6358.46
    ROSE-TTA66.2570.2650.3663.31
  • Efficiency comparison. ROSE-TTA has the shortest runtime and highest accuracy among the compared adaptation methods. We have added these results to Appendix C.4.

    MethodTime (min) ↓Acc. (%) ↑Gain (pp) ↑
    CLIP9.3668.34—
    TDA50.0069.51+1.17
    MCP69.2170.12+1.78
    DLAE237.3270.76+2.42
    ProtoDCS290.2370.42+2.08
    ROSE-TTA48.5470.78+2.44

Q2: The prediction stability of a sample xx is evaluated under Gaussian noise. What about using alternative noise generators? The rationale for this design choice is unclear. Neither theoretical analysis nor supporting empirical experiments are provided.

Response: Thank you for your thoughtful comments. Other noise generators can also be used to evaluate prediction stability. We have added an experiment using different noise generators. We have added these results and the discussion to Appendix D.11.

MethodNoise generatorIN Acc. (%)
TDA—69.51
ROSE-TTAGaussian70.78
ROSE-TTAUniform70.72
ROSE-TTALaplace70.81

From the above results, our method maintains strong performance under different types of noise perturbations.

Q3: The technical section is generally readable. However, the definition of G^\hat{G} in Eq. (6) is not straightforward, which hurts the readability of this section. More detailed specifications should be provided to explain its function.

Response: Thank you for pointing out the ambiguity. The unified categorical graph G^\hat G combines visual and text relations between classes. This allows classes with few or no cached samples to use visual information from related class caches for prediction.

  • Visual information from the test stream. Q=MG^cM⊤∈RC×CQ=M\hat G_cM^\top\in\mathbb R^{C\times C}, where QabQ_{ab} sums the reliability-weighted similarities between samples in Ca\mathcal C_a and Cb\mathcal C_b. If Ca\mathcal C_a is empty, row aa and column aa of QQ are zero.

  • Global category information from text. GtG_t contains similarities between the text embeddings of all classes. In GtQGt⊤G_tQG_t^\top, these similarities weight the visual relations in QQ. A class with an empty cache can therefore use visual relations from classes with similar text embeddings and available cached samples.

  • Complementary predictions. G^\hat G provides global category information to guide feature aggregation in both the text and visual spaces, producing complementary predictions PtP_t and PiP_i. Through G^\hat G, PtP_t incorporates test-specific visual information, while PiP_i uses text relations to supplement incomplete class caches.

Q4: In Eq. (8), … fxf_x is used to update all cached features … without accounting for feature quality … Section 3.2 aims to construct reliable, consistently stable caches … These two objectives appear contradictory.

Response: Thank you for raising this concern. Feature quality is considered through entropy and perturbation stability during cache selection. Reliable historical features may still be poorly matched to the current query, so Eq. (8) uses fxf_x to refine them into F^\hat F for the current prediction. We retain FF, not F^\hat F, in the cache, so the two objectives do not conflict.

Q6: … the early adaptation stage … How does graph-based structural completion improve performance when many class caches are empty or populated with unreliable features? This important investigation is absent from the current manuscript.

Response: Thank you for highlighting early adaptation. We first explain how graph-based structural completion handles empty class caches and unreliable features, then evaluate its effect on cache predictions and cumulative accuracy. We have added these results and the discussion to Appendix D.8.

  • For empty class caches, GtG_t provides the similarities between class text embeddings. Through G^\hat G, these similarities allow classes with no cached entries to use visual information from other classes' cached features.

  • For unreliable cached features, G^c\hat G_c assigns smaller reliability weights to entries with higher entropy or greater perturbation sensitivity when constructing G^\hat G.

  • To examine the role of graph-based structural completion in early adaptation, we analyze cache prediction scores and cumulative classification accuracy.

  • We group classes by the number of entries currently stored in their caches. The reported scores are defined as follows:

    • For a test feature fxf_x, ℓc\ell_c is the normalized cache prediction score for class cc. This score excludes PclipP_{\mathrm{clip}}. Graph-based structural completion adds PiP_i and PtP_t, both computed using G^\hat G. Without these terms, ℓcw/o=[Norm(αP^cache)]c\ell_ c^{\mathrm{w/o}}=[{Norm}(\alpha\hat P_ {\mathrm{cache}})]_ c; with them, ℓcw/=[Norm(α(P^cache+Pi+Pt))]c\ell_ c^{\mathrm{w/}}=[{Norm}(\alpha(\hat P_ {\mathrm{cache}}+P_ i+P_ t))]_c.

    • The class cache Cc\mathcal C_c stores entries with pseudo-label cc. Thus, Sk={c:∣Cc∣=k}\mathcal S_k=\lbrace c:|\mathcal C_c|=k\rbrace contains classes whose caches each hold exactly kk entries.

    • We average the class scores to obtain ℓˉk=1∣Sk∣∑c∈Skℓc\bar{\ell}_ k=\frac{1}{|\mathcal S_ k|}\sum_{c\in\mathcal S_ k}\ell_c, separately for each setting. This is the mean score assigned to classes with cache size kk.

  • We have added a comparison of mean cache scores across cache sizes for a test sample at 10% test progress, with and without Pi,PtP_i,P_t.

    DatasetGraph enhancementℓˉ0\bar{\ell}_0ℓˉ1\bar{\ell}_1ℓˉ2\bar{\ell}_2ℓˉ3\bar{\ell}_3ℓˉ4\bar{\ell}_4ℓˉ5\bar{\ell}_5
    ImageNetw/o Pi,PtP_i,P_t0.00000.00060.00070.00080.00090.0011
    ImageNetw/ Pi,PtP_i,P_t0.00070.00080.00090.00090.00100.0010
    Caltech101w/o Pi,PtP_i,P_t0.00000.00810.00900.01030.01180.0221
    Caltech101w/ Pi,PtP_i,P_t0.00640.00930.00950.01010.01090.0142
    • From the above results, classes with fewer entries receive higher mean normalized scores with graph-based structural completion in this illustration.
  • We have also added a comparison of cumulative top-1 accuracy over the first 10% of the same test stream.

    DatasetSettingCumulative Acc. at 10% (%)
    ImageNetw/o Pi,PtP_i,P_t62.68
    ImageNetw/ Pi,PtP_i,P_t69.05
    Caltech101w/o Pi,PtP_i,P_t89.24
    Caltech101w/ Pi,PtP_i,P_t93.12
    • From the above results, graph-based structural completion improves early adaptation accuracy on both datasets.

Q7: Other minor concerns — M1: How should Figures 1(a) and 1(b) be interpreted?

Response: Thank you for pointing this out. We have clarified Figures 1(a) and 1(b) in the revised manuscript.

  • Cache Accuracy (x-axis): formally defined as Accc=1∣Cc∣∑x∈Cc1[y^(x)=y(x)]\mathrm{Acc}_ c=\frac{1}{|\mathcal C_ c|}\sum_{x\in\mathcal C_ c}\mathbf{1}[\hat y(x)=y(x)], measuring the fraction of samples in a nonempty class cache Cc\mathcal C_ c whose pseudo-label y^(x)\hat y(x) matches the ground-truth y(x)y(x).
  • Frequency (y-axis): The normalized distribution of class caches. It shows the relative frequency of class caches falling into each accuracy bin, normalized to [0,1][0,1] by dividing by the maximum count.
  • Both figures show that entropy-based selection can retain incorrect pseudo-labels in the cache, especially during early adaptation.

Q7: Other minor concerns — M2: Table 3 lacks ablation baselines. A baseline without the proposed components should be included to verify the effectiveness of each module.

Response: Thank you for your suggestion. We have added a baseline without the three proposed modules to Table 3. It keeps CLIP frozen and updates the positive cache using entropy alone. The results show that the full method outperforms the baseline and each module contributes to accuracy.

MetricBaselinew/o ddw/o PtP_t, PiP_iw/o F^\hat FROSE-TTA
CD Acc. (%)67.4969.8268.5669.1270.26
IN+OOD Acc. (%)64.9665.6765.3465.7666.25

We would appreciate your consideration of these clarifications and additional results in your final evaluation. Please let us know if you have further questions. Thank you again for your detailed and constructive feedback!

Reviewer_dDJAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ROSE-TTA, a reliable online test-time adaptation framework for vision-language models. The method aims to improve both cache construction and cache utilization. Specifically, the authors introduce a noise-aware uncertainty measure to select reliable samples for cache updates. The authors design a graph-based structural completion module to improve global information in the cache, and a sample-specific refinement module to adapt cached features to each incoming test sample. Experiments on 15 benchmark datasets demonstrate competitive performance compared with existing test-time adaptation methods.

Critical strengths
  1. The paper addresses a meaningful problem by considering the reliability of cache construction and the incomplete information in online test-time adaptation.
  2. The proposed framework is reasonably designed, combining uncertainty-aware cache selection, graph-based structural completion, and sample-specific refinement.
Critical weaknesses
  1. The technical novelty of the proposed method is relatively limited. The three main components rely on existing techniques: uncertainty estimation, graph-based information propagation, and feature refinement. The proposed framework mainly combines these techniques, without introducing a substantially new learning mechanism. The authors should better explain the differences from existing cache-based TTA methods.
  2. The experimental comparisons may not be fully fair. Table 1 shows that ROSE-TTA achieves the best overall performance when using GPT-4o-generated text descriptions. However, with hand-crafted prompts, its average accuracy is lower than PTA on the cross-dataset benchmark. It is unclear how much of the improvement comes from the proposed method rather than the additional text descriptions. The authors should compare different methods under the same prompt settings.
  3. The ablation studies are not sufficient to fully validate the proposed graph-based structural completion mechanism. Table 3 only reports the results of removing the two graph-enhanced prediction terms together. More independent ablation experiments are needed to show their individual contributions. In addition, experiments under different levels of cache class imbalance would help demonstrate the effectiveness of the proposed mechanism.
  4. The computational overhead needs further discussion. Although the method does not require backpropagation, the noise-aware estimation and graph construction still introduce additional computation and memory costs. Table 4 shows that ROSE-TTA requires more memory than TDA. A more detailed analysis of the performance-efficiency trade-off would strengthen the paper.
Questions for authors

Please see the weaknesses.

6 comments

We sincerely appreciate your careful review and constructive suggestions. Thank you for recognizing the problem and framework design. We have carefully addressed each of the concerns as follows:

W1: The technical novelty of the proposed method is relatively limited. The three main components rely on existing techniques: uncertainty estimation, graph-based information propagation, and feature refinement. The proposed framework mainly combines these techniques, without introducing a substantially new learning mechanism. The authors should better explain the differences from existing cache-based TTA methods.

Response: Thank you for the comment. Following your suggestion, we have added a detailed comparison with existing cache-based TTA methods to clarify how ROSE-TTA differs:

  • RoTTA, which also addresses cache class imbalance, balances cached samples to limit frequent-class dominance, but it does not ensure sufficient cache information for classes with few or no cached samples. ROSE-TTA completes cache information by incorporating text information through graph-based structural completion.

  • MCP, which also improves cache quality, uses entropy and prototype proximity for sample selection, but does not reuse these selection scores as reliability weights in positive-cache retrieval. ROSE-TTA uses perturbation stability and entropy-based confidence in both cache construction and cache utilization, refining the cache information used for prediction.

  • DLAE improves cache coverage through logit recalibration and exploratory sample selection. However, it still leaves information gaps in the cache unresolved when suitable samples are unavailable. ROSE-TTA completes cache information through graph-based structural completion, using text relations to share existing visual evidence across classes.

We further clarify the key insight and technical novelty of our unified framework:

  • Key insight. In streaming settings, reliable cache information can still be incomplete, while completing missing information must account for the reliability of the available information. This motivates us to jointly address cache reliability and completeness end to end, from cache construction through utilization to prediction.

  • Technical novelty. We introduce a unified framework that jointly completes and refines cache information. Uncertainty-aware cache construction favors reliable entries and passes their reliability estimates to graph-based structural completion. For reliability, these estimates give greater weight to reliable cache information. For completeness, text relations supply the global category information missing from sparse caches. Finally, the unified categorical graph G^\hat G integrates both sources to provide more reliable and complete cache information for prediction. Sample-specific refinement further injects online information from the current query to enrich cache information.

W2: The experimental comparisons may not be fully fair. Table 1 shows that ROSE-TTA achieves the best overall performance when using GPT-4o-generated text descriptions. However, with hand-crafted prompts, its average accuracy is lower than PTA on the cross-dataset benchmark. It is unclear how much of the improvement comes from the proposed method rather than the additional text descriptions. The authors should compare different methods under the same prompt settings.

Response: Thank you for raising this concern. We have added comparisons under two prompt settings using CLIP ViT-B/16. TDA, PTA, and ROSE-TTA share the same prompts within each setting. We have added this experiment to Table 5 of the revised manuscript.

  • Hand-crafted prompts

    MethodIN + OOD Acc.CD Acc.
    TDA65.0167.53
    PTA65.6169.38
    ROSE-TTA66.0469.20
  • GPT-4o-generated descriptions

    MethodIN + OOD Acc.CD Acc.
    TDA65.1267.60
    PTA65.6369.48
    ROSE-TTA66.2570.26

From the above results, ROSE-TTA benefits more from the same rich descriptions than TDA and PTA, highlighting its advantage in using text information to complement incomplete early caches.

W3: The ablation studies are not sufficient to fully validate the proposed graph-based structural completion mechanism. Table 3 only reports the results of removing the two graph-enhanced prediction terms together. More independent ablation experiments are needed to show their individual contributions. In addition, experiments under different levels of cache class imbalance would help demonstrate the effectiveness of the proposed mechanism.

Response: Thank you for your helpful suggestions. We have added independent branch ablations and an experiment with different levels of cache class imbalance.

  • Independent branch ablations. We remove PiP_i, PtP_t, or both from the full method. Both branches improve accuracy on both benchmarks. We have added these ablations to Table 3.

    MetricTDAw/o PiP_iw/o PtP_tw/o PtP_t and PiP_iFull ROSE-TTA
    IN + OOD Acc. (%)65.1265.8466.0365.3466.25
    CD Acc. (%)67.6069.6769.8468.5670.26
  • Cache class imbalance. We keep the cache capacity at 5 entries per class for half of the ImageNet classes and reduce it for the other half. ROSE-TTA loses less accuracy than TDA relative to the balanced setting, showing its effectiveness in handling cache class imbalance. We have added this experiment to Table 6.

    Cache SettingCache DistributionTDA Acc. (%)ROSE-TTA Acc. (%)
    Balanced1,000 classes × 5 entries69.5170.78
    Mild Imbalance500 classes × 5 + 500 classes × 369.1070.68
    Severe Imbalance500 classes × 5 + 500 classes × 168.9270.32
    Missing Classes500 classes × 5 + 500 classes × 068.2970.06

W4: The computational overhead needs further discussion. Although the method does not require backpropagation, the noise-aware estimation and graph construction still introduce additional computation and memory costs. Table 4 shows that ROSE-TTA requires more memory than TDA. A more detailed analysis of the performance-efficiency trade-off would strengthen the paper.

Response: Thank you for the constructive comments. We have optimized ROSE-TTA and added an efficiency comparison. The optimized version reduces memory overhead over TDA from 41.0% to 7.3% and requires 6.5% less runtime than TDA, while maintaining performance. We have added the experimental results to Table 4.

MethodImageNet Acc. (%)Total time (min)GPU memory (MB)
CLIP68.349.36808.96
TDA69.5150.00860.16
ROSE-TTA, original70.7848.541212.98
ROSE-TTA, optimized70.7746.77922.86

To explain the memory savings above, we analyze graph storage in the original implementation, explain the two optimizations, and compare the space complexity of GcG_c, WW, and G^c\hat G_c before and after optimization. We have added these analyses to Appendix C.3.

Analysis of memory overhead

  • We have added a memory analysis of the graphs and weight matrix in the original implementation. On ImageNet, C=1000C=1000 is the number of classes, and a full cache holds N=5000N=5000 entries, with five entries per class. The table lists the FP32 storage of each graph or matrix. The cache-graph GcG_c, weight matrix WW, and reliability-weighted cache graph G^c\hat G_c account for most of this storage.

    Graph / matrixShapeStorage (MB)
    Cache-graph Gc=FF⊤G_c=FF^\topN×NN\times N95.37
    Weight matrix WWN×NN\times N95.37
    Reliability-weighted cache graph G^c=Gc⊙W\hat G_c=G_c\odot WN×NN\times N95.37
    Text-graph GtG_tC×CC\times C3.81
    Gate-graph MMC×NC\times N19.07
    Unified categorical graph G^\hat GC×CC\times C3.81
  • To reduce the memory overhead, we have proposed two implementation changes.

    • Graph storage. We replace storage of the full cache graph with blockwise computation, computing a few rows at a time. We store only the current rows of GcG_c, WW, and G^c\hat G_c, and reuse their memory for the next few rows.

    • FP16 storage. Following TDA, we store the main tensors of our added modules in FP16. Each converted tensor uses half its FP32 storage.

Derivation of blockwise computation

  • To show how we avoid storing the full cache graph, we have added the following derivation using the paper's graph definition.

    • We select up to bb cached features from FF. Let II be their row index set, so ∣I∣≤b|I|\le b. Each cache entry appears in exactly one index set II. The corresponding ∣I∣|I| rows of GcG_c are (Gc)I,:=FI,:F⊤(G_ c)_ {I,:}=F_ {I,:}F^\top. We compute WI,:W_{I,:} directly from the reliability scores, then multiply these rows elementwise by WI,:W_ {I,:}:

      \in\mathbb R^{|I|\times N}.$$
    • We initialize Q∈RC×CQ\in\mathbb R^{C\times C} to zero once. For each II, we sum columns and rows for samples in the same class cache, giving M:,I[(G^c)I,:M⊤]∈RC×CM_{:,I}[(\hat G_c)_{I,:}M^\top]\in\mathbb R^{C\times C}. We add this matrix to QQ and reuse the memory for the current rows of GcG_c, WW, and G^c\hat G_c to process the next II:

      Q=∑IM:,I[(G^c)I,:M⊤]=MG^cM⊤.Q=\sum_I M_{:,I}\big[(\hat G_c)_{I,:}M^\top\big]=M\hat G_cM^\top.

    • Finally, combine QQ with GtG_t to obtain the unified categorical graph:

      G^=softmax⁡row(GtQGt⊤).\hat G=\operatorname{softmax}_{\mathrm{row}}(G_tQG_t^\top).

Theoretical Space Complexity Analysis

  • To explain the main memory savings, we have added a theoretical analysis of GcG_c, WW, and G^c\hat G_c, which dominate the original graph storage.

  • Original implementation:

    • Cache-graph GcG_c: N×NN\times N entries, requiring O(N2)O(N^2) space.
    • Weight matrix WW: N×NN\times N entries, requiring O(N2)O(N^2) space.
    • Reliability-weighted cache graph G^c\hat G_c: N×NN\times N entries, requiring O(N2)O(N^2) space.

    The combined space complexity is O(N2)+O(N2)+O(N2)=O(N2)O(N^2)+O(N^2)+O(N^2)=O(N^2).

  • Optimized implementation: We use a constant row limit bb, independent of NN.

    • (Gc)I,:(G_c)_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.
    • WI,:W_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.
    • (G^c)I,:(\hat G_c)_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.

    For these three matrices, the combined space complexity is O(bN)+O(bN)+O(bN)=O(bN)=O(N)O(bN)+O(bN)+O(bN)=O(bN)=O(N) for constant bb.

  • From the above analysis, our optimization reduces the combined space complexity of the three cache matrices from O(N2)O(N^2) to O(N)O(N) for constant bb.


Please let us know if any questions remain. We would be happy to discuss them further. Thank you again for your careful review.

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

This paper proposes ROSE-TTA, a training-free, cache-based test-time adaptation framework for vision-language models. It improves cache construction using noise-aware prediction stability and enhances cache utilization through graph-based class-information completion and sample-specific feature refinement. Experiments across multiple cross-dataset and out-of-distribution benchmarks demonstrate competitive performance.

Critical strengths
  1. Clear problem–solution alignment. The proposed components directly address the identified cache issues, including unreliable sample selection, class imbalance, and insufficient sample-specific information.
  2. Comprehensive empirical validation. The ablation studies, cache visualizations, and quantitative comparisons provide consistent evidence that the proposed components improve cache reliability and utilization.
Critical weaknesses
  1. Incremental contribution. The paper addresses several known limitations of cache-based TTA using three technically reasonable components. However, these components mainly provide targeted improvements to an existing pipeline rather than a substantially new formulation or insight.
  2. Limited accuracy–memory trade-off. Compared with TDA on ImageNet, ROSE-TTA increases memory usage by approximately 41% while improving accuracy by only 1.27 percentage points. Although runtime remains comparable, the modest gain may not sufficiently justify the additional memory and system complexity.
Questions for authors

None

6 comments

Thank you for your thoughtful review and valuable questions! We appreciate your recognition of the problem–solution alignment and empirical analysis. Below, we address your questions and indicate the changes we’ve made in response to your suggestions.

W1: Incremental contribution. The paper addresses several known limitations of cache-based TTA using three technically reasonable components. However, these components mainly provide targeted improvements to an existing pipeline rather than a substantially new formulation or insight.

Response: Thank you for the valuable comment. We have added a detailed explanation of our key insight and the technical novelty of ROSE-TTA:

  • Key insight. In streaming settings, reliable cache information can still be incomplete, while completing missing information must account for the reliability of the available information. This motivates us to jointly address cache reliability and completeness end to end, from cache construction through utilization to prediction.

  • Technical novelty. We introduce a unified framework that jointly completes and refines cache information. Uncertainty-aware cache construction favors reliable entries and passes their reliability estimates to graph-based structural completion. For reliability, these estimates give greater weight to reliable cache information. For completeness, text relations supply the global category information missing from sparse caches. Finally, the unified categorical graph G^\hat G integrates both sources to provide more reliable and complete cache information for prediction. Sample-specific refinement further injects online information from the current query to enrich cache information.

W2: Limited accuracy–memory trade-off. Compared with TDA on ImageNet, ROSE-TTA increases memory usage by approximately 41% while improving accuracy by only 1.27 percentage points. Although runtime remains comparable, the modest gain may not sufficiently justify the additional memory and system complexity.

Response: Thank you for the constructive comments. We have optimized ROSE-TTA and added a new efficiency comparison. The optimized version reduces memory overhead over TDA from 41.0% to 7.3% and requires 6.5% less runtime than TDA, while maintaining performance. We have added the experimental results to Table 4.

MethodImageNet Acc. (%)Total time (min)GPU memory (MB)
CLIP68.349.36808.96
TDA69.5150.00860.16
ROSE-TTA, original70.7848.541212.98
ROSE-TTA, optimized70.7746.77922.86

To explain the memory savings above, we analyze graph storage in the original implementation, explain the two optimizations, and compare the space complexity of GcG_c, WW, and G^c\hat G_c before and after optimization. We have added these analyses to Appendix C.3.

Analysis of memory overhead

  • We have added a memory analysis of the graphs and weight matrix in the original implementation. On ImageNet, C=1000C=1000 is the number of classes, and a full cache holds N=5000N=5000 entries, with five entries per class. The table lists the FP32 storage of each graph or matrix. The cache-graph GcG_c, weight matrix WW, and reliability-weighted cache graph G^c\hat G_c account for most of this storage.

    Graph / matrixShapeStorage (MB)
    Cache-graph Gc=FF⊤G_c=FF^\topN×NN\times N95.37
    Weight matrix WWN×NN\times N95.37
    Reliability-weighted cache graph G^c=Gc⊙W\hat G_c=G_c\odot WN×NN\times N95.37
    Text-graph GtG_tC×CC\times C3.81
    Gate-graph MMC×NC\times N19.07
    Unified categorical graph G^\hat GC×CC\times C3.81
  • To reduce the memory overhead, we have proposed two implementation changes.

    • Graph storage. We replace storage of the full cache graph with blockwise computation, computing a few rows at a time. We store only the current rows of GcG_c, WW, and G^c\hat G_c, and reuse their memory for the next few rows.

    • FP16 storage. Following TDA, we store the main tensors of our added modules in FP16. Each converted tensor uses half its FP32 storage.

Derivation of blockwise computation

  • To show how we avoid storing the full cache graph, we have added the following derivation using the paper's graph definition.

    • We select up to bb cached features from FF. Let II be their row index set, so ∣I∣≤b|I|\le b. Each cache entry appears in exactly one index set II. The corresponding ∣I∣|I| rows of GcG_ c are (Gc)I,:=FI,:F⊤(G_ c)_ {I,:}=F_{I,:}F^\top. We compute WI,:W_{I,:} directly from the reliability scores, then multiply these rows elementwise by WI,:W_{I,:}:

      \in\mathbb R^{|I|\times N}.$$
    • We initialize Q∈RC×CQ\in\mathbb R^{C\times C} to zero once. For each II, we sum columns and rows for samples in the same class cache, giving M:,I[(G^c)I,:M⊤]∈RC×CM_{:,I}[(\hat G_c)_{I,:}M^\top]\in\mathbb R^{C\times C}. We add this matrix to QQ and reuse the memory for the current rows of GcG_c, WW, and G^c\hat G_c to process the next II:

      Q=∑IM:,I[(G^c)I,:M⊤]=MG^cM⊤.Q=\sum_I M_{:,I}\big[(\hat G_c)_{I,:}M^\top\big]=M\hat G_cM^\top.

    • Finally, combine QQ with GtG_t to obtain the unified categorical graph:

      G^=softmax⁡row(GtQGt⊤).\hat G=\operatorname{softmax}_{\mathrm{row}}(G_tQG_t^\top).

Theoretical Space Complexity Analysis

  • To explain the main memory savings, we have added a theoretical analysis of GcG_c, WW, and G^c\hat G_c, which dominate the original graph storage.

  • Original implementation:

    • Cache-graph GcG_c: N×NN\times N entries, requiring O(N2)O(N^2) space.
    • Weight matrix WW: N×NN\times N entries, requiring O(N2)O(N^2) space.
    • Reliability-weighted cache graph G^c\hat G_c: N×NN\times N entries, requiring O(N2)O(N^2) space.

    The combined space complexity is O(N2)+O(N2)+O(N2)=O(N2)O(N^2)+O(N^2)+O(N^2)=O(N^2).

  • Optimized implementation: We use a constant row limit bb, independent of NN.

    • (Gc)I,:(G_c)_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.
    • WI,:W_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.
    • (G^c)I,:(\hat G_c)_{I,:}: at most b×Nb\times N entries, requiring O(bN)O(bN) space.

    For these three matrices, the combined space complexity is O(bN)+O(bN)+O(bN)=O(bN)=O(N)O(bN)+O(bN)+O(bN)=O(bN)=O(N) for constant bb.

  • From the above analysis, our optimization reduces the combined space complexity of the three cache matrices from O(N2)O(N^2) to O(N)O(N) for constant bb.


We hope these explanations clarify the contribution of ROSE-TTA and its accuracy–memory trade-off. Please let us know if any concerns remain. Thank you again for your time and helpful feedback!

Dear reviewer xY62,

Thanks for the time you dedicated to carefully reviewing this paper. It would be highly appreciated if you let us know whether our responses properly address your concerns, despite your busy schedule. Thanks a lot!

Best regards,

Authors of submission 33522

Comments on the paper

1 comment
AuthorsOpenReview ↗

General responses and manuscript revision summary

Dear reviewers and AC,

We sincerely thank all reviewers and AC for their great effort and constructive comments on our manuscript. We appreciate this opportunity to engage in discussions with the reviewers. During the rebuttal period, we have been focusing on these beneficial suggestions from the reviewers and doing our best to add several experiments and revise our manuscript. We believe our current carefully revised manuscript can address all the reviewers' concerns.

As reviewers highlighted, our paper addresses the meaningful and practically important problem of reliable online adaptation with incomplete cache information (Reviewers dDJA and YziE). We also appreciate that reviewers found our framework reasonably designed (Reviewer dDJA) and closely aligned with the identified cache challenges (Reviewers xY62 and YziE), with well-designed graph-based structural completion and sample-specific refinement mechanisms (Reviewer YziE). Furthermore, we appreciate the recognition of our comprehensive empirical validation (Reviewer xY62).

Moreover, we thank the reviewers for pointing out the need for clearer motivation and technical novelty (Reviewers xY62, dDJA, and YziE), clearer comparisons with existing cache-based TTA methods (Reviewers dDJA and YziE), further discussion of memory overhead (Reviewers xY62 and dDJA), comparisons with additional methods (Reviewer YziE), comparisons under shared prompt settings (Reviewer dDJA), independent branch ablations and a baseline without our modules (Reviewers dDJA and YziE), cache class imbalance experiments (Reviewer dDJA), alternative noise generators (Reviewer YziE), investigation of the early adaptation stage (Reviewer YziE), and clearer explanations of the unified categorical graph, sample-specific refinement, and Figures 1(a) and 1(b) (Reviewer YziE). In response, we have revised the manuscript and added the following analyses and experiments:

  • [Reviewers xY62, dDJA, and YziE] We add clarification highlighting our motivation to jointly address cache reliability and completeness end to end, from cache construction through utilization to prediction in the Introduction.

  • [Reviewers dDJA and YziE] We add a comparison between ROSE-TTA and existing cache-based TTA methods in Section 4.

  • [Reviewer dDJA] We add fair comparisons under shared prompt settings in Table 5.

  • [Reviewer YziE] We add accuracy comparisons with seven additional methods under shared cache and prompt settings in Appendix D.9.

  • [Reviewers dDJA and YziE] We add independent branch ablations and a baseline with all three modules removed to verify the effectiveness of each module in Table 3.

  • [Reviewer dDJA] We add cache class imbalance experiments by varying per-class capacities in Table 6.

  • [Reviewers xY62 and dDJA] We add optimized ROSE-TTA to the efficiency comparison, showing that it reduces memory overhead over TDA from 41.0% to 7.3% and takes 6.5% less time than TDA while maintaining accuracy, as reported in Table 4.

  • [Reviewers xY62 and dDJA] We analyze original graph storage, describe the optimizations, and compare the space complexity of GcG_c, WW, and G^c\hat G_c in Appendix C.3.

  • [Reviewer YziE] We add runtime and accuracy comparisons with existing cache-based TTA methods in Appendix C.4.

  • [Reviewer YziE] We add an experiment comparing noise generators in Appendix D.11.

  • [Reviewer YziE] We compare cache prediction scores and cumulative accuracy during early adaptation to illustrate the effect of graph-based structural completion in Appendix D.8.

  • [Reviewer YziE] We clarify the definition and function of the unified categorical graph G^\hat G in Eq. (6) in Section 3.3.

  • [Reviewer YziE] We clarify that F^\hat F is used only for the current prediction in Section 3.3.

  • [Reviewer YziE] We clarify the axes and interpretation of Figures 1(a) and 1(b) in Section 3.1.

These manuscript revisions are highlighted in blue\color{blue}{\text{blue}} to facilitate checking.

We hope our responses and revisions address the reviewers' concerns, and we welcome further questions and discussion. Thank you again for your time and constructive feedback.

Many thanks,

Submission33522 Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.