Matryoshka Representation Learning — part 5/5

Cleaned-text code points [62453, 74040). Bibliography omitted here; source.md includes it.

Exact search has a search time complexity of O ⁡ ( d ​ k ​ N ) O(dkN) , and HNSW has a search time complexity of O ⁡ ( d ​ k ​ log ⁡ ( N ) ) O(dk\log(N)) , where N N is the database size, d d is the representation size, and k k is the shortlist length. To examine real-world performance, we tabulated wall clock search time for every query in the ImageNet-1K and ImageNet-4K validation sets over all representation sizes d d in Table 19 for both Exact Search and HNSW32, and ablated wall clock query time over shortlist length k k on the ImageNet-1K validation set in Table 21 . The wall clock time to build the index and the index size is also shown in Table 20 .

## Appendix J Analysis of Model Disagreement

##### Class Trends

Does increasing representation size necessarily help improve classification performance across all classes in ImageNet-1K? We studied this question by examining trends in performance with increasing representation size from d = 8 , … ​ 2048 d={8,...2048} . For MRL {\rm MRL} models, we observed that 244 244 classes showed a monotonic improvement in performance with increasing d d , 177 177 classes first improved but then observed a slight dip (one or two misclassifications per class), 49 49 classes showed a decline first and then an improvement, and the remaining classes did not show a clear trend. When we repeated this experiment with independently trained FF models, we noticed that 950 950 classes did not show a clear trend. This motivated us to leverage the disagreement as well as gradual improvement of accuracy at different representation sizes by training Matryoshka ​ Representations {\rm Matryoshka~Representations} . Figure 12 showcases the progression of relative per-class accuracy distribution compared to the Matryoshka ​ Representation ​ Learning {\rm Matryoshka~Representation~Learning} -2048 dimensional model. This also showed that some instances and classes could benefit from lower-dimensional representations.

##### Discussion of Oracle Accuracy

Based on our observed model disagreements for different representation sizes d d , we defined an optimal oracle accuracy [ 58 ] for MRL {\rm MRL} . We labeled an image as correctly predicted if classification using any representation size was correct. The percentage of total samples of ImageNet-1K that were firstly correctly predicted using each representation size d d is shown in Table 22 . This defined an upper bound on the performance of MRL {\rm MRL} models, as 18.46 % 18.46\% of the ImageNet-1K validation set were incorrectly predicted ∀ d ∈ { 8 , 16 , … , 2048 } \forall d\in\{8,16,\ldots,2048\} . We show the oracle performance on MRL {\rm MRL} models for ImageNet-1K/V2/A/R/Sketch datasets in Table 23 .

In an attempt to derive an optimal routing policy to emulate oracle accuracy, we designed the adaptive classification via cascading method as discussed in Appendix D.1 . This led to an interesting observation on the expected dimensionality for 76.30 % 76.30\% top-1 classification accuracy being just d ∼ 37 d\sim 37 . We leave the design and learning of a more optimal policy for future work.

##### Grad-CAM Examples

We analyzed the nature of model disagreement across representation sizes with MRL {\rm MRL} models with the help of Grad-CAM visualization [ 80 ] . We observed there were certain classes in ImageNet-1K such as "tools", "vegetables" and "meat cutting knife" which were occasionally located around multiple objects and a cluttered environment. In such scenarios, we observed that smaller representation size models would often get confused due to other objects and fail to extract the object of interest which generated the correct label. We also observed a different nature of disagreement arising when the models got confused within the same superclass. For example, ImageNet-1K has multiple "snake" classes, and models often confuse a snake image for an incorrect species of snake.

##### Superclass Performance

We created a 30 superclass subset of the validation set based on wordnet hierarchy (Table 24 ) to quantify the performance of MRL {\rm MRL} model on ImageNet-1K superclasses. Table 25 quantifies the performance with different representation size.

## Appendix K Ablation Studies

### K.1 MRL {\rm MRL} Training Paradigm

##### Matryoshka ​ Representations {\rm Matryoshka~Representations} via Finetuning.

To observe if nesting can be induced in models that were not explicitly trained with nesting from scratch, we loaded a pretrained FF-2048 ResNet50 model and initialized a new MRL {\rm MRL} layer, as defined in Algorithm 2 , Appendix C . We then unfroze different layers of the backbone to observe how much non-linearity in the form of unfrozen conv layers needed to be present to enforce nesting into a pretrained FF model. A description of these layers can be found in the ResNet50 architecture [ 29 ] . All models were finetuned with the FFCV pipeline, with same training configuration as in the end-to-end training aside from changing lr = 0.1 =0.1 and epochs = 10 =10 . We observed that finetuning the linear layer alone was insufficient to learn Matryoshka ​ Representations {\rm Matryoshka~Representations} at lower dimensionalities. Adding more and more non-linear conv+ReLU layers steadily improved classification accuracy of d = 8 d=8 from 5 % 5\% to 60 % 60\% after finetuning, which was only 6 % 6\% less than training MRL {\rm MRL} end-to-end for 40 epochs. This difference was successively less pronounced as we increased dimensionality past d = 64 d=64 , to within 1.5 % 1.5\% for all larger dimensionalities. The full results of this ablation can be seen in Table 26 .

##### Relative Importance.

