# A Note on Scheduling Equal-Length Jobs
to Maximize Throughput

Marek Chrobak Department of Computer Science, University of California,
Riverside, CA 92521<EMAIL_ADDRESS>Supported by NSF grants
CCR-9988360, CCR-0208856, and NSF/CNRS grant INT-0340752. Christoph Dürr
Laboratoire de Recherche en Informatique, Université Paris-Sud, 91405 Orsay,
France<EMAIL_ADDRESS>Supported by the EU 5th framework programs QAIP
IST-1999-11234, the NSF/CNRS grant 17171 and the CNRS/STIC 01N80/0502 and
01N80/0607 grants. Wojciech Jawor11footnotemark: 1 Łukasz Kowalik Instytut
Informatyki, Uniwersytet Warszawski, Banacha 2, 02–097, Warszawa, Poland.
<EMAIL_ADDRESS>Supported by KBN grant 4T11C04425. Maciej
Kurowski33footnotemark: 3

###### Abstract

We study the problem of scheduling equal-length jobs with release times and
deadlines, where the objective is to maximize the number of completed jobs.
Preemptions are not allowed. In Graham’s notation, the problem is described as
$1|r_{j};p_{j}=p|\sum U_{j}$. We give the following results: (1) We show that
the often cited algorithm by Carlier from 1981 is not correct. (2) We give an
algorithm for this problem with running time $O(n^{5})$.

##  1 Introduction

We study the following scheduling problem: We are given $n$ jobs numbered
$1,2,\dots,n$. For each job $j$, a release time $r_{j}$ and a deadline $d_{j}$
are given. All jobs have the same processing time $p$. (We assume that all
numbers are positive integers.) We want to find a non-preemptive schedule of
the given set of jobs that maximizes the throughput, where the _throughput_ is
defined as the number of completed jobs. (Equivalently, we can minimize the
number of late jobs.) In Graham’s notation, the problem is described as
$1|r_{j};p_{j}=p|\sum U_{j}$.

The feasibility version of this problem, where we ask whether _all_ jobs can
meet their deadlines, has been studied thoroughly. Polynomial time algorithms
for this version were first found, independently, by Simons [4] and Carlier
[2]. A faster algorithm, with running time $O(n\log n)$, was subsequently
given by Garey et al [3]. Interestingly, all three algorithms use quite
different techniques.

The elegant feasibility algorithm of Carlier [2] is based on a dynamic
programming approach that processes jobs from left to right (in order of
release times). For each time $t$, it constructs a partial schedule with jobs
that complete execution at or before time $t$. Carlier also considers a
certain _dominance_ relation on partial schedules. Intuitively, one partial
schedule dominates another if this other schedule cannot be extended to
produce an overall better schedule, independently of the jobs that are to be
released after time $t$. The schedule computed for each time has the property
that it dominates all other partial schedules up to this time.

In [2], Carlier also attempted to extend his technique to the maximization
problem, and proposed a polynomial-time algorithm. This result is now widely
cited in the literature. However, in Section 3 we present an example of an
instance on which Carlier’s algorithm produces a sub-optimal schedule, proving
that this algorithm is not correct. We then extend our construction to show
that even the general approach from [2] does not work. To this end, we show
that any left-to-right dynamic programming algorithm needs to keep track of an
exponential number of partial schedules. (See Section 4 for a more rigorous
statement of this claim.) This result reveals an interesting feature of
scheduling equal-length jobs, as it shows that the maximization problem is
structurally more difficult than the feasibility problem.

Finally, in Section 5, we present an $O(n^{5})$-time algorithm for
$1|r_{j};p_{j}=p|\sum U_{j}$. Our technique is based on the approach developed
by Baptiste [1], who gave an $O(n^{7})$-time algorithm for the weighted
version of this problem.

##  2 Preliminaries

In the rest of the paper ${\cal J}$ denotes a set of $n$ jobs, $r_{j}$ and
$d_{j}$ the integer release time and deadline of a job $j$, and $p$ a fixed
processing time. Typically, we assume ${\cal
J}={\left\\{1,2,\dots,n\right\\}}$, although in the next section we also use
capital letters $A,B,\dots$, to denote jobs (possibly with indices.)

We order the jobs according to the deadlines, breaking the ties arbitrarily,
that is, $i<j$ implies $d_{i}\leq d_{j}$, for all $i,j$. Without loss of
generality, we assume that $d_{j}\geq r_{j}+p$ for all $j$. We can further
assume that $\min_{i}r_{i}=0$, and by ${d_{\mbox{\tiny max}}}=d_{n}$ we denote
the latest deadline.

We say that a job $j$ is _executed_ in time interval $[t,t^{\prime}]$ if it is
started and completed in $[t,t^{\prime}]$. (Equivalently, the job $j$ is
started after or at $t$, but no later than at $t^{\prime}-p$.) Thus all the
scheduled jobs must be executed in the interval $[0,{d_{\mbox{\tiny max}}}]$.

A _schedule_ $S$ is a function that assigns starting times to some of the jobs
in ${\cal J}$, such that the scheduled jobs are executed between their release
times and deadlines and no two jobs overlap.

Define a schedule $S$ to be _canonical_ if it has the following two
properties:

(c1) $S$ is _left-shifted_ , in the following sense: for any job $j\in S$, the
starting time of $j$ is either $r_{j}$ or the completion time of the job in
$S$ that precedes $j$.

(c2) $S$ is _earliest-deadline_ , that is, if $i,j\in S$ and $i$ is scheduled
before $j$, then either $i$ is scheduled before $r_{j}$ or $i<j$.

It is quite easy to see that each schedule can be converted into a canonical
schedule without changing the set of completed jobs. For suppose that there
are two jobs $i,j\in S$ that violate condition (c2). This means that $i>j$,
but $i$ is scheduled at or after time $r_{j}$ and before $j$. We can then swap
$i$ with $j$ in the schedule. We continue this process until we obtain a
schedule that satisfies (c2). Then, to achieve condition (c1), we modify the
schedule from left to right by shifting all jobs leftward, either to their
release times, or to the completion time of the previous job, whichever is
greater. Note that this shifting cannot violate property (c2).

For simplicity, we will slightly abuse the terminology above and treat a
schedule simply as a _sequence_ of jobs. The actual schedule corresponding to
this sequence is a left-shifted schedule that executes the jobs in the given
order. Further, we will sometimes treat a schedule $S$ as a _set_ of scheduled
jobs, and write $i\in S$, etc.

Denote by $C(S)$ the makespan of a schedule $S$ (that is, the latest
completion time of a job in $S$.) If $m\not\in S$ and $d_{m}\geq C(S)+p$, then
by $S\oplus m$ we denote the schedule obtained from $S$ by scheduling $m$ at
time $\max{\left\\{C(S),r_{m}\right\\}}$. The schedule $S\oplus m$ is called
an _extension_ of $S$.

##  3 Carlier’s Algorithms

### Feasibility algorithm.

In [2] Carlier presented two algorithms for scheduling equal-length jobs. The
first algorithm was for determining feasibility, and the second for maximizing
throughput.

The feasibility algorithm for each time $x=0,1,\dots,{d_{\mbox{\tiny max}}}$
computes a schedule $S_{x}$ of jobs to be executed in the interval $[0,x]$. We
call $S_{x}$ _active_ if it contains all jobs with deadlines at most
$C(S_{x})$. The schedules $S_{x}$ are computed incrementally, from left to
right, as follows. At time $x$, we consider the set $H={\left\\{j\in{\cal
J}:r_{j}\leq x-p\right\\}}-S_{x-p}$, namely the jobs that were released at or
before $x-p$ and have not been scheduled in $S_{x-p}$. If $H=\emptyset$, we
take $S_{x}=S_{x-p}$. Otherwise, pick the earliest-deadline job $m\in H$. If
$S_{x-p}\oplus m$ is active, let $S_{x}=S_{x-p}\oplus m$, otherwise
$S_{x}=S_{x-1}$. After we compute $S_{{d_{\mbox{\tiny max}}}}$, if
$S_{{d_{\mbox{\tiny max}}}}={\cal J}$, we are done, otherwise report that
${\cal J}$ is not feasible. To achieve polynomial time, we can modify the
algorithm, so that it only considers the time values $x=r_{j}+lp$, for some
$j\in{\cal J}$ and $l\in{\left\\{0,\dots,n\right\\}}$.

To justify correctness of this algorithm, Carlier considers a certain
_dominance_ relation on partial schedules. Intuitively, one partial schedule
dominates another if this other schedule cannot be extended to produce an
overall better schedule, independently of the jobs that are to be released in
the future. It turns out that, under the assumption that ${\cal J}$ is
feasible, at each step $x$, schedule $S_{x}$ dominates all other schedules in
the interval $[0,x]$. In particular, this implies that, for $x={d_{\mbox{\tiny
max}}}$, the resulting schedule $S_{d_{\mbox{\tiny max}}}$ will contain all
jobs from ${\cal J}$. It should be noted that this algorithm, as well as the
next maximization algorithm, does not take into account the values of the
deadlines of the non-expired jobs, when choosing the next job to schedule,
only their ordering.

### Maximization algorithm.

In [2], Carlier also attempted to extend his technique to the maximization
problem, and proposed the following algorithm:

Algorithm 1
---
Initialize $S_{x}^{0}=\emptyset$ for all $x$ and $S_{x}^{k}$ undefined for
$k\geq 1$
for $k=1,2,\dots,n$ do
|  for $x=p,p+1,\dots,{d_{\mbox{\tiny max}}}$ do
|  | $H{\;\leftarrow\;}{\left\\{j\in{\cal J}:r_{j}+p\leq x\right\\}}-S_{x-p}^{k-1}$
|  |  $H^{\prime}{\;\leftarrow\;}{\left\\{j\in H:d_{j}\geq x\right\\}}$
|  |  if $H^{\prime}=\emptyset$
|  |  |  then $S_{x}^{k}{\;\leftarrow\;}S_{x-1}^{k}$
|  |  |  else
|  |  |  |  $m{\;\leftarrow\;}$ earliest deadline job in $H^{\prime}$
|  |  |  | $S_{x}^{k}{\;\leftarrow\;}S_{x-p}^{k-1}\oplus m$
return $S_{d_{\mbox{\tiny max}}}^{k}$ for the largest $k$ such that
$S_{d_{\mbox{\tiny max}}}^{k}$ is defined

