The Probability Simplex is Compatible

We thank the Reviewer for the thoughtful summary they provided about our paper and for highlighting the strengths of our paper, including our novel approach to model compatibility, sound theoretical results, comprehensive coverage, and empirical efficacy as demonstrated in the experiments.

[Impact of compatibility and model performance.]

We thank the Review for the insightful comment. To further clarify, employing M's features alone for both query and gallery setups constitutes what is typically referred to as a self-test, observable in the main diagonal of the compatibility matrix. As correctly pointed out by the Reviewer, the comparisons suggested are already reflected within the main diagonal of the compatibility matrix presented in our study. Specifically, the open-set setups are illustrated in the Fig. 7d, 7e, 7f, as indicated. Unfortunately, to ensure compatibility, some performance trade-offs are inevitable.

[Exploring top-k dimensionality reduction.]

We thank the reviewer for the insightful question. One potential approach to mitigate the memory impact of storing features is through Top-K sparsification [1][2]. In the following table, we present the compatibility metrics for various compression levels achieved using Top-K sparsification in a two-network setting (ResNet18 and ResNet152), pretrained on ImageNet1K and validated on the open-set CIFAR100. It can be observed that as the feature size decreases—corresponding to higher sparsification levels (lower values of K)—compatibility metrics such as $AA$ and $ACA$ tend to slightly decline.

[1] Longfei Zheng, Yingting Liu, Xiaolong Xu, Chaochao Chen, Yuzhou Tang, Lei Wang, and Xiaolong Hu. Fedpse: Personalized sparsification with element-wise aggregation for federated learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3514–3523, 2023.

[2] Longfei Zheng, Yingting Liu, Xiaolong Xu, Chaochao Chen, Yuzhou Tang, Lei Wang, and Xiaolong Hu. Fedpse: Personalized sparsification with element-wise aggregation for federated learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3514–3523, 2023.However, the AC metric remains unaffected, indicating that compatibility between the two models is preserved.

[Infrequent model updates in retrieval systems.]

We thank the Reviewer for highlighting the performance in scenarios with infrequent updates and appreciate their focus on face recognition. In addition to face recognition with infrequent update the applicability of our approach can extend to other areas such as real-time robotics and video surveillance, where rapid updates are essential to adapt to unknown contexts. In such systems, representation updates might occur within seconds or minutes. This rapid adaptability is crucial when a robot sends real-time images to a remote learning server, requiring timely updates based on these images. Such updates ensure that the newly downloaded representation model remains compatible with the features previously extracted and stored in the robot's memory buffer.

We have evaluated the performance of our approach after a single model update in a face recognition setup. This analysis also addresses Reviewer Zp2R's request for face recognition evaluation, and we invite the Reviewer to refer to that response for further details. Our approaches (particularly LSP) obtain comparable performance with BCT when the model is updated once, while outperforming it for multiple step updates.

[Compatibility in self-supervised learning.]

As previously noted in our response to Reviewer Zp2R, we recognize that would be very interesting to address backward compatibility, starting with models learned through self-supervised learning. However, learning compatible representations starting from two generic models, for which no assumptions are made (including those learned through self-supervised methods), typically involves making them compatible by mapping one representation onto the other. To learn this mapping, a specific training set is typically required. When multiple updates are made, a series of mapping transformations accumulate, which must be applied sequentially. This results in an increasingly complex architecture that reduces the computational advantage of feature extraction, as each image must traverse all the mappings. However, the BCT paper does not employ a mapping-based approach. We followed the supervised setting described in the BCT paper, which does not employ a mapping-based approach. Instead, it retrains a new model by leveraging the previous model and classifier within a supervised task in an incremental setting, using this as a surrogate from which to learn the feature representation to perform retrieval.

[Theorem assumptions and conclusion.]

We thank the Reviewer for the precise observations regarding the assumptions underlying the theorem presented in our manuscript. We agree with your understanding, the revised paper now includes clear statements of the assumptions in the main body and outlines the form of the conclusion succinctly. The detailed proof remains in the appendix, as previously structured.

[Improved presentation.]

We thank the Reviewer for the feedback regarding Sections 3.2 and 3.3. We have revised these sections for clarity and restructured the content, ensuring the projection matrix is defined before its use in Equation 2. These changes should improve coherence and understanding. We appreciate the suggestions.

[Fixed minor issues.]

After consideration, we agree that specifying SGD is not crucial in the context of our discussion, as it refers to standard training procedures in deep neural networks. We have omitted this detail to streamline the text. Thank you for pointing this out.

