NUDGE: Lightweight Non-Parametric Fine-Tuning of Embeddings for Retrieval
Authors: Sepanta Zeighami
Zac Wellmer
Aditya Parameswaran
Venue: ICLR 2025 Poster (2025)
Keywords: semantic similarity search
pre-trained embedding model
fine-tuning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We present NUDGE, a lightweight non-parametric method to fine-tuning embeddings from pre-trained models for nearest neighbor retrieval

Abstract: $k$-Nearest Neighbor search on dense vector embeddings ($k$-NN retrieval) from pre-trained embedding models is the predominant retrieval method for text and images, as well as Retrieval-Augmented Generation (RAG) pipelines. In practice, application developers often fine-tune the embeddings to improve their accuracy on the dataset and query workload in hand. Existing approaches either fine-tune the pre-trained model itself or, more efficiently, but at the cost of accuracy, train adaptor models to transform the output of the pre-trained model. We present NUDGE, a family of novel *non-parametric* embedding fine-tuning approaches that are significantly more accurate and efficient than both sets of existing approaches. NUDGE directly modifies the embeddings of data records to maximize the accuracy of $k$-NN retrieval. We present a thorough theoretical and experimental study of NUDGE's non-parametric approach. We show that even though the underlying problem is NP-Hard, constrained variations can be solved efficiently. These constraints additionally ensure that the changes to the embeddings are modest, avoiding large distortions to the semantics learned during pre-training. In experiments across five pre-trained models and nine standard text and image retrieval datasets, *NUDGE runs in minutes and often improves NDCG@10 by more than 10\% over existing fine-tuning methods. On average, NUDGE provides 3.3$\times$ and 4.3$\times$ higher increase in accuracy and runs 200$\times$ and 3$\times$ faster, respectively, over fine-tuning the pre-trained model and training adaptors.*

Published as a conference paper at ICLR 2025
NUDGE: LIGHTWEIGHT NON-PARAMETRIE -UNNITUNING OF EMBEDDINGS FOR RETRIEVAL
Sepanta Zeighami
Zac Wellmer
Aditya Parameswaran
UC Berkeley
zac01984.ad
UC Berkeley adit adityasp@eerkeeey.eed
ze seighami@berkeley.
ABSTRACT
k-Nearest Neighbor search on dense vector embeddings (k-NN retrieval) from pre-trained embedding models is the predominant retrieval method for text and images, as well as Retrieval-Augmented Generation (RAG) pipelines. In prac- tice, application developers often fine-tune the embeddings to improve their ac- curacy on the dataset and query workload in hand. Existing approaches either fine-tune the pre-trained model itself or, more efficiently, but at the cost of ac- curacy, train adaptor models to transform the output of the pre-trained model. We present NUDGE, a family of novel par-paaaetttic embedding fine-tuning approaches that are significantly more accurate and efficient than both sets of ex- isting approaches. NUDGE directly modifies the embeddings of data records to maximize the accuracy of k--N retrieval. We present thorough theoretical and experimental analysis of NUDGE's s non non-parametric approach. We show that even though the underlying problem is NP-Hard, constrained variations can be solved efficiently. These constraints additionally ensure that the changes to the embed- dings are modest, avoiding large distortions to the semanties learned during pre- training. In experiments across five pre-trained models and nine standard text and image retrieval datasets, NUDGE runs in minutes and often achieves NDCG@ 10 at least 10% higher than existing fine-tuning methods. On average, NUDGE pro- vides 3.3x and 4.3x higher increase in accuracy and runs 200x and 3x faster, respectively, over fine-tuning the pre-trained model and training adaptors.
INTRODUCTION
k-Nearest Neighbor search on dense vector embeddings (k-NN retrieval) from pre-traine mr-itrained embed- ding models is the de-facto standard for text and image retrieval, as well as in Setrieval-Augmene
Generation (RAG) pipelines. (Lewis et al.) 2020 Li et al. 2023a Gao et al. 2023 Patil et al.. [023] Du et al. 2022 Liu et al., 2021b). Given data records (e.g.. text chunks or images), k-NN re- trieval embeds them using a pre-trained model as d-dimensional vectors in Rd. To answer a query, it similarly embeds the query in Rd and retrieves the top-k data records whose embeddings have the highest cosine similarity (or inner product) with the query embedding. By simply performing a top-k look-up (often through vector databases), the simplicity and efficiency of k--N retrieval has made it increasingly popular and often preferred to other retrieval paradigms, e.g., late interaction (Khattab & Zaharia 2020 (Santhanam al.] (021) or generative retrieval (Tay al., 2022; Wang et al. 2022). However, the out-of-the-box pre-trained model is often not sufficiently accurate on the dataset or queries in hand, and fine-tuning typically used to improve the accuracy.
There are two standard approaches to fine-tuning embeddings: fine-tuning the pre-trained mod- els directly (referred to henceforth as PTFT) or training aduptor models on top of the pre-trained
models (Zhao et al. 2024] Zhou et al. 2024 Aarsen 2024, Suvansh Sanjeev] 2024, LlamaIndex 2024b). PTFT can be more accurate but comes with practical challenges: it (1) requires access to the model parameters and must rely on third-party APIs for closed-source models | (2) is com- putationally expensive, and (3) incurs further hosting and maintenance costs for deployment of the fine-tuned model. An alternative is to learn an Adapior, ÿe. a transformation of the output of the (frozen) pre-trained model, f. so that the function ge o generates accurate data and/or query em- beddings. Training ge can be done model-agnossicalll, that is. with only black-box access to the pre-trained model, addressing (1). Moreover, Adaptors are typically small models, such as linear 'E.., OpenAT currently does not provide interface for fine-tuning embedding model OpenAl 2024b).

---

Published as a conference paper at ICLR 2025
legend:
Initial data embedding * Pine-tuned data embedding
Training query embedding
Constrained region for fine-tuning example constraints
Table 1: Comparison of fine-tuning methods on standard text datasets (PTFT refers fine-tuning the pre-trained model). See Sec. for experimental setting.
normalized embeddings unit ball
NUDGE (ours)
PTFT
Adaptors
Needs Model
Yes
No
No
Parameters
Bounded change magnitude
Fine-Tuning
NUDGEs change data embeddings within a constrained region to maximize similar- ity with training queries. Data embeddings are colored based on queries for which they are the ground-truth answers.
Figure I:
447
7.99
2.18
Time (mins.)
Accuracy Boost (avg max%)
3.8/ / 15.6
2.9 12.4
12.4 / 24.8
models (Llamalndex 2024b), addressing (2), and lowering the associated costs in (3). Nonetheless, experimental results show, at best, modest accuracy gains from using Adaptors. We, therefore, lack a fine-tunnig approach for k-NN retrieval that simultaneously effective, efficient, and easy-to-use.
We present NUDGE, a family of approaches to non non-parametriaall fine-tune embeddings efficiently. NUDGE methods (or NUDGEs) are surprisingly effective, model-agnostic, and incur no additional deployment cost. NUDGEs take a novel non-parametric view of embedding fine-tuning: they view the embeddings themselves parameters of the N--N retrieval algorithm and directly modify the embeddings of data records to maximize the accuracy of k--N retrieval. Although we show that the underlying optimization problem is NP-Hart in general, and can lead to overfitting if data em- beddings are allowed to change arbitrarily, NUDGES efficiently solve constrained variations of this problem formulated to avoid overfitting. As shown in Fig. T NUDGES change each data embedding to maximize the similarity between the data embedding and the training queries to which the data record is correct answer, while constraining how and by how much the embedding can change. Intuitively, the constraints allow for enough modifications to the embeddings to improve accuracy on the dataset in hand while avoiding large distortion that would offset the semanties learned during pre-training. Fig. [ shows an example of the constrained region used, where new embeddings are constrained to be normalized (i.e., to fall on the unit ball), and the magnitude of changes to the embeddings to be bounded. NUDGES solve the constrained optimization problems in closed form, presenting simple and effective update formulae for embedding fine-tuning.
NUDGE's non-parametric formulation represents a new paradigm in embedding fine-tuning. It contrasts with parametric approaches adopted by PTFT and Adaptors that increase the similar- ity between query and answer pairs through contrastive-type losses (Zhao et al. (024). The non- parametric nature of NUDGE affords it more flexibility in optimization improve data embeddings for which training queries are available, but avoids embedding changes for data records without associated training queries. Parametric methods, on the other hand, have less flexibility in opti- mization, but any improvement may generalize to data records that don't have associated training queries. This makes NUDGE partieularly well-suited for closed-world settings where a relatively fixed dataset is queried multiple times, while parametric methods advantageous when general- izing to new data records (c.g., in a rapidly changing dataset) without associated training queries. In the latter setting, we show that NUDGE can be combined with parametric methods improve embeddings of data records both with and without associated training queries.
We present a thorough experimental evaluation, showing that NUDGES significantly outperform Adaptors and PTFT on standard text retrieval datasets from BEIR (Thakur et al. 202T) and KILT (Petroni et al. (2021) and image retrieval datasets COCO (Lin et al. 2014]. NUDGES obtain common accuracy metrics Recall 10 and NDCG@ 10 up to 16.0% higher than both PTFT and Adaptors and 24.4% higher than no fine-tuning, consistently outperforming parametric methods across 9 different datasets and 5 different embedding models. We also compre- hensively evaluate
2014) and Flickr (Yougg et al.)
generalization of NUDGEs compared with parametric meth- ods. We show that although NUDGEs, on their own, have limited out-of-distribution generalization ability, they can be combined with parametric methods inherit their out-of-distribution charac- teristics while complementing them with significant in-distribution accuracy improvements. Over- all, NUDGES are model-agnostic and can be used with any (potentially closed-source) embedding
2

---

Published as a conference paper at ICLR 2025
model, are trained in minutes datasets with millions of records, and the fine-tuned embeddings can be used directly without any additional model inference cost.
2 PRELIMINARIES
Notation. We use bar" on top of letters to denote raw data/queries that are not embedded. We use boldface capital letters to denote matrices (mostly used to represent embeddings), e.g., X E R is an r x & matrix, and use X; to refer to the i-th row of the matrix, which is a vector, X; E R | refers to the L2 norm of vector æ, |X ||
refers to the vector of row-wise norms, (1XII X
and X refers to X with normalized rows. We use [s] to refer to the set 2 ..... 8).
X
Given dataset, D of records (e.g., text chunks or images), k-NN retrieval first embeds the data records using an embedding model, ED, to generate an embedding matrix D E Raxd where d is the embedding dimensionality. The i-th row, D., of D is the embed- ding of the i-th record, D; that is, D; ED (D:). To answer a query q. k-NN retrieval first embeds the query using an embedding model, &g (often Eg and &D are the same, but can be different, espe- cially in multi-modal setting) to obtain q = Eq (g). k-NN retrieval then returns the top-k records in D whose embeddings have the highest similarity to q, measured by either the inner product or cosine similarity, i.e., the records ...,.., Drs that correspond to the k highest values in the set (Di 9,..., Dn q) when using the inner product similarity metric. By default, we use the inner product, which can be applied to normalized embeddings to obtain cosine similarity.
k-Nearest Neighbor Retrieval.
Ground- -ruuh Answers. Queries can require retrieving multiple data records, and each data record can have different degree of relevance to the query. For simplicity, here, we present our results in the setting where a query, q. requires retrieving a single ground-truth data record. We refer to the ground-truth data record for query, g. as the ground-truth answer to the query and often refer to the data record with its index y, y E [n]] Extensions to multiple ground-truth data records (each with potentialll different degrees of relevance to the query) is straightforward and presented in Appx. D
Fine-Tume Tuning. Fine-tuning aims to improve retrieval accuracy for the dataset D through optimizing embeddings. We let D E Raxd denote the fine-tuned data embeddings obtained after fine-tuning, where D E Rd is the fine-tuned embedding for the i-th data record. We consider a supervised setting where a query set with corresponding ground-truth answers is available, consisting of the query set, Q, and a set, Y, of ground-truth answers, where Y, is the index of the ground-truth answer for the j-th query, Oj. We split this set into two, a training set Q", YT and a validation set Q",YV, with nt and ny queries, respectively. Let Q" E R= and QV E R2y xd be matrices containing embeddings for training and validation queries. The training set can be collected over time from user interactions with the system, by collecting labels, or by generating synthetic training data using LLMs (e.g... [LlamaIndex (2024a); Meng et al. 2022
3 NON-PARAMETRIS EMBEDDING FINE-TUNING
Our NUDGE approach views embeddings as parameters of the k-NN retrieval algorithm, optimizing the embeddings directly to improve retrieval accuracy. In Sec. 3.1, we formalize the notion of non- parametric embedding fine-tuning by stating two optimization problems, one directly maximizing a retrieval accuracy metric and one maximizing similarity between queries and their ground-truth answers. Maximizing accuracy is the final goal, but similarity is a simpler surrogate to optimize in practice. Nonetheless, we show that the former is NP-hard and the latter unbounded (i.e., the objective can be improved indefinitely). Moreover, since both optimization problems allow embed- dings to arbitrarily change (i.c., are unconstrained), directly solving either can lead to overfitting. In Sec. 3.2. we present NUDGE, a family of approaches that solve a combination of constrained variations of the two optimization problems to address generalization and efficiency challenges.
3.1 UNCONSTRAINED NON- CON-PARAMETRIC EMBEDDING TUNING PROBLEMS
Let A E Raad be the modification to be learned to the embeddings, so that its i-th row, A,, is the modification to D,, That is, after fine-tuning, the final embedding is D = D + A. We use Q and Y to refer to a generic query embedding matrix with corresponding ground-truth answers containing N queries. Q and Y can respectively be either Q" and Y or Q" and YV. Recall that Y, is the index of the ground-truth answer to the i-th query, so that Dy, and Av, are d-dimensional vectors, respectively, referring to the data embedding of the ground- -tunn answer to i-th query, and the modification be learned to the data embedding of the ground-truth answer i-th query.
3

---