The algorithm does not specify the start times of the jobs in the schedule,
only their ordering. As explained in the introduction, the actual schedule is
obtained by left-shifting the jobs in this sequence.

A counter-example. We now show that the above algorithm is not correct.
Consider the instance ${\cal J}={\left\\{A,B,C\right\\}}$ given in Fig. 1.
Each job $j$ is represented by a rectangle of length equal to the processing
time (in this case $p=2$), extending from its release time $r_{j}$ to
$r_{j}+p$, and by a line segment extending from $r_{j}+p$ to $d_{j}$. For
example, $r_{C}=1$ and $d_{C}=7$.

$S^{k}_{x}$ | $x=$ |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7
---|---|---|---|---|---|---|---|---|---
$k\\!=\\!1$ |  |  - |  - |  A |  C |  C |  B |  C |  C
$k\\!=\\!2$ |  |  - |  - |  - |  - |  AC |  CB |  CB |  BC
$k\\!=\\!3$ |  |  - |  - |  - |  - |  - |  - |  - |  -

Figure 1: Counter-example for Carlier’s maximization algorithm. The instance
is shown on the left, and the schedules $S^{k}_{x}$ are shown in the table on
the right.

In the loop for $k=1$ the algorithm constructs the schedules $(A)$, $(C)$, and
$(B)$. Then, for $k=2$, it computes the schedules $(A,C)$, $(C,B)$, $(B,C)$,
and for $k=3$ it finds no schedules. The optimal schedule is $(A,B,C)$. The
algorithm fails simply because the schedules computed for $k=2$ do not include
$(A,B)$, which is the only schedule of 2 jobs that can be extended to
$(A,B,C)$ by adding a job at the end.

##  4 A Better Counter-Example

The example above still leaves open the possibility that the algorithm can be
corrected with some minor modifications. We now give another construction
showing that even the general strategy from [2], namely a _left-to-right
dynamic programming approach_ , as defined later in this section, will not
work. In this approach we associate with every time $t$ a set ${\bf S}_{t}$ of
partial schedules, which are idle after $t$. Every set ${\bf S}_{t}$ is
computed by adding more jobs to schedules in sets ${\bf S}_{t^{\prime}}$ for
some earlier times $t^{\prime}<t$. Further, the decisions of the algorithm at
time $t$ can only depend on the values of the release times and deadlines that
are smaller or equal $t$ and comparisons involving deadlines that are greater
than $t$.

To illustrate this concept, consider the instances shown in Figure 2, where
$p=4$. Up to time $9$ the two instances are indistinguishable. The overall
optimal schedules are $(A,C,D,B)$ for the upper instance, and $(B,D,A)$ for
the lower instance. So a left-to-right dynamic program must store the partial
schedules $(B,D)$ and $(A,C)$ at time $9$.

Figure 2: An example of two instances where a left-to-right dynamic
programming algorithm must store two schedules at time $t=9$.

We now amplify this construction by telescoping $n$ instances of this kind. As
a result, we get an exponential number of partial schedules in some initial
interval $[0,t_{0}]$ that are “indistinguishable” from each other by any left-
to-right dynamic programming algorithm. Since the optimal solutions to those
instances in $[0,t_{0}]$ are different, any such algorithm would have to keep
track of exponentially many partial schedules.

For every $m$-bit string ${\bar{x}}=x_{0}x_{1}\ldots x_{m-1}$ we define an
instance ${\cal J}_{\bar{x}}$ that consists of $4m$ jobs. The instance is
partitioned into $m$ sub-instances, with sub-instance
$i\in{\left\\{0,\dots,m-1\right\\}}$ containing jobs $A_{i}$, $B_{i}$,
$C_{i}$, and $D_{i}$. We take $p$, the processing time, to be a sufficiently
large integer (as explained later, any $p\geq 2m+3$ will work). For
$i=0,\dots,m$, let

$\displaystyle u_{i}\;=\;i(2p+1)\quad\mbox{\rm and}\quad
v_{i}\;=\;m(2p+1)+\sum_{j=i}^{m-1}(p+(p+1)x_{i}).$

Let $t_{0}=u_{m}=v_{m}$. The time-scale is divided into intervals
$[u_{i},u_{i+1}]$ for the left part and into intervals $[v_{i+1},v_{i}]$ for
the second part. The release times and deadlines of the jobs are given in the
following table.

Figure 3: The instance ${\cal J}_{\bar{x}}$ defined by a bit string ${\bar{x}}$ starting with $10$. job | $A_{i}$ | $B_{i}$ | $C_{i}$ | $D_{i}$
---|---|---|---|---
release time | $u_{i}$ | $u_{i}+1$ | $u_{i}+p$ | $u_{i}+p+1$
deadline if $x_{i}=0$ | $v_{i+1}+p$ | $v_{i+1}+2$ | $u_{i}+2p$ | $v_{i+1}+1$
deadline if $x_{i}=1$ | $v_{i+1}+2p+1$ | $v_{i+1}+2p$ | $u_{i}+2p$ | $v_{i+1}+p$

Figure 3 shows an example of an instance ${\cal J}_{\bar{x}}$, for
${\bar{x}}=10...$.

For any given $m$-bit string ${\bar{x}}=x_{0}x_{1}\ldots x_{m-1}$, we define a
schedule $R_{\bar{x}}$ of ${\cal J}_{\bar{x}}$ as follows for all $0\leq i\leq
m-1$:

  * •

If $x_{i}=0$, $B_{i}$ and $D_{i}$ are scheduled at their release times and
$A_{i}$ right before its deadline (that is, at time $v_{i+1}$.) $C_{i}$ is not
scheduled.

  * •

If $x_{i}=1$, $A_{i}$ and $C_{i}$ are scheduled at their release times and
$D_{i},B_{i}$ right before their deadlines (that is, at times $v_{i+1}$ and
$v_{i+1}+p$, respectively.)

###### Lemma 1

Let ${\bar{x}}=x_{0}x_{1}\ldots x_{m-1}$ be an $m$-bit string. Then
$R_{\bar{x}}$ is an optimal schedule for ${\cal J}_{\bar{x}}$. Moreover, any
optimal schedule $S$ for ${\cal J}_{\bar{x}}$ contains the same job sequence
as $R_{\bar{x}}$.

Proof: By routine inspection, $R_{\bar{x}}$ is a correct schedule. We claim
that $R_{\bar{x}}$ is optimal. Let $\xi=\sum_{i}x_{i}$. Then schedule
$R_{\bar{x}}$ contains $3m+\xi$ jobs. In this schedule each interval
$[u_{i},u_{i+1}]$ has idle time $1$, and each interval $[v_{i+1},v_{i}]$ has
idle time $x_{i}$. So the total idle time is $m+\xi\leq 2m$, and thus, for
$p\geq 2m+3$, $R_{\bar{x}}$ is an optimal schedule.

It remains to show that every optimal schedule has the same job sequence as
$R_{\bar{x}}$. For this purpose let $\bar{S}$ be an optimal schedule and let
$S$ be a schedule obtained from $\bar{S}$ by left-shifting the jobs before
$t_{0}$ and right-shifting the jobs after $t_{0}$. Formally every job
scheduled before $t_{0}$ either starts at its release time or at the
completion time of another job, and every job scheduled at $t_{0}$ or later
completes either at its deadline or at a time where another job is started.
Clearly the order in which the jobs appear in $\bar{S}$ and $S$ is the same.

By induction, we show for every $0\leq i\leq m-1$ that $S$ is identical with
$R_{\bar{x}}$ in $[u_{i},u_{i-1}]\cup[v_{i+1},v_{i}]$. By induction hypothesis
these intervals can contain no job from $A_{j},B_{j},C_{j},D_{j}$ for $j<i$.
It shows that the only available jobs in $[u_{i},u_{i-1}]\cup[v_{i+1},v_{i}]$
are $A_{i},B_{i},C_{i},D_{i}$.

When $x_{i}=0$, the interval $[v_{i+1},v_{i}]$ must contain the job $A_{i}$,
otherwise the idle time would be more than $p-2>2m$, which contradicts the
optimality of $S$. Then the interval $[u_{i},u_{i+1}]$ cannot contain $C_{i}$,
since this would imply that the period $[u_{i},u_{i}+p]$ is idle. Therefore
this interval must contain the jobs $B_{i},D_{i}$, in that order.

When $x_{i}=1$, the intervals $[u_{i},u_{i+1}]$ and $[v_{i+1},v_{i}]$ must
contain all four jobs, at least portions of it, otherwise the idle time would
be at least $p>2m$. Job $C_{i}$ is tight. Therefore job $A_{i}$ must be
scheduled at its release time. This in turn shows that $D_{i},B_{i}$ must be
scheduled in the interval $[v_{i+1},v_{i}]$ in that order. $\Box$

A left-to-right dynamic algorithm is an algorithm ${\cal A}$ with the
following properties:

  * •

It processes the jobs from left to right on the time axis, and for each time
$t$ it constructs a collection ${\bf S}_{t}$ of partial schedules in the
interval $[0,t]$. The schedules in ${\bf S}_{t}$ are obtained by extending
schedules from ${\bf S}_{t^{\prime}}$, for $t^{\prime}<t$, by appending new
jobs at the end. The final schedule is chosen from ${\bf S}_{t}$ for
$t={d_{\mbox{\tiny max}}}$.

  * •

At each step $t$, ${\cal A}$ decides which non-expired jobs should be added to
previous schedules. This decision is based on values of the release times and
deadlines which are smaller or equal $t$ and on pairwise comparisons between
deadlines that are greater than $t$.

Consider now the behavior of ${\cal A}$ on instances ${\cal J}_{\bar{x}}$.
Until $t_{0}$, all these instances are indistinguishable to ${\cal A}$, since
all jobs expired by time $t_{0}$ are identical, and the deadline ordering for
the jobs. (For each $i$, the deadline ordering of $A_{i},B_{i},D_{i}$, does
not depend on whether $x_{i}=0$ or $1$.) Thus at time $t_{0}$, for each
${\bar{x}}$, ${\cal A}$ would need to store a partial schedule that consist of
the first $2m$ jobs from $R_{\bar{x}}$. So ${\cal A}$ would need to keep track
of exponentially many partial schedules.