We thank the Reviewer for pointing out the confusion. It was indeed intended to denote L2-norm, not L2-normalization. We apologize for this oversight and for any confusion it may have caused. The text has been corrected to clearly reflect its intended meaning. We thank the Reviewer for their precise feedback.

We thank the Reviewer for highlighting the incorrect terminology used to describe the softmax function on Line 211. We acknowledge that referring to softmax as a projection was inaccurate, as it does not satisfy the mathematical property $\sigma(\sigma(z)) \neq \sigma(z)$. The misunderstanding arose because the softmax outputs sum to 1, positioning them on a hyperplane, which might suggest a projection-like behavior. We have corrected this in the manuscript to ensure precision in our descriptions. We are grateful for the collaboration and appreciate your careful reading and valuable correction.

[Decrease of average distance between vectors. Plot.]

Considering $\cos \alpha$ alone (without the concentration parameters) is equivalent to assuming that deterministic class features follow a von Mises-Fisher (vMF) distribution with infinite concentration around their means. In this ideal scenario, all the images belonging to a specific class can be represented exactly by the same feature, and introducing additional data cannot improve this representation since the features representation is already perfect. However, as defined in BCT, compatibility aims to determine if more data—which leads to less uncertain features—can improve both intra-class and inter-class distances compared to the previous model. Nonetheless, if the features are already perfect, no additional data can further reduce their uncertainty. According to this, the two concentration parameters of the vMF distributions are essential and cannot be omitted, as they fundamentally quantify the relative expressive power between a base and an updated model. In this sense $1 - \cos \alpha$ for different $d$ values can represent the theoretical limit as the number of updates approaches infinity, where infinite data leads to perfect representation. Including this in the plots could clarify how each configuration progresses towards optimal model performance. However, further refinement of this theoretical aspect seems to be required and is being actively explored as part of the ongoing research.

[Additional Explanation about NaN, OOM and x symbols.]

We thank the Reviewer for requesting clarification. The ''NaN'' issue arises from the instability associated with adversarial training, a challenge widely recognized in the literature [1][2][3]. This condition may necessitate hyperparameter tuning or the use of a pretrained network, e.g. similar to the training setting used in the Google Landmark v2 dataset.

Regarding the ''OOM'' value, it denotes a GPU out-of-memory error. This occurs due to the need to instantiate a simplex matrix of size $O(N^2)$, where $N$ is the number of preallocated classes. Regrettably, our current hardware was inadequate to support this demand.

Lastly, the ''$\times$'' designation indicates that the ETF cannot be evaluated on the Google Landmark v2 dataset because the number of classes (81313) exceeds the encoder’s output limit of 2048.

[1] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.

[2] Martin Arjovsky and L´eon Bottou. Towards principled methods for training generative adversarial networks. arXiv preprint arXiv:1701.04862, 2017.

[3] William Fedus, Mihaela Rosca, Balaji Lakshminarayanan, Andrew M Dai, Shakir Mohamed, and Ian Goodfellow. Many paths to equilibrium: Gans do not need to decrease a divergence at every step. arXiv preprint arXiv:1710.08446, 2017.

[Using PSP/LSP features in BCT.]

We thank the Reviewer for suggesting the consideration of PSP and LSP features for baseline approaches involving learning. This suggestion is very interesting and appreciated. After evaluation, we observed that incorporating these features in a scenario with one model update results in a slight improvement. However, there remains an issue in tasks involving five steps where the regularization by BCT does not provide a global configuration of the feature space which remains aligned during training, thus compromising compatibility. Nevertheless, using features derived from softmax outputs and logits of models trained with BCT (BCT with PSP and BCT with LSP, respectively) achieves better performance compared to standard BCT in terms of higher compatibility ($AC$) and comparable accuracy ($AA$) values. We appreciate this valuable input, which has enriched our analysis. This also demonstrates that our approach can be used in conjunction with others, improving their compatibility at the cost of a slight drop in accuracy performance.

[Decrease of average distance between vectors]

We thank the Reviewer for their insights. The Reviewer is correct; in Fig. 5(a), $\alpha = 0$, indicating that reducing the variance of a vMF distribution decreases the average angle between vectors sampled from one distribution and those from another.

The reviewer thanks the authors for their detailed and comprehensive response, addressing the points of confusion, providing additional experimental results, and improving the quality of the paper. A few points are further discussed below:

Impact of compatibility and model performance. Using projected softmax/logits as features (in the self-test setup) results in accuracy degradation. The reviewer acknowledges that a similar concept exists for regularization-based methods such as BCT, where the performance of the new model learned with regularization is worse compared to a freely trained new model. However, this is not the case for all compatibility approaches, such as those using a mapping method like FCT[1]. Additionally, while using projected softmax/logits allows training-free compatibility out of the box, it does not support (partial) backfilling (i.e., if one wants to pay additional cost to gain more accuracy, that would not be possible), as discussed in [2].

