TTVD: Towards a Geometric Framework for Test-Time Adaptation Based on Voronoi Diagram
Authors: Mingxi Lei
Chunwei Ma
Meng Ding
Yufan Zhou
Ziyun Huang
Jinhui Xu
Venue: ICLR 2025 Poster (2025)
Keywords: Test-time adaptation
out-of-distribution generalization
distribution shift
computational geometry
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We demonstrate that the augmented Voronoi Diagram is an effective model for test-time adaptation.

Abstract: Deep learning models often struggle with generalization when deploying on real-world data, due to the common distributional shift to the training data. Test-time adaptation (TTA) is an emerging scheme used at inference time to address this issue. In TTA, models are adapted online at the same time when making predictions to test data. Neighbor-based approaches have gained attention recently, where prototype embeddings provide location information to alleviate the feature shift between training and testing data. However, due to their inherit limitation of simplicity, they often struggle to learn useful patterns and encounter performance degradation. To confront this challenge, we study the TTA problem from a geometric point of view. We first reveal that the underlying structure of neighbor-based methods aligns with the Voronoi Diagram, a classical computational geometry model for space partitioning. Building on this observation, we propose the Test-Time adjustment by Voronoi Diagram guidance (TTVD), a novel framework that leverages the benefits of this geometric property. Specifically, we explore two key structures: 1) Cluster-induced Voronoi Diagram (CIVD): This integrates the joint contribution of self-supervision and entropy-based methods to provide richer information. 2) Power Diagram (PD): A generalized version of the Voronoi Diagram that refines partitions by assigning weights to each Voronoi cell. Our experiments under rigid, peer-reviewed settings on CIFAR-10-C, CIFAR-100-C, ImageNet-C, and ImageNet-R shows that TTVD achieves remarkable improvements compared to state-of-the-art methods. Moreover, extensive experimental results also explore the effects of batch size and class imbalance, which are two scenarios commonly encountered in real-world applications. These analyses further validate the robustness and adaptability of our proposed framework.

Published as a conference paper at ICLR 2025
TTVD: TOWARDS A GEOMETRIC FRAMEWORK FOR TEST-TIME ADAPTATION BASED ON VORONOI DIA- GRAM
Mingxi Lei', Chunwei Ma², Meng Ding', Yufan Zhou', Ziyun Huang'; Jinhui Xu
Department of Computer Science and Engineering, University at Buffalo, SUNY
JMP Statistical Discovery LLC
3 Adobe Research
4 CComputer Science and Software Engineering, Penn State Erie
Sccoool of Information Science and Technology, University of Science and Technology of China
I imingxilo le, mengding @
@bu falffflloooo edu, Pchunwei ma jmp com tyufzhou@adoba com, #2x201@psuu edu, 9jhxu00@gmai com
ABSTRACT
Deep learning models often struggle with generalization when deploying real- world data, due to the common distributional shift to the training data. Test-time adaptation (TTA) is emerging scheme used inference time to address this issue. In TTA, models are adapted online at the same time when making pre- dictions test data. Neighbor-based approaches have gained attention recently, where prototype embeddings provide location information to alleviate the feature shift between training and testing data. However, due their inherit limitation of simplicity, they often struggle to learn useful patterns and encounter perfor- mance degradation. To confront this challenge, we study the TTA problem from a geometric point of view. We first reveal that the underlying structure of neighbor- based methods aligns with the Voronoi Diagram, a classical computational geom- etry model for space partitioning. Building this observation, propose the Test-Time adjustment by Voronoi Diagram guidance (TTVD), novel framework that leverages the benefits of this geometric property. Specifically, we explore key structures: (I) Cluster-induced Voronoi Diagram (CIVD): This integrates the joint contribution of self-supervision and entropy-basee methods to provide richer information. (II) Power Diagram (PD): A generalized version of the Voronoi Diagram that refines partitions by assigning weights each Voronoi cell. Our experiments under rigid, peer-reviewed settings CIFAR- 10-C, 100-C, ImageNet-C, and ImageNet-R shows that TTVD achieves remarkable improve- ments compared to ofate-of-the-art methods. Moreover, extensive experimental results also explore the effects of batch size and class imbalance, which are two scenarios commonly encountered in real-world applications. These analyses fur- ther validate the robustness and adaptability of our proposed framework.
INTRODUCTION
Deep learning models have demonstrated impressive capabilities across a multitude of recognition tasks, thanks substantial large datasets, advanced network architectures and computing capabil- ity (He et al. 2016 Zagoruyko & Komodakis 2016: Vaswani et al., 2017: Sutskever et al. 2014] Goodfellow et al. 2014; Ho et al., (022)). Nevertheless, they always struggle with generalization when faced with distribution shifts in test data, which is common challenge in real-workh scenar- ios. For instance, natural images sourced from diverse geographic locations, timeframes, and angles inherently exhibit variations in appearance, such as differences in brightness and contrast. Similarly, medical images acquired through various devices may vary due to differences in imaging protocols.
Jinhui Xu and Ziyun Huang are co-corresonding authors.
1 Part of Jinhui Xu's work was done the University Buffalo, SUNY.

---

Published as a conference paper at ICLR 2025
B000
(A)
Augmented Voronoi Diagram
Corrupted Data
Voronai Diagram
Power Diagram
Adapt
RAZA
(B)
Augmented Voronol Diagram
T3A (neighbor-based)
Tent
Voronoi Diagram
Accuracy: 58.43%
Accuracy: 74.04%
Accuracy: 75.34%
Accuracy: 98.54%
Figure 1: (A) Visualization of space partitions induced by Voronoi Diagram, Power Diagram and Augmented Voronoi Diagram (by self-supervision) MNIST-C (Mu & Gilmer] 2019) (digit "0" ~ "2" only, gaussian-noise-cne corrupec))) in R2. (B) Visualization of adaptation performance on MNIST- C Cusing T3A (Iwasawa & Matsuo 2021). Tent (Wang et al. [222 and VD and Augmented VD with joint influence. See Appendix C for details.
Test-time adaptation (TTA) (Wang et al. 2021 Sun et al. 2020 Liu et al. 2021b; Niu al. 2023
Iwasawa & Matsuo 2021 Zhang et al. 2021 Gong et al. [002 Wang et al.] 2002 Goya et al. online adaptation strategy tackle the problem. While TTA shares some similarities with domain adaptation (French et al. 2017 Ganin al. 2016). it differs in two key aspects: the source data unavailable at time, and only the current mini-batch of unlabeled test data is used for adaptation. Recent studies on TTA have primarily focused on two categories of methods: self-supervision, as proposed by [Sun et (2020); Liu et al. (2021b). and entropy minimization, as proposed by Wang et al.) (2021). Despite these advances, current TTA methods still face two critical limitations as follows.
2022 Niu al.][202 Zhao et al. 2023 has emerged
(I) The first challenges is the reliance on insufficient or incomplete information during test-time, which restricts the ability of these methods to fully adapt to unseen data. For instance, self- supervision may inadvertently lead to overfitting on auxiliary tasks, which in turn degrades the model's performance on the primary objective, such as object recognition (Liu et al.) 2021b). Ad- ditionally, more recent work (Press et al. 2024 points out that entropy minimization may fail after many iterations due to test feature embeddings drifting from the training data class means. In re- sponse these challenges,
nrighbor-basee methods (Liang et al.] 2020 Jang et al. 2022 Liang et al. 2021: Zhang et al., 20233 Hardt & Sun 2024) have gained attention in recent state-of-the-art approaches, as they leverage information from the training data neighborhood ting and align test embedding. However, these methods often fail to adjust the model sufficiently to learn better patterns (Figure Dp. resulting suboptimal performance, and leaving the issue of robust and effective test-time adaptation unresolved. (II) A second critical challenge arises from nega- tive model updates, which stem from two main factors: noisy samples and conflicting gradients. Niu et al. (2023) highlights that noisy samples can adversely affect entropy minimization, leading to suboptimal adaptation. Moreover, (Gandelsman et al. (2022) demonstrates that jointly training self-supervision and entropy minimization can degrade accuracy the ImageNet validation set due to negative transfer aJang et al. 2023) Javaloy & Valera 2022). This often occurs when conflict- ing gradients happens from sharing single set of network parameters for multiple task objectives, ultimately leading to diminished performance. Neighbor- based methods often handle these issues poorly due their inherent limitations in addressing noisy samples and conflicting objectives.
mitigate overfit-
2

---

Published as a conference paper at ICLR 2025
In essence, the underlying geometric structure of these neighbor-basee based methods is Voronoi Diagram (VD) (Aurenhammer 1991). a classical geometry model for space partition. This geometric frame- work has been applied across various domains of deep learning due to its inherent mathematical benefits (Ma et al. 2022 2023 You et al., 2022 Balestriero et al., 2023). VD offers high inter- pretability, with visualizations derived from its construction algorithm in R allowing for analytical solutions to all partition boundaries (Figure I]. Additionally, recent advancements in geometric
structures (Aurenhammer 1987: Chen al., 2013 2017 Huang et al., 2021a) based on VD offer improved properties over its original form, creating more complex space partitions.
Building on the strengths of geometric structures, in this paper, we revisit the TTA problem from geometric view and utilize their potential to address the challenges by introducing our proposed framework, Test-time adjustment by Voronoi Diagram guidance (TTVD). Specifically, we focus on two key structures, Cluster-induced Voronoi Diagram (CIVD, (Chen et al., 2013) 2017: (017:Huane Huang et al.) 2021a)) and the Laguerre-Vorone Diagram (a.k.a Power Diagram, PD (Aurenhammer (987)). (I)
CIVD, recent breakthrough in computational geometry, extends VD from a point-to-poing distance- based diagram to a cluster-to-point influence-based structure. It enables us to assign partitions (Voronoi cells) not only based on a point (e.g class prototypes), but also cluster of points, thereby enhancing robustness during test time. (II) PD generalizes VD to create more flexible partitions by weighting each cell differently. This weighted structure enables PD to handle varying levels of influ- ence for different points, making it particularly effective in identifying noisy samples near decision boundaries. Our contributions are summarized as follows,
We revisit the Test-Time Adaptation problem from geometric view and formulate it using Voronoi Diagram. It is a powerful structure with two key advantages: (I) VD highly interpretable, allowing for clear visualizations and analytical boundary solutions in R², and (II) advancements in VD-based structures offer robust partitioning, which have not yet been explored in TTA. Based on these insights, we first introduce the foundation of guiding TTA by VD, paving the way to integrate more advanced geometric structures to further adaptation improvements.
We propose to use Cluster-induced Voronoi Diagram, a recent breakthrough geometric structure to guide TTA. Specifically, extending the traditional VD to CIVD allows us to create more robust space partitions, as Voronoi cells are determined by a cluster of points rather than individual points. Furthermore, the joint influence mechanism of its cluster-to-poing structure can unify multiple objectives, enables seamless integration of self-supervision and entropy minimization, thereby improving adaptation in dynamic test environments.
We conducted a fine-grained analysis of loss landscape utilizing the iterpretability of VD, uncov- ering that current sample filtering strategies may not effectively remove noisy samples. To address this, we propose filter samples near partition boundaries by incorporating the Power Diagram. PD's flexible boundaries allow for more precise identification of noisy samples, thereby improving the efficiency of sample filtering and enhancing model robustness.
2 RELATED WORK
Domain Adaptation. Domain adaptation (DA.) (French al.) 2017 Ganin et al. 2016 Li al., 2018) aims to alleviate the performance degradation caused by the distribution discrepancies be- tween training and testing data. Classical approaches involve joint optimization on both source and target domains to enable domain generalization (Ganin et al. 2016 Li et al. (018)). Source-free do- main adaptation (SFDA) (Liang al.
2020 2021] Kundu et al. [022 Liu al. 2021a is a subset of DA where source data is unavailable during adaptation. This setting has been explored in various studies, including SHOT (Liang et al. 2020). USFDA (Kundu et al.) 2020) SFDA methods can be
roughly categorized into self-supervised training (Achituve et al. [021]
Pan Pan et al. 2020) Chen et al.)
2020 neighborhood clustering (Yang et al. 2023 2021) and adversarial alignments (Tang & Jia
2020
Kang al. 2018 Shen et al. 2024)..
Test-time Adaption and its Neighbor- Methods. Test-Time Adaptation refers to the process of adapting pre-trained model to distribution shifts encountered during testing, without access- ing the original training data. Unlike domain adaptation, which focuses on both source and target domains during training. TTA operates solely at test time, making it more flexible for real-world applications where training data may no longer be available. Many approaches to TTA have focused on beiehdor-based methods, which utilize neighborhood information for adaptation. For example,
3