It should be noted that the maximization algorithm proposed by Carlier does
fall into the framework described above. Although the algorithm, as shown,
makes $n$ left-to-right passes along the time axis, each schedule $S^{k}_{t}$
depends only on schedules $S^{k^{\prime}}_{t^{\prime}}$ for $k^{\prime}\leq k$
and $t^{\prime}\leq t$. So the algorithm could be equivalently reformulated to
compute all these schedules in just a single pass.

One may also ask what happens if some bounded look-ahead, say $\ell p$, is
allowed in the algorithm. Our construction can be easily modified to show that
this will also not work. To see this, simply add $\ell$ “tight” jobs to the
instances, with release times $t_{0},t_{0}+p,\dots,t_{0}+(\ell-1)p$, and
deadlines $t_{0}+p,\dots,t_{0}+\ell p$, respectively, and shift the right half
of the instances by $\ell p$. The same result holds, if the algorithm is
granted the ability to verify if the schedules in ${\bf S}_{t}$ are feasible
or not. The details are left to the reader.

##  5 A Maximization Algorithm

Our algorithm is based on a technique developed by Baptiste [1] for solving
the weighted version of the problem. We show how to improve Baptiste’s
$O(n^{7})$ time complexity exploiting the fact that the jobs have equal
weights. Our algorithm can be thought of as a dual to the one in [1]. While
Baptiste’s algorithm computes maximum weight schedules for a certain family of
sub-instances, our algorithm considers similar sub-instances, but for given
weights computes _minimum makespans_ of schedules with given weights. In our
case, the weight of a schedule is the number of jobs, and thus is bounded by
$n$. This gives us a desired reduction in running time.

###### Theorem 1

The scheduling problem $1|r_{j};p_{j}=p|\sum U_{j}$ can be solved in time
$O(n^{5})$.

Proof: Our algorithm uses dynamic programming and it runs in $n$ phases.
During the $k$-th phase we take under consideration only jobs $1,2,\ldots,k$.
(Recall that jobs are ordered by their deadlines.) Let
$\Theta^{\prime}={\left\\{r_{i}+lp:\;i=1,\ldots,n;\;l=-1,0,\ldots,n\right\\}}$.
It is easy to see that $|\Theta^{\prime}|=O(n^{2})$. For each
$\alpha\in\Theta^{\prime}$ and each $u\in{\left\\{1\ldots k\right\\}}$ we
define:

${\cal J}^{k}_{\alpha}$ = the set of all jobs
$j\in{\left\\{1,2,\dots,k\right\\}}$ with $r_{j}\geq\alpha$.

$B^{k}_{\alpha,u}$ = the minimal value $\beta\in\Theta^{\prime}$ such that it
is possible to execute exactly $u$ jobs from ${\cal J}^{k}_{\alpha}$ in the
interval $[\alpha+p,\beta]$.

If a schedule in the definition of $B^{k}_{\alpha,u}$ does not exist, we
assume that $B^{k}_{\alpha,u}=+\infty$. It is convenient to extend this
notation by setting $B^{k}_{\alpha,0}=\alpha+p$ for all
$k\in{\left\\{0,\ldots,n\right\\}}$, $\alpha\in\Theta^{\prime}$, and
$B^{k}_{\alpha,u}=+\infty$ for $k\in{\left\\{0,\ldots,n\right\\}}$,
$\alpha\in\Theta^{\prime}$ and $u>k$.

Now we show how $B^{k}_{\alpha,u}$ depends on the values computed during the
previous phase, i.e. $B^{k-1}_{\alpha^{\prime},u^{\prime}}$, for
$\alpha^{\prime}\in\Theta^{\prime}$ and
$u^{\prime}\in{\left\\{0,\ldots,n\right\\}}$. Let $k>0$, $\alpha$, $u>0$ be
fixed, and let us consider a canonical schedule $S$ that satisfies the
conditions defining $B^{k}_{\alpha,u}$:

(s1) exactly $u$ jobs from ${\cal J}^{k}_{\alpha}$ are executed in $S$,

(s2) all jobs are executed in the interval $[\alpha+p,\beta]$,

(s3) $\beta$ is minimal,

where $\beta=B^{k}_{\alpha,u}$. If $k\notin S$ then we have
$B^{k}_{\alpha,u}=B^{k-1}_{\alpha,u}$. So from now on we will assume that
$k\in S$. We will denote the number of jobs executed in $S$ before and after
$k$ by $x$ and $y$, respectively. The starting time of job $k$ is denoted by
$\gamma$. (See Fig 4.)

Figure 4: Notation

Since the jobs are ordered by their deadlines, and $S$ is canonical, we
conclude that $S$ must satisfy the following conditions:

(s4) all the jobs executed after job $k$ are in ${\cal J}^{k-1}_{\gamma}$ and
are executed in the interval $[\gamma+p,\beta]$,

(s5) all the jobs executed before job $k$ are in ${\cal J}^{k-1}_{\alpha}$ and
are executed in the interval $[\alpha+p,\gamma]$,

(s6) $\gamma=\max(r_{k},B^{k-1}_{\alpha,x})$,

(s7) $\beta=B^{k-1}_{\gamma,y}$.

Notice that, if we knew the value of $x$, we could easily derive $\gamma$
using property (s6), and then derive $\beta$ using property (s7). As we do not
know $x$, we have to iterate over all possible values $x=0,1,\ldots,u-1$, and
choose the schedule with minimal $\beta$. Finally, we set $B^{k}_{\alpha,u}$
to $\min(B^{k-1}_{\alpha,u},\beta)$.

The algorithm is summarized in the pseudo-code below:

Algorithm 2
---
Let $\Theta^{\prime}$ be the set of values $r_{i}+pl$ where
$i\in{\left\\{1,2,\dots,n\right\\}}$ and
$l\in{\left\\{-1,0,\ldots,n\right\\}}$
for $\alpha\in\Theta^{\prime}$, $k\in{\left\\{0,\ldots,n\right\\}}$, and
$u\in{\left\\{k+1,\ldots,n\right\\}}$ do
$B^{k}_{\alpha,u}{\;\leftarrow\;}+\infty$
for $\alpha\in\Theta^{\prime}$ and $k\in{\left\\{0,\ldots,n\right\\}}$ do
$B^{k}_{\alpha,0}{\;\leftarrow\;}\alpha+p$
for $k{\;\leftarrow\;}1,2,\dots,n$ do
|  for $\alpha\in\Theta^{\prime}$ and $u\in{\left\\{1,\ldots,k\right\\}}$ do
|  |  $\beta_{\mbox{\rm\tiny min}}{\;\leftarrow\;}B^{k-1}_{\alpha,u}$
|  |  for $x{\;\leftarrow\;}0,1,\dots,u-1$ do
|  |  |  $y{\;\leftarrow\;}u-x-1$
|  |  |  $\gamma{\;\leftarrow\;}\max(r_{k},B^{k-1}_{\alpha,x})$
|  |  |  if $\gamma+p\leq d_{k}$ then
|  |  |  |  $\beta{\;\leftarrow\;}B^{k-1}_{\gamma,y}$
|  |  |  |  $\beta_{\mbox{\rm\tiny min}}{\;\leftarrow\;}\min(\beta_{\mbox{\rm\tiny min}},\beta)$
|  |  $B^{k}_{\alpha,u}{\;\leftarrow\;}\beta_{\mbox{\rm\tiny min}}$

After the completion of the algorithm, the number of jobs executed in the
optimal schedule is equal to the maximal value of $u$ such that
$B^{n}_{-p,u}\neq+\infty$. (Recall that, by our convention,
$\min(\Theta^{\prime})=-p$.) The optimal schedule itself can also be easily
derived from the values stored in the array $B$ with the use of standard
techniques.

The overall complexity of our algorithm is $O(n^{5})$, because each of
$O(n^{4})$ values $B^{k}_{\alpha,u}$ is computed in linear time. $\Box$

## References

  * [1] P. Baptiste.  Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times.  Journal of Scheduling, 2:245–252, 1999.
  * [2] J. Carlier.  Problèmes d’ordonnancement à durées égales.  QUESTIO, 5(4):219–228, 1981.
  * [3] M. Garey, D. Johnson, B. Simons, and R. Tarjan.  Scheduling unit-time tasks with arbitrary release times and deadlines.  SIAM Journal on Computing, 10(2):256–269, 1981.
  * [4] B. Simons.  A fast algorithm for single processor scheduling.  In Proceedings IEEE 19th Annual Symposium on Foundations of Computer Science (FOCS’78), pages 246–252, 1978.


# MLLM-Bench, Evaluating Multi-modal LLMs using GPT-4V

Wentao Ge†, Shunian Chen†, Guiming Chen†, Junying Chen†, Zhihong Chen , Shuo
Yan, Chenghao Zhu
Ziyue Lin, Wenya Xie, Xidong Wang, Anningzhe Gao, Zhiyi Zhang, Jianquan Li,
Xiang Wan, Benyou Wang∗
Shenzhen Research Institute of Big Data
The Chinese University of Hong Kong, Shenzhen
<EMAIL_ADDRESS><EMAIL_ADDRESS>
https://github.com/FreedomIntelligence/MLLM-Bench
https://mllm-bench.llmzoo.com/
First four authors contributed to this work equally; Zhihong and Benyou are
the corresponding authors

###### Abstract

In the pursuit of Artificial General Intelligence (AGI), the integration of
vision in language models has marked a significant milestone. The advent of
vision-language models (MLLMs) like GPT-4V have expanded AI applications,
aligning with the multi-modal capabilities of the human brain. However,
evaluating the efficacy of MLLMs poses a substantial challenge due to the
subjective nature of tasks that lack definitive answers. Existing automatic
evaluation methodologies on multi-modal large language models rely on
objective queries that have standard answers, inadequately addressing the
nuances of creative and associative multi-modal tasks. To address this, we
introduce MLLM-Bench, an innovative benchmark inspired by Vicuna (Zheng et
al., 2023), spanning a diverse array of scenarios, including Perception,
Understanding, Applying, Analyzing, Evaluating, and Creation along with the
ethical consideration. MLLM-Bench is designed to reflect user experience more
accurately and provide a more holistic assessment of model performance.
Comparative evaluations indicate a significant performance gap between
existing open-source models and GPT-4V. We posit that MLLM-Bench will catalyze
progress in the open-source community towards developing user-centric vision-
language models that meet a broad spectrum of real-world applications. See
online leaderboard in https://mllm-bench.llmzoo.com.