Exploring top-k Sparsification dimensionality reduction. Thank you for providing results using Top-k Sparsification as a dimensionality reduction approach. Including these results, along with the additional points mentioned below, should improve the paper’s contribution:

• Elaborate Top-K Sparsification and how it fits into the compatibility setup.
• When possible, compare with baselines using regular features of the same dimension (e.g., for K=256, how does it compare with BCT with 256-dimensional features?).

Summary. This reviewer can summarize the specific contributions as follows and encourages the authors to clarify the pros/cons/limitations in the paper:

• Positives:
  • A new approach to model compatibility that does not require any training.
  • Good empirical results when the model is updated very frequently.
  • Possibility of dimensionality reduction (e.g., using Top-k Sparsification).
• Limitations:
  • Accuracy decline due to using projected softmax/logits instead of regular features.
  • Limited benefits to scenarios with very frequent updates only.
  • Need for dimensionality reduction when the number of classes is large.
  • Infeasibility of backfilling/partial-backfilling when accuracy is prioritized over cost.

Based on the above, this reviewer would be happy to increase the score to 6 after the rebuttal.

[1] Ramanujan, Vivek et al. "Forward compatible training for representation learning." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.

[2] Jaeckle, Florian, et al. "Fastfill: Efficient compatible model update." The Eleventh International Conference on Learning Representations (2023).

We thank the Reviewer for the constructive feedback and for acknowledging our efforts to clarify the points of confusion and improve the paper's quality. We appreciate the Reviewers' positive adjustment of the score.

[Discussion about the Partial Backfilling]

We agree with the Reviewer that mapping-based methods may have a lesser impact on degradation compared to BCT-like approaches. We also acknowledge that, in its current formulation, our proposed method cannot support online-backfilling like Forward Compatible Training, since it does not assume the availability of additional data to learn a forward mapping. However, from a practical perspective, it should be feasible to incorporate a learnable residual mapping from a side-training dataset into our non-trainable approach. This could improve compatibility by introducing minor corrections to our proposed framework. If these corrections are minor, simpler and less expressive forward mapping transformations could be utilized, potentially requiring less data. Further refinement and extensive evaluation of this improvement appear necessary and are currently under active investigation as part of our ongoing research efforts.

Regarding backfilling, our method enables partial backfilling by transforming some features extracted from the base model using our approach, while re-extracting the remaining features with an updated model that is trained independently, potentially elsewhere. This process still achieves time savings in reindexing. According to this, the following table presents the Recall@1 values for LSP and PSP features across different backfill ratios between a gallery extracted with ResNet18 and a query set extracted with ResNet152. The gallery is partially backfilled with representations from ResNet152. This backfilling can be performed asynchronously with the operation of the retrieval system. We employ a naive approach (random selection) to backfill the gallery set. Upon completion of the backfill, the proposed approach achieves the performance of the independently trained model.

[Elaboration of Top-k Sparsification]

In response to the Reviewer’s request for further elaboration on top-$k$ sparsification for dimensionality reduction, it is worth noting that this approach is particularly justified for PSP feature representations. Indeed, top-$k$ selectively ignores components of the softmax output vectors that are minimally activated. The retained $k$ components correspond to classes most similar to the input class. Thus, in an open-set scenario, these components might represent an unseen class, indicated by the top-$k$ classes that show some activation in the softmax output.

From a theoretical perspective, [1] demonstrates that softmax loss yields competitive top-$k$ performance for all values of $k$ simultaneously. This indicates that it preserves the ranking of the probabilities, which can contribute to keep the order of the activated components across different dimensions when they are transformed by our PSP method. Accordingly, top-$k$ sparsification seems to be well-suited for dimensionality reduction by setting all entries of a PSP feature representation vector to zero except for the top-$k$. Although LSP lacks similar theoretical support because logits are not probabilistically normalized, our alignment proof with respect to PSP, and the fact that both share similar hyperspherical geometry, suggests that they might behave similarly.

In the following table, we report results for PSP and LSP, where top-$k$ dimensional reduction has been applied to reduce features to the top-128 dimensions. For BCT and LCE, the feature size is reduced to the same 128 dimensions via a fully-connected layer, facilitating a direct comparison of the two methods under the same feature dimensions. These models were trained on the TinyImageNet200 training set and evaluated on the TinyImageNet200 validation set using Recall@1 at 2, 5, 20, and 50 update steps. Both PSP and LSP show slightly improved compatibility (AC) and accuracy (AA) performance in all cases compared to the results in Tab. 1b of the revised paper, where no dimension reduction was applied. Conversely, all compared methods exhibit a decrease in compatibility and accuracy due to the constrained feature space. Specifically, for BCT and LCE, performance is comparable to that in Tab. 1b of the revised paper during infrequent updates (2 and 5 steps) but declines significantly with more frequent updates.