---

Published as a conference paper at ICLR 2025
adjusts the classifier by updating the linear layer with pseudo-prototype representations derived from the test data. Similarly, Test- Time Adaptation via Self- Training (TAST, (Jang et al. 2022)) introduces trainable adaptation mod- ules on top of a frozen feature extractor, while AdaNPC (Zhang et al. 2023) leverages deep nearest neighbor classifiers for adaptation. In addition to these neighbor-based methods, other approaches
Test-Time Template Adjuster (T3A, (wwasawa & Matsuo 2021)
explore TTA from different perspectives, including self-training (Sun et al. [2020] Liu et al.
202
and entropy minimization (Wang al. 2021 Gong et al. 2022 Niu al. 2023; Wang al. 2022)
It is worth noting that these methods are not always mutually exclusive; many TTA techniques com- bine multiple strategies to improve performance, blending ideas from neighbor- based adaptation with self-training or entropy-based optimization. Some previous algorithms (e.g. SHOT (Liang) et al. ) in DA can also be repurposed and adapted to be used in TTA.
Computational Geometry for Deep Learning. Computational geometry is branch of computer science and mathematics that focuses on the study of algorithms for solving geometric problems. Traditionally, it has been applied in computer graphics, robotics, and geographic information sys- tems. However, recent studies have increasingly explored its potential in machine learning, uncov- ering valuable insights across various domains. In the theoretical perspective, studies (Balestriero) jet al., 2019 Balestriero & Baraniuk, 202T) have established a link between convolutional neural networks and computational geometry, showing that deep networks recursively partition the input space into cells. Similarly, (Wang et al.) 2019) provides a geometric analysis of recurrent neural networks (RNNs), demonstrating that RNNs also segment input space. More recently, (Balestriero it al. 2023) reveals that the output of a multi-head attention block in transformers is the Minkowski sum of convex hulls, enabling feature extraction for downstream tasks. In the application perspec- tive, computational geometry has been utilized in deep learning for various tasks. Deep Voro (Ma al., 2022) unifies few-shot learning methods using Cluster-induced Voronoi Diagrams (Huang et al. 202 to aggregate heterogeneous features. iVoro (Ma et al. (023) enables exemplar-free class-incremental learning by progressively constructing Voronoi cells for new classes. SplineCam (Humayun et al., 2023) visualizes decision boundaries and input partitions using continuous piece- wise linear splines. FedUD Lei et al.] (2025) addresses the domain gap in federated learning by ensuring consistency in Voronoi Diagrams across clients, effectively aligning feature distributions.
METHODOLOGY
In this section, we first revisit the general setting of TTA. Then, we introduce the geometric frame- work based on the Voronoi Diagram and further extend to two well-established geometric struc- tures, the Power Diagram and the Cluster-induced Voronoi Diagram.
Problem Setup. Test-time adaptation refers to the process of adapting a pre-trained model to dis- tribution shifts that occur between the training and testing phases, without accessing the original training data or labels during test time. Formally, let Dirain and Drest be the training and test dis- tributions, respectively, where Prest exhibits shift from Dtrain. The goal of TTA is to adapt the model fo. with parameters learned from Dtrain, using only the unlabeled test data X to improve performance the shifted distribution. For K K-way classification problem, online test stream of data { E Xtest are used to update the model 0 as follows at every time step L
infer: U. = (o, adapt: Oc+1 = 0c XV
where J. represents the model's prediction for and L is the user-defined loss function. For example, Tent (Wang et al. p minimizes the entropy loss f = pp() log p(te), while TTT (Sun et al. (2200) minimizes the self-supervised rotation prediction loss from the auxiliary classifier. Commonly, only the channel-wise affine parameters in normalization layers are updated during TTA, while the rest of the model remains unchanged. This approach ensures computational efficiency, making it suitable for real-time adaptation during testing. For convenience notation and throughout the following analysis, the parameter set f is separated into two components: the feature extractor, denoted as or, and the classifier, denoted as th. The time step subscript is dropped unless otherwise specified.
4

---

Published as a conference paper at ICLR 2025
3.1 VORONOL DIAGRAM: FOUNDATIONAL GEOMETRIC STRUCTURE FOR NEIGHBOR BEIGHBOR-BASED TEST-TIME ADAPTATION
Geometrically, Voronoi Diagram has long been foundational structure for the analysis of nearest neighbor algorithms. It partitions space based on distances to a set of points as follows,
Definition 3.1 (Voronoi Diagram). Let d be the distance function associated with R where is the dimensionality of feature space. A Voronoi Diagram partitions the space into K disjoint cells = [Wi, "..,"",,4000 .WK) such that 1 = TR... Each cell is obtained via wi = {2 E TR : r(2) = r). r E {1,-.. _K3. with
r(z) arg min d(2, Mx), kE(I....KK
(2)
where Ps is the center (also referred to as Voronoi site) of k-th cell. VD partitions into the space K' disjoint cells, where the boundaries between these cells are determined by the distances that are equidistant from two or more sites. These boundaries form the edges of the Voronoi cells, and they help define distinct regions around each site. Based on this property, VD can classify feature points by Equation 2 assigning each point to the site that minimizes the distance between them. In TTA, since the training distribution Drest deviates from Dtrain. feature points may not fall into correct cells (Figure [). Therefore, at every time step, the adaptation can be formulated based on alignments between feature points and Voronoi cells, with our propsed VD-based loss,
infer:
Uk ()) +eT), +
VD loss:
UK log Un LVD(Ük)
Σ k
where B(zjiT) Σ,
softmax funetion with temperature scaling factor T, E is the machine ep- silon for improving numer- ical stability in code im- plementation and Oæ is the predicted soft label of x. The intuition behind this distance-based loss is to encourage feature points move closer one of the Voronoi sites. The scaling factor con- trols the regulation strength towards the sites. When feature point is sufficiently close to a site, the VD loss minimized. This formulation can be seamlessly integrated into TTA, as presented in Algorithm [ forming the basis for more advanced geometric structures that will be introduced later. Commonly, the Voronoi site can be set using the class mean of the training data Xtrain-
Algorithm 1: VD-based Guidance for Test-time Adaptation
Input: Pretrained feature extractor oo. Voronoi sites μa, test stream {æ)+
Output: Prediction stream {ūk J for each online batch {z} : do
infer: Ih =3(-d(a(xz), un) +ET); // Equation adapt: oc+1 = di AVLvv(0))
// Equation
end
3.2 INDUUEDD VORONOI DIAGRAM: MULTI-SITE INFLUENCES MECHANISM IMPROVES ROBUSTNESS
Cluster-induced Voronoi Diagram is a generalization of the ordinary Voronoi Diagram that extends VD from point-to-poing distance-based diagram to a cluster-to-point influence-based structure. While VD has been extensively studied for its exceptional utility in wide range of analyses, its inherent simplicity can be limiting in certain complex scenarios. One key characteristic of VD is that the influence from each site is independent and does not interact or combine with other sites. However, real-world applications, it is common for influences from multiple sources to be "combined" to create joint influence. For example, in physics, point mass may receive forces from a number of other masses, and the combined effect of these forces jointly determines the motion of p. CIVD improves VD by introducing such multi-suurce influence below,
Definition 3.2 (Cluster-induced Voronoi Diagram (Chen et al. 2013 2017 Huang et al., 2021b))
Let [C,,..., Ck) be set of cluster and F(z, Cx) is pre-defined influence function. A Cluster- induced Voronoi Diagram partitions the space into K disjoint cells Ω {wI, [WK such that
uK W I.. Each cell is obtained via W, = {a e R : r(z) = r). r (1..... : K), with
r(2) arg max F F(2, Cx), where the influence between and Cs {p(()) commonly defined ())
5

---

Published as a conference paper at ICLR 2025
(A)
(B)
1.08
O
0.96
0.84
0.72
0.60
0.48
0.36
0.24
0.12
0.00
{FeD Nirpoou1
(rvp)oaa
frenbosa
Figure 2: Noisy sample filtering by diagram subtraction. (a) Entropy landscape of MNIST. Loss
value quickly shrinks once a sample leave the boundaries. (b) Multi-site provides more reliable samples. The solid and dash line are boundaries given by PD and VD, respectively. Reliable samples can be identified by subtracting Voronoi cells, marked in deeper colors.
as
(x, sign(>)
E(d(1e (0) =)))² 2))?
(4)
Here, denotes the item index of the cluster Ca and y is a hyperparameter that controls the scale of the influence. Similar VD, CIVD partitions the space into disjoint cells, while the bound- aries are determined by cluster of points CR. given the influence function F' (Equation D Inspired by this, CIVD shows great promise for robust adaptation through its multi-source influence mech- anism, offering greater effectiveness in scenarios where single-point influence is insufficient. It particularly well suited for TTA, where only small batches of data are available at each time step. The multi-source framework allows the model to dynamically adapt the limited information provided, improving its ability to generalize and maintain performance in challenging, real-time set- tings where traditional methods may struggle capture the full complexity of the data distribution. Specifically, C. can be established via self-supervision, benefiting from data augmentation for im- proved robustness. We utilize rotation augmentation, where images are rotated at different angles Rol, E (0, 90, 180, 270] to generate CN, and each rotation corresponds to a Voronoi site (a) This process is performed using self-supervised label augmentation (Lee al. 2020). Similar Equa- 3 the soft label given by CIVD can be calculated from the influence function, incorporating the expanded sites Pk (a)
enhancing robustness against individual predictions.
Additionally for TTA, CIVD expands Voronoi site μ4 to a cluster of site Ck. integrating the approach of self-supervision and entropy minimization. The joint label vf(c) avoids the negative transfer since the objective is now unified.
3.3 POWER DIAGRAM: IDENTIFYING NOISY SAMPLES BY FLEXIBLE BOUNDARIES
Voronoi Diagram (a.k.a Power Diagram) is another generalization of the Voronoi Diagram that extends the concept by moving from equally-weighted sites to werihhey-weighted sites. tra- ditional VD, each site is treated equally, which may not be suitable for all scenarios. PD improves VD by introducing the power distance between point and site as follows,
Definition 3.3 (Power Diagram (Aurenhammer 1987)). Let d the distance function associated with space T a Power Diagram partitions the space into K disjoint cells S2 {wi, ... ,wk] } such that K w R.d. Each cell associated with a weight is and obtained w, {2 R r(2) r). (1,....K] with
r(z)
arg min (z, v ke(1..... .K}
(5)
Lemma 3.1 Ma et al.
A logistic regression model parameterized by W kxe and 6k partitions the feature space E into a K-eell Power Diagram with pa = 1 kkk and of
2023 2022
8* *+ | 1xxee]?

---

Published as a conference paper at ICLR 2025
VD
Diagram Precomputation
CIVD
Inference
CIPD
Adaptation
Figure 3: (Left) Illustrations on differences between VD, CIVD and CIPD. (Right) Illustrations on Test-time adaptations by Voronoi Diagram(s) guidance.
illustration of the Power Diagram is given in Figure 1 By adding weights to the sites, the boundaries of the cells can be shifted in orthogonal directions, allowing for more flexible partition- ing. Noted that CIVD and PD are parallel structures, meaning they can be seamlessly integrated. CIVD can be retrofitted to CIPD follows for further robustness improvements,
Definition 3.4 Cluster-induced Power Diagram). Let C {CI.... Cx } be set of cluster and F(z, C&) pre-defined influence function. Cluster-induced Power Diagram partitions the space into K disjoint cells Ω (Wi,-.. wK) } such that UK - = Re. Each cell is obtained via wp- {= IR r(z) = r). r {I, Kj. with r(z) = arg max Cx,, where the influence RE(I...,KK)
between and Cs (1(2) are defined
F (2, -sign(>) Eid(u (0) -
-2f77
(6)
As mentioned earlier, noisy samples negatively impact entropy minimization, resulting subopti- mal adaptation. Existing methods propose addressing this issue by filtering out these samples based on their entropy values, drawing from empirical observations of the relationship between adaptation accuracy and gradient norms. This approach is plausible since models tend be more confident in predicting low-entropy samples, and the gradients produced by these samples are considered more reliable. However, the underlying relationship between entropy values and sample selection re- mains unclear. To further explore this, we adopt geometric perspective using the interpretability of the VD. From the visualization of the entropy loss landscape Figure 24. it can be observed that noisy samples are only identifiable if they are near the boundaries, leaving many noisy samples undetected. Inspired by the boundary-shinn shifting capability of the PD, we propose incorporating PD to improve noisy sample filtering. By subtracting the PD from the VD, we can extract larger re- gion from the resulting differences, which may also capture areas contributing to unstable gradients. Noisy samples in these regions are excluded during adaptation, thereby enhancing the robustness of the model.
Overall, our proposed TTVD is constructed progressively, transitioning from standard VD to CIVD and CIPD, as summarized in Figure 3. At besting-time, we infer and adapt the model accordingly by CIPD (Algorithm in Appendix H using Equation
4 EXPERIMENTS
In this section, present comprehensive evaluation of our method, benchmarking it against other approaches using the peer-reviewed, open-source toolkit TTAB (Zhao et al. 2023), standardized codebase designed ensure fair comparisons across methods.
7

---

Published as a conference paper at ICLR 2025
4.1 EXPERIMENT SETUP
Dataset, CIFAR-1O-C, CIFAR-100-C, and ImageNet-C (Hendrycks & Dietterich/ 2019) are bench- mark datasets designed assess model robustness in the presence of various corruptions and shift. CIFAR-10-C and CIFAR-100- 100-C are corrupted versions of the original CIFAR-10 and CIFAR-100 datasets, where each image has been subjected to 15 different types of common cornuptions such as noise, blur, and weather distortions, with five levels of severity. ImageNet-C applies similar cor- ruptions the large-scale ImageNet dataset, providing a higher-resolution challenge for models. ImageNet-R Crangeeet-Reniitione (Hendrycks et al.) 2021 consists of non-photorealistic rendi- tions of ImageNet classes, such as paintings, cartoons, and sculptures, testing a model's ability to generalize beyond traditional photographic imagery. These datasets allow us to comprehensively assess the robustness of our method under a range of real-world distortions and domain shifts.
Compared Methods. We include the four groups of state-of-the-an methods for the experiments listed below, and their extended introduction are given in Appendix
Neighbor-based methods: (I) T3A (Iwasawa & Matsuo 2021). (II) TAST (Jang et al. 2022
Repurposed domain adaptation methods: (I) Adapt
(Schneider et al. 2020). (II) SHOT (Liagg
ct al. 2020).
Self- methods: TTT (Sun et al. 2020).
Entropy-based methods: (I) TENT (Wang al. 2021 (II) NOTE (Gong et al. 2022). (III) Con-
jugate_PL_ (Goyal et al.] 2022). (IV) SAR (Niu et al. (023).
Implementation Details. We adhere the standard settings given in TTAB for faimess compar- ison. Specifically, generic hyperparameters are grid-searched for the best combination, following guidelines in TTA. Method-specific hyperparameters for each TTA algorithm are selected according to their original experimental setups. Results are reported using the optimal configuration for each method. For TTVD, we trained ResNet-26 for CIFAR-IO-C and CIFAR- and ResNet-50 for ImageNet-C and ImageNet-R, following the official recipe from the torchvision library, using label augmentation (Lee et al. 2020). We use the full training of CIFAR- 10, CIFAR- 100 to compute the class means for Voronoi sites and 10% of ImageNet for similar calculation.
Evaluation Metries. Two metrics are used report the performance: classification error and ex- pected calibration error (ECH) on online test samples. ECE measures the trustworthiness of the model's s confidence its predictions, which is crucial in real-world applications.
4.2 EXPERIMENT RESULTS
Overall Performance Comparison. TTVD demonstrates the best overall performance across mul- tiple datasets. Even under rigid grid-search tuning, our method consistently achieves the lowest classification error and ECE, reducing classification errors by 0.8%, 0.7%, 1.6%, 0.7% on the four datasets, respectively, and ECE by 3.4%, 1.8%, 4.1 1% and 4.3%, demonstrating its trustworthiness.
Effect of Components in TTVD. We ablate our methods by gradually downgrading CIPD to the very basic VD. From Table 2 the performance of VD already surpasses that of other neighbor- based methods. When generalizing VD to CIVD, we observe significant improvement of 5.7% overall for all corruption types. across all corruption types. To investigate the reason behind this, we conducted a sample-level analysis in Appendix(A.] A.I] which demonstrates that the multi-influence structure of CIVD enhances its robustness. Finally. CIPD, with its flexible boundaries and noise filtering mechanisms, further improves upon CIVD by an additional 2.2%, showcasing its superior adaptability.
'The subscripted values represent comparisons made under the oracle model selection setting from TTAB. These values may not reflect real-world performance, as they assume access to ground truth test labels to select optimal models during test time- a condition rarely available in practical scenarios. Additionally. it has been shown from TTAB that, in these results may indicate optimal performance in controlled environments, they do accurately represent how the model would perform real-world, lahel-free settings.
cases, this approach can lead to overlitting to online batches. While
'The experimental settings of TTAB are followed to omit the values for TTT on the ImageNet dataset. This omission aligns with the TTAB guidelines for fair comparison across methods.
8

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of State-of-the-art Methods Regarding Error and Expected Calibration Error The Top Optimal Results are Highlighted in Bold Metrics are Reported Using Level-5
Corruption for CIFAR-C and ImageNet-C, Averaged over 15 Corruption Types. Detailed Results
for Each Corruption Type are Provided in Appendix B
CIFAR 10-C(())
CIFAR 100- (00-C(%)
ImageNer- C(%)
ImageNet-
T3A Iwasawa Matsuo 2021
40.3
19.5
67.6
21.1
83.1
26.3
79.4
20.5
Dang et al. 2022
39.6
40.5
69.8
29.2
74.8
25.1
78.8
21.1
BN AdaptSShnnidec et al.
2020
27.5
18.1
56.6
18.5
72.3
32.8
68.9
30.9
Liang et al. 2020
21.9
16.4
49.8,168)
18.5
63.4(624)
36.4
68.6
31.2
TTT
Sun
2020
21.3
15.2
53.4,51.9
20.2
TENT Wang al.
24.0p1.
16.9
53.5,40.9
18.3
62. 62.7(119)
38.7
68.3
31.4
POTE(Goog al. 2022
28.6124.0
21.5
58.5
23.5
65.7
34.1
68.2
31.7
Conjugale PL. Goyal
2022
24.0g229)
16.9
53.5/51.0)
18.3
63. (62.2)
38.4
68.7
31.2
SAR(Niu et al., 2025
24.2
16.9
53.7
18.1
61.4(59.1)
38.4
68.5
31.3
(Our)
20.5
11.8
44.1
17.0
59.8
21.0
67.5
16.8
Table 2: Ablation Study Using Different Geometric Structures CIFAR-1O-C Across Various Comupttion Types Regarding Error (%
Noise
Blur
Weather
Digital distortion
gau
sho
imp
def
gla
mot
200
5n0
fro
bri
con
ela
fog
pix
jP8
Avg.
37.5
34.5
43.8
19.5
42.9
25.6
25.6
15.0
20.0
30.1
23.3
27.3
CIVD
30.0
27.0
35.9
14.8
36.2
19.7
16.0
21.5
20.0
11.6
15.9
24.6
17.8
21.1
27.9
22.7
CIPD
27.4
24.6
3288
13.2
36.0
18.1
14.2
19.9
17.5
10.1
13.2
22.6
15.3
18.2
24.6
20.5
Adaptation Curves. As discussed in earlier sections regarding the phenomenon of model over- fitting in TTA, it is imperative to thoroughly investigate the adaptation dynamics as the adapta- tion process unfolds over time. As presented in Figure 4 Tent and SAR do not show signs of overfitting. This may be due to the rigid experimental settings and thorough grid search pro- cess we employed, ensuring optimal hyperparameter selection. However, it can be observed that TTVD consistently outperforms across the four noise throughout the entire sequence of online batches. The model maintains a significant downward trend over the various time steps, suggest- ing that continues learn and adapt effectively, with the potential for further improvements if provided with more data. This highlights TTVD's robustness and resilience against overfitting. In contrast, both TENT and SAR ex- hibit more modest improvements in adaptation, and their performance of- ten stagnates or converges at lower accuracy levels compared to TTVD. Specifically, SAR shows notable limitation in its ability to adapt, par- ticularly in the presence of impulse noise, where it quickly reaches a plateau and ceases improve. Fur- thermore, in the case defocus blur, SAR struggles learn useful patterns in the early stages of adaptation, resulting in poor performance on the initial batches. TENT, while slightly better than SAR in some cases, also demonstrates limitations in adapting to these perturba- tions. The early stagnation of both Tent and SAR may indicate potential overfitting to specific noise conditions or a failure to effectively generalize across different noise types as TTVD does.
Table 3: Comparison to Neighbor- Methods Re- garding Error (%) Four types of Blur Corruption in ImageNet-C.
Defoc
Glass
Motion
Zoom
T3A Iwwawwa Matsuo, 2021
92.2
90.3
90.7
85.2
TAST Tang al. 2022
83.7
92.0
92.3
76.7
AdaNPC et al. 2023
83.1
83.0
72.3
60.6
TTVD
79.5
77.7
68.6
53.2
Comparison to Neighbor-based Methods. We follow the report of an additional nearest neighbor method, AdaNPC (Zhang al. (023). benchmark our method in four types of blur corruption in ImageNet-C (defocus blur, glass blur, motion blur and zoom blur). In Table TTVD consistently outperforms the previous methods, demonstrating superior robustness to blur distortions.

---

Published as a conference paper at ICLR 2025
Gaussian Naise
Shot Noise
Impuise Noise
Defocus Blur
87.5
85
Errot (96
85
85
85.0
80
TTVD
Tent
80
Tent
TTVD
80
Tent
TTVD
82.5
Tent
TTVD
75
80.0
75
250
750
250
500
750
500
750
500
750
Online Batch
Online Batch
Online Batch
Online Batch
Figure 4: Comparison on the Adaptation Curves on different noise perturbations in ImageNet-CC Error (%) calculated over all retrospective test samples. The first four types of perturbations in the dataset are presented above.
How Accurate Should the Class Means Be? TTVD requires of- fline calculation Voronoi sites, which must be performed during the pre-training phase. In our experiments, this calculation took less than 10 minutes on 10% of the ImageNet training set using an NVIDIA-RTX A6000. However, in the new era of large-scale datasets, this process may become more resource-intensive Inter- estingly, TTVD demonstrates high robustness the precision of these Voronoi sites, as shown in Table
Table Robustness to Class Mean Precision Using Differ- ent Proportions of ImageNet Data.
5%
TTVD 59.8
59.8
59.9
Effect of Batch Size and Label Shift. Test-time adaptation often receives small batches every time, and label shift, i.e., Non iid test stream may happen in online adaptation. We tested TTVD with various smaller batch sizes and different level of label shifted data in Appendix B demonstrating its high ability to adapt under challenging scenarios.
CONCLUSION
In this paper, we revisit the Test-Time Adaptation problem from a geometric perspective, formu- lating it using the Voronoi Diagram- -a classical and powerful structure in computational geometry known for its elegant mathematical properties. Building on the foundation of guiding TTA with tra- ditional Voronoi Diagram, we extend the approach to more advanced geometric structures, namely the Eluster-induced Voronoi Diagram and the Power Diagram. These structures offer enhanced flexibility and robustness, making them particularly well-suited for TTA. Our experiments demon- strate the effectiveness of our proposed method, TTVD, across a variety of datascts and scenarios, highlighting its capacity adapt diverse challenges in real-world settings.
REFERENCES
Idan Achituve, Haggai Maron, and Gal Chechik. Self-supervised learning for domain adaptation on point clouds. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pp. 123-133, 2021.
F. Aurenhammer. Power diagrams: Properties, algorithms and applications. SIAM Journal on Computing, 16(1):78-9))) 1987. doi: 1371027/02 U 021 6006
Franz Aurenhammer. Voronoi diagrams survey of fundamental geometric data structure. ACM
Comput. Surv., 23(3) sep 1991. ISSN 0360-0300. doi: 16.11445116883.1166888 URL
Randall Balestriero and Richard G. Baraniuk. Mad max: Affine spline insights into deep learning. Proceedings of the IEEE, 10965):004-777, 2021. doi: 10. 10.10///PO...222.442220000
Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk. The geometry of deep networks: Power diagram subdivision. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2025
Randall Balestriero, Romain Cosentino, and Sarath Shekkizhar. Characterizing large language model geometry solves toxicity detection and generation. arXiv preprint arXi::3112.01648, 2023.
Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu. On clustering induced voronoi dia- grams. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 390-399, 2013. doi: 1011009/FCS.2...3
Danny Z. Chen, Ziyun Huang, Yangwei Liu, and Jinhui Xu. On clustering induced voronoi dia- grams. SIAM Journal on Computing, 1666)1167-17711 2017. doi: 10.1 10.1137/15M10444874, URL
https::/doo www.oo...............oo......... /11./11.111111111 0011//551444000 044874.
Min-Hung Chen, Baopu Li, Yingze Bao, Ghassan AlRegib, and Zsolt Kira. Action segmentation with joint self-supervised temporal domain adaptation. In Proceedings of the IEEF/CVF Confer- ence on Computer Vision and Pattern Recognition (CVPR),June 2020.
Geoffrey French, Michal Mackiewicz, and Mark Fisher. Self-ensembling for visual domain adapta- tion. arXiv preprint arXiv: htt:::706.000000 2017.
Yossi Gandelsman, Yu Sun, Xinlei Chen, and Alexei Efros. Test-time training with masked autoen- coders. Advances in Neural Information Processing Systems, 35:29374-29385, 2022.
Yaroslav Ganin, Bvgeniya Ustinova, Hana Ajakan, Paseal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Domain-adversarial training of neural networks. Journal of machine learning research, 17(59):1-35, 2016.
Taesik Gong, Jongheon Jeong, Taewon Kim, Yewon Kim, Jinwoo Shin, and Sung-Ju Lee. NOTE: Robust continual test-time adaptation against temporal correlation. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2022.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014.
Sachin Goyal, Mingjie Sun, Aditi Raghunanthan, and Zico Kolter. Test-time adaptation via conju- gate pseudo-labels. Advances in Neural Information Processing Systems, 2022.
Moritz Hardt and Yu Sun. Test-time training on nearest neighbors for large language models.
In The Twelfth International Conference on Learning Representations, 2024. URL https:
//openreview. hwtp::/ntttfoouuuuooee http://eee..mmmmmoeec.....obuoa.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. arXiv preprint 1903 2019.
Dan Hendryeks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, al. The many faces of robustness: A criti- cal analysis of out-of-distribttion generalization. Proceedings of the IEEE/CVF international conference computer vision, pp.
2021.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-66 0851, 2020.
Ziyun Huang, Danny Z. Chen, and Jinhui Xu. Influence- voronoi diagrams of clusters. Compu- tational Geometry, 96: 06:101746, 2021a. ISSN 0925-7721. doi: https://oo..rrg///.00006....ooo 2021. 101746. URL http://:www..aaaaaaaa...oo/////a
www.
50925772121000 00000XX
Ziyun Huang, Danny Z Chen, and Jinhui Xu. Influence-basse voronoi diagrams of clusters. Com- putational Geometry, 96: 96:101746, 2021b.

---

Published as a conference paper at ICLR 2025
Ahmed Imtiaz Humayun, Randall Balestriero, Guha Balakrishnan, and Richard G. Baraniuk. Splinecam: Exact visualization and characterization of deep network geometry and decision boundaries. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recog- nition (CVPR), pp. 3789-3798, June 2023.
Yusuke Iwasawa and Yutaka Matsuo. Test-time classifier adjustment module for model- domain generalization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 2427-2440. Curran Associates, Inc., 2021. URL https: http:hhttt///oooteeoo
/tttpp:://rrccee /tttpp:://rrocceedings neu ps cccpppp..pppppp.
pdf
Minguk Jang. Sae- Young Chung, and Hye Won Chung. Test-time adaptation via self- with nearest neighbor information. arXiv preprint arXiv:2207.1079. 2022.
Adrián Javaloy and Isabel Valera. Rotograd: Gradient homogenization in multitask learning. In International Conference on Learning Representations, 2022. URL httpttts///oeeeeiiiee
Junguang Jiang, Baixu Chen, Junwei Pan, Ximei Wang. Dapeng Liu, jienj and Mingsheng Long. Forkmerge: Mitigating negative transfer auxiliary-task learning. In Thirty-seventh Confer- on Neural Information Processing Systems, 2023. URL htttps://cpenrevieyt
Corum?1d=v2ikk111BB0)
Guoliang Kang, Liang Zheng, Yan Yan, and Yi Yang. Deep adversarial attention alignment for unsupervised domain adaptation: the benefit of target expectation maximization. In Proceedings of the European conference on computer vision (ECCV), pp. 401-416, 2018.
Jogendra Nath Kundu, Naveen Venkat, Rahul M V, and R. Venkatesh Babu. Universal source-fres domain adaptation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Hankook Lee, Sung Ju Hwang, and Jinwoo Shin. Self-supervised label augmentation via input trans- formations. In International Conference on Machine Learning, pp- 5714-5724. PMLR, 2020.
Mingxi Lei, Meng Ding, Chunwei Ma, Ziyun Huang, Mingehen Gao, and Jinhui Xu. Unifying domain gap in Federated learning: geometric approach. Neurocomputing, 617:128813, 2025. ISSN 0925-2312. doi: http:///...nneearrrc////////////
128813. URL ht www.
sciencedi wwt.:/cw...sseeeeeeeeee
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C Kot. Domain generalization with adver- sarial feature learning. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5400-5409, 2018
Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation. In International Conference on Machine Learning (ICML), pp. 6028-6039, 2020.
Jian Liang, Dapeng Hu, Yunbo Wang, Ran He, and Jiashi Feng. Source data-absent unsupervised domain adaptation through hypothesis transfer and labeling transfer. IEFE Transactions on Pat- tern Analysis and Machine Intelligence (TPAMI), 2021. In Press.
Yuang Liu, Wei Zhang, and Jun Wang. Source-free domain adaptation for semantic segmentation. In Proceedings of the IEEF/CV Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1215-1224, June 2021a.
Yuejiang Liu, Parth Kothari. Bastien Germain van Delft, Baptiste Bellot-Gurlet Taylor Mordan, and Alexandre Alahi. TTT++: When does self-supervised test-time training fail or thrive? In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021b. URI. fittps://openrvv/ eew net. fatt/forune forum? frmmmiid 86NHK yFDI
Chunwei Ma, Ziyun Huang, Mingehen Gao, and Jinhui Xu. Few-shot learning as cluster-induced voronoi diagrams: A geometric approach, 2022.
12

---

Published as a conference paper at ICLR 2025
Chunwei Ma, Zhanghexuan Ji. Ziyun Huang, Yan Shen, Mingchen Gao, and Jinhui Xu. Pro- gressive voronoi diagram subdivision enables accurate free inaseminceeeetall learning. In The Eleventh International Conference on Learning Representations, 2023. URL https:
//pperevveew net./formm? 202ammm22ddxxXXX_mcccbb...
Martin McBride. pyvoro. 2014.
Norman Mu and Justin Gilmer. Mnist-c: A robustness benchmark for computer vision. arXiv preprint 190.v:9906002333 2019.
Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yaofo Chen, Shijian Zheng, Peilin Zhao, and Mingkui Tan. Efficient test-time model adaptation without forgetting. In The Internetional Conference on Machine Learning, 2022.
Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Zhiquan Wen, Yaofo Chen, Peilin Zhao, and Mingkui Tan. Towards stable test-time adaptation in dynamic wild world. In Internetional Conference on Learning Representations, 2023.
Fei Pan, Inkyu Shin, Francois Rameau, Seokju Lee, and In So Kweon. Unsupervised intra-domain adaptation for semantic segmentation through self-supervision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Ori Press, Ravid Shwartz-Zii -Zia, Yann LeCun, and Matthias Bethge. The entropy enigma: Success and failure of entropy minimization. arXiv preprint arXiv:2405.cm 05012, 2024.
Steffen Schneider, Evgenia Rusak, Luisa Eck, Oliver Bringmann, Wieland Brendel, and Matthias Bethge. Improving robustness against common corruptions by covariate shift adaptation. Ad- vances in neural information processing systems, 33: 115399-1151,, 2020.
Yan Shen, Zhanghexuan Ji, Chunwei Ma, and Mingchen Gao. Continual domain adversarial adap- tation via double-head discriminators. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings The The 27th International Conference on Artificial Intelligence and Statisties, volume 238 of Proceedings of Machine Learning Reseurch, pp. 2584-2592. PMLR, 02-04 May 2024. URL
Andrey Sobolev. pyvoro. https://githinn jowpe/ubwooooooooea--ooeeeoeeeae jora:mm/joojjorrrr//y////oo 2014.
Yu Sun, Xiaolong Wang, Liu Zhuang, John Miller, Moritz Hardt, and Alexei A. Efros. Test-time training with self-supervision for generalization under distribution shifts. In ICML, 2020.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
Hui Tang and Kui Jia. Discriminative adversarial domain adaptation. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5940-5947, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- fion processing systems, 30, 2017.
Georges Voronoi. Nouvelles applications des paramètres continus la théorie des formes quadra- tiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik (Crelles Journal), 1908(134): 198-113))):4124)11 -87, 1908a.
Georges Voronoi. Nouvelles applications des paramètres continus la théorie des formes quadra- tiques. premier mémoire. sur quelques propriétés des formes quadratiques positives parfaites. Journal für die reine und angewandte Mathematik (Crelles Journal), 1908(133):97-102 1908b.
Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. International Conference on Learning Repre- sentations, 2021.
13

---

Published as a conference paper at ICLR 2025
Qin Wang, Olga Fink, Luc Van Gool, and Dengxin Dai. Continual test-time domain adaptation. In Proceedings of Conference on Computer Vision and Patter Recognition, 2022.
Zichao Wang, Randall Balestriero, and Richard Baraniuk. A MAX-AFFINE SPLINE PERSPEC- In International Conference on Learning Rep- resentations, 2019. URL https: / net (t-rJum 12AqF))
OF RECURRENT
Shiqi Yang, Joost van de Weijer, Luis Herranz, Shangling Jui, et al. Exploiting the intrinsic neigh- borhood structure for source-free domain adaptation. Advances neural information processing systems, 34:29393-29405, 2021.
Shiqi Yang, Yaxing Wang, Joost de Weijer, Luis Herranz, Shangling Jui, and Jian Yang. Trust your good friends: Source-free domain adaptation by reciprocal neighborhood clustering. IEEE Transactions Pattern Analysis and Machine Intelligence,
2023. doi:
N0.1109/TPAMM..233333311
Haoran You, Randall Balestriero, Zhihan Lu, Yutong Kou, Huihong Shi, Shunyao Zhang, Shang Wu, Yingyan Lin, and Richard Baraniuk. Max-affine spline insights into deep network prun- ing. Transactions on Machine Learning Research, 2022. ISSN 2835-8856. URL https:
7 wwtrrviiww..et/oouummeeeeeee
Sergey Zagoruyko and Nikos Komodakis. 1605.0160,.,7 2016.
Wide residual networks.
arXiv preprint
M. Zhang, S. Levine, and C. Finn. MEMO: Test time robustness via adaptation and augmentation. 2021.
Yifan Zhang, Xue Wang, Kexin Jin, Kun Yuan, Zhang Zhang, Liang Wang, Rong Jin, and Tie- niu Tan. AdaNPC: Exploring non-parametric classifier for test-time adaptation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scar- lett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 41647-41676. PMLR, 23-29 Jul 2023. URL mlr www.m..r.rrrree...mmmmmmmmmmm..e press v202 2hang html
htttps://proceed.neg
Hao Zhao, Yuejiang Liu, Alexandre Alahi, and Tao Lin. On pitfalls of test-time adaptation. In International Conference on Machine Learning (ICML), 2023.
A APPENDIX
A.1 SAMPLE ANALYSIS
In Section experimental results indicate that CIVD contributes the most to the improvement. To understand the reason behind this, we investigate how misclassified samples are corrected after CIVD is employed. We arbitrarily inspect three examples from the "bike", "bus", and "clock" class in Figure 5 Figure 6 and Figure 7, respectively. The distances between the feature points and all Voronoi sites are shown.
The "bike" example originally is misclassified as "lobster" in individual VD. However, the 90-degree rotated image correctly classified. When the CTVD applies the influence function to aggregate the information of all four rotations, the model eventually gets the correct prediction. In the "bus" example, all four rotated images are misclassified as various classes, such as "bowl", "table" "house". However, the distances the ground-true label are all relatively small, CIVD aggregates these distances and makes the correct prediction. The "clock" example shows a similar phenomenon.
In conclusion, this sample analysis reveals that the expanded Voronoi sites and rotated image set contribute the improvement in CIVD.
14

---

Published as a conference paper at ICLR 2025
CIVD prediction: bicycle
20
40
60
80
100
Individual VD prediction: lobster
20
40
60
80
100
Individual VD prediction: bicycle
20
60
80
100
Individual VD prediction: cockroach
20
40
60
80
100
Individual VD prediction: bed
20
40
60
80
100
Figure 5: A misclassified "bike" sample corrected by CIVD. The x-axis denotes the index of classes and y-axis denotes the distance their corresponding Voronoi sites. The green lines indicate the ground-true label and the red lines indicate the predicted label.
15

---

Published as a conference paper at ICLR 2025
CIVD prediction: bus
20
40
60
80
100
Individual VD prediction: bowl
20
40
60
80
100
Individual prediction: bowl
20
60
80
100
Individual VD prediction: table
20
40
60
80
100
Individual VD prediction: house
20
40
60
80
100
Figure 6: A misclassified "bus" sample corrected by CIVD. The x-axis denotes the index of classes and y-axis denotes the distance to their corresponding Voronoi sites. The green lines indicate the ground-true label and the red lines indicate the predicted label.
16

---

Published as a conference paper at ICLR 2025
CIVD prediction: clock
20
40
60
80
100
Individual VD prediction: orange
20
40
60
80
100
Individual VD prediction: orange
20
60
80
Individual VD prediction: camel
20
40
60
80
100
Individual VD prediction: worm
20
40
60
80
100
Figure 7: A misclassified "clock" sample corrected by CIVD. The x-axis denotes the index of classes and y-axis denotes the distance to their corresponding Voronoi sites. The green lines indicate the ground-true label and the red lines indicate the predicted label.
17

---

Published as a conference paper at ICLR 2025
B ADDITIONAL TABLES
Table Comparison Regarding Error (%) on CIFARIO-C Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
def
gla
mot
200
500
fog
con
cla
pix
jpg
Avg.
A3A
65.1
59.5
65.3
37.0
47.5
34.5
33.8
24.7
36.4
34.5
10.1
49.8
25.1
51.6
29,7
40.3
TAST
63.0
58.3
64.5
36.7
46.9
33.6
33.0
24.7
35.6
34.1
10.3
49.8
25.0
49.2
29.6
39.6
BN_Adapt
39.2
37.0
46.0
26.5
35.5
27.5
SHOT
29.3
27.0
34.7
14.2
33.6
16.8
15.0
19.2
21.6
18.1
11.5
16.1
25.4
20.1
26.5
21.9
TTT
25.6
23.0
29.8
13.2
34.6
9.2
26.1
24.0
23.2
21.3
TENT
32.5
29.7
39.2
15.6
36,9
18.1
16.1
21.4
23,0
19.3
12.6
16.9
26.5
22.7
29.9
24.0
NOTE
47.3
40.1
43.9
23.3
38.1
22.6
21.3
19.8
2344
21.3
9.2
30.7
23.8
35.9
27.9
28.6
Conjugate_PL
32.5
29.8
39.2
15.6
36.9
18.0
26.5
22.7
29.9
24.0
SAR
33.3
30.0
39.7
15.7
36.8
18.0
16.1
21.9
22.8
19.4
12.7
17.2
26.4
22.8
30.5
24.2
TTVD
Table 6: Comparison Regarding Error (%) on CIFARI00-C Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
del
gla
moll
200
500
log
bri
con
cla
pix
JPg
Avg.
T3A
89.3
88.4
90.4
64.8
60.7
65.6
43.4
82.3
50.1
82.7
60.6
67.6
TAST
89.2
88.2
90.7
66.3
63.5
63.1
60.0
62.1
64.7
67.9
47.8
82.4
55.0
81.6
64.1
69.8
BN_Adapi
70.3
70.1
69.1
46.5
61.1
48.8
45.9
58.9
55.1
45.1
51.0
53.2
54.2
62.6
56.6
SHOT
58.4
57.6
59.1
41.2
55.2
44.2
41.2
51.9
50.6
48.7
40.2
49.0
48.7
46.2
55.4
49.8
TTT
64.0
63.2
65.5
43.8
57.4
49.6
43.3
54.7
50.5
49.6
38.8
70.0
49.5
45.6
56.4
53.4
TENT
65.1
64.6
65.0
44.1
43.4
55.9
52.4
42.5
49.4
51.6
50.3
59.5
53.5
NOTE
76.1
74.3
74.6
53.8
57.5
50.8
47.6
$2.5
$1.8
56.1
38.8
67.1
48.6
70.5
$7.6
58.5
Conjugate
65.1
SAR
65.3
64.9
65.2
44.2
58.3
47.2
47.6
56.5
54.6
52.4
42.6
48.7
51.7
50.5
59.6
53.7
TTVD
58.2
57.4
63.2
38.8
59.9
45.7
40.2
50.7
49.3
45.7
36.6
42.1
50.6
44.1
54.4
49.1
Table 7: Comparison Regarding Error (%) on ImageNet-C Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
def
gla
mol
200
SB0
fro
fog
bri
cunl
cla
pix
JPS
Avg.
Т3A
89.0
87.7
89.8
91.7
90.9
90.2
84.7
78.7
97.8
70.2
43.2
85.5
94.9
88.6
74.5
83.1
TAST
81.0
79.6
82.0
83.7
92.0
82.3
76.7
70.2
69.4
62.4
34,3
77.6
86.6
89.6
55.3
74.8
BN_Adapt
91.1
88.0
91.6
92.0
90.9
79.1
65.9
64.7
634
47.0
36.7
81.5
62.5
65.9
64.8
73.1
SHOT
75.2
72.0
76.3
86.7
85.0
75.2
61.9
52.7
53.4
29.9
96.2
51.4
47.6
48.4
63.4
TENT
83.4
80.2
83.9
83.5
81.7
68.3
56.3
55.9
55.2
39.1
29.9
69.9
$2.8
50,3
50.6
62.7
NOTE
80.4
77.3
80.7
86.4
85
73.0
42.1
29.8
57.0
66.7
55.0
65.7
Conjugate.PP
84,0
80.7
84.6
83,9
83.4
68.8
56.6
56.5
55.7
39.2
29.9
71.0
52.9
49.5
49.8
63.1
SAR
81.7
82.3
81.9
84.7
82.1
65.1
54.4
54.1
54.0
38.5
29.7
66.8
50.2
47.8
48.3
61.4
TTVD
76.2
75.4
74.4
79.5
77.7
68.6
53.2
55.9
58.7
41.2
30.4
65.0
47.3
42.1
50.8
59.8
18

---

Published as a conference paper at ICLR 2025
Table 8: Comparison Regarding Expected Calibration Error (%) CIFARIO- Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
def
gla
mot
fro
fog
hri
con
cla
pix
iPg
Avg.
T3A
13.3
14.9
13.3
22.9
19.2
20.3
23.4
21.7
19.7
18.9
21.4
21.3
23.5
16.1
21.7
19.5
TAST
18.2
22.9
17.6
43.3
33.7
46.2
46.6
54.4
43.8
45.7
68.1
31.4
54.7
30.7
50.4
40.5
BN Adapt
24.8
23.4
28.8
12.4
26.4
13.5
12.8
17.2
16.5
14.1
10.3
11.2
19.1
17.4
22.8
18.1
SHOT
21.5
19.5
25,4
11.1
24,4
19.4
TTT
18.3
16.5
20.4
10.5
23.8
14.4
12.0
14.4
13.1
10.7
7.7
20.2
17.3
12.0
16.5
15.2
TENT
22.3
20.4
26.8
11.7
25.1
13.0
11.8
15.2
15.9
14.1
9.6
11.9
18.7
16.1
20.6
16.9
NOTE
34,9
31.1
30.8
18.1
28.2
17.6
16.9
14.6
16.9
17.3
7.7
20.4
17.1
31.0
20.5
21.5
Conjugate_Pr.
22.2
20.4
26,9
11.7
25.1
13.0
11.9
15.2
16.0
14.2
9.5
11.9
18.6
16.0
20.5
16.9
SAR
22.4
20.5
26.8
11.8
24.8
12.9
11.9
15.4
16.1
20,9
16.9
TTVD
13.8
12.9
13.4
9.9
15.9
11.4
9.8
11.6
11.1
10.6
8.3
9.3
12.4
11.4
13.4
11.8
Table Comparison Regarding Expected Calibration Error (%) on CIFARI00-C Level-5. Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
def
gla
mot
Z00
fog
con
cla
pix
ipg
Avg.
T3A
7.9
8.6
6.8
21.4
25.8
25.8
27.7
28.6
25
22.6
35.0
10.4
33.0
10.7
26.6
21.1
TAST
9.8
10.8
8.3
32.6
35
35.8
39.0
36.8
34.3
31.0
51.1
16.5
43.9
17.3
34.9
29.2
Adapt
21.2
21.0
21.3
16.2
19.7
17.0
17.7
18.1
20.4
18.5
SHOT
19.7
19.8
20.0
16.2
20.6
17.1
15.5
18.9
18.9
17.3
16.1
21.5
18.6
17.4
19.9
18.5
TENT
20.0
20.5
20.5
16.3
19.5
16.8
15.1
19.5
18.4
17.5
16.0
18.7
17.9
17.3
19.8
18.3
NOTE
32.1
31.3
29.8
20.4
21.6
19.0
18.8
20.8
20.9
21.5
16.1
28.9
18.4
32.7
20.6
23.5
Conjugate_PL
20.0
20.5
20.5
16.3
19.5
16.8
19.5
18.4
17.5
16.0
17.3
19.9
18.3
SAR
20.2
20.3
20.6
16.2
19.9
16.6
15.4
19.7
18.1
17.4
16.0
16.8
17.9
17.1
19.5
18.1
TIVD
12.2
12.6
Table 10: Comparison Regarding Expected Calibration Error (%) ImageNet-CC Level-5.
Noise
Blur
Weather
Digital distortion
gau
sho
imp
del
gla
mmol
SIO
fro
fog
hri
con
cla
pix
jPg
Avg.
T3A
20.4
21.7
19.6
17.7
9.0
19.2
24.7
30.7
31.6
39.2
66.2
23.9
14.5
11.3
45.4
26.3
TAST
18.9
20.3
17.9
16.3
17.6
23.2
37.5
65.6
22.3
13.3
10.3
44.6
25.1
BN Adapt
14.1
17.2
13.6
13.2
14.3
26.0
39.3
40.4
41.7
58.2
68.4
23.7
42.6
39,2
40.4
32.8
SHOT
TENT
17.9
21.8
17.9
18.1
20.5
33.2
44.8
45.4
46.2
61.5
70.1
31.0
48.3
51.9
51.3
38.7
NOTE
19.4
22.6
19.2
13.5
14.5
26.9
57.7
69.9
22.2
42.8
33.1
44.8
34.1
Conjugate
17.1
20.4
16.8
17.1
20.6
34.0
45.0
45.1
45.8
61.6
70.3
28.6
49.8
53.0
51.6
38.4
SAR
18.1
17.6
18.0
15.2
17.8
34.7
45.4
45.8
45.8
61.3
70.1
33.1
49.6
52.0
51.5
38.4
TTVD
10.4
11.0
28.5
26.1
19

---

Published as a conference paper at ICLR 2025
Table 11: Comparison Regarding Error (%) on ImageNet-C Level-5 with Various Smaller Batch Size.
Noise
Blur
Weather
Digital distortion
gau
imp
def
gla
Fog
con
pix
JPg
Avg.
Batch-Size-32
T3A
79.5
78.2
80.3
82.2
90.9
80.7
75.2
69.2
68.3
641.7
33.8
76.0
85.3
88.7
54.5
73.6
BNaAdapt
86.2
83.4
86.9
87.2
86.4
75.1
60.8
43.1
32.9
77.8
59.0
62.2
61.0
68.2
SHOT
75.1
72.0
76.0
91.5
87.5
77.6
63.3
54.3
55.4
40.1
31.2
98.8
53.2
50.1
50.7
65.1
TENT
81.4
79.0
79.5
82.1
81.3
66.9
56.2
54.5
54.1
39.1
30.8
70.0
52.1
48.6
48.9
61.6
NOTE
82.8
79.8
83.5
86.0
84.9
72.6
59.2
58.3
56.6
41.2
30,0
76.0
56.1
62.6
56.4
65.7
Conjugate_PP
82.0
78.7
81.1
81.5
81.2
65.0
55.0
53.6
54.0
38.6
30.7
72.9
50.1
46.5
47.8
61.2
SAR
89.4
79.5
78.0
85.6
79.5
67.2
55.0
67.5
50.8
48.3
51.4
61.9
TTVD
80.7
76.1
73.8
79.5
78.
67.3
52.2
54.6
59.0
40.6
30.6
63.1
47.7
41.2
49.3
59.6
Minch-Size-18
78.2
90.9
88.6
BN RN_Adapt
87.7
85.0
88.0
88.5
88.0
77.7
66.0
63.
61.7
46.
35.9
80.0
62.5
65.3
64.4
70.7
SHOT
77.7
74.7
78.2
95.6
91.1
85.9
69.3
57.4
43.3
34.5
99.4
57.5
53.4
54.6
68.7
TENT
85.1
80.0
79.4
83.6
84.5
68.7
60.6
54,9
56.9
41.4
33.7
76.3
55.0
51.3
54.0
64.4
NOTE
84.0
80.8
84.5
85.8
84.8
72.5
59.0
58.3
56.7
40.6
30.0
75.3
55.7
60.4
57.0
65.7
Conjugate.PL
81.2
79.5
78.5
82.7
79.9
66.4
33.2
52.8
48.3
52.8
62.3
SAR
81.8
88.1
83.6
93.0
86.6
69.7
$8.4
53.7
54.4
40.3
33.2
77.4
53.3
48.9
52.5
63.0
TTVD
Batch Size 8
T3A
79.5
78.2
80.3
82.2
90.9
80.8
75.2
69.2
68.3
60.7
33.7
76.0
85.4
88.7
54.5
73.6
BN_Adapt
89.8
87.7
90.5
71.8
70.0
SHOT
83.8
81.5
84.2
98.2
96.2
90.8
77.7
64.1
63.6
52.8
42.2
99.6
68.5
63.4
62.5
75.3
TENT
97.8
96.6
86.7
95.8
91.1
86.6
75.
64.8
69.7
48.0
41.6
94.4
69.6
61.6
68.9
76.6
NOTE
84.6
81.4
85.2
85.7
84.6
72.4
58.9
58.3
56.9
40.3
74.7
55.5
59.3
57.1
65.7
Conjugate.PL.
87.7
80.0
79.2
86.9
84.1
72.7
65.8
58.9
59.1
47.1
39.5
81.1
59.3
53.4
58.2
67.7
SAR
92.5
90.5
92.4
80.2
77.3
56.7
57.4
70.6
TTVD
78.2
75.9
76.3
84.0
83.2
80.0
58.3
59.5
62.1
45.6
35.6
75.8
51.8
46.8
54.5
64.5
Table 12: Comparison Regarding Error on ImageNet-C Level-5 with Non-i.i.d test stream, Gener- ated by Dirichlet Distribution with Parameter a. Lower Value of a Indicates Worse Label Shift.
Noise sho
Blur
Weather fog
Digital distortion cla
gau
imp
def
gla
mot
ZOO
SBO
fro
bri
con
pix
jpg
Avg.
T3A
79.6
78.3
80.3
82.1
90.8
80.6
75.2
68.3
33.7
75.9
85.3
88.6
54.6
73.5
BN Adapt
85.7
82.5
86.4
86.5
85.7
73.8
60.8
59.6
58.1
41.8
31.5
76.4
57.3
60.6
59.6
67.1
SHOT
75.0
71.9
TENT
81.7
78.1
81.8
82.1
81.4
66.7
55.1
54.3
54.3
38.6
29.5
68.1
51.8
47.9
51.3
61.5
NOTE
80.5
77.4
80.9
86.6
85.4
72.6
60.0
58.4
56.1
42.2
29.6
78.2
56.8
66.6
54.7
65.7
Conjugate
83.0
79.0
83.2
83.4
81.1
66.7
54.6
54,8
54.1
38.3
29.6
71.0
51.0
47.2
51.6
61.9
SAR
86.0
76.6
80.1
88.5
83.6
66.2
55.0
54.6
54.0
38.4
29.6
68.4
50.8
49.7
51.2
62.2
TIVD
77.8
75.0
74.3
65.7
50.8
59.8
0.1
T3A
79.7
78.2
80.3
82.1
90.9
80.8
75.1
69.2
68.4
60.9
33.8
76.0
85.2
88.7
54.5
73.6
Adapt
86.4
42.1
60.7
59.7
SHOT
76.0
72.4
77.2
88.0
85.4
76.7
62.4
53.7
54.5
39.6
30.6
98.1
52.8
47.9
49.8
64.3
TENT
82.3
78.4
82.3
82.5
81.6
67.2
55.7
55.2
54.2
38.9
30.4
70.0
52.4
48.8
48.9
61.9
NOTE
80.6
77.5
80.8
86.5
85.5
72.8
59.9
58.4
56.2
42.4
29.9
78.2
56.8
66.7
54.9
65.8
Conjugate_Pr.
82.6
79.4
83.2
82.8
82.4
67.0
55.4
55.1
54.7
38.5
30.1
70.9
50.8
47.5
48.8
62.0
SAR
85.9
78.6
81.5
86.5
83.0
66.6
55.5
54.7
39.1
68.8
52.6
48.3
49.2
62.3
TTVD
77.2
75.1
74.2
79.4
77.1
68.7
53.1
56.5
58.8
41.8
30.8
66.8
47.6
42.6
$1.1
60.1
a = 0.01
T3A
79.5
78.2
80.2
82.0
80.6
75.9
85.1
88.5
$4.6
73.5
BN BN_Adapt
88.1
85.5
88.5
89.0
88.6
79.3
68.6
66.6
65.4
$1.8
42.9
80.4
65.5
69.0
67.7
73.1
SHOT
82.7
79.9
83.2
90.5
98.5
63.9
65.3
74,5
TENT
85.1
83.3
85.8
86.3
86.1
75.1
65.9
63.3
62.9
50.1
42.6
76.4
62.4
60.2
60.1
69.7
NOTE
80.6
77.6
80.9
86.8
85.5
72.8
59.8
58.5
56.4
42.8
29.7
78.1
56.8
66.7
55.2
65.9
Conjugate.PL
86.2
83.6
86.3
86.5
86.4
76.0
42.1
76.0
61.8
59.4
62.1
69.8
SAR
89.6
83.8
85.2
91.2
85.8
75.6
65.3
63.0
62.2
49.3
41.5
76.1
61.7
59,5
59.2
69.9
TTVD
80.6
20

---

Published as a conference paper at ICLR 2025
C DEMONSTRATIVE ILLUSTRATION OF MNIST-C DATASET IN R²
Figure I aims to illustrate how our method partitions the space for the MNIST-C (Mu & Gilmer 2019) dataset. We use the clean MNIST dataset to train ResNet26 backbone, followed by linear layer with output dimension of 2 for ease of visualizing realistic Voronoi Diagrams in R². In the augmented Voronoi Diagram, self-supervision is employed to expand Voronoi sites, with feature means calculated as the locations of sites. We follow the same training recipe and hyperparameter settings as those for CIFAR-10-C. The positions of vertices in the boundaries are calculated us- ing pyvoro (Sobolev, 2014), and cells are plotted using generativepy (MeBride) 2014). The figure demonstrates that feature points are more distinctly separated in the augmented Voronoi Diagram, highlighting its superior adaptation ability. By leveraging saff-superviiion, it refines decision bound- aries, leading to improved feature alignment and classification accuracy.
D HYPERPARAMETER SETTINGS IN THE EXPERIMENT
We follow the TTAB codebase to grid search the learning rate from (0.005, 0.001, 0.00055) for CIFAR dataset and {0.001, 0.0005, 0.0001) for ImageNet dataset. We set 7 -0.8 to scale and duce the influence of distant Voronoi sites. We use T = 1 as the standard temperature for the softmax function. For model pretraining, we follow the recipe of ResNet55- ResNeet50-Wiights LMAGENETIK-VI from the torchvision library to train the feature extractor. The batch size is set to 64, aligning to previous studies for fair comparison. can be observed from Table B that TTVD is robust the choice of learning rates.
Learning Rate
CIFAR-10-C (%)
CIFAR-100-C (%)
ImageNet-C (%)
0.005
27.4
57.8
0.001
27.1
58.2
76.0
0,0005
26.9
58.1
76.2
0.0001
76.2
Table 13: Learning Rate vs. Accuracy for CIFAR-10, CIFAR-100, and ImageNet Datasets.
E EXTENDED INTRODUCTION TO VORONOI DIAGRAM
Voronoi diagrams are a fundamental tool in computational geometry that partition a given space into regions. The origins of Voronoi diagrams can be traced back to 1644, when philosopher René Descartes first considered similar ideas. However, they are named after Russian mathematician Georgy Voronoi, who formally defined and studied them in 1908. Voronoi's work (Voronoi 1908a b) extended earlier studies on quadratic forms and lattice structures, laying the mathematical ground- work for partitioning spaces into convex regions, termed Voronoi cells. In Voronoi diagram, space is divided into regions such that each region contains all points closer to a given site, or point, than to any other site.
Over the years, Voronoi diagrams have been used to solve problems in various domains due to their ability to model spatial relationships and proximity. In computer science, they are employed in tasks such as nearest neighbor search, mesh generation, and image processing, In physics, Voronoi diagrams help modeling the behavior of particle systems and simulating crystallization processes. In biology, they are used to understand the structure of cells and tissues, where natural divisions often resemble Voronoi partitions. In urban planning, Voronoi diagrams assist in the allocation of resources, such determining optimal locations for services like hospitals or fire stations, where regions of influence need to defined based on proximity.
Their versatility comes from the diagram's intrinsic ability to partition space in efficient and meaningful way, especially when dealing with problems that involve spatial clustering or resource distribution. More recently, in machine learning and artificial intelligence, Voronoi diagrams have been applied to various fields (Ma et al., 2022] 2023) Humayun et al.) 2023 [Bllestriero et al. 2023 You et al. 2022). This geometric approach forms the foundation of our proposed method, TTVD.
21

