  In many retrieval systems the original high dimensional data (e.g., images)
is mapped to a lower dimensional feature through a learned embedding model. The
task of retrieving the most similar data from a gallery set to a given query
data is performed through a similarity comparison on features. When the
embedding model is updated, it might produce features that are not
comparable/compatible with features already in the gallery computed with the
old model. Subsequently, all features in the gallery need to be re-computed
using the new embedding model -- a computationally expensive process called
backfilling. Recently, compatible representation learning methods have been
proposed to avoid backfilling. Despite their relative success, there is an
inherent trade-off between the new model performance and its compatibility with
the old model. In this work, we introduce FastFill: a compatible model update
process using feature alignment and policy based partial backfilling to
promptly elevate retrieval performance. We show that previous backfilling
strategies suffer from decreased performance and demonstrate the importance of
both the training objective and the ordering in online partial backfilling. We
propose a new training method for feature alignment between old and new
embedding models using uncertainty estimation. Compared to previous works, we
obtain significantly improved backfilling results on a variety of datasets: mAP
on ImageNet (+4.4\%), Places-365 (+2.7\%), and VGG-Face2 (+1.3\%). Further, we
demonstrate that when updating a biased model with FastFill, the minority
subgroup accuracy gap promptly vanishes with a small fraction of partial
backfilling.