Although the representation benefits from top-$k$ sparsification for dimensionality reduction, as empirically confirmed (Appendix K), this promising and important aspect merits further investigation in future studies.

[1] Lapin, M., Hein, M., and Schiele, B. "Loss functions for top-$k$ error: Analysis and insights". (CVPR2016)

[Clarification about projection matrices and their formulation.]

We thank the Reviewer for their valuable feedback and for pointing out the need for clearer explanations regarding the projection matrices $\mathbf{P} _ {t,k}$ and $\mathbf{P} _ {k,k}$ used in our paper. We appreciate your careful reading and acknowledge the need for clearer exposition on this aspect.

To clarify, the projection matrices are not learned or trained but are derived analytically as part of our methodology. Specifically, the matrix $\mathbf{P} _ {k,k}$ can be explained through the concept of the centering matrix [marden96]. According to this, our proposed projection matrix can be expressed as:

where $\mathbf{I} _ {C^k}$ is the identity matrix, $C^k$ represents the number of elements, and $\mathbf{J}_{k,k}$ is a matrix entirely composed of ones. The projection $\mathbf{P} _ {t,k}$ can be then defined as:

where where $\mathbf{0} \in \mathbb{R}^{(C^t-C^k) \times C^k}$ with $C^t$ and $C^k$ the number of classes of the updated and base model, respectively. We realize this explanation was not adequately highlighted in the paper, and we have revised the relevant sections to ensure this is clearly presented and easy to locate. We believe that this adjustment will address the raised concerns and clarify the theoretical foundation of the projection matrices.

[Marden96] [John I Marden. Analyzing and modeling rank data. CRC Press, 1996.]

[Clarification about training setting, retrieval and self-supervision]

We thank the Reviewer for the insightful comments regarding the incremental setting discussed in our paper. We followed the standard retrieval-based incremental setting pioneered by BCT [1], which has been widely adopted in subsequent research. To provide further clarification, we emphasize that our approach and its associated theoretical analysis have not deviated from the original formulation presented in [1]. There, classification was used as a surrogate task to learn representations, which were then evaluated in a retrieval setting. In addition, one of our main contributions is discovering how to achieve compatibility in independently trained models (as in Tab. 2), a novel approach not addressed by BCT. This notably differentiates our work from the task incremental setting of BCT and related papers.

We recognize that it would be very interesting to address backward compatibility, starting with models learned through self-supervised learning. However, learning compatible representations starting from two generic models, for which no assumptions are made (including those learned through self-supervised methods), typically involves making them compatible by mapping one representation onto the other (as for example in Meng, Qiang, et al. "Learning compatible embeddings." ICCV2021).

To learn this mapping, a specific training set is typically required. When multiple updates are made, a series of mapping transformations accumulate, which must be applied sequentially. This results in an increasingly complex architecture that reduces the computational advantage of feature extraction, as each image must traverse all the mappings. However, the BCT paper does not employ a mapping-based approach; instead, it retrains a new model by leveraging the previous model and classifier within a supervised task in an incremental setting, using this as a surrogate from which to learn the feature representation to perform retrieval.

[Clarification about compatible metrics and performance.] We thank the Reviewer for the comments on the evaluation metrics used in our manuscript. We appreciate the Reviewer's perspective that metrics such as average compatibility, average accuracy, and average compatibility accuracy might seem complex. We acknowledge this complexity but also want to point out that the detailed results for these metrics, including the impact on performance when new classes are added or the architecture is changed, are indeed inherently included in those metrics and therefore present in our reported data. Specifically, the main diagonals of the compatibility matrices align with the Reviewer's intuition of ``before and after'', as they quantify performance gains from using a learned model to perform retrieval. When both the query and gallery are extracted using the same model, these diagonals directly illustrate how the classification surrogate task contributes to the learned representation's performance. In Appendix H of the revised manuscript, we have included the compatibility matrices for PSP, LSP, and all compared methods to further highlight this, specifically for the 5-step scenario on the CIFAR100 dataset under the extended classes setting.

[Evaluation metrics before and after.]

We thank the Reviewer for the feedback on the evaluation metrics. We would like to clarify that Tables 1 and 2 present retrieval results, not classification outcomes. We acknowledge the need for clearer communication on this aspect, which is more explicitly stated in our revised manuscript.

[ Compatibility with ViT architectures.]

