# Perfect Consistent Hashing

Matthew Sackman
<EMAIL_ADDRESS>
###### Abstract

Consistent Hashing functions are widely used for load balancing across a
variety of applications. However, the original presentation and typical
implementations of Consistent Hashing rely on randomised allocation of hash
codes to keys which results in a flawed and approximately-uniform allocation
of keys to hash codes. We analyse the desired properties and present an
algorithm that perfectly achieves them without resorting to any random
distributions. The algorithm is simple and adds to our understanding of what
is necessary to create a consistent hash function.

##  1 Introduction

A hash function is a function that deterministically and uniformly maps keys
of unbounded size to members of a finite set of hash codes. It is
deterministic in that in the absence of changes to the set of hash codes, the
same key is always mapped to the same hash code. It is uniform in that each
hash code is equally likely to be generated. If $h_{C}(\kappa)$ is the hash
function $h$ with the set of hash codes $C$, applied to the key $\kappa$, then
$\forall\sigma\in C,\forall\kappa.\>p(h_{C}(\kappa)=\sigma)=1/|C|$.

A typical simple hash function is to treat the key as a natural number and
then to take its modulus by the number of hash codes, $|C|$. This result is
then used as an index into $C$, which is ordered in some way and treated as
mapping naturals to hash codes. If $C[x]$ represents the result of indexing
this mapping $C$ by $x$ then this simple hash function can be written as
$h_{C}(\kappa)=C[\kappa\mod|C|]$. One problem with such a simple hash function
is that when a new hash code is added to $C$ or an existing hash code removed,
the existing mapping between keys and hash codes is non-minimally altered. If
$C\subset C^{\prime}$ and $|C^{\prime}|=|C|+1$ (so $|C|$ and $|C^{\prime}|$
are relatively prime) then we can define the set of keys which do not get
remapped as

$\\{\kappa\mid\delta\in\\{0\dots(|C|-1)\\},\,\iota\in\mathbb{N},\,\kappa=\delta+\iota\cdot|C|\cdot|C^{\prime}|\\}$

Thus in any set of keys of size $|C|\cdot|C^{\prime}|$, there will be on
average only $|C|$ keys for which $h_{C}(\kappa)=h_{C^{\prime}}(\kappa)$, so
the probability of a key not being remapped to a different hash code is
$1/|C^{\prime}|$, or $p(h_{C}(\kappa)=h_{C^{\prime}}(\kappa))=1/|C^{\prime}|$.
Clearly, as the set of hash codes grows large, the probability of a key
mapping to the same hash code after the addition or removal of a new hash code
approaches zero.

In many applications, this high likelihood of keys being remapped when $C$ is
altered is unacceptable; so we require a different hash function. For example,
in the case of a distributed cache, a hash function might be being used to
determine which node contains a requested object, with the key provided to the
hash function being an object identifier (e.g. a URL), and the hash codes
being node identifiers (e.g. I.P. addresses). In this scenario, when the set
of nodes (i.e. hash codes) is altered, we want to minimise the number of
objects that must move between nodes in order to satisfy the new mapping.
Consistent Hashing [KLL97] provides exactly this: in addition to the usual
determinism and uniformity properties of hash functions, it also requires that
when a hash code is added or removed, only the minimal number of keys are
remapped to maintain uniformity. In the case of addition, the minimal number
of keys is simply the number of keys that must be mapped to the new hash code;
therefore it is not permitted to remap keys between existing hash codes.

This remapping requirement in combination with the uniformity requirement
reveals further details of how the hash function should behave. For the
uniformity property to be maintained after a hash code is added, each existing
hash code should give up an equal proportion of their keys to become the keys
of the new hash code. Once again with $C\subset C^{\prime}$ and
$|C^{\prime}|=|C|+1$, the uniformity property gives us $\forall\sigma\in
C,\forall\kappa.\>p(h_{C}(\kappa)=\sigma)=1/|C|$ and $\forall\sigma\in
C^{\prime},\forall\kappa.\>p(h_{C^{\prime}}(\kappa)=\sigma)=1/|C^{\prime}|$.
We can now relate these by

$\forall\sigma\in C,\forall\kappa.\>h_{C}(\kappa)=\sigma\implies
p(h_{C^{\prime}}(\kappa)=\sigma)=\frac{|C|}{|C^{\prime}|}$

i.e. if $h_{C}(\kappa)$ yields hash code $\sigma$ for key $\kappa$, then the
probability of $h_{C^{\prime}}(\kappa)$ yielding the same $\sigma$ for the
same $\kappa$ is $|C|/|C^{\prime}|$. The probability of
$h_{C^{\prime}}(\kappa)$ yielding a hash code from $C$ is $|C|/|C^{\prime}|$,
leaving $1/|C^{\prime}|$ for the new hash code, as required. Note that there
is no possibility of keys being moved between existing hash codes: each hash
code loses only as many keys as are required to be donated to the new hash
code; all remaining keys stay with their existing hash code thus the remapping
property is satisfied. The inverse specifies the conditions of a hash code
being removed: to maintain the uniformity property, the removed hash code’s
keys must be equally distributed amongst the remaining hash codes, and to
maintain the remapping property, no keys are remapped except those that were
mapped to the now departed hash code. It is worth observing that the
requirement that only $1/|C^{\prime}|$ of the keys are remapped is the
complement of that achieved by our unsuitable simple hash function in which
only $1/|C^{\prime}|$ keys are not remapped!

The introduction of the properties of a Consistent Hash also presented an
algorithm [KLL97], which we refer to as the classic algorithm. Whilst this
algorithm has been implemented in many different programming languages and
used in many scenarios, it has several flaws which we explore in this paper.
We then present a new algorithm which precisely achieves the desired
properties and solves the flaws identified in the classic algorithm.

##  2 Classic Algorithm

The classic algorithm places hash codes at random points around a circle. Keys
to the hash function are interpreted as points on the circle, and the hash
function identifies the next hash code point around the circle, fig:circle-
simple. In this way, we can think of each hash code as owning different
segments of the circle. It is usual to apply a standard hash function to keys
in order to limit the keys to the range of the circle and ensure uniform
distribution of keys around the circle. Whilst the hash codes are placed at
random points around the circle, the points may still be found
deterministically, for example generated by applying a standard hash function
to the hash code names themselves.

$\delta$$\gamma$$\beta$$\epsilon$$\alpha$ $\kappa$ Figure 1: A circle divided
into five segments by five randomly placed hash code points, and the search
for the next hash code point from the key $\kappa$

Because each discrete point around the circle can only be occupied by a single
hash code, addition of hash codes is not commutative. This is not an essential
property, but it does have an effect on the size of the state that must be
maintained for the hash function. Addition is not commutative because of the
possibility that two hash codes both try to occupy the same point around the
circle. When such a collision occurs, a number of solutions are possible, but
one of the two hash codes must win the particular point otherwise the
remapping property will be violated (commutativity could be achieved if
neither hash code wins the contested point, but that would result in keys
being transferred from the first hash code added (the initial winner), to a
different existing hash code, which is illegal). If hash code points around
the circle are randomly generated, then the state maintained must include all
those points (when a collision occurs, a fresh random point is generated for
the new hash code). If the hash code points are generated deterministically by
applying a standard hash function to the hash code identifiers, then the state
must maintain the order in which hash codes were added and removed so that the
points can be correctly reestablished including the outcome of collisions
(when a collision occurs, a number of options are available, such as hashing
the concatenation of the new hash code name and an attempt-number).

This classic algorithm achieves the remapping and deterministic properties but
fails to guarantee the uniformity property. Whenever a hash code is added, its
determined point around the circle splits an existing segment, transferring a
portion of the keys from that segment to the new hash code. No other segments
around the circle are altered so all other keys remain mapped to their
existing hash codes, fig:circle-simple-add. Similarly, when a hash code is
removed, the disappearance of its point around the circle merges its segment
with the next segment. Again, no other points around the circle are altered,
so no keys are remapped between other, surviving, hash codes. As a result, the
remapping property is achieved. The determinism property is immediate,
provided state is maintained appropriately in light of changes to $C$ as
discussed previously.

$\delta$$\delta$$\gamma$$\gamma$$\beta$$\beta$$\alpha$ $\alpha$
$\displaystyle\overset{+\epsilon}{\Longrightarrow}$ Figure 2: Modifying an
existing circle by the addition (left to right), or removal (right to left) of
a point for the hash code $\epsilon$

Uniformity however is at best approximated. The location of hash code points
is random, so with just two hash codes, it is very unlikely for each hash
code’s points to be $180^{\circ}$ apart: just $1/R$ where $R$ is the range of
the circle. So the likelihood of the segments being of equal size and thus
uniformity achieved, is very low. If one traverses around the perimeter of the
circle at constant speed, encountering a hash code point (and entering a new
segment) can be modelled by a Poisson process. The interval between such
encounters (i.e. the segment length) is then an exponential distribution
[NR05, XXX09]. The extreme left-skew of this distribution demonstrates how
exceedingly unlikely it is to achieve uniformity. For example, a circle
divided by 10 points, one for each of 10 hash codes, will have a mean arc
length of $36^{\circ}$, but a median arc length of just $25^{\circ}$.

To address this, the classic algorithm uses several points for each hash code,
fig:circle-multi-point. This changes the distribution of segment lengths from
exponential to Erlang; an Erlang-$k$ distribution is the sum of $k$
independent exponential distributions. If $k$ points are used per hash code
then the distribution of lengths forms an Erlang-$k$ distribution (the second
parameter to the Erlang distribution, $\lambda$, is in this case $k\cdot|C|$).
As $k$ rises, so the skew in the distribution of lengths is reduced. However,
the ratios of smallest and largest segment lengths to the mean length remains
high: with $k$ as high as $|C|$, the mean length will be around $1.1$ of the
smallest length, and the largest length will also be around $1.1$ of the mean
length. With $k=4\cdot|C|$, these ratios fall to around $1.06$, and with
$k=8\cdot|C|$, they only fall to around $1.04$.