Published as a conference paper at ICLR 2025
MaxA-EFT. Maximum Accuracy Embedding Fine-Tuning Problem, MaxA-EFT, is the problem of finding A to fine-tune data embeddings that maximizes the number of queries in Q answered cor- rectly, formalized as follows. For query embedding matrix Q with ground-truth answers Y. let (,),, for i E [M], be the indicator variable denoting if the i-th query is answered correctly after fine-tuning with A. Formally, (4) = 1 if the following holds, and zero otherwise
Q: (Dy; + Av;) > Q (D) + Aj), Vj E ([x) YY),
(1)
Where [n] \ Y; is the set data records indices that are not ground-truth answer the i-th query.
Problem (MaxA-EFT). MaxA-EFP MaxA-FFTiR is the problem finding to maximize the number of queries answered correctly after fine-tuning with A, i.e., arg max AERaxa DiE(N] I()).
Theorem 1. MaxA-EFT is NP-Hard.
Theorem is proved by reduction from the Maximum Feasible Linear Subsystem problem as studied in Amaldi & Kann (1955), Appx. [.T]] Apart from the NP-hardness, MaxA-EFT allows data embeddings to be arbitrarily changed by A. This change can distort the semantics captured in D by the pre-trained model, and lead poor generalization to queries outside of Q.
MaxS-EFT. alternative formulation Maximum Similarity Embedding Fine-Tuning Problem,
arg max
Σ Q.. + +y;),
(2)
AER N
referred to MaxS-EFT. Here, we change data embeddings to maximize the similarity between queries and ground-truth answers, a standard optimization objective (e.g., Hendeesnnnrron et al. (2017), Trancforrranss (024b)). However, the non- non-parametric formulation makes Eq. an uncon- strained optimization problem with a linear objective, so the problem is unbounded and has no optimal solution. Moreover, setting Ay; so Q: Ay; and increasing the magnitude of Ay; bitrarily improves the objective, yielding trivial solutions with poor generalization to unseen queries. 3.2 NUDGE APPROACHES
Because of the potential for overfitting and the computational challenges due to NP-hardness, we do not solve either MaxA-EFT or MaxS-EFT directly. Instead, we introduce NUDGE, a family of approaches that solve constrained variations of MaxA-EFT and MaxS-EFT, designed to avoid overfitting, while being efficient. We discuss two main approaches, NUDGE-M and NUDGE-N, in Secs. 3.2.1 and 3.2. and present other practical extensions in Appx.
C
3.2.1 NUDGE-M: NUDGE WITH BOUNDED MAGNITUDE
NUDGE-M solves MaxS-EFF on the training set, but with the added constraint || Y. Vi E [n], for a scalar 7 2 0. 7 controls how much each embedding can change during fine-tuning. NUDGE- M sets y by solving MaxA-EFT on the validation set. Intuitively, this approach (1) changes data embeddings to maximize the similarity between embeddings and queries on the training set, (2) ensures that the magnitude of the changes to the embeddings is bounded to avoid overfitting, and (3) decides how much the embeddings are allowed to change by maximizing validation accuracy. NUDGE-M provides a closed-form solution to do this. We provide overview of the solution here and leave the details and formal proofs to Appx. B.2
Optimization Formulation. Define MaxS-M for scalar 2 O, as the set of optimal solutions the following constrained version of MaxS-EN EFTT with bounded magnitude:
MaxS-Ma -M()) = arg max
Σ QT (Dyr + Ayr)
sE(NT]
s.t. A E Rad
| S V
A A MaxS-M(1) changes data embeddings by at most y while maximizing the similarity between training queries and their ground-truth answer. We set to maximize the validation accuracy after fine-tuning with E MaxS-M(7):
Σ (A) (E(nv]
max
s.t. A E Maxxx MMMxS-M(()))>
4

---

