# An alternative proof of the vulnerability of retrieval in high intrinsic
dimensionality neighborhood

Teddy Furon
Univ Rennes, Inria, CNRS, IRISA - France

###### Abstract

This paper investigates the vulnerability of the nearest neighbors search,
which is a pivotal tool in data analysis and machine learning. The
vulnerability is gauged as the relative amount of perturbation that an
attacker needs to add onto a dataset point in order to modify its neighbor
rank w.r.t. a query. The statistical distribution of this quantity is derived
from simple assumptions. Experiments on six large scale datasets validate this
model up to some outliers which are explained in term of violations of the
assumptions.

##  1 Introduction

The search of Nearest Neighbors (NN) not only appears in the top-10 algorithms
in data mining according to [Wu et al., 2008], but it is also at the root of
many machine learning methods ranging from detection [Gu et al., 2019],
classification [Yang et al., 2020], and regression [Devroye et al., 1994].
Chen and Shah [2018] explain its popularity because it is a flexible, non
parametric, interpretable, and computationally efficient method.

As such, many security and safety-oriented applications rely on information
retrieval operated by the NN search. The existence of an attacker
intentionally circumventing the NN search becomes a plausible threat. For
instance, social networks often compare uploaded content to a collection of
materials to detect ‘forbidden’ content (terrorism, pedopornography, fake
news, etc) or to identify copyright holders (content monetization). The
detection of outliers to spot fraud in financial transactions or intrusion in
security systems is another example of critical applications of the NN search
[Gu et al., 2019].

The NN search recently went to the rescue of other machine learning
techniques. At training time, Bahri et al. [2020] use the NN search to
sanitize the tranining set detecting mislabeled data, while Weerasinghe et al.
[2021] prevent poisoning attacks. At test time, Nguyen and Raff [2018] use it
as a defense against adversarial examples to robustify regression. Cohen et
al. [2020], Papernot and McDaniel [2018], and Ma et al. [2018] share the same
idea to detect adversarial images by considering them as outliers. They gauge
the confidence of the classifier according to the neighbors of the input in
the training set in some activation layer of the neural network. Note that
this defense has been under scrutiny in the works of Sitawarin and Wagner
[2019] and Athalye et al. [2018]. Wang et al. [2018] analyze the theoretical
robustness of classification based on NN search against adversarial attacks
and propose in [Yang et al., 2020] to sieve the training set to prune out
isolated points that cause vulnerability.

The versatility and ubiquity of the NN search motivate research on its
intrinsic vulnerability, independently of any machine learning procedure. It
is of utmost importance to analyze the security of this key primitive before
its deployment in applications where security matters. Our article follows the
approach funded by Amsaleg et al. [2020]. It especially deals with vectors
(features extracted from objects) living in high dimensional space and
compared with the Euclidean distance. It quantifies the amount of perturbation
in this feature space needed to delude the retrieval mechanism in terms of
modification of the nearest neighbors. This is exemplified by the scenario
where the attacker modifies the $k_{x}$ nearest neighbor in the dataset to
reduce its neighboring rank to a target $k_{t}<k_{x}$.

Under some broad assumptions, our contribution models the necessary amount of
perturbation as a random variable and reveals its precise distribution
depending on ranks $k_{x}$ and $k_{t}$, the size $n$ of the dataset, and on a
scalar index $\ell$ characterising the distances of the dataset points in the
neighborhood. Section 4 shows that this r.v. converges to a simple
distribution when the dataset size $n$ grows to infinity. Experiments in Sect.
5 over six large scale datasets (four of them gather one billion dataset
points each) of very different nature shows a very close fit with the
asymptotical model. Section 6 extends results to a plurality scenarios where
the query (or a dataset point) is modified so that the $k_{x}$-NN becomes the
$k_{t}$-NN: if $k_{t}<k_{x}$, the perturbated point gets closer to the anchor,
if $k_{t}>k_{x}$ it is moved farther away.

##  2 Related Work

###  2.1 Experimental Evidence of the Vulnerability

The forgery of query image deflecting nearest neighbor search has a long
history in Content-Based Image Retrieval (CBIR) and image classification.

Do et al. [2012] motivate their work by pinpointing that CBIR became a
technology brick used in applications where security is at stake, like content
monetization on social networks. In the pre-era of deep learning, these
authors delude such a mechanism (i.e. a given dataset image is no longer
returned by the $k$-NN search) by exploiting the Achilles’ heel of the SIFT
local description (orientation). Tolias et al. [2019] play the opposite game
with nowadays deep learning representation: the query image (e.g. depicting a
flower) is manipulated to retrieve images matching another visual content
(e.g. the Eiffel tower) to protect the privacy of the querying user. Xiao and
Wang [2021] investigate the same scenario but with black-box transferability.
The general poor level of security is due to two weak points: i) deep neural
networks provide discriminative but sensitive feature vectors easily corrupted
by image manipulation, a well-known fact in the literature of adversarial
examples [Sabour et al., 2016], and ii) a small move in this high dimensional
feature space may be sufficient to dramatically change the nearest neighbors
as demonstrated by Amsaleg et al. [2020].

Our paper is dedicated to this later vulnerability.

###  2.2 Theoretical Evidence of the Vulnerability

Wang et al. [2018] extend the theoretical analysis of classification based on
nearest neighbors. The classic theory shows how the probability of correct
classification behaves for fixed $k$ and $n$ increasing [Devroye et al., 1996,
Chap. 5] or the universal consistency when $k$ is allowed to grow with $n$
s.t. $\nicefrac{{k}}{{n}}\to 0$ [Devroye et al., 1996, Chap. 6]. Wang et al.
[2018] generalize this to the adversarial risk by introducing the concept of
astuteness: not only a query $\mathbf{q}$ should be correctly classified, but
so are all the points surrounding it at a distance lower than a robustness
radius $r$. They outline the vulnerability of NN classifier in the following
way: zero robustness is expected for a fixed $k$ and one has to set $k$ to a
very large amount $\Omega(\sqrt{dn\log n})$ to asymptotically reach the
robustness of the optimal Bayesian classifier.

Amsaleg et al. [2020] are the only authors we are aware of studying the core
robustness of the NN search _out of any supervision task_. There is no label
and thus no law $p(Y|X)$, but just a collection of $n$ points in
$\mathbb{R}^{d}$. They do not make assumption about the distribution of the
points around the query but only about their distances. They show that,
asymptotically as the size of the dataset increases, the necessary relative
amount of perturbation has a simple expression. Their Theorem 2 states that if
the perturbation amount is bigger than this lower bound, then the attacker is
sure to reach his goal.

Our work offers a much more accurate model of the amount of perturbation
revealing its asymptotical and non-asymptotical distributions. Indeed, our
results contradict the Theorem 2 of [Amsaleg et al., 2020].

##  3 Problem Statement

Let us consider a dataset $\mathcal{D}$ of $n$ points
$\\{\mathbf{x}_{i}\\}_{i=1}^{n}\in\mathbb{R}^{d}$, plus a query point
$\mathbf{q}$ wherever in this space. Suppose that an artificial intelligent
program bases its decision on the dataset points neighboring the query.
Especially, the decision will take dataset point $\mathbf{x}$ into account if
it is one of the $k_{t}$ nearest neighbors of $\mathbf{q}$.

Suppose that this is not the case for that query $\mathbf{q}$ and this dataset
point $\mathbf{x}$. In other words, $\mathbf{x}$ is only the $k_{x}$ nearest
neighbor of $\mathbf{q}$ with $1\leq k_{t}<k_{x}\leq n$. This work is
interested in the amount of perturbation to be applied to dataset point
$\mathbf{x}$ so that the program now takes it into account.

###  3.1 Definition of the Relative Amount of Perturbation

As shown in Fig. 1, we denote by $\mathbf{t}$ the dataset point which is the
$k_{t}$ nearest neighbor of $\mathbf{q}$. We also introduce
$t:=\|\mathbf{t}-\mathbf{q}\|$ and $x:=\|\mathbf{x}-\mathbf{q}\|$ (Euclidean
norm) ; we have $t<x$. The perturbation pushes $\mathbf{x}$ to a new point
$\mathbf{y}$ with the goal that its neighbor rank is $k_{y}\leq k_{t}$, thus
at a distance $y:=\|\mathbf{y}-\mathbf{q}\|\leq t$ away from $\mathbf{q}$.

The relative amount of perturbation is evaluated by the ratio
$\delta:=\|\mathbf{x}-\mathbf{y}\|/\|\mathbf{x}-\mathbf{q}\|$, with
$\delta\in(0,1)$. It measures the norm of the perturbation
$\mathbf{y}-\mathbf{x}$ relatively to the original distance $x$ of
$\mathbf{x}$ from $\mathbf{q}$. Sabour et al. [2016] also use this metric.
Obviously, this ratio is set to the minimum if $\mathbf{x}$ is pushed onto
$\mathbf{y}$ in a direct line towards $\mathbf{q}$ so that $\mathbf{y}$
belongs to the line segment $\overline{\mathbf{x}\mathbf{q}}$ as shown in Fig.
1. This implies that:

$k_{y}\leq k_{t}\quad\Longleftrightarrow\quad y\leq
t\quad\Longleftrightarrow\quad\delta\geq 1-\frac{t}{x}.$ (1)

The sequel assumes that this strategy is feasible and we set
$\delta=1-\nicefrac{{t}}{{x}}$.

$x\delta$$\mathbf{y}$$\mathbf{q}$$\mathbf{t}$$\mathbf{x}$$t$$x$ Figure 1:
Configuration of the dataset neighbors $\mathbf{x}$ and $\mathbf{t}$, and the
manipulated point $\mathbf{y}$ with respect to the query $\mathbf{q}$.

###  3.2 Statistical Model

The relative amount of perturbation depends on the configuration of the
dataset points locally around $\mathbf{q}$. Amsaleg et al. [2020] consider
that this dataset of points is indeed random. This means that distances $t$
and $x$ are occurrences of random variables $T_{n}$ and $X_{n}$ (note that
$0<T_{n}<X_{n}$), and so is the relative amount of perturbation $\delta$
w.r.t. random variable $\Delta_{n}:=1-T_{n}/X_{n}$. The subscript $n$ stresses
that the size of the dataset is a major factor.

Amsaleg et al. [2020] do not impose a specific distribution of the dataset
points in $\mathbb{R}^{d}$, but only assume a statistical distribution of
their distances from $\mathbf{q}$.

######  Assumption 3.1.

The distances of the dataset points w.r.t. the query $\mathbf{q}$ are random
variables independent and identically distributed, whose c.d.f. is denoted by
$F:\mathbb{R}^{+}\to[0,1]$ and p.d.f. $f:\mathbb{R}^{+}\to\mathbb{R}^{+}$.

We should have written $F_{\mathbf{q}}$ and $f_{\mathbf{q}}$ to outline that
this statistical model only holds for the distances from $\mathbf{q}$ ; we
omit this subscript for the sake of simplicity.

A second assumption deals with the behaviour of the c.d.f. $F$ around 0.

######  Assumption 3.2.

The distances of the dataset points w.r.t. the query $\mathbf{q}$ are
absolutely continuous r. v., whose c.d.f. $F$ is a regularly varying function
Bingham et al. [1987] around $0^{+}$ with index $\ell>0$ in the sense that,
$\forall\lambda>0$

$\lim_{x\to 0^{+}}\frac{F(\lambda x)}{F(x)}=\lambda^{\ell}.$ (2)

Again, we use a simplified notation although the value of the index $\ell$ of
the regular variation is specific to the given $\mathbf{q}$ because it models
the distribution of the distance from $\mathbf{q}$. Indeed, Amsaleg et al.
[2020] call it the Local Intrinsic Dimension (LID) to insist that it only
characterises the local neighborhood of the query point.

This assumption is motivated by the theory of extreme values [Feller, 1991,
Chap.VIII]. As $n$ increases while the ranks $k_{x}$ and $k_{t}$ are fixed,
the distances of the $k_{x}$ and $k_{t}$ nearest neighbors tap into the lower
tail of the distance distribution, which ought to be regularly varying because
it is lower bounded by 0. This implies that the _absolute_ amount of
perturbation $X_{n}-T_{n}$ asymptotically goes to zero. Yet, the asymptotical
behavior of the _relative_ amount $\Delta_{n}=(X_{n}-T_{n})/X_{n}$ is not
trivial. In the end, the neighborhood of $\mathbf{q}$ is parametrized with the
single index $\ell$.

As an example, if the neighbors are Gaussian distributed spanning an affine
hyperplane of dimension $d^{\prime}\leq d$ and passing through query
$\mathbf{q}$, then $\ell=d^{\prime}$. The converse is of course not true.
Indeed, index $\ell$ can be much smaller than the representational dimension
$d$.

##  4 Statistics of the Relative Perturbation

###  4.1 Finite dataset size $n$

The joint probability distribution of $(T_{n},X_{n})$ has the following
expression [H. A. David, 2003, Eq. 2.2.1]:
$\forall(t,x)\in\mathbb{R}^{+2}$

$g_{n}(t,x)=\begin{cases}0\quad\quad\quad\quad\quad\quad\text{if }t\geq x\geq
0\\\
\frac{F^{k_{t}-1}(t)[F(x)-F(t)]^{k_{x}-k_{t}-1}[1-F(x)]^{n-k_{x}}}{B(k_{t},k_{x}-k_{t})B(k_{x},n-k_{x}+1)}\\\
\quad\times f(t)f(x)\quad\text{if }x>t\geq 0,\end{cases}$ (3)

where $B$ is the Beta function.

The c.d.f. $F_{\Delta_{n}}$ of random variable $\Delta_{n}$ is given by

$\displaystyle F_{\Delta_{n}}(\delta)$ $\displaystyle=$
$\displaystyle\mathbb{P}(\Delta_{n}\leq\delta)=\mathbb{P}(X_{n}(1-\delta)\leq
T_{n})$ (4) $\displaystyle=$
$\displaystyle\int_{0}^{+\infty}\left(\int_{(1-\delta)x}^{x}g_{n}(t,x)dt\right)dx.$
(5)

Figure 2 illustrates function $g_{n}$ and the domain of integration. Appendix
A shows the following results:

######  Proposition 4.1.

The c.d.f. of the minimal relative amount of perturbation is given by:

$F_{\Delta_{n}}(\delta)=1-\mathbb{E}\left[I_{\nicefrac{{F((1-\delta)F^{-1}(\Xi))}}{{\Xi}}}(k_{t},k_{x}-k_{t})\right].$
(6)

with $\Xi\sim Beta(k_{x},n-k_{x}+1)$

$I_{x}(\alpha,\beta)$ is the regularized incomplete beta function, i.e. the
c.d.f. of the beta distribution $Beta(\alpha,\beta)$.

Figure 2: Visualization of the part of $g_{n}(t,x)$ to be integrated in (5),
for $\delta=\nicefrac{{1}}{{3}}$, $k_{t}=2$, $k_{x}=4$, $n=40$, and
$F(x)=x^{5}$.

###  4.2 Infinite dataset size $n\to+\infty$

We now look for a better understanding of the distribution of $\Delta_{n}$
asymptotically as $n\to+\infty$. Figure 3 shows that its c.d.f.
$F_{\Delta_{n}}$ seems to converge to an asymptotic function. Appendix B uses
the Laplace’s method to find the limit

$F_{\Delta}(\delta):=\lim_{n\to+\infty}F_{\Delta_{n}}(\delta)=I_{L(\delta)}(k_{x}-k_{t},k_{t}).$
(7)

with $L(x):=1-(1-x)^{\ell}$.

This can be restated as the main result of this paper:

######  Proposition 4.2.

For two natural integers $k_{x}>k_{t}$, the relative amount of perturbation
$\Delta_{n}$ converges in distribution to
$\Delta=1-B^{\nicefrac{{1}}{{\ell}}}$ with $B\sim Beta(k_{t},k_{x}-k_{t})$ as
the size $n$ of the dataset increases.

###### Proof.

Since function $L$ is a strictly increasing function, $F_{\Delta}(\delta)$ can
be expressed as the c.d.f. of the random variable
$L^{-1}(B^{\prime})=1-(1-B^{\prime})^{\nicefrac{{1}}{{\ell}}}$ with
$B^{\prime}\sim B(k_{x}-k_{t},k_{t})$:

$\mathbb{P}(L^{-1}(B^{\prime})\leq\delta)=\mathbb{P}(B^{\prime}\leq
L(\delta))=F_{\Delta}(\delta).$ (8)

Knowing that $B=1-B^{\prime}$ is distributed as $B(k_{t},k_{x}-k_{t})$, we
have
$\Delta=1-(1-B^{\prime})^{\nicefrac{{1}}{{\ell}}}=1-B^{\nicefrac{{1}}{{\ell}}}$.
∎

Figure 3: Convergence of $F_{\Delta_{n}}$ to $F_{\Delta}$ as $n$ increases
from $10^{2}$ to $10^{6}$, $k_{t}=2$, $k_{x}=4$, and $F(x)=x^{\ell}$ with
$\ell=5$.

###  4.3 Statistics of Random Variable $\Delta$

This section derives the mean, the median, and the mode associated to the
asymptotical distribution of $\Delta$.

######  Proposition 4.3.

The r. v. $\Delta$ has the following statistics:

  * •

Expectation:

$\mathbb{E}[\Delta]\approx
1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}\left(1-\frac{\ell-1}{2\ell^{2}}\frac{k_{x}-k_{t}}{k_{t}(k_{x}+1)}\right)$
(9)

for $k_{x}\gg 1$.

  * •

Median:

$\displaystyle\bar{\Delta}$ $\displaystyle=$ $\displaystyle
1-(I^{-1}_{\nicefrac{{1}}{{2}}}(k_{t},k_{x}-k_{t}))^{\nicefrac{{1}}{{\ell}}}$
(10) $\displaystyle\approx$ $\displaystyle
1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}\left(1+\frac{2k_{t}-k_{x}}{k_{t}(3k_{x}-2)}\right)^{\nicefrac{{1}}{{\ell}}}$

for $k_{t}\geq 2$ and $k_{x}\geq k_{t}+2$.

  * •

Mode:

$\mathsf{mode}=1-\left(\frac{k_{t}}{k_{x}}\right)^{\nicefrac{{1}}{{\ell}}}\left(1+\frac{(\ell+1)k_{t}-k_{x}}{\ell
k_{x}k_{t}-(\ell+1)k_{t}}\right)^{\nicefrac{{1}}{{\ell}}}$ (11)

###### Proof.

See Appendix C, which also contains exact formulas for the special case
$k_{t}=1$. ∎

These statistics are expressed in order to outline the quantity
$1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}$, which is indeed
the main result of article [Amsaleg et al., 2020, Th. 2]. Quoting this
article, it outlines that “the amount of perturbation required to subvert
neighborhood rankings diminishes with the local intrinsic dimensionality”
$\ell$ of this neighborhood. For instance, for large $\ell$, this term further
simplifies into $\approx\log(\nicefrac{{k_{x}}}{{k_{t}}})/\ell$, which shows
that $\ell$ is of utmost importance. It has a bigger impact than the ratio
$\nicefrac{{k_{x}}}{{k_{t}}}>1$ due to the log scale.

Figure 4 shows how the mode of the p.d.f. of $\Delta$ decreases as $\ell$
increases, especially for large $k_{x}$. It also illustrates that it becomes
more peaky around its mode .

However, Amsaleg et al. [2020] do not state what this quantity is w.r.t.
$\Delta$. Their Theorem 2 states that if the relative amount of perturbation
$\delta$ is strictly bigger than
$1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}+\epsilon$, then
$\mathbf{x}$ has been modified into a point $\mathbf{y}$ whose rank
$k_{y}<k_{t}$. Yet, that $\epsilon$ is fuzzily defined in [Amsaleg et al.,
2020, Th. 2]: “For any sufficiently small real value $\epsilon>0$”. Our result
contradicts this statement: That amount of perturbation achieves its goal only
up to a probability which heavily depends on $\epsilon$:

$\mathbb{P}(success)=F_{\Delta}\left(1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}+\epsilon\right).$
(12)

Figure 4: Asymptotic probability density function of $\Delta$ as a function of
$\delta\in[0,0.5]$ for values of $\ell\in\\{10,20,\ldots,70\\}$ for $k_{x}=4$
(or $k_{x}=100$, dashed) and $k_{t}=2$.

##  5 Experimental Work

###  5.1 Experimental Protocol

The experimental protocol uses six datasets: ImageNet, CIFAR, BigANN, DEEP,
MSSPACEV, MSTuring.

The first four datasets are related to computer vision. They correspond to
global feature vectors extracted from images thanks to a deep neural network
(ResNet50 for ImageNet and CIFAR, GoogLeNet for DEEP [Babenko and Lempitsky,
2016]) or to local hand-crafted descriptors (SIFT for BigANN [Jégou et al.,
2011]). MSTuring and MSSPACEV [Qi and Chen, ] are related to web search. They
are both released by Microsoft Research and consist of vector encoding of
documents and/or queries better capturing the intent of the search.

ImageNet, CIFAR, and BigANN are used in the article [Amsaleg et al., 2020],
whereas DEEP, MSSPACEV, and MSTuring are used in the NeurIPS’21 Approximate
Nearest Neighbor Search Challenge111https://big-ann-benchmarks.com. Table 1
summarizes these data ; Fig. 5 shows the empirical p.d.f. of the indices
$\ell$ measured according to the following protocol.