---

Published as a conference paper at ICLR 2025
which leverages Voronoi diagrams to guide Test-Time Adaptation, ultimately leading to enhanced model performance in dynamically changing environments.
F EXTENDED INTRODUCTION TO COMPARED METHODS
T3A method designed to improve domain generalization by adjusting models during the test phase without requiring backpropagation or changes to the feature extractor. '3A creates pseudo- prototypes from online, unlabeled test data and adjusts the classifier by measuring the distance between test samples and these prototypes. By focusing only the classifier's 's linear layer, T3A is lightweight and efficient, enhancing model performance on unseen domains while avoiding the risks of complex optimization processes.
TAST introduces trainable adaptation modules on top of a frozen feature extractor and generates pseudo-labels for test data using nearest neighbor information. This method improves upon exist- ing TTA techniques by ensuring more robust adaptation in scenarios where test-time domain shifts occur.
BN_ EN_Adapt explores how deep learning models can become more robust to common image cor- ruptions like blur and noise. The authors highlight that in many real-world applications, models can adapt to recurring corruptions using unsupervised methods. By modifying batch normaliza- tion statistics during inference, the paper demonstrates that adapting to corrupted data significantly boosts model robustness, surpassing baseline performance across several benchmarks. This simple yet effective strategy improves the performance of models on corrupted image datasets.
SHOT addresses unsupervised domain adaptation (UDA) without requiring access to source data, a key limitation existing UDA methods. SHOT leverages a pre-trained source model and transfers its knowledge to the target domain by freezing the classifier module (source hypothesis) and adapting the feature extraction module for the target domain using self-supervised learning and information maximization.
TTT involves updating the model at test time using self-super learning task on each individual test sample before making prediction. By using tasks like image rotation prediction as the auxiliary self-supervised task, TTT allows the model to adapt better to the test distribution.
TENT Entropy minimization in the TENT method works by reducing the uncertainty of model's predictions during test-time. This is done by minimizing the entropy, or uncertainty, of the predicted probability distribution. Specifically, TENT updates the model's parameters focusing the affine transformations in normalization layers- based on the gradient of the entropy with respect to these parameters. By iteratively adjusting the model in response test data, TENT improves the model's s confidence its predictions without needing labeled data, resulting in better adaptation to new or corrupted data at test time.
NOTE aims to address challenges in adapting models to non-i.idd test data streams, common in real-world applications like autonomous driving. NOTE includes two components: Instance- Aware Batch Normalization (IABN), which adjusts for out-of-distribution instances, and Prediction- Balanced Reservoir Sampling (PBRS), which simulates i.idd samples from temporally correlated data.
Congugate PL leverages the convex conjugate of the training loss create new TTA loss function. The authors demonstrate that meta-learning the optimal TTA loss consistently recovers a function similar to the softmax-ent entrrpy for classifiers trained with cross-entropy. For models trained with other losses, such as squared loss or PolyLoss, the optimal TTA loss differs. By interpreting this through the lens of convex conjugates, the paper presents a general framework for designing TTA losses.
SAR investigates the challenges of TTA when faced with real-world distribution shifts, such as mixed shifts, small batch sizes, and imbalanced label distributions. The authors find that traditional batch normalization can destabilize TTA, proposing instead the use of group and layer normalization for better stability. To further enhance stability, they introduce sharpness aware and reliable tropy minimization method that removes noisy samples and encourages robust model updates under challenging test scenarios.
22