$\beta$$\delta$$\beta$$\epsilon$$\gamma$$\epsilon$$\alpha$$\delta$$\delta$$\gamma$$\beta$$\gamma$$\alpha$$\epsilon$$\alpha$
$\kappa$ Figure 3: A circle of segments for five hash codes, each with three
random points ($k=3$), being indexed by the key $\kappa$

In some scenarios it may well be acceptable to have one hash code receive
$8\%$ more keys than another. Note though that this imbalance is not reduced
by adding additional hash codes, indeed quite the opposite: the lower $k/|C|$
falls, the greater the spread. To reduce the imbalance, the value of $k$ needs
to be determined as a multiple of the maximum number of hash codes. Thus if
the set of hash codes is normally relatively small and only under certain
conditions are many more hash codes added, then the circle will generally
contain many more points than strictly necessary, due to the high $k$. In
scenarios with large numbers of hash codes, the probability of points
colliding rises and you may even run out of points: with 20,000 hash codes
each with 200,000 points, over $93\%$ of 32-bit integers are used up, thus
switching to a 64-bit circle perimeter range would become necessary.

As the classical algorithm is typically implemented by holding the points in a
binary tree, the depth of the tree determines the look-up cost. Assuming any
other hash functions being used to prepare the key are
$\operatorname{O}\bigl{(}1\bigr{)}$, we should have an overall cost of
$\operatorname{O}\bigl{(}\log_{2}(k\cdot|C|)\bigr{)}$ which simplifies to
$\operatorname{O}\bigl{(}\log_{2}(|C|)\bigr{)}$ as $k$ is a constant. Some
implementations claim worst cost of $\operatorname{O}\bigl{(}1\bigr{)}$
because of the finite upper limit on the number of points around the circle,
and thus a limit on the depth of the corresponding tree, but that’s arguably a
consequence of limitations of the implementation, and average cost (rather
than worst-case) is still $\operatorname{O}\bigl{(}\log_{2}(|C|)\bigr{)}$.
Techniques do exist to reduce this for the average case, but they increase
memory footprint and make adding and removing hash codes more expensive.
Obviously, this does not invalidate such approaches, but we will not consider
them further here.

The memory footprint of so many points is also worth considering: if an
implementation holds the points in some sort of tree, 20,000 hash codes each
with 200,000 points would result in a tree of depth 32, with 8.6 billion nodes
(number of nodes in a tree is found by $2^{d+1}-1$ where $d$ is the tree
depth). Assuming each node carries two 64-bit pointers to its children and a
64-bit value, we have a minimum of 192 bits per node, or 24 bytes. Such a tree
then works out at a minimum memory cost of around 200 GB, or around 10 MB per
hash code.

##  3 Analysing Requirements

The large number of replicas in the classic algorithm is not only necessary to
address the exponential distribution of segment lengths (and thus approximate
uniformity given a static number of hash codes) but also to maintain
approximate uniformity in light of changes to the set of hash codes, $C$. We
now consider how to algorithmically place points around the circle for each
hash code such that we precisely achieve and maintain uniformity, and do not
rely on any random distributions.

As stated previously, when a hash code is added, it should inherit an equal
number of keys from each of the existing hash codes, and when it leaves, it
should equally distribute its keys to the surviving hash codes. In the classic
algorithm, to achieve this with the removal of a hash code requires that that
hash code must have at least as many segments as there are remaining hash
codes so that each of its own segments might be followed by a segment of a
each of the other hash codes.111In the classic algorithm, due to the random
placement of hash code points, a high number of replicas, $k$, is also
necessary to have confidence the required permutations are achieved, but as we
shall show, as the number of hash codes increases, the multiple of $|C|$ to
define $k$ must itself rise.

For example, with three hash codes, $\alpha$, $\beta$, $\gamma$, we require
that $\alpha$ must have at least two segments: one followed by $\beta$ and the
other followed by $\gamma$. The same holds for the other two hash codes, so we
must accommodate all possible pairs around the circle: $(\alpha,\beta)$,
$(\beta,\alpha)$, $(\alpha,\gamma)$, $(\gamma,\alpha)$, $(\beta,\gamma)$,
$(\gamma,\beta)$. One solution would be
$[\alpha,\beta,\alpha,\gamma,\beta,\gamma]$, with each segment being of equal
length (fig:circle-perfect-3), though there are a number of equivalent
solutions. Note how the last element of each pair forms the first element of a
different pair, and thus there are six segments of the circle corresponding to
the six pairs. This is a minimal solution: the required pairings cannot be
achieved with fewer points around the circle. If two hash codes leave, by
elimination, the one remaining hash code will inherit all the keys and
therefore we do not need to worry about the distribution of a single key’s
points around the circle. This explains why with three hash codes, we concern
ourselves with pairs of hash codes, and not triples.

$\alpha$$\beta$$\alpha$$\gamma$$\beta$$\gamma$ $\kappa$
$\displaystyle\overset{-\gamma}{\Longrightarrow}$ Figure 4: A circle
containing all possible pairs of three hash codes ($\alpha$, $\beta$,
$\gamma$) as neighbouring segments of equal size (left), being modified by the
removal of a hash code $\gamma$ (right), both being indexed by the key
$\kappa$

With four hash codes, $\alpha$, $\beta$, $\gamma$, $\delta$, if two hash codes
leave, we still require uniformity of distribution of keys to the two
remaining hash codes. This is no longer about incorporating every possible
pair of hash codes around the circle, it is now about incorporating every
possible triple of hash codes: pairs will maintain uniformity in case of one
removal, triples are required for two removals. In general, for $|C|$ hash
codes, every permutation of length $|C|-1$ must exist around the circle in
such a way that all but the first element (i.e. the last $|C|-2$ elements) of
each permutation forms the first elements of the next permutation. This is
known as a universal cycle for the $|C|-1$ permutations of $C$, and is a well
studied problem [Jac93].

Permutations of length one less than the number of available symbols are known
as shorthand permutations as the remaining symbol is implicit. For example
with the symbols $\alpha$, $\beta$, $\gamma$, $\delta$, the permutation
$[\gamma,\delta,\beta]$ can be considered shorthand for
$[\gamma,\delta,\beta,\alpha]$. Thus we can also say that we require a
universal cycle of the shorthand permutations of $C$. In general, it is always
possible to find a universal cycle of shorthand permutations, and efficient
algorithms exist to directly construct such permutations [RW10, HRW10].

Such a cycle will work as desired in light of multiple removals of hash codes.
As every hash code in the cycle is followed an equal number of times by each
of the other hash codes, removal of any hash code will equally distribute its
keys amongst the remaining hash codes, who’s segments will grow in size. For
example, with four hash codes, $\alpha$, $\beta$, $\gamma$, $\delta$, a
universal cycle of shorthand permutations is:

$[\alpha,\beta,\gamma,\alpha,\beta,\delta,\alpha,\gamma,\beta,\alpha,\gamma,\delta,\beta,\alpha,\delta,\gamma,\beta,\delta,\gamma,\alpha,\delta,\beta,\gamma,\delta]$

Uniformity is achieved: each hash code has six entries and thus six segments
of equal length around the circle, fig:circle-perfect-4. If we remove the hash
code $\gamma$ then we are left with:

$[\alpha,\beta,\alpha,\alpha,\beta,\delta,\alpha,\beta,\beta,\alpha,\delta,\delta,\beta,\alpha,\delta,\beta,\beta,\delta,\alpha,\alpha,\delta,\beta,\delta,\delta]$

In our notation here, removal is represented by substitution of the removed
hash code with the next surviving hash code. As each element is a segment of
the circle of equal length, this makes it easier to check uniformity; each
remaining hash code now has eight entries, and thus uniformity has been
maintained (fig:circle-perfect-4-remove).

$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\delta$$\alpha$$\gamma$$\beta$$\alpha$$\gamma$$\delta$$\beta$$\alpha$$\delta$$\gamma$$\beta$$\delta$$\gamma$$\alpha$$\delta$$\beta$$\gamma$$\delta$
Figure 5: A circle constructed from the 24 elements of a universal cycle of
the shorthand permutations of four hash codes, $\alpha$, $\beta$, $\gamma$ and
$\delta$

Note how there are two $\alpha,\alpha$ pairs, two $\beta,\beta$ pairs, and two
$\delta,\delta$ created by the removal of the six $\gamma$ segments. Each of
these themselves are still followed by each of the remaining hash codes: one
$\alpha,\alpha$ pair is followed by a $\beta$, and one by a $\delta$;
similarly for the other pairs. Thus multiple removals of hash codes still
result in uniformity of distribution of keys. This is not a surprising result
given the nature of the permutations: the very reason why there are two
instances of $\gamma$ followed by $\alpha$ (thus forming the two
$\alpha,\alpha$ pairs upon removal of $\gamma$) is so that they can be
followed by each of the remaining hash codes: $\beta$ and $\delta$ in this
case.

If we remove another hash code, for example $\delta$, then we are now left
with:

$[\alpha,\beta,\alpha,\alpha,\beta,\alpha,\alpha,\beta,\beta,\alpha,\beta,\beta,\beta,\alpha,\beta,\beta,\beta,\alpha,\alpha,\alpha,\beta,\beta,\alpha,\alpha]$

Again, uniformity has been maintained: we have now 12 $\alpha$s and 12
$\beta$s (fig:circle-perfect-4-remove).

Figure 6: The circle of fig:circle-perfect-4 with the hash codes $\gamma$
removed (left), and $\gamma$ and $\delta$ removed (right)