We appreciate the Reviewer's suggestion to compare our results with a broader range of modern architectures. In response to the Reviewer's comment, we have included additional benchmarks in our revised manuscript, encompassing a variety of architectures including the Vision Transformer (ViT). In Appendix J of the revised manuscript, we provide detailed analyses demonstrating that PSP and LSP consistently achieve the highest compatibility scores across various datasets, including ImageNet1k, Cifar100, and Places365.

[ Advantages and accuracy trade-off.]

We thank the reviewer for their feedback on the effectiveness of our method, as demonstrated in Tables 1 and 2. While we acknowledge their observations, it is important to highlight that our method offers significant advantages: it requires no retraining, no prior BCT classifier, no auxiliary loss as in BCT, and neither mappings nor any modifications to the network architecture. Moreover, unlike traditional BCT approaches that rely on transitive properties and may not sustain performance over the long term, our approach maintains its effectiveness, albeit with an increased representation dimension. Thanks to the suggestion of colleague Reviewer EQDT, we have shown that top-k sparse representation can reduce the dimension without significantly compromising performance.

We also wish to highlight that our main contribution includes providing theoretical support for the proposals discussed. We believe this enhances the foundation of our findings.

We thank the Reviewer for recognizing the strengths of our work: specifically the novel approach to backward compatibility without involving the old model, the direct analysis of softmax and logits projections, and the potential of achieving compatibility between models trained independently. Additionally, we would like to emphasize that our proposed approach has theoretical support, further validating its effectiveness.

Thanks for your clarifications.

I already understood and appreciate that this method does not require re-training like BCT when I first read the paper.

However, my biggest concern remains that you have designed metrics that are different from what was used in baselines i.e. before/after (please look at the BCT paper for example). This makes it hard for me to judge the validity of this proposed approach. IIUC, you should be able to extract the same metrics that ALL the baselines used based on your metrics and present to the reviewers here. In fact, if you were to check out say BT2 paper, they have very comprehensive before and after results that present an intuitive report of how well it works e.g., Table 6 in BT2. I wish to see the same thing.

Thanks for the response.

However, I am not sure we are on the same page. I am asking for the same metric used by prior work, BCT, BT2, etc, to be used to compare PSP/LSP against them, i.e., a table where you have PSP, LSP, BCT, Bt2, etc, on different rows and with the before/after just like how the prior work evaluate their work. So what is the baseline here? Is the one mentioned on L416? If so, that's not what I am looking for.

I will keep my score as a result.

TinyImageNet200:

We thank the Reviewer for their clarification and appreciate their patience. We apologize for any confusion. It appears we misunderstood the Reviewer's request for a comparative analysis using the same metrics as those employed in prior works. Incorrectly, we suggested examining the main diagonals of the compatibility matrices of several methods for this comparison.

We now understand that the Reviewer is requesting the standard metrics as reported by the BCT and the BT2 papers, typically presented as $\phi _ {new}/\phi _ {old}$ and $\phi _ {new}/\phi _ {new}$ by BT2, and as $(\phi _ {new}, \phi _ {old})$ and $(\phi _ {new}, \phi _ {new})$ by BCT, respectively referred to as cross-test and self-test. We want to assure the Reviewer that these numbers are already included in our paper, albeit in a different format. Our format choice reflects the paper's focus on frequent updates, which involve multiple old models. Consequently, instead of using subscripts $new$ and $old$, we use indices corresponding to the time steps.

In the BT2 notation, $\phi _ {new}/\phi _ {new}$ corresponds to $\phi _ {2}/\phi _ {2}$, and $\phi _ {old}/\phi _ {old}$ to $\phi _ {1}/\phi _ {1}$. Similarly, for the cross-test, $\phi _ {new}/\phi _ {old}$ corresponds to $\phi _ {2}/\phi _ {1}$. In cases of frequent model updates, metrics such as $\phi _ {3}/\phi _ {3}$ and $\phi _ {4}/\phi _ {4}$ are continuously evaluated. As these evaluations accumulate, a variety of model pairs become available for assessing compatibility. Regardless of the notation used these metric evaluations can systematically organized into what is commonly referred to as a compatibility matrix as:

if a further update model $\phi _ {newer}$ is available, it is possible to consider:

In the general case with multiple model update indexed by their sequential time step:

All of our metric evaluations are organized into compatibility matrices, as above, and are presented in Figures 7, 8, and 9 of the revised paper for various approaches.

Accordingly, to address the Reviewer's comment accurately, we have replicated the results for all the approaches in those Figures in the tables below to match the notation used in BT2. Specifically, the tables compare our methods—PSP and LSP—with other approaches, namely BCT, CoReS, ETF-CE, ETF-DR, LCE, AdvBCT and BT2, across two datasets: CIFAR100 and TinyImageNet200, in this case in a two-step scenario instead of the multistep one we used in the revised paper. All the approaches involves a ResNet18-based model trained on half of the classes available in each dataset, which is then updated to include the entire dataset. During the model update of the baseline approach, no compatible methods (e.g. additional losses, mapping, network architecture changes) are used. For the baseline, features are extracted from the encoder's output. We used BT2 with a feature space of 128, as specified in the original paper, and applied the same settings to BCT and LCE to ensure a fair comparison. The results align with those presented in the revised manuscript and reinforce the reproducibility of our analysis across the requested experimental setups. Slight performance variations in BCT and LCE are due to differences in embedding size compared to the manuscript, adjusted to align with the feature size of BT2.

Please refer to the Response To the Questions (9btr) for the response.

[Clarification about Norm vs Normalization in Eq. 2.]

We thank the Reviewer for the clarification regarding Equation (2) and the definition of the feature representation $\mathbf{h}^k$. We inadvertently made a typo by missing the numerator, which may have misled the Reviewer and made the equation incomplete. We apologize for this oversight. The correct formula is:

$\mathbf{h}^k = \frac{ \mathbf{P} _ {k, k} \ \sigma( \mathbf{z}^k )}{ \| \| \mathbf{P} _ {k, k} \ \sigma(\mathbf{z}^k) \| \|_2}.$

Therefore, to clarify, $\mathbf{h}^t$ is a normalized feature vector, not the result of a norm we inaccurately described as yielding a scalar for distance measurement.

[Code Double Check and Contribution.]

We thank the Reviewer for the careful review and for taking the time to check the code provided in our supplemental materials. We appreciate the Reviewer's efforts in verifying that logits and the probability outputs from the pretrained models are indeed used as feature representations, as described. We again apologize for our oversight which may have misled the Reviewer.

We completely agree with the Reviewer that for well-trained models, the prediction probabilities for the same image should naturally align. Our contribution is to provide a formal proof of this intuition, which not only confirms the phenomenon but also strengthens its theoretical foundation.

[Possible Applications and Advantages.]

We thank the Reviewer for their insightful comments, which indeed seem to align with the framework of compatibility learning, originally defined in [1] to evaluate the compatibility of models trained under different conditions.

This raised issue may resemble the ''Neural Lineage'' problem recently presented at CVPR2024, which involves identifying the parent model from which a well-behaved neural network was fine-tuned. Specifically, neural lineage detection involves predicting from which parent model a child model has been fine-tuned, given a set of potential parent models. If we understand correctly what the Reviewer pointed out, it may share similarities with the ''Neural Lineage''. However, instead of detecting if a model was obtained by fine-tuning from a parent model, in the case of compatible representations, one should determine if the base model was learned using the same training dataset similar to another model. The point raised by the Reviewer is very interesting and merits future research into its implications.

[1] Shen, Y., Xiong, Y., Xia, W., and Soatto, S. (2020). Towards backward-compatible representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 6368-6377).

[Accuracy Gain of the New Model.]

We appreciate this observation. Here, the task of classification is used as a ''surrogate task'' to learn the internal feature representation, which is then employed to represent images for retrieval/search tasks. Since the number of classes in the surrogate classification task varies at each step, the gain in classification accuracy does not directly provide a meaningful measure of how well images are represented. For instance, the first surrogate classification task may involve 5 classes and the subsequent one 20 classes. The first might show higher classification accuracy due to its simplicity, while the second, a more challenging task, might show lower accuracy. However, the features learned from the second task, involving 20 classes, are more expressive for representing images despite the reduced classification accuracy, as they incorporate a greater diversity of data into the representation.

We appreciate the Reviewer's intuition regarding the gains derived from the classifier's surrogate task. If we understand the question correctly, the main diagonals of the compatibility matrices support this intuition. These diagonals quantify the performance gains achieved when a learned model is used for retrieval, as both the query and gallery are extracted with the same model. This directly demonstrates the impact of the surrogate classification task on the learned representation.

To clarify, we have included the compatibility matrices for PSP, LSP, and all compared methods in Appendix H of the revised manuscript, specifically for the 5-step scenario on the CIFAR100 dataset under the extended classes setting.

We thank the Reviewer for their thoughtful feedback and for recognizing the strengths of our work.

Thank you for providing further clarification. Based on your response, I summarize my understanding of your work:

[Clarification about Norm vs Normalization in Eq. 2.] We thank the...

The authors may have misunderstood my first question. If we aim to compute the similarity between vectors $z_1$ and $z_2$, we cannot define a many-to-one mapping:

$\psi: z \mapsto h,$

and then compare $h_1=\psi(z_1)$ and $h_2=\psi(z_2)$ to measure the similarity between $z_1$ and $z_2$.

For example:

$h=\psi(z)=\frac{z}{\\|z\\|}, z_1 = (10000, 0), z_2 = (1, 0)$

It is evident that the features $z_1$ and $z_2$ are distinct. However, after applying the many-to-one mapping, $h_1=\psi(z_1)$and$h_2=\psi(z_2)$ become identical.

[Accuracy Gain of the New Model.] We appreciate this...

So, the primary application appears to be task-specific, specifically for surrogate classification. Am I correct?

Thank you for the detailed clarification. I am still confused about the evaluation metric used in this paper. If the method demonstrates accuracy improvement and focuses on the classification task, why not use Top-1 Accuracy? Conversely, if the method focuses on a retrieval task, why not use metrics such as Precision, Recall, F1-Score, or Mean Average Precision? I am not entirely familiar with this domain (AC, AA, ACA) and therefore defer to the ACs and other reviewers who may have more expertise in this area.

We thank the Reviewer for the follow-up questions and for expressing their thoughts on the evaluation metrics. To clarify:

1. Our study addresses retrieval task in model compatibility. No classification task.
2. Model compatibility requires evaluating retrieval performance (we used Recall@1) across different model versions: the gallery is expressed with model $\phi_1$ while queries with model $\phi_2$.
3. As the number of sequential model updates increases (i.e., $\phi_1$, $\phi_2$, $\phi_3$, ...), so does the number of paired interactions between query and gallery expressed with these models.
4. The AC, AA, and ACA metrics summarize the performance of paired model interactions into three numbers by averaging all interactions, as detailed in Section 4.1.

We acknowledge the inherent complexity of these metrics and appreciate the Reviewer's trust in the expertise of the Area Chair and other Reviewers.

[Clarification of the Projection Matrix Definition is needed due to Complex Analysis.]

We appreciate the Reviewer's comment for clarification on the definition of the projection matrix $\mathbf{P} _ {k,k}$. To provide a more concise explanation, the projection matrix $\mathbf{P} _ {k,k}$ can be succinctly expressed using the concept of the centering matrix \cite{marden1996analyzing}, defined as: $\mathbf{P} _ {k,k} = \mathbf{I} _ {C^k} - \frac{1}{C^k} \mathbf{J} _ {C^k}$ where $\mathbf{I} _ {C^k}$ is the identity matrix, $C^k$ represents the number of classes, and $\mathbf{J}_{C^k}$ is a matrix entirely composed of ones. The centering matrix is typically used to remove the mean, thus centering the data. In our case, it is specifically applied to the vertices of the Probability Simplex $\mathbf{e}_i$ stacked into the identity matrix $\mathbf{I} _ {C^k}$, while the matrix $\frac{1}{C^k} \mathbf{J} _ {C^k}$ subtracts the mean to each vertex $\mathbf{e}_i$.
We have included this clarification in the revised manuscript. We thank the Reviewer for their suggestions, which have improved the readability and understanding of our work and provided us with a different perspective.

[Pseudo-code of Proposed Methods.]

We thank the Reviewer for the constructive suggestion. We agree that this addition will improve the paper. We have appended pseudo code in the revised manuscript in Appendix F.

[Newer Methods Performance.]

Newer Algorithms such as CoReS and ETF-CE may perform worse when the model is updated for few steps because they are designed to enforce a fixed predetermined representation space. They are designed to pre-allocate a large number of future classes to accommodate any further class data expansion. Although ETF-CE is not specifically designed for compatibility, it performs learning through a simplex fixed classifier as in CoReS. In principle, this approach is limited by the number of class prototypes in the classifier, which must be fewer than the encoder's output size. CoReS addresses this issue by adding a linear layer before the classifier to extend this limit. Conversely, BCT operates more adaptively by enforcing classifiers that have been learned in the past and then kept fixed. BCT is based on what the authors term ''transitive compatibility'', which suggests compatibility is a pairwise relationship between models and not a global one as formulated in CoReS and ETF-CE. This pairwise model relationship used in BCT can extend to multiple model updates, but only under the assumption that the transitive property holds. As an example BCT allows the final model, $\phi _ 3$, to be transitively compatible with $\phi _ 1$, even though $\phi _ 1$ is not directly involved in the training of $\phi _ 3$. Therefore, there is a trade-off between these two strategies, depending on whether long-term or short-term compatibility is required.
In light of this basic working principle, the good performance of BCT may be attributed to the fact that neither ETF-CE nor CoReS leverage the previous model. As a final note, in the experiment we used the more computationally intensive variant of BCT that uses ''synthesized classifier weights''. In this variant, the classifier weights for the previous step are partially computed as the mean of the features extracted by the previous model from the images of the novel step. This process leverages the old model to extract features from the new training set, maximizing its utility. In contrast, the standard BCT implementation leads to a substantial performance drop, as demonstrated in the table below. Specifically, the performance metrics AC, AA, and ACA of the standard BCT across models trained for 2, 5, 20, and 50 steps on CIFAR100 are presented, and evaluated using Recall@1 on the CIFAR100 test set. A comparison of these results with the BCT performance in Tab. 1a of the submitted manuscript demonstrates the superior performance of the BCT variant. However, the naive implementation involves significantly less computational effort, as it relies only on the old classifier rather than the entire old model.

[Face Recognition Evaluation.]

We appreciate the reviewer’s comment regarding the applicability of our proposed methods, LSP and PSP, to face recognition datasets. In response to this, we have conducted evaluations of both methods using the CASIA-WebFace dataset [1] and the IJB-C 1:1 verification protocol [2]. Results confirm that our methods consistently achieve the highest performance in scenarios involving multiple model updates, and they perform comparably to BCT when the model is updated once. Importantly, while there is a slight decrease in average accuracy ($AA$), we observe a significant gain in compatibility with BCT as the number of update steps increases.

[1] Dong Yi, Zhen Lei, Shengcai Liao, and Stan Z Li. Learning face representation from scratch. arXiv preprint arXiv:1411.7923, 2014.

[2] Brianna Maze, Jocelyn Adams, James A Duncan, Nathan Kalka, Tim Miller, Charles Otto, Anil K Jain, W Tyler Niggel, Janet Anderson, Jordan Cheney, et al. Iarpa janus benchmark-c: Face dataset and protocol. In 2018 international conference on biometrics (ICB), pp. 158–165. IEEE, 2018.

We thank the Reviewer for their positive comments regarding the comprehensive theoretical analysis in our manuscript and for recognizing our method’s robust performance across a large number of model update steps. We appreciate the insightful feedback. We also thank the Reviewer for the feedback regarding the complexity of the theoretical analysis in our manuscript.

In our responses, we addressed key concerns and provided clarifications to highlight the impact and relevance of our work. We pointed out the balance between achieving backward compatibility and maintaining strong model performance, demonstrating the practical benefits in scenarios like infrequent model updates and discussed the advantages of the frequent ones. To further strengthen our methodology, we explored top-k dimensionality reduction, showing its utility in learning compatible representation, evaluated on face recognition tasks and integrated PSP/LSP features into BCT. We discussed compatibility in self-supervised learning and the theoretical limit as the number of updates approaches infinity, reinforcing the soundness of our approach. To ensure clarity, we improved the presentation of the paper, incorporating pseudo-code of the proposed methods and additional results with Vision Transformer architectures. We also elaborated on the accuracy gains achieved by our new model and addressed theorem assumptions and their implications.

These changes represent a considerable additional effort to address Reviewer concerns, clarify ambiguities, and include numerous model architectures. This effort not only demonstrates the method’s applicability but also confirms its theoretical support for handling more complex datasets and architectures.

Changes include:

• Appendix F: Pseudo-code for PSP/LSP with softmax or logits. Thanks to Reviewer dqbF.
• Appendix H: Compatibility Matrices for CIFAR100. Thanks to Reviewer Zp2R.
• Appendix I: Compatibility Matrices for ImageNet1k pre-trained models: added Places365. Thanks to Reviewer Zp2R.
• Appendix J: ViT Architectures, similar to Appendix I, with external pre-training. Thanks to Reviewer Zp2R.
• Appendix K: Top-K sparsification. Thanks to Reviewer EQDT.
• Section 1: Improved contributions as suggested by Reviewer EQDT.
• Section 3: Listed assumptions and theorem results. Thanks to Reviewer EQDT.
• Section 3: Improved presentation using centering matrix. Thanks to Reviewers dqbF, Zp2R.
• Section 4: Revised the limitations. Thanks to Reviewer EQDT.
• Section 4: Improved explanation about metrics. Thanks to Reviewer Zp2R.

We believe these updates have significantly improved the quality of our paper. We sincerely thank all Reviewers for their constructive feedback and active participation throughout this discussion phase.

In addition to these major changes, we have addressed all minor concerns raised by the Reviewers and actively engaged in the discussion to address their questions. A summary of the responses, pre and post-rebuttal, can be found in the Response Summary and Post Rebuttal Response Summary, respectively.

All changes are highlighted in blue in the revised PDF, which is available through the usual link on OpenReview.