Published as a conference paper at ICLR 2025
(A) denotes I, (see Eq. 1b the validation set QV YV, Eie(my) (A) is the validation ac- euracy after fine-tuning with A. This problem is referred to Bi-level Maximization with bounded Magnitude, BiMax-M. We denote the optimal solution to BiMax-M by A M
NUDGE-M. NUDGE-M is an algorithm that optimally solves BiMax-M:
Theorem 2. There exists an algorithm, referred to as NUDGE-M, that optimally solves BiMax-M in Onv log nvy ryrd). Specifically, NUDGE-M sets A AM as
A AM-
where G:= G.=> ++=Emm 11=
Vi [m],
(3)
|G:
JE(PT]
and I. is the indicator function with a predicate argument, for optimally chosen scalar y
Eq. 3 presents the simple update rule used by NUDGE-M to fine-tune data embeddings, using which the fine-tuned embeddings computed as D D A Observe that G; is the sum of query embeddings whose ground-truth answer is D,, so that data embeddings are moved towards the queries for which they are the ground-truth answers. We also note that ((nrd) is the complexity of a single iteration over training data, and (mnynd) is the complexity of calculating validation accuracy once. Thus, ignoring the log term, the above time complexity is equal single training and validation iteration for parametric approaches (i.e., Adaptors or PTFT), and has smaller constant factors since does not perform any model forward passes.
The optimal 7 in Eq. 3 is calculated by solving linear inequalities resulting from the definition of IY We provide overview here and leave the details Appx. B.2 First, note that MaxS-M(7) G Y ||| found using the KKT points of the optimization problem. Thus, BiMax-M reduces to finding Eielar
y that maximizes
IY (y ||G||
G )- For each i [mv], substituting A y |Il
G into the
definition of Z.V [ in Eq. we have Z.V (7 | = 1 if the following holds, and zero otherwise:
G
Gy
Q (Dy, +
QK (D, + |G,
(4)
|G
Eq. 4 is set of inequalities in yy Denote the solution to the inequalities by I, so that E I; if and Since the inequalities are linear in y, I, is an interval R. Consequently,
only if IV (1 G
(
arg max
Σ 1h E 4..
(5)
EERV
and the solution to Eq. is y that intersects the most number of intervals across all T;, i E [nv], which can be found by single iteration over the intervals after sorting their start and end points.
3.2.2 NUDGE-N: NUDGE WITH NORMALIZED EMBEDDINGS
NUDGE-N additionally constrains the norm of the fine-tuned embedding. This constraint serves as an additional regularization, helping with
generalization (see Sec(4.2).
Optimization Formulation. Analogous to MaxS (axxSMM(n) but with an added constraint, we define MaxS-N(1) the optimal solution the following optimization problem:
MaxS-N(7) = arg max
Σ of (Dx? + Av?)
|E|1T]
s.t. A E Radd
< <
Vi [
To find suitable 7, solve the same optimization problem BiMax-M, except that we replace MaxS-M(7) with MaxS-N(7). We call this problem Bi- Bi-level Maximization with Normalized em- beddings, BiMax-N, and refer its optimal solution as A N
NUDGE-N. NUDGE-N an algorithm that optimally solves BiMax-N:
Theorem 3. There exists an algorithm, referred to as NUDGE-N, that optimally solves BiMax-N in (nd + log nv) + wrd). Specifically, NUDGE-N sets A
D.,
if C..D 2
G
G: (D; G.)
A
Z, = G; (D; G. D.j
(6)
(4 Z - D., otherwise,
and G is as defined in Eq. for optimally chosen scalar 7*
5

---

Published as a conference paper at ICLR 2025
ofs the update rule used by NUDGE-N to fine-tune data embeddings, using which the fine-tuned embeddings are obtained as D = + N. This update moves the data embedding on the unit ball (to satisfy || + A = 1) between D, and [.l. where G.. is the normalized sum of embeddings [G.T
of queries whose ground-truth answer is D.. Y determines how much to move the embedding, and Ze determines the direction. Ze is the normalized projection of G; onto the tangent plane of the unit ball at D, so that moving in the direction of Z: maximally increases MaxS-N objective.
Finding the optimal 7" is similar to NUDGE-M. We first use KKT to solve MaxS-N(7) and sub- stitute the resulting into the definition of TV in Eq. | The optimal y- then found as the value that satisfies the maximum number of the resulting inequalities. The resulting incqualities are, in this case, quadratic (compared with linear for NUDGE-M) but can still be solved in closed-form. Nevertheless, from practical perspective, solving the quadratic equations is tedious as it requires considering various special cases. We observed that performing a grid search to find 7 that maxi- mizes validation accuracy finds accurate solutions and is almost as efficient (experiments in Sec. 4.3 show NUDGE-N is not very sensitive to the value of y²). We use this implementation in practice.
3.3 EXTENSIONS AND ALTERNATIVES
Combining NUDGE and Parametric Methods for Generalization. NUDGE's non-parametric methodology distinguishes between data records that have associated queries at training time (re- ferred to as in-distribution labels) and data records that don't (referred to as out-of-distributio la- bels). NUDGE is designed to improve embeddings of in-distribution labels, and does not modify the embedding of data records that don't 't appear in the training set. In contrast, parametric methods such as PTFT and Adaptor modify the embedding function and have the ability to generalize and improve embeddings of out-of- of-distribution labels well. This makes NUDGE well-suited for closed world settings where data records are relatively fixed, and generalization to new records is not needed. On the other hand, when generalization is needed, NUDGE can be combined with parametric methods to provide the best of both worlds: improving accuracy for queries with in-distribution labels through NUDGE and on queries with out-of-distribution labels through parametric methods. Sec. /4.2 ically studies generalization ability of NUDGE when combined with parametric methods.
Alternative Constraint Formulations. Constraints are important part of NUDGE, controlling how embeddings are updated. The L2 norm constraints in NUDGE-M and NUDGE-N are chosen since we focus dense embeddings and bounding L2 norm leads to dense embedding updates. However, other constraints are possible, for example, using L1 norm instead of L2 norm to create sparse updates using adaptive thresholds in NUDGE-M and NUDGE-N to increase flexibility in fine-tuning. We studied both such approaches, deriving fine-tuning update rule using L norm in Ap- pendix C.I and empirically evaluating both use of LI norm and adaptive thresholds in Appendix EE6 We observed limited benefits from using such alternative constraint formulations.
4 EXPERIMENTS
We present results on standard text and image retrieval benchmarks and multiple pre-trained models. For the sake of space, additional detailed results and ablation studies are deferred to Appx. E
Datasets.
For text retrieval datasets we use 7 standard datasets: SciFacts Wadden et al. 2020
Fever (Fever 2024), ArguAna (Arguana 2024) (we use their BEIR (Thakur et 20. versions),
TriviaQA Joshi et al. (2017), HotpoiQA (Yang et al. 2018), and Natural Questions K Kwiatkowski ct al. 2019) (we use their KILT (Petroni et al. (021) l) versions), and NF-Corrus (Boteva et al. 2016) (although all datasets have BEIR version,
non-BEIR versions whenever that is larger). We use the datasets as is, without any preprocessing step, except for datasets from KILT, where we only use Wikipedia pages that contain answer least one query (i.e., pages where we expect fine- tuning to have an impact) due to computational constraints (embedding and storing the embeddings for all Wikipedia pages requires significant computational resources and unlikely to impact the results). For image retrieval, we use COCO (Lin et al.) 2014) (we use the dataset from 2014) and Flickr (Young al. 2014) datasets. We use image captions as queries to retrieve the corresponding image. For all text and image datasets, we use 1.7-0.1-0.2 train, validation and test split, but limit test and validation sizes to at most 10,000 queries if there is more. Statistics about data and query size are presented in Table 2
Pre-Trained Models. We report results on fine-tuning embeddings for 5 different pre-trained mod- els, 3 for text and 2 for image retrieval, where we consider models of different sizes and embedding dimensions. For text, we use BGE-small (Xiao et al. 2023) with 33M parameters and embedding

---

Published as a conference paper at ICLR 2025
Table 2: Total number of queries and records in the datasets
NF-Corpus
SciFact
ArguAna
Fever
NQ
TriviaQA
HotpotQA
COCO
Flickr
Query Data
2,429 3,633
1,109 5,183
1,401 8,674
123,142 5,416,568
79,782 7,631,395
58,245
74,259 7,631,395
414,113 82,783
155,070 31,014
7,631,395
Table 3: Average results across text datasets grouped by the embedding model used
Emb. Model + Method
BGE-S
GTE-L
TE3-L
R@L
R@ 10
NDCG@1 10
@
R @ 10
NDCG@N 10
R @
R@ @
10
NDCG@1 10
NUDGE-M
49.7
66.6
57.0 (+8.4)
52.1
73.4
61.0 (+7.7)
54.1
75.6
63.2 (+11.0)
NUDGE-N
52.0
72.6
61.1 (+12.4)
53,4
74.8
62.7 (+9.4)
55,2
76.0
63.9 (+11.7)
Adapter
39.5
65.5
51.6 (+2.9)
45.1
68.4
55.7 (+2.4)
46.9
66.2
54.4 (+2.2)
PIFT
40.9
66.1
52.5 (+3.8)
N/A
N/A
N/A
N/A
N/A
N/A
No Tiniin
37.0
62.4
48.7
41.6
67.0
53.3
40.0
67.5
52.2
dimension 384, GTE-large (Li et al. 2023b) with 434M
parameters and embedding dimension 1024 (OpenAI, 2024a), closed-source model with embedding di-
and OpenAl's text-embeddingglargee
mensions 3072. The three models are respectively referred to as BGE-S, GTE-L and TE3-L. For image retrieval, we use two CLIP variants (Radford et al.] 2021). ViT-B/32 and ViT-L/14, which have, respectively, 151M and 427M parameters and 512 and 768 embedding dimensions. We re- spectively call them CLIP-B and CLIP-L.
Baselines. We report results using the embeddings without fine-tuning, called No Fine-Tuning, in addition to training Adaptors and fine-tuning the pre-trained model, referred to as PTFT (see Appx. [. for implementation details). Due to computational constraints, we report results for the latter only for the small open-source model BGE-S. For both, we present two versions. By default, we use the Multiple Negative Ranking (MNR) loss (Henderson et al., 2017) for training, which is the standard contrastive fine-tuning loss when positive query/answer pairs are available, suggested by SentenceTrrnsformee Transformers (Sentence' Trieiieerraafooooi rransfomeer) (024a) and used by LlamaIndex (Llama 2024d) for fine-tuning (although Llamalndex only uses a single positive example per query (Lla- malndex 2024e)). Despite our hyperparameter tuning effort, we observed accuracy improve- ments on some datasets through fine-tuning with this loss (see T)ble We then modified the loss, so that only negative samples whose cosine similarity is at least equal to a threshold are included in the loss (see E. for details), which improved accuracy on some datasets but worsened it on other. We use the suffix -I. to denote the baselines using this modified loss. We report results using this loss to gain more insight into the baseline's 's behavior. We use cosine similarity as the retrieval distance metric for No Fine-Tuning, Adaptor, and PTFT.
Metrics. We report typical metrics Recall@k @R@k k for short) and NDCG@k with k: 10 by default, following MTEB benchmark (Muennighoff et al.) 2022). We also report Recall@ 1, the validation metric, and the change in NDCG@ & compared with No Fine-Tuning in parenthesis (+/-).
4.1 BASELINE RESULTS
Summary of results. Tables present our accuracy results averaged across all text or image datasets for different models. Table 55) presents the per dataset results for BGE-S. The per dataset results for other models followed similar trends and are deferred to Appx. E.2
As Tables 3 4 show, both NUDGE-M and NUDGE-N provide significant accuracy gains, provid- NDCG@ 10 boost over No Fine-Tuning while PTFT and Adaptor only improve NDCG@ @ 10 up 4.0%, when averaged across datasets, for both text and image retrieval. Inter- estingly, the accuracy gains from NUDGE-M and NUDGE-N depends on the pre-trained model. GTE-L outperfors TE3-L without fine-tuning, but using NUDGE TE3-L outperforms GTE-L.
ing up to 14.3% 4..3%
Moreover, Table X shows the total fine-tuning time to run BGE-S on our text datasets (i.e., time obtain the associated results in Table 3) using an Nvidia A100 GPU well as using 32 core Intel Broadwell CPUs. The reported time excludes the time to embed the data records (which is the same across all methods). NUDGE variants run in 1-2 minutes with GPU and in less than 11 minutes using CPUs, which is, respectively, more than and 11 times faster than Adaptor and more than 200 times faster than PTFT, which cannot be run CPUs in reasonable tmme-frame. For both Adaptor and PTFT, the reported run times are for optimized implementations that include early stopping and optimizations for efficient calculation of validation accuracy (see Appx. B.

---

Published as a conference paper at ICLR 2025
Table 4; Average results across image datasets grouped by the embedding model used
Emb. Model -
CLIP-B
CLIP-L
Method
R@1
R@ 10
NDCG@10
R
R@
NDCG@10 10
NUDGE-M
28.6
55.1
40.9 (+14.1)
30.1
58.1
43.2 (+10.7)
NUDGE-N
28.8
55.3
41.1 (+14.3)
30.1
58.2
43.3 (+10.8)
Adapter
18.5
43.5
29.9 (+3.0)
24.1
50.9
36.5 (+4.0)
No Funiig
15.9
40.1
26.9
20.5
46.5
32.5
Table 5: NDCG@ 10 results for using BGE-S on text datasets
Method
ArguAna
Fever
HotpotQA
NF-Corpus
NQ
SciFact
TriviaQA
NUDGE-M
47.9 (+0)
95.0 (+13.7)
63.1 (+5.0)
40.0 (+6.1)
38.6 (+17.5)
79.2 (+6.5)
35.5 (+9.6)
NUDGE-N
47.9 (+0)
93.5 (+12.3)
65.2 (+7.1)
44.6 (+10.))
45.9 (+24.8)
87.8 (+15.1)
43.0 (+17.2)
Adapter
47.9 (+-)
81.2 (+0)
58.1 (+0)
37.4 (+3.5)
27.4 (+6.2)
83.5 (+10.9)
25.9 (+0)
Adapter-L
47.9 (+0)
88.4 (+7.2)
62.7 (+4.6)
35.7 (+1.9)
(412.))
85.1 (+12.4)
27.2 (+1.2)
PTFT
47.9 (+0)
81.2 (+0)
58.1 (+0)
46.1 (+12.2)
28.1 (+7.0)
80.4 (+7.7)
25.9 (+0)
PTFT-L
47.9 (+0)
84.1 (+2.9)
62.1 (+4.0)
36.0 (+2.2)
36.8 (+15.6)
72.7 (+0)
26.0 (+0.1)
No Muninnn
47.9
81.2
58.1
33.8
21.2
72.7
25.9
Detailed Results. Table shows the detailed retrieval accuracy text datasets for BGE-S. NUDGE significantly outperforms parametric methods on almost all datasets. NUDGE-N outperforms NUDGE-M on most datasets, showing the benefit of constraining embeddings to be normalized.
The results show that parametric approaches are unreliable and fail to provide significant accuracy improvements despite requiring significantly more computational resources. The reported results are after hyperparameter tuning as well tweaking the loss function (i.c., variants). We observed that the latter does help improve (and sometimes worsen) accuracy for parametric approaches on some datasets, with Adaptor-L. and PTFT-L providing accuracy improvements on Fever and HotpotQA where Adaptor and PTFT provided none. Meanwhile, NUDGE consistently provides significant accuracy boosts without any hyperparameter tuning. We provide a detailed discussion of the failure modes of the parametric approaches in Appx. E.3
Impact of label distribution. Across datasets, we see NUDGE-M and NUDGE-N perform simi- larly on some datasets, while NUDGE-N outperforms NUDGE-M in other settings. As we discuss in details in Appendix 12 difference between NUDGE-N and NUDGE-M can be explained based on the label distribution. Specifically, NUDGE-M performs worse on datasets where many queries ask for labels that are not seen during training (c.g.. NQ, HotpotQA, SciFact), while it performs better when label ditribution is skewed towards fixed set of labels (e.g., Fever, CoCo and Flickr).
4.2 OUT-OF-DISTRIUUTURN
GENERALIZATION
Next, we study the impact of fine-tuning on duttrf-distributionn queries and labels. To study impact of out-of outoof-distribution queries, separately for each dataset, we use K-means to cluster all the queries in two clusters, referred to C1 and C2. We split C1 into 3 sets, C Cyal and Cjea, where Chrain and CYall are used for training and validation. We report test results on Clest as in-distribution and on C2 as out-tf-distribution results. To study impact of out- -iito--distriuution labels, we split the test set into two sets. We define queries with out-of-distribution labels as queries whose ground-truth answer contains a data record not the training set. We refer to the rest of the test set queries with in-distribution labels. We abbreviate in-distribution as InD and out-of-distribution as OoD. We also include results for A+NUDGE-N and P-NUDGE-N, which are methods that perform NUDGE-N on embeddings obtained after performing Adaptor and PTFT, respectively.
Average results across text datasets and with BGE-S model are shown in Table 6 As expected, NUDGE variants significantly outperform Adaptor and PTFT on both in-distribution queries and la- bels. Moreover, A+NUDGE-N and P+NUDGE-N provide the best results for OoD Label, showing that combining NUDGE-N with parametric methods helps NUDGE-N provide better generalization to unseen labels while preserving NUDGE-N's significant accuracy boosts in In-Distribution set- tings. However, surprisingly, we see little benefit to parametric methods in OoD settings, which is counter-intuitive as we expect such approaches to provide better generalization ability than NUDGE.
To investigate this further, we plot the per dataset generalization results for 3 datasets in Table 7 (results for other datasets is presented in Appendix F First, observe that Adapter and PTFT
8

---

Published as a conference paper at ICLR 2025
Table Generalization results using BGE-S. NDCG@ 10 average over text datasets
Method
In-Dist. Query
Out-Of-Dist. Query
In-Dist. Label
Out-Of-Dist, Label
NUDGE-M
57.6 (+8.8)
36.6 (-11.6)
72.5 (+24.7)
39.5 (-6.4)
NUDGE-N
60.8 (+12.0)
49.9 (+1.7)
72.5 (+24.6)
46.8 (+1.0)
NUDGE-M+N
58.7 (+9.9)
49.8 (+1.6)
67.4 (+19.6)
46.9 (+1.0)
A+NUDGE-N
60.2 (+11.4)
49.1 (+0.9)
72.9 (+25.0)
47.3 (+1.5)
P+NUDGE-N
61.1 (+12.4)
49.2 (+1.0)
72.0 (+24.1)
47.6 (+1.7)
Adapter
51.0 (+2.3)
47.7 (-0.5)
52.5 (+4.6)
46.6 (+0.8)
PTFT
53.7 (+4.9)
48.2 (0.0)
53.9 (+6.0)
46.0 (+0.1)
No Fine-Tuning 48.8
48.2
47.9
45.9
Table 7:
Generalization results using BGE-S for 3 datasets. Showing increase/decrease in
NDCG@ 10 over No Fine-Tuning (IQ: InD Query. OQ: OoD Query, IL: InD Label, OL: OoD Label)
NQ
NFCorpus
SciFact
Method
IQ
OQ
IL
OL
1Q
OQ
IL
OL
1Q
OQ
IL
OL
NUDGE-M
23.7
-19.2
63.6
-17.4
6.2
0.0
8.0
-11.8
6.0
0.0
12.6
-2.7
NUDGE-N
28.6
1.5
60.6
-2.5
9.1
4.2
12.7
-2.7
12.5
-0.5
25.9
-1.4
NUDGE-M+N
28.5
1.4
60.8
-2.8
8.4
4.4
8.7
-3.3
3.9
0.0
6.5
0.0
A+NUDGE-N
29.8
3.4
62.3
1.5
9.3
4.2
12.1
2.5
7.3
-8.0
27.5
-7.1
P+NUDGE-N
33.6
1.9
56.0
6.5
11.0
1.7
18.0
3.1
8.2
-2.9
20.3
-10.1
Adapter 8.2
4.3
7.1
5.5
0.3
0.3
3.7
5.3
7.3
-8.0
21.6
-5.4
PTFT 15.0
0.8
6.3
11.0
1.7
14.2
5.0
8.0
-2.9
19.7
-10.3
do, in fact. improve OoD accuracy in NQ and NFCorpus datasets. However, the accuracy gains are offset by performance regression in SciFact dataset, where both Adaptor and PTFT show poor OoD generalization, performing much worse than No Fine-Tuning We note that SciFact is the smallest dataset our experiments with less than 1,000 training queries, making generalization particularly difficult. Overall, this shows that the ability of parametric approaches to generalize also comes with the risk of overfitting to the training set.
Regarding NUDGE-N, it is con-paramttric and thus performs similar to No Fine- TiniiTnnng in OoD settings, while it provides significant accuracy boosts in InD settings (around 20% higher accuracy compared with Adaptor or PTFT on InD Label in Table 6). It misses out on the opportunity to generalize in NQ and NFCorpus (performing worse than Adaptor and PTFT in OoD settings in those datasets), but it also does not experience sigmificant accuracy regression on SciFact (and performs better than Adaptor and PTFT on that dataset). For better generalization. NUDGE can be combined with Adaptor and PTFT to inherit their OoD generalization ability while achieving significantly higher accuracies in the InD settings, as evidenced by A+NUDGE-N and P+NUDGE-N methods.
Finally, we note that although NUDGE-M performs well on in-distribution samples, its performance deteriorates OoD queries. To understand this, in Tables G and 7 also included NUDGE-M+N which normalizes the embeddings obtained by NUDGE-M, M. We see that NUDGE- MMN avoids such an accuracy deterioration OoD queries, suggesting that unnormalized embeddings the main reason behind the poor Ool generalization of NUDGE-M. Indeed, when retrieving top-k results using inner product similarity, fine-tuned embeddings with large magnitude can adversely impact the answer to queries that are far from fine-tuned data records, thus causing performance degradation on OoD queries (also see the discussion on the impact of label distribution in Sec.
4.3 IMPACT OF
Fig. shows the impact of y NUDGE variants, obtained by using the update rule for NUDGE- and NUDGE-M, respectively from Eq. 6 and Eq. 3 with different values of 7. Interestingly, for NUDGE-N, similar values of y work well across datasets, suggesting that y relates to inherent characteristics of the embedding space independent of the dataset. However, for NUDGE-M the best value of changes more significantly across datasets. We further discuss in Appendix E. that label distribution can explain this behavior. For label distributions skewed towards a fixed set of labels large 7 does not hurt accuracy, but the opposite observed on heavy tailed label distributions.

---

Published as a conference paper at ICLR 2025
CoCo
ArquAna Pever
NF-Carous Scifact
HotPAQA
NQ
Fick
TriviaQA
(a) NUDGE-M
(b) NUDGE-N
Table 8: Run time using BGE-S
1.0
Time GPU (mins.)
Time CPU
0.8
0.8
Method
NDC0810
(mins.)
0.6-
0.6
NUDGE-M
1.14
7.12
NUDGE-N
2.18
11.0
0.2
0.2
Adaptor
7.99
77.8
PTFT
447
N/A
0.0
1.0
1.5
0.0
0.0
0.3
Figure 2: Impact of y on accuracy (BGE-S for text, CLIP-B for image)
5 RELATED WORK
Decades of research has explored various retrieval methods, including sparse (Robertson et al.) 2009), dense (Karpukhin et al. 2020). late interaction Khattab & Zaharia (2020), and generative retrieval Tay et al. (2022) to name few. Compared with such retrieval paradigms, k-NN retrieval has recently gained incrasedd popularity (see et al. (2024) for a survey of recent studies) due to its simplicity and efficiency. K--N retrieval uses embeddings from pre-trained models, thus avoid- ing the need for extensive training on the dataset in hand, and performs retrieval through a simple vector index look-up avoiding expensive model inference at query time.
This paper focuses on improving k-NN retrieval accuracy given access to a pre-trained embedding model. Related work be divided into two categories. The first category, including this paper, aims to improve the embeddings through fine-tuning for the specific dataset and query workload. fine-tuning the pre-trained model itself, through similar training strategy used during pre-training
is possible. Zhao et al. (2024); Tang et al. (2022); Tam et al. (2022); Liu et al. (2021a); Pires et al. requires access the model parameters, compu- tationally expensive and incurs extra hosting and maintenance costs the fine-tuned models at de- ployment time. A common alternative in practice to train Adaptors (Suvansh Sanjeev [024] [ to transform the output of the models. As our experiments show, adaptors pro- vide limited accuracy gains. On the other hand, our approach, NUDGE, is efficient, model agnostic, does not require hosting and maintaining any model at deployment time, and provides significant accuracy boost. Work in the second category, orthogonal to this paper, modify the retrieval algo- rithm to improve accuracy, e.g., through query rewriting reranking. (see Zhao et al. (2024); ;; Gao et al. (2023) for a survey). Notable examples include Gao et al. (2022); Waan et al. (2023). which rewrite expand queries with hypothetical documents, (Sarthi et al. (2024), which adds summary text chunks to the dataset to improve retrieval, |aachan et al. (2022) which reranks passages based on probability of observing the query, and Lin et al. (2024) which extracts document structure for query answering. Our work could be combined with any of these approaches.
2019); Yu al. (2022 Ma et al. (2024),
Beyond retrieval, our work is related to recent work on fine-tuning pre-trained models for various purposes (Ouyang et al., [2022, Rafailov et al., 2024, ZZiegler al. 2019] Zhang et al.) [024]] Patil et al. (202)) but shows the novel insight that non-parametric fine-tuning of model output, instead of fine-tuning model parameters, can provide significant accuracy improvements. Similar to Ouyang eet al. (2022) ; Rafailov et al.] y Ziegler et al. (2019). our optimization constrains how much model output can change during fine-tuning. In NUDGE, this constraint represents the intuition that among all fine-tuned embeddings that achieve a specific training loss, the one with the least change from non-fine-tune applicable to fine-tuning, the KL--divergence constraint in Ouyang et al. (2022): ZZegler et al. (209 has additional significance due to the use of a reward model.
embedding should be preferred. Although this intuition can be broadly
CONCLUSION
We studied the problem of fine-tuning embeddings to improve A-NN retrieval accuracy. We pre- sented NUDGE, novel non-parametric approach to embedding fine-tuning that is efficient, provides significant accuracy boosts, and does not require any model hosting or maintenance at deployment time. Our experimental results show that NUDGE improves accuracy by up 16.0% compared with existing methods and up to 24.4% compared with no fine-tuning. Future work includes incorporating NUDGE inside vector databases and generating and maintaining query sets for fine-tuning.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
End-to-end source code is available at htttp:://githbb. com/ sze ghami /wwziiggam//ndgee /nudge that downloads the datasets from publiely available sources, runs our methods and the baselines, and reproduces our results. The codebase contains a docker file and instructions to run the code in docker container ensure the code is easily executable and runs with the same configuration to reproduce our results exactly. The code contains any and all data processing steps (as already described in Sec. 44) hyperparameter and other experimental settings (as described in Sec. and
detailed in Appx. E.1 and implementation of all the methods and baselines.
ACKNOWLEDGMENTS
We acknowledge support from grants DGF-2243822, I1S-2129008, IIS- 19407997 and IIS-1940757 awarded by the National Science Foundation, funds from the State of California, funds from the Alfred P. Sloan Foundation, as well as EPIC lab sponsors: G-Research, Adobe, Microsoft, Google, and Sigma Computing.
REFERENCES
Tom Aarsen. Training and Finetuning Embedding Models with Sentence Transformers v3 - hug- gingface.co. https: h/tp:///uggggge wnw.aggginnc.....oooooom cw/blog//rain hntgggginnof.c.c./ooo////aaaaa sennteneeeeeeeeeeeeeee trans formers 2024. Accessed 15-07-2024.
Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems linear relations. Theoretical computer science, 147(1-2):181-210, 1995.
Arguana. ArguAna Data.
datta
2024. Accessed 24-07-2024.
Vera Boteva, Demian Gholipour, Artem Sokolov, and Stefan Riezler. A full-text learning to rank
dataset for medical information retrieval. 2016. URLhttpp:/ wwwp cl i beerg.rgg..
de/- ree--riezles weezlerrppbbl catt inttiion//ppp wttp//paprr////R222111
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint arXiv:2401.0828) 2024.
Ming Du, Arnau Ramisa, Amit Kumar KC, Sampath Chanda, Mengjiao Wang, Neelakandan Rajesh, Shasha Li, Yingchuan Hu, Tao Zhou, Nagashri Lakshminarayana, et al. Amazon shop the look: A visual search system for fashion and home. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 282222833, 2022.
Fever. Fact Extraction and VERification. https://fever..
2024. Accessed 24-07-2024.
Luyu Gao. Xueguang Ma, Jimmy Lin, and Jamie Callan. Precise zero-shot dense retrieval without relevance labels. arXiv preprint arXiv:2212. 222/2.//4999 10496, 2022.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Netrieval-augmentt generation for large language models: A survey. arXiv preprint arXiv:2312. 10997, 2023.
Matthew Henderson, Rami AI-Rfou, Brian Strope, Yun-Hsuan Sung, László Lukács, Ruiqi Guo, Sanjiv Kumar, Balint Miklos, and Ray Kurzweil. Efficient natural language response suggestion for smart reply. arXiv preprint 1rXiv:1705.000
2017.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint arXiv: 1755:0170, 2017.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint 2004 04406, 2020.
Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 39-48, 2020.
11

---

Published as a conference paper at ICLR 2025
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: a benchmark for question answering research. Transactions the Association for Computational Linguistics, 7:453-466, 2019.
Patrick Lewis, Ethan Perez. Alcksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augnae -ugmented genera- tion for nnowledge-intensiv nlp tasks. Advances Neural Information Processing Systems, 33: 9459-9474, 2020.
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models. In International conference on machine learning, pp. 19730-19744 PMLR, 2023a.
Zehan Li, Xin Zhang, Yanzhao Zhang, Dingkun Long, Pengjun Xie, and Meishan Zhang. Towards general text embeddings with multi-stage contrastive learning. arXiv preprint arXiv2330..32811, 2023b.
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects context. In Computer Vision-ECCV 2014: 13th Europeun Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part 13, pp. 740-755. Springer, 2014.
Yiming Lin, Madelon Hulsebos, Ruiying Ma, Shreya Shankar, Sepanta Zeighami, Aditya G Parameswaran, and Eugene Wu. Towards accurate and efficient document analytics with large language models. arXiv preprint arXiv:2405.04674 2024.
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Lam Tam, Zhengxiao Du Zhilin Yang, and Jie Tang. P- tuning v2: Prompt tuning can be comparable to fine-tuning universally across scales and tasks. arXiv preprint arXiv:2110.07600 2021a.
Yiding Liu, Weixue Lu, Suqi Cheng, Daiting Shi, Shuaiqiang Wang. Zhicong Cheng, and Dawei
Yin. Pre-trained language model for web-scale retrieval in baidu search. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 3365-3375, 2021b.
LlamaIndex.
Dataset generation LlamaIndex
docs.llamainexx.i.
https:
generation/ 2024a. Accessed 11 21-07-2024.
dame::///eoo....maaddee.e almaiiddxx
ai/en/ aal.00aaaa.....aaa222a//a/atatt0 2024b. Accessed 15-
07-2024.
Llamalndex.
Llamaindex finetuning loss labels.
Tlama
1lama Lttpr//eweiiiattttto/oo/ooooaaad
11 1lama http:///wwalleeaao/////ttt///aae 20240.0222c2 Accessed | 05--2200
Llamaindex finetuning loss http::///ghhhhhuuc/c//orrr-a-1r /taee//eeeeeooooooraaoooooooo110
Llamalndex.
Llamaindex finetuning
1lama
Ilama www.iiiiexiiii 2024d. Accessed 18-07-2024.
LlamaIndex.
Ilama llama_indees
llmam htnna//nnnnniiiiiioeoo/e//oaaann
adapter. py 144pterrpy+L.14
2024e. Accessed 18-07-2024.
Xueguang Ma, Liang Wang, Nan Yang, Furu Wei, and Jimmy Lin. Fine-tuning llama for multi-stage text retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2421-2423 2024.
12

---

Published as a conference paper at ICLR 2025
Yu Meng. Jiaxin Huang, Yu Zhang, and Jiawei Han. Generating training data with language models: Towards zero-shot language understanding. Advances in Neural Information Processing Systems, 35:462-477, 2022.
Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. Mteb: Massive text embed- ding benchmark. arXiv preprint 100002220.003116 2022. doi: 1048500AR33V222000771666 URL
07316
OpenAI.
2024a. Accessed 18-07-2024.
OpenAL. Fine-tuning, 2024b. Accessed 16-07-2024.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744, 2022.
Shishir G. Patil, Tianjun Zhang, Xin Wang, and Joseph E. Gonzalez. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305. 153334 2023.
Fabio Petroni, Aleksandra Pikus,, Angela Fan, Patrick Lewis, Majid Yazdani, Nicola De Cao, James Thorne Yacine Jermite, Vladimir Karpukhin, Jean Maillard, Vassilis Plachouras, Tim Rocktäschel, and Sebastian Riedel. KILT: a benchmark for knowledge intensive language tasks. In Proceedings of the 2021 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies, pp. 2523-2544, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/202 1.w.a// 200. URL stttps:/aallantholoog"s org/ 2021. naaci main. 200
Telmo Pires, Eva Schlinger, and Dan Garrette. How multilingual is multilingual bert? arXiv preprint 1rXiv: 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pp- 7748-8763.. PMLR, 2021.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
Stephen Robertson, Hugo Zaragoza, et al. The probabilistic relevance framework: Bm25 and be- yond. Foundations and Trends@ in Information Retrieval, 3(4):333-389, 2009.
Devendra Singh Sachan, Mike Lewis, Mandar Joshi, Armen Aghajanyan, Wen-tau Yih, Joelle Pineau, and Luke Zettlemoyer. Improving passage retrieval with zero-shot question generation. arXiv preprint arXiv:2204.0744400 2022.
Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint arXiv:2112.01488, 2021.
Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D Man- ning. Raptor: Recursive abstractive processing for rrganizga retrieval. arXiv preprint 11X8:92401.18059 2024.
SentenceeTransfommers..
Losses:
Sentence Transformers documentation.
https:
sesbert.net/docs/paeeee
html #sentence Saainne__rranee trans formers.orrr..ooo losses htt.anawss...aaaaaaaaaaaaaaaaaaa
2024a. Accessed 18-07-2024.
13

---

Published as a conference paper at ICLR 2025
SentenceeTransfommers.
Losses;
Sentence
Transformers documentation.
https:
7/sbert net //tp://ww....coooooooooooooaaann
html #sentenc transformeze wtt.s:/sooooooooooaaaiaaaaaaaa/. 2024b. Ac-
cessed 18-07-2024.
Anton Troynikov Suvansh Sanjeev. Embedding
com/ http:/ebbddinngddaatttaeeeeeeeee
2024. Accessed 15-07-2024.
Weng Lam Tam, Xiao Liu, Kaixuan Ji, Lilong Xue, Xingjian Zhang, Yuxiao Dong, Jiahua Liu, Maodi Hu, and Jie Tang. Parameter-efficient prompt tuning makes generalized and calibrated neural text retrievers. arXiv preprint arXiv:2207.07085 2022.
Zhengyang Tang, Benyou Wang, and Ting Yao. Dptdr: Deep prompt tuning for dense passage retrieval. arXiv preprint arXiv:2208. 17503, 2022.
Yi Tay, Vinh Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, et al. Transformer memory differentiable search index. Advances in Neural Information Processing Systems, 35:21831-21843, 2022.
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. http:t::: / /oppnrevieieeeeeeeoooeeeeeeeeeer net wo
David Wadden, Shanchuan Lin, Kyle Lo, Lucy Wang, Madeleine van Zuylen, Arman Cohan, and Hannaneh Hajishirzi. Fact or fiction: Verifying scientific claims. In EMNLP. 2020.
Liang Wang. Nan Yang, and Furu Wei. Query2doc: Query expansion with large language models.
arXiv preprint arXiv:2303.07675 2023.
Yujing Wang, Yingyan Hou, Haonan Wang, Ziming Miao, Shibin Wu, Qi Chen, Yuqing Xia, Cheng- min Chi, Guoshuai Zhao, Zheng Liu, et al. A neural corpus indexer for document retrieval. Ad- vances in Neural Information Processing Systems, 15:25600-22614, 2022.
Shitao Xiao, Zheng Liu, Peitian Zhang, and Niklas Muennighoff. C-pack: Packaged resources to advance general chinese embedding, 2023.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question 2018.
answering. arXiv preprint arXiv:1809.000
Peter Young, Alice Lai, Micah Hodosh, and Julia Hockenmaier. From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions. Transactions of the Association for Computational Linguistics, 2:67-78, 2014.
Yue Yu, Chenyan Xiong, Si Sun, Chao Zhang, and Amold Overwijk. Coco-dr: Combating distribu- tion shifts zero-shot dense retrieval with contrastive and distributionally robust learning. arXiv preprint 22..::2220...2211111 2022.
Tianjun Zhang, Shishir G Patil, Naman Jain, Sheng Shen, Matei Zaharia. Ion Stoica, and Joseph E Gonzalez. Raft: Adapting language model to domain specific rag. arXiv preprint MrXiv:2403.10131 2024.
Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. Dense text retricval based on pretrained language models: A survey. ACM Transactions on Information Systems, 42(4):1-60) 2024.
Chunting Zhou, Pengfei Liu, Puxin Xu, Srinivasan Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu. Lili Yu, et al. Lima: Less is more for alignment. Advances in Neural Information Processing Systems, 36, 2024.
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint 1895591909.08593, 2019.
14

---

Published as a conference paper at ICLR 2025
A
APPENDIX OVERVIEW
This appendix organized as follows:
Appx.
contains the proofs of the theoretical results in the paper.
Appx.
discusses other NUDGE variants.
Appx.
discusses the extension of NUDGE multi-label settings.
Appx.
provides details about the experimental setting and additional experiments.
B PROOFS
respectively, provide the proofs of Theorems, 5 The proofs of technical lemmas are presented in Appx. B.4
Appx. B. B.3
B.
PROOF OF THEOREM
We show a reduction from homogeneous maximum feasible linear subsystem, Max-FLS, shown to be XP-Hard in Amaldi & Kann (195). We first formally state the decision version of the problem.
Problem (Homogeneous MaS-F Given linear system Ax < O, where size an integer K with < K < s, does there exist solution E RD satisfying at least K inequalities of the system?
size s t, and
We show reduction from Homogeneous Max-FLS to the decision version of MaxA-EFT, The decision version of MaxA-Ei A-FF asks whether there exists A such that the training accuracy is at least K, i.e., whether least K different I, (A), A), E [NT] can be satisfied.
Given A, the reduction defines an instance MaxA-EFT by specifying D. Q. and Y. Specifically, let Q = A. D = 0 R (i.e., a 2 x t matrix only consisting of zeros) and Y = {Y Y. Y, = 0 Vi E [s] (i.e., this instance only has 2 data records, embedding dimension t and there are training queries).
We next show that there exists A so that the training accuracy of MaxA-EFT least K if and only if there exists a solution æ to Homogeneous Max-FLS satisfying at least K inequalities of the system.
Observe that, by the above construction, (A) is satisfied and only
Q: (A, Ao) < O.
Suppose the training accuracy is at least K for some A. Let A1- and let (.,, ig) be the index of K training samples answered correctly. Thus, we have A, x < for all i (hi,..., showing the existing K' inequalities the subsystem that are satisfied.
Conversely, assume some æ satisfies at least K inequalities in the subsystem. Let Ao = 0 and A Σ. We have that least K inequalities in
QA < 0
are satisfied, that the training accuracy is least K. The reduction is polynomial time, thus showing MaxA-EFT is NP-hard.
B.2 PROOF OF THEOREM 2
Setup. Recall that for any E [n].
G Σ I| ii= jE(nT]
so that
arg max
Σ CQ - Ayr) arg max AERaxd 1EIN
Σ G. G. A; arg max
Σ
G. A:.
xdRaxd [E(rr]
A Aeduxd
iE]n).|[..11
The proofs here use the above formulation for Maxs-M Moreover, we set A = 0 for any i where ||, 0, given that they do not appear in the above objective. Note that even when A 0 for any E [n]. the i-th record still influences the BiMax-XX M objective and needs to be taken into account when solving the outer optimization in BiMax-M.
15

---

Published as a conference paper at ICLR 2025
Algorithm NUDGE-M algorithm
Require: A training set Q y validation set Q", yv and data embeddings D Ensure: Fine-tuned data embeddingg
1: G; + EzEnn) Lli = 1 for all i E [n]
2: Calculate St, for all [nv]: [n]
3: ++0
4: for in [nv] do
5: if Si.j > S,yY for any E E [n] YY 1xxy - GGs- =0} then
6: Continue
T = 0 so skip the query
7: P-fje [n] Y Gury Gig 0}
8:
N - [E M G.y. - Gi. < <0}
S. S
S.y-
9:
u t minjeN F..y- +t maxjEP Bayy Gi,5
10:
if 0 < then
11:
Continue
44 = so skip the query
12:
I < (max 0}, u)
13:
Lappend(1.)
14: 7" < arg maxy Ener 11 E 1,]
15: D. <- D; [ [||| 0 ف
16: return D
Finding MaxS-M. We first find MaxS M by solving the following optimization problem:
Ene(n) G; A;
arg max A AaR
t.
|Ai|| E [n].
In this problem, the constraints independent for each [n], ||G * O. and the objective is simply summation across G; .D;;+ + A;) values, so that solution is optimal for this problem
if and only if for each i [m). A is optimal solution to
arg max AER
G: A
S. t.
A
S %
Solving this problem, we have:
Lemma 1. For any i E [n], whenever
|G+|]] # 0 and 7 2 0, the optimal solution to
arg min AER 8. t.
G A;
A
S 7
G:
A 7 G
Solving BiMax-M. The goal is now to find parameter 7 2 0 such that the maximum number of validation queries are answered correctly. Observe that, by definition, the i-th validation query, i [nv] is correctly answered when Vj [nv] Y...
Gyy
G
Q Dr. + +[[[[| Gry # 0
Q D, + o
G
GG
where, we abuse notation and assume
G| G,
0f |G
0 for any j. Define
G
G = ||]]]| +
and Sr, = Q D
G
16

---

Published as a conference paper at ICLR 2025
for any j [n]. Thus, we have that the i-th validation query is answered correctly when Vj [nv] \ Y,
(-00, Sus Sury guvvy -hi5
if G,yy - -1. <0
Sty S,,,
r ve
P,,y -biy ,00 R,
if yyyy 9 >0
if G.Y. Gr. 0 and St.j - S.yy < 0
0,
otherwise.
J. defines an interval in so that 7 Ji means the correct answer the i-th validation query has higher similarity to the query compared with the j-th data record, for j + Y, Thus, answer the i-th query correctly, we must have E I; = jjrry' Jt.j. To maximize the number of queries answered correctly, after finding I; for all i, we simply need to find ry value that intersects the most number of intervals among /1 /,,..: Jay: i.e., arg max, Σner I/ T.), where / (7,, Jay )- Finding point where maximum intervals overlap is basic algorithmic problem and can be done by a single iteration through the intervals after sorting their start and end points.
NUDGE-M. Alg. presents NUDGE-M, which formalizes the above procedure, and also incorpo- rates the constraint Y 2 O. Lines 4 find the intervals 4, Vi E [nv] and add it list (inter- section of half intervals can be found by calculating the maximum of lower bounds and minimum of upper bounds of the intervals, done in lines 7..) The algorithm returns new data embeddings by simply performing a single addition.
Time complexity. Alg. can be implemented so that lines 9 with single pass over the dataset. Therefore, finding 4 for all queries (lines 4 [3) take O(ny X n2 x d). Calculating takes time Onn x d). Finding 7 in line 14 is the basic problem of finding the maximum number of over- lapping ranges and can be done in Ony log(ny)). by first sorting the ranges in / based on their lower bound and iteratively traversing the sorted list and keeping track of the number of overlapping ranges. Thus, Alg. 1 can be implemented O(n x + log(nv) + noy x d).
B.3 PROOF THEOREM 3
Setup. In the discussion below, for simplicity, we assume for any i [n] G;
D; 2 Although the discussion below can be extended to consider G; D, < O, the results will be more tedious (see Lemma 2). Moreover, in practice we expect G, D; 2 O to hold, as otherwise queries and their correct answers will have negative similarity suggesting either a poor training dataset pre- trained embedding model. We simply set G; = 0 whenever G. D; < 0. Morcover, similar to Appx. B.2 rewrite the MaxS-N objective
arg max AcRexd iE(nr)
Σ of (Dy, + AYT)
arg max
G. = arg max AeRaxd
Σ
G. A.
A AERUXE
and set A normalized, (i.e.. |I = 1, vi E (n]), or we otherwise normalize them.
for any i where |G O. Furthermore, assume the embeddings D;
Finding MaxS-N. We first find MaxS-N(7) by solving the following optimization problem:
arg max Eie(n G. D; AERox
A % Vi E
A
+ A = 1, E [n].
In this problem, the constraints are independent for each é E [n]. and the objective is simply a summation across G; -D; A;) values, so that solution A is optimal for this problem if and only if for each E [n]. A is an optimal solution to
arg max
G D;
AERa
S.
A 2 < 7
A + D 1.
Solving this problem, we have:
17

---

Published as a conference paper at ICLR 2025
Lemma 2. For any E [n]. let 0, be the angle between G, and D:. Whenever 02 10, 0,
| = 1 and || # the optimal solution to the optimization problem
arg min AERa
G A
t.
AIl S 7 D
A
=1,
G [Glll
Dj:
cos 0, 2 1
A
74 GG GD)
Di, otherwise.
G| D.)
For simplicity of notation, we denote by Z, Rd the vector
G; D; G.
|G; (D; Dil
We also denote by Zt, = Q.- Zj. by D.j = Q D, and by Gt. = I||G,|| * 0]Q"" all i [nv],j E [n].
G for G
Solving BiMax-N. Next, consider solving BiMax-N, Vj E [n]. Substituting A into the defini- tion of I. (A for each i E [nv]. IV (A 1 if and only if for all j E [n] Y
Q (Dyy + y v. Q (D) + A]).
First, consider the case simpler setting when |[ * 0 for all j E [n]. Let 0.j = max 0, and
a.j min min 0z}. Substituting the values from Lemma 2 have Eq, 7 equivalent
(1 ,yy + V114-1) Z,xy > (1 (1- D). + 11 7) Zijr
if < 2 2 cos cos ly.
(1- - --DDDry + v1(1-1) v.y," > gi.j
if 7 2 2 - 2 cos By! j
? < 2 cos yyp i pry < <0,
Pexyy > -1-3)D,, + 11(4-2) Zi.j
if 7 > 2 - 2 2006 0y. .j'
? < cos 0yy Oyy 0j
Gaxy > 9i.5
otherwise.
(8)
Observe that finding the values o for which the inequalities in Eq hold requires solving inequal- ities of the form a / - 7) + by + > 0, for some a, 6, E R.
Lemma 3. Let f(y) = / -744-7)-0 7)+ by + cfor a, b, E We say there are k roots, 7o. k if there exists is distinct 7/S E (0, 4) for which f(r) = 0. We must have k E 1,,1, if two roots exist, we have
2a bc avo
2a² bc avo
for 4a² 4bc a²c²
70 a² + b2
m1
a² + b²
and if only one root exists
2a² be avo 2a
be + avo
9o E
a² + b2
a² + b²
Moreover, for any 7 E (0, 4). (()) > 0 holds if and only if
(0,4)
if zero roots and
(c
(c 0,b > 0) (c 0,a 0))
0
if zero roots and
(c < 0 or (c - 0, < 0) or (c= 0, 5))
(10, 71)
if two roots and < 0
e
99)
70) U (7,4)
two roots and c > 0
(0,
if root and
0 0, a 0)
(70,
if one root and (c < 0 or
0, a 0).
18

---

Published as a conference paper at ICLR 2025
Thus, for the i-th query and the j-th data record, i E j E [n] Y.V, we can use Eq. 9 together with Eq. 8 to obtain a set I, C (0, 4) such that Eq. 7 holds if and only if y E I. Moreover, 4,, will consist of at most 3 intervals in S (0, 4). Let 1; Delnn)yy Lig. and note that the i-th query will be answered accurately and only y J.. Finally, y arg max, Eiginv] I[ E Ii] is an optimal solution the MAxSS problem.
Now whenever |G = 0 for any j E [m]. Eq. changes since we need to also consider A = O,
A or both. Each case leads to a similar set of inequalities to Eq. 8 which are similarly solved using Lemm 3 Moreover, we calculate validation accuracy separately Tor when y 0.
NUDGE-N. NUDGE-N follows the above procedure. It first calculates G and Z, so that for the i-th query, and j-th data points, j # Y.V. applying Lemma 3 to Eq. 8 gives Jig- Then, it computes T; by single pass over Ji, values, and finally finds y value that intersects most 's by sorting their beginning and end and iteration through the list.
Time Complexity. Calculating G takes time O(drr), and Z takes O(dn). Then, for the i-th query, finds I which takes ((dd), since each Is, only contains constant number of intervals and can be computed in (d). Finally, finding 7 that intersects the most intervals, can be done in Onny logny. n.). Thus, in total, NUDGE-N takes total of O(nv(n(v) + nv) + nrd).
B.4 PROOF OF TECHNICAL LEMMAS
B.4.1 PROOF OF LEMMA
If 0 the only feasible, and therefore optimal, solution is A 0. Next, consider y > 0. Observe that the optimization problem is convex, so we find A, values that satisfy the KKT conditions which, since the Slater's condition holds whenever y > 0, provide necessary and sufficient conditions for optimality.
We have that the Lagrangian is
1 G; D,+ 2 yu(1 A 72))
so that the KKT conditions are G. + ~A; 0.
(10)
M(|| |1 - - O, u20 0.
(11)
(12)
If fa 0, we must have ||G,] O, which is contradiction. Thus, p 0, and
A 1 72 0.
(13)
From Eq. 10
G
A
(14)
Substituting this into Eq. 13 and since f >> 0, we have
|
/4 7
and substituting back into Eq. 14 have
G: A = ? G
B.4.2 PROOF OF LEMMA
We replace A + D = 1 with A; + Dill < so that the optimization is over convex set, and solve the problem with A + D S 1 constraint. As we will see, the only solution to the problem will have || + DiIl = 1. implying that it is the optimal solution to the original problem as well.
Thus, consider the convex problem with | D.ll S I constraint, or equivalantly A D z 1.
We find A, values that satisfy the KKT conditions, which, since the Slater's 's condition holds when- ever 7 0, provide necessary and sufficient conditions for optimality.
19