For each query, an exhaustive search finds the $k_{x}$-nearest neighbors in
the dataset of size $n$, and their distances $\\{d_{i}\\}_{i=1}^{k_{x}}$ to
the query. The minimum relative amount of perturbation is computed by
$\delta=1-\nicefrac{{t}}{{x}}$ where $t=d_{k_{t}}$ and $x=d_{k_{x}}$ are the
distances of the $k_{t}$-th and $k_{x}$-th nearest neighbors. For each query,
the index $\ell$, so-called Local Intrinsic Dimension, is estimated using the
maximum likelihood estimator, a.k.a. the Hill estimator [Hill, 1975]:

$\hat{\ell}=-\left(k_{x}^{-1}\sum_{i=1}^{k_{x}}\log(\nicefrac{{d_{i}}}{{d_{k_{x}}}})\right)^{-1}$
(13)

The protocol provides $q$ pairs of measurements
$\\{(\hat{\ell}_{i},\delta_{i})\\}_{i=1}^{q}$ (one per query). We consider the
neighborhoods with similar estimation values $\hat{\ell}_{i}$ as independent
realizations of our statistical model described by assumptions 3.1 and 3.2.

Figure 5 shows that the datasets have different range of indices. The index
$\ell$ takes values often bigger than 30 in CIFAR and ImageNet, whereas DEEP,
MSSPACEV and MSTuring are peculiar with index values often below 5. Note that
these ranges are weakly related to the space dimension (see Tab. 1).

Table 1: Details about the datasets dataset | $d$ | type | $(n,q)$ | $k_{x}$
---|---|---|---|---
ImageNet | 2048 | float | (1,2M,10K) | 1K
CIFAR | 2048 | float | (50K,10K) | 1K
BigANN | 128 | uint8 | (1B,10K) | 100
DEEP | 96 | float | (1B,10K) | 100
MSTuring | 100 | float | (1B,100K) | 100
MSSPACEV | 100 | uint8 | (1B,29K) | 100
Figure 5: Empirical p.d.f. of Hill estimations $\hat{\ell}$ (13) with the
kernel density estimator of Pham [2004].

###  5.2 Statistical Analysis

The kernel density estimator of Botev et al. [2010] learns an empirical joint
p.d.f. $\pi(\ell,\delta)$ defined over $\mathbb{R}^{+}\times[0,1]$ from the
measurements. In the same way, we learn an empirical marginal p.d.f.
$\hat{f}_{L}(\ell)$ from the estimations $\\{\hat{\ell}_{i}\\}_{i=1}^{q}$ (3rd
cardinal spline KDE with Silverman rule [Pham, 2004]). Our goal is to compare
the empirical joint p.d.f. $\pi(\ell,\delta)$ to the one based on our model,
$f_{\Delta}(\delta|\ell)\hat{f}_{L}(\ell)$, coming from (37). Figure 6 shows
the very good match between the empirical and joint models for ImageNet. The
same observation holds for the other datasets (see figures in Appendix D).

For further investigation, we would like to compare the empirical marginal and
the asymptotical p.d.f. of $\Delta$. To gather a maximum of samples, we
normalize the LID index $\ell$ with the following transformation:

######  Proposition 5.1.

Suppose that $\Delta$ follows the asymptotical distribution given in Prop. 4.2
with index $\ell$ and the ranks $(k_{t},k_{x})$, then
$\tilde{\Delta}=1-(1-\Delta)^{\nicefrac{{\ell}}{{\ell_{0}}}}$ also follows the
asymptotical distribution with the same ranks, but index $\ell_{0}$.

###### Proof.

Since $B=(1-\Delta)^{\ell}\sim Beta(k_{t},k_{x}-k_{t})$, then
$\tilde{\Delta}=1-(1-\Delta)^{\nicefrac{{\ell}}{{\ell_{0}}}}=1-B^{\nicefrac{{1}}{{\ell_{0}}}}$.
∎

We apply this trick to create the samples $\\{\tilde{\delta}_{i}\\}_{i=1}^{q}$
with one common unique index value $\ell_{0}=10$. It is as if all the
measurement were coming from independent neighborhoods realizing the
statistical model with index $\ell_{0}$. The empirical p.d.f. of
$\tilde{\Delta}$ is learned with the method of Pham [2004]. Figure 7 compares
this p.d.f. with the asymptotical model $f_{\Delta}(\cdot|\ell_{0})$ in (37)
from different pairs $(k_{t},k_{x})$. One can see the very close fitting to
the theoretical model although the datasets are of different nature, size, and
setup.

Such a good fitting is surprising because we only made two assumptions about
the data, and moreover, they are violated by some datasets. For instance,
MSSPACEV and BigANN contains quantized vectors belonging to
$\\{0,1,\ldots,255\\}^{d}$. Therefore, the distances between points take
discrete values and this is a clear violation of assumption 3.2. The model is
indeed robust enough to tackle a fine enough granularity of the distance
values.

Figure 6:  Comparison of the empirical (learned with k.d.e. [Pham, 2004]) and
theoretical p.d.f. of the normalized r.v. $\tilde{\Delta}$ defined in Prop.
5.1 with $\ell_{0}=10$, $k_{x}=1000$, $k_{t}=1$. Figure 7: Comparison of the
empirical p.d.f. of the normalized data $\tilde{\Delta}$ and their related
asymptotical models (see Prop. 5.1) with $\ell_{0}=10$ and
$(k_{t},k_{x})\in\\{(1,100),(10,100),(1,1000)\\}$. Expectation ($\triangle$),
median ($\circ$), and mode ($\square$).

###  5.3 Discrepancies and Explanations

This section presents the limits of the proposed model. It first explains the
very light discrepancies visible in Fig. 7, and then exhibits typical
scenarios where the model fails.

####  5.3.1 Convergence Rate

In Fig. 7, CIFAR and ImageNet p.d.f. shows a small shift of $\approx 0.03$
compared to the theoretical curve. This is due to the fact that they do not
yet reach the asymptotical regime as their size is not so large (see Tab. 1).
Indeed, this offset is already visible in Fig. 3 even for dataset size as
large as one million.

For the billion scale datasets of Tab. 1, Fig. 8 shows the Kolmogorov-Smirnov
goodness of fit test value between the empirical and the asymptotical c.d.f.
of $\tilde{\Delta}$ when downsizing the collection of points by a factor 10 or
100. This illustrates the slow convergence to the asymptotical model as $n$
increases.

Figure 8: Kolmogorov-Smirnov goodness of fit test value w.r.t. to the size of
the dataset. Same setup as in Fig. 7.

####  5.3.2 Inaccurate Estimation of the Index $\ell$

All the empirical p.d.f.’s have a slightly different skewness than the
theoretical plot. We do not have access to the index $\ell$, we can only
estimate its value from the distances of the $k_{x}$ nearest neighbors. The
measurement $\delta$ is normalized into $\tilde{\delta}$ by the estimated
index $\hat{\ell}$. Even if $\delta$ were occurences of r.v. $\Delta$,
$\tilde{\delta}$ does not follow the distribution of Prop. 5.1 due to the
estimation noise present in $\ell$.

This discrepancy is almost not visible for CIFAR, ImageNet, and BigANN. For
these datasets, the estimated index is rarely below 5 as shown in Fig. 5. We
evaluate the inaccuracy of the Hill estimator by the Kolmogorov-Smirnov
goodness of fit test value for typical estimations $\hat{\ell}$. Figure 9
shows that indeed estimating indices $\ell<10$ is difficult. This is
especially true for DEEP and may explain its heavier tail in Fig. 7. The joint
p.d.f. displayed in Appendix D confirm this phenomenon: for all datasets, the
differences between empirical and theoretical are more visible at lower index
value (i.e. on the left side of the heat map representation).

Figure 9: Empirical average of Kolmogorov-Smirnov test values as a function of
$\hat{\ell}$. The estimated indices are binned into intervals $5\times[k,k+1)$
with $k\in\\{0,1,\ldots,11\\}.$

####  5.3.3 Mixture of distributions

Figure 10 shows typical failures of the model. We use some of the earlier
datasets, MSSPACEV MSTuring, and DEEP but on a specific setup
$(k_{t},k_{x})=(1,100)$. Note that this setup was not an issue for BigANNin
Fig. 7.

Assumption 3.1 supposes that the distances from the query follow a unique
distribution. This might not be the case for some queries. We envisage the
following cases: The $k_{x}=100$ smallest distances may correspond to:

  1. 1.

a subset of documents matching the query,

  2. 2.

a subset of documents not matching the query,

  3. 3.

the union of two matching / non matching subsets.

Cases 1 and 2 comply with assumption 3.1, but not case 3.

MSSPACEV and MSTuring are collections of data related to web search with
vector encodings of queries and documents. It is expected that a web search
ends up with returned documents ranked first because they have a semantic
connection to the query (i.e.a match) or because it statically happens that
their distances are small. Case 3 might also happen with DEEP which is a
collection of features extracted from “images of the web”, dixit Babenko and
Lempitsky [2016]. Over such a huge collection of pictures scrapped from the
internet, it is likely that there exist duplicates or quasi-copy of some query
images in the dataset, yielding case 3.

This is a priori not the case with CIFAR and ImageNet. For these last two
datasets, the feature vectors are extracted with a classifier deep neural
network and the images are coming from a collection meant for classification.
For instance, if the query is an image of a dog, it will match the hundreds of
dog images in the collection. Therefore, case 1 is likely and this does not
violate our assumption. These are our suppositions, there is no way to certify
occurrences of case 3.

We now explain with a hand-waving rationale that the mixture of distributions
explains the heavy tails in Fig. 10. Suppose for instance that the $k_{m}$
nearest neighbors are matches following a different distribution than the
$k_{x}-k_{m}$ followers, with $k_{t}\leq k_{m}<k_{x}$. Measurement
$\hat{\ell}$ may be corrupted by this mixture of distributions, but since it
is essentially the inverse of an average over $k_{x}$ distances (13), the
estimate is robust provided that $k_{m}\ll k_{x}$. On the contrary,
measurement $\delta$ is very sensitive to distance $t$ (1). Therefore, if
$k_{t}<k_{m}$, distance $t=d_{k_{t}}$ is expected to be significantly smaller
than the others, and $\delta$ gets close to 1. Moreover, a value
$\delta\lesssim 1$ is indeed spread over a wide upper interval due to the
normalization mapping tuned with a very low ratio
$\nicefrac{{\hat{\ell}}}{{\ell_{0}}}$. Fig. 9 shows that DEEP, MSSPACEV, and
MSTuring have queries with low estimates $\hat{ell}$. This amplifies the
discrepancy and explains the heavy upper tail. This means that, under case 3,
the perturbation is bigger than statistically predicted by the model.

The fact that these failures do not happen in Fig. 7 where $k_{t}=10$, means
that $1<k_{m}<10$ in DEEP, MSSPACEV, and MSTuring. Indeed, the smaller $k_{t}$
the more likely a case 3 occurs.