Whilst it is clear that removal will maintain uniformity when the circle is
constructed from a universal cycle of shorthand permutations of $C$, it is
less clear how to construct such circles additively: given the cycle for
$\alpha$, $\beta$, $\gamma$, $\delta$ given in fig:circle-perfect-4, how do
you modify it to incorporate a new hash code, $\epsilon$, whilst achieving the
remapping property? Equivalently, given the circle diagram of the remaining
$\alpha$s and $\beta$s on the right in fig:circle-perfect-4-remove, it is far
from clear how to construct this, and thus create the necessary spaces for
later hash codes to fill. In the classic algorithm, the circle exists to
achieve the remapping property both for addition and removal of hash codes.
However, with the positions of each hash code point being precisely determined
by the universal cycle, the circle only now serves to provide the remapping
property upon removal of a hash code, not the addition: addition can no longer
be achieved by splitting existing segments. Happily, our new algorithm manages
to achieve the uniformity and remapping properties precisely, without needing
to address this problem.

However, first let us examine the size of these cycles. Because all but one
hash code from each permutation overlaps with the next hash code, each
permutation contributes one hash code to the length of the cycle. The number
of shorthand permutations of $C$ is the same as the number of $|C|$-length
permutations of $C$, which is $|C|!$. Thus with just 12 hash codes, we have a
cycle length of 479,001,600. Whilst this is less than $2^{32}$, 13 hash codes
would be create a cycle length greater than $2^{32}$. This not only impacts
the representation of the circle (and its memory footprint if the entire
circle must be constructed and maintained), but also affects the key: in
essence what this means is that a 32-bit key can only choose between up to 12
hash codes. A 512-bit key can only choose between up to 98 hash codes. This
has implications for consistent hashing generally: with large numbers of hash
codes and short keys, it is impossible to achieve perfect uniformity, and an
approximate solution in such scenarios cannot be bettered. To achieve perfect
uniformity and the remapping property in light of removals, every permutation
needs an equal chance of being selected. The use of shorthand permutations is
only necessary to be able to construct universal cycles out of the segments
around the circle.

This factorial of $|C|$ also impacts performance. As discussed earlier, the
classic algorithm is typically implemented using a binary tree to hold the
points around the circle. The depth of the tree and thus the average cost of
look-up is now $\operatorname{O}\bigl{(}\log_{2}(|C|!)\bigr{)}$ which is worse
than $\operatorname{O}\bigl{(}|C|\bigr{)}$ (we present an intuitive proof of
this later). However, with even small numbers of hash codes, the factorial
results in so many nodes that it is unwise to maintain the whole tree in
memory. Instead the nodes of the tree would need to be constructed by some
means as the tree was traversed. This would likely result in a very different
look-up cost.

The factorial also explains why the multiple of $|C|$ to define the number of
replicas, $k$, in the classic algorithm must rise itself as $|C|$ rises: to
approximate maintaining uniformity in light of removals, the classic algorithm
must have sufficient points per hash code to approximate a universal cycle of
shorthand permutations of $C$. Thus $k$ should also be a multiple of the
factorial of $|C|$ to have confidence of being able to approximate such a
cycle by random placement of hash code points.

##  4 New algorithm

In the previous section, the universal cycle served to position the hash codes
around the circle such that uniformity was achieved, and that in the event of
removal of hash codes, uniformity would be maintained. It can be considered
that what the hash function is actually returning is not a single hash code,
but a permutation of the hash codes, with removed hash codes filtered out.

Our new algorithm explicitly returns a permutation of all the hash codes. The
interpretation of a permutation as a result of the hash function is not fixed,
but for our purposes, we read $[\alpha,\beta]$ as first try $\alpha$, then try
$\beta$. Every permutation is equally probable, which achieves both the
uniformity requirement and the remapping requirement in light of removal of
hash codes (i.e. as before, filtering out removed hash codes from the
resulting permutation will maintain uniformity). Each permutation exists as a
leaf of a tree, but this is not a binary tree: whilst the root node has two
children, all other nodes have one more child than does their parent,
fig:tree-2-add. We then subdivide the key to navigate through the tree. The
remapping requirement means that if we use part of the key to decide between
different orderings of particular hash codes in the resulting permutation then
we must forevermore use that same part of the key to make that same decision.

$[\alpha]$$[\alpha,\beta]$0$[\beta,\alpha]$1
$\displaystyle\overset{+\gamma}{\Longrightarrow}$
Figure 7: A tree of the permutations of two hash codes (left), being extended
by an additional layer for a third hash code (right)

With one hash code, the result is trivial. With two hash codes, $\alpha$ and
$\beta$, we want the answer to be the permutation $[\alpha,\beta]$ as often as
the permutation $[\beta,\alpha]$. To choose between these, we use the key
($\kappa$) modulus two. With three hash codes, $\alpha$, $\beta$ and $\gamma$,
we now have six permutations. As we previously used $\kappa\bmod 2$ to choose
between $\alpha$ before $\beta$ versus $\beta$ before $\alpha$, we must
continue to do so, and must then discard that part of the key (by dividing by
two). At the next layer of the tree we have two 3-way choices, each refining
the previous choice by adding in the new hash code $\gamma$. Thus we use the
remaining key modulus three to make this choice. The tree at the right of
fig:tree-2-add is shown as a table in fig:tree-3-table.

$\kappa\bmod 6$ | $\frac{\kappa}{2}\bmod 3$ | $\kappa\bmod 2$ | Permutation
---|---|---|---
0 | 0 | 0 | $[\alpha,\beta,\gamma]$
1 | 0 | 1 | $[\beta,\alpha,\gamma]$
2 | 1 | 0 | $[\alpha,\gamma,\beta]$
3 | 1 | 1 | $[\beta,\gamma,\alpha]$
4 | 2 | 0 | $[\gamma,\alpha,\beta]$
5 | 2 | 1 | $[\gamma,\beta,\alpha]$
Figure 8: The tree on the right of fig:tree-2-add as a table for ease of
reading

In general, each layer of the tree adds a new hash code. A node of any
particular layer can be seen to receive a permutation from its parent, and to
add its new hash code in every possible position within that permutation; each
node has a child for each of the possible positions at which its own hash code
can be inserted. But no modifications are made to the ordering of existing
hash codes within the permutation which a node receives, and it is this that
achieves the remapping property. Note that in the tree of fig:tree-2-add, the
index of each branch indicates the distance from the end of the existing
permutation at which the new hash code is inserted. This is an arbitrary
choice: any strategy for determining the position of the new hash code within
the received permutation is acceptable (and can even vary per layer), provided
the strategy is both deterministic and uniform.

If we consider all keys modulus two (i.e. the values $0$ and $1$), then with
just the hash codes $\alpha$ and $\beta$, we see $0$ (and thus all even keys)
maps to $[\alpha,\beta]$, and $1$ (and thus all odd keys) maps to
$[\beta,\alpha]$. With the hash codes $\alpha$, $\beta$ and $\gamma$, all keys
modulus six (i.e. the values $0$ to $5$), and if we just consider the first
element of each permutation returned, then we see $0$ and $2$ are mapped to
$\alpha$ (as they were previously without the $\gamma$ hash code), $1$ and $3$
are mapped to $\beta$ (as they were previously without the $\gamma$ hash
code), and $4$ and $5$ are mapped to $\gamma$. Thus we have ensured that in
the transition from two to three hash codes, we only remap keys to the new
value ($4$ and $5$ going to $\gamma$), and we have taken an equal (and
minimal) number of keys from each of the existing hash codes (i.e. $4$ from
$\alpha$ and $5$ from $\beta$), resulting in an equal distribution of keys to
values. Uniformity has been maintained and the remapping property achieved.

We must also check what happens when a hash code is removed. If the hash code
removed is the most recently added, then we can simply discard the lowest
layer of the tree and return to the earlier configuration. Otherwise, we
continue with the existing tree, but must filter out the removed hash code
from the resulting permutation (depending on the implementation, this
filtering could be done as the resulting permutation is constructed). With the
hash codes $\alpha$, $\beta$ and $\gamma$, there are two permutations which
start with $\alpha$: $[\alpha,\beta,\gamma]$ and $[\alpha,\gamma,\beta]$. If
the $\alpha$ hash code is removed, we see that its keys are equally
redistributed and uniformity maintained: we have one permutation where the
initial $\alpha$ is followed by a $\beta$ and one where it is followed by a
$\gamma$. As in the previous section, this is simply a consequence of using
permutations. It should be noted that in common with the classic algorithm,
our algorithm makes addition of hash codes non-commutative: each hash code is
accommodated by individual layers of the tree (and thus is navigated by
specific sections of the key), and so the order in which the hash codes were
added matters.

If after $\alpha$ has been removed we add the hash code $\delta$, then
$\delta$ can simply take the space created by the removal of $\alpha$. The
remapping and uniformity properties are precisely achieved. We now can define
exactly the state that our algorithm requires: a list containing current hash
codes interspersed with a marker used to indicate free slots caused by hash
codes being removed. The list will only grow when a hash code is added and
there are no free slots, and will shrink whenever the hash code at the end of
the list is removed (thus you should never have a free slot marker at the end
of the list). Barring substitutions of a new hash code for a free slot marker,
the list elements will be in the order in which the hash codes were added,
corresponding to the layers of the tree.

The average cost of look-up is now $\operatorname{O}\bigl{(}|C|\bigr{)}$, as
each hash code adds a layer to the tree. Whilst we have the same number of
leaves as in the previous section (i.e. $|C|!$), we no longer use a binary
tree: each node has one more child than does its parent. As a child is
determined by indexing a node’s list of children by the modulus of part of the
key, the selection of the child remains $\operatorname{O}\bigl{(}1\bigr{)}$
despite nodes having increasing numbers of children as depth increases.
Consequently, we have one division, one modulus, and one indexing operation
per layer of the tree. Assuming each of these are
$\operatorname{O}\bigl{(}1\bigr{)}$, the average cost of reaching a leaf, and
thus a look-up, is $\operatorname{O}\bigl{(}|C|\bigr{)}$. This then is our
intuitive proof that $\operatorname{O}\bigl{(}\log_{2}(|C|!)\bigr{)}$ is worse
than $\operatorname{O}\bigl{(}|C|\bigr{)}$: the binary tree from the previous
section and our non-binary tree from this section both contain the same number
of leaves, but the binary tree is limited to two children per node and so must
use more nodes than our non-binary tree which has an additional child per node
per generation. Consequently, for the same number of leaves, the binary tree
must be deeper than our non-binary tree, thus the cost of navigating to a leaf
must be higher. Therefore $\operatorname{O}\bigl{(}\log_{2}(|C|!)\bigr{)}$ is
worse than $\operatorname{O}\bigl{(}|C|\bigr{)}$.

As we have the same number of leaf nodes as in the previous section, caused by
the factorial of $|C|$, we have the same implications in the relationship
between key bit length (or entropy) and the permissible number of hash codes.
Thus whilst our algorithm does indeed achieve perfect uniformity and satisfies
the remapping property, the cost is in the factorial relationship between the
number of hash codes, and the range of the key. Equally, the number of nodes
in our tree is given by $\sum\nolimits_{i=1}^{|C|}{i!}$. Whilst this is fewer
nodes than the binary tree for the same number of leaves (indeed, the number
of nodes of our tree tends towards half the number of nodes of the binary
tree), nevertheless the number of nodes makes it impractical to maintain such
a tree in memory, so once again we must construct the permutation dynamically
as we descend the tree. Such an implementation is given in fig:code:new. The
performance cost will change however: each layer of the tree will insert its
hash code into the resulting permutation. The most efficient mechanism for
doing this will be to build the permutation in a tree, for which insertions
will on average $\operatorname{O}\bigl{(}\log_{2}(n)\bigr{)}$ where $n$ is the
number of values in the tree. As we know we will need to do $|C|$ insertions
and the average number of values in the tree will be $|C|/2$, we have a total
cost of all the insertions of
$\operatorname{O}\bigl{(}|C|\cdot\log_{2}(|C|/2)\bigr{)}$. Whilst this is a
worse average cost than navigating a pre-constructed tree (which was
$\operatorname{O}\bigl{(}|C|\bigr{)}$), the memory savings are significant.

consistent_hash(HashCodes, Key) -$>$
consistent_hash([], Key, HashCodes, 1).

consistent_hash(Permutation, _Key, [], _CurrentBase) -$>$
Permutation;
consistent_hash(Permutation, Key, [HC | HashCodes], CurrentBase) -$>$
Pos = Key rem CurrentBase,
Permutation1 = insert_at(Permutation, HC, Pos),
consistent_hash(Permutation1, Key div CurrentBase, HashCodes,
CurrentBase \+ 1).

insert_at(List, E, Nth) -$>$
insert_at(E, Nth, [], List).

insert_at(E, 0, HeadRev, Tail) -$>$
lists:reverse(HeadRev, [E | Tail]);
insert_at(E, N, HeadRev, [Elem | Tail]) -$>$
insert_at(E, N \- 1, [Elem | HeadRev], Tail).

Figure 9: An implementation in Erlang of our new algorithm

In the code listing of fig:code:new, as we subdivide the key we build up the
permutation in a list rather than a tree. Whilst this will be less efficient
than using a tree, for small values of $|C|$ the difference will be slight and
the code simplified (as ever, beware large constant overheads!). Note that
there is no marker provided to indicate removed hash codes; instead these can
be filtered out from the resulting permutation as necessary. In this
implementation, the position calculated by each layer of the tree is the
distance from the start of the received permutation at which to insert the new
hash code. Thus this will produce permutations in a different order to that of
fig:tree-3-table but the properties still hold, and the code is simplified.

If there is no need to return a permutation, and instead only the first
element of the permutation is required as a result then further
simplifications can be made to the code by avoiding construction of the
permutation, and so reducing the average complexity back to
$\operatorname{O}\bigl{(}|C|\bigr{)}$. We keep track of the current first
element of the permutation, and update it at each layer if we find the
position of new hash code is 0, thus replacing the old first element. This is
shown in fig:code:new-one-result.

consistent_hash([HC | HashCodes], Key) -$>$
consistent_hash(HC, Key, HashCodes, 2).

consistent_hash(Result, _Key, [], _CurrentBase) -$>$
Result;
consistent_hash(Result, Key, [HC | HashCodes], CurrentBase) -$>$
Result1 = case Key rem CurrentBase of
0 -$>$ HC;
_ -$>$ Result
end,
consistent_hash(Result1, Key div CurrentBase, HashCodes,
CurrentBase \+ 1).

Figure 10: Simplifications achieved by only requiring a single result

However, in this simpler scenario, we need to be much more careful about
removed hash codes: we cannot permit the algorithm to return the marker for a
removed hash code as the result, as we have no way of knowing what would have
been next in the permutation. Instead, we must cope with the removed-hash-code
marker directly in the implementation itself. This is trickier as we need to
consider many different combinations of each layer updating the current
result. fig:code:new-one-result-marker shows an example implementation. In the
input list of hash codes, the Erlang atom undefined is used to indicate the
removed-hash-code marker.

consistent_hash(HashCodes, Key) -$>$
consistent_hash(undefined, Key, HashCodes, 1).

consistent_hash({HC, _Pos}, _Key, [], _CurrentBase) -$>$
HC;
consistent_hash({candidate, HC, _PosC, _PosI}, _Key, [], _CurrentBase) -$>$
HC;
consistent_hash(Result, Key, [HC | HashCodes], CurrentBase) -$>$
PosN = Key rem CurrentBase,
Result1 =
case {Result, HC} of
{undefined, undefined} -$>$
Result;
{undefined, _} -$>$
{HC, PosN};
{{candidate, _HCC, PosC, _PosI}, _} when PosN $>$ PosC -$>$
Result;
{{candidate, HCC, PosC, PosI}, undefined} when PosN =$<$ PosI -$>$
{candidate, HCC, PosC \+ 1, PosN};
{{candidate, HCC, PosC, PosI}, undefined} -$>$
{candidate, HCC, PosC \+ 1, PosI};
{{candidate, _HCC, _PosC, PosI}, _} when PosN =$<$ PosI -$>$
{HC, PosN};
{{candidate, _HCC, _PosC, PosI}, _} -$>$
{candidate, HC, PosN, PosI};
{{_HCC, PosC}, _} when PosN $>$ PosC -$>$
Result;
{{HCC, PosC}, undefined} -$>$
{candidate, HCC, PosC \+ 1, PosN};
{{_HCC, _PosC}, _} -$>$
{HC, PosN}
end,
consistent_hash(Result1, Key div CurrentBase, HashCodes,
CurrentBase \+ 1).

Figure 11: Improving fig:code:new-one-result by accommodating removed hash
codes

Whilst there are ten combinations of existing-result and new hash code to
consider in this code, the algorithmic complexity is no worse, and so when
just a single result is required, the cost of the function is
$\operatorname{O}\bigl{(}|C|\bigr{)}$. Whilst this is still worse than for the
classic algorithm, for the smaller sizes of $|C|$ that our algorithm is best
suited for, this is unlikely to preclude use of our algorithm. Equally, in
cases where there is a very high churn rate of hash codes being added and
removed, the lower cost of these operations in our algorithm may favour it
over the classic algorithm.

##  5 Evaluation

As mentioned earlier, whilst our algorithm achieves perfect uniformity along
with the remapping and determinism properties, the trade-off is higher average
cost ($\operatorname{O}\bigl{(}|C|\cdot\log_{2}(|C|)\bigr{)}$ (or
$\operatorname{O}\bigl{(}|C|\bigr{)}$ if a single element is returned rather
than an entire permutation) versus
$\operatorname{O}\bigl{(}\log_{2}(|C|)\bigr{)}$ for the classic algorithm) and
rapid consumption of the entropy of the key. If more hash codes are used than
can be supported by the entropy of the key then the consequence is certain
permutations will never be reached and thus certain hash codes may never
appear at the front of resulting permutations. However, our algorithm can
dynamically construct the result as the key is consumed, thus avoiding
building the entire tree, saving memory. This is possible because the contents
of each child node are determined by just the remainder of the key and the
node’s hash code itself. By contrast in the classic algorithm, the contents of
each child node are determined randomly by the placement of hash code points.
This means at a minimum, all the points of every hash code must be held in
memory for the classic algorithm.

Returning a permutation rather than a single result is in practice very
useful, and has several interpretations depending on the application. For
example, if the application is a distributed key-value store then the
permutation would indicate an ordering of machines to try: in the case of a
read operation you might choose to issue reads to the first few machines from
the permutation, either to check that they all have the same value, or because
due to transient load imbalances, one may reply more quickly than the others.
For a write operation, the client application may well indicate that it only
considers a write completed once it has been synchronously written to at least
$N$ machines; again, the first $N$ elements from the permutation indicate
exactly to which machines to issue synchronous writes.

In such key-value stores, it is very often the case that certain keys are much
more frequently accessed than others. This might be due to a particularly
popular URL; the effect of “being slash-dotted” or “going viral”. In these
scenarios, a single key can substantially skew loading across a cluster of
machines. Here again, returning a permutation from the consistent hash
function can be advantageous: if each element of the permutation is a
particular machine in your distributed key-value store and loading information
per machine is available, the client may well be able to filter out
particularly heavily loaded machines and still access the required information
promptly. In an eventually consistent scenario with writes as well as reads
occurring, this could result in the serving of stale data, but the trade-off
would be better load balancing and improved latencies.