##  1 Introduction

The field of artificial intelligence has witnessed a paradigm shift with the
incorporation of multi-modal inputs, particularly the amalgamation of visual
and linguistic data, mirroring the complex processing capabilities of the
human brain. The development of multi-modal large language models (MLLMs) such
as GPT-4V represents a leap towards more sophisticated, context-aware AI
systems. These models are increasingly crucial for tasks that demand an
understanding of both visual cues and textual content, embodying a step closer
to the elusive goal of Artificial General Intelligence (AGI). However, the
expansion of capabilities brings forth the challenge of evaluation – how does
one accurately measure the effectiveness of a system designed to mimic the
inherently subjective and associative processes of human perception?

The predominant evaluation frameworks for MLLMs have largely centered on
objective metrics derived from tasks with clear-cut, correct answers. Such
tasks, while valuable, do not encapsulate the full spectrum of human-like
cognitive tasks that modern MLLMs aim to perform. The realms of creativity,
association, and ethical judgment within multi-modal contexts, for instance,
resist reduction to simple right or wrong answers. This limitation in
evaluation methodologies leads to an incomplete understanding of a model’s
capabilities and fails to provide insight into how such models might interact
with users in real-world scenarios, where answers are often nuanced and
context-dependent.

In response to this gap, we introduce MLLM-Bench, a comprehensive benchmarking
suite inspired by the multifaceted nature of the vicuna (Zheng et al., 2023).
MLLM-Bench encompasses six levels of capabilities: Perception, Understanding,
Applying, Analyzing, Evaluating, and Creation.111This categorization is
inspired by Bloom’s Taxonomy. It also delves into five detailed sub-scenarios
designed to probe the models’ abilities in nuanced and complex contexts. By
aligning our benchmarking closer to real-world applications and user
experiences, we aim to not only provide a more rigorous assessment of current
MLLMs but also to drive the open-source community towards the development of
more user-friendly and contextually adept vision-language models.

The contributions of this paper are three-fold:

  * •

Systematic Evaluation on Open Vision-Language Tasks: The paper introduces a
comprehensive evaluation framework for open-ended vision-language tasks. This
approach marks a significant advancement in assessing MLLMs, moving beyond
traditional, narrowly defined tasks. The systematic evaluation encompasses a
broader range of scenarios that MLLMs encounter, providing a more accurate
measure of their capabilities in mimicking human-like cognitive processes.

  * •

Comprehensive Taxonomy Design Highlighting Ethical Considerations: The authors
designed a detailed taxonomy for benchmarking MLLMs. This taxonomy not only
categorizes various tasks and scenarios MLLMs might encounter but also
emphasizes the ethical implications associated with these benchmarks. By doing
so, the paper addresses a critical aspect often overlooked in AI development,
ensuring that ethical considerations are integral to the evaluation process of
MLLMs.

  * •

Introduction of a New Benchmark Dataset and Systematic Evaluation of Existing
Models: The paper presents a new benchmark dataset, MLLM-Bench, specifically
tailored to test the multifaceted capabilities of MLLMs in more complex and
nuanced contexts. In addition to introducing this dataset, the paper conducts
a systematic evaluation of existing vision-language models against this
benchmark. This approach not only assesses current models’ performance but
also sets a new standard for future developments in MLLMs, aligning them
closer to real-world applications and user experiences.

##  2 MLLM-Benchmark

###  2.1 Taxonomy

##### Six Hierarchical Capability Level

Due to the absence of a standardized framework for categorizing the
capabilities of multi-modal large language models, and acknowledging that
vision language models emulate human cognitive processes to a certain extent,
we have chosen to adopt the revised Bloom’s Taxonomy (Krathwohl, 2002) as the
framework for this benchmark. In reference to Bloom’s Taxonomy, we manually
conclude 42 capabilities of MLLMs across a hierarchy spanning six cognitive
levels and create 10 questions for each capability. For each of the
capabilities, we create 10 questions, resulting in a total of 420 image-
instruction pairs, as shown in Table 1. The detailed capability levels are
shown below:

  * •

Perception: In this level, MLLMs have the basic capability to recognize and
retrieve information from multi-modal inputs, i.e., image and text
instructions. This is basically matching elements in the image to text. The
capabilities involved in this level include general object recognition, OCR,
landmark recognition, etc.

  * •

Understanding: Building upon the capabilities of the previous level, MLLMs
with this level of capability should be able to process the information
gathered during perception to construct meaning. This involves comprehension
and interpretation of the data in context.

  * •

Applying: MLLMs with this level of capability can apply the information and
knowledge to new but similar situations. This includes using information from
one modality to inform another, such as applying text-based knowledge to
understand an image. Typical capabilities at this level include medical image
understanding and professional graph understanding.

  * •

Analyzing: In the analysis stage, MLLMs at this capability level have the
ability to break information into parts to explore patterns and relationships.
This level is where the model engages in more complex tasks like attribute
comparison, where it discerns subtle differences or similarities between
objects, or event cause reasoning, where it infers causal relationships within
the data.

  * •

Evaluation: Evaluation capabilities enable MLLMs to make judgments based on
criteria and standards. This could involve assessing the quality of images,
identifying potential problems, or discerning the authenticity of image
content.

  * •

Creation: The highest level of MLLMs’ capability involves the creation of new
and original works. At this level, models should be able to synthesize
information from both visual and textual data to generate new content, which
can range from visual storytelling to coding with vision.

##### Emphasis on Ethics

While advancing the technical capabilities of MLLMs, it is crucial to ensure
that these models also adhere to high ethical standards and can detect or
identify ethical issues. In pursuit of this objective, within the MLLM-Bench,
we have specifically integrated a capability that includes a comprehensive
suite of ethical considerations, including bias detection, ethical judgments,
and privacy protection.

Table 1: Overview of 42 capabilities on 6 cognitive levels in MLLM-Bench. Capability Level | Capability | Total Number
---|---|---
Level 1: Perception | General Object Recognition | 10
OCR | 10
Action Recognition | 10
Logo Recognition | 10
Food Recognition | 10
Landmark Recognition | 10
Multilingual Text Recognition | 10
Level 2: Understanding | Scene Understanding | 10
Attribute Recognition | 10
Image Topic Understanding | 10
Hidden Objects Recognition | 10
Facial Expression Recognition | 10
Emotion Understanding | 10
Multi-modal Commonsense Understanding | 10
Joke and Meme Understanding | 10
Multilingual Multicultural Understanding | 10
Document Understanding | 10
Level 3: Applying | Object Localization | 10
Object Counting | 10
Spatial Relationship Understanding | 10
Professional Graph Understanding | 10
Medical Image Understanding | 10
Image Captioning | 10
Dense Captioning | 10
Level 4: Analyzing | Natural Relation Understanding | 10
Structuralized Image Understanding | 10
Attribute Comparison | 10
Difference Finding | 10
Event Cause Reasoning | 10
Social Relation Reasoning | 10
Identity Reasoning | 10
Function Reasoning | 10
Physical Property Reasoning | 10
Visual Math Reasoning | 10
Action Prediction | 10
Trend Prediction | 10
Level 5: Evaluation | Image Quality Evaluation | 10
Damage Evaluation | 10
Fake Image Detection | 10
Ethical Problem Detection | 10
Level 6: Creation | Coding Capability with Vision | 10
Visual Storytelling | 10

###  2.2 Protocol to data creation

We have recruited six volunteers.222All of whom are undergraduates, graduate
students, or research assistants at a university with an all-English
curriculum Each person is responsible for annotating a subclass. During the
annotation process, volunteers are asked to collect data that is aligned with
the following dimensions:

  * •

Data leakage prevention To prevent data leakage, annotators should prioritize
using contemporary images rather than those that might be widely available in
common datasets.

  * •

License-friendly data Utilize publicly licensed data, preferably sourced from
social networks with favorable sharing agreements, like Twitter, or data that
has been personally photographed by the annotators and is copyrighted.

  * •

Data clarity The images must be clear enough to be identifiable by humans.
However, a mix of some lower-resolution images is also included, reflecting
the varied quality of data in real-world scenarios.

  * •

Impartiality For instance, topics like geopolitical issues should be excluded
to maintain a neutral and unbiased stance in our dataset. More importantly, we
do not provide standardized answers.

  * •

Encouragement for diverse formats in responses  Instructions should be crafted
to not be definitively answered with a simple ’yes’ or ’no’. For example, it
could elicit descriptive narrative segments. This is better aligned with real-
world usages, which is the core difference between existing benchmark and the
created one – expected answers are usually open and not limited to Yes-no or
multiple-choice selection.

###  2.3 Data quality control

We employ a two-step protocol to validate the data: cross review and expert
verification.

Cross review Upon completion of the data collection, the six volunteers are
required to review each other’s work. Any data that does not meet the
aforementioned criteria, especially in terms of quality, will be discarded. If
the exclusion of certain photos results in a subclass having fewer than ten
items, volunteers will have the additional task of replenishing it until each
category meets the quota and the cross-verified data is free from any issues.

Expert verification Following cross-verification, an experienced volunteer
with expertise in data evaluation will inspect each data sample individually
for quality assurance. Any low-quality images identified will be re-collected,
following a logic similar to the cross-verification process.

We believe that after two rounds of rigorous data validation, our dataset will
have reached a satisfactory level of quality.

###  2.4 Data statistics

Figure 1: Distribution of Instructions. We present the relative distribution of these recurring Instructions and their subsequent distributions. Table 2: Sample questions in MLLM-Bench. Capability Level |  Capability |  Image |  Sample Questions
---|---|---|---
Perception |  General Object Recognition |  |  Identify the objects in the image and indicate the use case of the item.
Understanding |  Scene Understanding |  |  Infer the activities that are likely to take place during the scene based on the objects present.
Applying |  Object Counting |  |  How many pears in the picture have an upright stem?
Analyzing |  Visual Math Reasoning |  |  Compute the solution to this question using a straightforward method, and illustrate the step-by-step process.
Evaluation |  Fake image detection |  |  Determine the likelihood that this photo is real, considering both the technical aspects of photography and the plausibility of the scene depicted. Provide a detailed rationale for your conclusion.
Creation |  Visual Story Telling |  |  Write a winter ballad on the solitude and muffled world under snow, reflecting life’s resilience in a monochrome setting.