---

Published as a conference paper at ICLR 2025
AdaNPC constructs memory bank containing features and labels from the source domain, and during inference, it retrieves the nearest neighbors from this memory to predict labels for incoming test samples. This memory is dynamically updated with test features and predictions, making the method effective for handling distribution shifts.
G EXPERIMENTS COMPUTE RESOURCES
All experiments are conducted using GPU NVIDIA RTX A6000.
H ALGORITHMS
Algorithm 2: CIVD Guidance for Test-time Adaptation
Input: Pretrained feature extractor do, set of Voronoi sites C, test stream {x)r
Output: Prediction stream (ūx }.
for each online batch { do
infer: Uk = (3-FF((6 (z. Cx) + ETT;;
// Eqquaiioo Equation
adapt: 0t+1 02 AVLv
end
Algorithm 3: CIPD Guidance for Test-time Adaptation
Input:
Pretrained feature extractor do, set of Voronoi sites C, weights of Voronoi sites test stream {a}+
Output: Prediction stream (ūk) for each online batch {a} do infer: yk (3-F (z, Cx) + ET)
// Equutiio
adapt: 0++1 = az - AV
// Equation
end
23


Reviews:
[{"review_id": "lfjHLYBNDf", "reviewer": "Reviewer_WP62", "summary": "This paper introduces a novel Test-Time Adaptation (TTA) method using Voronoi Diagrams, termed TTVD. The manuscript highlights the integration of cluster-induced Voronoi Diagrams with Power Diagrams, marking their inaugural application in the TTA domain. This combination aims to ensure both flexibility and robustness within the method. Based on the experiments presented, TTVD demonstrates a clear reduction in errors, which is commendable. The writing is clear, the methodology sound, and the experimental outcomes show significant improvement. However, the manuscript does raise concerns about its level of innovation, primarily since it builds upon pre-existing methodologies without introducing novel concepts.", "questions": "1. The parameter gamma seems to be a critical aspect of TTVD; however, its determination and impact on algorithm performance are not thoroughly discussed in the manuscript. Could you provide a detailed explanation on how gamma values are selected and their influence on the method's efficacy?\n2. Regarding the introduction of parameter eps in equation (3) to avoid the log0 issue, the justification seems unclear. The rationale that including eps prevents log0 errors in equation (3) is not compelling, as the log0 problem might not arise even without eps. Could you elaborate on the necessity of eps in this context?\n3. The manuscript assumes the Voronoi sites are pre-determined without detailing the process of converting Xtest into Voronoi sites. For clarity and completeness, please provide a comprehensive description of how Xtest data are transformed into Voronoi sites.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The proposed TTVD method is presented as both simple and rational, making it easily understandable.\n2. The experimental performance of the TTVD method is impressive and showcases the method’s efficacy.", "weaknesses": "1. The main innovation of TTVD appears to be the combination of existing methods (Cluster-induced Voronoi Diagram and Power Diagram), which might not sufficiently fulfill the criteria for substantial novelty.\n2. The manuscript lacks a comprehensive discussion and validation of parameter settings, such as \\gamma, \\eps, and \\tau, which are crucial for the reproducibility and understanding of the research.\n3. The comparative analysis primarily focuses on methods proposed up to and including 2023. Given the rapid advancements in the field, incorporating more recent methodologies (from 2024) could provide a more current understanding of TTVD's positioning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rep79WWNlS", "reviewer": "Reviewer_ET99", "summary": "This paper uses a combination of different variants of Voronoi Diagrams in test-time adaptation. The proposed method combines original Voronoi Diagram, Cluster-induced Voronoi Diagram, and Power Diagram. The proposed method outperforms a collection of relevant baselines under 4 benchmarking datasets.", "questions": "- For the Voronoi Diagram method in Section 3.1, Is it true that the Voronoi sites won’t be updated once initialized? Since in Algorithm 1, it is not adapted. \n- How to get the soft prediction based on $F$ in formula (4) and (6)? How three diagrams are combined? \n- What is the purpose of Lemma 3.1? Is it how the $v_k$s are initialized?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed method is novel, seems to be the first working applying Voronoi Diagram in test-time adaptation, although there are works (e.g. T3A, AdaNPC) share similar intuitions. \n- The author choose very appropriate baselines: all of them are highly relevant and shares similarities to the proposed method. The proposed method has strong performance.", "weaknesses": "- The algorithm part seems unfinished and lacks many details. For example, the paper only include how to compute the soft prediction $\\hat{y}$ for VD, but not for CIVD and PD. Also, it is not introduced how these three components are combined and whether there are additional hyper parameters or flexibilities. \n- It seems like this paper changes the way of doing inference (from simple linear layer to a combination of three types of Voronoi Diagrams). However, the TTA process is still just entropy minimization, like a simpler version of SHOT. Given this similarity, it is highly unsure why the proposed method can solve the challenges in introduction, and how. \n- [Minor] The format of references may need to be updated. There are many places where the author use \\cite, while it should be \\citep. Please correct it in the next version.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TRCpuC12hn", "reviewer": "Reviewer_rD6K", "summary": "The paper targets the challenge of test-time adaptation (TTA) in deep learning models. The authors propose a framework, TTVD (Test-Time adjustment by Voronoi Diagram guidance), which leverages the geometric properties of Voronoi Diagrams to adapt models online during inference. The paper introduces two key geometric structures: Cluster-induced Voronoi Diagram (CIVD) and Power Diagram (PD), to enhance the robustness and adaptability of models facing distributional shifts. Extensive experiments on benchmark datasets like CIFAR-10-C, CIFAR-100-C, ImageNet-C, and ImageNet-R demonstrate the effectiveness of TTVD against state-of-the-art methods.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper offers a fresh perspective on TTA by employing Voronoi Diagrams, which is a significant departure from traditional approaches and shows promise in handling distributional shifts.\n2. The authors provide a rigorous experimental evaluation, demonstrating TTVD's superiority over existing methods on multiple benchmark datasets, which strengthens the credibility of their approach.\n3. Leveraging Voronoi Diagrams for TTA enhances model interpretability, allowing for clearer visualizations and understanding of partition boundaries, which is a valuable asset in deep learning.", "weaknesses": "1. While the paper discusses the benefits of TTVD, it lacks a detailed discussion on the computational overhead introduced by the geometric structures, which could be a concern for real-time applications.\n2. While experimental results are promising, it would be valuable to see a comparison with theoretical bounds or guarantees, if available, to understand the limits of TTVD.\n3. Some sections, particularly the methodology, could benefit from more detailed explanations or pseudo-code to aid reproducibility.\n4. The performance of geometric structures like CIVD and PD may be sensitive to hyperparameters. The paper could provide more insights into hyperparameter tuning and the robustness of these parameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8mnrs7FkqF", "reviewer": "Reviewer_wGB6", "summary": "This paper presents the Test-Time adjustment by Voronoi Diagram (TTVD) framework by leveraging geometric principles, particularly the Voronoi Diagram (VD) and its extensions: the Cluster-induced Voronoi Diagram (CIVD) and the Power Diagram (PD). TTVD addresses the limitations of current test-time methods by using these geometric structures to improve feature alignment and sample filtering. CIVD enhances robustness by considering clusters rather than individual prototypes, while PD allows flexible boundaries to better handle noisy samples near decision boundaries. The proposed TTVD demonstrates substantial improvements over state-of-the-art TTA methods on several corrupted datasets, showing its effectiveness in real-world distribution shift scenarios.", "questions": "The reviewer may have limited familiarity with the Voronoi Diagram, which could have led to some misunderstandings. The authors are encouraged to provide additional explanations during the rebuttal to clarify above points, especially the contributions of the paper and the assumptions between TTT and TTA.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- By introducing geometric frameworks like VD, CIVD, and PD, TTVD leverages computational geometry to improve the alignment of test-time features with training distributions. This approach provides a mathematically grounded and visually interpretable solution to feature adaptation in TTA.\n- TTVD shows consistent improvements over existing methods across multiple datasets, reducing classification error rates and enhancing model calibration as indicated by lower Expected Calibration Error (ECE) scores. The inclusion of diverse corruption types in the evaluation (e.g., noise, blur, and weather-based distortions) demonstrates the framework’s adaptability to real-world conditions.", "weaknesses": "- Both CIVD and PD are well-established geometric structures, raising questions about the novelty of TTVD’s core contributions. The first two contributions mainly apply these established methods to the TTA setting, which may limit the originality of the approach.\n- The distinction between “test-time training” (TTT) and “test-time adaptation” (TTA) is somewhat blurred. According to the TENT framework, TTA excludes access to source data, while TTT can include self-supervised losses on source data. TTVD’s reliance on pre-computed Voronoi sites calculated during pre-training suggests it should be categorized as TTT rather than TTA. This distinction impacts baseline comparisons, as the current baselines primarily include TTA methods, potentially leading to an unfair performance comparison.\n- The paper claims that TTVD extends VD from a point-to-point structure to a cluster-to-point influence mechanism, but it’s unclear why distances in standard VD (calculated by $\\mu_k$) would not already reflect cluster-to-point relationships. A clearer explanation of this transition’s significance would be beneficial.\n- The method lacks details on integrating VD, CIVD, and PD into a single loss function. Questions remain regarding whether the label y is generated by substituting $d(\\cdot)$ in Equation 3 with $F(\\cdot)$, how the components are balanced, and whether this balance is sensitive to different datasets.\n- The paper lacks computational details on estimating key parameters ($\\mu, C, and~ v$) in the TTVD framework. More clarity on these calculations would enhance understanding of the implementation and reproducibility of TTVD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)