Performance comparisons in general of the classic algorithm and our new
algorithm are of limited value as they will inevitably reflect both the
suitability of each algorithm to the artificial conditions of the benchmark,
and the relative amounts of effort to optimise each implementation.

##  6 Conclusion

Consistent Hashing is a widely used and important technique, applicable to
many applications. Hopefully this work provides a more detailed understanding
as to how it can be achieved and what the trade-offs involved are.

We have shown how the classic algorithm relies on random distributions to
approximately maintain the uniformity property. We then examined how, given
the way in which the circle achieves the remapping property, universal cycles
of shorthand permutations may be used to precisely achieve and maintain the
uniformity property in light of removals of hash codes but that adding new
hash codes is non-obvious. Finally, by abandoning the use of a circle, we
presented our new algorithm which also relies on permutations but makes the
addition of hash codes simple. We have discussed potential implementation
strategies and average performance of these algorithms and shown that a cost
of achieving perfect uniformity and remapping is in the factorial relationship
between the number of hash codes and the key size.

## References

  * [HRW10] Alexander Holroyd, Frank Ruskey, and Aaron Williams.  Faster generation of shorthand universal cycles for permutations.  Computing and Combinatorics, pages 1–10, 2010.
  * [Jac93] B.W. Jackson.  Universal cycles of k-subsets and k-permutations.  Discrete mathematics, 117(1-3):141–150, July 1993.
  * [KLL97] D Karger, E Lehman, and T Leighton.  Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web.  In ACM Symposium on Theory of Computing, 1997.
  * [NR05] Heiko Niedermayer and Simon Rieche.  On the Distribution of Nodes in Distributed Hash Tables.  Proc. Workshop Peer-to-Peer-Systems and Applications (KiVS), pages 193–196, 2005.
  * [RW10] Frank Ruskey and Aaron Williams.  An explicit universal cycle for the (n-1)-permutations of an n-set.  ACM Transactions on Algorithms (TALG), pages 1–15, 2010.
  * [XXX09] N Xiaouien, L Xianliomq, and Zhou Xu.  Load distributions of some classic DHTs.  J. Systems Engineering and Electronics, 20(2):400–404, 2009.


# Mini DALL·E 3: Interactive Text to Image by
Prompting Large Language Models

Zeqiang Lai 1 Xizhou Zhu 23 Jifeng Dai 23 Yu Qiao 2 Wenhai Wang 4
1Beijing Institute of Technology 2Shanghai AI Laboratory 3Tsinghua University
4CUHK
https://minidalle3.github.io/

###### Abstract

The revolution of artificial intelligence content generation has been rapidly
accelerated with the booming text-to-image (T2I) diffusion models. Within just
two years of development, it was unprecedentedly of high-quality, diversity,
and creativity that the state-of-the-art models could generate. However, a
prevalent limitation persists in the effective communication with these
popular T2I models, such as Stable Diffusion, using natural language
descriptions. This typically makes an engaging image hard to obtain without
expertise in prompt engineering with complex word compositions, magic tags,
and annotations.

Inspired by the recently released DALL·E 3– a T2I model directly built-in
ChatGPT that talks human language, we revisit the existing T2I systems
endeavoring to align human intent and introduce a new task - interactive text
to image (iT2I), where people can interact with LLM for interleaved high-
quality image generation/edit/refinement and question answering with stronger
images and text correspondences using natural language. In addressing the iT2I
problem, we present a simple approach that augments LLMs for iT2I with
prompting techniques and off-the-shelf T2I models. We evaluate our approach
for iT2I in a variety of common-used scenarios under different LLMs, _e.g_.,
ChatGPT, LLAMA, Baichuan, and InternLM. We demonstrate that our approach could
be a convenient and low-cost way to introduce the iT2I ability for any
existing LLMs and any text-to-image models without any training while bringing
little degradation on LLMs’ inherent capabilities in, _e.g_., question
answering and code generation. We hope this work could draw broader attention
and provide inspiration for boosting user experience in human-machine
interactions alongside the image quality of the next-generation T2I systems.

Figure 1:  Examples of two interactive text-to-image conversations produced by
Mini DALL·E 3. In these cases, people can ask the agent to generate images via
natural language and request an edit if the results are unsatisfactory. The
generation and editing can be completed in a multi-turn dialog with
recognition of the conservation context.

††Preliminary version. Work in Progress.

##  1 Introduction

The evolution of artificial intelligence content generation has been
significantly accelerated by the proliferation of text-to-image (T2I)
diffusion models [20, 18, 41, 43]. Within just two years of rapid development
since 2021, it was unprecedentedly of high quality, diversity, and creativity
that the state-of-the-art T2I models [39, 40, 43, 41, 4, 55, 13] could
generate. For the first time, “talk to paint” is no longer a daydream, and
complex surrealistic arts can be generated via textual descriptions, with
stronger expressive ability than previous unconditional and class conditional
image generation systems as shown in Fig. 2.

However, it is unfortunate that most of the existing T2I models, such as
Stable Diffusion [41], are still limited in understanding natural language. In
other words, people have to learn to write complex text prompts to obtain the
best results, which fit the used models but are not necessarily user-friendly
and straightforward for humans, as illustrated by Fig. 6. As a result, this
typically makes an engaging image hard to obtain without expertise in prompt
engineering with proper word compositions and sometimes weird phrase
organizations. Besides, there have been dozens of different textual and
numerical configurations in a diffusion-based T2I pipeline, such as CFG scale,
word weighting, negative prompts, and style keywords, which are also
complicated for non-professional users.

To make it easier for users to utilize T2I models, Stable Diffusion (SD) WebUI
[2] is first created to provide a user-friendly web UI to access the latest
techniques without any coding. However, a typical workflow of generating a
satisfactory image usually involves several stages, _e.g_., generation,
variation, super-resolution, _etc_. This makes the tab-based interface of SD-
WebUI somewhat awkward to use. Therefore,
ComfyUI111https://github.com/comfyanonymous/ComfyUI was designed by utilizing
a graph/nodes interface that connected different stages via nodes and edges,
which makes workflows more clear. Nevertheless, these software tools still
could not solve the problem of complicated configurations required for a
charming image. This urges the development of
Fooocus222https://github.com/lllyasviel/Fooocus – a tool with a bunch of
built-in optimizations and quality improvements. Fooocus frees users from
complex parameter-tuning, but it still requires them to write a proper and
precise text prompt for the desired images. However, this can be challenging
in some cases, such as when the required scenes are artistic conceptions
rather than specific objects, or when the users have no idea how to describe
what they want to generate, etc.

Figure 2:  The evolution of image generation systems.

Generally, it might be difficult for users to come up with the right prompts
and configurations at once, but it is much easier to tell what they want or do
not want via natural language if the first version is unsatisfactory, _e.g_.,
“Don’t be a sticker” and “Where is the dog?”, as shown in Fig. 1. Moreover, it
would be more straightforward to perform a multi-turn conversation with T2I
models to iterate the images over and over again, mimicking the communication
processes between human designers and their customers. These analyses reveal a
promising direction for building the next generation of T2I systems with a new
human-machine interface using natural language – a system that is able to
infer users’ intentions and automatically generate the proper text prompts
leveraging the reasoning abilities of large language models (LLM). This is not
only because natural language is the easiest way that everyone can master, but
also because it frees users from brainstorming sophisticated textual
descriptions and requires only simple instructions instead (see Fig. 6 for
more illustrations).

Figure 3:  Illustrations of different human-machine interfaces for T2I
systems.

Inspired by the recently released demo of DALL·E 3 [35] – a powerful T2I model
directly built-in ChatGPT that utilizes human language, we revisit existing
techniques aimed at aligning human intent in generating images and introduce a
new task called interactive text to image (iT2I). This task is featured by
several aspects, including 1) _Multi-Turn_ : users are allowed to chat with
the system (typically powered by LLMs) to progressively specify requirements,
shortcomings, and suggestions of the expected/generated images; 2)
_Consistency_ : the ability to keep identity for consistent multi-turn image
editing, series characters creation, _etc_.; 3) _Composability_ : the ability
to be composed with/built-in existing chat assistants for interleaved image
generation and (visual) question answering for seamless user experience. All
these properties make iT2I systems powerful tools for a wide range of
applications, from content generation and design to interactive storytelling
and more.

As an initial solution to address this problem, we propose a simple yet
effective approach that enhances language models for iT2I using prompting
techniques and pre-trained text-to-image models. Specifically, we prompt the
LLM to instruct it to generate an image with an intermediate textual
description enclosed by special tags. After detecting the special tags, the
description is parsed and transformed through a prompt refinement module.
Then, a pretrained T2I model is employed to generate the image. We evaluate
our approach across various common use cases and different language models
such as ChatGPT [7, 36], LLAMA [48], Baichuan [56] and InternLM [46]. Our
results demonstrate that our approach can easily enable iT2I capabilities in
any existing language model and text-to-image model without the need for
additional training. Furthermore, it has minimal impact on the language
models’ inherent abilities in question answering and code generation.

We hope this work could draw broader attention and provide inspiration for
boosting user experience in human-machine interactions alongside the image
quality of the next-generation T2I models.

##  2 Related Works

#### Text-to-Image Generation.

Text-to-image (T2I) generation is a widely-explored research area at the
intersection of computer vision and natural language processing. Notable
approaches include generative models, like Variational Autoencoders (VAE) [22,
47], Generative Adversarial Networks (GAN) [17, 21], and autoregressive models
[12], which enable image synthesis guided by textual descriptions. Recent
multimodal models like CLIP [38] and DALL·E [39] have further improved
alignment between text and generated images, while the birth and development
of diffusion models [41, 43, 4, 55, 13, 40] have pushed the boundaries of
text-image interactions.