MLLM-Bench is characterized by a rich diversity and complexity of
instructions, each tailored to probe a specific capability of multi-modal
large language models. These instructions challenge models to generate
responses that are both comprehensive and descriptive, engaging with the
multifaceted nature of real-world scenarios and information. To illustrate the
breadth of our instruction set, we present a word cloud visualization that
encapsulates the frequency of terms within our instructions, as shown in
Figure 4. We list one example per category in Table 2.

##  3 Benchmarking

###  3.1 Evaluation protocols

A prompt for win-tie-lose evaluation using GPT-4V Prompt: ### Evaluation by
Voting ### You are an excellent evaluator. ### Your assignment involves
providing evaluations for given responses. ### Each evaluation will consist of
*an image*, *a question*, and *two corresponding answers*. Your task is to
discern which response is superior based on the **quality of the answer** and
its alignment with the image. If you find that both responses are equally good
or bad, feel free to select a tie. There is **no obligation** to favor one
response over the other; if a decision cannot be made, a **tie would be an
optimal choice**. ### During the evaluation process, please focus exclusively
on the **semantic quality** of the answers and its **alignment with the
image**. Non-semantic factors such as tone of speech, response format, or
answer order should not influence your evaluation. The primary focus should be
on the **quality and accuracy** of the answers. ### You should ONLY output
your vote ’Answer1’, or ’Answer2’, or ’Tie’ in the last line. Figure 2:  An
example prompt. Pay attention to design a prompt that produce a well-formatted
answer for result extraction (like better, worse or equal). A prompt for
quantitative evaluation using GPT-4V Prompt: ### Evaluation by Scoring ### You
are a helpful feedback provider. ### Your task is to provide feedback on the
performance of two answers in response to the question displayed below and the
given image. ### Please rate the helpfulness, relevance, accuracy, and level
of detail of the responses. ### Each answer receives an overall score on a
scale of 1 to 10, where a higher score indicates better overall performance.
Figure 3:  An example prompt. Pay attention to design a prompt that produce a
well-formatted answer for result extraction (like better, worse or equal).
Table 3:  Using GPT-4V for pairwise Evaluation on Multi-modal LLMs.
---
Question: Map out the complex interdependencies between species in this food
web and identify any potential cascade effects if one species were to become
extinct.
Answer 1 (llava-v1.5-13b): |  Answer 2 (lvis-instruct4v-llava-7b):
In the image, there is a complex interdependent system involving a forest,
trees, rabbits, squirrels, insects (including beetles), and a bird. The food
web shows that these different species interact and play roles in the
ecosystem. For instance, rabbits and squirrels are herbivores, consuming
plants, while insects like beetles help in decomposing plant matter, and the
bird is a predator that feeds on insects and small mammals.
If one species were to become extinct, it could lead to a cascade effect where other species are affected as well. For example, if the rabbits were to become extinct, the herbivore population would decrease, impacting the plants they were consuming. This would lead to an increase in plant growth and change the availability of food for other herbivores, such as squirrels and insects. Additionally, there could be imbalances in predator-prey relationships, leading to overpopulation of certain species, and consequently, a decline in the biodiversity and ecosystem functioning. The ecosystem would need to adapt to these changes, either by altering the populations of the remaining species or by introducing new species into the area. |  In the image, there is a forest food web featuring various animals, including a bird, a fox, a rabbit, a squirrel, and a frog. The bird is perched on a tree branch, while the other animals are scattered around the forest floor. The interdependencies between these species are numerous, as they all play essential roles in maintaining the ecosystem’s balance.
For example, the bird feeds on insects, which helps control their population
and maintain a healthy environment. The fox is a predator, feeding on smaller
animals such as rabbits, squirrels, and insects, thus controlling their
populations and maintaining the balance of the food web. The rabbit and
squirrel are herbivores, feeding on grass, plants, and seeds, contributing to
the forest’s overall health. The frog, as an amphibian, is also a part of the
food web, feeding on insects and small aquatic creatures.
If one species were to become extinct, it could lead to a cascade effect on
the food web, as the loss of a key species may disrupt the balance of the
ecosystem. This could result in an overpopulation of other species, which
could then lead to a decline in the populations of those species that depend
on them for food. In turn, this could have a negative impact on the overall
health of the forest ecosystem and potentially affect other species in the
food web.
GPT-4V Judgment333The answer shown here is for demonstration purposes, it is
different from the real output in our experiment.
Answer 1 and  Answer 2 both provide a general outline of the relationships and
potential cascade effects within the food web depicted in the image. Answer 1
starts by describing the food web including a variety of species and their
roles in the ecosystem, such as herbivores (rabbits and squirrels),
decomposers (insects like beetles), and predators (birds). It then moves on to
discuss the potential cascade effects if one species, specifically the
rabbits, were to become extinct. The explanation includes the potential
increase in plant growth, changes in the availability of food for other
herbivores, imbalances in predator-prey relationships, overpopulation of
certain species, a decline in biodiversity, and the need for ecosystem
adaptation. Answer 2 also describes the forest food web, identifying the
animals present and their roles, such as the bird controlling insect
populations, the fox as a predator, and the herbivorous activities of the
rabbit and squirrel. It also acknowledges the frog’s role in this ecosystem.
The answer then hypothesizes about the potential cascade effects if a key
species were to become extinct, including overpopulation of other species, a
decline in populations of dependent species, and a negative impact on the
overall health of the forest ecosystem. Both answers are good in terms of
providing an overview of the food web’s complexity and the interdependencies
among the species. However,  Answer 1 is slightly more aligned with the image
as it specifically names the insects as beetles and discusses the role of
birds in greater detail, while  Answer 2 incorrectly identifies a frog, which
is not present in the image. Therefore, in terms of accuracy and alignment
with the image,  Answer 1 is superior.

Our evaluations are conducted following two protocols: pairwise voting and
pairwise scoring. For pairwise voting, we provide a judge with one question
and two answers from two LLMs, and ask the judge to choose between which
answer is better (tie as the third option). For pairwise scoring, we ask a
judge to score the two answers respectively on a scale of 1 1̃0 and output the
two scores. The prompts for these two methods are detailed in Figure 2 and
Figure 3 respectively. Since we have multiple models to compare, we use an
anchor answer in each evaluated sample. Specifically for each protocol, we
choose answers from GPT-4V and LLaVA-v1.5-Vicuna-13B as anchors, yielding four
settings (for each protocol and anchor). Table 3 illustrates an example of
pairwise voting. For pairwise voting, we compute the number of win/tie/lose of
a benchmarked model over an anchor model. For pairwise scoring, we first sum
up the scores for the benchmarked and anchor model, then report the ratios of
the two scores. A strong benchmark model is expected to have a large number of
wins in pairwise voting, and a high score ratio in pairwise scoring. To avoid
positional bias (Wang et al., 2023a)444Though this paper investigate the
positional bias in text-only evaluation, we later show that such bias exists
in our evaluation as well., we shuffle the position of each paired sample for
all settings.

###  3.2 MLLMs for evaluation

The table provides a summary of various language and vision models, with
details about their parameters, open-source status, model architecture
components, and whether they are trainable. See baselines in Table 4 . Some
key points are:

GPT-4V is mentioned but without detailed specifications provided. CogVLM-Chat
has 17.6 billion parameters, utilizes EVAV2-CLIP-E visual adapter, and
Vicuna-7B-v1.5 base language model but is not trainable. Several models, such
as LLaVA-v1.5-13B, BLIP2-Flan-T5-XL, and InstructBLIP-Vicuna-13B, range from 4
billion to 14 billion parameters and incorporate various combinations of
visual adapters and base language models, none of which are trainable. Qwen-
VL-Chat, mPLUG-Owl2-LLaMA2-7B, SEED-LLaMA, and MiniGPT-v2 are models with
parameters ranging from 7.8 to 9.6 billion, all of which are trainable. The
IDEFICS-9b-instruct and Fuyu-8b models have around 9 billion parameters and
use different approaches for their visual components but do not specify their
trainability. LVIS-Instruct4v-LLaVA-7b, with 7 billion parameters, features a
CLIP-ViT-L visual component and Vicuna-7B-v1.5 base language model but is not
trainable.

Table 4: Model cards in our benchmark. “/” means the item remains confidential, or we are not able to know from their paper or technical report. For better visual clarity, we use their abbreviations in all subsequent tables.  Models | # Params | Open- | Model Architecture
---|---|---|---
sourced | Visual Adapter | Base LLM
GPT-4V | / | no | / | /
CogVLM-Chat (Wang et al., 2023b) | 17.6B | yes | EVAV2-CLIP-E | Vicuna-7B-v1.5
LLaVA-v1.5-13B (Liu et al., 2023c) | 13B | CLIP-ViT-L | vicuna-13B-v1.5
InstructBLIP-Vicuna-13B (Dai et al., 2023) | 14B | ViT+Q-Former | Vicuna-13B
Qwen-VL-Chat (Bai et al., 2023a) | 9.6B | ViT-bigG | Qwen-7B
mPLUG-Owl2-LLaMA2-7B (Ye et al., 2023) | 8B | ViT-L | LLaMA2-7B
SEED-LLaMA (Ge et al., 2023) | 13B | Multiple | LLaMA2-13B
kosmos-2-patch14-224 (Peng et al., 2023) | 1.7B | / | Magneto
IDEFICS-9B-instruct (Laurençon et al., 2023) | 9B | OpenCLIP | LLaMA
Fuyu-8B (Bavishi et al., 2023) | 9.4B | Linear | Persimmon
MiniGPT-v2 (Chen et al., 2023b) | 7.8B | EVA | LLAMA2-7B
LVIS-Instruct4v-LLaVA-7b (Wang et al., 2023c) | 7B | CLIP-ViT-L | Vicuna-7B-v1.5

###  3.3 Evaluation Results