---

Published as a conference paper at ICLR 2025
We have that the Lagrangian is
H, - D; 2 ( -7) + + A :
+24, -:),,
so that the KKT conditions are
G + ; + > + AD;
(15)
X( A I + 2A, Dí) = O,
(16)
1 |l 7) O,
(17)
| 112 S
(18)
| 1| + 2A; D, S 0,
(19)
μ1, X 2 0,
(20)
where Eq. 15 is obtained by setting the gradient of the Lagrangian to zero, and Eq. 19 and 16
obtained by substituting
D. + A 11 |
|| 1
2 D, = A 1| 2A D,,
since
|
=
To find the points satisfying all Eq. 15 20 we consider setting depending on whether À = 0 or
1 0 not.
Case I, \ 0, f 0. Substituting
and = Eq. we have G; = Thus, no solution
with x = 0 and μ = 0 exists since G; + O.
Case 2, > 0, μ 0. Having À 0 and μ O, have from Eq. 15
# G.,
substituting which into Eq. 17 with w have
| ? 2
G
|[
and therefore A
VTGGT (KKT conditions become similar to the ones in Theorem 2) Because
G.
>> O, we must have A || due to Eq.
17
so that from Eq. 19 we have
G:
D. 0.
|G
Y + 2/7 cos 0, < 0,
where 0; the angle between G, and D.. Thus, we must have
cos 0,
2
Since cos 0, 2 0 and 7 > 0 by assumption, there are no solutions with À = 0, fz > 0. Case 3, À > 0, 0. Substituting 0 in Eq.
15
we have
G, AD;
A ;
X
Substituting this in Eq. 16 we have
G, XD;
G, >D;
1
D; 0,
X
| + X²
2XG;
D. +2A(G D:- = =0
implying, since À > 0,
A >= -=
and therefore
G D,.
A; =
GG
20

---

Published as a conference paper at ICLR 2025
Note that to satisfy Eq. 18 must have
G. ||lll|
G. |G, (1G.
D.)
D,) S/
simplifying which we have
cos 0, 2 7
To summarize, showed that setting
G: Dj, # = 0, and A = |G,
A
|G,1|
satisfy all KKT conditions whenever cos 0; 2 1 z.2
Case 4, À > 0, n > From Eq. 15 we have
A G; - AD;
(21)
X
and since | - 0, Eq. 16 simplifies to 7 +22 D; 0, so that
G: D.D, AD; D:
2
A+ P.
Therefore,
# X G. Dr X.
(22)
7
Substituting this in Eq. 21 we have
- -D
(23)
2 G. Dj
Now, substituting Eq. 23 in Eq. get
1(> G: D.Y² (G
GGi - AD;) (G: - (D)) =7
So
7 [|GG 2 X² 2XG, D2) = X2 + (G. D,)² -2GG, D,.
Rearranging, obtain a quadratic equation in X,
|G (7 4 cos² 0,) = 0, ?
x²
where we have used the fact that have
(D, G,)2 = || cos? 2 0,. Solving the equation and simplifying
Y
A = D, G, + | sin 0
(24)
Note that we must also have μ > 0, so substituting Eq. 24 into Eq. 22 and rearranging we must have
7 7 2 1) D; G, >0,
G 0 V 4-7
7 2
ssin 8 V 4 7-7-
1) > cos
(25)
Observe that, for 0, E [0, 3]. both sin 0g and cos 02 are non-negative, so that when 7 < 2 only the positive branch is able to satisfy Eq. 25 In this case, we have
7
= D, G. + |G sin 0
(26)
V 4 4-7
Note that
/ 7
||:||| cos 0
|| sin 0, V 4 4-
0.
21