#### Image Generation Interface.

There are a variety of different approaches for image generation and editing –
each possesses its own merits and drawbacks. The most straightforward ones are
text-based approaches where people write text prompts for either image
generations [41, 40] or image editing [6, 61]. Besides, image-based approaches
are also popular. In this case, people either provide a reference image asking
the T2I models to generate image variations [40, 59], or provide edge/depth
maps to control the image layout [34, 27, 64], or performing image translation
with a style image [1, 45], or asking generating images of a given subject
[25, 57]. To facilitate the precise control, point-based approaches [49, 31]
are widely adopted by utilizing state-of-the-art localization methods [30,
23]. Recently, drag-based approaches [11, 44, 29, 33, 37, 62, 28] are also
proposed for more interactive experience. As for UX design, there are Rich-T2I
[15] and DialogPaint [53], which share similar spirits as ours. In the
literatures of integrating T2I to LLM, there are NExT-GPT [54], GILL [24],
DreamLLM [9], SEED [16]. Although these methods also provide the capability
for interleaved text-image generation, they are not specifically designed for
iT2I mostly and are limited to image quality and multi-turn correspondence.

Figure 4:  Illustration of 6 types of interactions in interactive text-to-
image workflow.

#### Prompting LLMs.

The in-context-learning capability [7] is one of the strongest advantages of
LLMs. It enables users to freely customize LLMs for a particular task or
enhance the capabilities of LLMs by simple prompting. For example, chain-of-
thoughts [52] is the first prompting technique that enhances LLMs by asking
them to generate a series of intermediate reasoning steps. After that, there
are also a number of improved prompting techniques that leverage the heuristic
of majority voting [51], backtracking [58], and graph of thoughts [5]. In this
work, we also provide an approach to augment LLM with iT2I ability via
prompting, as it can be rapidly applied to any existing LLMs without any
training.

##  3 Interactive Text to Image

Interactive Text to Image (iT2I) aims to provide a user-friendly approach to
generate images that meet user requirements in an interactive manner. Users
can instantiate a multi-turn dialogue between humans and AI agents, where they
can communicate requirements, shortcomings, and suggestions of the generated
images or the expected ones with natural language.

###  3.1 Problem Definition

Precisely, the iT2I problem can be defined as the task of generating images
from textual descriptions in a way that the generated images closely align
with the provided text, ensuring that the generated visual content accurately
represents the textual information. There are some notable properties of iT2I
systems:

Multi-Turn refers to the ability of the system to engage in a dynamic and
iterative dialogue with the user. Unlike traditional text-to-image systems
that may generate a single image based on a static textual input, multi-turn
iT2I systems can accept multiple rounds of textual input, enabling users to
refine and specify their visual requirements through an ongoing conversation.
This property enhances the user experience and allows for more fine-grained
control over the generated images.

Consistency means that these systems can automatically determine if they
should take into account not only the current textual input but also the
previous visual context. It involves persisting the visual identity of images
in different rounds of generations. This capability enables iT2I systems to
perform consistent multi-turn image editing/refinement, produce personalized
and contextually relevant objects/characters, _etc_.

Composability relates to the ability to combine or integrate image generation
with other tasks. This means that the ability of image generation should be
modular and compatible with the inherent abilities of LLMs, allowing users to
seamlessly incorporate them to perform interleaved conservations for querying
both text and visual content.

###  3.2 Types of Instruction

As shown in Fig. 4, there are various instructions that could be found in an
iT2I system, such as generation, editing, selecting, and refinement. Different
instructions could have varying levels of complexity when it comes to
interpretation. Some instructions can be effectively addressed by leveraging
the capabilities of an LLM, such as selecting, which primarily involves
textual decision-making. However, certain instructions may necessitate a
deeper synergy between the LLM and the T2I models.

Generation refers to the process of generating entirely new images based on a
given textual description. In this context, the iT2I system creates images or
illustrations from scratch, attempting to capture the essence and details of
the provided textual input. It essentially transforms queries into neural
representations or prompts for T2I models.

Referring generation is another variant of generation, where the system
generates images that refer to or are inspired by existing objects, scenes, or
concepts mentioned in the textual input and appear in the context.

Selecting is a relatively straightforward instruction that involves choosing
or picking from a set of pre-existing or bag of generated images based on the
textual input.

Editing performs the task of modifying or refining existing images in response
to textual instructions. This may involve altering specific attributes of an
image, enhancing or diminishing certain features, or adapting the image to
match the requirements outlined in the instruction.

Refinement means to further enhance or optimize an existing image to better
align with the textual description. While editing involves making specific
modifications, refinement often involves fine-tuning the visual output to
achieve a higher level of detail, realism, or accuracy in accordance with the
provided textual guidance.

Question Answering is the inherent ability of LLMs. An iT2I system should be
able to persist the ability as much as possible, as it is crucial to provide a
coherent experience interleaving images and text for users.

###  3.3 Discussion

In the literature of image editing and multi-modal LLM, there are a number of
works that are closely related to iT2I. Most of these related works could
provide interactive interfaces. For example, InstructPix2Pix [6] and its
follow-up works [65, 63] could be repeatedly applied to a single image to
achieve multi-turn image editing. However, these interactive multi-turn
abilities only apply to image editing instructions. There are also multi-modal
LLMs [54, 24, 9, 16] that could generate response with interleaved text and
images, but most of them focus more on (visual) question answering with multi-
modal responses rather than interactive image generation. The key vision of
iT2I is to build a chat-based system that could respond to all image
generation/editing instructions in a multi-turn, consistent, and composable
manner. This is the major difference between iT2I from all previous
works/tasks.

##  4 Mini-DALLE3

In this section, we depict a blueprint of an iT2I system, which we refer to as
Mini-DALLE3. The overall architecture of Mini-DALLE3 is illustrated in Fig. 5,
and it comprises several key components: an LLM, a router, an adapter, and T2I
models. The LLM can be an existing text-only LLM, such as ChatGPT [36] and
LLaMA [48], or multi-modal LLM [50]. It is responsible to analyze user
intentions and produce the proper outputs in text or neural representations.
The router would automatically dispatch the parsed image representations (if
there exist ones in the LLM output) to the image generation module. The
adapter transforms the image representations to better fit the backend T2I
models. Depending on the type of image representations, the adapter can be a
neural network if the image representations are neural embedding or prompt
refinement modules with handcrafted rules or LLM. Next, we illustrate a simple
yet effective instantiation of Mini-DALLE3 architecture by prompting large
language models.

Figure 5:  Pipeline Overview. Mini-DALLE3 consists of two stages, with 1) a
router that analyzes the response from the prompted/finetuned LLM and
dispatches the demand for image generation if needed, and 2) an adapter that
transforms the image embedding or descriptions for subsequent T2I models.

###  4.1 Multi-Turn Interaction by Prompting LLM

Multi-turn interaction lies at the heart of interactive text-to-image. It
possesses the requirements of integrating textual/visual context and
understanding instructional instead of descriptive messages. To address it, we
propose to leverage the stronger context-understanding ability of LLMs by
prompting them to pretend to generate images via textual descriptions. This
intermediate textual description not only provides stronger flexibilities to
augment the system capabilities with plug-and-play modules such as prompt
variation/refinement but also enables us to utilize numerous pretrained LLMs
and T2I models without heavy finetuning.

Image Generation as Function Call. Specifically, we utilize the few-shot
prompt as shown in Fig. 6 to transform the problem of multi-turn image
generation into a problem of multi-turn textual description generation.

Figure 6: The few-shot prompt for iT2I generation.

Our prompt entails several key steps. Initially, we define the LM’s role and
explicitly convey to it that it possesses the ability to generate images.
Subsequently, we request the LM to produce images by generating descriptive
text enclosed within $\left<\text{image}\right>$ tags. If the generated images
exhibit a high degree of correlation with previous ones, the LM is instructed
to generate “edit” rather than generate “image”. Finally, we provide a few
number of few-shot examples to further guide the LM’s responses. Leveraging
the robust in-context learning capabilities inherent in advanced LLMs, we
observe that this approach yields favorable outcomes. The LM successfully
generates images accompanied by coherent textual responses, as illustrated in
Fig. 1. Importantly, these capabilities can be harnessed without the need for
specialized training and can be swiftly integrated into existing LLMs.

Prompt Refinement&&Variations. Although we can generate textual descriptions
that integrate the information from context by prompting LLMs, the
descriptions might not be sufficient to generate high-quality images.
Therefore, we propose to leverage another round of prompt refinement to
transform the vanilla descriptions to better fit subsequent T2I models. It is
worth noting that the prompt refinement can also apply to embedding if the
previous intermediate representation is embedding. In this instantiation, we
perform text transformation by prompting LLM again with the following few-shot
prompt. Furthermore, we can perform prompt variation by repeatedly performing
different prompt refinements, which is useful for responding to the request to
generate a list of images.

Figure 7: Qualitative comparison of interactive text-to-image generation by
prompting different LLM.

###  4.2 Hierarchical Content Consistency Control

Content consistency is another important aspect of an iT2I system. Although
similar topics (subject-driven T2I, example-driven T2I, personalization,
concept learning) are widely explored in the context of conventional T2I [42,
57, 26], only a few works explore the multi-turn scenarios and seldom works
explore the integration of these abilities into a single unified system. Our
decomposition makes it possible to utilize existing T2I models that were not
designed for multi-turn scenarios. For example, the edited description of
Prompt-to-prompt [32] can be automatically generated through LLM in an
interactive manner.