Table 5 and Table 6 show results for pairwise voting using GPT-4V and LLaVA as
anchors, respectively. From Table 5, it is evident that the powerful
proprietary model GPT-4V significantly outperforms the others. Even the best-
performing LLaVA-V1.5 only secures 51 wins over GPT-4V out of 420 questions.
Notably, GPT-4V achieves a higher win rate across all capabilities, with a
particularly large gap in Analyzing and Perception capabilities compared to
other models.

In contrast, in Table 6, we used LLaVA-v1.5, the relatively superior model
from Table 5, as an anchor to compare with other models. This shift to a less
dominant anchor yields more balanced win rates and accentuates inter-model
performance disparities. In this context, Qwen-VL-Chat outperforms LVIS with a
higher win rate (116 vs 75), indicating significant variances in capabilities.
These findings suggest the utility of selecting a moderately capable model as
an anchor for more nuanced comparative assessments of model capabilities.

Table 5: Number of wins/ties/loses for each model over GPT-4V on each level by Direct Voting. Models are sorted by total number of wins over GPT-4V in descending order. Answers of GPT-4V are used as anchors. Models | Perception | Understanding | Applying | Analyzing | Evaluation | Creation |  $\sum$ wins
---|---|---|---|---|---|---|---
LLaVA-v1.5 | 5/15/50 | 10/39/51 | 14/18/38 | 6/41/53 | 10/12/18 | 6/19/15 | 51
LVIS | 5/18/47 | 11/33/56 | 10/16/44 | 9/31/60 | 8/15/17 | 5/20/15 | 48
mPLUG-Owl2 | 3/12/55 | 12/31/57 | 12/9/49 | 5/34/61 | 8/9/23 | 5/18/17 | 48
CogVLM-Chat | 6/15/49 | 11/31/58 | 6/21/43 | 6/28/66 | 7/16/17 | 6/12/22 | 42
Qwen-VL-Chat | 7/15/48 | 13/33/54 | 7/27/36 | 4/43/53 | 8/16/16 | 2/22/16 | 41
MiniGPT-v2 | 3/14/53 | 9/29/62 | 3/22/45 | 5/28/67 | 7/17/16 | 4/18/18 | 31
InstructBLIP | 2/12/56 | 10/19/71 | 7/9/54 | 3/24/73 | 5/9/26 | 1/15/24 | 28
Fuyu-8B | 3/7/60 | 9/13/78 | 3/5/62 | 1/15/84 | 6/9/25 | 1/9/30 | 23
IDEFICS-9B | 2/13/55 | 9/16/75 | 4/16/50 | 3/23/74 | 3/17/20 | 2/16/22 | 23
SEED-LLaMA | 4/9/57 | 2/21/77 | 5/18/47 | 7/22/71 | 2/17/21 | 3/10/27 | 23
kosmos2 | 3/7/60 | 8/14/78 | 4/10/56 | 4/17/79 | 3/12/25 | 0/8/32 | 22
BLIP2 | 0/4/66 | 2/8/90 | 2/6/62 | 2/5/93 | 2/6/32 | 1/7/32 | 9
Table 6: Number of wins/ties/loses for each model over LLaVA-v1.5 on each level by Direct Voting. Models are sorted by total number of wins over LLaVA-v1.5 in descending order. Answers of LLaVA-v1.5 are used as anchors. Models | Perception | Understanding | Applying | Analyzing | Evaluation | Creation |  $\sum$ wins
---|---|---|---|---|---|---|---
Qwen-VL-Chat | 26/28/16 | 23/60/17 | 27/28/15 | 27/57/16 | 7/25/8 | 6/30/4 | 116
CogVLM-Chat | 19/31/20 | 19/58/23 | 14/33/23 | 16/53/31 | 6/30/4 | 4/28/8 | 78
LVIS | 20/29/21 | 13/69/18 | 17/37/16 | 15/72/13 | 4/31/5 | 6/25/9 | 75
mPLUG-Owl2 | 12/36/22 | 18/60/22 | 8/38/24 | 12/63/25 | 5/28/7 | 8/28/4 | 63
InstructBLIP | 11/22/37 | 10/43/47 | 12/21/37 | 6/53/41 | 3/26/11 | 3/15/22 | 45
IDEFICS-9B | 5/32/33 | 6/58/36 | 12/29/29 | 10/48/42 | 4/23/13 | 1/25/14 | 38
kosmos2 | 3/15/52 | 11/34/55 | 6/19/45 | 10/32/58 | 3/18/19 | 2/12/26 | 35
SEED-LLaMA | 9/18/43 | 6/44/50 | 9/27/34 | 6/43/51 | 4/19/17 | 1/22/17 | 35
Fuyu-8B | 5/17/48 | 7/49/44 | 9/15/46 | 4/39/57 | 2/17/21 | 3/12/25 | 30
MiniGPT-v2 | 8/23/39 | 5/42/53 | 7/24/39 | 3/53/44 | 2/23/15 | 2/25/13 | 27
BLIP2 | 1/6/63 | 5/12/83 | 4/8/58 | 4/14/82 | 1/5/34 | 0/5/35 | 15

Table 7 and Table 8 present results for pairwise scoring using GPT-4V and
LLaVA as anchors, respectively. In contrast to the prior-mentioned pairwise
voting approach, pairwise scoring reveals a narrower variance between GPT-4V
and other models, as evidenced in Table 7. Notably, LLaVA-v1.5 scores at 71%
of GPT-4V’s rate, despite a significantly lower winning rate. This indicates
that GPT-4V also gave moderate scores to other models. However, this also
leads to closer scores among the models. Nevertheless, their ranking is
similar to that in Table 5 for the pairwise voting, which shows the
consistency of GPT-4V’s scoring.

As shown in Table 8, after switching to LLaVA-v1.5 as the anchor, Qwen-VL-Chat
achieved the best result, similar to pairwise voting. It can be observed that
after adopting the scoring method, changing anchors has little impact on the
ranking of models, with only IDEFICS-9B and MiniGPT-v2 switching places (their
scores were very close). This finding indicates that scoring voting offers a
more reliable assessment of model performance, irrespective of the chosen
anchor.

Table 7: Averaged score ratio on each level. Models are sorted by overall averaged score ratios in descending order. Answers of GPT-4V are used as anchors. Model | Perception | Understanding | Applying | Analyzing | Evaluation | Creation | Avg
---|---|---|---|---|---|---|---
LLaVA-v1.5 | 0.63 | 0.77 | 0.65 | 0.69 | 0.83 | 0.83 | 0.71
Qwen-VL-Chat | 0.65 | 0.77 | 0.68 | 0.61 | 0.83 | 0.80 | 0.70
LVIS | 0.61 | 0.75 | 0.65 | 0.63 | 0.82 | 0.77 | 0.69
mPLUG-Owl2 | 0.58 | 0.73 | 0.61 | 0.61 | 0.78 | 0.80 | 0.67
CogVLM-Chat | 0.59 | 0.74 | 0.62 | 0.59 | 0.78 | 0.72 | 0.66
IDEFICS-9B | 0.34 | 0.58 | 0.49 | 0.50 | 0.57 | 0.63 | 0.53
MiniGPT-v2 | 0.44 | 0.54 | 0.44 | 0.50 | 0.65 | 0.71 | 0.52
InstructBLIP | 0.45 | 0.57 | 0.37 | 0.43 | 0.57 | 0.39 | 0.47
Fuyu-8B | 0.39 | 0.55 | 0.33 | 0.38 | 0.52 | 0.42 | 0.43
SEED-LLaMA | 0.39 | 0.43 | 0.42 | 0.40 | 0.48 | 0.51 | 0.43
kosmos-2 | 0.38 | 0.53 | 0.41 | 0.38 | 0.43 | 0.36 | 0.42
BLIP-2 | 0.24 | 0.24 | 0.24 | 0.24 | 0.29 | 0.19 | 0.24
Table 8: Averaged score ratio on each level. Models are sorted by overall averaged score ratios in descending order. Answers of LLaVA-v1.5 are used as anchors. Model | Perception | Understanding | Applying | Analyzing | Evaluation | Creation | Avg
---|---|---|---|---|---|---|---
Qwen-VL-Chat | 1.05 | 1.04 | 1.02 | 0.95 | 0.96 | 0.96 | 1.0
LVIS | 0.97 | 0.99 | 0.93 | 0.94 | 0.97 | 0.96 | 0.96
CogVLM-Chat | 0.92 | 0.96 | 0.95 | 0.88 | 0.9 | 0.86 | 0.92
mPLUG-Owl2 | 0.92 | 0.95 | 0.89 | 0.87 | 0.84 | 1.01 | 0.91
MiniGPT-v2 | 0.62 | 0.71 | 0.69 | 0.73 | 0.67 | 0.81 | 0.70
IDEFICS-9B | 0.72 | 0.7 | 0.69 | 0.67 | 0.65 | 0.73 | 0.69
InstructBLIP | 0.69 | 0.72 | 0.54 | 0.59 | 0.66 | 0.46 | 0.62
Fuyu-8B | 0.56 | 0.68 | 0.51 | 0.54 | 0.67 | 0.51 | 0.58
SEED-LLaMA | 0.61 | 0.57 | 0.63 | 0.54 | 0.6 | 0.56 | 0.58
kosmos-2 | 0.53 | 0.68 | 0.54 | 0.53 | 0.47 | 0.41 | 0.55
BLIP-2 | 0.32 | 0.32 | 0.32 | 0.31 | 0.29 | 0.21 | 0.31

To show the validity of our evaluation, we also report the pairwise
correlation of between rankings obtained on our four settings and rankings on
SEEDBench (Li et al., 2023c). As shown in Table 9, results obtained from the
four settings have a minimum pairwise correlation of 0.74, indicating a strong
ranking correlation between them, which proves the validity of our evaluation
protocols and the legitimacy of using anchors in evaluation. In contrast, the
correlations of our results and results from SEEDBench are relatively low,
which may be due to their difference in evaluation protocols. SEEDBench
consists of 14K multiple-choice questions. For each sample, it compares the
next-token-prediction loss and select the option with the minimum loss as the
model output. However, this evaluation protocol is disadvantageous to models
that tend to output detailed or verbose answers because such models may not
output the options in a first few tokens. Our benchmark and evaluation
protocols instead provides another perspective of evaluating model
performances, complementing the existing benchmarks for MLLMs.