Figure 10: Cases of failure. Comparison of the empirical p.d.f. of the
normalized data $\tilde{\Delta}$ and their related asymptotical models (see
Prop. 5.1) with $\ell_{0}=10$ and $(k_{t},k_{x})=(1,100)$. Expectation
($\triangle$), median ($\circ$), and mode ($\square$).

##  6 Discussion

As in Amsaleg et al. [2020], the analysis can be extended to two cases:

  * •

The modified point goes away from a reference point in the sense that the
target rank $k_{t}$ is bigger than the actual rank $k_{x}$.

  * •

It is the query $\mathbf{q}$ that is perturbed and the dataset points are
untouched. The query is pushed closer to (or away from) a target dataset point
so that its rank decreases (resp. increases).

The second point is easy to handle by re-defining
$\Delta_{n}=\nicefrac{{T_{n}}}{{X_{n}}}-1$ with $T_{n}\geq X_{n}$.

######  Proposition 6.1.

For two natural integers $k_{x}<k_{t}$, the relative amount of perturbation
$\Delta_{n}$ converges in distribution to
$\Delta=B^{-\nicefrac{{1}}{{\ell}}}-1$ with $B\sim Beta(k_{x},k_{t}-k_{x})$,
as the size $n$ of the dataset increases.

###### Proof.

From Prop. 4.2, we have that the ratio of two neighbor distances converges to
$B^{\nicefrac{{1}}{{\ell}}}$ with $B$ following a Beta distribution. Here, we
have $X_{n}<T_{n}$, so that $(X_{n}/T_{n})^{\ell}\leq 1$ converges to
$Beta(k_{x},k_{t}-k_{x})$ and $\Delta_{n}$ converges to
$\Delta=B^{-\nicefrac{{1}}{{\ell}}}-1$ ∎

The second point applies as well provided that the index $\ell$ now
characterizes the distances from the target dataset point. As $n$ increases,
the query and this dataset point get closer (for a fixed rank $k_{x}$) and
Amsaleg et al. [2020] argue that they asymptotically share the same index
value. In other words, the index $\ell$ can be considered as a very smooth
continuous function over the location in the space.

As said in the introduction, the vulnerability of retrieval also depends on
the ability to forge a content, say an image, whose extracted feature vector
exactly corresponds to $\mathbf{y}$. This point is out of our scope and Sabour
et al. [2016] and Tolias et al. [2019] give experimental evidence as far as
description with deep neural networks is concerned. If one knows the Lipschitz
constant $C$ of the neural network, then $C^{-1}\Delta$ gives a statistical
lower bound of the Euclidean distortion in the input space. Yet, such an image
may not exist because the description may not be a surjection. Targeting point
$\mathbf{y}$ reduces the distortion in the feature space but not necessarily
in the input space.

##  7 Conclusion

The article Amsaleg et al. [2020] gives asymptotical statistics about the
relative amount of perturbation outlining its dependence on the Local
Intrinsic Dimensionality. This new proof refines this result by providing the
exact expression of its cumulative distribution function for fixed $n$ (6) and
its convergence to the limit distribution (7). Expectation, median, and mode
show similar dependence on the Local Intrinsic Dimensionality index $\ell$.
The relative amount of necessary perturbation not only decreases in
expectation but also concentrates around this expectation when $\ell$
increases for a fixed rank ratio $\nicefrac{{k_{t}}}{{k_{x}}}$, or for an
increasing rank ratio and a fixed index $\ell$.

## References

  * Amsaleg et al. [2020] L. Amsaleg, J. Bailey, A. Barbe, S. M. Erfani, T. Furon, M. E. Houle, M. Radovanović, and N. X. Vinh.  High intrinsic dimensionality facilitates adversarial attack: Theoretical evidence.  _IEEE Transactions on Information Forensics and Security_ , pages 1–1, 2020.
  * Athalye et al. [2018] A. Athalye, N. Carlini, and D. Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 274–283. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/athalye18a.html.
  * Babenko and Lempitsky [2016] A. Babenko and V. Lempitsky.  Efficient indexing of billion-scale datasets of deep descriptors.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2055–2063, 2016.  doi: 10.1109/CVPR.2016.226.
  * Bahri et al. [2020] D. Bahri, H. Jiang, and M. Gupta.  Deep k-NN for noisy labels.  In H. D. III and A. Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 540–550. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/bahri20a.html.
  * Bingham et al. [1987] N. H. Bingham, C. M. Goldie, and J. L. Teugels.  _Regular Variation_.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1987.  doi: 10.1017/CBO9780511721434.
  * Bonnaillie-Noël [2004] V. Bonnaillie-Noël.  Méthode de Laplace et de la phase stationnaire.  Technical report, ENS de Cachan, 2004.
  * Botev et al. [2010] Z. I. Botev, J. F. Grotowski, and D. P. Kroese.  Kernel density estimation via diffusion.  _The Annals of Statistics_ , 38(5):2916 – 2957, 2010.  doi: 10.1214/10-AOS799.  URL https://doi.org/10.1214/10-AOS799.
  * Chen and Shah [2018] G. H. Chen and D. Shah.  _Explaining the Success of Nearest Neighbor Methods in Prediction_.  2018\.
  * Cohen et al. [2020] G. Cohen, G. Sapiro, and R. Giryes.  Detecting adversarial samples using influence functions and nearest neighbors.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2020.
  * Devroye et al. [1994] L. Devroye, L. Gyorfi, A. Krzyzak, and G. Lugosi.  On the strong universal consistency of nearest neighbor regression function estimates.  _The Annals of Statistics_ , 22(3):1371–1385, 1994.  ISSN 00905364.  URL http://www.jstor.org/stable/2242230.
  * Devroye et al. [1996] L. Devroye, L. Gyorfi, and G. Lugosi.  _A Probabilistic Theory of Pattern Recognition_.  Springer-Verlag, 1996.
  * Do et al. [2012] T.-T. Do, E. Kijak, L. Amsaleg, and T. Furon.  Enlarging hacker’s toolbox: deluding image recognition by attacking keypoint orientations.  In _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 1817–1820. IEEE, 2012.
  * Feller [1991] W. Feller.  _An Introduction to Probability Theory and Its Applications_ , volume 2.  Wiley, 2nd edition, 1991.
  * Gu et al. [2019] X. Gu, L. Akoglu, and A. Rinaldo.  Statistical analysis of nearest neighbor methods for anomaly detection.  _arXiv preprint arXiv:1907.03813_ , 2019.
  * H. A. David [2003] H. N. N. H. A. David.  _Order Statistics_.  Number 9780471389262. Wiley, 3rd edition edition, 2003.
  * Hill [1975] B. M. Hill.  A Simple General Approach to Inference About the Tail of a Distribution.  _The Annals of Statistics_ , 3(5):1163 – 1174, 1975.  doi: 10.1214/aos/1176343247.  URL https://doi.org/10.1214/aos/1176343247.
  * Jégou et al. [2011] H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg.  Searching in one billion vectors: re-rank with source coding.  In _ICASSP_ , pages 861–864, Prague, Czech Republic, May 2011. IEEE.  doi: 10.1109/ICASSP.2011.5946540.  URL https://hal.inria.fr/inria-00566883.
  * Ma et al. [2018] X. Ma, B. Li, Y. Wang, S. M. Erfani, S. Wijewickrema, G. Schoenebeck, D. Song, M. E. Houle, and J. Bailey.  Characterizing adversarial subspaces using local intrinsic dimensionality.  In _International Conference on Learning Representations_ , 2018.
  * Nguyen and Raff [2018] A. T. Nguyen and E. Raff.  Adversarial attacks, regression, and numerical stability regularization.  _AAAI’19 Workshop on Engineering Dependable and Secure Machine Learning Systems_ , arXiv preprint arXiv:1812.02885, 2018.
  * Papernot and McDaniel [2018] N. Papernot and P. McDaniel.  Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning.  _arXiv preprint arXiv:1803.04765_ , 2018.
  * Pham [2004] D.-T. Pham.  Fast algorithms for mutual information based independent component analysis.  _IEEE Transactions on Signal Processing_ , 52(10):2690–2700, 2004.  doi: 10.1109/TSP.2004.834398.
  * [22] M. Qi and Q. Chen.  Github of MSSPACEV.  URL https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B.
  * Sabour et al. [2016] S. Sabour, Y. Cao, F. Faghri, and D. J. Fleet.  Adversarial manipulation of deep representations.  In _ICLR_ , 2016.  URL http://arxiv.org/abs/1511.05122.
  * Sitawarin and Wagner [2019] C. Sitawarin and D. Wagner.  On the robustness of deep k-nearest neighbors.  In _2019 IEEE Security and Privacy Workshops (SPW)_ , pages 1–7. IEEE, 2019.
  * Tolias et al. [2019] G. Tolias, F. Radenovic, and O. Chum.  Targeted mismatch adversarial attack: Query with a flower to retrieve the tower.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5037–5046, 2019.
  * Wang et al. [2018] Y. Wang, S. Jha, and K. Chaudhuri.  Analyzing the robustness of nearest neighbors to adversarial examples.  In _International Conference on Machine Learning_ , pages 5133–5142. PMLR, 2018.
  * Weerasinghe et al. [2021] S. Weerasinghe, T. Abraham, T. Alpcan, S. M. Erfani, C. Leckie, and B. I. P. Rubinstein.  Closing the big-LID: An effective local intrinsic dimensionality defense for nonlinear regression poisoning.  In Z.-H. Zhou, editor, _Proc. of the 30th IJCAI_ , pages 3176–3184, 8 2021.  doi: 10.24963/ijcai.2021/437.  URL https://doi.org/10.24963/ijcai.2021/437.
  * Wu et al. [2008] X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, S. Y. Philip, et al.  Top 10 algorithms in data mining.  _Knowledge and information systems_ , 14(1):1–37, 2008.
  * Xiao and Wang [2021] Y. Xiao and C. Wang.  You see what i want you to see: Exploring targeted black-box transferability attack for hash-based image retrieval systems.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1934–1943, June 2021.
  * Yang et al. [2020] Y.-Y. Yang, C. Rashtchian, Y. Wang, and K. Chaudhuri.  Robustness for non-parametric classification: A generic attack and defense.  In S. Chiappa and R. Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 941–951. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/yang20b.html.

##  Appendix A Proof of Proposition 4.1

The c.d.f. $F_{\Delta_{n}}$ of r.v. $\Delta_{n}$ is given by:

$F_{\Delta_{n}}(\delta)=\begin{cases}&0,\quad\forall\delta\leq 0\\\
&1,\quad\forall\delta\geq 1,\end{cases}$ (14)

and $\forall\delta\in(0,1)$:

$\displaystyle F_{\Delta_{n}}(\delta)$ $\displaystyle=$
$\displaystyle\mathbb{P}(\Delta_{n}\leq\delta)=\mathbb{P}(X_{n}(1-\delta)\leq
T_{n})$ (15) $\displaystyle=$
$\displaystyle\int_{0}^{+\infty}\int_{(1-\delta)x}^{\infty}g_{n}(t,x)dt.dx$
(16) $\displaystyle=$
$\displaystyle\frac{1}{B(k_{x},n-k_{x}+1)}\int_{0}^{+\infty}H(\delta,x)f(x)[1-F(x)]^{n-k_{x}}dx,$
(17)

with

$\displaystyle H(\delta,x)$ $\displaystyle:=$
$\displaystyle\frac{1}{B(k_{t},k_{x}-k_{t})}\int_{(1-\delta)x}^{x}F^{k_{t}-1}(t)f(t)[F(x)-F(t)]^{k_{x}-k_{t}-1}dt$
(18) $\displaystyle=$ $\displaystyle
F(x)^{k_{x}-1}\int_{\frac{F((1-\delta)x)}{F(x)}}^{1}\frac{\tau^{k_{t}-1}[1-\tau]^{k_{x}-k_{t}-1}}{B(k_{t},k_{x}-k_{t})}d\tau$
$\displaystyle=$ $\displaystyle
F(x)^{k_{x}-1}\left(1-I_{\nicefrac{{F((1-\delta)x)}}{{F(x)}}}(k_{t},k_{x}-k_{t})\right),$

where the change of variable is defined by $\tau:=F(t)/F(x)$ and
$I_{x}(\alpha,\beta)$ is the regularized incomplete beta function. In the end,
with another change of variable $\xi:=F(x)$

$\displaystyle F_{\Delta_{n}}(\delta)$ $\displaystyle=$
$\displaystyle\frac{1}{B(k_{x},n-k_{x}+1)}\int_{0}^{1}H(\delta,F^{-1}(\xi))(1-\xi)^{n-k_{x}}d\xi$
(19) $\displaystyle=$
$\displaystyle\int_{0}^{1}\left(1-I_{\nicefrac{{F((1-\delta)F^{-1}(\xi))}}{{\xi}}}(k_{t},k_{x}-k_{t})\right)\frac{\xi^{k_{x}-1}(1-\xi)^{n-k_{x}}}{B(k_{x},n-k_{x}+1)}d\xi$
(20) $\displaystyle=$ $\displaystyle
1-\mathbb{E}\left[I_{\nicefrac{{F((1-\delta)F^{-1}(\Xi))}}{{\Xi}}}(k_{t},k_{x}-k_{t})\right],$
(21)

with $\Xi\sim Beta(k_{x},n-k_{x}+1)$.

##  Appendix B Proof of Proposition 4.2

We use the following version of Laplace’s method stated in Bonnaillie-Noël
[2004]:

######  Lemma B.1.

Let $g,h$ : $(0,1)\to\mathbb{R}$ two continuous functions s.t.

  * •

$\int_{0}^{1}|g(\xi)|e^{h(\xi)}d\xi<+\infty$

  * •

$\exists\delta_{0}>0,\forall\delta\in(0,\delta_{0}),\forall\xi\in[\delta,1),h(x)<h(\delta)$

  * •

Around $0^{+}$,

$\displaystyle g(\xi)$ $\displaystyle\approx$ $\displaystyle
A\xi^{\alpha},\quad\text{with }\alpha>-1$ (22) $\displaystyle h(\xi)$
$\displaystyle\approx$ $\displaystyle
a-c\xi^{\beta}+o(\xi^{\beta}),\quad\text{with }c>0,\beta>0$ (23)

Then

$\int_{0}^{1}g(\xi)e^{nh(\xi)}d\xi\approx\frac{A}{\beta}\Gamma\left(\frac{\alpha+1}{\beta}\right)e^{an}(cn)^{-\frac{\alpha+1}{\beta}}\quad\mbox{as
}n\to+\infty.$ (24)

We then rewrite (20) in the form
$\int_{0}^{1}g(\xi)e^{nh(\xi)}dx/B(k_{x},n-k_{x}+1)$ with

$\displaystyle h(\xi)$ $\displaystyle=$ $\displaystyle\log(1-\xi)$ (25)
$\displaystyle g(\xi)$ $\displaystyle=$
$\displaystyle\left(1-I_{\nicefrac{{F((1-\delta)F^{-1}(\xi))}}{{\xi}}}(k_{t},k_{x}-k_{t})\right)\xi^{k_{x}-1}(1-\xi)^{-k_{x}},$
(26)

Thanks to the assumption (2), we know that

$\lim_{\xi\to 0^{+}}\frac{F((1-\delta)F^{-1}(\xi))}{\xi}=\lim_{x\to
0^{+}}\frac{F((1-\delta)x)}{F(x)}=(1-\delta)^{\ell}.$ (27)

This allows to instantiate the constants defined in Lemma B.1 as

$\displaystyle A=I_{1-(1-\delta)^{\ell}}(k_{x}-k_{t},k_{t}),\quad\alpha$
$\displaystyle=$ $\displaystyle k_{x}-1,$ $\displaystyle a=0,\quad
c=1,\quad\beta$ $\displaystyle=$ $\displaystyle 1.$ (28)

This leads to the following asymptotical expression:

$F_{\Delta_{n}}(\delta)\approx
I_{1-(1-\delta)^{\ell}}(k_{x}-k_{t},k_{t})\frac{n!}{n^{k_{x}}(n-k_{x})!}\quad\mbox{as
}n\to+\infty,$ (29)

and to the limit function $F_{\Delta}$:
$\forall\delta\in(0,1)$

$F_{\Delta}(\delta):=\lim_{n\to+\infty}F_{\Delta_{n}}(\delta)=I_{1-(1-\delta)^{\ell}}(k_{x}-k_{t},k_{t}),$
(30)

thanks to the well-known asymptotic convergence
$\Gamma(n+\alpha)\approx\Gamma(n)n^{\alpha}$, $\forall\alpha\in\mathbb{C}$.

##  Appendix C Proof of proposition 4.3

This appendix uses the fact that $\Delta=1-B^{\nicefrac{{1}}{{\ell}}}$ with
$B\sim Beta(k_{t},k_{x}-k_{x})$.

###  C.1 Expectation

We did not find any close-form expression for $\mathbb{E}[\Delta]$. Yet, the
expectation and the variance of $B\sim Beta(k_{t},k_{x}-k_{x})$ equal

$\mathbb{E}[B]=\frac{k_{x}-k_{t}}{k_{x}},\quad\mathbb{V}[B]=\frac{\mathbb{E}[B](1-\mathbb{E}[B])}{(k_{x}+1)}.$
(31)

We see that $B$ concentrates around its expectation as $k_{x}$ becomes large.
The second order Taylor series around $\mathbb{E}[B]$ gives

$\displaystyle\Delta$ $\displaystyle=$ $\displaystyle
1-B^{\nicefrac{{1}}{{\ell}}}$ (32) $\displaystyle=$ $\displaystyle
A_{0}+A_{1}(B-\mathbb{E}[B])+A_{2}(B-\mathbb{E}[B])^{2}+o((B-\mathbb{E}[B])^{2})\quad\text{with}$
(33) $\displaystyle A_{0}$ $\displaystyle=$ $\displaystyle
1-\mathbb{E}[B]^{\nicefrac{{1}}{{\ell}}},\quad
A_{1}=-\nicefrac{{1}}{{\ell}}\mathbb{E}[B]^{\nicefrac{{1}}{{\ell}}-1},\quad
A_{2}=-\nicefrac{{1}}{{2\ell}}(\nicefrac{{1}}{{\ell}}-1)\mathbb{E}[B]^{\nicefrac{{1}}{{\ell}}-2}.$
(34)

Applying the expectation operator on both sides of the equation we obtain: for
$k_{x}\gg 1$,

$\displaystyle\mathbb{E}[\Delta]$ $\displaystyle\approx$ $\displaystyle
1-\mathbb{E}[B]^{\nicefrac{{1}}{{\ell}}}-\frac{1}{2\ell}\left(\frac{1}{\ell}-1\right)\mathbb{E}[B]^{\nicefrac{{1}}{{\ell}}-2}\mathbb{V}[B]=1-\left(\frac{k_{t}}{k_{x}}\right)^{\nicefrac{{1}}{{\ell}}}\left(1-\frac{\ell-1}{2\ell^{2}}\frac{k_{x}-k_{t}}{k_{t}(k_{x}+1)}\right).$
(35)

###  C.2 Median

Translating quantiles of $B$ to quantiles of $\Delta$ is easy as $x\to
1-x^{\nicefrac{{1}}{{\ell}}}$ is a strictly decreasing function over $(0,1)$:
The $p$-quantile of $B$ equals $I^{-1}_{p}(k_{t},k_{x}-k_{t})$ so that the
$p$-quantile of $\Delta$ equals
$1-(I^{-1}_{1-p}(k_{t},k_{x}-k_{t}))^{\nicefrac{{1}}{{\ell}}}$. For instance,
the median $\bar{\Delta}$ of $\Delta$ is simply
$\bar{\Delta}=1-\bar{B}^{\nicefrac{{1}}{{\ell}}}$. The median $\bar{B}$ of
$Beta(\alpha,\beta)$ is usually approximated by
$(\alpha-\nicefrac{{1}}{{3}})/(\alpha+\beta-2/3)$ for $\alpha\geq 2$ and
$\beta\geq 2$. This translates to the following approximation: for $k_{t}\geq
2$ and $k_{x}\geq k_{t}+2$:

$\displaystyle\bar{\Delta}$ $\displaystyle\approx$ $\displaystyle
1-\left(\frac{k_{t}-\nicefrac{{1}}{{3}}}{k_{x}-\nicefrac{{2}}{{3}}}\right)^{\nicefrac{{1}}{{\ell}}}=1-(\nicefrac{{k_{t}}}{{k_{x}}})^{\nicefrac{{1}}{{\ell}}}\left(1+\frac{2k_{t}-k_{x}}{k_{t}(3k_{x}-2)}\right)^{\nicefrac{{1}}{{\ell}}}.$
(36)

###  C.3 Mode

We first compute the p.d.f. by derivating the c.d.f $F_{\Delta}$ (7):

$f_{\Delta}(\delta|\ell)=\frac{\ell}{B(k_{x}-k_{t},k_{t})}\left(1-(1-\delta)^{\ell}\right)^{k_{x}-k_{t}-1}(1-\delta)^{k_{t}\ell-1}\mathds{1}_{[0,1]}(\delta).$
(37)

If $k_{t}\ell>1$ and $k_{x}-k_{t}>1$, the derivative of the p.d.f. cancels in
three points: $\delta\in\\{0,\delta_{m},1\\}$. Since
$f_{\Delta}(0)=f_{\Delta}(1)=0$, and $f_{\Delta}(\delta)\geq
0,\,\forall\delta\in(0,1)$, this shows that

$\delta_{m}:=1-\left(\frac{k_{t}\ell-1}{(k_{x}-1)\ell-1}\right)^{\nicefrac{{1}}{{\ell}}}=1-\left(\frac{k_{t}}{k_{x}}\right)^{\nicefrac{{1}}{{\ell}}}\left(1+\frac{(\ell+1)k_{t}-k_{x}}{\ell
k_{x}k_{t}-(\ell+1)k_{t}}\right)^{\nicefrac{{1}}{{\ell}}}$ (38)

is the unique maximum, hence the mode of this distribution.

###  C.4 Special Case: $k_{t}=1$

If $k_{t}=1$, then $B=(1-\Delta)^{\ell}\sim Beta(1,k_{x}-1)$ and
$K:=B^{\nicefrac{{1}}{{\ell}}}=1-\Delta$ follows by definition a Kumaraswamy
distribution $\mathcal{K}(\ell,k_{x}-1)$. This gives simpler formulas:

  * •

Expectation:

$\mathbb{E}[\Delta]=1-\mathbb{E}[B]=1-(k_{x}-1)B(1+\nicefrac{{1}}{{\ell}},k_{x}-1).$
(39)

  * •

Median:

$\bar{\Delta}=1-\bar{K}=1-\left(1-2^{-\frac{1}{k_{x}-1}}\right)^{\nicefrac{{1}}{{\ell}}}.$
(40)

  * •

Mode:

$\mathsf{mode}=1-\left(\frac{\ell-1}{(k_{x}-1)\ell-1}\right)^{\nicefrac{{1}}{{\ell}}}.$
(41)

##  Appendix D Experimental Results

This appendix shows figures comparing on the left the empirical joint p.d.f.
$\pi(\ell,\delta)$ (learned with k.d.e. [Botev et al., 2010]) and its
theoretical counterpart, and on the right the comparison of the empirical
(learned with k.d.e. [Pham, 2004]) and theoretical p.d.f. of the normalized
r.v. $\tilde{\Delta}$ defined in Prop. 5.1 (with $\ell_{0}=10$) for the
datasets BigANN, CIFAR, ImageNet, DEEP, MSSPACEV, and MSTuring (one per page).
Theoritical expectation ($\triangle$), median ($\circ$), and mode ($\square$)
are also displayed.

Figure 11: BigANN with $k_{x}=100$, $k_{t}=1$.

Figure 12: BigANN with $k_{x}=100$, $k_{t}=10$.

Figure 13: DEEP with $k_{x}=100$, $k_{t}=1$.

Figure 14: DEEP with $k_{x}=100$, $k_{t}=10$.

Figure 15: MSSPACEV with $k_{x}=100$, $k_{t}=1$.

Figure 16: MSSPACEV with $k_{x}=100$, $k_{t}=10$.

Figure 17: MSTuring with $k_{x}=100$, $k_{t}=1$.

Figure 18: MSTuring with $k_{x}=100$, $k_{t}=10$.

Figure 19: CIFAR with $k_{x}=1000$, $k_{t}=1$.

Figure 20: ImageNet with $k_{x}=1000$, $k_{t}=1$.


# Refining the Responses of LLMs by Themselves

Tianqiang Yan Tianqiang Yan. Email<EMAIL_ADDRESS>Tiansheng Xu
Future Network of Intelligence Institute, The Chinese University of Hong Kong,
Shenzhen 518172, P. R. China  Department of Mathematics, Faculty of Nature
Science, Imperial College, London SW7 2AZ, United Kingdom

###### Abstract

In the past few years, Large Language Models (LLMs) have generated
unprecedented enthusiasm, with models like GPT providing human-like responses
for a wide range of inquiries in nearly all domains. However, these models
often fail to deliver satisfactory answers aligned with users’ specific needs
on their first attempt, necessitating multiple iterations and additional user
input to refine the responses. This can lead to an unnecessary investment of
time and effort from users. In this paper, we propose a simple yet efficient
approach based on prompt engineering that leverages the large language model
itself to optimize its answers without relying on auxiliary models. We
introduce an iterative self-evaluating optimization mechanism, with the
potential for improved output quality as iterations progress, removing the
need for manual intervention. The experiment’s findings indicate that
utilizing our response refinement framework on the GPT-3.5 model yields
results that are on par with, or even surpass, those generated by the cutting-
edge GPT-4 model. Detailed implementation strategies and illustrative examples
are provided to demonstrate the superiority of our proposed solution.

##  1 Introduction

###  1.1 Revisiting Large Language Models

Large Language Models (LLMs) have become a significant development in deep
learning techniques, which allows them to understand and generate natural
language using vast amounts of textual data. LLMs have shown exceptional
potential and flexibility in various Natural Language Processing (NLP) and
Natural Language Generation (NLG) tasks, such as text summary, machine
translation, sentiment analysis, content creation, and conversational AI.
These models are trained using a self-supervised learning approach where they
learn from unlabeled data by predicting the following word or token in
sequential data. This process enables LLMs to decipher the syntax, semantics,
and general knowledge of human language while also retaining significant
amounts of factual information retrieved from the training dataset.

The emergence and evolution of LLMs were due to the advancements in
transformer models, a type of neural network that utilizes attention
mechanisms to encode and decode sequential data. Vaswani et al. first proposed
transformer models [1], and since then, many variations, including BERT [2],
GPT-3 [3], XLNet [4], and XLM-RoBERTa [5], have been developed, demonstrating
unrivaled performance in several NLP benchmarks and tasks, further
highlighting the potency and versatility of LLMs.

OpenAI’s ChatGPT stands as one of the most renowned LLMs in the field, of
which the latest version is based on GPT-4 [6]. GPT-4 has demonstrated
performance that rivals or exceeds human experts in numerous interdisciplinary
tasks, while offering support for multimodal data and expanding the range of
applications for large language models to a previously unattained scale. At
present, the multimodal features of GPT-4’s ChatGPT remain inaccessible to
most users. Nonetheless, in regular conversations, the latest version of
ChatGPT has exhibited considerable enhancements in understanding and response
capabilities compared to its earlier iterations. In addition, the well-
developed commercialization of ChatGPT, exemplified by Microsoft’s GPT-4-based
Chat with Bing and Office Copilot, as well as a multitude of third-party
applications using GPT APIs, has facilitated the gradual permeation of LLM
concepts and applications across diverse fields and demographics. This has
established a significant milestone in the realm of computer science.

The superiority of LLMs represent a pivotal advancement in NLP research,
offering new prospects for language generation, dialogue systems, and creative
writing. As LLMs continue to evolve, they are expected to play an increasingly
critical role in dictating the direction of natural language processing and
machine learning research.

###  1.2 Studies on refining the responses of LLMs

Despite their impressive capabilities, these models are not without
limitations: obtaining a user’s desired answer in a single attempt remains a
challenging endeavor. Various factors contribute to this issue, such as biases
inherent in training data and model architectures, which can result in
incorrect or contextually inappropriate responses [7]. Moreover, the lack of
explainability and transparency in the decision-making process of these black-
box models further exacerbates the difficulty in optimizing model outputs for
user needs [8]. This phenomenon is primarily attributed to the challenges
faced by these models in comprehending nuanced and highly specialized contexts
or adhering to specific writing styles and formats while generating responses,
which often leads to inconsistencies and deviations from the desired output.
[9, 10].

The Reinforcement Learning with Human Feedback (RLHF) mechanism is a recent
advancement in the field of language learning models (LLMs) that aims to
optimize their interactive responses to human users. This innovative approach
is designed to incorporate human feedback in training LLMs to generate more
effective, accurate, and contextually relevant responses, while mitigating
potential pitfalls associated with traditional reinforcement-learning-based
methods [3]. One significant advantage of the RLHF mechanism lies in its
ability to leverage both expert demonstrations and preference comparisons to
build a reward model for the LLM, which enables the model to adapt and improve
its response generation based on human-provided feedback [11]. In order to
train the RLHF mechanism to optimize the LLM’s responses to human users, an
initial set of demonstrations is provided by human experts who interact with
the LLM, generating high-quality responses. These demonstrations are then
utilized to perform supervised fine-tuning [12]. Building upon this
foundation, the mechanism further incorporates user preference comparisons
through a process wherein the LLM generates multiple candidate responses, and
users are asked to rank or rate these responses according to their relevance,
usefulness, and quality. To adjust and update the reward model accordingly,
the RLHF mechanism employs an algorithm that computes the gradients of the
reward model based on the aggregated user feedback [11].

Despite RLHF’s numerous advantages in training LLMs, one major concern is the
possibility of negative side effects from over-optimizing to human feedback,
potentially leading the LLM to generate uninformative or excessively verbose
responses in order to maximize its perceived reward [12]. Additionally, the
reliance on human-generated demonstrations and feedback inherently introduces
the potential for bias or inconsistency into the training process, which may
influence the performance and behavior of the resulting LLM. In the meantime,
the integration of RLHF in LLMs demands high quality volunteer or user
responses, leading to increased time and monetary costs.

Another extensively examined research study elucidated that LLMs exhibit a
chain-of-thought cognition, and concurrently emphasized that deconstructing
the inferential procedure of a problem via chain-of-thought prompting may
serve to augment the model’s proficiency in addressing intricate challenges
[13]. Fundamentally, this concept necessitates users to meticulously dissect
their queries prior to inputting them into comprehensive language models or to
encourage the model to deliver responses accompanied by an elaborate reasoning
process. If the RLHF optimization procedure is encapsulated into four stages:
“User formulates a query, model proffers a resolution, user evaluates the
quality of the solution, model fine-tunes based on assessment,” then chain-of-
thoughts prompting embodies a more efficacious application-tier feedback
optimization technique. This is attributed to its regardlessness of whether
the model itself has undergone optimization, and its potential capacity to
facilitate the model in producing dependable replies in a singular endeavor.
Nonetheless, the challenge with the chain-of-thought theory is that if a
user’s query is manually dissected, the model’s ability to generate a reliable
response hinges on whether the user has accurately provided the decomposed
version of the corresponding question. On the other hand, if the user requests
the model to deliver step-by-step answers, but there is a discrepancy between
the model’s interpretation of the problem and the user’s original purpose, the
ultimate solution can also be entirely off-course. In summary, both RLHF and
chain-of-thought prompting offer valuable advantages. As such, our aim is to
integrate the strengths of these two methods and develop a fast to deploy,
fully automated strategy to improve the performance of LLMs.

In this study, we concentrate on the exploration of application mechanisms
employed by prevalent LLMs. Our approach is predicated exclusively upon user
inquiries, LLM responses, and judicious supplementary prompts, aiming to
enhance the quality of LLM feedback. It’s important to note that the term
“quality” used here (including the same expression that appears later)
encompasses multiple metrics, including but not limited to the accuracy,
comprehensiveness, and conciseness of the answer. Explicitly, we propose a
feasible methodology that obviates the necessity for ancillary models or
supplementary manual interventions, enabling an LLM to autonomously refine its
response to a query through a prompt-driven, adaptively iterative self-
assessment and optimization process. With this paradigm as our goal, we design
a viable, general-purpose optimization mechanism that is inspired the ideas of
conversational reinforcement learning and chain-of-thought. Our contributions
can be concluded as:

  * •