Specifically, we leverage the off-the-shelf T2I models that take previous
images as additional input to ensure consistent multi-turn generation. To
better ensure the image quality, we introduce a hierarchical control strategy
that utilizes different models for different levels of content changes. For
small content changes that can be described in a few words, such as changing
styles, word weighting, and simple object manipulation, we adopt the models of
Prompt to prompt [32] and MasaCtrl [8]. We utilize IP-Adapter [60] to perform
large content changes as these models are more flexible for the input textual
prompts.

###  4.3 Composiblitiy

As we have not modified the original LLM, our system can natively support the
composition with question answering and image generation interleavedly.

##  5 Evaluation

Will prompting harm the inherent abilities of LLM? We provide a preliminary
evaluation if the iT2I prompt harms the inherent abilities of LLM. As
previously shown in Fig. 1, our prompting technique would not cause severe
degradation in the LLM abilities. We can still ask LLMs for either question
answering or code generation as before. To further investigate the impact of
the iT2I prompt, we perform an ablation study on five subtasks of MMLU [19],
comparing the models with and without the iT2I prompt. The results are
provided in Tab. 1, it can be observed that the iT2I prompt only brings minor
degradations.

Task |  GPT3.5-Turbo Original |  GPT3.5-Turbo Mini-DALLE3
---|---|---
Abstract Algebra | 42.42 | 43.43
High School Physics | 40.00 | 38.67
Marketing | 88.41 | 86.70
Philosophy | 77.41 | 70.65
College Computer Science | 48.48 | 42.42
Average | 59.34 | 56.37
Table 1: Evaluation results of different models on the subtasks of MMLU, using the script from chain-of-thought-hub [14]. Figure 8: Examples use cases of interactive text-to-image generation. Interactive Image Generation |  Storytelling |  Concept Prototyping |  Interactive Logo Design
---|---|---|---
A vibrant illustration of a traditional Spring Festival scene. The street is filled with colorful decorations, lanterns, and people celebrating. Lion dancers and dragon parades add to the festive atmosphere, while families gather to enjoy delicious food together. The scene is filled with joy and excitement, capturing the spirit of the Spring Festival. |  A beautiful girl with flowing hair, dressed in regal attire, stands tall in a grand castle. Her royal lineage is evident in her graceful demeanor. The ancient stories speak of her unmatched beauty, making her the fairest of them all. |  A Retro Spaceship with a bulbous shape, fins, and a silver and red color scheme. It has a streamlined design and a nostalgic feel, reminiscent of classic sci-fi movies. The spaceship is adorned with retro-style decals and has large windows to provide a view of the cosmos. It exudes a sense of adventure and exploration as it cruises through the vastness of space. |  A minimalist logo with the text ”Mini DALLE 3” written in a clean and modern font. The letters are arranged in a straight line, with each letter having equal spacing. The color palette consists of vibrant shades of blue and green, representing creativity and innovation.
In this illustration, a group of people is gathered in an open area, setting off firecrackers to celebrate the Spring Festival. The sky is filled with colorful bursts of light and smoke as the firecrackers explode, creating a festive and energetic atmosphere. The people are wearing traditional clothing and have joyful expressions on their faces as they enjoy the tradition of setting off firecrackers to ward off evil spirits and bring good luck for the coming year. |  Inside a majestic castle made of stone, the girl sleeps peacefully in her grand bed. Despite any noise that could wake the dead, she remains undisturbed in her slumber, earning her the nickname ”Sleepyhead.” |  A Retro Spaceship with a bulbous shape and a silver and red color scheme. It has a streamlined design reminiscent of classic sci-fi movies. The spaceship features a rounded cockpit with large windows, allowing the pilot to have a panoramic view of space. The exterior is adorned with retro-style decals and has a polished metallic finish. It exudes a sense of nostalgia and adventure as it travels through the cosmos. |  A minimalist logo with the text ”Mini DALLE 3” written in a clean and modern font. The letters are arranged in the same line, with each letter having equal spacing. The color palette consists of vibrant shades of green and orange representing creativity and innovation. The logo is placed on a white background, creating a clean and sleek look.
Table 2: Generated captions of the examples in Figure 8.

Comparsion of different LLM. We evaluate our approach with different LLMs,
including commerical services OpenAI GPT3.5 [7], GPT4 [36],
Claude333https://claude.ai, and open-source LLAMA2-13B-Chat [48],
Baichuan2-13B Chat [56], ChatGLM2-6B-Chat [10], Qwen-14B-Chat [3],
InternLM-20B-Chat [46]. As shown in Fig. 7, all commercial LLMs successfully
generate the images with appropriate corrsponding text (interleaved)
responses. This indicates that our prompting approach could be a simple yet
effective way to rapidly augment existing LLMs with iT2I ability.
Nevertheless, the results are less satisfactory for the open-source LLMs.
Overall, Baichuan2 [56] generates the best results, while Qwen and InternLM
tend to refuse to generate images even if they are prompted to do so. ChatGLM2
could generate an image but the correspondence is incorrect.

iT2I Examples. Here, we show a number of iT2I examples, which cover different
use scenarios from single-turn/multi-turn image generation to interleaved
text-image storytelling. The results are shown in Fig. 8 and Tab. 2.

##  6 Conclusion

In conclusion, this paper introduces the concept of interactive text-to-image
(iT2I) and presents an approach to augmenting existing large language models
for this task. Our evaluation shows that this approach enables convenient iT2I
capabilities without significant degradation of the models’ inherent
capabilities. This work has the potential to enhance user experiences in
human-machine interactions and elevate the image quality of next-generation
T2I models, offering promising directions for future research and development.