Table 9: Pairwise Spearman correlations between our results of different settings and SEEDBench. “Vote” and “Score” represent pairwise voting and pairwise scoring. “4V” and “LLaVA” are the anchors used for comparison. | Vote-4V | Vote-LLaVA | Score-4V | Score-LLaVA | SEEDBench
---|---|---|---|---|---
Vote-4V | 1 | 0.74 | 0.85 | 0.82 | 0.23
Vote-LLaVA | 0.74 | 1 | 0.81 | 0.79 | 0.05
Score-4V | 0.85 | 0.81 | 1 | 0.98 | 0.6
Score-LLaVA | 0.82 | 0.79 | 0.98 | 1 | 0.2
SEEDBench | 0.23 | 0.05 | 0.6 | 0.2 | 1

###  3.4 Bias Analysis

In this section, we use the results of using LLaVA-v1.5 as anchors to analyze
different biases presented in the evaluation, to mitigate the potential
influence brought by quality differences between answers.

####  3.4.1 Positional Bias

Table 10: Positional bias at answer-pair level. Answer 1 stands for the first answer seen by GPT-4V, answer 2 stands for the second answer seen by GPT-4V Vote 1 | Vote 2 | Count | Answer-pair level Positional Bias | Percentage
---|---|---|---|---
Answer 1 | Answer 2 | 1610 | No bias | 65.1%
Tie | Tie | 2494
Answer 1 | Answer 1 | 117 | Answer 1 | 26.1%
Answer 1 | Tie | 1525
Answer 2 | Answer 2 | 67 | Answer 2 | 8.8%
Answer 2 | Tie | 487

In our experiment, we evaluate each pair of answers twice, swapping the order
of the answers to reduce the impact of positional bias on the experimental
results, and analyze the positional bias of GPT-4V at the answer-pair level.
We conduct an analysis to assess the presence of positional bias in GPT-4V at
the level of answer-pair. The criteria used to determine the existence of
positional bias at this level are outlined in Table 10. It is important to
note that the sequence in which votes 1 and 2 are cast is irrelevant to the
determination of bias.

Table 10 presents our findings. It suggests that GPT-4V has a propensity to
favor the first answer in the sequence during the evaluation process at the
answer-pair level. Ideally, an unbiased evaluator would consistently choose
the same answer, irrespective of the order in which the responses are
presented, indicating a lack of positional bias across all answer pairs.
However, our results show that GPT-4V exhibits no bias in 65.9% of the cases.
Yet, in 27.3% of the instances, it leans towards the first answer, and in 6.8%
of the cases, it favors the second answer. Based on this observation, it is
advised to conduct multiple evaluations by swapping the order of the answers
to mitigate the positional bias.

####  3.4.2 Length Bias

Figure 4: Length Bias

We analyze the length bias of GPT-4-V at the vote level555Length is calculated
using the tiktoken library.. We mark the votes for short answers as 0, Tie as
0.5, and the votes for long answers as 1, and then calculate the weighted
average of all votes. Ideally, GPT4-V should not show a preference for length,
so the calculated average should be around 0.5 and does not change with the
increase in length difference.

From Figure 4, we can see that the average preference of GPT4-V is slightly
higher than 0.5 when the length difference is relatively small (smaller than
200), that is, it slightly prefers longer answers. As the length difference
increases, the preference for length gradually decreases. One of the reasons
for this situation is that the answers with a length greater than LLaVA-v1.5
mainly come from MiniGPT-v2 and SEED-LLaMA, and the capabilities of these two
models are slightly inferior to LLaVA in the evaluation. That is, the length
bias is coupled with the difference in model answer quality, and the
difference in model answer quality may mask the potential length bias. The
same situation also applies to cases with small length differences. Overall,
the evaluation of GPT-4V did not show a significant length bias, and the
slight length bias shown is likely to come from the difference in the quality
of the answers themselves.

##  4 Related Work

##### Large Language Models

Recently, the research on LLMs has emerged as a prominent research direction
(Zhao et al., 2023) and different LLMs trained on massive text data are
presented and/or released by both academia and industry, e.g., GPT-3 (Brown et
al., 2020), BLOOM (Scao et al., 2022), PaLM (Chowdhery et al., 2022),
Galactica (Taylor et al., 2022), LLaMA (Touvron et al., 2023) and Falcon
(Almazrouei et al., 2023). According to the research problems, existing
studies can be classified into the following categories: (i) Scaling laws
(Kaplan et al., 2020; Hoffmann et al., 2022); (ii) Emergent ability (Brown et
al., 2020; Wei et al., 2022a); (iii) Prompting (Wei et al., 2022b); (iv)
Training (Rasley et al., 2020; Shoeybi et al., 2019); (v) Alignment tuning
(Stiennon et al., 2020; Ouyang et al., 2022); (vi) Tools manipulation (Schick
et al., 2023).

##### Multi-modal Large Language Models

Existing studies in Multi-modal Large Language Models (MLLMs) aim to bridge
vision encoders and large language models, where the former plays a role of
visual perception and the latter is responsible for cognition. Flamingo and
BLIP-2 (Li et al., 2023b) are two early studies to show the possibility of
bridging vision encoders to large language models, where they demonstrate the
impressive ability of zero-shot visual question answering. Follow-up studies
like MiniGPT-4 and LLaVA (Liu et al., 2023d) mainly explore and improve
instruction-following abilities of MLLMs. Most recently, a variety of MLLMs
(e.g., InstructBLIP (Dai et al., 2023), mPLUG-Owl (Ye et al., 2023), KOSMOS-2
(Peng et al., 2023), Shikra (Chen et al., 2023a), Qwen-VL (Bai et al., 2023a),
and CogVLM (Wang et al., 2023b)) is proposed to enhance MLLMs from different
aspects (e.g., visual encoding, vision-language alignment, and visual
grounding).

##### Evaluation for Multi-modal Large Language Models

The powerful and comprehensive capabilities of multi-modal large language
models make their assessment extremely challenging. Current benchmarks
primarily fall into several categories: (1) Multiple-choice questions
(evaluating the perception and cognition abilities of MLLMs): MME (Fu et al.,
2023), SEED (Li et al., 2023d), and TouchStone (Bai et al., 2023b); (2)
Chatbot Arena type (user-based evaluation of different capabilities): LVLM-
eHub (Xu et al., 2023), VisIT-Bench (Bitton et al., 2023); (3) Hallucination
assessment (focusing on a key issue currently faced by MLLMs -
hallucinations): POPE (Li et al., 2023a) and HallusionBench (Liu et al.,
2023b). The works most related to us are (i) MMBench (Liu et al., 2023a) and
MM-Vet (Yu et al., 2023), using GPT-4 as the evaluator to quantitatively
measure the performance of different MLLMs; (ii) a concurrent work (Zhang et
al., 2023), using GPT-4V to evaluate the text-to-image generation task.

##  5 Limitation

While MLLM-Bench strives to assess vision-language models (MLLMs)
comprehensively, it cannot encapsulate the full diversity of real-world multi-
modal interactions, acknowledging the challenge of simulating the
unpredictable variety of real-life tasks. The benchmark’s design, which seeks
to mirror human user experience, may introduce subjectivity, potentially
affecting the consistency and generalizability of results.

The qualitative nature of benchmarks, especially in creative or ethical
scenarios, also complicates the evaluation process. Ethical considerations,
despite being integrated into the framework, cannot capture the full spectrum
of societal implications, with the fluidity of AI ethics demanding continuous
updates to the benchmark.

Acknowledging these limitations is vital for the nuanced application and
interpretation of MLLM-Bench results, and underscores the necessity for
iterative refinement to enhance the tool’s relevance and evaluative accuracy.

##  6  Future Work

Human evaluation. We will also conduct human evaluation to validate how much
GPT-4v evaluator is aligned with human experts.

Meta evaluators on the GPT-4V evaluator We will design some Meta evaluation
criterion for the GPT-4V evaluator. For example, we could define three
hypothesis, namely, Paired Bootstrap Hypothesis, Transitive Hypothesis, and
Human Alignment Hypothesis. The Paired Bootstrap Hypothesis suggests that
effectiveness of an evaluator can be statistically evaluated by comparing
different versions of the evaluator through a process known as
’bootstrapping.’ This involves repeatedly resampling data to assess the
stability of the evaluators’ performance. The Transitive Hypothesis suggests
that if a high-performing model exceeds a moderately performing one in
capabilities, and this moderate model, in turn, outperforms a less capable,
lower-tier model, then it is expected that the high-performing model will also
surpass the lower-tier model in performance. Lastly, the Human Alignment
Hypothesis focuses on aligning GPT-4V judgment with human judgment, especially
in human ethical standards and expectations, ensuring that the AI remains a
beneficial and ethical tool for users. These hypotheses collectively
contribute to a comprehensive framework for assessing and improving the
effectiveness and reliability of evolving AI technologies.

##  7 Conclusion

In conclusion, this paper represents a groundbreaking stride in the evolution
of multi-modal large language models (MLLMs), addressing critical gaps in the
current evaluation frameworks and methodologies. By introducing the first
systematic evaluation for open vision-language tasks, we establish a new
benchmark for assessing the capabilities of MLLMs in a broader, more realistic
context. Our comprehensive taxonomy, with a specific focus on ethical
considerations, paves the way for a more responsible and conscientious
approach to AI development. The MLLM-Bench, our novel benchmark dataset, is a
testament to our commitment to advancing the field towards more nuanced and
user-centric AI systems. These contributions not only enhance our
understanding of MLLMs but also guide future research and development,
ensuring that these advanced systems are evaluated on parameters that truly
reflect their complexity and real-world applicability. As we continue to
explore the vast potential of AI, our work underscores the importance of
ethical, comprehensive, and context-aware evaluation in realizing the full
promise of MLLMs.

## Acknowledgement

Contribution of this paper is shown as below:

Component | Contributors
---|---
Data collection and checking |  Wentao Ge, Shuo Yan, Wenya Xie, Chenghao Zhu, Ziyue Lin, and others
Baseline and benchmark |  Guiming Chen and Junying Chen
GPT-4V evaluation | Shunian Chen
UI and website |  Zhiyi Zhang and Jianquan Li
Overall design |  Zhihong Chen and Benyou Wang
Table 11: Contribution of each author

