Large retrieval systems such as face search, person re-identification and product search store millions of items as vectors produced by one fixed encoder. When the incoming queries start to look different, because of a new camera, fog, compression or sensor noise, the obvious fix is test-time adaptation: let the encoder adjust itself on the unlabeled queries. That fix has a hidden cost. Adapting the encoder moves its output coordinates, and the stored gallery was encoded in the old coordinates. Re-encoding the whole gallery ("backfilling") is the expensive operation these systems exist to avoid. The adapted queries therefore become better in their own space and worse at finding anything in the index. We propose to adapt only the query side, with no source training data, and to use the gallery itself as the fixed target. We summarize the stored gallery as a small set of reference vectors called anchors (k-means centroids of the legacy embeddings). We then adjust only the encoder's normalization parameters so that two things hold. Each shifted query should fall confidently near some anchor. The pattern of which anchors co-occur across a batch of queries should match the pattern the gallery itself shows.
In two sentences: the legacy gallery is the only "source data" a no-backfill system needs, and it already sits in the old coordinate system. Pulling shifted queries toward gallery anchors, and constraining the batch-level relational structure rather than trusting per-query pseudo-labels, should adapt to the shift while keeping queries compatible with the index by construction.
Core Claim
Test-time adaptation and backward compatibility are currently studied as if they were unrelated. The research file's Gap 4 states the tension directly: adaptation needs non-isometric feature changes, while compatibility needs geometric stability. We claim the tension largely dissolves once the adaptation objective is defined in the legacy space through gallery anchors instead of through the model's own classifier. A query can only score well under our objective if it lands in legacy coordinates near legacy structure, so adaptation and compatibility pull in the same direction.
The specific new ingredient is a relational, pseudo-label-free term. We match the anchor co-assignment matrix of target queries to that of the gallery, in the spirit of the distance-matrix matching of Learning Autoencoders with Relational Regularization. This term is aimed at the regime where per-sample pseudo-labels are wrong. That is the documented failure point of prototype-based adaptation methods under severe shift.
Concretely, let $g_1,\dots,g_k$ be unit-normalized k-means centroids of the stored gallery embeddings. Let $f_\theta$ be the legacy encoder, where $\theta$ is only the normalization-layer scale and shift. For a query $x$, define its anchor profile $p(x)=\mathrm{softmax}_j(\cos(f_\theta(x),g_j)/T)$, with temperature $T$. Stack the profiles of a batch of $B$ queries into $P\in\mathbb{R}^{B\times k}$. Define the co-assignment matrix $C_Q=P^\top P/B$, and compute the matching matrix $C_G$ once from the gallery embeddings themselves. The adaptation loss is
$$ \mathcal{L}(\theta)=\frac{1}{B}\sum_{x}H\big(p(x)\big)+\beta\,\mathrm{KL}\big(\bar C_Q\,\|\,\bar C_G\big), $$
where $H$ is Shannon entropy, the bars denote normalization to a distribution over the $k\times k$ entries, and $\beta$ weighs the relational term. For small batches, $C_Q$ is kept as an exponential moving average.
Relation to Prior Work
Three groups of work motivate the problem.
Backward-compatible training, introduced in Towards Backward-Compatible Representation Learning, trains a new model through a frozen legacy classifier. It showed that an unconstrained new model scores 0% against an old gallery while BCT reaches 67.23–70.70% on IJB-C. Our anchor term is the analogue of BCT's "influence loss," with gallery centroids replacing the legacy classifier. The difference is that BCT needs labeled source data and the legacy head, and we need neither.
Follow-ups such as Learning Compatible Embeddings and λ-Orthogonality Regularization relax the constraint with point-to-set terms or bounded-orthogonality adapters. They are also offline and supervised. The λ-orthogonality paper also supplies a constraint on our design: its finding that unconstrained affine maps erase legacy knowledge is why we restrict adaptation to normalization parameters.
The lifelong works (DJAA, Lifelong ReID with Backward-Compatibility, L2R) are the closest in spirit. All three retrain over sequential domains with replay buffers of past images or features. We do no retraining and keep no image replay.
On the adaptation side, three methods supply our machinery and our failure cases. Tent minimizes the entropy of the model's own predictions by updating normalization affine parameters. We reuse its parameterization but replace its classifier with gallery anchors. CAFA pulls pseudo-labeled test features toward stored source class centroids, using at least 5% of the source data to compute them. Our anchors come from the unlabeled gallery instead, and our relational term avoids per-sample pseudo-labels. This targets the documented collapse of such methods when initial error is high. EATA shows that Tent collapses to 0% clean accuracy in lifelong streams. That result motivates our lifelong compatibility test.
CAiDA also uses "anchors" in source-free adaptation, but as confident target pseudo-label seeds, not as fixed legacy-space references.
Finally, anchor-based relative representations supply the lens. Relative representations describe a sample by its cosine similarities to shared anchors, making spaces comparable up to rotation and scale. Relative geodesic representations extend this to curved spaces. Both assume the same anchor inputs pass through both models. We cannot assume that in a source-free system, so we place anchors only in the legacy space and make the query's anchor profile the training signal. HGA shows that alignment without paired anchors is possible by matching global geometry. We borrow that idea in the relational term, but we avoid HGA's non-convex rotation search, which takes about an hour per run with restarts.
Research Program
The first component is a measurement study answering a question nobody in the file has answered. How much do existing test-time adaptation methods break gallery compatibility? We encode a clean gallery with a frozen legacy model, stream corrupted queries, and run the standard adapters. We then report two things: their usual classification metric, and retrieval against the untouched gallery. To separate drift from shift, we also measure an evaluation-only diagnostic. Held-out clean images are encoded by the adapted and the legacy model, and we compare their anchor profiles. Low agreement means the adapter moved the coordinate system.
The second component is the method above, plus its systems details. These include the choice of $k$, centroid computation cost relative to backfilling, the moving-average estimate of $C_Q$ for small batches, and a fallback to statistics-only updates when batches are tiny.
The third component is a stress analysis of the relational term's main assumption, that queries and gallery share a population. We deliberately skew the query label distribution and measure how much the term's benefit shrinks. We also test whether a softened version (matching only the off-diagonal structure, or optimal-transport marginals with slack) keeps the gain.
Baselines
The naive reference is doing nothing: the frozen legacy encoder embeds corrupted queries and searches the clean gallery. Its gap from the upper bound tells us how much there is to recover. The upper bound, which no deployable method can reach, encodes the clean version of each query with the legacy model. This is perfect restoration, the best possible compatible query.
Statistics-only normalization adaptation, as in UBNA (Klingner et al.), replaces source batch-norm statistics with target statistics and changes nothing else. We expect it to be the strongest simple competitor, because renormalizing target features toward source-like activations is arguably compatibility-preserving by construction.
Tent and EATA are run with the legacy classifier head where one exists. EATA is run from its official code (mr-eggplant/EATA). For reference, EATA reports 65.0% corruption error on ImageNet-C severity 5 against Tent's 71.6%, and about 74% clean accuracy retained in lifelong streams where Tent falls to 0%. CAFA reports 12.13% error on CIFAR-10-C versus Tent's 13.98% and 55.24% on ImageNet-C versus 81.99% for the source model.
The strongest existing competitor for our exact question is CAFA re-implemented with gallery-cluster means and covariances in place of labeled source statistics, giving it exactly the information our method uses. All of these are classification-error numbers. We found no reported result on Lacuna for retrieval against a frozen legacy gallery under ImageNet-C or CIFAR-10-C, so the retrieval numbers for every baseline will be produced in this work.
For fairness, all methods share the same backbone, the same legacy gallery, the same query streams and orderings, the same batch sizes, and the same trainable parameters (normalization affine only). Each method gets an identical hyperparameter search budget, tuned on a held-out corruption type not used for reporting.
Two ablations isolate our ingredients. Entropy over gallery anchors without the relational term is "Tent with the gallery as head." The relational term alone tests whether batch-level structure suffices. A further reference retains a small paired anchor set of clean source images and fits an orthogonal Procrustes map from the adapted to the legacy space. This uses information our method does not have.
Beating the field means the following. On severity-4 and severity-5 corruptions, our method must exceed both statistics-only adaptation and gallery-CAFA in retrieval mean average precision against the legacy gallery. It must also keep clean-query retrieval within a small margin of the frozen model after a lifelong stream. A win that appears only at mild severity would not count.
Why not just…?
Why not just swap in target batch-norm statistics and stop? This is a real threat, and we may lose to it at mild shift. Renormalization changes no learned weights, so drift is limited. Its weakness is that it only matches first- and second-order activation statistics. It does not move queries toward legacy structure, and it degrades with small batches, a limitation the file notes for UBNA and Tent. The measurement study and the batch-size sweep settle this directly. If statistics-only adaptation matches our method at severity 5 and batch size 16, the relational term is not earning its place and we will say so.
Why not just run Tent or EATA and search the old gallery? Tent's objective rewards confidence under the model's own classifier, not proximity to legacy embeddings. Nothing stops the affine updates from moving the coordinate system, and EATA's lifelong result (clean accuracy falling to 0% for Tent) shows that this drift can be extreme. Many retrieval encoders also have no classifier head to adapt against. Our drift diagnostic on clean held-out images will show whether Tent's gains in classification error coincide with losses in legacy retrieval.
Why not just use CAFA with gallery cluster statistics? This is the closest competitor, and our method shares its anchor-pulling spirit. The difference is that CAFA trusts each query's pseudo-label. When initial error is very high, pulling queries to the wrong centroid compounds the error, a failure the file records for CAFA and CAiDA. Our relational term constrains only how anchors co-occur across the batch, which does not require any individual assignment to be right. The decisive comparison is retrieval at severity 5, stratified by the frozen model's initial error. If gallery-CAFA matches us there, the contribution reduces to the observation that the gallery can stand in for source statistics. That is still useful, but much smaller.
Why not just fit a rotation or linear map back to the legacy space? With paired anchors, Procrustes is cheap, but it requires retaining source images. Unconstrained affine maps were shown by λ-Orthogonality Regularization to erase legacy knowledge. Unpaired rotation search (HGA) is non-convex and slow. We include paired-anchor Procrustes as a reference that has more information than our method. Matching it without paired data would be the strongest outcome.
Proposed Experiments
The main testbed turns the corruption benchmarks into retrieval tasks. For ImageNet-C, the gallery is clean ImageNet images encoded once by a legacy ResNet-50. Queries are held-out images under each of the 15 corruptions at all 5 severities, and a match is a gallery item of the same class. CIFAR-10-C and CIFAR-100-C give cheaper replicates. For fine-grained retrieval we corrupt CUB200 queries against a clean gallery, following the compatibility protocol of λ-Orthogonality Regularization. For person re-identification, Market-1501 gallery identities are queried with corrupted Market-1501 images, and a cross-dataset variant uses DukeMTMC as a camera shift.
We report retrieval Top-1 and mean average precision against the legacy gallery as primary metrics. Secondary metrics are the clean-probe profile agreement (our drift diagnostic), compute per query, and, for comparability, classification error where a head exists.
Three decisive checks determine whether the idea holds.
The first is the drift check. Tent-style methods should show a gap between classification gains and legacy-retrieval gains, while our method shows none. If no such gap exists, the problem we target is not real.
The second is the severity check. The relational term should matter most where the frozen model's initial error is highest, and gallery-CAFA should degrade there. If both curves coincide, our central mechanism is not doing what we claim.
The third is the lifelong check, following EATA's protocol of streaming corruptions in sequence. After the stream, clean queries must still retrieve from the legacy gallery near the frozen model's level. This is the operational meaning of "backward compatible" for a system that never backfills.
The label-skew experiment then bounds when the relational assumption breaks. It tells practitioners when to fall back to the entropy-only variant.
References
- Learning Autoencoders with Relational Regularization
- Towards Backward-Compatible Representation Learning
- Learning Compatible Embeddings
- $\boldsymbol{\lambda}$-Orthogonality Regularization for Compatible Representation Learning
- Anti-Forgetting Adaptation for Unsupervised Person Re-Identification
- Lifelong Person Re-Identification with Backward-Compatibility
- L2R: Lifelong Learning for First-stage Retrieval with Backward-Compatible Representations
- Tent: Fully Test-Time Adaptation by Entropy Minimization
- CAFA: Class-Aware Feature Alignment for Test-Time Adaptation
- Efficient Test-Time Model Adaptation without Forgetting
- Confident Anchor-Induced Multi-Source Free Domain Adaptation
- Relative representations enable zero-shot latent space communication
- Connecting Neural Models Latent Geometries with Relative Geodesic Representations
- Unsupervised Latent Space Alignment with Hyperspherical Geodesic Matching
- Unsupervised BatchNorm Adaptation (UBNA): A Domain Adaptation Method for Semantic Segmentation Without Using Source Domain Representations