We performed an ablation of MRL {\rm MRL} over the relative importance, c m c_{m} , of different nesting dimensions m ∈ ℳ m\in\cal{M} , as defined in Sec. 3 . In an attempt to improve performance at lower dimensionalities, we boosted the relative importance c m c_{m} of training loss at lower dimensions as in Eq. 1 with two models, MRL {\rm MRL} -8boost and MRL {\rm MRL} -8+16boost. The MRL {\rm MRL} -8boost model had c m ∈ ℳ = [ 2 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] c_{m\in\cal M}=[2,1,1,1,1,1,1,1,1] and the MRL {\rm MRL} -8+16boost model had c m ∈ ℳ = [ 2 , 1.5 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] c_{m\in\cal M}=[2,1.5,1,1,1,1,1,1,1] . The relative importance list c m ∈ ℳ c_{m\in\cal M} had a 1-to-1 correspondence with nesting dimension set ℳ \mathcal{M} . In Table 27 , we observed that MRL {\rm MRL} -8boost improves top-1 accuracy by 3 % 3\% at d = 8 d=8 , and also improves top-1 accuracy of all representation scales from 16 to 256 over MRL {\rm MRL} , while only hurting the performance at 512 to 2048 representation scales by a maximum of 0.1%. This suggests that the relative importance c m c_{m} can be tuned/set for optimal accuracy for all m ∈ ℳ m\in\mathcal{M} , but we leave this extension for future work.

##### Matryoshka ​ Representations {\rm Matryoshka~Representations} at Arbitrary Granularities.

To train MRL {\rm MRL} , we used nested dimensions at logarithmic granularities ℳ = { 8 , 16 , … , 1024 , 2048 } \mathcal{M}=\{8,16,\ldots,1024,2048\} as detailed in Section 3 . We made this choice for two empirically-driven reasons: a) The accuracy improvement with increasing representation size was more logarithmic than linear (as shown by FF models in Figure 3 ). This indicated that optimizing for granularities increasing in a non-logarithmic fashion would be sub-optimal both for maximum performance and expected efficiency; b) If we have m m arbitrary granularities, the expected cost of the linear classifier to train MRL {\rm MRL} scales as O ⁡ ( L ∗ ( m 2 ) ) O(L*(m^{2})) while logarithmic granularities result in O ⁡ ( L ∗ 2 ​ l ​ o ​ g ​ ( d ) ) O(L*2log(d)) space and compute costs.

To demonstrate this effect, we learned Matryoshka ​ Representations {\rm Matryoshka~Representations} with uniform ( MRL {\rm MRL} -Uniform ) nesting dimensions m ∈ ℳ = { 8,212,416,620,824 , 1028 , 1232 , 1436 , 1640 , 1844 , 2048 } m\in\mathcal{M}=\{8,212,416,620,824,1028,1232,1436,1640,1844,2048\} . We evaluated this model at the standard ( MRL {\rm MRL} -log ) dimensions m ∈ ℳ = { 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , 2048 } m\in\mathcal{M}=\{8,16,32,64,128,256,512,1024,2048\} for ease of comparison to reported numbers using 1-NN accuracy (%). As shown in Table 29 , we observed that while performance interpolated, MRL {\rm MRL} -Uniform suffered at low dimensions as the logarithmic spacing of MRL {\rm MRL} -log resulted in tighter packing of information in these initial dimensions. The higher nesting dimensions of MRL {\rm MRL} -Uniform did not help in significant accuracy improvement due to accuracy saturation, which is often logarithmic in representation size as shown by FF models. Note that the slight improvement at dimensions higher than 512 for MRL {\rm MRL} -Uniform is due to multiple granularities around them compared to just three for MRL {\rm MRL} -log , which are not useful in practice for efficiency.

##### Lower Dimensionality.

We experimented with training MRL {\rm MRL} with smaller nesting dimension than m = 8 m=8 , as shown in Table 29 , with two models: MRL-4 and MRL-6. We found that using lower than 8-dimensions to train MRL {\rm MRL} , i.e. m 0 ∈ { 4 , 6 } m_{0}\in\{4,6\} for MRL-4 and MRL-6 respectively, did not affect the top-1 accuracy of other granularities significantly. However, granularities smaller than 8-dimensions had very low accuracy and were often unusable for deployment along with additional training difficulty. We also observed a small dip in accuracy at higher dimensions which we attribute to the joint loss that now also included the harder optimization of the smallest dimension. Lastly, we hypothesize the dimensionality of 8 is an empirically validated design choice due to the considerable accuracy it provided along with the ease of training.

### K.2 Retrieval

##### Adaptive Retrieval.

To examine the effect of increasing shortlist lengths on search time, we performed a reranking ablation over shortlist lengths for D s D_{s} = 16 and D r D_{r} = 2048 over ImageNet-1K in Table 30 , and over ImageNet-4K in Table 31 . We observed that using a larger shortlist k k saturated ImageNet-1K performance at k k =200. But using larger shortlists until k = 2048 k=2048 , the maximum value supported by the FAISS framework, steadily improved performance on ImageNet-4K. This is likely due to the increased database size, but could also indicate a correlation with ImageNet-4K being slightly out-of-distribution making the task at hand harder.

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .