# Eigenvector decomposition to determine the existence, shape, and location of
numerical oscillations in Parabolic PDEs

Corban Harwood and Ethan Jensen

(December 2020)

Abstract. In this paper, we employed linear algebra and functional analysis to
determine necessary and sufficient conditions for oscillation-free and stable
solutions to linear and nonlinear parabolic partial differential equations. We
applied singular value decomposition and Fourier analysis to various finite
difference schemes to extract patterns in the eigenfunctions (sampled by the
eigenvectors) and the shape of their eigenspectrum. With these, we determined
how the initial and boundary conditions affect the frequency and long term
behavior of numerical oscillations, as well as the location of solution
regions most sensitive to them.

##  1 Introduction

Finite difference methods are powerful discretization techniques that
approximate the solutions of partial differential equations (PDE) by
partitioning the domain into a uniform grid. However, this method of
partitioning can lead to severe errors in the numerical solution. Von
Neumann[1] developed an analytic tool that relates the stability of the
numerical solution to the spacing in time, $\Delta t$. Similarly for stable
solutions, poorly chosen values for $\Delta t$ can lead to qualitative
differences in the numerical solution versus the true solution that manifest
as spurious waves[2], called numerical oscillations. Parabolic PDE are
powerful equations that describe many physical phenomena, such as heat flow
and particle diffusion. Reaction-diffusion equations in particular, such as
the Fisher-KPP equation and the FitzHugh-Nagumo equation have applications in
chemistry, and biology[3, 4]. All of these are PDE are affected by numerical
oscillations.[5, 6] Therefore, it is imperative that we understand the nature
of numerical oscillations.
Previous work by Main and Harwood[7] has demonstrated the dependence of
numerical oscillations on the eigenspectrum of the time-step matrix for two-
level finite difference schemes. Motivated by this discovery, this paper
calculates a set of conditions for guaranteeing the rapid decay of numerical
oscillations in linear diffusion PDE by taking advantage of symmetries in the
eigenvectors of various numerical methods. We also show how these conditions
may be extended to nonlinear diffusion PDE.

##  2 Theory

###  2.1 The Finite Difference Method

Finite differences are numerical methods that partition the solution into
discrete units in time and in space to numerically approximate the true
continuous solution. To discretize the PDE, spatial derivatives are
approximated with a Taylor series approximation[8], and then time derivatives
are approximated with a numerical scheme.

###  2.2 Special Properties of Toeplitz Matrices

Toeplitz matrices are important symmetric matrices that contain the finite
difference approximations of the second spatial derivative. For example, the
second central difference approximation is

$\frac{\partial^{2}}{\partial x^{2}}u(x)=\frac{u(x+\Delta x)-2u(x)+u(x-\Delta
x)}{\Delta x^{2}}+O(\Delta x^{2})$

Indexing each u, we have

$(u_{i})_{xx}=\frac{1}{\Delta x^{2}}(u_{i+1}-2u_{i}+u_{i-1})$

The corresponding Toeplitz matrix is

$T_{0}=\begin{bmatrix}-2&1&0&0\\\ 1&-2&\ddots&0\\\ 0&\ddots&\ddots&1\\\
0&0&1&-2\end{bmatrix}$

Using the tridiagonal matrix algorithm, we calculate the eigenvalues and
eigenvectors of $T_{0}$ analytically.[9] Its eigenvalues are defined by

$\lambda_{j}=-4\sin^{2}\left(\frac{\pi j}{2(k+1)}\right),\ j=1,2,....k$

The corresponding eigenvectors $x_{j}$ are indexed according to their
eigenvalues and are defined by sine eigenfunctions. The matrix of eigenvectors
S, where $S=\begin{bmatrix}x_{1}&x_{2}&\ldots&x_{k}\end{bmatrix}$ is defined
by

$S_{n,j}=\sin\left(\frac{\pi nj}{k+1}\right)$

This matrix S is one of the three most important matrices in all of Linear
Algebra[10], and it has many interesting properties and symmetries that we
make use of in this paper.

######  Lemma 1.

Let $S_{n,j}=\sin\left(\frac{\pi nj}{k+1}\right)$. Then,

$S^{-1}=\left(\frac{2}{k+1}\right)S$

###### Proof.

S contains all the eigenvectors of $T_{0}$. Since $T_{0}$ is symmetric, its
eigenvectors are orthogonal, so $S^{T}S=D$, for some diagonal matrix $D$.

$S_{n,j}=\sin\left(\frac{\pi nj}{k+1}\right)$
$\vec{x}_{j}^{T}\vec{x}_{j}=\sum_{n=1}^{k}\sin^{2}\left(\frac{\pi
jn}{k+1}\right)=\sum_{n=1}^{k}\frac{1}{2}+\sum_{n=1}^{k}\cos\left(\frac{2\pi
nj}{k+1}\right)=\frac{k+1}{2}$

Thus, we have

$S^{T}S=\left(\frac{k+1}{2}\right)I$

Since $S_{n,j}=S_{j,n}=\sin\left(\frac{\pi nj}{k+1}\right)$, $S$ is also
symmetric.

$\therefore S^{-1}=\left(\frac{2}{k+1}\right)S$

∎

######  Lemma 2.

Let $S_{n,j}=\sin\left(\frac{\pi nj}{k+1}\right)$. Then,

$S_{n,j}=(-1)^{n+1}S_{n,k+1-j}$

###### Proof.

$S_{n,j}=\sin\left(\frac{\pi nj}{k+1}\right)$ $S_{n,k+1-j}=\sin\left(\frac{\pi
n(k+1-j)}{k+1}\right)=(-1)^{n+1}\sin\left(\frac{\pi nj}{k+1}\right)$
$\therefore S_{n,j}=(-1)^{n+1}S_{n,k+1-j}$

∎

###  2.3 Numerical Schemes

Consider the heat equation $u_{t}=\delta u_{xx}$. First, approximating in
space, we have

$(u_{i})_{t}=\frac{\delta}{\Delta x^{2}}(u_{i+1}^{n}-2u_{i}^{n}+u_{i-1}^{n})$

Combining these relations into a relation for the entire solution vector, we
have

$\frac{\partial}{\partial t}(\vec{u}_{n})=\frac{\delta}{\Delta
x^{2}}T_{0}\vec{u}_{n}$ $d(\vec{u_{n}})=\frac{\delta\Delta t}{\Delta
x^{2}}T_{0}\vec{u}_{n}$

Since the PDE is linear, the exact solution in time is the matrix exponential

$\vec{u}_{n+1}=e^{rT_{0}}\vec{u}_{n}$

where $r=\frac{\delta\Delta t}{\Delta x^{2}}$ is a simplifying constant. To
discretize in time, finite difference approximations of PDE use a numerical
scheme, which approximate the matrix exponential solution. Below are a few of
the numerical schemes studied.[11]
Explicit Schemes (Forward Euler, Runge-Kutta)

$\vec{u}_{n+1}=(I+rT_{0})\vec{u}_{n}$
$\vec{u}_{n+1}=(I+rT_{0}+\frac{r^{2}}{2}T_{0}^{2})\vec{u}_{n}$
$\vec{u}_{n+1}=(I+rT_{0}+\frac{r^{2}}{2}T_{0}^{2}+\frac{r^{3}}{6}T_{0}^{3})\vec{u}_{n}$

Implicit Scheme (Backward Euler)

$\vec{u}_{n+1}=(I-rT_{0})^{-1}\vec{u}_{n}$

Semi-Implicit Scheme (Crank-Nicolson)[12]

$\vec{u}_{n+1}=(I-\frac{r}{2}T_{0})^{-1}(I+\frac{r}{2}T_{0})\vec{u}_{n}$

If we consider a general scheme $\vec{u}_{n+1}=M\vec{u}_{n}+\vec{B}$ where M
is the time-step matrix, then there exist polynomials p and q such that
$M=q^{-1}(rT_{0})p(rT_{0})$ because each numerical scheme is a Taylor
approximation to the matrix exponential. Thus, all time-step matrices for the
heat equation can derive their eigenvectors and eigenvalues from $T_{0}$. See
Theorem 4 in the Appendix.

##  3 Methodology

Numerical oscillations can only occur when the eigenvalues of the time-step
matrix start to become negative. Thus, numerical oscillations in the solution
can be prevented by restricting the eigenspectrum of the time-step matrices to
non-negative values (Non-negative Eigenvalue Condition).

######  Theorem 3.

[Fundamental Theorem of Numerical Oscillations] Let $u_{t}=\delta u_{xx}$ be
given by an approximation $u^{n+1}=Mu^{n}$ and let M = $R(T_{0})$ be a
rational function of $T_{0}$. Then, numerical oscillations are absent if and
only if

$|a_{j}|R(r\lambda_{j})\geq 0,\ \ j=1,2,3,...k$

where $a_{j}$ are the Fourier coefficients from the discrete finite sine
transform of $u_{0}-\overline{u}$ (initial condition minus the steady state),
and $R(r\lambda_{j})$ are the eigenvalues of M.

###### Proof.

All finite difference schemes of the heat equation are of the form

$\vec{u}_{n}=M\vec{u}_{n-1}+\vec{B}$

where $M=R(rT_{0})=q^{-1}(rT_{0})p(rT_{0})$ and
$\vec{B}=q^{-1}(rT_{0})\vec{b}$, where $\vec{b}$ is a sparse vector containing
the boundary conditions.

$\vec{u}_{n}=M^{n}u_{0}+\left(\sum_{k=0}^{n-1}M^{k}\right)\vec{B}$
$\vec{u}_{n}=M^{n}u_{0}+(M^{n}-I)(M-I)^{-1}\vec{B}$
$\vec{u}_{n}=M^{n}(u_{0}-(I-M)^{-1}\vec{B})+(I-M)^{-1}\vec{B}$ (1)
$\lim_{n\rightarrow\infty}\vec{u}_{n}=\lim_{n\rightarrow\infty}M^{n}(u_{0}-(I-M)^{-1}\vec{B})+(I-M)^{-1}\vec{B}$

Since the scheme is stable $\lim_{n\rightarrow\infty}M^{n}=0$. Thus,

$\overline{u}=(I-M)^{-1}\vec{B}$

where $\overline{u}$ is the steady state. Plugging this back into (1), we have

$\vec{u}_{n}=M^{n}(u_{0}-\overline{u})+\overline{u}$

Performing the eigenvector decomposition, we have

$\vec{u}_{n}=STS^{-1}(u_{0}-\overline{u})+\overline{u}$

From Theorem 1, we have

$\vec{u}_{n}=\frac{2}{k+1}STS(u_{0}-\overline{u})+\overline{u}$

From Theorem 4, we have

$\vec{u}_{n}=\frac{2}{k+1}\sum_{j=1}^{k}a_{j}R(r\lambda_{j})^{n}\vec{x}_{j}+\overline{u}$

Where $a_{j}$ are the Fourier coefficients from the discrete finite sine
transform of $u_{0}-\overline{u}$, $\lambda_{j},\vec{x}_{j}$ are the
eigenvalues and eigenvectors of $T_{0}$.
Thus, if $R(r\lambda_{j})<0$, solution components will oscillate as they are
being powered up unless $|a_{j}|=0$. Therefore, numerical oscillations are
absent if and only if

$|a_{j}|R(r\lambda_{J})\geq 0,\ \ j=1,2,3...k$

∎

Therefore, numerical oscillations are not just dependant on the numerical
scheme. The initial strength of the numerical oscillations is also dependant
on the smoothness of the initial condition and boundary conditions.

###  3.1 Eigenspectrums of numerical methods

The eigenspectrum of explicit methods for the heat equation take the form

$(\lambda_{M})_{j}=R(r\lambda_{j})=1+r\lambda_{j}+\frac{r^{2}}{2}\lambda_{j}^{2}+\frac{r^{3}}{6}\lambda_{j}^{3}$

The eigenspectrum of the Crank-Nicolson method for the heat equation is

$(\lambda_{M})_{j}=R(r\lambda_{j})=\frac{1+(r/2)\lambda_{j}}{1-(r/2)\lambda_{j}}$

Even-order Runge-kutta methods as well as the implicit backward Euler method
have a strictly positive eigenspectrum - these schemes do not produce
numerical oscillations.

###  3.2 Shape of Numerical Oscillations

Odd order Runge-Kutta methods, such as the forward Euler method, are
increasing functions. Likewise, the Crank-Nicolson eigenspectrum is also an
increasing function on $(-4,0)$. Since $\lambda_{j}=-4\sin^{2}\left(\frac{\pi
j}{2(k+1)}\right)$ is a decreasing function in j, the eigenvalues of the odd-
order Runge-Kutta methods and the Crank-Nicolson method are decreasing in j.

Thus, of the schemes that can produce numerical oscillations, the smallest
eigenvalues get paired with the highest frequency eigenfunction, and the
frequency of the corresponding eigenfunction gets smaller as the eigenvalue
gets bigger. Hence, if the eigenspectrum is partially negative, then the
eigenvalues that are negative will be indexed with the highest frequency
eigenvectors. This explains why numerical oscillations usually manifest as a
high frequency phenomenon in linear parabolic PDE.

##  4 Results

###  4.1 Balanced Eigenvalue Condition

From Theorem 3, the non-negative eigenvalue condition,

$|a_{j}|R(r\lambda_{j})\geq 0,\ j=1,2,3,...k$

ensures that no numerical oscillations occur in the solution. Beyond this,
however, is a secondary condition that guarantees fast-decaying numerical
oscillations, almost imperceptible relative to the numerical solution. We call
this the balanced eigenvalue condition, given by

$R(r\lambda_{j})+R(r\lambda_{k+1-j})\geq 0,\ \ |a_{j}|\geq|a_{k+1-j}|\
j=1,2,3,...\left\lfloor\frac{k+1}{2}\right\rfloor.$

The part $R(r\lambda_{j})+R(r\lambda_{k+1-j})\geq 0$ ensures that the
eigenfunction indexed by $k+1-j$ will decay faster than the corresponding
envelope eigenfunction indexed by $j$. The part $|a_{j}|\geq|a_{k+1-j}|$
ensures that the initial amplitude of the oscillating wave will start smaller
than the amplitude of the corresponding envelope.

The balanced eigenvalue condition is motivated by lemma 2. Lemma 2 shows that
eigenfunctions indexed by $k+1-j$ have a corresponding eigenfunction indexed
by $j$ which acts as an envelope, matching the magnitude of the eigenvector at
every index and equalling the eigenfunction at every odd index. These
relations from Lemma 2 are visualized in Figure 1.

Figure 1: Comparison of Matching Eigenfunctions

The initial conditions that satisfy $|a_{j}|\geq|a_{k+1-j}|$ are smooth
functions with little total variation, for example, a monotonic function[13].
Initial conditions that are not smooth incite numerical oscillations by
powering up the eigenvalues paired with the high frequency eigenvectors.
Disagreements between the initial condition and the boundary condition cause
numerical oscillations because large changes at the smallest level of
resolution powers up the eigenvalue of the highest frequency eigenvector.

The free parameters in the setup of the numerical solution are combined into
the simplifying constant $r=\delta\Delta t/\Delta x^{2}$. To get conditions
for r that predict numerical oscillations, we calculate the largest value of r
such that the non-negative eigenvalue condition and the balanced eigenvalue
condition are true for each numerical scheme.

Consider the heat equation

$u_{t}=\delta u_{xx}$

The time-step matrix for the heat equation is a rational function of $rT_{0}$.
Thus, the eigenvalues are rational functions of $r\lambda_{j}$ and the non-
negative and balanced eigenvalue conditions for the heat equation can be
solved in terms of $r\lambda_{j}$. Then, using the fact
$\textup{min}(\lambda_{j})=-4$ obtains appropriate bounds for r.

Explicit methods are conditionally stable. For the odd-order Runge-Kutta
methods, the balanced eigenvalue condition is met if the solution is
stable.[14] In contrast, the Crank-Nicolson method on the heat equation is
unconditionally stable. r can be increased indefinitely, but as it is
increased the balanced eigenvalue condition is violated and numerical
oscillations become both more prevalent and take longer to decay.

Consider the linear reaction diffusion equation

$u_{t}=\delta u_{xx}-\rho u$

with spatial discretization

$(\vec{u}_{n})_{t}=\left(\frac{\delta}{\Delta x^{2}}T_{0}-\rho
I\right)\vec{u}_{n}$

The time-step matrix of the linear reaction diffusion equation is also
rational function of $rT_{0}-\rho\Delta tI$. Thus, the eigenvectors remain the
same as those of the heat equation, and we can use the same kind of analysis.
However, the change in the eigenvalues means that the non-negative eigenvalue
condition and the balanced eigenvalue condition need to be recalculated. See
Table 1 for the Non-negative Eigenvalue conditions and balanced eigenvalue
conditions for each numerical scheme.

These oscillatory conditions are shown graphically in Figure 2.

Figure 2: Oscillatory Conditions

###  4.2 Demonstration

We demonstrate the effect of the initial conditions and boundary conditions
have on a numerical solution whose eigenspectrum satisfies the balanced
eigenvalue condition. In Figure 3 we show color maps of various numerical
solutions to the heat equation using the forward Euler method, with $r=0.5$.

Figure 3: Simulations of the heat equation

The top image depicts a solution to the heat equation with a very smooth
initial condition, and agreeing boundary conditions. The numerical scheme
satisfies the balanced eigenvalue condition. Hence, minimal numerical
oscillations are present. The middle image depicts a solution to the heat
equation with a very noisy initial condition. Despite satisfying the balanced
eigenvalue condition this initial condition incited numerical oscillations
that match the frequency of the high-frequency components in the initial
condition which are seen in the figure as stripes. The bottom image depicts a
solution to the heat equation whose initial condition is smooth, but whose
left-hand boundary condition did not match the initial condition, creating
very slight numerical oscillations on the left edge.

###  4.3 Nonlinear Reaction-Diffusion Equations

In addition to linear PDE, we also studied various nonlinear PDE.

Nonlinear Reaction-Diffusion: $u_{t}=\delta u_{xx}-\rho u^{2}$
Fisher-KPP: $u_{t}=\delta u_{xx}-\rho u(1-u)$
FitzHugh-Nagumo Reaction-Diffusion: $u_{t}=\delta u_{xx}-\rho u(1-u)(a-u)$

Each of these PDE has at least one stable steady state solution, a curve
satisfying the boundary conditions that is drawn towards some constant
function $u_{0}$. Table 1 shows the linearizations of the three nonlinear PDE
about their corresponding steady states. Since the linearizations of the
nonlinear PDE match the form of the linear diffusion PDE, the non-negative
eigenvalue condition of the linearizations are a worst-case bounding to
prevent numerical oscillations (see corollary 6.1 in the appendix).

###  4.4 Location of Numerical Oscillations

Combining the nonlinear portion with the diffusion term produces orthogonal
eigenfunctions[15] with shapes that resemble functions balanced between pure
sine waves and elementary basis vectors. Figure 4 shows the eigenvectors of
the time-step matrix of the Forward Euler method on the Fisher-KPP equation
about a monotone steady state, ordered by eigenvalue, with r=1 and
$\rho/\delta=1$. The eigenvectors with the smallest eigenvalues retain much of
their wave-like form at the end of the solution closest to the stable steady
state and localising the numerical oscillations to the portion of the solution
nearest to the stable equilibrium.

###  4.5 Application of the Balanced Eigenvalue Condition

Our work also showed that a symmetry in the eigenvectors of nonlinear schemes,
similar to that from lemma 2 exists for these eigenfunctions, meaning that the
balanced eigenvalue condition can be partially applied for numerical methods
of nonlinear PDE. In Figure 5, eigenvectors from the time-step matrix of the
Fisher-KPP equation are shown, split between those that are more tightly
centered (shown in gray), and those that maintain wave-like properties (shown
in color). Corresponding eigenfunctions having components that closely match
each other in magnitude are shown with the same color.

Figure 4: Eigenvectors for the Fisher-KPP equation

Figure 5: Nonlinear Eigenfunction Symmetry

##  5 Discussion

###  5.1 Characterization of Numerical Oscillations

In this paper, Fourier analysis was used to give a description of the
numerical solution as a sum of waves. Numerical oscillations, in turn were
characterised by the high frequency sine eigenfunctions. Finding patterns in
these eigenfunctions established a carrier wave relationship between high-
frequency eigenfunctions and their opposing low-frequency eigenfunctions. The
Fourier analysis showed that the balanced eigenvalue condition which results
from this pairing guarantees that the numerical oscillations decay fast
relative to the solution and that initial conditions can be chosen to either
create or avoid numerical oscillations.

###  5.2 Analysis of Numerical Oscillations in Nonlinear PDE

In addition to linear PDE, several nonlinear reaction-diffusion PDE were also
studied. By looking at the method matrices of the numerical methods about
stable steady-states, the structure of the eigenfunctions of the nonlinear
equations could be deduced. The nonlinear component, mixed with the diffusion
component creates orthogonal eigenfunctions which resemble sine functions when
the solution gets close to a stable equilibrium. This localizes the numerical
oscillations to the part of the function closest to the stable equilibrium.
Additionally, the rough symmetry of these wave-like components suggests that
the balanced eigenvalue condition could also be applied to the numerical
methods of nonlinear reaction diffusion equations.

###  5.3 Final Remarks and Further Research

In contrast to von Neumann stability analysis, this paper makes use of the
precise values of the eigenvalues of the numerical methods to make claims
about the quality of the numerical solution. The same method of analysis can
likely be generalized to other numerical techniques that rely on matrix
representations of the solution. Finite volume and finite element methods for
example, although using different methods to discretize in space, all make use
of a time-step matrix to approximate PDE in time.

## References

  * [1] J. G. Charney, R. Fjörtoft, and J. v. Neumann, “Numerical integration of the barotropic vorticity equation,” Tellus, vol. 2, no. 4, pp. 237–254, 1950.
  * [2] T. K. Lee and X. Zhong, “Spurious numerical oscillations in simulation of supersonic flows using shock-capturing schemes,” AIAA journal, vol. 37, no. 3, pp. 313–319, 1999.
  * [3] R. FitzHugh, “Mathematical models of excitation and propagation in nerve,” Biological engineering, pp. 1–85, 1969.
  * [4] A. Kolmogorov, I. Petrovskii, and N. Piskunov, “Study of a diffusion equation that is related to the growth of a quality of matter, and its application to a biological problem,” Byul. Mosk. Gos. Univ. Ser. A Mat. Mekh, vol. 1, no. 1, p. 26, 1937.
  * [5] J. Teixeira, “Stable schemes for partial differential equations: the one-dimensional reaction–diffusion equation,” Mathematics and Computers in Simulation, vol. 64, no. 5, pp. 507–520, 2004.
  * [6] V. John and P. Knobloch, “On spurious oscillations at layers diminishing (sold) methods for convection–diffusion equations: Part i–a review,” Computer methods in applied mechanics and engineering, vol. 196, no. 17-20, pp. 2197–2215, 2007.
  * [7] R. C. Harwood and M. Main, “Eigenvalue dependence of numerical oscillations in parabolic partial differential equations,” arXiv preprint arXiv:1701.04798, 2017.
  * [8] D. Eberly, “Derivative approximation by finite differences,” Magic Software, Inc, 2008.
  * [9] G. Hu and R. F. O’Connell, “Analytical inversion of symmetric tridiagonal matrices,” Journal of Physics A: Mathematical and General, vol. 29, no. 7, p. 1511, 1996.
  * [10] G. Strang, “The discrete cosine transform,” SIAM review, vol. 41, no. 1, pp. 135–147, 1999.
  * [11] U. M. Ascher, S. J. Ruuth, and R. J. Spiteri, “Implicit-explicit runge-kutta methods for time-dependent partial differential equations,” Applied Numerical Mathematics, vol. 25, no. 2-3, pp. 151–167, 1997.
  * [12] J. Crank and P. Nicolson, “A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type,” in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 43, pp. 50–67, Cambridge University Press, 1947.
  * [13] B. Booton, “General monotone functions and their fourier coefficients,” Journal of Mathematical Analysis and Applications, vol. 426, no. 2, pp. 805–823, 2015.
  * [14] C. B. Moler, Numerical computing with MATLAB.  SIAM, 2004.
  * [15] A. Osipov, “Evaluation of small elements of the eigenvectors of certain symmetric tridiagonal matrices with high relative accuracy,” Applied and Computational Harmonic Analysis, vol. 43, no. 2, pp. 173–211, 2017.

##  6 Appendix

######  Theorem 4.

Let p and q be polynomials, A and B be square matrices, and B invertible, and
$A=p(B)q^{-1}(B)$. Then for all eigenvalues $\lambda_{B}$ of B,
$\lambda_{A}=p(\lambda_{B})q^{-1}(\lambda_{B})$ is an eigenvalue of A, and all
eigenvectors $x$ of B are eigenvectors of A.

###### Proof.

We start the proof with mathematical induction. Let $\lambda_{B}$ be an
eigenvalue of $B$ and $x$ be its corresponding eigenvector. Then our base case
is

$Bx=\lambda_{B}x$ (2)

Let us assume the following

$B^{k}x=\lambda_{B}^{k}x$ (3)

Then

$B^{k+1}x=BB^{k}x=B\lambda_{B}^{k}x=\lambda_{B}^{k}Bx=\lambda_{B}^{k+1}x$ (4)

So $B^{n}x=\lambda_{B}^{n}x$ for $n=1,2,3,...$ by mathematical induction.
Let $p(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$ and
$q(x)=\sum_{n=0}^{\infty}b_{n}x^{n}$ be polynomial functions, and let
$A=p(B)q^{-1}(B)$

$Aq(B)=p(B)$ (5) $Aq(B)x=p(B)x$ (6)
$A\sum_{n=0}^{\infty}b_{n}B^{n}x=\sum_{n=0}^{\infty}a_{n}B^{n}x$ (7)
$A\sum_{n=0}^{\infty}b_{n}\lambda_{B}^{n}x=\sum_{n=0}^{\infty}a_{n}\lambda_{B}^{n}x$
(8) $Aq(\lambda_{B})x=p(\lambda_{B})x$ (9)

Multiplication is associative with constants.

$Ax=p(\lambda_{B})q^{-1}(\lambda_{B})x$ (10)

Thus, x is also an eigenvector of A, and its eigenvalue is
$p(\lambda_{B})q^{-1}(\lambda_{B})$. ∎

######  Lemma 5.

Let $A$ be positive definite. If $B-A$ is a positive definite, then $B$ is
positive definite.

###### Proof.

Let $A$ and $B-A$ be positive definite.

$x^{T}Ax\geq 0\ \forall x$ $x^{T}(B-A)x\geq 0\ \forall x$ $x^{T}Bx-x^{T}Ax\geq
0\ \forall x$ $\therefore x^{T}Bx\geq 0\ \forall x$

So B is positive definite. ∎

######  Theorem 6.

Let $M-N(\vec{u}_{n})$ be the time-step matrix of a nonlinear diffusion PDE
where M is the time-step matrix for the diffusion part, and N is a nonlinear
vector function. If $N(\hat{u})-N(\vec{u}_{n})$ is positive definite for all n
for some constant $\hat{u}$, and $M-N(\hat{u})$ is positive definite, then
$M-N(\vec{u}_{n})$ is positive definite for all n.

###### Proof.

$[M-N(\vec{u}_{n})]-[M-N(\hat{u})]=N(\hat{u})-N(\vec{u}_{n})$

$M-N(\hat{u})$ and $N(\hat{u})-N(\vec{u}_{n})$ are both positive definite for
all n.
$\therefore M-N(\vec{u}_{n})$ is also positive definite for all n by lemma 5 ∎

######  Corollary 6.1.

Nonnegative eigenvalues for numerical methods of the equations
$u_{t}=u_{xx}-\rho u^{2}$, $u_{t}=u_{xx}-\rho u(1-u)$, $u_{t}=u_{xx}-\rho
u(1-u)(a-u)$ is guaranteed by the nonnegative eigenvalue condition about the
linearizations of those schemes about their respective stable equilibria.

###### Proof.

(1) $u_{t}=u_{xx}-\rho u^{2}$
Discretization: $\vec{u}_{n+1}=(M-\rho\cdot diag(\vec{u}_{n}))\vec{u}_{n}$
Discretization of the linearization: $\vec{u}_{n+1}=M\vec{u}_{n}$

$M-(M-\rho\cdot diag(\vec{u}_{n}))=\rho\cdot diag(\vec{u}_{n})$

Thus, if the time-step matrix M of the linearization is positive definite,
then the time-step matrix $M-diag(\vec{u}_{n})$ is positive definite for
$u(n,i)\geq 0$ by theorem 6.

(2) $u_{t}=u_{xx}-\rho u(1-u)$
Discretization: $\vec{u}_{n+1}=(M-\rho(I-diag(\vec{u}_{n})))\vec{u}_{n}$
Discretization of the linearization: $\vec{u}_{n+1}=(M-\rho I)\vec{u}_{n}$

$(M-\rho I)-(M-\rho(I-diag(\vec{u}_{n})))=diag(\vec{u}_{n})$

Thus, if the time-step matrix $M-\rho I$ of the linearization is positive
definite, then the time-step matrix $M-\rho(I-diag(\vec{u}_{n}))$ is positive
definite for $u(n,i)\geq 0$ by theorem 6.

(3) $u_{t}=u_{xx}-\rho u(1-u)(a-u)$
Discretization: $\vec{u}_{n+1}=(M-\rho(I-diag(\vec{u}_{n})(aI-
diag(\vec{u}_{n}))))\vec{u}_{n}$
Discretization of the linearization (about $u_{0}=0$): $\vec{u}_{n+1}=(M+\rho
aI)\vec{u}_{n}$
Discretization of the linearization (about $u_{0}=1$):
$\vec{u}_{n+1}=(M+\rho(1-a)I)\vec{u}_{n}$

$(M+\rho aI)-(M-\rho(I-diag(\vec{u}_{n})(aI-
diag(\vec{u}_{n}))))=\rho(2aI-(1+a)diag(\vec{u}_{n})+diag(\vec{u}_{n})^{2})$

Since $\rho(2a-(1+a)x+x^{2})\geq 0$ for $0\leq a\leq 1,\ 0<x<1$,
$\rho(2aI-(1+a)diag(\vec{u}_{n})+diag(\vec{u}_{n})^{2})$ is positive definite
by theorem 6.

$(M+\rho(1-a)I)-(M-\rho(I-diag(\vec{u}_{n})(aI-
diag(\vec{u}_{n}))))=\rho(I-(1+a)diag(\vec{u}_{n})+diag(\vec{u}_{n})^{2})$

Since $\rho(1-(1+a)x+x^{2})\geq 0$ for $0.1\leq a\leq 1,\ 0<x<1$,
$\rho(I-(1+a)diag(\vec{u}_{n})+diag(\vec{u}_{n})^{2})$ is positive definite by
theorem 6. ∎

##  7 Tables

Heat equation $u_{t}=\delta u_{xx}$
---
Numerical Scheme | N.N eig. cond. | Bal. eig. cond.
Forward Euler | $r\leq 1/4$ | $r\leq 1/2$
Runge-Kutta 3 | $r\leq 0.39902$ | $r\leq 0.62819$
Runge-Kutta 5 | $r\leq 0.54515$ | $r\leq 0.80426$
Crank Nicolson | $r\leq 1/2$ | $r\leq 1$
Linear Reaction-Diffusion $u_{t}=\delta u_{xx}-\rho u$
Numerical Scheme | N.N eig. cond. | Bal. eig. cond.
Forward Euler | $r\leq 1/4-1/4\rho\Delta t$ | $r\leq 1/2-1/2\rho\Delta t$
Crank Nicolson | $r\leq 1/2-1/4\rho\Delta t$ | $r\leq 1-1/2\rho\Delta t$
Table 1: Non-oscillatiory conditions Nonlinear Equation | Steady State | Linearization
---|---|---
$u_{t}=\delta u_{xx}-\rho u^{2}$ | $u_{0}=0$ | $u_{t}=\delta u_{xx}$
$u_{t}=\delta u_{xx}-\rho u(1-u)$ | $u_{0}=1$ | $u_{t}=\delta u_{xx}-\rho u$
$u_{t}=\delta u_{xx}-\rho u(1-u)(a-u)$ | $u_{0}=0$ | $u_{t}=\delta u{xx}+\rho au$
$u_{t}=\delta u_{xx}-\rho u(1-u)(a-u)$ | $u_{0}=1$ | $u_{t}=\delta u{xx}+\rho(1-a)u$
Table 2: Linearizations of Nonlinear Reaction-diffusion Equations


#  EVCap: Retrieval-Augmented Image Captioning
with External Visual–Name Memory for Open-World Comprehension

Jiaxuan Li1, Duc Minh Vo1, Akihiro Sugimoto2, Hideki Nakayama1
1The University of Tokyo, Japan 2National Institute of Informatics, Japan
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Large language models (LLMs)-based image captioning has the capability of
describing objects not explicitly observed in training data; yet novel objects
occur frequently, necessitating the requirement of sustaining up-to-date
object knowledge for open-world comprehension. Instead of relying on large
amounts of data and scaling up network parameters, we introduce a highly
effective retrieval-augmented image captioning method that prompts LLMs with
object names retrieved from External Visual–name memory (EVCap). We build
ever-changing object knowledge memory using objects’ visuals and names,
enabling us to (i) update the memory at a minimal cost and (ii) effortlessly
augment LLMs with retrieved object names utilizing a lightweight and fast-to-
train model. Our model, which was trained only on the COCO dataset, can be
adapted to out-domain data without additional fine-tuning or retraining. Our
comprehensive experiments conducted on various benchmarks and synthetic
commonsense-violating data demonstrate that EVCap, comprising solely 3.97M
trainable parameters, exhibits superior performance compared to other methods
of equivalent model size scale. Notably, it achieves competitive performance
against specialist SOTAs with an enormous number of parameters. Our code is
available at https://jiaxuan-li.github.io/EVCap.

##  1 Introduction

Advanced image captioning based on large language models (LLMs) [3, 9, 25, 8]
has focused on the approach using big-scale models trained on ever-
increasingly large-scale datasets, which is no longer viable. This is because
the computational cost to train the models increases exponentially and, more
importantly, updating training data is almost impossible that keep pace with
the growth of novel objects in our daily lives. Sustaining ever-changing
object knowledge with a reasonable cost is a pressing concern in LLMs-based
models to truly unlock open-world comprehension.

Figure 1: Overall comparison of our EVCap and SOTAs. (Upper) Comparison of the
number of trainable parameters, CIDEr score on COCO and NoCaps datasets. The
size of each circle reflects the log number of trainable parameters. EVCap
(3.97M) has less trainable parameters than others while achieving comparable
results with SOTAs at scale. (Lower) Generated captions by SmallCap, BLIP-2,
and our EVCap for a commonsense-violating image from the WHOOPS dataset.
$\times$ and $\checkmark$ indicate incorrect and correct predictions,
respectively. Incorrect objects in captions are highlighted in red, while
correct ones are in blue. SmallCap and BLIP-2 give incorrect predictions for
“ice skates” and “wood floor”, respectively, while our EVCap utilizes an
external visual–name memory to enhance attention to objects within the image,
leading to superior performance for image captioning.

Retrieval-augmented image captioning [35, 20] is emerging as an alternative
since it considerably reduces training costs in both time and data while
producing encouraging results. Nonetheless, with their huge datastore, it is
obvious that LLMs would imitate the given texts, limiting their ability to
describe open-world objects properly. For instance, SmallCap [35] considers
the words “skateboard” and “wooden floor” to be a pair regardless of visual
appearances containing a commonsense-violating pair of “ice skates” and “wood
floor” (Fig. 1, lower). Additionally, prompting the LLMs given a lot of
retrieved texts becomes cumbersome, requiring more trainable parameters. Fig.
1 (upper) shows that the CIDEr scores obtained by a lightweight SmallCap [35]
with 43M trainable parameters are far away from those obtained by a heavy
REVEAL [20] with 2.1B trainable parameters. Beyond that, due to the frequent
occurrence of new objects, access to their sample texts is not always
feasible, making the memory utilized in [35, 20] difficult to grow. We thus
aim to streamline the external memory used in previous work [35, 20] by
storing a sufficiently small amount of object information. And, of course, not
only does the model not stereotype the example sentences, but the number of
trainable parameters would be reduced drastically as a result of the causation
(Fig. 1).

We follow [40, 13] to construct a key-value memory where the key is
represented by object’s features, and the value corresponds to object’s name.
Unlike [40, 13], which rely on object definition as the key, our method
leverages the visual appearance of the object as the key because of the
abundance of object images readily available on the internet. We propose an
external visual–name memory tailored for ease of expansion and cost-
effectiveness in upholding up-to-date object information. We present a highly
effective retrieval-augmented LLMs-based image captioning method, called
EVCap, that prompts frozen LLMs with object names retrieved from our proposed
memory for open-world comprehension. EVCap contains a frozen image encoder ViT
[14] and Q-Former [25] with trainable image query tokens for object retrieval,
an attentive fusion module, a trainable linear layer for mapping between
vision and language latent spaces, and a frozen LLM decoder [10] for
generating captions. Specifically, the attentive fusion module feeds retrieved
object names and visual features into a customized frozen Q-Former using
trainable object name query tokens to implicitly reduce the presence of
superfluous object names. As a result, EVCap amounts to only 3.97M trainable
parameters. Once trained, the model can be adapted to new domains and large-
scale data without further fine-tuning or retraining. Our contributions are as
follows:

  * •

We provide an extensible external visual–name memory with minimal but useful
object information, which enables LLMs-based models to comprehend the open
world.

  * •

We present a remarkably lightweight and highly efficacious retrieval-augmented
image captioning EVCap with 3.97M trainable parameters.

On in-/out-domain benchmarks and synthetic commonsense-violating dataset,
EVCap trained solely on COCO dataset competes with other lightweight methods
by a margin while being on par with other specialist SOTAs.

##  2 Related Work

Image captioning aims to describe the contents of a given image. It can be
roughly divided into two approaches: non-LLMs-based methods and LLMs-based
ones. The former approaches [22, 42, 4] typically employ a visual encoder and
a language decoder in an end-to-end fashion to generate captions. However,
they are incapable of describing open-world objects. The latter one leverages
pre-trained large-scale vision models (CLIP [32], ViT [12]) and LLMs (GPTs
[31, 7], T5 [33], LLaMA [37]) by bridging the gap between two modalities using
either pre-training with large-scale data or the learned mapper or prompt
techniques. LLMs-based models [29, 25, 9, 8] demonstrate advancements in image
captioning challenges, allowing the capacity to describe anything as long as
pre-trained vision models can recognize it. Our method belongs to the LLMs-
based approaches, but instead of relying fully on the pre-trained vision
model, we use object names retrieved from the external memory to augment LLMs-
based image captioning.

Novel object captioning is a branch of image captioning that describes images
containing objects that were not seen during training. Non-LLMs-based methods
explore more objects by learning from unpaired image-sentence sources (DCC
[19], NOC [39]) or relied on novel object detectors to recognize novel
concepts (NBT [28], OSCAR [26] and VinVL [45]). LLMs-based methods such as
ViECap [15] leverage the pre-trained CLIP [32] to obtain object entities.
Nevertheless, the cut-off in training time of the pre-trained object detector
or CLIP prevents it from detecting novel objects that arise quickly in
reality. Unlike earlier work, we can readily update our recognition of novel
concepts by adding them to external memory, ensuring that we keep any new
objects from the past and even the future.

Retrieval-augmented image captioning is a recently popular approach that
augments the captioning model with retrieved information for better open-world
understanding. AoANet [16] uses a memory bank of image-sentence pairs and
target words. SmallCap [35] employs image-to-text retrieval to obtain sampled
captions from a captions datastore. RA-CM3 [44] retrieves documents from an
external memory of a mixture of text and image via a dense multimodal
retriever. EXTRA [34] and Re-ViLM [43] exploit the similarity of the input
image and vision candidates to retrieve captions. Unlike previous methods, our
external memory contains visual–name pairs to avoid redundant information in
the external captions/documents. In addition, we use an attentive fusion
module to mitigate the effects of irrelevant retrieved object names on caption
generation.

Figure 2: Schematic of our proposed EVCap. It consists of an external
visual–name memory with image embeddings and object names (upper), a frozen
ViT and Q-Former equipped with trainable image query tokens, an attentive
fusion module developed by a customized frozen Q-Former and trainable object
name query tokens, and a frozen LLM with a trainable linear layer (lower). The
ViT and Q-Former extract learned visual features from the input image, which
are then used to retrieve object names from the external memory. These
retrieved object names and learned visual features undergo cross-attention in
the customized Q-Former, creating refined object name features. Finally, the
object name features combined with visual features are fed into the LLM post a
linear layer for generating captions.

##  3 Proposed EVCap

###  3.1 Idea of EVCap

We aim to build a retrieval-augmented LLMs-based image captioning model with a
sufficiently small yet informative external memory. It involves two
challenges: (1) constructing an expandable external memory, and (2) building
an effective LLMs-based model using retrieved object names.

As discussed above, challenge (1) can be resolved by utilizing the visual
appearance of objects. However, if we restrict our memory to only a
visual–name pair for each object, our memory will be lacking in diversity.
Therefore, we gather several images for each target object. Additionally, we
keep the synthetic images in our memory to avoid the harm that synthetic
images might cause to our method, as pointed out in [18]. With the capability
to collect images from the internet, EVCap can be easily expanded to include
novel objects from the real world effortlessly.

We base our method on a frozen pre-trained vision model and LLM with several
trainable layers (Fig. 2), giving in a model that is cheap to train. To guide
the LLM, we adopt a recently popular approach called prompting as in [29, 25,
11, 35, 46]. We begin by matching the learned visual features from the input
image with image embeddings stored in memory, retrieving object names. We also
introduce an attentive fusion module designed to implicitly remove irrelevant
retrieved names. Finally, following the attentive fusion, we combine the
learned visual features and object name features to form a prompt for the LLM
to generate a caption, thus addressing challenge (2).

###  3.2 External visual–name memory

To build the external visual–name memory, we first collect image–name pairs
from the external data source. After that, we encode these images into image
embeddings, which serve as keys in memory, and use their names as values.

External data source. We utilize object images from LVIS dataset [17] to
construct our external visual–name memory $\mathcal{M}$. Specifically, we use
1203 objects in LVIS, where we randomly select from one to ten images for each
object, amounting to 8581 object images. Furthermore, as mentioned in Sec.
3.1, we also incorporate synthetic images in our memory construction. Using
stable diffusion [36], we generate five additional images for each object,
with a prompt of “a photo of {object name}”, resulting in a total of $M=14596$
$(8581+5\times 1203)$ images. Each object image $X^{i}$ is associated with an
object name $v^{i}$. Note that many object images may share the same object
name. For the sake of simplicity, we may regard each image as corresponding to
a single name. In summary, we have $M$ image–name pairs
$\\{(X^{i},v^{i})\\}^{M}_{i=1}$ for external memory construction.

External memory construction. For each image $X^{i}$, we use a frozen vision
encoder $\mathcal{E}(\cdot)$ (see Sec. 3.3 for detail) to project it into 32
embeddings with the size of $1\times 768$ each:
$\\{\mathbf{k}^{i}_{1},\mathbf{k}^{i}_{2},\cdots,\mathbf{k}^{i}_{32}\\}=\mathcal{E}(X^{i})$.
We then average 32 embeddings to produce a single embedding $\mathbf{k}^{i}$
($1\times 768$) that serves as the key (visual) in $\mathcal{M}$. The paired
object name $v^{i}$ acts as its value (name). Consequently, we have the
visual–name memory $\mathcal{M}=\\{(\mathbf{k}^{i},v^{i})\\}^{M}_{i=1}$ which
is indexed using FAISS [21], facilitating rapid searches based on similarity
measures. Our memory can be expanded effortlessly by gathering additional
visual–name pairs (see Sec. 5.3).

###  3.3 Object names retrieval

Image encoding. We feed a frozen vision encoder $\mathcal{E}$ image $X$ and
image query tokens $\mathbf{T}_{\mathrm{img}}$ to produce visual features
$\mathcal{Q}$. To enable the retrieval process controllable, we make image
query tokens to be trainable. Thus, the image encoding process can be
summarized as $\mathcal{Q}=\mathcal{E}(X,\mathbf{T}_{\mathrm{img}})$. We use
the BLIP-2 pre-trained vision encoder [25], which consists of a pre-trained
vision transformer ViT-g [14] outputting image features ($257\times 1408$),
and a Q-Former receiving image features producing $|\mathcal{Q}|=32$ learned
visual features ($1\times 768$ each). We denote
$\mathcal{Q}=\\{\mathbf{q}_{1},\mathbf{q}_{2},...,\mathbf{q}_{32}\\}$.

Retrieval. Having obtained $\mathcal{Q}$, we calculate the cosine similarity
between the query $\mathbf{q}_{j}\in\mathcal{Q}$ and the key
$\mathbf{k}^{i}\in\mathcal{M}$. The similarity calculation is given by
$\operatorname{SIM}(\mathbf{q}_{j},\mathbf{k}^{i})=\frac{\mathbf{\mathbf{q}_{j}^{\top}}\mathbf{k}^{i}}{\|\mathbf{q}_{j}\|\|\mathbf{k}^{i}\|}$,
where $i\in[1,M]$, $j\in[1,32]$. Given each $\mathbf{q}_{j}$, we select one
key with the highest similarity score, resulting in 32 key–value candidates
$\\{\mathbf{k}_{j}^{\mathrm{best}},v_{j}^{\mathrm{best}}\\}^{32}_{j=1}$.

After that, we filter out candidates with repeated object names (values), and
then select the top-K values. In particular, we determine the index $j$ from
the key that has the highest $\operatorname{SIM}$ score. These selected values
$v_{j}^{\mathrm{best}}$ are redefined as the new notation $v_{l}$ in the
retrieved top-K object names for the input image, which can be summarized as
follows:

$\\{\mathbf{k}_{j}^{\mathrm{best}},v_{j}^{\mathrm{best}}\\}=\arg\max_{\mathbf{k}^{i}}\operatorname{SIM}\left(\mathbf{q}_{j},\mathbf{k}^{i}\right),\\\
\vspace*{-0.75\baselineskip}$

$j=\arg\max_{j}\operatorname{SIM}(\mathbf{q}_{j},\mathbf{k}_{j}^{\mathrm{best}}),v_{l}\leftarrow
v_{j}^{\mathrm{best}},$

where $l\in[1,\mathrm{K}]$. As a result, the retrieved top-K object names are
$\\{v_{l}\\}^{\mathrm{K}}_{l=1}$.

###  3.4 Attentive fusion

Since the object names obtained from the retrieval process may be redundant,
we develop an attentive fusion module to selectively distill object name
features.

The retrieved object names $\\{v_{l}\\}^{\mathrm{K}}_{l=1}$ are concatenated
together into a sequence $\mathcal{S}$, each separated by a delimiter:
$\mathcal{S}=\\{v_{1},\texttt{[SEP]},v_{2},\texttt{[SEP]},\cdots,\texttt{[SEP]},v_{\mathrm{K}}\\}$.
The sequence $\mathcal{S}$ and visual features $\mathcal{Q}$ are fed into a
customized Q-Former $\mathcal{F(\cdot)}$, which is constructed from the frozen
pre-trained Q-Former as we used in vision encoder $\mathcal{E}$. Nonetheless,
in order to enable object names to get attention from visual features, we
switch the image embedding port and the text instruction port (see [25] for
architecture detail). Like in the image encoding process in Sec. 3.3, we make
the object name query tokens $\mathbf{T}_{\mathrm{obj}}$ learnable during
training to assist in learning object name features related to the caption.
The size of $\mathbf{T}_{\mathrm{obj}}$ is $P\times 768$, where $P$ indicates
the number of object name query tokens. We get the object name features
$\mathcal{V}=\mathcal{F}(\mathcal{S},\mathcal{Q},\mathbf{T}_{\mathrm{obj}})$.

###  3.5 Caption generation

Before inputting the visual features $\mathcal{Q}$ and object name features
$\mathcal{V}$ into the LLM decoder, we concatenate ($\oplus$) them and use a
linear layer $\phi(\cdot)$ to project them into the input latent space of the
LLM as $\phi(\mathcal{Q}\oplus\mathcal{V})$. The LLM used for caption
generation in this work is the pre-trained Vicuna-13B [10], an open-source
chatbot constructed from LLaMA [37]. During training and evaluation, we design
a prompt in a conversational format, that is similar to [46]:

###Human: <ProjFeature> Describe this image in detail.
###Assistant:

in which, ProjFeature denotes the projected feature
$\phi(\mathcal{Q}\oplus\mathcal{V})$ after the linear layer. In training
phase, given input caption tokens $\\{c_{i}\\}^{L}_{i=1}$, the LLM decoder
concatenates the embedded prompt $\\{\mathbf{w}_{i}\\}^{N}_{i=1}$ and the
embedded caption tokens $\\{\mathbf{c}_{i}\\}^{L}_{i=1}$ as input, and
predicts the caption tokens in an autoregressive fashion, while in the
evaluation phase, we only need to input the embedded prompt. We train EVCap by
minimizing the cross-entropy loss in an end-to-end way:
$\mathcal{L}_{\theta}=-\sum_{i=1}^{L}\log
p_{\theta}\left(c_{i}\mid\mathbf{w}_{1},...\mathbf{w}_{N},\mathbf{c}_{1},...,\mathbf{c}_{i-1}\right)$,
in which $\theta$ indicates the trainable parameters.

##  4 Experimental Settings

###  4.1 Training setup

Implementation. EVCap uses the same image encoder as in BLIP-2 [25],
consisting of a ViT-g [14] and their pre-trained Q-Former. Since we intend to
obtain object name features through cross-attention between retrieved object
names and visual features, we develop a customized Q-Former, which consists of
BERT [23] with cross-attention layers inserted at every other transformer
block. We use a frozen Vicuna-13B [10] as the caption generator.

Training dataset. For all experiments, we exclusively train EVCap using the
training set of COCO dataset [27], consisting of 82k images and 5 captions per
images. The entire training process takes about 3 hours on 4 A6000 GPUs, using
mixed precisions (more details in the supplementary).

Table 1: Quantitative comparison against SOTA methods on three common image
captioning benchmarks. * denotes using a memory bank. We report the size of
training data and parameters; BLEU@4 (B@4), METEOR (M), CIDEr (C), and SPICE
(S) scores on COCO test set; C and S scores on in-domain, near-domain, out-
domain and overall data of NoCaps validation set; C and S scores on Flickr30k
test set. Higher score is better. Bold indicates the best results among
compared methods, normal indicates the second best results.

Method | Training | COCO | NoCaps val | Flickr30k
---|---|---|---|---
Data | Para. | Test | In-domain | Near-domain | Out-domain | Overall | Test
|  | B@4 | M | C | S | C | S | C | S | C | S | C | S | C | S
Heavyweight-training models
VinVL [45] | 8.9M | 110M | 38.2 | 30.3 | 129.3 | 23.6 | 96.8 | 13.5 | 90.7 | 13.1 | 87.4 | 11.6 | 90.9 | 12.8 | – | –
AoANet+MA* [16] | COCO | – | 38.0 | 28.7 | 121.0 | 21.8 | – | – | – | – | – | – | – | – | – | –
NOC-REK* [40] | COCO | 110M | – | – | – | – | 104.7 | 14.8 | 100.2 | 14.1 | 100.7 | 13.0 | 100.9 | 14.0 | – | –
RCA-NOC* [13] | COCO | 110M | 37.4 | 29.6 | 128.4 | 23.1 | 92.2 | 12.9 | 87.8 | 12.6 | 87.5 | 11.5 | 88.3 | 12.4 | – | –
ViECap ${}_{\text{GPT2}}$ [15] | COCO | 124M | 27.2 | 24.8 | 92.9 | 18.2 | 61.1 | 10.4 | 64.3 | 9.9 | 65.0 | 8.6 | 66.2 | 9.5 | 47.9 | 13.6
InstructBLIP ${}_{\text{Vicuna-13B}}$ [11] | 129M | 188M | – | – | – | – | – | – | – | – | – | – | 121.9 | – | 82.8 | –
OSCAR [26] | 4.1M | 338M | 37.4 | 30.7 | 127.8 | 23.5 | 83.4 | 12.0 | 81.6 | 12.0 | 77.6 | 10.6 | 81.1 | 11.7 | – | –
BLIP [24] | 129M | 446M | 40.4 | – | 136.7 | – | 114.9 | 15.2 | 112.1 | 14.9 | 115.3 | 14.4 | 113.2 | 14.8 | – | –
BLIP-2 ${}_{\text{FlanT5-XL}}$ [25] | 129M | 1.2B | 42.4 | – | 144.5 | – | 123.7 | 16.3 | 120.2 | 15.9 | 124.8 | 15.1 | 121.6 | 15.8 | – | –
REVEAL* ${}_{\text{T5}}$ [20] | 1.3B | 2.1B | – | – | 145.4 | – | – | – | – | – | – | – | 123.0 | – | – | –
Lightweight-training models
MiniGPT4 ${}_{\text{Vicuna-13B}}$ [46] | 5M | 3.94M | 38.0 | 29.6 | 129.6 | 23.4 | 99.0 | 14.8 | 106.9 | 15.3 | 110.8 | 14.9 | 108.8 | 15.1 | 78.4 | 16.9
SmallCap* ${}_{\text{GPT2}}$ [35] | COCO | 7M | 37.0 | 27.9 | 119.7 | 21.3 | – | – | – | – | – | – | – | – | 60.6 | –
ClipCap ${}_{\text{GPT2}}$ [29] | COCO | 43M | 33.5 | 27.5 | 113.1 | 21.1 | 84.9 | 12.1 | 66.8 | 10.9 | 49.1 | 9.6 | 65.8 | 10.9 | – | –
EVCap* ${}_{\text{Vicuna-13B}}$ | COCO | 3.97M | 41.5 | 31.2 | 140.1 | 24.7 | 111.7 | 15.3 | 119.5 | 15.6 | 116.5 | 14.7 | 119.3 | 15.3 | 84.4 | 18.0
Specialist SOTAs
Qwen-VL ${}_{\text{Qwen-7B}}$ [5] | 1.4B | 9.6B | – | – | – | – | – | – | – | – | – | – | 121.4 | – | 85.8 | –
CogVLM ${}_{\text{Vicuna-7B}}$ [41] | 1.5B | 6.5B | – | – | 148.7 | – | – | – | – | – | 132.6 | – | 128.3 | – | 94.9 | –
PaLI ${}_{\text{mT5-XXL}}$ [9] | 1.6B | 17B | – | – | 149.1 | – | – | – | – | – | – | – | 127.0 | – | – | –
PaLI-X ${}_{\text{UL2-32B}}$ [8] | 2.2B | 55B | – | – | 149.2 | – | – | – | – | – | – | – | 126.3 | – | – | –

###  4.2 Evaluation setup

Evaluation dataset. We evaluate EVCap, trained using the COCO training set,
across four datasets: its test set, two challenging benchmarks – NoCaps
validation set and Flickr30k test set, and a synthetic commonsense-violating
dataset – WHOOPS. We adhere follow prior work [15, 41] to use the same images
of Karpathy split [22] on COCO test set, NoCaps [2] validation set, and
Karpathy split on Flickr30k [30] test set. In addition, WHOOPS [6] is a
synthetic image captioning dataset comprising 500 synthetic commonsense-
violating images and 2500 paired captions.

Compared methods. We compare EVCap with several SOTAs. According to the
trainable parameters size, they can be divided into 1) Heavyweight-training
(between 100M to 5B): VinVL [45], AoANet [16], NOC-REK [40], RCA-NOC [13],
ViECap [15], InstructBLIP [11], OSCAR [26], BLIP [24], BLIP-2 [25], REVEAL
[20]; 2) Lightweight-training (less than 100M): MiniGPT4 [46], SmallCap [35],
ClipCap [29]; and also 3) Specialist SOTAs with huge trainable parameters
(larger than 5B): Qwen-VL [5], CogVLM [41], PaLI [9], PaLI-X [8]. Among these
methods, AoANet, NOC-REK, RCA-NOC, REVEAL, and SmallCap are retrieval-
augmented captioning methods.

##  5 Experimental Results

###  5.1 Results on in-/out-domain benchmarks

Figure 3: Examples of captions generated by our EVCap and three SOTA methods
on COCO test set, NoCaps validation set, and Flickr30k test set. GT refers to
the Ground Truth captions. Incorrect objects in captions are highlighted in
red, while correct ones are in blue. Our EVCap correctly generates captions
across different datasets, showing performance comparable to BLIP-2. In
contrast, SmallCap and MiniGPT4 sometimes either miss objects or include
incorrect ones in their generated captions.

We assess EVCap against SOTAs on both in-domain and out-domain benchmarks. The
COCO test set can be considered as in-domain data as we only train our model
on the COCO training set. Out-domain benchmarks are the NoCaps validation set
and the Flickr30k test set.

Quantitative results. Tab. 1 details our EVCap’s performance in comparison
with SOTA methods. We first evaluate training costs in terms of training data
sizes and parameters. Similar to various heavyweight-training models that
exclude LLMs and the majority of lightweight-training models, EVCap is trained
solely on the COCO training set. It utilizes only 3.97M trainable parameters,
positioning it as the second smallest, slightly larger than MiniGPT4 with
3.94M. Among lightweight-training models, our approach outperforms others,
achieving the highest scores on all benchmarks. Despite using less training
data and nearly identical trainable parameters as MiniGPT4, EVCap
significantly surpasses it, with a marked improvement of 10.5, 10.5, and 6.0
in CIDEr scores for each benchmark. When further compared with heavyweight-
training models, the performance of EVCap stands out among million-level
models, nearly matching InstructBLIP, except in NoCaps. Note that since BLIP-2
does not include Vicuna checkpoints, InstructBLIP performs pre-training with
Vicuna using the same procedure as BLIP-2, whereas EVCap does not involve pre-
training. Against REVEAL, which also uses external memory, our EVCap utilizes
about 1/3000 training data and 1/500 training parameters yet yields comparable
results. Moreover, EVCap’s performance is on par with BLIP-2, the top-
performing model with 1.2B trainable parameters. This highlights EVCap’s
efficiency and effectiveness despite its significantly smaller training cost,
thanks to our external visual–name memory. Regarding specialist SOTAs, they
use billion-level training data and over 5B trainable parameters, so it is
acceptable that they can achieve exceptionally strong performance, surpassing
EVCap by nearly 10 on all benchmarks in CIDEr scores.

Qualitative results. Fig. 3 presents a comparison of captions generated by our
EVCap and three SOTA models across three benchmarks. The captions of SmallCap
are generated by its publicly accessible demo [1]. We generate captions of
MiniGPT4 and BLIP-2 using their respective pre-trained models. As a
lightweight and retrieval-augmented captioning method, SmallCap struggles to
produce accurate captions for given images, primarily because it relies on
retrieved captions laden with extraneous information. MiniGPT4, though aligned
with the primary content of images, sometimes misses certain objects like
“trees” and “headphones”. This oversight stems from its focus on the main
objects in images, without integrating additional cues for other objects
provided by the retrieved object names. In contrast, the captions generated by
our EVCap are comparable to those of BLIP-2.

###  5.2 Results on commonsense-violating data

To explore our EVCap’s capability in describing contents in open-word
settings, we further evaluate it on WHOOPS dataset, which contains
commonsense-violating images.

Table 2: Quantitative results on commonsense-violating data – WHOOPS dataset.
EVCap (w/ WHOOPS) denotes EVCap using the memory expanded by WHOOPS objects.
The results reveal the open-world comprehension ability and expandability of
EVCap.

Method | B@4 | M | C | S
---|---|---|---|---
Only pre-trained models
BLIP [24] (from [6]) | 13 | – | 65 | –
BLIP-2 ${}_{\text{FlanT5-XXL}}$ [25] (from [6]) | 31 | – | 120 | –
BLIP-2 ${}_{\text{FlanT5-XXL}}$ [25] (reproduced) | 28 | 26.7 | 93.1 | 17.9
Finetuned models on COCO
MiniGPT4 [46] | 24.2 | 26.7 | 84.8 | 18.2
BLIP [24] | 22.9 | 25.0 | 79.3 | 17.1
BLIP-2 ${}_{\text{FlanT5-XL}}$ [25] | 25.8 | 27.0 | 89.1 | 18.3
End-to-end trained models on COCO
EVCap | 24.1 | 26.1 | 85.3 | 17.7
EVCap (w/ WHOOPS) | 24.4 | 26.1 | 86.3 | 17.8

Quantitative results. In Tab. 2, we compare the performance of EVCap,
MiniGPT4, BLIP, and BLIP-2 on WHOOPS dataset. This dataset is particularly
challenging due to its inclusion of unusual objects [6]. Initially, as an end-
to-end trained model, our EVCap exhibits performance similar to MiniGPT4.
However, there is a noticeable improvement in the CIDEr score, after the
external memory is enriched with 2396 new objects from the WHOOPS dataset,
each represented by 5 synthesized images generated using stable diffusion
[36]. It highlights the effectiveness of our idea of incorporating an
expandable external memory into the captioning model for open-world
comprehension.

Qualitative results. Fig. 4 illustrates the captions generated by EVCap, EVCap
(w/WHOOPS), and three SOTAs for two images from the WHOOPS dataset. The first
image challenges common sense as it unusually pairs “Einstein” with “racing
car”. While all SOTAs simply refer to “Einstein” as “a man”, our EVCap and
EVCap (w/WHOOPS) correctly identify him. The second image shows another
unusual example. Similar to other methods except for BLIP-2, EVCap can not
recognize “blue cartoon character” as “Pikachu”, while EVCap (w/WHOOPS)
successfully predicts it because of the updated memory. In these two images,
SmallCap and MiniGPT4 tend to generate captions with hallucinatory objects, a
result of commonsense-violating contents present in the images.

Figure 4: Examples of captions generated by our EVCap, EVCap (w/ WHOOPS), and
three SOTAs on WHOOPS dataset. Incorrect objects are highlighted in red, while
correct ones are in blue.

###  5.3 Detailed analysis

Table 3: Ablation study on components prior to the LLM decoder in EVCap. The
result of “+ Attentive fusion” demonstrates the substantial impact of the
external visual–name memory.

Method | COCO test | NoCaps val | Flickr30k test
---|---|---|---
C | S | C | S | C | S
ViT + Q-Former (Baseline) | 134.4 | 23.9 | 108.8 | 14.2 | 76.8 | 17.3
\+ Image query tokens (Baseline+) | 134.1 | 23.8 | 109.0 | 14.3 | 77.3 | 17.2
\+ Attentive fusion (EVCap) | 140.1 | 24.7 | 119.3 | 15.3 | 84.4 | 18.0

Figure 5: Visualization of the captions generated from ablation study on the
NoCaps validation set. We also show the retrieved object names by EVCap,
presented in gray. Incorrect objects in captions are highlighted in red, while
correct ones are in blue.

Ablation study. We assess the contribution of each component prior to the LLM
decoder in EVCap by incrementally integrating the image query tokens and the
attentive fusion module into our baseline model. The baseline model comprises
a ViT+Q-Former, a linear layer, and a LLM decoder. The quantitative results
are shown in Tab. 3. When employing only the baseline model (Baseline), CIDEr
scores drop notably by 5.7, 10.5, and 7.6 on COCO, NoCaps, and Flickr30k,
respectively. The inclusion of trainable image query tokens (Baseline+) brings
a marginal improvement on NoCaps and Flickr30k. However, the performance is
significantly enhanced with the addition of attentive fusion (along with the
introduction of external memory), indicating the pivotal role of the external
visual–name memory in the overall effectiveness of EVCap. This is further
corroborated by the qualitative results in Fig. 5, where captions from
Baseline and Baseline+ inaccurately include objects like “couch” and “bed”,
and Baseline+ overlooks “hand”.

Figure 6: Visualization of the visual features in external memory using t-SNE.
For visual features in LVIS dataset’s objects (blue), the related objects fall
in the same cluster. After adding more visual features of synthesized images
from WHOOPS’ objects, new objects (red) are located at appropriate clusters
(zoom-in view).

Exploration for external memory expandability. To demonstrate the scalability
of the external memory in EVCap, we visualize the visual features stored in
LVIS external memory, and newly synthesized data from objects appearing in the
WHOOPS dataset. We employ t-SNE [38] to plot visual features after reducing
their dimensions to 2-D (Fig. 6). For clear visualization, we only randomly
display 3649 visual features in LVIS memory, and add 479 visual features from
WHOOPS objects. Among them, 35 samples are randomly labeled. The result shows
a clear clustering of LVIS objects (blue) in the external memory, as well as
the successful integration and appropriate localization of new objects from
WHOOPS (red) into these clusters. This pattern not only confirms the
distinctiveness of visual features already present in the memory but also
demonstrates the potential to accurately incorporate and differentiate new
objects introduced from updated data. These findings highlight our external
memory’s ability to expand and maintain its effectiveness even as new data is
incorporated.

Impact of external memory size. We examine the impact of external memory size
in Tab. 4. On the one hand, we randomly remove 30%, 60%, and 90% data in the
external memory constructed from LVIS objects. The results show the
performance gradually degrades on NoCaps as reducing 30% and 90% LVIS. Despite
some unexpected increases in certain results on NoCaps (5th row) and Flickr30k
(4th - 5th rows), they do not alter the overall downward trend. Similar
phenomena are also noted in SmallCap [35], we speculate it is due to data
distribution. On the other hand, as we infuse WHOOPS knowledge into LVIS
memory, there is a slight improvement on NoCaps (out) and Flickr30k. These
observations validate the model’s capability to effectively retrieve object
names from an updated memory, enhancing its performance in generating
captions.

Table 4: Impact of the external memory size on the performance of EVCap by
evaluation under CIDEr scores. Changes in the size of external memory result
in changes in performance.

Method | NoCaps val | Flickr30k
---|---|---
In | Near | Out | Overall | Test
LVIS objects (EVCap) | 111.7 | 119.5 | 116.5 | 119.3 | 84.4
– 30% LVIS | 112.0 | 119.2 | 115.3 | 118.8 | 85.0
– 60% LVIS | 111.4 | 119.1 | 116.2 | 119.0 | 85.1
– 90% LVIS | 110.6 | 118.2 | 115.8 | 118.3 | 83.6
\+ WHOOPS | 110.7 | 118.9 | 116.7 | 119.0 | 84.9

Figure 7: CIDEr scores after training EVCap with the number of retrieved
object names $\mathrm{K}$ from 1 to 20. The results indicate that the
performance is relatively optimal when $\mathrm{K}$ is set to be 10.

Impact of the number of retrieved object names. We investigate how the number
of retrieved object names $\mathrm{K}$ (Sec. 3.3) affect EVCap in Fig. 7. We
train the model with $\mathrm{K}$ from 1 to 20 and evaluate the performance
under CIDEr on all three benchmarks. From the results, we can find that the
model works worst on the out-domain dataset (NoCaps) when only one retrieved
object name is used. As we gradually add more object names, performance
fluctuates but improves. This pattern aligns with our intuition that when
using one object name, the model will make errors or miss some objects in
generated captions due to the incorrect object name. When we add more object
names, we increase the error tolerance, and the attentive module in EVCap
automatically pays more attention to image-related object names, thus
improving results. Furthermore, we observe that setting $\mathrm{K}$ to 10
yields relatively optimal overall performance, validating the choice of
$\mathrm{K}=10$ in EVCap.

Analysis with different decoders. To explore the influence of different LLMs
decoders on our EVCap, we experiment by substituting Vicuna-13B with GPT2 and
Vicuna-7B, as detailed in Tab. 5. With GPT2 as the decoder, EVCap still
markedly surpasses other GPT2-based models, achieving impressive gains of 11.3
and 10.0 under CIDEr on COCO and Flickr30k, compared to SmallCap. When
employing Vicuna-7B, the comparison of performance trends mirrors those
observed with Vicuna-13B, further attesting to the robustness and adaptability
of EVCap across different LLM decoders. Notably, both SmallCap, which
retrieves captions, and our GPT2-based EVCap, which retrieves object names,
use the same GPT2 decoder. Therefore, their comparison also underscores the
effectiveness of our method’s object name retrieval and attentive fusion
strategy.

Table 5: Analysis with different LLM decoders including GPT2, Vicuna-7B, and
Vicuna-13B. The results reveal EVCap is effective when applying it in
different LLM decoders.

Method | LLM | COCO test | NoCaps val | Flickr30k test
---|---|---|---|---
C | S | C | S | C | S
SmallCap [35] | GPT2 | 119.7 | 21.3 | – | – | 60.6 | –
ViECap [15] | GPT2 | 92.9 | 18.2 | 66.2 | 9.5 | 47.9 | 13.6
EVCap | GPT2 | 131.0 | 23.2 | 97.6 | 13.3 | 70.6 | 16.1
MiniGPT4 [46] | Vicuna-7B | 119.4 | 23.5 | 108.7 | 15.7 | 73.9 | 17.2
InstructBLIP [11] | Vicuna-7B | – | – | 123.1 | – | 82.4 | –
EVCap | Vicuna-7B | 139.0 | 24.7 | 116.8 | 15.3 | 82.7 | 18.0
MiniGPT4 [46] | Vicuna-13B | 129.6 | 23.4 | 108.8 | 15.1 | 78.4 | 16.9
InstructBLIP [11] | Vicuna-13B | – | – | 121.9 | – | 82.8 | –
EVCap | Vicuna-13B | 140.1 | 24.7 | 119.3 | 15.3 | 84.4 | 18.0

Limitations. First, EVCap cannot retrieve all objects that appear in the given
image, leading to incomplete image descriptions as the second example in Fig.
4. We will investigate integrating object detection with image captioning to
enhance completeness. Second, our focus on object representation restricts
consideration of other crucial captioning elements, affecting overall
performance. Similar to all models trained on the COCO dataset, our EVCap
inherits its captioning style, which limits its ability to generate varied
styles. This limitation is reflected in our relatively modest performance
improvements in Tab. 2, compared to MiniGPT4. We will overcome this limitation
by exploring methodologies that encourage style diversity in the future.

##  6 Conclusion

We further advance image captioning in real-world scenarios by introducing
EVCap, a novel image captioning model with object names retrieved from an
external visual–name memory. The external memory is easily expandable,
allowing for effortless updates with new object visuals and names. EVCap
stands out for its efficiency, comprising merely 3.97M trainable parameters,
yet delivering robust performance. We extensively compare EVCap with SOTAs on
various benchmarks and commonsense-violating data, demonstrating its
significant superiority in performance.

## References

  * [1] https://huggingface.co/spaces/RitaParadaRamos/SmallCapDemo.
  * Agrawal et al. [2019] Harsh Agrawal, Karan Desai, Yufei Wang, Xinlei Chen, Rishabh Jain, Mark Johnson, Dhruv Batra, Devi Parikh, Stefan Lee, and Peter Anderson.  Nocaps: Novel object captioning at scale.  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * Alayrac et al. [2022] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al.  Flamingo: A visual language model for few-shot learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Anderson et al. [2018] Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang.  Bottom-up and top-down attention for image captioning and visual question answering.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Bai et al. [2023] Jinze Bai, Shuai Bai, Shusheng Yang, Shijie Wang, Sinan Tan, Peng Wang, Junyang Lin, Chang Zhou, and Jingren Zhou.  Qwen-vl: A frontier large vision-language model with versatile abilities.  _arXiv preprint arXiv:2308.12966_ , 2023.
  * Bitton-Guetta et al. [2023] Nitzan Bitton-Guetta, Yonatan Bitton, Jack Hessel, Ludwig Schmidt, Yuval Elovici, Gabriel Stanovsky, and Roy Schwartz.  Breaking common sense: Whoops! a vision-and-language benchmark of synthetic and compositional images.  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2023.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Chen et al. [2023a] Xi Chen, Josip Djolonga, Piotr Padlewski, Basil Mustafa, Soravit Changpinyo, Jialin Wu, Carlos Riquelme Ruiz, Sebastian Goodman, Xiao Wang, Yi Tay, et al.  PaLI-X: On scaling up a multilingual vision and language model.  _arXiv preprint arXiv:2305.18565_ , 2023a.
  * Chen et al. [2023b] Xi Chen, Xiao Wang, Soravit Changpinyo, AJ Piergiovanni, Piotr Padlewski, Daniel Salz, Sebastian Goodman, Adam Grycner, Basil Mustafa, Lucas Beyer, Alexander Kolesnikov, Joan Puigcerver, Nan Ding, Keran Rong, Hassan Akbari, Gaurav Mishra, Linting Xue, Ashish V Thapliyal, James Bradbury, Weicheng Kuo, Mojtaba Seyedhosseini, Chao Jia, Burcu Karagol Ayan, Carlos Riquelme Ruiz, Andreas Peter Steiner, Anelia Angelova, Xiaohua Zhai, Neil Houlsby, and Radu Soricut.  PaLI: A jointly-scaled multilingual language-image model.  In _International Conference on Learning Representations (ICLR)_ , 2023b.
  * Chiang et al. [2023] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.  _See https://vicuna. lmsys. org (accessed 14 April 2023)_ , 2023.
  * Dai et al. [2023] Wenliang Dai, Junnan Li, Dongxu Li, Anthony Meng Huat Tiong, Junqi Zhao, Weisheng Wang, Boyang Li, Pascale Fung, and Steven Hoi.  Instructblip: Towards general-purpose vision-language models with instruction tuning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2023.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Fan et al. [2023] Jiashuo Fan, Yaoyuan Liang, Leyao Liu, Shaolun Huang, and Lei Zhang.  Rca-noc: Relative contrastive alignment for novel object captioning.  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2023.
  * Fang et al. [2023] Yuxin Fang, Wen Wang, Binhui Xie, Quan Sun, Ledell Wu, Xinggang Wang, Tiejun Huang, Xinlong Wang, and Yue Cao.  Eva: Exploring the limits of masked visual representation learning at scale.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Fei et al. [2023] Junjie Fei, Teng Wang, Jinrui Zhang, Zhenyu He, Chengjie Wang, and Feng Zheng.  Transferable decoding with visual entities for zero-shot image captioning.  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2023.
  * Fei [2021] Zhengcong Fei.  Memory-augmented image captioning.  In _Proc. AAAI Conference on Artificial Intelligence (AAAI)_ , 2021.
  * Gupta et al. [2019] Agrim Gupta, Piotr Dollar, and Ross Girshick.  LVIS: A dataset for large vocabulary instance segmentation.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * Hataya et al. [2023] Ryuichiro Hataya, Han Bao, and Hiromi Arai.  Will large-scale generative models corrupt future datasets?  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2023.
  * Hendricks et al. [2016] Lisa Anne Hendricks, Subhashini Venugopalan, Marcus Rohrbach, Raymond Mooney, Kate Saenko, and Trevor Darrell.  Deep compositional captioning: Describing novel object categories without paired training data.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * Hu et al. [2023] Ziniu Hu, Ahmet Iscen, Chen Sun, Zirui Wang, Kai-Wei Chang, Yizhou Sun, Cordelia Schmid, David A Ross, and Alireza Fathi.  Reveal: Retrieval-augmented visual-language pre-training with multi-source multimodal knowledge memory.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Johnson et al. [2019] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  _IEEE Transactions on Big Data_ , 7(3):535–547, 2019.
  * Karpathy and Fei-Fei [2015] Andrej Karpathy and Li Fei-Fei.  Deep visual-semantic alignments for generating image descriptions.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015.
  * Kenton and Toutanova [2019] Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , 2019.
  * Li et al. [2022] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In _Proc. International conference on machine learning (ICML)_ , 2022.
  * Li et al. [2023] 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 _Proc. International conference on machine learning (ICML)_ , 2023.
  * Li et al. [2020] Xiujun Li, Xi Yin, Chunyuan Li, Pengchuan Zhang, Xiaowei Hu, Lei Zhang, Lijuan Wang, Houdong Hu, Li Dong, Furu Wei, et al.  Oscar: Object-semantics aligned pre-training for vision-language tasks.  In _Proc. European Conference on Computer Vision (ECCV)_ , 2020.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _Proc. European Conference on Computer Vision (ECCV)_ , 2014.
  * Lu et al. [2018] Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh.  Neural baby talk.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Mokady et al. [2021] Ron Mokady, Amir Hertz, and Amit H Bermano.  Clipcap: Clip prefix for image captioning.  _arXiv preprint arXiv:2111.09734_ , 2021.
  * Plummer et al. [2015] Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In _Proc. IEEE International Conference on Computer Vision (ICCV)_ , 2015.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Radford et al. [2021] 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 _Proc. International conference on machine learning (ICML)_ , 2021.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research (JMLR)_ , 21(1):5485–5551, 2020.
  * Ramos et al. [2023a] Rita Ramos, Desmond Elliott, and Bruno Martins.  Retrieval-augmented image captioning.  In _Proc. Conference of the European Chapter of the Association for Computational Linguistics (EACL)_ , 2023a.
  * Ramos et al. [2023b] Rita Ramos, Bruno Martins, Desmond Elliott, and Yova Kementchedjhieva.  Smallcap: Lightweight image captioning prompted with retrieval augmentation.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023b.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Touvron et al. [2023] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Van der Maaten and Hinton [2008] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  _Journal of machine learning research (JMLR)_ , 9(11), 2008.
  * Venugopalan et al. [2017] Subhashini Venugopalan, Lisa Anne Hendricks, Marcus Rohrbach, Raymond Mooney, Trevor Darrell, and Kate Saenko.  Captioning images with diverse objects.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Vo et al. [2022] Duc Minh Vo, Hong Chen, Akihiro Sugimoto, and Hideki Nakayama.  Noc-rek: Novel object captioning with retrieved vocabulary from external knowledge.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Wang et al. [2023] Weihan Wang, Qingsong Lv, Wenmeng Yu, Wenyi Hong, Ji Qi, Yan Wang, Junhui Ji, Zhuoyi Yang, Lei Zhao, Xixuan Song, Jiazheng Xu, Bin Xu, Juanzi Li, Yuxiao Dong, Ming Ding, and Jie Tang.  Cogvlm: Visual expert for pretrained language models.  _arXiv preprint arXiv:2311.03079_ , 2023.
  * [42] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In _Proc. International conference on machine learning (ICML)_.
  * Yang et al. [2023] Zhuolin Yang, Wei Ping, Zihan Liu, Vijay Korthikanti, Weili Nie, De-An Huang, Linxi Fan, Zhiding Yu, Shiyi Lan, Bo Li, et al.  Re-ViLM: Retrieval-augmented visual language model for zero and few-shot image captioning.  In _Findings of the Association for Computational Linguistics: EMNLP_ , 2023.
  * Yasunaga et al. [2023] Michihiro Yasunaga, Armen Aghajanyan, Weijia Shi, Richard James, Jure Leskovec, Percy Liang, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  Retrieval-augmented multimodal language modeling.  In _International Conference on Learning Representations (ICLR)_ , 2023.
  * Zhang et al. [2021] Pengchuan Zhang, Xiujun Li, Xiaowei Hu, Jianwei Yang, Lei Zhang, Lijuan Wang, Yejin Choi, and Jianfeng Gao.  Vinvl: Revisiting visual representations in vision-language models.  In _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Zhu et al. [2023] Deyao Zhu, Jun Chen, Xiaoqian Shen, Xiang Li, and Mohamed Elhoseiny.  Minigpt-4: Enhancing vision-language understanding with advanced large language models.  _arXiv preprint arXiv:2304.10592_ , 2023.

