TTVD: Towards a Geometric Framework for Test-Time Adaptation Based on Voronoi Diagram

We thank Reviewer wGB6 for the positive feedback and valuable review!

Response to Weakness 1: We will answer your concern below regarding your Question 1.

Response to Weakness 2: Thank you for pointing this out. We agree that the idea of "fully TTA" (carefully quoted here from TENT) excludes access to source data. However, as modern methods continue to evolve, it can be observed that SODA methods often do not strictly adhere to these settings. For instance, NOTE[1] requires pre-training from scratch to implement its proposed batch normalization layers, and AdaNPC[2] similarly relies on pre-training with its proposed KNN-based loss function. From their experiments, we observed that they primarily compare their results to the same baseline we used.

While categorizing previous TTA methods is not the main focus of our paper, we think that their primary distinction lies in their methodology rather than their settings: TTT employs self-training, whereas TENT utilizes entropy minimization. Since our adaptation approach aligns more closely with entropy minimization, we included these baselines for comparison. However, we understand your concern and have added additional baselines from more recent methods that incorporate self-training or require modifications to the pre-training process.

Response to Weakness 3: In standard VD, each Voronoi cell is dominated/influenced by a single site $\mu_k$, as Eq. 2 shown. In contrast, in CIVD, each cell is influenced by a cluster of sites $\mathcal{C}_k$, as Eq. 4 shown. This transition to multi-site influence enhances the robustness of the cells. Essentially, a standard VD can be viewed as a special case of 1-nearest neighbor, as VD serves as a foundational structure for nearest-neighbor methods. We have added a figure at the end of Section 3 to illustrate the differences among VD, CIVD, and CIPD, providing a clearer explanation.

Response to Weakness 4: You are right that label y is generated by replacing $d$ with $F$. However, there seems to be a misunderstanding regarding our proposed method. In fact, VD, CIVD, CIPD are seperate structures. We have revised our summary of them at the end of Section 3 for clarity. VD → CIVD → CIPD represent a progressive relationship rather than a combination. VD is the simplest point-to-point structure among the three. CIVD builds upon it as a cluster-to-point structure, while CIPD further extends CIVD by incorporating the power distance, as described in Eq. 5. We have added the pseudo-code for CIVD and CIPD in Appendix H. We use CIPD for all datasets, as it is the most advanced structure of the three.

Response to Weakness 5: Thank you for your advice. We submitted our code in the supplementary to help public readers understand and reproduce our method. $\mu$ is calculated from the class means of the training set, which is stated under the ``implementation details'' in the experiment section. To generate $\mathcal{C}$, we use self-supervision to expand the Voronoi sites, which is stated in detail in Section 3.2. For example, we use rotation to expand $K$ sites to $4K$ sites, and every 4 sites form a cluster $\mathcal{C_k}$. $v$ is set according to Lemma 3.1, where it can be calculated from the classifier layer of the pretrained model.

Response to Question 1: We are grateful for the opportunity to explain! We understand that this paper is intensive on Voronoi Diagrams, a classical structure from computational geometry that are not widely explored in the field of machine learning, which may challenge the readability.

As reviewer ET99 commented, our method is the first to apply VD for Test-time Adaptation, even though VDs were originally developed for space partition. Our contribution is mainly about the exploration between VDs, neighbor-based methods and TTA. First, we revealed that nearest neighbor algorithms can be analyzed through standard VD. Then, we find that advanced VDs, such as CIVD, PD, offer benefits for TTA, because of their unique properties (enhanced robustness from multi-site influence, more flexible partitions). We would like to note that previous papers on CIVD mainly focus on theoretical aspects in geometry [6][7][8]. In contrast, our work seeks to explore its potential, bring renewed attention to it, and transition it into machine learning applications, specifically TTA.

Thank you for your constructive comments. We address the concerns as follows.

Response to Weakness 1: We report the GPU memory usage and process time for each batch on CIFAR-C as below. The memory usage is similar to TTT, while TTVD is faster and similar to TENT.

Response to Weakness 2: Your are right that a theoretical analysis of VDs would greatly benefit the understanding of our method. Actually, this is also a challenge for most of the current TTA methods. We will leave this a valuable future work.

Response to Weakness 3: Thank you for your advice. We have added the pseudo-code for CIVD and CIPD in the Appendix H. We also included our code in the supplementary materials for public readers to understand and reproduce our method.

Response to Weekness 4: The only hyperparameter introduced in our method is $\gamma$ that control the magnitude of influence. We find it does not affect the model's accuracy. We set $\gamma=-0.8$ as a heuristic value to appropriately scale the influence of distant sites. Additionally, we provide a toy 3D illustration of the influence function to help your understanding, showing that as the distance increases, the influence of a site diminishes (https://anonymous.4open.science/r/iclr-654F/output.png).

We sincerely thank Reviewer WP62 for the valuable time and effort in reviewing our work. We address the concerns as follows.