## References

  * Ahn et al. [2023] Namhyuk Ahn, Junsoo Lee, Chunggi Lee, Kunhee Kim, Daesik Kim, Seung-Hun Nam, and Kibeom Hong.  Dreamstyler: Paint by style inversion with text-to-image diffusion models.  _arXiv preprint arXiv:2309.06933_ , 2023.
  * AUTOMATIC1111 [2022] AUTOMATIC1111.  Stable Diffusion Web UI, 2022.
  * Bai et al. [2023] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, Binyuan Hui, Luo Ji, Mei Li, Junyang Lin, Runji Lin, Dayiheng Liu, Gao Liu, Chengqiang Lu, Keming Lu, Jianxin Ma, Rui Men, Xingzhang Ren, Xuancheng Ren, Chuanqi Tan, Sinan Tan, Jianhong Tu, Peng Wang, Shijie Wang, Wei Wang, Shengguang Wu, Benfeng Xu, Jin Xu, An Yang, Hao Yang, Jian Yang, Shusheng Yang, Yang Yao, Bowen Yu, Hongyi Yuan, Zheng Yuan, Jianwei Zhang, Xingxuan Zhang, Yichang Zhang, Zhenru Zhang, Chang Zhou, Jingren Zhou, Xiaohuan Zhou, and Tianhang Zhu.  Qwen technical report, 2023.
  * Balaji et al. [2022] Yogesh Balaji, Seungjun Nah, Xun Huang, Arash Vahdat, Jiaming Song, Karsten Kreis, Miika Aittala, Timo Aila, Samuli Laine, Bryan Catanzaro, et al.  ediffi: Text-to-image diffusion models with an ensemble of expert denoisers.  _arXiv preprint arXiv:2211.01324_ , 2022.
  * Besta et al. [2023] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michał Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler.  Graph of Thoughts: Solving Elaborate Problems with Large Language Models, 2023.
  * Brooks et al. [2023] Tim Brooks, Aleksander Holynski, and Alexei A Efros.  Instructpix2pix: Learning to follow image editing instructions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18392–18402, 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.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Cao et al. [2023] Mingdeng Cao, Xintao Wang, Zhongang Qi, Ying Shan, Xiaohu Qie, and Yinqiang Zheng.  Masactrl: Tuning-free mutual self-attention control for consistent image synthesis and editing, 2023.
  * Dong et al. [2023] Runpei Dong, Chunrui Han, Yuang Peng, Zekun Qi, Zheng Ge, Jinrong Yang, Liang Zhao, Jianjian Sun, Hongyu Zhou, Haoran Wei, et al.  Dreamllm: Synergistic multimodal comprehension and creation.  _arXiv preprint arXiv:2309.11499_ , 2023.
  * Du et al. [2022] Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang.  Glm: General language model pretraining with autoregressive blank infilling.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 320–335, 2022.
  * Endo [2022] Yuki Endo.  User-controllable latent transformer for stylegan image layout editing.  _Computer Graphics Forum_ , 41(7):395–406, 2022.
  * Esser et al. [2021] Patrick Esser, Robin Rombach, and Bjorn Ommer.  Taming transformers for high-resolution image synthesis.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 12873–12883, 2021.
  * Feng et al. [2023] Zhida Feng, Zhenyu Zhang, Xintong Yu, Yewei Fang, Lanxin Li, Xuyi Chen, Yuxiang Lu, Jiaxiang Liu, Weichong Yin, Shikun Feng, et al.  Ernie-vilg 2.0: Improving text-to-image diffusion model with knowledge-enhanced mixture-of-denoising-experts.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10135–10145, 2023.
  * Fu et al. [2023] Yao Fu, Litu Ou, Mingyu Chen, Yuhao Wan, Hao Peng, and Tushar Khot.  Chain-of-thought hub: A continuous effort to measure large language models’ reasoning performance.  _arXiv preprint arXiv:2305.17306_ , 2023.
  * Ge et al. [2023a] Songwei Ge, Taesung Park, Jun-Yan Zhu, and Jia-Bin Huang.  Expressive text-to-image generation with rich text.  In _IEEE International Conference on Computer Vision (ICCV)_ , 2023a.
  * Ge et al. [2023b] Yuying Ge, Yixiao Ge, Ziyun Zeng, Xintao Wang, and Ying Shan.  Planting a seed of vision in large language model.  _arXiv preprint arXiv:2307.08041_ , 2023b.
  * Goodfellow et al. [2020] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _Communications of the ACM_ , 63(11):139–144, 2020.
  * Gu et al. [2022] Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo.  Vector quantized diffusion model for text-to-image synthesis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10696–10706, 2022.
  * Hendrycks et al. [2020] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33:6840–6851, 2020.
  * Kang et al. [2023] Minguk Kang, Jun-Yan Zhu, Richard Zhang, Jaesik Park, Eli Shechtman, Sylvain Paris, and Taesung Park.  Scaling up gans for text-to-image synthesis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10124–10134, 2023.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Kirillov et al. [2023] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  _arXiv preprint arXiv:2304.02643_ , 2023.
  * Koh et al. [2023] Jing Yu Koh, Daniel Fried, and Ruslan Salakhutdinov.  Generating images with multimodal language models.  _arXiv preprint arXiv:2305.17216_ , 2023.
  * Li et al. [2023a] Dongxu Li, Junnan Li, and Steven CH Hoi.  Blip-diffusion: Pre-trained subject representation for controllable text-to-image generation and editing.  _arXiv preprint arXiv:2305.14720_ , 2023a.
  * Li et al. [2023b] Tianle Li, Max Ku, Cong Wei, and Wenhu Chen.  Dreamedit: Subject-driven image editing.  _arXiv preprint arXiv:2306.12624_ , 2023b.
  * Li et al. [2023c] Yuheng Li, Haotian Liu, Qingyang Wu, Fangzhou Mu, Jianwei Yang, Jianfeng Gao, Chunyuan Li, and Yong Jae Lee.  Gligen: Open-set grounded text-to-image generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 22511–22521, 2023c.
  * Li et al. [2023d] Zhengqi Li, Richard Tucker, Noah Snavely, and Aleksander Holynski.  Generative image dynamics.  _arXiv preprint arXiv:2309.07906_ , 2023d.
  * Ling et al. [2023] Pengyang Ling, Lin Chen, Pan Zhang, Huaian Chen, and Yi Jin.  Freedrag: Point tracking is not you need for interactive point-based image editing.  _arXiv preprint arXiv:2307.04684_ , 2023.
  * Liu et al. [2023a] Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, et al.  Grounding dino: Marrying dino with grounded pre-training for open-set object detection.  _arXiv preprint arXiv:2303.05499_ , 2023a.
  * Liu et al. [2023b] Zhaoyang Liu, Yinan He, Wenhai Wang, Weiyun Wang, Yi Wang, Shoufa Chen, Qinglong Zhang, Yang Yang, Qingyun Li, Jiashuo Yu, et al.  Internchat: Solving vision-centric tasks by interacting with chatbots beyond language.  _arXiv preprint arXiv:2305.05662_ , 2023b.
  * Mokady et al. [2022] Ron Mokady, Amir Hertz, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Null-text inversion for editing real images using guided diffusion models.  _arXiv preprint arXiv:2211.09794_ , 2022.
  * Mou et al. [2023a] Chong Mou, Xintao Wang, Jiechong Song, Ying Shan, and Jian Zhang.  Dragondiffusion: Enabling drag-style manipulation on diffusion models.  _arXiv preprint arXiv:2307.02421_ , 2023a.
  * Mou et al. [2023b] Chong Mou, Xintao Wang, Liangbin Xie, Jian Zhang, Zhongang Qi, Ying Shan, and Xiaohu Qie.  T2i-adapter: Learning adapters to dig out more controllable ability for text-to-image diffusion models.  _arXiv preprint arXiv:2302.08453_ , 2023b.
  * OpenAI [2023a] OpenAI.  Dall·e 3 system card.  2023a.
  * OpenAI [2023b] OpenAI.  Gpt-4 technical report, 2023b.
  * Pan et al. [2023] Xingang Pan, Ayush Tewari, Thomas Leimkühler, Lingjie Liu, Abhimitra Meka, and Christian Theobalt.  Drag your gan: Interactive point-based manipulation on the generative image manifold.  In _ACM SIGGRAPH 2023 Conference Proceedings_ , pages 1–11, 2023.
  * 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 _International conference on machine learning_ , pages 8748–8763. PMLR, 2021.
  * Ramesh et al. [2021] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In _International Conference on Machine Learning_ , pages 8821–8831. PMLR, 2021.
  * Ramesh et al. [2022] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ , 2022.
  * 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 _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10684–10695, 2022.
  * Ruiz et al. [2022] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yael Pritch, Michael Rubinstein, and Kfir Aberman.  Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation.  2022\.
  * Saharia et al. [2022] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _arXiv preprint arXiv:2205.11487_ , 2022.
  * Shi et al. [2023] Yujun Shi, Chuhui Xue, Jiachun Pan, Wenqing Zhang, Vincent YF Tan, and Song Bai.  Dragdiffusion: Harnessing diffusion models for interactive point-based image editing.  _arXiv preprint arXiv:2306.14435_ , 2023.
  * Sohn et al. [2023] Kihyuk Sohn, Nataniel Ruiz, Kimin Lee, Daniel Castro Chin, Irina Blok, Huiwen Chang, Jarred Barber, Lu Jiang, Glenn Entis, Yuanzhen Li, et al.  Styledrop: Text-to-image generation in any style.  _arXiv preprint arXiv:2306.00983_ , 2023.
  * Team [2023] InternLM Team.  Internlm: A multilingual language model with progressively enhanced capabilities.  https://github.com/InternLM/InternLM, 2023.
  * Tibebu et al. [2022] Haileleol Tibebu, Aadin Malik, and Varuna De Silva.  Text to image synthesis using stacked conditional variational autoencoders and conditional generative adversarial networks.  In _Science and Information Conference_ , pages 560–580. Springer, 2022.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Wang et al. [2023a] Qian Wang, Biao Zhang, Michael Birsak, and Peter Wonka.  Instructedit: Improving automatic masks for diffusion-based image editing with user instructions.  _arXiv preprint arXiv:2305.18047_ , 2023a.
  * Wang et al. [2023b] Wenhai Wang, Zhe Chen, Xiaokang Chen, Jiannan Wu, Xizhou Zhu, Gang Zeng, Ping Luo, Tong Lu, Jie Zhou, Yu Qiao, et al.  Visionllm: Large language model is also an open-ended decoder for vision-centric tasks.  _arXiv preprint arXiv:2305.11175_ , 2023b.
  * Wang et al. [2022] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_ , 2022.
  * Wei et al. [2022] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022.
  * Wei et al. [2023] Jingxuan Wei, Shiyu Wu, Xin Jiang, and Yequan Wang.  Dialogpaint: A dialog-based image editing model.  _arXiv preprint arXiv:2303.10073_ , 2023.
  * Wu et al. [2023] Shengqiong Wu, Hao Fei, Leigang Qu, Wei Ji, and Tat-Seng Chua.  Next-gpt: Any-to-any multimodal llm, 2023.
  * Xue et al. [2023] Zeyue Xue, Guanglu Song, Qiushan Guo, Boxiao Liu, Zhuofan Zong, Yu Liu, and Ping Luo.  Raphael: Text-to-image generation via large mixture of diffusion paths.  _arXiv preprint arXiv:2305.18295_ , 2023.
  * Yang et al. [2023a] Aiyuan Yang, Bin Xiao, Bingning Wang, Borong Zhang, Chao Yin, Chenxu Lv, Da Pan, Dian Wang, Dong Yan, Fan Yang, et al.  Baichuan 2: Open large-scale language models.  _arXiv preprint arXiv:2309.10305_ , 2023a.
  * Yang et al. [2023b] Binxin Yang, Shuyang Gu, Bo Zhang, Ting Zhang, Xuejin Chen, Xiaoyan Sun, Dong Chen, and Fang Wen.  Paint by example: Exemplar-based image editing with diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18381–18391, 2023b.
  * Yao et al. [2023] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of thoughts: Deliberate problem solving with large language models.  _arXiv preprint arXiv:2305.10601_ , 2023.
  * Ye et al. [2023a] Hu Ye, Jun Zhang, Sibo Liu, Xiao Han, and Wei Yang.  Ip-adapter: Text compatible image prompt adapter for text-to-image diffusion models.  _arXiv preprint arXiv:2308.06721_ , 2023a.
  * Ye et al. [2023b] Hu Ye, Jun Zhang, Sibo Liu, Xiao Han, and Wei Yang.  Ip-adapter: Text compatible image prompt adapter for text-to-image diffusion models.  2023b.
  * Yildirim et al. [2023] Ahmet Burak Yildirim, Vedat Baday, Erkut Erdem, Aykut Erdem, and Aysegul Dundar.  Inst-inpaint: Instructing to remove objects with diffusion models.  _arXiv preprint arXiv:2304.03246_ , 2023.
  * Yin et al. [2023] Shengming Yin, Chenfei Wu, Jian Liang, Jie Shi, Houqiang Li, Gong Ming, and Nan Duan.  Dragnuwa: Fine-grained control in video generation by integrating text, image, and trajectory.  _arXiv preprint arXiv:2308.08089_ , 2023.
  * Zhang et al. [2023a] Kai Zhang, Lingbo Mo, Wenhu Chen, Huan Sun, and Yu Su.  Magicbrush: A manually annotated dataset for instruction-guided image editing, 2023a.
  * Zhang and Agrawala [2023] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  _arXiv preprint arXiv:2302.05543_ , 2023.
  * Zhang et al. [2023b] Shu Zhang, Xinyi Yang, Yihao Feng, Can Qin, Chia-Chih Chen, Ning Yu, Zeyuan Chen, Huan Wang, Silvio Savarese, Stefano Ermon, Caiming Xiong, and Ran Xu.  Hive: Harnessing human feedback for instructional visual editing.  _arXiv preprint arXiv:2303.09618_ , 2023b.