##  Supplementary Material for
EVCap: Retrieval-Augmented Image Captioning with External Visual–Name Memory
for Open-World Comprehension

Figure A: Samples of images and corresponding names in the external
visual–name memory constructed from LVIS’s objects.

This supplementary material complements our paper with the following sections:
First, we delve into the implementation specifics of our EVCap, which were not
covered in the main paper (see Sec. A). Second, we offer an expanded
discussion on the external visual-name memory, as utilized in the main paper
(see Sec. B). Finally, we present additional results to evaluate the
effectiveness of EVCap (see Sec. C).

##  A Implementation Details

Our method is based on Pytorch and is trained within one epoch with a batch
size of 24 using mixed precisions. We optimize the model using AdamW, setting
the weight decay at 0.05, and using $\beta_{1}$ and $\beta_{2}$ values of 0.9
and 0.99, respectively. A cosine learning rate (LR) decay strategy is adopted,
starting with an initial LR of 1e-4. The model undergoes 5000 linear warm-up
steps, beginning with a start LR of 1e-6. During the evaluation phase, we use
a beam search strategy with a beam size of 5 to generate captions.

Figure B: Samples of images and corresponding names in the added WHOOPS’s
objects.

##  B External Visual–Name Memory

###  B.1 LVIS memory

As stated in Sec. 3.2 of the main paper, we utilize 1203 objects from the LVIS
dataset. For each of these objects, we randomly select between one and ten
images from LVIS. Additionally, we enrich our data by incorporating five
synthetic images for each object, created using stable diffusion. We show two
samples of this external visual-name memory, constructed using objects from
LVIS in Fig. A.

###  B.2 WHOOPS memory

To illustrate the scalability of the external memory in EVCap, we expand it by
integrating WHOOPS knowledge into the original external visual–name memory in
Sec. 5.2 and Sec. 5.3 of the main paper. Specifically, we focus on objects
that are mentioned in the answers of VQA annotations in the WHOOPS dataset
because of their conciseness and emphasis on key objects. For each of these
objects, we produce five synthetic images employing stable diffusion. Two
examples from this augmented memory, featuring newly added object images and
their corresponding names, are presented in Fig. B.

##  C Additional Results

Table A: Quantitative results under the CIDEr score on in-domain (In), near-
domain (Near), out-domain (Out), and overall data of the NoCaps test set. *
denotes using a memory bank. We note that our results on the test set are
publicly submitted to Nocaps leader-boarda (8th rank). Higher score is better.
Bold indicates the best results among compared methods, normal indicates the
second best results.

Method | In | Near | Out | Overall
---|---|---|---|---
Heavyweight-training models
VinVL [45] | 93.8 | 89.0 | 66.1 | 85.5
NOC-REK* [40] | 100.0 | 95.7 | 77.4 | 93.0
OSCAR [26] | 81.3 | 79.6 | 73.6 | 78.8
Lightweight-training models
SmallCap* ${}_{\text{GPT2}}$ [35] | 87.9 | 84.6 | 84.4 | 85.0
EVCap* ${}_{\text{Vicuna-13B}}$ | 114.9 | 117.0 | 117.1 | 116.8
Specialist SOTAs
CogVLM ${}_{\text{Vicuna-7B}}$ [5] | – | – | 128.0 | 126.4
PaLI ${}_{\text{mT5-XXL}}$ [9] | – | – | – | 124.4
PaLI-X ${}_{\text{UL2-32B}}$ [8] | – | – | – | 124.3

ahttps://eval.ai/web/challenges/challenge-page/355/leaderboard/1011

###  C.1 Experiments on NoCaps test set

We additionally assess our EVCap against SOTAs on the NoCaps test set, since
we notice several other methods have also benchmarked their performance on
this dataset. Note that, NoCaps test set does not have publicly accessible
ground truth annotations. To obtain evaluation scores, we submitted our
results to the NoCaps leaderboard.

Quantitative results. Tab. A presents the quantitative results of our EVCap on
the NoCaps test set. Our method outperforms all other SOTA models, both in
heavyweight-training and lightweight-training categories, that have reported
results on this dataset. Additionally, as a lightweight method, our approach
achieves the 8th rank on the NoCaps leaderboard, only surpassed by specialized
SOTAs such as CogVLM, which holds the 1st rank.

Qualitative results. Fig. D shows the captions generated by our EVCap
alongside those from three SOTA methods on the NoCaps test set. It also
includes the object names retrieved by EVCap and the captions retrieved by
SmallCap. Consistent with the findings in the main paper, SmallCap tends to
generate hallucinatory objects that are absent in the input images, such as
“tie” and “mouse”. The same hallucinatory object “mouse” is also found in the
retrieved captions, indicating that SmallCap’s diminished performance is
largely due to its reliance on retrieved captions containing irrelevant
information. In comparison, our EVCap demonstrates a performance on par with
BLIP-2.

Figure C: CIDEr scores after training EVCap with the number of object name
query tokens $P$ from 2 to 10. The results indicate that the performance is
relatively optimal when $P$ is set to be 8. Figure D: Examples of captions
generated by our EVCap, and three SOTAs on the NoCaps test set. We also list
the retrieved object names by our EVCap (below the captions of EVCap) and
retrieved captions by SmallCap (right side) in italics. Table B: Comparison
against SOTA methods on training time and used GPUs. * denotes using a memory
bank.

Method | Training time | GPUs
---|---|---
Heavyweight-training models
VinVL [45] | – | –
AoANet+MA* [16] | – | –
NOC-REK* [40] | 8d | 2 RTX3090
RCA-NOC*[13] | 1d | 8 A100
ViECap ${}_{\text{GPT2}}$[15] | – | –
InstructBLIP ${}_{\text{Vicuna-13B}}$[11] | 1.5d | 16 A100
OSCAR [26] | 74h | 1 V100
BLIP [24] | – | 2 16-GPU nodes
BLIP-2 ${}_{\text{FlanT5-XL}}$ [25] |  $\sim$9d | 16 A100
REVEAL* ${}_{\text{T5}}$ [20] | 5d | 256 CloudTPUv4 chips
Lightweight-training models
MiniGPT4 ${}_{\text{Vicuna-13B}}$ [46] | 10h | 4 A100
SmallCap* ${}_{\text{GPT2}}$ [35] | 8h | 1 A100
ClipCap ${}_{\text{GPT2}}$ [29] | 6h | 1 GTX1080
EVCap* ${}_{\text{Vicuna-13B}}$ | 3h | 4 A6000
Specialist SOTAs
Qwen-VL ${}_{\text{Qwen-7B}}$ [5] | – | –
CogVLM ${}_{\text{Vicuna-7B}}$ [41] | 1d | 4096 A100
PaLI ${}_{\text{mT5-XXL}}$ [9] | – | –
PaLI-X ${}_{\text{UL2-32B}}$ [8] | – | –

###  C.2 Further analysis

Comparison on training time and used GPUs. Tab. B compares training time and
the used GPUs of our EVCap with various SOTA models. Due to the diversity of
GPUs employed across different models, drawing a direct comparison is
challenging. Nevertheless, it’s evident that the training time for our EVCap
is comparatively shorter than most models.

Number of object name query tokens. We explore the impact of varying the
number of retrieved object names $P$ (Sec. 3.4 of the main paper) on EVCap in
Fig. C. We train the model using different values of $P$, ranging from 2 to
10, and evaluate the performance under CIDEr on all three benchmarks. The
results suggest that setting $P=8$ offers relatively optimal results.

Figure E: Examples of captions generated by our EVCap, and three SOTAs on the
COCO test set. We also list the retrieved object names by our EVCap (below the
captions of EVCap) and retrieved captions by SmallCap (right side) in italics.
Figure F: Examples of captions generated by our EVCap, and three SOTAs on the
NoCaps validation set. We also list the retrieved object names by our EVCap
(below the captions of EVCap) and retrieved captions by SmallCap (right side)
in italics.

###  C.3 More qualitative examples.

More qualitative examples on the COCO test set, NoCaps validation set, and
Flickr30k test set are shown in Fig. E, Fig. F, and Fig. G, respectively.

Figure G: Examples of captions generated by our EVCap, and three SOTAs on the
Flickr30k test set. We also list the retrieved object names by our EVCap
(below the captions of EVCap) and retrieved captions by SmallCap (right side)
in italics.