---

Published as a conference paper at ICLR 2025
for 0: E [0, 21. and thus X > 0 is satisfied. Simplifying Eq. 25
observe that for 8; E
[0,
21 and
0 < 7 2,
(2 7)2 sin 11 7(4 -7)
7(4 - 7) (2 7)- 7)2
> cos0, = 0, > arctan(
cos 0; <
v 11
214-21 (2-1)-
(27)
To summarize, taking the positive branch Eq. 24 we showed that
A 2 (G,
(D, G.)
Di.
2 2| sin 0:
2
A = D, G. + |G; sin 0:.
and
4 4-
(2 7)2
/ | sin sin0:
D: Gi
7/4 7)
satisfy the KKT conditions whenever
cos 0z <
2
Finally, consider the negative branch in Eq. 24 and
> 2. To have μ > 0, following an argument
similar to Eq. 27 must have
cos 02 < 211
and similarly for X > 0, we must have
|G cos A. || sin 0
7 >0
= 0, < arctan
4 A-7
cos 0, > 2 zV..
4
However, x |1 3 for all > [2.4]. which implies μ > 0 and X 0 cannot hold at the same
time in this case. Finally, observe that ||, - (D; D.ll = || sin 0,.
B.4.3 PROOF OF LEMMA
We first find y values where f(7) = 0. Observe that
r -)) + by + c 0 a²2(4- 161- (by cc)²= so that a²>(4 - (by + c)2
necessary for [(7) = 0. Moreover solving the quadratic inequality, a² d2>((4 7) c)2 = 0 iff r 170,11 } where
70 2a 2 be avo
71 2a - bc avo
for = 4a² 4bc a²c².
a2 + 12
a² + 12
Thus, 7 E (70, 71 is necessary for f(>) = 0. which proves the first part of the lemma.
The proof of the rest of the lemma uses the above, the fact that f is continuous, in addition to the following facts:
e <> 0> f(0) > 0, e< 0 f() <
(28)
0,6 0 S(4) > 0, c= 0=
{(4) <
(29)
f has at most local extrema, which is a maximum if a > and a minimum if a < 0
(30)
If there are zero roots, f()) > 0 either for all of (0, 4) or none of it, which can be determined by checking the function value 0 or 4 using Eq. 28 and 29 A 0 or b of If c b 0, then we
can solve f(7) > 0 based on whether the function has minimum or maximum using Eq. 30 or is a constant when a 0.
If there is one root, Yuu then f()) is either positive after To or before it. If c * 0. we can find this by checking f0) using Eq. 28 If c O, then f()) has two roots, at 0 and %oo and f(r) 0 can be determined based on whether the function has a minimum or maximum using Eq. 30 Both c and a cannot be zero, because the function by cannot be zero both ? O and 7 To for no * 0.
22

---

Published as a conference paper at ICLR 2025
If there are two roots, then f()) 0 either between the two roots, outside the interval between the two roots, which can be checked based on f(0) using Eq 28 c cannot be zero because f(n) cannot be zero at y y Yo and y "/1 for 3 distinct values to 0, Yo: 71-
C OTHER NUDGE VARIANTS
C.1 SPARSITY CONSTRAINT
In NUDGE, how embeddings are fine-tuned (i.e., the form of the matrix A) depends on how con- straints defined in the formulation of the constrained non-parametric optimization problem. Our discussion so far considers constraints on the L2 norm of the change in embedding (in Max op- timization problem in Sec. (.2.T] and constraints that force created embeddings to be normalized (in MaxS-N optimization problem in Sec. 3.2.2). Here, instead of bounding the L2 norm, we consider bounding the LI norm of embedding changes, As we see next, bounding the LI norm creates sparse embedding updates.
Consider the MaxS optimization problem but with bounds LI norm instead of L2 norm. We obtain the following optimization problem, denoted as MaxS-5.
MaxS-S(7) arg
Σ o (Dyr Ay,)
(E((T)
A R | S [n).
Where |1-I11 is the L1 norm. A A E MaxS-S(7)) changes data embeddings by at most y now in terms of the LI norm, while maximizing the similarity between training queries and their ground- truth answer. We have that"
Lemma 4. The optimal solution MaxS-S(y). A is
b (ysign(Gr..) E \ for all i E [m] and j E [d], where G' is defined as in Eq.
0
where 5 arg max G.yl jE(d
(31)
j otherwise,
Proof. Observe that for any E [m]. we have that, A7. the optimal embedding change in MaxS-S(n) for the i data record, is the optimal solution to
arg max A.ER
G. A;
s.t.
| S.y
A? defined in Eq. 31 is feasible solution to above. Moreover, G: A7 = maxje(d G., Now consider any feasible solution A,,
A. = G. S Gasll
Σ ]E[d]
S max G JEld]
S max
Gaay = G. A
JE[d]
JE(d]
jE[d]
Thus, AT is an optimal solution.
We refer to fine-tuning with Eq. 31 as NUDGE-S. Observe that A as defined in Eq. 31 is very sparse, with only one non-zero entry per row. This means updating data embeddings as D A performs sparse update. It specifically only changes the embedding of a single dimension of every data record. As our experiments in Sec. E.6 this since we use dense embeddings. Since the emheddings are dense, large modifications on a single dimension independent other dimensions will likely lead poor embeddings. This is because we expect embedding dimensions to be co-dependent, and large modifications in single embedding dimension can distort the semanties of the embedding space. Nonetheless, we expect the above to be beneficial if the embedding space is sparse. We provide an experimental analysis of NUDGE-S Appx. E.6
beneficial in most settings consider,
Overall, the above shows how constraints shape the embedding updates performed by NUDGE, where different constraints can lead to different fine-tuning update rules (compare Eq. 3T with Eqs.
Recall that X,, is the element in the i-th and j-th column of X
23

---

Published as a conference paper at ICLR 2025
and 6nd
We expect different constraint forms to be beneficial in different settings. depending the geometry of the embedding space. NUDGE, through the use of constraints in its optimization, pro- vides framework incorporate knowledge about the embedding space in the fine-tuning process.
C.2 ITERATIVE VARIANTS
Besides defining constraint optimization problem variants within the NUDGE family, here, we also consider NUDGE variants that use different optimization methods to solve the optimization prob- lem. We consider variants that use iterative optimization so that they are more flexible in their optimization approach but do not provide closed-fore optimal solutions.
Specifically, the NUDGE variants discussed in the paper can difficult to implement (especially NUDGE-N) and are not flexible, e.g., considering other accuracy metrics constraints requires a new theoretical study. Here, we discuss simple NUDGE variants that use gradient descent to optimize MaxS-FFT (e-g., solve the inner optimization in BiMax-M) and hyperparameter tuning to optimize MaxA-EFT (e.g., to solve the outer optimization BiMax-M). This approaches can be less efficient and suboptimal, but can still provide accurate solutions, and are simple and flexible. In such NUDGE variants, the learning rate and number of iterations act as knobs constraining how much the embeddings change.
NUDGE-IM. First, note that MaxS-EFT equivalent to minimizing the following loss
-= Σ QDy + Av.).
(32)
<E(NT]
NUDGE-IM performs gradient descent loss in Eq. 32 with learning rate for iterations (a and determined through hyperparameter tuning to maximize validation accuracy) with normalized gradients:
VAC
(0) < O,
A
(1) (1-1)
&
Lemma 5. NUDGE-IM finds solution equal to NUDGE-M, and thus optimally solves BiMax-M, whenever at = y", where 7 is the optimal y value found by NUDGE-M.
Proof. Observe that G; = AV,,C and therefore the gradient remains constant through optimiza- tion. Thus, after iterations, have
G.
atI[G + 0
G.I.I
Thus, setting 7" = at, we obtain the same results as NUDGE-M.
The above lemma implies using gradient descent with suitable a and can also provide accurate solutions, but at the cost of efficiency due iterative updates and hyperparameter tuning (instead of using the closed-form solutions), and the added challenge of finding suitable and t. Appx. E.5 presents an experimental study these trade-offs.
NUDGE-IN. Another alternative is NUDGE-IN, an iteratively normalized NUDGE variant. NUDGE-IN is similar to NUDGE-IM but normalizes the embeddings after every update:
(t-)
Va.C
D (0) + D.. D + D
[VA
Vi E [n].
V
[V
NUDGE-IN ensure the fine-tuned embeddings are normalized similar to NUDGE-N. Although, there is no theoretical equivalency between solutions of NUDGE-IN and NUDGE-N, we ob- served similar accuracy in practice. Meanwhile, NUDGE-IN is less efficient but simpler to imple- ment.
D MULTI-LABEL FORMULATION
In the main body of the paper, we provided fine-tuning solutions assuming each query has a single ground-truth answer. Here, we discuss how our results can be extended to multi-label setting. We first formalize the problem setting with multiple labels and then discuss how to extend our results.
Ground- Ground-Truth Answers. For a query, q. its ground-truth answer is a ranking of the data records so that the highest-ranked records the most related to the query. This ranking be represented
24

---

Published as a conference paper at ICLR 2025
Table 9: NDCG@ 10 results for GTE-L on text datasets
Method
ArguAna
Fever
HotpotQA
NF-Corpus
NQ
SciFact
TriviaQA
NUDGE-M
52.4 (+0)
95.6 (+8.6)
60.8 (+10.3)
45.2 (+7.9)
50.6 (+9.5)
82.4 (+7.9)
40.1 (+9.9)
NUDGE-N
52.4 (+0)
93.1 (+6.1)
57.0 (+6.4)
46,9 (+9.6)
56.2 (+15.1)
88.3 (+13.8)
45.0 (+14.7)
Adapter
52.4 (+0)
87.0 (+0)
53.0 (+2.5)
38.5 (+1.1)
41.1 (+0)
87.8 (+13.4)
30.2 (+0)
No Fine-Tuning
52.4
87.0
50.5
37.4
41.1
74.5
30.2
Table 10: NDCG@ 10 results for TE3-L on text datasets
Method
ArguAna
Fever
HotpotQA
NF-Corpus
NQ
SciFact
TriviaQA
NUDGE-M
42.4 (+0.1)
94.8 (+14.8)
65.2 (+14.2)
50.7 (+10.5)
56.6 (+13.0)
86.5 (+11.1)
46.1 (+13.1)
NUDGE-N
42.4 (+0.1)
93.1 (+13.2)
63.4 (+12.3)
49.0 (+8.7)
59.6 (+16.0)
89.8 (+14.4)
50.1 (+17.1)
Adapter
41.7 (-0.6)
88.7 (+8.8)
54.5 (+3.4)
42.1 (+1.8)
42.4 (-1.2)
90.9 (+15.5)
32.7 (-0.3)
No Fine-Tuning 42.3
79.9
51.0
40.2
43.6
75.4
33.0
using relevance scores, which, for each data record, quantifies how related the record is the query (relevance score zero means the record is unrelated). The ground-truth ranking can be obtained by sorting the data records based on their relevance scores. More formally, we represent the ground- truth ranking for a query with a ground-truth rank index set, (ri....;Tpp for some integer p denoting the number of data records that are related to the query; the remaining records are not relate to the query. This means that record Dy, has relevance r; to the query, and any record index not present in y is assumed to have zero relevance score. Thus, sorting the dataset based on gives the ground-truth answer to the query. We drop the set r if y = 1, or if r = ... = rp-
{,,,,.., Up. and corresponding
ground-truth relevance score set
Fine- Tuninu Query Sets. For fine-tuning, a query set and corresponding ground-truth answers are available, consisting of queries Q and ground-trut truth answer sets Y, R, where for the j-th query ūj E Q. Y2 is the ground-truth index set and R is the ground-truie -ruth relevance this training set is split into two, training set ,T,YT, R² and validation set QV YV Ry, with ny and ny queries respectively. Similar to single label setting, let Q" E RR xd and QV E R xd be matrices containing embeddings for training and validation queries.
set for qj. We assume
Problem Formulation. Both MaxS-EFT and MaxA-EFT can be modified to utilize multiple labels. For MaxS-EFT we can change the objective to Eie[or] Evr Q -D,, + Dj-), where sum-
mation over Y can optionally be weighted by relevance scores. For MaxA-EFT, we can adjust the inequalities in the definition of the correct answer to query (i.e., Eq. D so that for query q with two relevance scores r1 and r2, F1 > r2, and for R1 and R2 containing document indexes with 7 and r2 relevance scores, we say q is answered correctly when
(D, + A.)
(Dj + A,), i i RI,j E R2.
(33)
NUDGE. To solve BiMax-M and BiMax-N, observe that the above modifications cause marginal changes for MaxS and MaxS-N. and only require modifying the definition of G in the corre- sponding optimal solutions. However, the solutions to the outer optimization problem in BiMax-M and BiMax-N require further modifications since now a different set of inequalities needs to be solved to find the range of for which query is answered correctly. However, each inequality still of the same form as before (compare Eq, 33 with Eq. [], and thus, the same methodology applies.
E ADDITIONAL EXPERIMENTS AND DETAILS
Here we present additional experimental details and results:
Appx. F.1 discussed details on the implementation of Adaptor and PTFT, including hyper- parameter tuning, loss, and efficiency considerations.
Appx.
contains detailed per dataset results summarized in the paper's main body.
Appx.
presents experiments the training processes of Adaptors and PTFT to under-
stand their failure modes.
Appx.
E.4
provides ablation study of various normalization methods in NUDGE.
25

---

Published as a conference paper at ICLR 2025
Appx.
E.5
provides experimental comparison between NUDGE-M and its corresponding
iterative variant NUDGE-IM, IM.
Appx.
E.6
provides an experimental evaluation of alternative constraint variants.
Appx.
7
studies the impact noise on query embeddings during fine-tuning.
Appx.
studies combining NUDGE with query rewriting methods.
Appx.
presents additional out-of-distribution generalization results.
Appx.
E.
presents
comparing CPU and GPU runtimes.
Appx.
presents an ablation study of NUDGE.
Appx.
studies the impact of label distribution on NUDGE's accuracy.
E.1 ADAPTOR AND PTFT DETAILS AND AYPER-PARAMETER TUNING
-L loss. The results presented with -L suffix use modified version of MNR loss. The MNR loss, for a batch of b queries. QB, and positive examples (i.e., data records that the correct answer to queries) DB, where D; is positive example for Q; for any i [b), treats every other example in the batch as negative examples for Qú Let St, = Q: |1
Q. for any i,j E [b]. Then, MNR loss minimizes
S..
LMNA =
Σ log
Σ EjEl| e
iE[b
for some temperature parameter т. Our modified loss, for the i-th query, ignores samples, j. for which Siyj < 17 for some threshold 7y:
T(S 2 n E ISS,, 2 n/e=S..>
L' C'= log SE[b]
This follows the intuition that, at the fine-tuning stage, the model only needs to get better at dis- tinguishing between records that have high similarity and is already accurate enough separate relevant from non-relevant items. T and are related and are jointly set through hyperparameter tuning.
Modeling details and byper-parameter Tuning, For both Adaptor and PTFT, we did hyperparam- eter tuning determine the learning rate (and use of scheduler), batch size (although for PTFT it is bottlenecked by GPU memory size), number of training steps, model architecture and initializa- tion (for Adaptor, we tried linear up to 8 layer MLPs) and which layers train (for PTFT, tried training the full model or training the last layer), and the choice and parameters of the loss function. We only performed ssper-parameter tuning for BGE-S, and used the resulting paper-parameters for other models. We note that the choice of initialization is particularly important for Adaptor, and we observed a significant advantage to ensuring that at initialization, Adaptor is an identity function. For single-layer adaptor, this can be achieved by setting the weight matrix to the identity matrix (also done by Llama Index (LlamaIndex 2024c)). For multi-layer adaptors, using ReL.U activa- tion, assuming queries are normalized (so that a query input 2 -1), we achieve this by setting the weights identity, the bias of first layer to +1, the bias of last layer to -1 and other biases to O. We are unaware of this initialization being used by existing work for multi-layer adaptors, and we observed benefits to using this initialization over initialization that modify the embeddings at initialization (e.g., setting all biases to 0).
Efficient Implementation. For Adaptor, our implementation based on Llama Index LlamaIndex (024b) and for PTFT based on Sentence Transformers Aarsen (2024), but with additional consid- erations for initialization (for Adaptor, see above), loss function (see above) and efficiency. We observed that validation passes (for model checkpointing) often take longer than training passes (be- cause the number of data records is often more than the number of training queries in our datasets), we used hyperparameter tuning to set the validation frequency to as low as possible without affect- ing final accuracy. For Adptor, when applying Adaptor only to queries (so that data records don't t get embedded), we also used vector index (Faiss library Douze et al. (2024h) but did not observe any speed-ups (perhaps due to the already parallelizable nature of answering batched queries, and that we only do top-1 lookup during validation). For PTFT, single validation pass, which requires re-embedding the entire dataset, can take more than an hour on our large datasets (Fever, NQ, Trivi- aQA, HotpotQA). To reduce the computational cost, for each validation query, we selected its top-10
26

---

Published as a conference paper at ICLR 2025
Table 11: NDCG@ results for CLIP-B on im-
Table 12: NDCG@ 10 results for CLIP-L on im- age datasets
age datasets
Method
COCO
Flickr
Method
COCO
Flickr
NUDGE-M
29.7 (+11.6)
52.2 (+16.5)
NUDGE-M
31.4 (+9.0)
55.0 (+12.5)
NUDGE-N
29.9 (+11.9)
52.4 (+16.7)
NUDGE-N
31.5 (+9.1)
55.1 (+12.6)
Adapter
20.0 (+2.0)
39.8 (44.1)
Adapter
25.0 (+2.6)
48.0 (+5.5)
No FFine-Tuning
18.0
35.7
No Fine-Tuning
22.4
42.5
Adagtoor, V
Adaptor, T
NUDCE4M,
NUDGE-IM, T
PTFLV
(e) NE- Corpus
(b) NQ
(c) SciFact
1.0
0.9-
0.6-
0.8
1603
0.6-
0.4
0.5
0.4
0.2
0.5
20
40
60
80
100
0
20
40
60
100
20
40
80
100
% of Training Duration
of Training Duration
75
of Traaninn Duration
Figure 3: Training and validation accuracy for BGE-S three datasets
answers based on the pre-trained model and only included those (in addition to ground-truth train- ing and validation answers) data records in the dataset for validation. This provided more than 10x speed-up for validation on large datasets, and we observed similar final accuracy (intuitively, this removes data records from validation that, unless the pre-trained model significantly changes, unlikely to impact validation accuracy). Finally, we use early stopping validation accuracy drops by more than 5% compared with the maximum it had achieved.
E.2 OTHER PER DATASET RESULTS
Tables 12 present the per dataset results for the embedding models GTE-L, TE3-L, CLIP-B and
CLIP-L. The tables (in addition to Table 5) present the detailed results from which Tables 3 4 generated.
E.3 TRAINING AND VALIDATION ACCURACY DURING TRAINING
To better understand the differences and failure modes of the approaches, Fig. 3 shows the validation and training accuracy for Adaptor, PTFT and NUDGE-IM, where T and respectively signify training and validation sets.
Fig. (a) and (b) show two failure modes for Adaptor, overfitting, and underfitting. Specifically, Fig. 3 (a) shows NUDGE provides much better validation accuracy compared with Adaptors the same training accuracy, suggesting that Adaptor simply overfits to the training set instead of learning generalizable patterns. Fig. (b) shows the other end of the spectrum, where Adaptor fails to fit the training set at all (while NUDGE both fits the training set and improves validation accuracy). We observed this behavior that increasing the number of parameters, e.g., by introducing additional layers, did not improve accuracy, suggesting that perhaps using adaptors wrong modeling choice. Fig. 3 (c) shows the only dataset where Adaptor performs well, where it both fits the training set and improves validation accuracy.
large data and query sets. We also observed (but not shown here)
PTFT, on the other hand, has much smaller generalization gap compared with Adaptor. However, both validation and training accuracy increase much slower pace, and eventually plateau. Espe- cially for NQ, we observe that the model underfits the training set. We hypothesized that one reason could be due the loss function used, where indeed Table. 5 shows our attempt at modifying the loss function does help improve accuracy on NQ, but not consistently across datasets (and worsens the accuracy other datasets).
E.4 NORMALIZATION ABLATION STUDY
We compare NUDGE-N, with NUDGE-IN (as described Sec. with two other potential variants to understand the impact of normalization. NUDGE-M+N variant that first performs
27

---

Published as a conference paper at ICLR 2025
Table 13: Normalization Study, avg. BGE-S accuracy
Method
NDCG@16 @ 10
NUDGE-N
61.1
NUDGE-IN
61.8
NUDGE-M+N
58.8
NUDGE-IM+R
52.4
Table 14: Accuracyfefficiency of iterative and non-iterative NUDGE variants (BGE-S text datasets)
Method
R@1 1
R@ 10
NDCG@10
Fine-Tuning Tuning Time (s)
NUDGE-IM-(10 1
50.4
66.5
57.2
11.3
NUDGE-IM-(109 IM-00-3 102)
50.4
66.5
57.1
4.16
BEDGE-IM-(10- (10
48.0
59.2
51.1
3,46
NUDGE-M
50.5
66.6
57.3
3.49
NUDGE-M and then normalizes embeddings post-hoc. NUDGE-IM+R is variation of NUDGE- IM with L2 regularization added to the loss to penalize embeddings with large norms. Table 13 shows the results for this experiment, showing that normalizing embeddings after optimization, i.c., NUDGE-M+N performs
than when normalization is considered as part of optimization, which the case for both NUDGE-IN and NUDGE-N, BUDGE-IM+H performs worse than all methods, showing advantage for enforcing normalization constraint over 1.2 regularization. Meanwhile, NUDGE-IN and NUDGE-N perform similarly (see Sec. C.2 for a discussion between the two).
E.5 ITERATIVE VS. CLOSED-FOREE NUDGE VARIANTS
We present results comparing NUDGE-M and NUDGE-IM. We use NUDGE-IM-(a, t) to refer to NUDGE-IM with learning rate run for t iteration (although validation accuracy, so the presented accuracy can be for a model trained with fewer iterations than t). Overall, the results show that NUDGE-M saves time while providing the best accuracy, while some NUDGE-IM variants are as accurate while being less efficient. Nonetheless, NUDGE-IM variants simple implement and more flexible (e.g., in terms of validation accuracy metric to use), and thus may be preferred in some applications.
model checkpointing based on
E.6 NUDGE CONSTRAINT VARIANTS
E. SPARSITY CONSTRAINTS
which performs sparse embedding updates in practice. Specifically, we apply the NUDGE-S update formula in Eq. 31 to fine-tune the embeddings with various values of y E [0. 0.5) for various text datasets using BGE-S. The results of this experiment are shown in Fig.
We evaluate the accuracy of the NUDGE variant discussed in Appx. C.1
Overall, as the figure shows, in almost all datasets, updating the embeddings with sparse updates worsens accuracy, with drop of NDCG for any ς > 0. This is expected since the updates change only a single dimension of the embedding of every data record. Since the embeddings are dense vectors where different dimensions are expected to be dependent on each other, modifying only a single embedding dimension can distort the semantics in the embedding vectors and worsen aceu- racy. Interestingly, the only exception is ArguAna, where NUDGE-S indeed improves accuracy. This contrasts with NUDGE-M and NUDGE-N (as well as PTFT and Adaptor, See Table (5) that do not improve accuracy on ArguAna. This suggests that embedding space for ArguAna has dif- ferent characteristics, and emphasizes the relationship between the regularization method and the embedding geometry.
E.6.2 ADAPTIVE THRESHOLLDS
The constraint formulation for NUDGE-N and NUDGE-M enforces uniform bound of y on the magnitude of change of embeddings across the embedding space. Here, explore whether al-
28

---

Published as a conference paper at ICLR 2025
ArguAna
HotpesQA
NQ
TriviaQA
NF-Corpus
SclFact
0.6
NDCG@10
0.4
0.2
0.0
0.1
0.2
0.3
0.4
y
Figure 4: Fine-Tuning with NUDGE-S
Table 15: Using adaptive thresholds across datasets with BGE-S
Methods
NFCorpus
SciFact
ArguAna
Fever
NQ
TriviaQA
HotpotQA
NUDGE-M
40.9
79.2
47.9
95.0
38.6
35.5
63.1
NUDGE-M-C2
34.5
76.5
47.9
87.3
31.8
30.3
61.3
NUDGE-M-C5
34.4
75.7
47.9
86.1
30,9
30.2
61.2
NUDGE-M-C10
34.0
74.7
47.9
85.7
30.1
29.8
61.0
NUDGE-N
45.7
87.7
47.9
93.5
45.9
43,0
65.2
NUDGE-N-C2
43.1
87.7
47.9
93.5
45.9
42.8
65.1
NUDGE-N-CO 41.0
86.9
47.9
93.2
45.9
43.0
65.2
NUDGE-N-CI0 39.5
86.6
47.9
93.0
46.0
42.9
65.0
lowing for adaptive thresholds can improve accuracy, where different parts of the embedding space are allowed to use different bounds on the magnitude of change to the embeddings. To do so, we first cluster the data embeddings using K-Means clustering into clusters for an integer r. Then, we iteratively apply NUDGE-M and NUDGE-N to each cluster. This provides the model with the flexibility to set a different threshold ry for different clusters.
The result this experiment is presented in Table 15 for text datasets using BGE-S. NUDGE-M-Cr and NUDGE-N-Cr, refer, respectively, NUDGE-M and NUDGE-N applied different clusters as described above. Interestingly, we see that using clustering worsens the performance, especially for NUDGE-M, where the more clusters used, the worse the model gets. We suspect this is because fine-tuning is done on each cluster separately, and thus, the values across clusters are set independently. As result, this leads expect an optimal solution to the problem to be non-trivial, given that values for all the clusters need be set co-dependently. We leave such study to the future work. We also note that, as shown in Fig-2) NUDGE-N is less sensitive to the value of y, thus, its accuracy is only marginally impacted by the use of clustering.
suboptimal selection of values for different clusters. We
E.7 IMPACT OF NOISE IN TRAINING QUERIES
In this experiment we study the impact of unreliable training and validation queries on the fine- tunining outcome. Specifically, for each training/validation query embedding g, we add \(0 o²) noise, independently to every dimension of q. We vary to study the impact of noise mag- nitude on the behavior of NUDGE-M and NUDGE-N, The result of this experiment, varying E [0.025, 0.1, 0.5) is plotted in Fig.5
The results show that both NUDGE variants still outperform No Fine Tuning, even up until noise with standard deviation 0.2. Note that noise with standard deviation of 0.2 has average absolute value of around 0.16, while the average absolute value of the training query embeddings across all datasets is less than 0.04, showing that the tne-tuning processes is robust to i.i.d and unbiased noise. Interestingly,
results also show that NUDGE-M is more robust noise than NUDGE-N, and starts to outperform NUDGE-N for noise with standard deviation larger than 0.05. We believe this can be because normalization forces the embeddings fall in smaller subset of space. This can
29

---

Published as a conference paper at ICLR 2025
Table 16: NUDGE with HyDE using BGE-S embeddings
Method
NFCorpus
SciFact
NUDGE-M
40.0 (6.2)
79.2 (6.5)
NUDGE-N
44.6 (10.8)
87.8 (15.1)
HyDE+NUDGE-M
46.3 (12.5)
80.9 (8.2)
HyDE+NUDGE-N
49.6 (15.8)
88.5 (15.8)
HyDE
35.5 (1.7)
74.8 (2.1)
No Fine- TuninTTning
33.8
72.7
Tuning NUDGE
NUDGE-K
NUDCE will bost Neian
NDCC810
50-
45
0. 02.
0.05
0.1
0.2
0.4
Noise Stundard Devistion
Figure 5: Impact of noise in training queries, average NDCG@ 10 across text datasets using BGE-S,
force unrelated embeddings to become more entangled in the presence of noise, leading to worse accuracy.
E.8 USING QUERY REWRITING WITH NUDGE
Here we explore the potential of using NUDGE together with query rewriting approaches. Since NUDGE only modifies data embeddings, it is orthogonal to query rewriting approaches and can casily be combined with such methods. In this experiments, we study impact of combining NUDGE with HyDE Gao et al. (022). HyDE is popular query rewriting method that rewrites the query as hypothetical documents that answer the query using an LLM (we used GPT-4o mini), and uses the generated hypothetical documents as queries retrieve relevant documents from the dataset. Note that HyDE changes how the query embeddings are created, and operates completely independently of NUDGE. Thus, in this experiment, HyDE is used to generate the query embeddings (i.e.. the embedding matrices Q" and Q" are now generated using HyDE). NUDGE is then directly applied on the generated embeddings rewriting method is time-consuming (and expensive), as it requires multiple LLM generation calls for every query (HyDE in fact perform different generations for every query and averages the embeddings). Thus, we only report results on two datasets, NF-Corpus and SciFact.
before, without any modifications. We note that HyDE's query
Table 16 shows the result of this experiment. We see that combining HyDE with NUDGE improves accuracy over only using NUDGE, although NUDGE alone is still more accurate than using HyDE alone.
E.9
OTHER GENER ALIZATION RESULTS
This section contains generalization results for other models and dataset in the same setting as Sec. 4.2
Specifically, Table 17 contains per dataset generalization results not presented in the paper and Table 18 contains generalization results using GTE-L model averaged over the text datasets. Overall, we see that the trends in Tables [8 and [7 are in general similar to the results presented in and [ Here, we note that on HotpotQA, TriviaQA and Fever, both parametric approaches Adapter and PTFT are unable to improve accuracy over fine-tuning. This is consistent with the re- sults in Table and is further discussed and explained in Sec. [4.]] Thus, in the results presented for Adapter and PTFT in Table 17 we see zero change in accuracy over No Fine-Tuning.
E. RUNTIME MICRO-BENCIMME BENCHMARK
This section presents micro-benchmark, showing the runtime of matrix operations GPU and CPU, in order to justify the runtime numbers shown in Table Specifically, we perform 13 consec- utive matrix addition and multiplication operations on matrices of dimensions d d, and measure
30

---

Published as a conference paper at ICLR 2025
Generalization results using BGE-S for three text datasets. Results report change in NDCG@ 10 over No Fine-Tuning (ID: Dist,, OD: Out-of-Dist. L: Labeled, UL:Unlabeled)
Table 17:
HotpotQA
Triviaqa
Fever
Method
1Q
0Q
IL
OL
IQ
0Q
IL
OL
1Q
0Q
IL
OL
NUDGE-M
4.1
0.5
25.0
-5.2
9.1
-22.2
49.4
-13.7
12.5
-40.1
14.0
6.1
NUDGE-N
5.5
0.9
19.9
0.6
16.6
1.6
41.1
3.1
11.5
4.1
12,4
9.7
NUDGE-M+N
2.0
0.4
8.2
0.9
16.7
1.2
42.0
2.8
10.2
3,4
10.6
9.5
A+NUDGE-N
5.5
0.9
19.9
0.6
16.6
1.6
41.1
3.1
11.5
4.1
12.4
9.7
P+NUDGE-N
5,5
0.9
20.9
0.2
16.6
1.6
41.1
3.1
11.5
4.1
12.4
9.7
Adapter
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
PTFT
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Table 18: Distribution shift results on GTE-L, 10 averaged over text datasets
Method
In-Distribution Query
Out-of-Distribution Query
NUDGE-M
59.3 (+6.2)
38.9 (-14.4)
NUDGE-N
61.8 (+8.7)
54.4 (+1.1)
Adapter
55.2 (+2.1)
52.8 (-0.5)
No Fine-Tuning
53.1
53.3
the total runtime (average across 10 runs). Fig. shows the runtime of the approaches for various values of d. We see that at d 384, GPU is 2.3x faster, but d 3072 the GPU is 1600x faster. This justifies the less than expected speed-ups of using GPUs in Table 8 where due to embedding dimension being 384, most operations in NUDGE-M. NUDGE-N, and Adaptor involve only small matrix operations.
E.11 ABLATION STUDY OF NUDGE
We provide an ablation study to better understand the impact of various constraints in NUDGE. In addition to NUDGE-M and NUDGE-N, we present NUDGE-M+N, which performs normaliza- tion on the output of NUDGE-M. That is, instead of incorporating normalization as a constraint in the optimization problem, NUDGE-M+N simply normalizes the embeddings after performing NUDGE-M. We also present NUDGE-NU, which is variation of NUDGE-N that only includes the normalization constraint, but not the constraint on the magnitude of the change in the embeddings (the solution is equivalent to the first branch of Eq. 6).
Table 19 shows the results of comparing the above variants across text datasets using the BGE-S model. The table shows normalizing the embeddings as part the optimization (NUDGE-N) is better than simply normalizing the output after optimization (NUDGE-M+N), although both work better than using unnormalized embeddings (NUDGE-M). Moreover, allowing the magnitude of change to the embeddings be unbounded (NUDGE-NU) performs worse than all other variants, showing the benefit of constraining how much embeddings can change during fine-tuning. Overall, comparing NUDGE-N, No Fine- -Tnning and all other variants, we see that the benefits of NUDGE- N come from a combination of all design choices made.
E. IMPACT OF LABEL DISTRIBUTION
Here, we study the impact of label distribution in the results presented in Sec. 4 To do so, Fig. plots the distribution of test labels in relation the training set. A point (æ, v) the plot means that y percent of test queries on the dataset have a label that appears x times in the training set. For instance, all test queries for ArguaAna have ground truths unseen during training, while for CoCo and Flickr, all test queries have a ground truth that appeared between 1-4 times in the training set (i.e, there are 1-4 training queries with ground truth being the same data record as the test query).
Next, we discuss the relationship between label distribution and normalization to explain the per- formance difference between NUDGE-M and NUDGE-N. Note that if data record is not ground truth to any training query, NUDGE-M will not modify its embedding. On the other hand, NUDGE- M will likely increase the magnitude of the data embeddings that are the ground truth for some training query. This can create a discrepancy between the magnitude of different data embeddings in NUDGE-M depending whether they were present in the training set. Embeddings with smaller
31

---

Published as a conference paper at ICLR 2025
CPU GPU
Milliecondd
10P
10-1
384
768
1536
3072
Matrix Dim.
Figure 6: Runtime niirr-bbenchmark
Table 19: Ablation of NUDGE
Method
NDCG@10 @10
NUDGE-N
61.1
NUDGE-M+N
58.8
NUDGE-M
57.0
NUDGE-NU
56.6
No Fine-Tumme TuninT
48.7
magnitudes will generally have lower inner product similarity with test queries, which is detrimental many test queries ask for data embeddings whose ground truth was not seen during training. The exact impact depends on whether label distribution is heavy-tailed (with many test labels not present in training set) or it is skewed towards a fixed set of labels (with test labels likely seen during train- ing). For example, we see large gap between NUDGE-M M and NUDGE-N in SciFact, TriviaQA, NQ and HotpotQA, where, as Fig. shows, the ground truth for between 40-60% of test queries was not seen during training. Meanwhile, NUDGE-M performs similarly to NUDGE-N on CoCo, Flicker and Fever datasets, where, as shown in Fig. almost no test query asks for data records not seen during training.
Regarding image datasets CoCo and Flickr, we also note that, all images have exactly 5 differ- ent queries. Thus, the ground truth for all test queries is present in the training set. This means NUDGE-M modifies the embedding of all data records during fine-tuning, leading an increase in the magnitude of all embeddings. Interestingly, in both CoCo and Flickr datasets, our results show that the increase in the magnitude has low variation across embeddings. In fact, the standard deviation of the magnitude of the embeddings after fine-tuning is 0.02 (average embedding magni- tude is 2.24 an 1.81 respectively for CoCo and Flickr datasets). Since there is a low variation the magnitudes of the embeddings. normalization does not make a significant difference. As result, NUDGE-M and NUDGE-N (which requires normalized embeddings) perform similarly.
Finally, Fig. 7 also helps explain why none of the approaches perform well on ArguAna, where no test label appears in the training set. As such, all models have to rely generalization improve accuracy, which is more challenging.
Impact of label distribution on y. Here, we also discuss the impact of label distribution on the best value of y for NUDGE-M. Recall that, as we saw in Fig. 2 for NUDGE-M the best value of y changes more significantly across datasets compared with NUDGE-N. In fact, for NUDGE- M. we see an interesting relationship between 7 and label distribution. For the label distributions concentrated on a fixed set of labels (i.e., CoCo, Flickr, Fever, NF-Corpus without test queries asking for labels not seen during training), the larger values of y do not hurt accuracy, since, as discussed above, larger magnitudes of fine-tuned embeddings in those dataset is not detrimental. Nonetheless, for other datasets, increased can worsen accuracy for test queries that ask for data records not seen during training. This leads to a trade-off, where increasing 7 can improve accuracy for queries on data records seen during training and worsen accuracy for records not seen during training. We see that this trade-off leads to different suitable ? values for datasets SciFact, HotpotQA, NQ and TrivaiaQA.
32

---

Published as a conference paper at ICLR 2025
CoCo
ArguAna
NF-
HotpotQA
NO
Flickr 100
SclFact
TriviaQA
Percentage of samples
80
60
20
Number of times tast label appears in training set Figure Label dist, across datasets
33


Reviews:
[{"review_id": "gzM7sy5rZ6", "reviewer": "Reviewer_j9KJ", "summary": "This work presented a family of novel non-parametric embedding fine-tuning approaches that are significantly more accurate and efficient than both sets of existing approaches.", "questions": "1. What is the sensitivity of NUDGE's performance to hyperparameter selection, particularly the choice of γ. If 'NUDGEM sets γ by solving MaxA-EFT on the validation set', how should γ be set on the training set?\n\n2. In Eq.1, the range of j is confusing, what does '\\Y_j' represent?\n\n3. Why do NUDGE-M and NUDGE-N methods have similar average results on image retrieval pre-trained models. （CLIP-B and CLIP-L）\n\n4. The criteria for selecting the constraint boundaries in NUDGE-M and the specific reasoning behind the grid search implementation for NUDGE-N's gamma optimization are not fully detailed.\n\n5. How to mitigate the impact of unreliable training query embeddings when fine-tuning based on these embeddings?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The s NUDGE, a non-parametric embedding fine-tuning method, which innovatively addresses the limitations of parametric approaches in k-Nearest Neighbor (k-NN) retrieval. This originality stems from shifting focus to the embeddings themselves rather than model parameters, offering a novel optimization perspective for retrieval tasks. \n\n2.Comprehensive experimental and theoretical analyses validate NUDGE's efficacy across five pre-trained models and nine retrieval datasets.\n\n3.The paper is well-organized and presents its methodology and experimental findings clearly.\n\n4.By providing a lightweight, model-agnostic solution with strong generalization to out-of-distribution queries, NUDGE offers substantial improvements in both computational efficiency and accuracy.", "weaknesses": "1. It does not extensively explore or compare alternative constraint types. For example, additional regularization techniques, such as sparsity constraints or adaptive thresholds.\n\n2. Lack a detailed ablation study that examines how skewed distributions impact both in-distribution and out-of-distribution performance could reveal if other normalization techniques or dataset-specific adjustments would better manage this overfitting.\n\n3. While the optimization and constraint methods are described, some of the choices behind the approach could use further explanation.", "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": "k58mFCL9XF", "reviewer": "Reviewer_ubhs", "summary": "This paper introduces NUDGE, a non-parametric embedding fine-tuning approach designed to enhance k-nearest neighbor (k-NN) retrieval accuracy in text and image retrieval tasks. Two main variants, NUDGE-M and NUDGE-N, apply controlled modifications to embeddings, with NUDGE-M using bounded changes and NUDGE-N adding normalization to improve out-of-distribution generalization. Experimental results across multiple datasets show that NUDGE consistently outperforms traditional PTFT and Adapter methods.", "questions": "As the modifications of the embeddings still require learning and would be sufficiently large given a large dataset, how much benefit does this method still have when the dataset is large?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. **Intuition of the Proposed Method**: The paper clearly presents NUDGE's core idea of directly modifying embeddings as parameters, offering a simple, intuitive approach to fine-tuning that improves retrieval accuracy without altering the model.\n\n2. **Extensive Experimental Evaluation**: Experiments are comprehensive, covering diverse retrieval tasks (text, cross-modal) and configurations, validating NUDGE's effectiveness, efficiency, and adaptability across different datasets and models.", "weaknesses": "1. **Theoretical Issues**:\n   - Equation (1), defining MaxA-EFT, is disconnected from the actual task as it primarily maximizes inner product similarity without a clear link to retrieval-specific objectives.\n   - The NP-hard nature of MaxA-EFT, while noted, lacks clear relevance to the search task, and the authors fail to define an explicit optimization problem for solving it.\n   - Equation (2) being unbounded is more of a general mathematical property and seems unrelated to the paper’s focus on non-parametric methods.\n   - Line 212’s constraint on \\(\\Delta\\) uses matrix norm notation, which doesn’t adequately capture the constraints on embedding norms, indicating a need for clearer notation.\n\n2. **Experimental Issues**:\n   - Table 3’s results are overly generalized under “across text datasets,” obscuring which datasets contributed to the reported metrics.\n   - In BEIR benchmark results (Table 5 and Table 9), the first column shows identical performance across all methods, which is counterintuitive and suggests either data or methodology issues.\n   - The GPU speedup in Table 6 is marginal compared to the CPU, which raises efficiency concerns, as an A100 GPU should provide significantly higher speedup for such operations relative to CPU processing.", "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": "Qch3yAgxAb", "reviewer": "Reviewer_ZHaK", "summary": "The context is embedding-based retrieval, for Q&A on documents, RAG, text-to-image retrieval, etc. The authors propose to do domain adaptation by \"fine-tuning\" the document embeddings with a supervision. The results show that this is more accurate (and faster) than to fine-tune the feature extraction model or to train a transformation model on top of frozen features.", "questions": "I would be willing to raise my rating if the \"closed-word\" setting of the paper was clearly discussed and mentioned as a limitation compared to the baselines it compares with. It is not even sure it's legitimate to call the method \"fine-tuning\". However, it *is* an interesting study of what can happen if embeddings are optimized directly (it's just not practical beyond a benchmark setting). \n\nFor out-of-sample results, it would be interesting to see what would happen if an actual feature transformation model was trained on top of the embeddings found by this method.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. The study is an interesting exploration of dataset side adaptation, in the case of a \"closed world\" dataset that is frozen. \n\nS2. The approach and baselines are relevant. The adaptation relies on simple linear algebra, so it is fast and much can be done in closed form.\n\nS3. Convincing results: since the training acts directly on the embeddings (as opposed to network parameters) it has more degrees of freedom than when training on the model (indirect fine-tuning)", "weaknesses": "W1. The \"elephant in the room\" for this method is that it does not work on out-of-sample documents. Since the embeddings of the database are adjusted at fine-tuning time, new documents cannot benefit from it, unless new training data is added for them as well, which becomes a really narrow application setting. This is all the more apparent since out-of-distribution on the queries side is considered in this work.\n\nW2. The method works only on densely annotated training data, since a document that is never returned to a query will not be adapted. This is apparent in the KILT dataset where documents that do not appear in any result are simply removed. \n\nW3. Because of this particular setting, the queries in experiments must be split in train+val+test, which is unusual. Therefore there are no comparisons with state-of-the-art methods.", "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": "f23h1n7yhe", "reviewer": "Reviewer_K1aL", "summary": "This paper introduces NUDGE, a novel method for retrieval that directly fine-tunes index embeddings by treating them as \"model parameters\". The theoretical analysis yields two variants, NUDGE-M and -N, and elucidates their time complexities. Experimental results demonstrate that NUDGE significantly outperforms existing methods for in-distribution data and achieves comparable performance for out-of-distribution scenarios.", "questions": "[Q1] It seems appropriate to position NUDGE as the third paradigm for retrieval task fine-tuning. The three paradigms can be summarized as follows: 1) Fine-tuning the foundation model; 2) Training a tiny model to refine the embedding; 3) directly fine-tuning the embedding. These approaches present interesting trade-offs. In terms of training cost, the order is 1 > 2 > 3, while for cost of adding more photos to the DB, the order is reversed: 3 > 2 > 1. Fine-tuning a foundation model is computationally intensive, but it easily accommodates new images added to the database. NUDGE, on the other hand, is less demanding to train, but requires additional computation to update embeddings for newly added DB images. In this context, the second paradigm appears to offer the best balance among the three. Do you have any insights on this?\n\n\n\n[Q2] How is the generalizability of other NUDGE variants?\n\n \n\nJustification of my score:\n\nAlthough concerns about generalizability and practicality have been raised, the overall contributions of NUDGE—such as its efficient training, strong performance, and introduction of a new fine-tuning paradigm—significantly outweigh its weaknesses. Based on these considerations, this paper merits acceptance. However, given the identified limitations, I look forward to discussing with the authors and other reviewers to further evaluate its merits. At present, I believe NUDGE represents a valuable and striking contribution to the retrieval community. I hope the authors can address my concerns or, at the very least, discuss them as limitations of this work in future revisions.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "[S1] The proposed method is novel, simple, and easy to implement.\n\n[S2] The experiments effectively demonstrate the efficacy of NUDGE for in-distribution data.\n\n[S3] The theoretical analysis clearly delineates the characteristics of NUDGE-N and NUDGE-M.\n\n[S4] The paper is well-structured and easy to follow.\n\n[S5] NUDGE represents a potential new paradigm for fine-tuning.\n\n[S6] The authors have provided the code with their submission.", "weaknesses": "[W1] Fine-tuning the embedding directly makes the database difficult to update. Specifically, if new photos are added to the database, their embeddings must also be trained. This requires relabeling (or pseudo labeling) at least a few queries whose GT answers include the new DB images, which incurs additional cost (or the new DB embedding will not be updated). This weakness, however, does not appear in previous two lines of works, ie. fine-tuning the foundation model, or training a new lightweight model to refine the embeddings. Consequently, this limitation somewhat impacts the practicality of NUDGE.\n\n\n\n[W2] NUDGE is unable to refine query embeddings. It has been well established that query embedding refinement can significantly enhance retrieval performance (as evidenced by query expansion and its variants). Both fine-tuning the foundation model and training an embedding update model are capable of updating query embeddings. However, NUDGE cannot accomplish this because the GT label for the input query is unknown, making it impossible to train. This limitation leaves considerable room for improvement.\n\n\n\n[W3] The generalizability of the proposed method is questionable. Intuitively, embedding update methods are likely to suffer from significant overfitting issues. The authors have invested considerable effort to address this, including constraining the $\\Delta$ and normalizing the updated embeddings (either pre- or post-update). While NUDGE-N ultimately achieves acceptable results for OOD data, overall confidence in its generalizability remains limited. For OOD scenarios, NUDGE-N shows only minor improvements on the BGE-S benchmark, with many other benchmarks left untested. When the embedding is not normalized (i.e., NUDGE-M), the generalizability appears notably poor. While it's plausible that the transition from NUDGE-M to NUDGE-N could yield such significant improvements, additional experiments elaborating on generalizability would be beneficial, as this might constitute a major drawback of NUDGE. Nevertheless, if NUDGE can perform adequately across most OOD benchmarks, or even in its current form, it may still be considered acceptable given the other strengths of this work.\n\n\n\n[W4] Nit: The authors should follow the ICLR 2025 template guidelines by placing table captions above the tables.", "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)