## References

  * (1)
  * Almazrouei et al. (2023) Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Merouane Debbah, Etienne Goffinet, Daniel Heslow, Julien Launay, Quentin Malartic, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo. 2023.  Falcon-40B: an open large language model with state-of-the-art performance.  (2023).
  * Bai et al. (2023a) Jinze Bai, Shuai Bai, Shusheng Yang, Shijie Wang, Sinan Tan, Peng Wang, Junyang Lin, Chang Zhou, and Jingren Zhou. 2023a.  Qwen-VL: A Versatile Vision-Language Model for Understanding, Localization, Text Reading, and Beyond.  arXiv:2308.12966 [cs.CV]
  * Bai et al. (2023b) Shuai Bai, Shusheng Yang, Jinze Bai, Peng Wang, Xingxuan Zhang, Junyang Lin, Xinggang Wang, Chang Zhou, and Jingren Zhou. 2023b.  Touchstone: Evaluating vision-language models by language models.  _arXiv preprint arXiv:2308.16890_ (2023).
  * Bavishi et al. (2023) Rohan Bavishi, Erich Elsen, Curtis Hawthorne, Maxwell Nye, Augustus Odena, Arushi Somani, and Sağnak Taşırlar. 2023.  Introducing our Multimodal Models.  https://www.adept.ai/blog/fuyu-8b
  * Bitton et al. (2023) Yonatan Bitton, Hritik Bansal, Jack Hessel, Rulin Shao, Wanrong Zhu, Anas Awadalla, Josh Gardner, Rohan Taori, and Ludwig Schimdt. 2023.  Visit-bench: A benchmark for vision-language instruction following inspired by real-world use.  _arXiv preprint arXiv:2308.06595_ (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. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Chen et al. (2023b) Jun Chen, Deyao Zhu, Xiaoqian Shen, Xiang Li, Zechun Liu, Pengchuan Zhang, Raghuraman Krishnamoorthi, Vikas Chandra, Yunyang Xiong, and Mohamed Elhoseiny. 2023b.  MiniGPT-v2: large language model as a unified interface for vision-language multi-task learning.  arXiv:2310.09478 [cs.CV]
  * Chen et al. (2023a) Keqin Chen, Zhao Zhang, Weili Zeng, Richong Zhang, Feng Zhu, and Rui Zhao. 2023a.  Shikra: Unleashing Multimodal LLM’s Referential Dialogue Magic.  _arXiv preprint arXiv:2306.15195_ (2023).
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. 2022\.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ (2022).
  * 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. 2023.  InstructBLIP: Towards General-purpose Vision-Language Models with Instruction Tuning.  arXiv:2305.06500 [cs.CV]
  * Fu et al. (2023) Chaoyou Fu, Peixian Chen, Yunhang Shen, Yulei Qin, Mengdan Zhang, Xu Lin, Zhenyu Qiu, Wei Lin, Jinrui Yang, Xiawu Zheng, et al. 2023\.  MME: A Comprehensive Evaluation Benchmark for Multimodal Large Language Models.  _arXiv preprint arXiv:2306.13394_ (2023).
  * Ge et al. (2023) Yuying Ge, Sijie Zhao, Ziyun Zeng, Yixiao Ge, Chen Li, Xintao Wang, and Ying Shan. 2023.  Making LLaMA SEE and Draw with SEED Tokenizer.  arXiv:2310.01218 [cs.CV]
  * Hoffmann et al. (2022) Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. 2022\.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ (2022).
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ (2020).
  * Krathwohl (2002) David R Krathwohl. 2002.  A revision of Bloom’s taxonomy: An overview.  _Theory into practice_ 41, 4 (2002), 212–218.
  * Laurençon et al. (2023) Hugo Laurençon, Lucile Saulnier, Léo Tronchon, Stas Bekman, Amanpreet Singh, Anton Lozhkov, Thomas Wang, Siddharth Karamcheti, Alexander M. Rush, Douwe Kiela, Matthieu Cord, and Victor Sanh. 2023.  OBELICS: An Open Web-Scale Filtered Dataset of Interleaved Image-Text Documents.  arXiv:2306.16527 [cs.IR]
  * Li et al. (2023c) Bohao Li, Rui Wang, Guangzhi Wang, Yuying Ge, Yixiao Ge, and Ying Shan. 2023c.  SEED-Bench: Benchmarking Multimodal LLMs with Generative Comprehension.  arXiv:2307.16125 [cs.CL]
  * Li et al. (2023d) Bohao Li, Rui Wang, Guangzhi Wang, Yuying Ge, Yixiao Ge, and Ying Shan. 2023d.  Seed-bench: Benchmarking multimodal llms with generative comprehension.  _arXiv preprint arXiv:2307.16125_ (2023).
  * Li et al. (2023b) Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. 2023b.  BLIP-2: Bootstrapping Language-Image Pre-training with Frozen Image Encoders and Large Language Models.  arXiv:2301.12597 [cs.CV]
  * Li et al. (2023a) Yifan Li, Yifan Du, Kun Zhou, Jinpeng Wang, Wayne Xin Zhao, and Ji-Rong Wen. 2023a.  Evaluating object hallucination in large vision-language models.  _arXiv preprint arXiv:2305.10355_ (2023).
  * Liu et al. (2023b) Fuxiao Liu, Tianrui Guan, Zongxia Li, Lichang Chen, Yaser Yacoob, Dinesh Manocha, and Tianyi Zhou. 2023b.  Hallusionbench: You see what you think? or you think what you see? an image-context reasoning benchmark challenging for gpt-4v (ision), llava-1.5, and other multi-modality models.  _arXiv preprint arXiv:2310.14566_ (2023).
  * Liu et al. (2023c) Haotian Liu, Chunyuan Li, Yuheng Li, and Yong Jae Lee. 2023c.  Improved Baselines with Visual Instruction Tuning.  arXiv:2310.03744 [cs.CV]
  * Liu et al. (2023d) Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. 2023d.  Visual Instruction Tuning.
  * Liu et al. (2023a) Yuan Liu, Haodong Duan, Yuanhan Zhang, Bo Li, Songyang Zhang, Wangbo Zhao, Yike Yuan, Jiaqi Wang, Conghui He, Ziwei Liu, et al. 2023a.  MMBench: Is Your Multi-modal Model an All-around Player?  _arXiv preprint arXiv:2307.06281_ (2023).
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ 35 (2022), 27730–27744.
  * Peng et al. (2023) Zhiliang Peng, Wenhui Wang, Li Dong, Yaru Hao, Shaohan Huang, Shuming Ma, and Furu Wei. 2023.  Kosmos-2: Grounding Multimodal Large Language Models to the World.  arXiv:2306.14824 [cs.CL]
  * Rasley et al. (2020) Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. 2020.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters. In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 3505–3506.
  * Scao et al. (2022) Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022\.  Bloom: A 176b-parameter open-access multilingual language model.  _arXiv preprint arXiv:2211.05100_ (2022).
  * Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023.  Toolformer: Language models can teach themselves to use tools.  _arXiv preprint arXiv:2302.04761_ (2023).
  * Shoeybi et al. (2019) Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. 2019.  Megatron-lm: Training multi-billion parameter language models using model parallelism.  _arXiv preprint arXiv:1909.08053_ (2019).
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ 33 (2020), 3008–3021.
  * Taylor et al. (2022) Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. 2022.  Galactica: A large language model for science.  _arXiv preprint arXiv:2211.09085_ (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. 2023\.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ (2023).
  * Wang et al. (2023c) Junke Wang, Lingchen Meng, Zejia Weng, Bo He, Zuxuan Wu, and Yu-Gang Jiang. 2023c.  To See is to Believe: Prompting GPT-4V for Better Visual Instruction Tuning.  arXiv:2311.07574 [cs.CV]
  * Wang et al. (2023a) Peiyi Wang, Lei Li, Liang Chen, Zefan Cai, Dawei Zhu, Binghuai Lin, Yunbo Cao, Qi Liu, Tianyu Liu, and Zhifang Sui. 2023a.  Large Language Models are not Fair Evaluators.  arXiv:2305.17926 [cs.CL]
  * Wang et al. (2023b) 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. 2023b.  CogVLM: Visual Expert for Pretrained Language Models.  arXiv:2311.03079 [cs.CV]
  * Wei et al. (2022a) Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. 2022a.  Emergent abilities of large language models.  _arXiv preprint arXiv:2206.07682_ (2022).
  * Wei et al. (2022b) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022b.  Chain of thought prompting elicits reasoning in large language models.  _arXiv preprint arXiv:2201.11903_ (2022).
  * Xu et al. (2023) Peng Xu, Wenqi Shao, Kaipeng Zhang, Peng Gao, Shuo Liu, Meng Lei, Fanqing Meng, Siyuan Huang, Yu Qiao, and Ping Luo. 2023.  Lvlm-ehub: A comprehensive evaluation benchmark for large vision-language models.  _arXiv preprint arXiv:2306.09265_ (2023).
  * Ye et al. (2023) Qinghao Ye, Haiyang Xu, Jiabo Ye, Ming Yan, Anwen Hu, Haowei Liu, Qi Qian, Ji Zhang, Fei Huang, and Jingren Zhou. 2023.  mPLUG-Owl2: Revolutionizing Multi-modal Large Language Model with Modality Collaboration.  arXiv:2311.04257 [cs.CL]
  * Yu et al. (2023) Weihao Yu, Zhengyuan Yang, Linjie Li, Jianfeng Wang, Kevin Lin, Zicheng Liu, Xinchao Wang, and Lijuan Wang. 2023.  Mm-vet: Evaluating large multimodal models for integrated capabilities.  _arXiv preprint arXiv:2308.02490_ (2023).
  * Zhang et al. (2023) Xinlu Zhang, Yujie Lu, Weizhi Wang, An Yan, Jun Yan, Lianke Qin, Heng Wang, Xifeng Yan, William Yang Wang, and Linda Ruth Petzold. 2023.  GPT-4V (ision) as a Generalist Evaluator for Vision-Language Tasks.  _arXiv preprint arXiv:2311.01361_ (2023).
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023\.  A survey of large language models.  _arXiv preprint arXiv:2303.18223_ (2023).
  * Zheng et al. (2023) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. P Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023.  Judging LLM-as-a-judge with MT-Bench and Chatbot Arena.  arXiv:2306.05685 [cs.CL]