We provide a novel paradigm to refine LLMs’ responses in an independent,
application-level, and fully automatic way.

  * •

Our paradigm, along with the implementation on its basis, allows instant
deployment with any available LLM APIs, while requiring nearly zero
development knowledge.

  * •

The implementation is examined with possible daily inquiries, and the joint
optimization scheme achieves overall the best outcome.

The following content of this report is arranged as follows: In Section II,
the proposed optimization scheme is introduced, and the three derived
solutions are described. In Section III, the detailed settings and the results
of our testing are demonstrated. Eventually, we conclude our study in Section
IV.

##  2 The adaptive optimization paradigm

In this paper, we design a highly-efficient, fully-automatic interaction
mechanism grounded in the application layer of large language models (LLMs).
Our approach enables adaptive optimization of AI-generated responses without
necessitating human involvement, while simultaneously eschewing the need for
fine-tuning the underlying language model or introducing supplementary models.
Additionally, the framework’s exclusive focus on the application layer makes
it remarkably convenient for users to integrate it with LLM APIs. In this
section, we will provide a thorough explanation of the optimization process.

Figure 1: This is an illustration of using our iterative optimization
framework to enhance the answers provided by LLM in response to user queries.
The diagram depicts one iteration of the optimization process, involving three
agents: the user (depicted as an avatar), a remote LLM server (represented by
a robot), and a terminal (symbolized by a computer). The automation loop is
enclosed within a dashed box.

###  2.1 The overall framework

The proposed optimization process can be outlined in the following steps:

  1. 1.

User step: The user inputs a query into the terminal and sends it via an API
to the remote LLM server, with a designated maximum number of optimization
iterations.

  2. 2.

Automatic step 1: The remote LLM server initially responds to the query by
producing a model-generated answer and returning it to the terminal.

  3. 3.

Automatic step 2: The terminal integrates the user query and the model’s
previous response to form a prompt, instructing the LLM model to analyze its
initial answer, identify any limitations, and provide feedback accordingly.

  4. 4.

Automatic step 3: The terminal generates an optimization prompt, combining the
LLM’s response, the user’s query, and the deficiency analysis, and sends it to
the remote server for improvement. The LLM model infers an updated answer and
sends it back to the terminal.

  5. 5.

Automatic step 4: The terminal receives the optimized response and generates a
prompt that combines the optimized answer with the previous response and the
user’s query, asking the model to determine if the optimized answer is an
improvement. The comparison result is then returned to the terminal.

  6. 6.

Automatic step 5: If the comparison result shows that the optimized answer is
better, the terminal utilizes a greedy strategy to repeat the automatic
optimization process (from step 3, automatic step 2) until the maximum
iterations have been reached. If the result is not improved, the terminal ends
the optimization process and returns the previous response.

Figure 1 offers an intuitive portrayal of our response refinement strategy,
exemplified through a simulated optimization process. The optimization process
as a whole is mainly automated through the terminal interactions with the
model API, with the exception of the user setting an upper limit for the
number of optimization loops. In practical applications, the specific
optimization process is hidden from the user, and they will receive a refined
response directly after inputting their question.

It should be noted that the interaction logic chain throughout the entire
enhance process is first-order, meaning that the scheme does not require the
LLM to remember the entire previous optimization process. This is done to
prevent large token costs and premature depletion of tokens. Furthermore, the
optimization process we have designed can ensure the reliability of this
first-order optimization mode. The specific reasons for this will be explained
in 2.2.

###  2.2 Refining the responses of LLMs by themselves

We have proposed an iterative optimization paradigm that integrates ideas from
self-supervised reinforcement learning and chain of thought.

Figure 2: The flowchart depicting the entire process of an adaptive iterative optimization mechanism. The deep blue rounded rectangles represent variables generated by the user, the black ones represent variables generated by the terminal, and the light blue ones represent variables generated by the remote model. A "$\oplus$" denotes the prompt combination operation. Table 1: Settings of the implemented structure of the response optimization LLM | Module | Prompt used
---|---|---
GPT-3.5-Turbo | Defect analysis |  Please list the defects of answer $a$ to the question $q$. List the defects in one sentence instead of a list with line breaks!
Guided optimisation |  The answer $a$ to the question $q$ is not optimal because that $d$. Please refine the answer providing a better one regarding the aforementioned flaw. You should provide nothing but the answer.
Voting for better |  The question is $q$, to which there are two optimal answers, one is $a$, the other one is $a^{*}$. Please answer either "1" or "2" if you think one of them is better, or "0" if you think they’re equally good. Do not reply anything else than a number!
Table 2: List of the selected questions and the corresponding reference answers. The reference answers are given by the human expert. Question |  Reference Answer
---|---
How to replace the memory on a 2020 Apple M1 processor version MacBook Air? |  In fact, the memory of this Macbook is NOT upgradable.
How to use the four numbers 2, 2, 8, and 8 along with basic arithmetic operations to obtain 24, with each number used exactly once? |  The answer varies. Any answer that meets the requirements is acceptable.
The first five numbers in a sequence are 2, 3, 6, 15, and 45, respectively. If the sixth number has only one decimal place and the sequence is incremented, what may be the sixth number? |  The answer can be 157.5, or more rigorously, multiple since this is an open question with limited conditions given.
Who was the father of Shinkansen? |  Shinji Sogō is credited with the creation of the first "bullet train", the Tōkaidō Shinkansen.
Why have Formula 1 racing cars adopted the design of halo since 2016? |  F1 officially adopted the design in 2018, NOT 2016. It is for protecting the drivers from potential head damage.
Figure 3: Answers of the five selected questions generated by the original
GPT-3.5-Turbo, the original GPT-4, and the refined GPT-3.5 (horizontal
comparison) Figure 4: Answers of the five selected questions generated by the
two pruned variations of the refined GPT-3.5, i.e. the blind refinement
version and the reckless refinement version (longitudinal comparison). “NR”
refers to that the process is essentially equivalent to the complete refined
GPT-3.5 framework, so there’s no need for a duplicate experiment.

Upon revisiting the optimization strategy of RLHF, it is apparent that the two
key steps in our refinement mechanism – namely, feedback defect analysis and
defect-guiding optimization logic – are fundamentally akin to those of RLHF.
However, there are notable distinctions between the two. Whereas RLHF is
geared towards LLMs still in their development and debugging phase with a
focus on “human feedback,” our optimization approach leverages self-evaluation
and self-optimization (SESO) through conversational self-interaction processes
that predominantly rely on prompt engineering. Prompt engineering represents a
milestone in the field of natural language processing that has emerged
concomitantly with the rise of large language models. Enabled by the powerful
contextual comprehension and reasoning capabilities inherent in contemporary
LLMs, prompt engineering allows for the specification of human-readable
prompts tailored to task objectives, thus empowering the model to deliver
desired outputs. To facilitate an examination of potential deficiencies in an
LLM’s reponse to a given query, all that is required is the transmission of a
pre-designed prompt to a remote server which is capable of conveying such a
request and providing the desired feedback. To construct a proficient prompt,
three critical constituents must be integrated: the initial inquiry posed by
the user, the present response generated by the LLM in reference to the
inquiry, and prompts that steer the model towards accurate comprehension,
analysis, and feedback aligned with the desired objectives. Moreover, in an
attempt to mitigate the potential inclusion of extraneous information in LLM
outputs, prompts can be augmented with limiting cues. For example, the prompt
may conclude with a directive such as “provide the analysis result only” to
focus the model’s output on specific aspects relevant to the query.

As our optimization strategy relies on an iterative process, an essential
element of our solution is an iterative self-termination mechanism based on a
voting method utilizing LLM. When the optimization process advances to this
stage, the terminal has already cached the user’s question, the pre-optimized
LLM response, and the post-optimized response. The essence of this iterative
self-termination strategy is to compare the model’s answers before and after
optimization based on the user’s question and select the one it considers
superior. The reason for such a judgment mechanism, instead of simply
iterating optimization until the user’s maximum optimization times are
reached, is that we cannot guarantee that the LLM output is 100% reliable. In
simple terms, whether the optimized answer generated by the model truly
achieves the goal of “optimization” is not entirely certain, depending on many
factors, including whether the model correctly understands the user’s intent,
and whether it accurately digests the defects in the previous answer and makes
targeted improvements. As the solution operates at the application level, and
the model remains a black box, this self-termination strategy supports
adaptive iterations while avoiding any potential negative consequences from
further optimization beyond the optimal point. To summarize, this iterative
optimization self-termination mechanism contributes to the stability of the
output while supporting the process’s adaptability.

This mechanism is also prompt-driven. The terminal integrates the user’s
query, the current and previous answers from the model, and then employs a
voting prompt to send the combined input to a remote server. A newly
initialized model returns its judgment result. To facilitate the terminal in
producing appropriate responses based on the voting result, it is critical to
add an limiting instruction. Assuming that the labels of the responses before
and after optimization are “1” and “2” respectively, the purpose of the
limiting instruction to allow the remote model to only return content limited
to be one of the two labels. When the model determines that the current
response would better answer the user’s query, it employs a greedy strategy by
repeating the previously mentioned optimization steps. On the other hand, if
the model determines that the previous answer is still the best response, it
returns that answer to the user.

Another crucial design aspect of our approach is that the response
optimization mechanism of this process is not blind, which attributes to the
defect-guided enhancement. The inspiration for this optimization method comes
from our understanding of the concept of the chain of thought [13]. The idea
fundamentally involves using explicit guidance or requiring the model to
output the reasoning process in order to improve the robustness of the output
of large language models as much as possible. The core purpose of this idea is
to prevent the model from blindly searching and generating answers. In the
application scenario targeted by our solution, skipping the defect analysis
and guided optimization steps would lead to a completely random optimization
path, which will further result in the instability of the optimization
process. For example, assuming the user’s question is “Where were the 2012
Olympics held?” and the model’s initial response is “The 2012 Olympics took
place in London, UK, opening on July 27th and closing on August 12th.” It can
be challenging to optimize this answer, even for a human. However, by
providing some guidance information to the model, such as “The original
question only asks about the location of the Olympics, while the previous
answer includes irrelevant time information,” the model can focus its
optimization effort and remove the unnecessary time information from the
refined answer with high probability.

We can summarize the entire process into a flow structure, as shown in Figure
2, based on the various optimization nodes mentioned above. The framework
operates with first-order memory since it ensures that each iteration produces
a results that is theoretically better than all previous optimization results.
Thus, the procedure effectively avoids the accumulation of previous outcomes,
which could lead to an increase in token consumption as the number of
iterations increases. It’s noteworthy that since prompts are based on natural
language, the design of prompts involved in each module in the figure may
vary. Our focus in this paper is to provide such a comprehensive response
optimization framework. In Section 3, we present a series of experiment
results to demonstrate the effectiveness of our scheme. These experiments
showcase the superiority of our approach in refining the responses generated
by large language models.