Response to Weakness 1: As reviewer ET99 commented, our method is the first to apply VD for Test-time Adaptation, even though VDs were originally developed for space partition. Our contribution is mainly about the exploration between VDs, neighbor-based methods and TTA. First, we revealed that nearest neighbor algorithms can be analyzed through standard VD. Then, we find that advanced VDs, such as CIVD, PD, offer benefits for TTA, because of their unique properties (enhanced robustness from multi-site influence, more flexible partitions). We would like to note that previous papers on CIVD mainly focus on theoretical aspects in geometry[1][2][3]. In contrast, our work seeks to explore its potential, bring renewed attention to it, and transition it into machine learning applications, specifically TTA.

Response to Weakness 2: We explain the setting of $\gamma$, $\epsilon$, and $\tau$ as follows.

$\epsilon$ is the machine epsilon, i.e. the smallest number that a computer can recognize as being greater than zero, but still very small in magnitude. It is used for code implementation, to improve the numerical stability, rather than a hyperparameter for the algorithm. We set it as 1e-8, similar to the epsilon used in Pytorch Adam implementation.

$\tau$ is temperature of the softmax function. We use the standard softmax function, where $\tau = 1$. Both $\epsilon$ and $\tau$ are included in the equation for completeness and are set according to common implementation practices, rather than being treated as hyperparameters to tune in our framework.

$\gamma$ is the parameter to control the magnitude of the influence. We use a small negative value to scale and diminish the influence of distant sites. For example, we provide a toy 3D illustration of the influence function to show that as the distance increases, the influence of a site becomes smaller (https://anonymous.4open.science/r/iclr-654F/output.png). We find that $\gamma$ does not affect the accuracy performance a lot from below, and we set $\gamma=-0.8$ as a heuristic value to appropriately scale the influence of distant sites.

Aside from these, common parameters such as the learning rate are configured according to the TTAB framework, as discussed in Appendix D. No additional parameters are introduced in our geometric framework.

Response to Weakness 3: We included 3 more recent methods to compare as below. It is worth noting that, since our method is based on VDs, it is orthogonal to most current approaches. This means it can be combined with other methods to further enhance performance.

Response to Question 1: We explained this in Weakness 2 above and it does not affect the model's accuracy.

Response to Question 2: Epsilon is a very small value used to enhance numerical stability in the code implementation, particularly when calling the log-softmax function in PyTorch. This is similar to the Adam optimizer implementation in PyTorch. We agree that the log problem might not arise, but we include this detail in the manuscript for completeness, and it does not affect the performance.

Response to Question 3: Thank you for your advice. Voronoi sites are computed from the training set and the adaptation follows them using test data. We stated in the experiment section, under the "implementation details".Additionally, we have included a figure at the end of Section 3 to illustrate the workflow of our method. Furthermore, we shown that our method is robust to the precision of the Vonronoi sites in Table 4.

[1] Danny Z. Chen, et al. On clustering induced voronoi diagrams. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science.

[2] Danny Z. Chen, et al. On clustering induced voronoi diagrams. SIAM Journal on Computing, 46(6):1679–1711, 2017.

[3] Ziyun Huang, et al. Influence-based voronoi diagrams of clusters. Computational Geometry, 96:101746, 2021a. ISSN 0925-7721.

[4] Ma, Jing. "Improved Self-Training for Test-Time Adaptation." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.

[5] Kang, Juwon, et al. "MemBN: Robust Test-Time Adaptation via Batch Norm with Statistics Memory." European Conference on Computer Vision. Springer, Cham, 2025.

[6] Oh, Yeongtak, et al. "Efficient Diffusion-Driven Corruption Editor for Test-Time Adaptation." arXiv preprint arXiv:2403.10911 (2024).

We appreciate your time and effort in reviewing our manuscript. Here are the clarification and answers to the concerns.

Response to Weakness 1: Thank you for your advice. We have added the pseudo-code for CIVD and CIPD. However, there seems to be a misunderstanding regarding our proposed method, possibly due to our wording. In fact, VD, CIVD, CIPD are seperate structures. We have revised our summary of them at the end of Section 3 for clarity. VD → CIVD → CIPD represent a progressive relationship rather than a combination. VD is the simplest point-to-point structure among the three. CIVD builds upon it as a cluster-to-point structure, while CIPD further extends CIVD by incorporating the power distance, as described in Eq. 5. Our experiments demonstrate that their performance follows the order: CIPD > CIVD > VD.

As defined in Eq. 4 and Eq. 6, only a single hyperparameter, $\gamma$, is introduced in both CIVD and CIPD. We find that $\gamma$ does not affect the accuracy performance a lot, and we set $\gamma=-0.8$ as a heuristic value to appropriately scale the influence of distant sites.

Response to Weakness 2: Your are right that we do inference using VDs instead of linear layers. Actually, not only SHOT but also many current TTA methods (TENT, NOTE, Conjugate PL, SAR) utilize entropy minimization. The unique properties of CIVD and CIPD contributing to the overall improvement. CIVD introduces multi-site influences, enhancing robustness, while CIPD enables more flexible partitioning by incorporating the power distance function.

Response to Minor Weakness 3: Thank you for your advice. We have revised them in our manuscript.

Response to Question 1: Yes, the Voronoi sites won't be updated. They are served as the adaptation guidance.

Response to Question 2: To get the soft prediction, simply replace $d$ with $F$ in Equation 3.

Response to Question 3: $v$ is set according to Lemma 3.1, where it can be calculated from the classifier layer of the pretrained model.