##  3 Testing and result analysis

###  3.1 The implementation and experiment design

We have publicly released the source code of an intelligent conversational
programme on GitHub, implemented based on the reponse refinement paradigm
discussed in this article, while following a flexible modular design as Figure
2. The project is available through the following link:
https://github.com/henryyantq/OptimaLLM. Here, we provide details of the model
configurations and prompts used, as listed in Table 1.

To date, public APIs for other large language models are not yet available.
Thus, in this section, we will only use OpenAI’s GPT as the target model for
our optimization framework. As demonstrated in Table 1, the scheme is applied
to the GPT-3.5-Turbo model (hereafter referred to as the refined GPT-3.5),
which presents a promising opportunity for improvement due to its status as an
earlier version of the GPT family offering the chat completion interface.
Additionally, the GPT-3.5-Turbo boasts advantages in terms of faster response
generation and smaller computational overheads, making it a feasible choice
even if multiple iterations are required to improve the quality of the
original model’s responses. The consumption of computational resources and
time is fully manageable under these circumstances.

Table 3: The comprehensive assessment results provided by the human expert. The model name indicated in the corresponding row and column refers to the model whose generated answer is acknowledged as having the best performance on that specific question and quota. The evaluation targets only include the three models (GPT-3.5-Turbo, GPT-4, and refined GPT-3.5) in Figure 3. Quota |  Q1 |  Q2 |  Q3 |  Q4 |  Q5
---|---|---|---|---|---
Accuracy |  refined GPT-3.5 = GPT-4 |  refined GPT-3.5 |  All |  refined GPT-3.5 |  refined GPT-3.5 = GPT-4
Conciseness |  refined GPT-3.5 |  refined GPT-3.5 |  hard to decide |  refined GPT-3.5 |  refined GPT-3.5
Completeness |  GPT-4 |  refined GPT-3.5 |  GPT-3.5-Turbo |  refined GPT-3.5 |  GPT-4

We have chosen five problems commonly faced in daily human life to evaluate
the model, as presented in Table 2. Out of the five questions, questions 1, 4,
and 5 are factual and questions 2 and 3 are inferential. Of the three factual
questions, questions 1 and 5 themselves are somewhat misleading, particularly
question 5, which requires the model to identify erroneous information within
the question. As for the inferential questions, questions 2 and 3 have
multiple correct answers. Therefore, the model is considered correct if it
recognizes and provides any or all of the solutions that meet the criteria,
with question 2 requiring the model to provide at least one accurate answer.

The entire experiment procedure consists of two main stages. In the first
stage (the horizontal comparison testing), we compare the responses provided
by the primary GPT-3.5-Turbo, the refined GPT-3.5 and the GPT-4 when
addressing identical questions. The GPT-4’s response process will remain
unoptimized, enabling us to assess whether an earlier LLM with our enhancement
process applied can rival its original self as well as the current industry-
leading model in terms of response quality. Besides, we compared the
computational overhead incurred by the native GPT-4 model and the refined
GPT-3.5 model when addressing the same questions, emphasizing the cost
benefits of applying our peripheral optimization scheme over using a more
advanced model for refined feedback. In the second stage (the longitudinal
comparison testing), we carry out a comparative assessment of the influence of
the optimization framework’s completeness on the resulting response quality,
using the same set of questions. In specific terms, we design two simplified
versions based on the original optimization framework. The first simplified
version is called “blind refinement”, which simplifies the original guided
optimization mechanism by allowing the model to optimize without referencing
any prompts in each loop. The second simplified version is named “reckless
refinement”, whereby the voting mechanism is removed, ensuring that the
optimization process never automatically stops before reaching the
predetermined maximum number of iterations. The goal of this stage is to
observe and analyze the influence of various modules within the framework on
optimization outcomes, underscoring the significance of module integration.

It’s crucial to elaborate on the measuring approach we have taken. To begin
with, all the questions we selected for comparative testing have correct
answers, which minimizes the uncertainty of response output, reduces the
subjectivity of the evaluation process, and ensures the reliability of the
results presented. In addition, since humans still possess a superior
understanding and evaluative ability in language and question-answering, the
final evaluation of response quality for each question from different models
is carried out by a human expert. The assessment of response quality is based
on three criteria: accuracy, conciseness, and completeness. Accuracy measures
how correct the responses are. Conciseness refers to whether the model’s
answers contain a significant amount of unnecessary information. Completeness
measures whether the model can address all the key points raised in the
question. The human expert takes all three aspects into consideration and
provides a comprehensive evaluation accordingly.

Overall, the aforementioned experiments can intuitively illustrates the
comprehensiveness of our response optimization process, and highlights its
potential for enhancing real-world large language models as well as competing
against the very best.

###  3.2 Experiment results and analysis

The outcomes from both phase 1 horizontal comparative testing and phase 2
longitudinal comparative testing are presented in Figure 3 and Figure 4
respectively, meanwhile Table 5 presents a comprehensive assessment of all the
response outcomes to each question, as evaluated by the human expert.

To facilitate a more intuitive comparison for readers, we have not included
the intermediate results generated during the iterative optimization process.
If it is necessary to refer to the intermediate results during subsequent
analysis, we will enumerate them at the corresponding location.

Based on the comprehensive assessment results of the horizontal comparison
test (see Table 3), our refined GPT-3.5 model achieved an astonishing 100%
accuracy in answering these questions, a clear advantage over both the
original GPT-4 and GPT-3.5-Turbo models without any response optimization
strategies. In addition, the refined GPT-3.5 also surpassed all competitors
regarding the answer conciseness. Yet in terms of answer completeness,
although GPT-4 answered one question incorrectly, our refined GPT-3.5 model
could not surpass its advantage in delivering more thorough explanations.
Notably, the answers obtained from the refined GPT-3.5 are results of the
iterative optimization of the response refinement framework proposed in this
paper, built upon the initial answers provided by the native GPT-3.5-Turbo. As
it is obvious that GPT-3.5-Turbo performed the worst on account of the
results, this demonstrates that our paradigm is capable of refining the
accuracy and redundancy of the initial answers to produce new ones with higher
quality. Furthermore, although refined GPT-3.5 may require more time for
iteration, but its total computational cost is much lower than that of GPT-4.
Even when using the same number of tokens, refined GPT-3.5 with a maximum
iteration limit of 3 can save 5 to 10 times the API usage consumption, thus
greatly reducing the economic burden on users. The reason for the lower
computational cost is not only due to the use of a more economical model, but
also because of the contribution of the first-order memory of the optimization
framework mentioned earlier,since such operation mode does not exponentially
accumulate the number of tokens, and the resource cost of each iteration can
be considered almost constant.

The organic combination of each module in the optimization framework is also
essential for obtaining high-quality responses. From the answers provided by
variants of refined GPT-3.5 that have removed one key module for each question
(as shown in Figure 4), it can be seen that both weakening the purpose of
optimization (guided optimization mechanism) and removing the ability of self-
review and self-stop (voting mechanism) significantly reduce optimization
capabilities and even result in negative optimization.

We found some pivotal clues based on the intermediate results to explain the
reasons for the shortcomings. As an example of the iterative optimization
process for the second question using the blind refinement framework, the
initial response given by the native GPT-3.5-Turbo contained numerous
incorrect steps and an incorrect equation: "$(8\times 8)+2\div 2-9=24$". This
answer is problematic because the original question does not include the
number 9, does not allow for any numbers other than 8, 8, 2, 2 to be used in
the calculation, and the equation on both sides of the equals sign is actually
not equivalent. After the first round of iteration, the blind refinement
mechanism removed only the cumbersome steps, keeping the erroneous equation as
the new response, which was still clearly incorrect. Even after the second and
third rounds of iteration, this incorrect equation remained a major part of
the answer, resulting in a final optimized solution that was still incorrect.
This suggests that allowing the model to optimize without a clear purpose can
result in the model repeatedly rewriting the answer without actually improving
it. At the same time, in the example of the reckless refinement framework that
removes the voting module to deal with the same question, the model provided a
correct answer by the end of the second iteration, but unexpectedly produced
an incorrect answer by the third iteration. The lack of self-review and self-
stop mechanisms means that the model continued to optimize beyond the point
where it had already obtained the correct answer, and as a result, ended up
outputting an incorrect answer that was generated in the final round of
optimization. Both of these typical examples serve to underscore the integral
roles played by these two modules throughout the optimization process.

To sum up, We have substantiated through the conclusions of the above
experiments that using the iterative optimization framework proposed in this
paper on a large language model can significantly enhance the quality of the
generated answers at a lower cost Furthermore, it highlights the contributions
made by the guided optimization mechanism and the voting mechanism in
improving optimization capabilities.

##  4 Conclusion

In this paper, we introduce a fully-autonomous adaptive iterative response
optimization paradigm, inspired by concepts from RLHF and the chain of
thought. This approach relies solely on simple prompt engineering and the LLM
API, without the need for manual intervention, auxiliary models, or access to
internal structures and parameters of language models. Specifically, we
present a detailed optimization framework utilizing an efficient modular
design, applied to the GPT-3.5-Turbo. Our experiments show that our
optimization mechanism enables a less-capable model to achieve response
quality better than its original self, and even on par with one of the best
current models while reducing resource consumption. Through this scheme, we
demonstrate that in many situations, the existing question-answering
interaction paradigm may not fully harness the potential of generative
language models. Appropriately designing prompts and planning response
interaction logic is a crucial approach to further unleash a model’s
potential.

## References

  * [1] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  ArXiv, abs/1706.03762, 2017.
  * [2] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  ArXiv, abs/1810.04805, 2019.
  * [3] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, T. J. Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeff Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  ArXiv, abs/2005.14165, 2020.
  * [4] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  In Neural Information Processing Systems, 2019.
  * [5] Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov.  Unsupervised cross-lingual representation learning at scale.  In Annual Meeting of the Association for Computational Linguistics, 2019.
  * [6] OpenAI.  Gpt-4 technical report.  arXiv preprint arXiv:2303.08774, 2023.
  * [7] Alec Radford and Karthik Narasimhan.  Improving language understanding by generative pre-training.  2018\.
  * [8] Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 2021.
  * [9] Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and William B. Dolan.  Dialogpt : Large-scale generative pre-training for conversational response generation.  In Annual Meeting of the Association for Computational Linguistics, 2019.
  * [10] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman.  Superglue: A stickier benchmark for general-purpose language understanding systems.  ArXiv, abs/1905.00537, 2019.
  * [11] Paul Francis Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  ArXiv, abs/1706.03741, 2017.
  * [12] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe.  Training language models to follow instructions with human feedback.  ArXiv, abs/2203.02155, 2022.
  * [13] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Huai hsin Chi, F. Xia, Quoc Le, and Denny Zhou.  Chain of thought prompting elicits reasoning in large language models.  ArXiv, abs/2201.11903, 2022.