# Training-Free Layout Control with Cross-Attention Guidance

Minghao Chen Iro Laina Andrea Vedaldi
Visual Geometry Group, University of Oxford
{minghao, iro<EMAIL_ADDRESS>
silent-chen.github.io/layout-guidance

###### Abstract

Recent diffusion-based generators can produce high-quality images based only
on textual prompts. However, they do not correctly interpret instructions that
specify the spatial layout of the composition. We propose a simple approach
that can achieve robust layout control without requiring training or fine-
tuning the image generator. Our technique, which we call layout guidance,
manipulates the cross-attention layers that the model uses to interface
textual and visual information and steers the reconstruction in the desired
direction given, e.g., a user-specified layout. In order to determine how to
best guide attention, we study the role of different attention maps when
generating images and experiment with two alternative strategies, forward and
backward guidance. We evaluate our method quantitatively and qualitatively
with several experiments, validating its effectiveness. We further demonstrate
its versatility by extending layout guidance to the task of editing the layout
and context of a given real image.

Figure 1: Left: our method can control the layout of an image generated by a
pre-trained diffusion model, such as Stable Diffusion [31], without any
finetuning or training. It also alleviates the problem that Stable Diffusion
may not generate all objects in the prompt. Right: given a single real image,
we manage to edit its position, context with the Dreambooth [33], and Text
Inversion [8] technique. $\langle*\rangle$ is the learned token that encodes
the object in the image.

##  1 Introduction

Generative AI is easily one of the most disruptive technologies that have
emerged in the last few years. In computer vision, new text-conditioned image
generation methods, such as DALL-E [29], Imagen [34], and Stable Diffusion
[31], have demonstrated that machines can generate image outputs of a quality
sufficient to use in many applications. These methods can easily multiply the
productivity of professional artists as well as laypeople.

Despite these successes, however, many practical applications of image
generation, particularly in a professional context, require a high level of
_control_ that current methods lack. Specifications in language-based image
generators are textual; and while text can tap into a vast library of high-
level concepts, it is a poor vehicle for expressing fine-grained visual
details in an image. In particular, text is a poor way of describing the
precise _layout of a composition_.

In fact, as shown in previous works [9] and as we show in our experiments,
state-of-the-art image generators are not even very good at correctly
interpreting simple layout instructions that are specified via text. For
example, when requesting an image with the prompt “a dog to the left of a
cat”, it is uncertain whether the resulting spatial relationship of the
objects will match the desired layout. In fact, prompts of this nature often
lead models to produce erroneous semantics, for example, an image of cat-dog
hybrid. This limitation is exacerbated by unusual compositions such as “horse
on top of a house”, which live outside the typical compositions that the model
observes during training.

In this work, we are thus interested in better understanding this limitation
and providing a simple tool to overcome it. We do so by studying and
intervening in the attention patterns that are extracted by text-to-image
models during generation. Our method achieves robust _layout control_ without
requiring further training, while still preserving the quality of the
generated images. Our work is complementary to others that also recently
looked at manipulating attention patterns to improve the compositionality and
faithfulness of the generations or enable localized image edits. For example,
[12] perform in-place semantic editing, allowing, _e.g_., to swap one object
for another in a generated image. Instead, we focus specifically on the
_spatial_ aspect of the compositionality.

To better control layout, our first contribution is to analyze and better
understand the role of attention patterns on layout in such image generators.
Text conditioning in these models is achieved by attending to different parts
of the text prompt (words) as the image is generated. Because each part of the
image attends independently to the different words via cross-attention, this
associates words and image locations at multiple levels in the architecture
hierarchy. We show that, while there is an intuitive correlation between
different concepts and their visual extent, this correlation is more nuanced
than one might think, and show that, perhaps counter-intuitively, the filler
tokens in the sentences (the start tokens and padding tokens), actually carry
significant information in the image generation process.

We note that, while layout cannot be easily controlled via textual prompting,
we can in fact _intervene_ directly in the activation patterns, steering the
reconstruction of the output image in a direction of choice with user-
specified inputs, such as bounding boxes, which we refer to as _layout
guidance_. In order to do this, we consider and compare two alternative
strategies for such an intervention: forward guidance and backward guidance.
Forward guidance directly biases the cross-attention layers to shift
activations in the desired pattern, letting the model incorporate the guidance
via the iterated application of its denoising steps. Backward guidance uses
backpropagation to update the activations in the network to match the desired
layout via energy minimization. To summarize, our contributions are three-
fold: (1) We propose two general training-free strategies to robustly control
the layout of images generated by large diffusion models. (2) We explore the
cross-attention maps and give insights, such as the start and padding tokens
surprisingly carrying heavy semantic and layout information. (3) We
quantitatively and qualitatively evaluate the effectiveness method and achieve
real image layout editing.

##  2 Related Work

##### Text-to-Image Generation.

For several years, generative adversarial networks (GANs) [10] have been the
dominant approach in image generation from textual prompts [30, 46, 47, 38,
40, 45]. Alternative representations for text, such as scene graphs, have also
been considered [18]. More recently, the focus has shifted onto text-
conditional autoregressive [29, 44, 7, 4] and diffusion models [24, 34, 31,
28, 11], with impressive results in generating images of remarkable fidelity,
while avoiding common GAN pitfalls such as training instability and mode
collapse [3]. A substantial increase in both the data scale [35] and the size
and capabilities of transformer models [27] has played a crucial role in
enabling this shift. Typically, these models are designed to accept a textual
prompt as input, which may pose a challenge for accurately conveying all
details of the image. This problem is exacerbated with longer prompts or when
describing an atypical scene. Recent studies have demonstrated the
effectiveness of classifier-free guidance [14] in improving the faithfulness
of the generations in relation to the input prompt. Others focus on improving
compositionally, _e.g_., by combining multiple diffusion models together with
different operators [22] or via structured representations for text prompts
[6].

##### Layout Control in Image Generation.

Closely related to achieving layout control is image generation with spatial
conditioning, which is typically specified as labeled bounding boxes or
semantic maps [36, 37, 41, 49, 5, 25]. These methods operate without text
prompts and, as a result, they rely on a closed-set vocabulary to generate
images, which is decided by the labeled concepts in the training distribution
(_e.g_., MS COCO [21]). However, large image-text models such as CLIP [27] are
now making it possible to extend to open-vocabulary generation. On the other
hand, it is often challenging for text to convey information about the precise
layout of a scene; even then, the _spatial_ fidelity of image generators is
extremely limited [9]. Therefore, jointly conditioning on text and layout has
been studied in [7, 13, 17] as well as predicting layout from text [15]. Very
recently, and concurrently with our work, [20, 42] propose mechanisms to
extend the state-of-the-art Stable Diffusion model [31] with spatial
conditioning. Gligen [20] uses a gated self-attention layer which enables
additional inputs (_e.g_., bounding boxes) to be processed. ReCo [42] achieves
layout control through regional tokens encoded as part of the text prompt.
However, unlike our approach, both of these methods require additional
training using images with localized objects as ground truth. Finally,
building on top of diffusion, some recent works show controllable image
generation from various conditioning signals [1, 48, 16].

##### Diffusion-Based Image Editing.

Most aforementioned methods lack the ability to control or edit an already
generated image, or even the ability to edit real images. For example, simply
changing a word in the original prompt typically leads to a drastically
different generation. This can be circumvented by providing or generating
masks for the objects of interest [24, 2]. Prompt-to-prompt [12] addresses
this issue with simple text-based edits by exploiting the fact that the cross-
attention layers present in most state-of-the-art architectures connect word
tokens to the spatial layout of the generated images. Text-based image editing
can also be achieved through single-image model fine-tuning [19, 39]. However,
these approaches, while successful at semantically editing entities can only
apply such edits _in-place_ and do not allow editing of the spatial layout
itself.

##  3 Method

We consider the problem of layout-guided text-to-image generation. Text-based
image generators allow to sample images $\boldsymbol{x}\in\mathbb{R}^{3\times
H\times W}$ from a conditional distribution $p(\boldsymbol{x}\mid y)$ where
$y\in\Sigma^{*}$ is a language description, $\Sigma$ is a vocabulary (a list
of words), and $\Sigma^{*}$ is the set of all possible sequences of words.
Given one such generator off-the-shelf, we wish to steer the output to match a
desired layout for the generated composition, _without further training_. In
other words, our objective is to investigate whether pre-trained text-to-image
generators can adhere to a layout specified by the user during inference,
without having been trained with explicit layout conditioning. In the simplest
case, given the textual description $y$, the index $i$ of a word $y_{i}$ in
the text prompt, and a bounding box $B$, we would like to generate an image
$\boldsymbol{x}$ that contains $y_{i}$ _inside_ $B$, essentially modifying the
generator to sample from a new distribution $p(\boldsymbol{x}\mid y,B,i)$ with
additional controls.

The rest of the section is structured as follows. In Section 3.1 we briefly
review several technical details of Stable Diffusion [31], as a publicly
accessible, state-of-the-art text-to-image generator. In Section 3.2, we
introduce a method that achieves layout guidance during the generation process
by intervening in the way the underlying image generator associates visual and
textual information. This is achieved via manipulation of the attention
response in certain cross-attention layers in the architecture, as well as via
an analysis of how textual information is encoded and how the latter affects
the output. Finally, in Section 3.3 we discuss how to make this approach
applicable to editing real images.

###  3.1 Preliminaries: Stable Diffusion

Figure 2: An overview of the two layout guidance strategies: The cross-
attention map for a chosen word token is marked with a red border. In forward
guidance, we bias (spatially) the word token, start token, and padding tokens.
In backward guidance, we perform backpropagation during the inference process
to optimize the latent.

We consider Stable Diffusion (SD) as a representative conditional image
generator of an important class of recent image generators based on diffusion
[29, 34, 31]. The SD model comprises a _textual encoder_ $Y=\phi(y)$ that maps
the input prompt into a tensor of fixed dimension $Y\in\mathbb{R}^{M\times
N}$. This works by prepending a start ([SoT]) symbol to $y$ and appending
$N-|y|-1$ padding ([EoT]) symbols at the end, to obtain $N$ symbols in total.
Then, the function $\phi$, implemented as a large language model (LLM), takes
the padded sequence of words as input and produces a corresponding sequence of
token vectors $Y_{i}\in\mathbb{R}^{M}$ with $i\in\\{1,\dots,N\\}$ as output.

While not crucial for our discussion, the SD model also contains an encoding
network $h$ that maps images $\boldsymbol{x}$ to corresponding latent codes
$\boldsymbol{z}=h(\boldsymbol{x})\in\mathbb{R}^{4\times\frac{H}{s}\times\frac{W}{s}}$,
where $s$ divides $H$ and $W$. The function $h$ is an autoencoder and has a
left inverse $h^{*}$, such that $\boldsymbol{x}=h^{*}\circ h(\boldsymbol{x})$.
The main purpose of this component is to replace the problem of modeling
$p(\boldsymbol{x}\mid y)$ with the problem of modeling $p(\boldsymbol{z}\mid
y)$, reducing the spatial resolution $s$-fold.

The other key component of SD is an iterative conditional denoising network
$D$. This network is trained to output a conditional sample
$\boldsymbol{z}\sim p(\boldsymbol{z}\mid y)$ of the latent code
$\boldsymbol{z}$. It is designed to take a noised sample
$\boldsymbol{z}_{t}=\alpha_{t}\boldsymbol{z}+\sqrt{1-\alpha_{t}}\boldsymbol{\epsilon}_{t}$,
where $\boldsymbol{\epsilon}_{t}$ is normally distributed noise and
$\alpha_{t}$ is a decreasing sequence, from $\alpha_{0}\approx 1$ to
$\alpha_{T}\approx 0$, representing the noise schedule. Then, the network $D$
returns an estimate of the noised sample $\boldsymbol{z}_{t}$:
$D(\boldsymbol{z}_{t},y,t)\approx\boldsymbol{\epsilon}_{t}.$ To sample an
image, one first samples $\boldsymbol{z}_{T}$, which is normally distributed,
and applies $D$ iteratively, to obtain the intermediate codes
$\boldsymbol{z}_{T-1},\dots,\boldsymbol{z}_{1},\boldsymbol{z}_{0}\approx\boldsymbol{z}$.
Finally, $\boldsymbol{z}$ is converted back to an image via the image decoder
$\boldsymbol{x}=h^{*}(\boldsymbol{z})$.

There is one more aspect of the SD architecture design that we require for our
purposes. While there are several important design choices that make the
network $D$ work well in practice, the mechanism that is of interest in our
investigation is _cross-attention_ , which allows the generation process to be
conditioned on text, thus connecting visual and textual information. Each
cross-attention layer takes an intermediate feature tensor
$\boldsymbol{z}^{(\gamma)}\in\mathbb{R}^{C\times\frac{H}{r}\times\frac{W}{r}}$
as input, where $\gamma$ is the index of the relevant layer in the network,
and $r$ is a scaling factor defining the spatial resolution at that level of
the representation. The cross-attention map $A^{(\gamma)}$ associates each
spatial location
$u\in\\{1,\dots,\frac{H}{r}\\}\times\\{1,\dots,\frac{W}{r}\\}$ to a token
indexed by $i\in\\{1,\dots,N\\}$:

$A^{(\gamma)}_{ui}=\frac{\exp\langle\boldsymbol{z}_{u}^{(\gamma)},K_{i}^{(\gamma)}\rangle}{\sum_{j=1}^{N}\exp\langle\boldsymbol{z}_{u}^{(\gamma)},K_{j}^{(\gamma)}\rangle},\\!\quad\boldsymbol{a}_{u}^{(\gamma)}=\sum_{i=1}^{N}A^{(\gamma)}_{ui}V_{i}^{(\gamma)},$

where the value $V_{i}^{(\gamma)}$ and the key $K_{i}^{(\gamma)}$ are linear
transformations of the token embedding $Y_{i}$ provided by the textual
encoder, and $\boldsymbol{a}_{u}^{(\gamma)}$ is the output of the cross-
attention layer.

Figure 3: Cross-attention maps of different text prompts at the generation
process. All of the examples indicate that start token ([SoT]) and padding
tokens ([EoT]) carry rich semantic and layout information.

###  3.2 Layout Guidance

Next, we introduce our method for training-free layout guidance. It has
already been shown that cross-attention layers regulate the spatial layout of
the generated image [12]. Specifically, the attention map the attention map
$A^{(\gamma)}_{ui}$ determines how strongly each location $u$ in layer
$\gamma$ is associated with each of the $N$ text tokens $y_{i}$. Since the sum
of association strengths $\sum_{i=1}^{N}A^{(\gamma)}_{ui}=1$ for each spatial
location $u$, the different tokens can be thought of as “competing” for
association with that location. To control the image layout using a bounding
box B that corresponds to token $y_{i}$, the attention can be biased such that
locations $u\in B$ within the target box are strongly associated with the
token $y_{i}$ (while other locations are not). We introduce two ways of
achieving this effect, which we refer to as forward guidance (Section 3.2.1)
and backward guidance (Section 3.2.2). We give an overview of the two
strategies in Figure 2.

Figure 4: Comparison between forward and backward guidance, including guidance
of start and padding tokens.

####  3.2.1 Forward Guidance

In forward guidance, we represent the bounding box $B$ as a smooth windowing
function $g^{(\gamma)}_{u}$ which is equal to a constant $c>0$ inside the box
and quickly falls to zero outside.111For simplicity, in our implementation, we
put a Gaussian blob with $\sigma$ decided by the resolution, height, and width
of the bounding box. We rescale the windowing function to sum to one
($\|g^{(\gamma)}\|_{1}=1$). Then, we bias the attention map $A^{(\gamma)}$ by
replacing it via:

$A^{(\gamma)}_{ui}\leftarrow(1-\lambda)A^{(\gamma)}_{ui}+\lambda
g^{(\gamma)}_{u}\sum_{v}A^{(\gamma)}_{vi},$ (1)

where $\lambda\in[0,1]$ defines the strength of the intervention. Note that:
(1) only the cross-attention map $A^{(\gamma)}_{ui}$ corresponding to token
$y_{i}$ is affected by this intervention (2) the window is weighed by the mass
$\sum_{v}A^{(\gamma)}_{vi}$ so as to leave the latter unchanged.

This intervention is injected at each application of the denoiser function $D$
at a selected subset of layers $\gamma\in\Gamma$. This means that the
activation maps computed by each of the selected layers are replaced with
Equation 1.

####  3.2.2 Backward Guidance

The second approach we consider is backward guidance. In this case, we bias
the attention $A^{(\gamma)}_{ui}$ by introducing the energy function

$E(A^{(\gamma)},B,i)=\left(1-\frac{\sum_{u\in
B}A^{(\gamma)}_{ui}}{\sum_{u}A^{(\gamma)}_{ui}}\right)^{2}$ (2)

This is used in a manner similar to _classifier guidance_ [3]. Specifically,
at each application of the denoiser $D$, when layer $\gamma\in\Gamma$ is
evaluated, the gradient of the loss (2) is computed via backpropagation to
update the latent $\boldsymbol{z}_{t}(\equiv\boldsymbol{z}^{(0)}_{t})$:

$\boldsymbol{z}_{t}\leftarrow\boldsymbol{z}_{t}-\sigma_{t}\eta\nabla_{\boldsymbol{z}_{t}}\sum_{\gamma\in\Gamma}E(A^{(\gamma)},B,i),$
(3)

where $\eta>0$ is a scale factor controlling the strength of the guidance and
$\sigma_{t}=\sqrt{(1-\alpha_{t})/\alpha_{t}}$. In order to generate an image,
we alternate between gradient updates and denoising steps. Please see the
experimental section for details.

Figure 5: A qualitative results of different text-to-image models with text
prompts defined in [9]. As stated in [9], most of the current models fail to
understand the corresponding spatial relationship. However, we achieved
control of the generated images with the help of guidance on cross-attention
maps.

####  3.2.3 Discussion

Next, we compare the two layout guidance mechanisms and explore the
significance of different text tokens during guided generation.

##### Forward vs. Backward.

Forward and backward guidance use different mechanisms to affect the pattern
of attention activations. Forward guidance modifies the activations directly
to conform to the prescribed pattern, which is “forced” repeatedly for a
number of denoising iterations at the beginning of the inference process. As
the model starts generating the correct output in the correct image region,
the attention will naturally match the prescribed layout. Forward guidance
does not incur any extra computational cost during the image generation
process.

In contrast, backward guidance uses a loss function to evaluate whether the
attention maps follow the desired pattern and modifies the latent to guide the
attention to focus on a particular region. While slower than forward guidance,
backward guidance is more nuanced, as it softly encourages rather than forces
a particular pattern for the attention map.

##### The Role of Tokens.

Another important finding is that the [SoT] and [EoT] tokens, which do not
correspond to content words in the input text, still carry significant
semantic and layout information (Figure 3). Specifically, the cross-attention
maps of [EoT] tokens correspond to salient regions in the generated image,
_i.e_. typically the union of individual semantic objects in the text prompt.
[SoT] tokens behave complementarily to [EoT], emphasizing the background.

Therefore, to ensure effective forward guidance, it is necessary to intervene
not only on the selected content token but also on the padding ones. However,
we have empirically found that this can sometimes result in overly aggressive
guidance, which could potentially harm image fidelity. In contrast, backward
guidance does not suffer from such drawbacks. As it optimizes the latent, the
cross-attention maps of all tokens are indirectly influenced by the guidance.
An illustration of the impact of forward and backward guidance on different
tokens is provided in Figure 4, supporting our conjecture that information is
nested in text embeddings and is difficult to optimize directly. For further
examples and details on our findings, refer to Section C.

###  3.3 Layout Editing

Layout guidance can also be used in combination with other techniques based on
diffusion image generators. For example, we can apply it to two off-the-shelf
methods that can be used for _editing_ a given input image, namely Textual
Inversion (TI) [8] and Dreambooth [33]. TI is a way of extending an existing
image generator with new concepts given one or several images as examples.
Given the images, TI expands the vocabulary of the text encoder with a new,
learnable token $\langle\ast\rangle$ representing the new concept. Then, it
generates prompts such as “a photo of a $\langle\ast\rangle$” and performs
standard conditional diffusion model training to optimize the text embedding
of $\langle\ast\rangle$, which can then be used to generate new images.
Dreambooth attempts to capture the appearance of a particular subject of which
several images are available. To achieve this, it fine-tunes a pre-trained
text-to-image model and learns an identifier token with respect to the object
in the picture.

Neither method supports localized spatial control over the newly generated
images; their edits are usually global and semantic. To apply layout guidance,
given an image as input, we use TI to acquire a new text embedding
representing the entity depicted in the image. Then, we follow with Dreambooth
to further fine-tune the U-Net and text encoder. Finally, layout guidance can
be applied as before to the fine-tuned model, thus controlling the layout of
the generated images while preserving its semantics, _i.e_. the identity of
the original object represented by $\langle\ast\rangle$.

##  4 Experiments

In this section, we evaluate our approach for training-free layout guidance.
In Section 4.1, we provide details on the implementation and the evaluation
datasets and metrics used in our experiments. We then compare the forward and
backward mechanisms (Section 4.2), present quantitative and qualitative
results (Section 4.3), and analyze the effect of different hyper-parameters
during layout guidance (Section 4.4).

| OA (%) | VISOR (%) |
---|---|---|---
Model | uncond | cond |  Inference Time
Stable Diffusion | 27.4 | 16.4 | 59.85 |  $\sim$ 4 sec/image
Ours (forward) | 25.9 | 23.5 | 90.73 |  $\sim$ 4 sec/image
Ours (forward∗) | 27.6 | 26.1 | 95.00 |  $\sim$ 5 sec/image
Ours (backward) | 38.8 | 37.6 | 96.90 |  $\sim$ 8 sec/image
Table 1: Comparison with the forward, backward method and stable diffusion baseline based on VISOR metric. Forward∗ means we also perform forward guidance on [SoT] and [EoT] tokens. We randomly sampled 1000 text prompts for computing.  | OA (%) | VISOR (%)
---|---|---
Model | uncond | cond
GLIDE | 3.36 | 1.98 | 59.06
GLIDE + CDM | 10.17 | 6.43 | 63.21
DALLE-mini | 27.10 | 16.17 | 59.67
CogView2 | 18.47 | 12.17 | 65.89
DALLE-v2 | 63.93 | 37.89 | 59.27
SD | 29.86 | 18.81 | 62.98
SD + CDM | 23.27 | 14.99 | 64.41
Ours | 40.01 | 38.8 | 95.95
Table 2: Comparison with other text-to-image generation models based on the VISOR metric. Our method achieves almost perfect results under the VISORcond metric. Method |  FID ($\downarrow$) |  $\rm{AP}_{p}$ ($\uparrow$) |  mAP ($\uparrow$)
---|---|---|---
Stable Diffusion [31] | 76 | 19.4 | 8.7
Ours | 82 | 33.5 | 16.7
Upper Bound | - | 77.9 | 32.2
Table 3: Comparison between SD and backward-guided SD (ours) on Flickr30k
Entities. Our approach improves spatial fidelity (suggested by higher AP/mAP
scores). mAP is calculated with an IoU threshold of 0.3.

###  4.1 Experimental setup

##### Implementation Details.

In all experiments, we utilize the open-source Stable-Diffusion (SD) V-1.5
[31] trained on the LAION-5B dataset [35] as the pre-trained image generator,
which serves as a strong baseline. A detailed description of the architecture
and noise scheduler is provided in Appendix A. We also adopted class-free
guidance [14] consistent with prior work [31].

In the forward setting, unless otherwise specified, we perform guidance on the
selected token(s), as well as [SoT] and [EoT] tokens. We apply Equation 1 to
every layer for the first 40 steps of the diffusion process and set $\lambda$
as 0.8. In the backward guidance setting, we calculate the loss on the cross-
attention maps of the mid-block and the first block of the up-sampling branch
of the denoising network (U-Net [32]) as we determined this to be the optimal
setting for balancing control and fidelity. We set the loss scale factor
$\eta$ to 30 by default but found that values between 30-50 work well across
most settings. Since the layout of the generated image is typically
established in the early stages of inference, backward guidance is performed
during the initial 10 steps of the diffusion process and repeated 5 times at
each step.

##### Evaluation Metrics.

To quantitatively evaluate the proposed method, we conduct experiments in two
different settings. First, we follow the evaluation process described in [9]
to compute the VISOR metric, which is designed to quantify the spatial
understanding abilities of text-to-image models. This metric focuses on two-
dimensional relationships, such as left, right, above, and below, between two
objects. We also measure object accuracy (OA), which measures if the generated
image contains both objects specified in the text prompt. To generate text
prompts for evaluation, we use the 80 object categories from the MS COCO
dataset [21], resulting in a total of 80 $\times$ 79 $\times$ 4 $=$ 25,280
prompts considering any combination of two object categories for each spatial
relationship. For each prompt, we generate a single image. As layout guidance
inputs we split the image canvas into two, vertically or horizontally, to
create two adjacent bounding boxes depending on the type of spatial
relationship defined by the text prompt. This only imposes a weak constraint
on the layout and can be done automatically (no user intervention is
required). For a fair comparison to previous methods, we use the same
detection model (OWL-ViT [23]) as in [9] when computing the VISOR metric.

Second, we evaluate our method on the Flickr30k Entities dataset [26, 43],
which contains image-caption pairs. Since the dataset provides visual
groundings of the textual descriptions, we sample a single caption per image
and its corresponding bounding boxes and use this as input to perform layout-
controlled guidance with SD. We generate a total of 1,000 images using samples
from the validation set. To assess the quality of the generated images, we
compute the FID score between the original images and the generated ones.
Additionally, to measure the accuracy of the generated images with respect to
layout, we apply the Detic [50] detector on the generated images and calculate
average precision (AP) against the ground truth bounding boxes.

Figure 6: Using user-specified bounding boxes, our method allows control over
the size and position of objects inside the generated images. On the left, the
size and position of flamingo changes according to the bounding box. On the
right, we show the ability to control multiple objects.  Figure 7: The top
left is the real image input. The images above the dash are generations using
only text inversion (TI) [8] and Dreambooth [33]. The images under the line
are generated by our method on top of Dreambooth and TI. We achieve control of
the position and orientation, under varying contexts, while preserving the
object’s appearance.

###  4.2 Forward vs. Backward Guidance

First, we compare the two different modes of guidance (forward and backward)
in Table 1 using the VISOR protocol with 1,000 randomly chosen text samples.
The biggest advantage of forward guidance is that the computation overhead is
negligible, thus leading to a faster inference time. We observe that, compared
to (unguided) SD, forward guidance does not increase the likelihood of
generating the objects specified in the text prompt, while the backward
mechanism yields a higher object accuracy. In terms of generating images with
correct spatial relationships, both forward and backward guidance achieve
significantly better results than the SD baseline proving the effectiveness of
both methods. As discussed previously, we also find that the inclusion of
[SoT] and [EoT] in forward guidance also results in better performance. In
addition to the quantitative analysis, we provide a qualitative comparison of
the forward and backward mechanisms in Figure 4. Our findings suggest that the
backward method has better layout control ability and helps to address the
issue of objects occasionally being omitted from the generated images in
diffusion models. Based on these observations, we primarily conducted our
experiments with the backward guidance setting.

###  4.3 Results

##### Evaluation with VISOR Metric.

Next, we compare our method to unguided SD and existing text-to-image
generation methods under the VISOR metric in Table 2. Our method exhibits
remarkable performance under the VISORcond metric, achieving an accuracy of
95.95%. This implies that our method successfully generates images with
accurate spatial relationships as specified in the text prompt, with a very
low error rate. Layout guidance not only improves VISOR metrics but also
increases object accuracy (OA) compared to the baseline (SD). This can be
further explained by looking at the third row of Figure 9: unguided SD
($\text{Scale}=0$) fails to generate the “bear” in an unusual composition.
However, when layout guidance is applied, the “bear” appears, leading to an
improvement in OA. We also note that, while DALLE-v2 [28] achieves the highest
OA overall, it appears to struggle more with layout instructions compared to
SD, as indicated by a lower VISORcond score.

##### Evaluation on Fickr30k Entities.

Further, we compare our backward-guided SD to unguided SD on the Flickr30k
Entities dataset in Table 3. In order to account for errors introduced by the
object detector, we also provide an “upper bound” of performance. This is
computed by applying the same detector (Detic [50]) to the ground truth images
corresponding to the input prompts. Our method slightly increases the FID
while achieving a substantial improvement in terms of AP, which we use to
measure layout faithfulness. On the AP over the person class (APP) and mAP, we
achieve 73% and 92% improvement over the SD baseline. Our results strongly
suggest that our method is capable of achieving robust control when utilizing
bounding box inputs to guide SD. This is achieved without requiring any
modifications to the parameters of SD or any additional training.

##### Qualitative Results for Layout Control.

In Figure 5, we provide a qualitative comparison of different text-to-image
models using text prompts sampled from [9]. Our results demonstrate that, in
the absence of explicit layout guidance, none of the image generators are
capable of accurately inferring the spatial relationships between objects
based purely on textual input, and often fail at generating one or both
objects. However, by incorporating layout guidance into SD (Ours), it becomes
possible to accurately position objects within a scene, even when they are
rarely seen together, such as “snowboard” and “bowl”. More examples are shown
in Figure 6. Our approach provides precise control over the _size_ and
_position_ of one or more objects, including unconventional object categories,
such as “flamingo” or “pikachu”, and atypical scene compositions.

##### Qualitative Results for Real Image Editing.

Finally, we showcase the potential of backward layout guidance in editing real
images. To achieve this, we leverage text inversion and Dreambooth as
described in Section 3.3. We show qualitative examples of this process in
Figure 7, confirming that our method effectively changes the position,
gesture, and orientation of the “dog” (based on the aspect ratio of the
bounding box) to fit the new context without altering its identity. As shown
in Figure 7, the capability to precisely control object size and position
cannot be attained through Dreambooth/TI alone. This highlights the potential
of our method in a wide range of applications related to image editing and
manipulation.

Figure 8: The cross-attention map of the word “cat” at different layers of the
denoising network (top to bottom) across timesteps (left to right).  Figure 9:
Qualitative comparison of different loss scales in the backward guidance. We
increase the loss scale from left to right keeping the same prompt and random
seed. With increasing scale, the generated objects are more tightly
constrained inside the given bounding boxes. However, for very high scales,
fidelity decreases significantly.

###  4.4 Further Analysis

Finally, we investigate how various factors, such as different layers, the
number of inference steps, and the loss scale, affect the performance of
layout guidance.

##### Cross-attention Layers and Guidance Steps.

Cross-attention maps at various layers of the denoising network are presented
in Figure 8. We observe that the down-sampling layers of U-Net do not capture
much information about the object (here, the “cat”). Therefore, we found it
most effective to perform backward guidance only on the mid and up-sampling
blocks of U-Net. The figure also illustrates that object outlines are
typically generated in the early stages of the diffusion process, before
$T=20$. Based on our experimentation, we find that 10-20 steps are generally
suitable for guidance. Additional quantitative analysis and examples are
presented in Appendix B.

##### Analysis on the Loss Scale.

In Figure 9, we qualitatively analyze the impact of the loss scale. We observe
that increasing the loss scale leads to stronger control over the generated
images, but at the cost of some fidelity, particularly with higher scales. The
optimal loss scale setting depends on the difficulty of the text prompt. For
example, an atypical prompt like “a sink above a bear” requires stronger
guidance to generate both objects successfully (without guidance, _i.e_.,
$\text{Scale}=0$, the bear is not generated). This suggests that layout
guidance helps the generator “recognize” multiple objects in the text prompt.

##  5 Conclusions

In this paper, we investigated the potential of manipulating the spatial
layout of images generated by large, pre-trained text-to-image models without
additional training or fine-tuning. Through our exploration, we discovered
that cross-attention maps play a dominant role in determining the layout and
that even the cross-attention maps of start and padding contain valuable
semantic and spatial information. We proposed and compared two approaches,
forward and backward guidance, for layout-controlled generation by modifying
cross-attention patterns explicitly. Our quantitative and qualitative
evaluations demonstrated the effectiveness of both methods. Additionally, we
extended our approach to real image layout editing, illustrating the
versatility of our training-free strategy. In future work, we plan to delve
deeper into cross-attention maps to control object geometry and apply our
approach to 3D model generation.

##### Ethics.

We use the Flick30K Entities and MS-COCO datasets in a manner compatible with
their terms. Some of these images may accidentally contain faces or other
personal information, but we do not make use of these images or image regions.
For further details on ethics, data protection, and copyright please see
https://www.robots.ox.ac.uk/~vedaldi/research/union/ethics.html.

##### Acknowledgements.

This research is supported by ERC-CoG UNION 101001212.

## References

  * [1] Arpit Bansal, Hong-Min Chu, Avi Schwarzschild, Soumyadip Sengupta, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Universal guidance for diffusion models.  arXiv preprint arXiv:2302.07121, 2023.
  * [2] Guillaume Couairon, Jakob Verbeek, Holger Schwenk, and Matthieu Cord.  Diffedit: Diffusion-based semantic image editing with mask guidance.  arXiv preprint arXiv:2210.11427, 2022.
  * [3] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  Advances in Neural Information Processing Systems, 34:8780–8794, 2021.
  * [4] Ming Ding, Zhuoyi Yang, Wenyi Hong, Wendi Zheng, Chang Zhou, Da Yin, Junyang Lin, Xu Zou, Zhou Shao, Hongxia Yang, et al.  Cogview: Mastering text-to-image generation via transformers.  Advances in Neural Information Processing Systems, 34:19822–19835, 2021.
  * [5] Wan-Cyuan Fan, Yen-Chun Chen, DongDong Chen, Yu Cheng, Lu Yuan, and Yu-Chiang Frank Wang.  Frido: Feature pyramid diffusion for complex scene image synthesis.  arXiv preprint arXiv:2208.13753, 2022.
  * [6] Weixi Feng, Xuehai He, Tsu-Jui Fu, Varun Jampani, Arjun Reddy Akula, Pradyumna Narayana, Sugato Basu, Xin Eric Wang, and William Yang Wang.  Training-free structured diffusion guidance for compositional text-to-image synthesis.  In The Eleventh International Conference on Learning Representations, 2023.
  * [7] Oran Gafni, Adam Polyak, Oron Ashual, Shelly Sheynin, Devi Parikh, and Yaniv Taigman.  Make-a-scene: Scene-based text-to-image generation with human priors.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XV, pages 89–106. Springer, 2022.
  * [8] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or.  An image is worth one word: Personalizing text-to-image generation using textual inversion.  arXiv preprint arXiv:2208.01618, 2022.
  * [9] Tejas Gokhale, Hamid Palangi, Besmira Nushi, Vibhav Vineet, Eric Horvitz, Ece Kamar, Chitta Baral, and Yezhou Yang.  Benchmarking spatial relationships in text-to-image generation.  arXiv preprint arXiv:2212.10015, 2022.
  * [10] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio.  Generative adversarial nets.  In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2014.
  * [11] 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.
  * [12] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  arXiv preprint arXiv:2208.01626, 2022.
  * [13] Tobias Hinz, Stefan Heinrich, and Stefan Wermter.  Generating multiple objects at spatially distinct locations.  arXiv preprint arXiv:1901.00686, 2019.
  * [14] Jonathan Ho and Tim Salimans.  Classifier-free diffusion guidance.  arXiv preprint arXiv:2207.12598, 2022.
  * [15] Seunghoon Hong, Dingdong Yang, Jongwook Choi, and Honglak Lee.  Inferring semantic layout for hierarchical text-to-image synthesis.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7986–7994, 2018.
  * [16] Lianghua Huang, Di Chen, Yu Liu, Yujun Shen, Deli Zhao, and Jingren Zhou.  Composer: Creative and controllable image synthesis with composable conditions.  arXiv preprint arXiv:2302.09778, 2023.
  * [17] Xun Huang, Arun Mallya, Ting-Chun Wang, and Ming-Yu Liu.  Multimodal conditional image synthesis with product-of-experts gans.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XVI, pages 91–109. Springer, 2022.
  * [18] Justin Johnson, Agrim Gupta, and Li Fei-Fei.  Image generation from scene graphs.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1219–1228, 2018.
  * [19] Bahjat Kawar, Shiran Zada, Oran Lang, Omer Tov, Huiwen Chang, Tali Dekel, Inbar Mosseri, and Michal Irani.  Imagic: Text-based real image editing with diffusion models.  arXiv preprint arXiv:2210.09276, 2022.
  * [20] 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.  arXiv preprint arXiv:2301.07093, 2023.
  * [21] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In Proceedings of the European Conference on Computer Vision (ECCV), 2014.
  * [22] Nan Liu, Shuang Li, Yilun Du, Antonio Torralba, and Joshua B Tenenbaum.  Compositional visual generation with composable diffusion models.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XVII, pages 423–439. Springer, 2022.
  * [23] Matthias Minderer, Alexey Gritsenko, Austin Stone, Maxim Neumann, Dirk Weissenborn, Alexey Dosovitskiy, Aravindh Mahendran, Anurag Arnab, Mostafa Dehghani, Zhuoran Shen, et al.  Simple open-vocabulary object detection with vision transformers.  arXiv preprint arXiv:2205.06230, 2022.
  * [24] Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishkin, Bob McGrew, Ilya Sutskever, and Mark Chen.  Glide: Towards photorealistic image generation and editing with text-guided diffusion models.  arXiv preprint arXiv:2112.10741, 2021.
  * [25] Taesung Park, Ming-Yu Liu, Ting-Chun Wang, and Jun-Yan Zhu.  Semantic image synthesis with spatially-adaptive normalization.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2337–2346, 2019.
  * [26] Bryan A. Plummer, Liwei Wang, Christopher M. Cervantes, Juan C. Caicedo, Julia Hockenmaier, and Svetlana Lazebnik.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  International Journal of Computer Vision (IJCV), 2017.
  * [27] 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.
  * [28] 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.
  * [29] 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.
  * [30] Scott Reed, Zeynep Akata, Xinchen Yan, Lajanugen Logeswaran, Bernt Schiele, and Honglak Lee.  Generative adversarial text to image synthesis.  In International conference on machine learning, pages 1060–1069. PMLR, 2016.
  * [31] 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 Conference on Computer Vision and Pattern Recognition (CVPR), pages 10684–10695, 2022.
  * [32] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In MICCAI, 2015.
  * [33] 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.  arXiv preprint arXiv:2208.12242, 2022.
  * [34] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Raphael Gontijo-Lopes, Burcu Karagol Ayan, Tim Salimans, Jonathan Ho, David J. Fleet, and Mohammad Norouzi.  Photorealistic text-to-image diffusion models with deep language understanding.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [35] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al.  Laion-5b: An open large-scale dataset for training next generation image-text models.  arXiv preprint arXiv:2210.08402, 2022.
  * [36] Wei Sun and Tianfu Wu.  Image synthesis from reconfigurable layout and style.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10531–10540, 2019.
  * [37] Tristan Sylvain, Pengchuan Zhang, Yoshua Bengio, R Devon Hjelm, and Shikhar Sharma.  Object-centric image generation from layouts.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2647–2655, 2021.
  * [38] Ming Tao, Hao Tang, Fei Wu, Xiao-Yuan Jing, Bing-Kun Bao, and Changsheng Xu.  Df-gan: A simple and effective baseline for text-to-image synthesis.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16515–16525, 2022.
  * [39] Dani Valevski, Matan Kalman, Yossi Matias, and Yaniv Leviathan.  Unitune: Text-driven image editing by fine tuning an image generation model on a single image.  arXiv preprint arXiv:2210.09477, 2022.
  * [40] Tao Xu, Pengchuan Zhang, Qiuyuan Huang, Han Zhang, Zhe Gan, Xiaolei Huang, and Xiaodong He.  Attngan: Fine-grained text to image generation with attentional generative adversarial networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1316–1324, 2018.
  * [41] Zuopeng Yang, Daqing Liu, Chaoyue Wang, Jie Yang, and Dacheng Tao.  Modeling image composition for complex scene generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7764–7773, 2022.
  * [42] Zhengyuan Yang, Jianfeng Wang, Zhe Gan, Linjie Li, Kevin Lin, Chenfei Wu, Nan Duan, Zicheng Liu, Ce Liu, Michael Zeng, et al.  Reco: Region-controlled text-to-image generation.  arXiv preprint arXiv:2211.15518, 2022.
  * [43] Peter Young, Alice Lai, Micah Hodosh, and Julia Hockenmaier.  From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions.  TACL, 2014.
  * [44] Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang, Burcu Karagol Ayan, et al.  Scaling autoregressive models for content-rich text-to-image generation.  arXiv preprint arXiv:2206.10789, 2022.
  * [45] Han Zhang, Jing Yu Koh, Jason Baldridge, Honglak Lee, and Yinfei Yang.  Cross-modal contrastive learning for text-to-image generation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 833–842, 2021.
  * [46] Han Zhang, Tao Xu, Hongsheng Li, Shaoting Zhang, Xiaogang Wang, Xiaolei Huang, and Dimitris N Metaxas.  Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 5907–5915, 2017.
  * [47] Han Zhang, Tao Xu, Hongsheng Li, Shaoting Zhang, Xiaogang Wang, Xiaolei Huang, and Dimitris N Metaxas.  Stackgan++: Realistic image synthesis with stacked generative adversarial networks.  IEEE transactions on pattern analysis and machine intelligence, 41(8):1947–1962, 2018.
  * [48] Lvmin Zhang and Maneesh Agrawala.  Adding conditional control to text-to-image diffusion models.  arXiv preprint arXiv:2302.05543, 2023.
  * [49] Bo Zhao, Lili Meng, Weidong Yin, and Leonid Sigal.  Image generation from layout.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8584–8593, 2019.
  * [50] Xingyi Zhou, Rohit Girdhar, Armand Joulin, Philipp Krähenbühl, and Ishan Misra.  Detecting twenty-thousand classes using image-level supervision.  In Proceedings of the European Conference on Computer Vision (ECCV), 2022.

This appendix contains the following parts:

  * •

Implementation Details. We provide more details of the experimental settings,
including the network architecture, noise scheduler, and evaluation protocol
and metrics.

  * •

Ablation Study. We provide a quantitative evaluation to better understand the
effects of different components and hyper-parameter choices. Specifically, we
explore the effects of different layers and loss scale factor.

  * •

Analysis on Different Tokens. We visualize the cross-attention map of
different prompts and provide extra experiments about controlling the layout
of the generated image with only padding tokens.

  * •

More Examples. We provide additional examples of our method, including
examples under VISOR [9] protocol and real image editing examples.

##  Appendix A Implementation Details

We provide additional details of our experimental settings.

##### Network Architecture.

In all experiments, we use the Stable Diffusion (SD) V-1.5 [31] as our base
model without any architecture modification. The diffusion model is trained in
the latent space of an autoencoder. Specifically, the diffusion model adopts
the U-Net [32] architecture with a relative downsampling factor of 8. The
down-sampling branch of the U-Net has three sequential cross-attention blocks.
The mid part of the U-Net has only one cross-attention block. The up-sampling
branch of the U-Net has three sequential cross-attention blocks. In each
cross-attention block, there are repeated layers following the order: ResBlock
$\rightarrow$ Self-Attention $\rightarrow$ Cross-Attention. The cross-
attention blocks in the down-sampling branch, mid part, and up-sampling have
2, 1, and 3 such repeated patterns, respectively.

##### Noise Scheduler.

The LMSDscheudler is utilized in all of our experiments with 51 time steps and
beta values starting at 0.00085 and ending at 0.012, following a linear
scheduler. We also adopt class-free guidance, as suggested in [14], with a
guidance scale of 7.5, consistent with prior work [31].

##### Evaluation Protocol and Metrics.

Unless otherwise specified, we perform most of our experiments on the
Flickr30K Entities dataset [43], which allows us to evaluate our approach
quantitatively as it provides both image-caption pairs and the visual
grounding (bounding boxes) for relevant words in each caption. We use an open-
vocabulary object detector (Detic [50]) to obtain the respective grounding on
generated images, which allows quantifying _layout fidelity_ using common
detection metrics such as average precision. For each image, the target
vocabulary for Detic is defined by the grounded entities in the corresponding
caption. To avoid contaminating the evaluation process with perceived human
attributes (such as gender, age, occupation, etc.), we convert all instances
of people (man, woman, child, boy, girl, policeman, student, etc.) to the
super-class “person” in the target vocabulary for Detic. Since then the person
category is predominant, we calculate average precision separately for this
category (AP${}_{\mathrm{p}})$ but also report the mean average precision
across all categories (mAP).

##  Appendix B Ablation Study

Base Model | Down-1 | Down-2 | Down-3 | Mid-1 | Up-1 | Up-2 | Up-3 |  FID ($\downarrow$) |  APp ($\uparrow$) |  mAP ($\uparrow$)
---|---|---|---|---|---|---|---|---|---|---
Stable Diffusion [31] | ✓ | ✓ | ✓ |  |  |  |  | 81.3 | 31.1 | 13.2
✓ |  |  |  |  |  |  | 83.5 | 23.1 | 10.0
| ✓ |  |  |  |  |  | 82.0 | 24.0 | 10.9
|  | ✓ |  |  |  |  | 82.2 | 34.5 | 14.2
|  |  | ✓ |  |  |  | 82.1 | 30.0 | 15.2
|  |  | ✓ | ✓ |  |  | 82.0 | 33.5 | 16.7
|  |  | ✓ |  | ✓ |  | 86.3 | 30.9 | 14.0
|  |  | ✓ |  |  | ✓ | 84.1 | 23.5 | 10.5
|  |  |  | ✓ | ✓ | ✓ | 84.5 | 35.6 | 16.5
|  |  |  | ✓ |  |  | 81.2 | 36.0 | 15.1
|  |  |  |  | ✓ |  | 87.5 | 35.0 | 14.3
|  |  |  |  |  |  | ✓ | 85.0 | 25.6 | 9.8
Table 4: Ablation study of loss constraints on different layers. Loss Scale |  FID ($\downarrow$) |  APp ($\uparrow$) |  mAP ($\uparrow$)
---|---|---|---
5 | 82.5 | 28.3 | 12.4
10 | 82.0 | 30.0 | 14.5
20 | 81.1 | 34.7 | 15.4
30 | 81.9 | 33.5 | 16.7
50 | 83.8 | 35.8 | 15.6
100 | 88.4 | 34.9 | 14.3
200 | 99.2 | 32.2 | 13.8
500 | 129.7 | 26.2 | 9.2
Table 5: Ablation study of the loss scale factor.

In this section, we supplement the ablation studies in the main paper with
quantitative evaluations, studying the impact of the loss scale factor and the
effect of backward guidance of cross-attention maps across different layers.
We followed the same setting as described above and in Section 4.1 (main
paper) using 1000 captions and their corresponding bounding boxes from the
Flickr30K Entities [26] dataset to generate images with a pre-specified
layout.

##### Impact of Layers.

First, we study the behavior of different layers, by applying backward
guidance on the cross-attention maps across different layers of the network.
The results are shown in Table 4. As stated in Section 4.4 and illustrated in
the table, layers of the down-sampling branch are the least likely to conform
to layout control (with Down-1 $<$ Down-2 $<$ Down-3 in terms of mAP). In
general, high-resolution blocks (such as Down-1 or Up-3) should not be used to
control the layout. To achieve the best trade-off between image quality and
layout control, a combination of the mid-block (Mid-1) and the first cross-
attention block in up-sampling branch (Up-1) of the U-Net is the optimal
choice overall.

##### Impact of Loss Scale Factor.

We follow the same setup to evaluate the scale factor $\eta_{t}$ used as the
strength of the loss for backward guidance. In Table 5 we report the FID, APp
and mAP for different loss scale factors. When the loss scale is set to 5–50,
the FID is low compared to a larger loss scale factor, indicating that the
quality with a loss scale factor of 5–50 is generally good. To achieve better
control over the layout, the loss scale factors of 20–50 have the lowest APp
and mAP. According to the experiments, a loss scale factor of 20–50 works
generally well. This factor can be adjusted by the user to get more realistic
images or achieve better control over the layout.

##  Appendix C Analysis on Different Tokens

Next, we study the type of information carried by different tokens and their
corresponding cross-attention maps, which is relevant for layout guidance.

##### Removing Word Tokens.

We first show that the padding tokens convey a significant amount of semantic
information. In Figure 10, we randomly pick a subset of captions from MSCOCO
[21] and generate images using the Stable Diffusion model and the full caption
as the input prompt. As a comparison, after the captions pass through the text
encoder, we replace the token embeddings of each caption with the embeddings
of its corresponding padding tokens, thus creating a prompt that consists only
of padding tokens. Then, we use this prompt to generate images. Surprisingly,
despite only generating from padding (_i.e_., non-word) token embeddings, we
observe that the generated images (Word Drop in Figure 10) closely follow both
the semantics and the layout of the image generated from the full-text prompt.
Thus, the figure clearly demonstrates that the padding tokens contain the
information of the whole sentence. This further justifies why in forward
guidance padding tokens cannot be ignored, _i.e_., it would be insufficient to
attempt to control selected word tokens only (main paper, Figure 4). In
backward guidance, however, controlling the cross-attention maps of padding
tokens is not necessary; this is now done by back-propagating and updating the
latent, which subsequently changes the cross-attention maps of all tokens,
even those that are not explicitly controlled.

Figure 10: Generating images without “seeing” the full-text prompt. We replace
the token embeddings for all words in each caption with their padding token
embeddings (word drop). We observe that the generated images after word
dropping exhibit similar semantics and layout to the images generated from the
full-text prompt, suggesting that significant information about the image is
contained in padding tokens. Figure 11: Visualization of cross-attention maps
of start token ([SoT]) and padding tokens ([EoT]) at the final step of
inference. Cross-attention maps are taken from the first cross-attention block
of the up-sampling branch of U-Net and averaged over all attention heads.

##### Cross-Attention Maps of Special Tokens.

During our experiments, we found that the cross-attention of the padding
tokens has a strong connection to the foreground of the generated images. We
illustrated this in Figure 3 (main paper), which shows that the cross-
attention maps of padding tokens resemble saliency maps, while the cross-
attention maps of the start tokens are mostly complementary to those of
padding tokens (_i.e_., they capture what can be considered as background). In
Figure 11, we show more examples of the cross-attention maps of the start and
padding tokens. The captions are randomly taken from MSCOCO [21]. This figure
further highlights the observation that cross-attention maps of these special
tokens contain important semantic and spatial information. For example, in the
first row, given “A short train traveling through a mountainous landscape” as
the input prompt, the cross-attention map of the padding tokens aligns with
the generated train and the start token focuses on the background of the
generated image.

##### Layout Control with Only Padding Tokens.

Motivated by the examples above, we perform backward guidance only on the
cross-attention maps of padding tokens to control the spatial layout of all
foreground objects simultaneously (as a group). Some examples are shown in
Figure 12. This figure verifies our assumption that by guiding the cross-
attention map of the padding tokens alone one can control the composition of
the images at the foreground/background level.

Figure 12: Backward guidance _only_ on the _padding_ tokens. We observe that
the cross-attention of padding tokens typically represents the foreground of
the generated image. Therefore, by spatially guiding the cross-attention maps
that correspond to padding tokens, we can control the position of the
foreground, which may include multiple objects (e.g., “pikachu” and
“basketball”).

##  Appendix D More Examples.

##### More Examples under VISOR Protocol.

We show more examples under the VISOR protocol in Figure 13 and Figure 14. Our
method generates the correct spatial relationships as shown in the figures.
There are also some failure cases, such as the last row in Figure 13. Our
method fails to generate both a fork and a carrot. This is an inherited
problem from the Stable Diffusion model. However, in most cases, layout
guidance helps generate _all_ entities in the text prompt, even when the
unguided Stable Diffusion fails (_e.g_., as is often the case with atypical
scene compositions), as well as conforming to a specific spatial arrangement.

Figure 13: Qualitative comparison between different generative models. For
each prompt, we generate four images. Some images of other models are from the
demo website of [9]. Figure 14: Qualitative comparison between different
generative models. For each prompt, we generate four images. Some images of
other models are from the demo website of [9].

##### More Image Editing Examples.

We show more examples of real image editing in Figure 7. Specifically, we
train for 500 steps to learn the embedding of $\langle*\rangle$ with text
inversion and then 150 steps fine-tuning of the text encoder and denoiser
network with Dreambooth. After finalizing the model, we perform inference with
our backward guidance using different text prompts and user-specified bounding
boxes. As shown in the figure, we manage to change the context, layout, and
style of the given real image.

Figure 15: More examples of real image editing. $\langle*\rangle$ is the
learned token that encodes the object in the real image.


# A New Variation of Hat Guessing Games

Tengyu Ma Xiaoming Sun Huacheng Yu

Institute for Theoretical Computer Science
Tsinghua University, Beijing, China
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Several variations of hat guessing games have been popularly discussed in
recreational mathematics. In a typical hat guessing game, after initially
coordinating a strategy, each of $n$ players is assigned a hat from a given
color set. Simultaneously, each player tries to guess the color of his/her own
hat by looking at colors of hats worn by other players. In this paper, we
consider a new variation of this game, in which we require at least $k$
correct guesses and no wrong guess for the players to win the game, but they
can choose to “pass”.

A strategy is called perfect if it can achieve the simple upper bound
$\frac{n}{n+k}$ of the winning probability. We present sufficient and
necessary condition on the parameters $n$ and $k$ for the existence of perfect
strategy in the hat guessing games. In fact for any fixed parameter $k$, the
existence of perfect strategy can be determined for every sufficiently large
$n$.

In our construction we introduce a new notion: $(d_{1},d_{2})$-regular
partition of the boolean hypercube, which is worth to study in its own right.
For example, it is related to the $k$-dominating set of the hypercube. It also
might be interesting in coding theory. The existence of
$(d_{1},d_{2})$-regular partition is explored in the paper and the existence
of perfect $k$-dominating set follows as a corollary.

Keywords: Hat guessing game; perfect strategy; hypercube; k-dominating set;
perfect code

##  1 Introduction

Several different hat guessing games have been studied in recent years [1, 2,
3, 4, 5, 6, 7]. In this paper we investigate a variation where players can
either give a guess or pass. It was first proposed by Todd Ebert in [3]. In a
standard setting there are $n$ players sitting around a table, who are allowed
to coordinate a strategy before the game begins. Each player is assigned a hat
whose color is chosen randomly and independently with probability $1/2$ from
two possible colors, red and blue. Each player is allowed to see all the hats
but his own. Simultaneously, each player guesses its own hat color or passes,
according to their pre-coordinated strategy. If at least one player guesses
correctly and no player guesses wrong, the players win the game. Their goal is
to design a strategy to maximum their winning probability.

By a simple counting argument there is an upper bound of the maximum winning
probability, $n/(n+1)$. It is known that this upper bound can be achieved if
and only if $n$ has the form $2^{t}-1$ [3]. It turns out that the existence of
such perfect strategy that achieves the upper bound corresponds to the
existence of perfect 1-bit error-correcting code in $\\{0,1\\}^{n}$.

In this paper, we present a natural generalization of Ebert’s hat guessing
problem: The setting is the same as in the original problem, every player can
see all other hats except his own, and is allowed to guess or pass. However,
the requirement for them to win the game is generalized to be that at least
$k$ players from them should guess correctly, and no player guesses wrong
($1\leq k\leq n$). Note that when $k=1$, it is exactly the original problem.

We denote by $P_{n,k}$ the maximum winning probability of players. Similarly
to the $k=1$ case, $P_{n,k}$ has a simple upper bound
$P_{n,k}\leq\frac{n}{n+k}$. We call a pair $(n,k)$ perfect if this upper bound
can be achieved, i.e. $P_{n,k}=\frac{n}{n+k}$. There is a simple necessary
condition for a pair $(n,k)$ to be perfect, and our main result states that
this condition is almost sufficient:

######  Theorem 1.

For any $d,k,s\in\mathbb{N}$ with $s\geq 2\lceil\lg k\rceil$,
$(d(2^{s}-k),dk)$ is perfect, in particular, $(2^{s}-k,k)$ is perfect.

There exists pair $(n,k)$ with the necessary condition but not perfect, see
the remark in Section 4.

Here is the outline of the proof: first we give a general characterization of
the winner probability $P_{n,k}$ by using the size of the minimum
$k$-dominating set of the hypercube. Then we convert the condition of $(n,k)$
perfect to some kind of regular partition of the hypercube (see the definition
in Section 2). Our main contribution is that we present a strong sufficient
condition for the existence of such partition, which nearly matches the
necessary condition. Then we can transform it into a perfect hat guessing
strategy.

As a corollary of Theorem 1, we also give asymptotic characterization of the
value $P_{n,k}$. For example, we show that for any fixed $k$, the maximum
winning probability approaches 1 as $n$ tends to the infinity.

Related work:

Feige [4] considered some variations including the discarded hat version and
the everywhere balanced version. Lenstra and Seroussi [6] studied the case
that $n$ is not of form $2^{m}-1$, they also considered the case with multiple
colors. In [2], Butler, Hajiaghayi, Kleinberg and Leighton considered the
worst case of hat placement with sight graph $G$, in which they need to
minimize the maximum wrong guesses over all hat placements. In [5] Feige
studied the case that each player can see only some of other players’ hats
with respect to the sight graph $G$. In [7], Peterson and Stinson investigated
the case that each player can see hats in front of him and they guess one by
one. Very recently, Buhler, Butler, Graham and Tressler [1] studied the case
that every player needs to guess and the players win the game if either
exactly $k_{1}$ or $k_{2}$ players guess correctly, they showed that the
simple necessary condition is also sufficient in this game.

The rest of the paper is organized as follows: Section 2 describes the
definitions, notations and models used in the paper. Then, Section 3 presents
the result of the existence of $(d_{1},d_{2})$-regular partition of hypercube
while Section 4 shows the main result of the hat guessing game. Finally, we
conclude the paper in Section 5 with some open problems.

##  2 Preliminaries

We use $Q_{n}$ to denote the the $n$ dimension boolean hypercube
$\\{0,1\\}^{n}$. Two nodes are adjacent on $Q_{n}$ if they differ by only one
bit. We encode the blue and red color by 0 and 1. Thus the placement of hats
on the $n$ players’ heads can be represented as a node of $Q_{n}$. For any
$x\in Q_{n}$, $x^{(i)}$ is used to indicate the string obtained by flipping
the $i^{th}$ bit of $x$. Throughout the paper, all the operations are over
$\mathbb{F}_{2}$. We will clarify explicitly if ambiguity appears.

Here is the model of the hat guessing game we consider in this paper: The
number of players is denoted by $n$ and players are denoted by
$p_{1},\ldots,p_{n}$. The colors of players’ hats will be denoted to be
$h_{1},\dots,h_{n}$, which are randomly assigned from $\\{0,1\\}$ with equal
probability. $h=(h_{1},\ldots,h_{n})$. Let $h_{-i}\in Q_{n-1}$ denote the
tuple of colors $(h_{1},\dots,h_{i-1},h_{i+1},\dots,h_{n})$ that player
$p_{i}$ sees on the others’ heads. The strategy of player $p_{i}$ is a
function $s_{i}:Q_{n-1}\rightarrow\\{0,1,\bot\\}$, which maps the tuple of
colors $h_{-i}$ to $p_{i}$’s answer, where $\bot$ represents $p_{i}$ answers
“pass” (if some player answers pass, his answer is neither correct nor wrong).
A strategy $\mathcal{S}$ is a collection of $n$ functions
$(s_{1},\ldots,s_{n})$. The players win the game if at least $k$ of them guess
correctly and no one guesses wrong. We use $P_{n,k}$ to denote the maximum
winning probability of the players. The following two definitions are very
useful in characterization $P_{n,k}$:

######  Definition 2.

A subset $D\subseteq V$ is called a $k$-dominating set of graph $G=(V,E)$ if
for every vertex $v\in V\setminus D$, $v$ has at least $k$ neighbors in $D$.

######  Definition 3.

A partition $(V_{1},V_{2})$ of hypercube $Q_{n}$ is called a
$(d_{1},d_{2})$-regular partition if each node in $V_{1}$ has exactly $d_{1}$
neighbors in $V_{2}$, and each node in $V_{2}$ has exactly $d_{2}$ neighbors
in $V_{1}$.

For example, consider the following partition $(V_{1},V_{2})$ of $Q_{3}$:
$V_{1}=\\{000,111\\}$, and $V_{2}=Q_{3}\setminus V_{1}$. For each vertex in
$V_{1}$, there are $3$ neighbors in $V_{2}$, and for each vertex in $V_{2}$,
there is exactly one neighbor in $V_{1}$. Thus $(V_{1},V_{2})$ forms a
$(3,1)$-regular partition of $Q_{3}$.

##  3 ($d_{1},d_{2}$)-Regular Partition of $Q_{n}$

In this section we study the existence of $(d_{1},d_{2})$-regular partition of
$Q_{n}$.

######  Proposition 4.

Suppose $d_{1},d_{2}\leq n$, if there exists a $(d_{1},d_{2})$-regular
partition of hypercube $Q_{n}$, then the parameters $d_{1},d_{2},n$ should
satisfy $d_{1}+d_{2}=\gcd(d_{1},d_{2})2^{s}$ for some $s\leq n$.

###### Proof.

Suppose the partition is $(V_{1},V_{2})$, we count the total number of
vertices

$\left|V_{1}\right|+\left|V_{2}\right|=2^{n},$

and the number of edges between two parts

$d_{1}\left|V_{1}\right|=d_{2}\left|V_{2}\right|.$

By solving the equations, we obtain

$\left|V_{1}\right|=\frac{d_{2}}{d_{1}+d_{2}}2^{n},\ \
\left|V_{2}\right|=\frac{d_{1}}{d_{1}+d_{2}}2^{n}.$

Both $\left|V_{1}\right|$ and $\left|V_{2}\right|$ should be integers,
therefore $d_{1}+d_{2}=\gcd(d_{1},d_{2})2^{s}$ holds, since
$\gcd(d_{1},d_{1}+d_{2})=\gcd(d_{2},d_{1}+d_{2})=\gcd(d_{1},d_{2})$. ∎

######  Proposition 5.

If there exists a $(d_{1},d_{2})$-regular partition of hypercube $Q_{n}$, then
there exists a $(d_{1},d_{2})$-regular partition of $Q_{m}$ for every $m\geq
n$.

###### Proof.

It suffices to show that the statement holds when $m=n+1$, since the desired
result follows by induction. $Q_{n+1}$ can be treated as the union of two
copies of $Q_{n}$ (for example partition according to the last bit), i.e.
$Q_{n+1}=Q_{n}^{(1)}\cup Q_{n}^{(2)}$. Suppose $(V_{1},V_{2})$ is a
$(d_{1},d_{2})$-regular partition of $Q_{n}^{(1)}$. We can duplicate the
partition $(V_{1},V_{2})$ to get another partition
$(V_{1}^{\prime},V_{2}^{\prime})$ of $Q_{n}^{(2)}$. Then we can see that
$(V_{1}\cup V_{1}^{\prime},V_{2}\cup V_{2}^{\prime})$ forms a partition of
$Q_{n+1}$, in which each node has an edge to its duplicate through the last
dimension. Observe that each node in $V_{1}$ ($V_{1}^{\prime}$) still has
$d_{1}$ neighbors in $V_{2}$ ($V_{2}^{\prime}$) and same for $V_{2}$
($V_{2}^{\prime}$), and the new edges introduced by the new dimension are
among $V_{1}$ and $V_{1}^{\prime}$, or $V_{2}$ and $V_{2}^{\prime}$, which
does not contribute to the edges between two parts of the partition. Therefore
we constructed a $(d_{1},d_{2})$-regular partition of $Q_{n+1}$. ∎

######  Proposition 6.

If there exists a $(d_{1},d_{2})$-regular partition of $Q_{n}$, then there
exists $(td_{1},td_{2})$-regular partition of $Q_{tn}$, for any positive
integer $t$.

###### Proof.

Suppose $(V_{1},V_{2})$ is a $(d_{1},d_{2})$-regular partition of $Q_{n}$. Let
$x=x_{1}x_{2}\cdots x_{nt}$ be a node in $Q_{nt}$. We can divide $x$ into $n$
sections of length $t$, and denote the sum of $i^{th}$ section by $w_{i}$,
i.e.

$w_{i}(x)=\sum_{j=ti-t+1}^{ti}x_{j},\ \ (1\leq i\leq n).$

Let $R(x)=w_{1}(x)w_{2}(x)\ldots w_{n}(x)\in Q_{n}$. Define

$V_{i}^{\prime}=\\{x\in Q_{nt}|R(x)\in V_{i}\\},\ (i=1,2).$

We claim that $(V_{1}^{\prime},V_{2}^{\prime})$ is a $(td_{1},td_{2})$-regular
partition of $Q_{nt}$. This is because for any vertex $x$ in $V_{1}^{\prime}$,
$R(x)$ is in $V_{1}$. So $R(x)$ has $d_{1}$ neighbors in $V_{2}$, and each of
which corresponds $t$ neighbors of $x$ in $V_{2}^{\prime}$, thus in total
$td_{1}$ neighbors in $V_{2}^{\prime}$. It is the same for vertices in
$V_{2}^{\prime}$. ∎

By Proposition 4-6 we only need to consider the existence of
$(d_{1},d_{2})$-regular partition of $Q_{n}$ where $\gcd(d_{1},d_{2})=1$ and
$d_{1}+d_{2}=2^{s}$ (where $s\leq n$), or equivalently, the existence of
$(d,2^{s}-d)$-regular partition of $Q_{n}$, where $s\leq n$ and $d$ is odd.
The following Lemma from [1] showed that when $n=2^{s}-1$ such regular
partition always exists.

######  Lemma 7.

[1] There exists a $(t,2^{s}-t)$-regular partition of $Q_{2^{s}-1}$, for any
integer $s,t$ with $0<t<2^{s}$.

The following theorem shows how to construct the $(t,2^{s}-t)$-regular
partition for $n=2^{s}-r$ (where $r\leq t$).

######  Theorem 8.

Suppose there exists a $(t,2^{s}-t)$-regular partition for $Q_{2^{s}-r}$ and
$t>r$, then there exists a $(t,2^{s}-t)$-regular partition for
$Q_{2^{s+1}-\min\\{t,2r\\}}$.

###### Proof.

For convenience, let $m=2^{s}-r$, and $l=2r-\min\\{t,2r\\}(\geq 0)$. Observe
that $2^{s+1}-\min\\{t,2r\\}=2m+l$, and if $t\geq 2r$ then $l=0$. Suppose that
$(V_{1},V_{2})$ is a $(t,2^{s}-t)$-regular partition for $Q_{m}$. We want to
construct a $(t,2^{s+1}-t)$-regular partition for $Q_{2m+l}$. The basic idea
of the construction is as follows:

We start from set $V_{2}$. We construct a collection of linear equation
systems, each of which corresponds to a node in $V_{2}$. The variables of the
linear systems are the $(2m+l)$ bits of node $x\in Q_{2m+l}$. Let
$V_{2}^{\prime}$ be the union of solutions of these linear equation systems,
and $V_{1}^{\prime}$ be the complement of $V_{2}^{\prime}$. Then
$(V_{1}^{\prime},V_{2}^{\prime})$ is the $(t,2^{s+1}-t)$-regular partition as
we desired.

Here is the construction. Since $(V_{1},V_{2})$ is a $(t,2^{s}-t)$ regular
partition for $Q_{m}$, the subgraph induced by $V_{2}$ of $Q_{m}$ is a
$(t-r)$-regular graph, i.e. for every node $p\in V_{2}$, there are $(t-r)$
neighbors of $p$ in $V_{2}$. For each $p\in V_{2}$, arbitrarily choose a
subset $N(p)\subseteq V_{2}$ of neighbors of node $p$ with size
$\left|N(p)\right|=r-l$. (here $r-l=r-(2r-\min\\{t,2r\\})=\min\\{t,2r\\}-r$,
so $r-l\leq t-r$, and $r-l>0$ since $t>r$)

Now for each node $p=(p_{1},\dots,p_{m})\in V_{2}$, we construct a linear
equation system as follows:

$\begin{cases}x_{1}+x_{2}=p_{1},\\\ x_{3}+x_{4}=p_{2},\\\ \ \ldots\ \ \ldots\
\ \ldots,\\\ x_{2m-1}+x_{2m}=p_{m},\\\ \sum_{j=1}^{m}x_{2j-1}+\sum_{j\in
N(p)}x_{2j}+\sum_{1\leq j\leq l}x_{2m+j}=0.\\\ \end{cases}$ (1)

Note that in the last equation the last term $\sum_{1\leq j\leq l}x_{2m+j}$
vanishes if $l=0$. Denote by $S(p)\subseteq Q_{2m+l}$ the solutions of this
linear system. For convenience, let $f:Q_{2m+l}\rightarrow Q_{m}$ be the
operator such that

$f(x_{1},\ldots,x_{2m+l})=(x_{1}+x_{2},x_{3}+x_{4},\dots,x_{2m-1}+x_{2m}).$

Then in the linear system (1) the first $m$ equations is nothing but $f(x)=p$.

Let $V_{2}^{\prime}=\cup_{p\in V_{2}}S(p)$, and
$V_{1}^{\prime}=Q_{2m+l}\setminus V_{2}^{\prime}$ be its complement. We claim
that $(V_{1}^{\prime},V_{2}^{\prime})$ is a $(t,2^{s+1}-t)$-regular partition
of $Q_{2m+l}$.

To begin with, observe the following two facts.

Observation 1 For every $x\in V_{2}^{\prime}$, we have $f(x)\in V_{2}$. It can
be seen clearly from the first $m$ equations in each equation system.

Observation 2 If $k\leq 2m$, then $f(x^{(2k)})=f(x^{(2k-1)})=(f(x))^{(k)}$. If
$k>2m$, $f(x^{(k)})=f(x)$. Recall the $x^{(i)}$ is the node obtained by
flipping the $i^{th}$ bit of $x$. The observation can be seen from the
definition of $f(x)$.

For any node $x\in V_{1}^{\prime}$, we show that there are $t$ different ways
of flipping a bit of $x$ so that we can get a node in $V_{2}^{\prime}$. There
are two possible cases:

Case 1: $f(x)\not\in V_{2}$. In this case if we flip the $i^{th}$ bit of $x$
for some $i>2m$, then from Observation 2, $f(x^{(i)})=f(x)$, so $f(x^{(i)})$
will remain not in $V_{2}$, and therefore $x^{(i)}$ will not be in
$V_{2}^{\prime}$, by Observation 1. So we can only flip the bit in
$(x_{1},\ldots,x_{2m})$.

Suppose by flipping the $i^{th}$ bit of $x$ we get $x^{(i)}\in V_{2}^{\prime}$
($i\in[2m]$), from the definition of $V_{2}^{\prime}$ we have : $f(x^{(i)})\in
V_{2}$, and $x^{(i)}$ satisfies the last equation in the equation systems
corresponding to $f(x^{(i)})$:

$\sum_{j=1}^{m}x_{2j-1}+\sum_{j\in N(f(x^{(i)}))}x_{2j}+\sum_{1\leq j\leq
l}x_{2m+j}=0.$ (2)

Since $f(x)\notin V_{2}$ and $(V_{1},V_{2})$ is a $(t,2^{s}-t)$-regular
partition of $Q_{m}$, so there are exactly $t$ neighbors of $f(x)$ in $V_{2}$,
which implies there are $t$ bits of $f(x)$ by flipping which we can get a
neighbor of $f(x)$ in $V_{2}$. Let $\\{j_{1},\ldots,j_{t}\\}\subseteq[m]$ be
these bits, i.e. $f(x)^{(j_{1})},\ldots,f(x)^{(j_{t})}\in V_{2}$, by
Observation 2,

$f(x^{(2j_{k}-1)})=f(x^{(2j_{k})})=f(x)^{(j_{k})}\in V_{2},\ \
(k=1,\ldots,t).$

But exactly one of $\\{x^{(2j_{k}-1)},x^{(2j_{k})}\\}$ satisfies the equation
(2) (here we use the fact $f(x)\notin V_{2}$, note that $j_{k}\not\in
N(f(x)^{(j_{k})})$. Thus totally, there are $t$ possible $i$ such that
$x^{(i)}\in V_{2}^{\prime}$.

Case 2: $f(x)\in V_{2}$. Since $x\notin V_{2}^{\prime}$, the last linear
equation must be violated, i.e.

$\sum_{j=1}^{m}x_{2j-1}+\sum_{j\in N(f(x^{(i)}))}x_{2j}+\sum_{1\leq j\leq
l}x_{2m+j}=1.$ (3)

We further consider three cases here: flip a bit in
$\\{x_{1},\ldots,x_{2m}\\}\setminus\\{x_{2j},x_{2j-1}:j\in N(f(x))\\}$; flip a
bit in $\\{x_{2j},x_{2j-1}:j\in N(f(x))\\}$; flip a bit in
$\\{x_{2m+1},\ldots,x_{2m+l}\\}$:

a) if $i\in[m]$ , $i\notin N(f(x))$, and $f(x)^{(i)}\in V_{2}$. Since $f(x)\in
V_{2}$, $(V_{1},V_{2})$ is a $(t,2^{s}-t)$-regular partition of $Q_{m}$, there
are $m-(2^{s}-t)-\left|N(f(x))\right|=(2^{s}-r)-(2^{s}-t)-(r-l)=t-2r+l$ such
index $i$, and $x^{(2i-1)}$ is the exactly the one in
$\\{x^{(2i-1)},x^{(2i)}\\}$ which is in $V_{2}^{\prime}$. (determined by
Equation 3). Thus in this case there are $(t-2r+l)$ neighbors of $x$ in
$V_{2}^{\prime}$.

b) if $i\in N(f(x))$, then both of $x^{(2i-1)},x^{(2i)}$ are in
$V_{2}^{\prime}$, there are $2\cdot\left|N(f(x))\right|=2(r-l)$ such
neighbors.

c) if $i>2m$, then every $x^{(i)}$ is in $V_{2}^{\prime}$,
($i=2m+1,\ldots,2m+l$), there are $l$ such neighbors.

Hence, totally $x$ has $(t-2r+l)+2(r-l)+l=t$ neighbors in $V_{2}^{\prime}$.

The rest thing is to show that every node $x\in V_{2}^{\prime}$ has
$(2^{s+1}-t)$ neighbors in $V_{1}^{\prime}$. The proof is similar to the proof
of Case 2 above, we consider three cases:

a) If $i\in[m]$, $i\not\in N(f(x))$, and $f(x)^{(i)}\in V_{2}$. Then exactly
one of $x^{(2k-1)},x^{(2k)}$ in $V_{2}^{\prime}$, thus there are
$m-(2^{s}-t)-\left|N(f(x))\right|=2^{s}-r-(2^{s}-t)-(r-l)=t-2r+l$ such
neighbors of $x$ in $V_{2}^{\prime}$.

b) If $i\in N(f(x))$ both $x^{(2i-1)},x^{(2i)}$ are not in $V_{2}^{\prime}$.

c) If $i>2m$, then every $x^{(i)}$ is not in $V_{2}^{\prime}$.

Hence totally, $x$ has $(t-2r+l)$ neighbors in $V_{2}^{\prime}$, and therefore
$(2m+l)-(t-2r+l)=2^{s+1}-t$ neighbors in $V_{1}^{\prime}$.

Hence we prove that $(V_{1}^{\prime},V_{2}^{\prime})$ is indeed a
$(t,2^{s+1}-t)$-regular partition of $Q_{2^{s+1}-\min\\{t,2r\\}}$. ∎

######  Theorem 9.

For any odd number $t$ and any $c\leq t$, when $s\geq\lceil\lg
t\rceil+\lceil\lg c\rceil$, there exists a $(t,2^{s}-t)$-regular partition of
$Q_{2^{s}-c}$.

###### Proof.

Let $s_{0}=\lceil\lg t\rceil$. By Lemma 7, there exists a
$(t,2^{s_{0}}-t)$-regular partition of $Q_{2^{s_{0}}-1}$. By repeatedly using
Theorem 8, we obtain that there exists $(t,2^{s_{0}+1}-t)$-regular partition
of $Q_{2^{s_{0}+1}-2}$, $(t,2^{s_{0}+2}-t)$-regular partition of
$Q_{2^{s_{0}+2}-2^{2}}$, etc., $(t,2^{s_{0}+\lceil\lg{c}\rceil-1}-t)$-regular
partition of $Q_{2^{s_{0}+\lceil\lg{c}\rceil-1}-2^{\lceil\lg{c}\rceil-1}}$,
and $(t,2^{s_{0}+\lceil\lg{c}\rceil}-t)$-regular partition of
$Q_{2^{s_{0}+\lceil\lg{c}\rceil}-c}$. By using Proposition 5, we get that
there exists a $(t,2^{s}-t)$-regular partition of $Q_{2^{s}-c}$, for any
$s\geq s_{0}+\lceil\lg{c}\rceil=\lceil\lg t\rceil+\lceil\lg{c}\rceil$. ∎

Combining Proposition 6 and Theorem 9, we have the following corollary.

######  Corollary 10.

Suppose $d_{1}=dt,d_{2}=d(2^{s}-t),n=d(2^{s}-c)$, where $d,t,s$ are positive
integers with $0<t<2^{s}$, $c\leq t$ and $s\geq\lceil\lg c\rceil+\lceil\lg
t\rceil$, then there exists a $(d_{1},d_{2})$-regular partition for $Q_{n}$.

##  4 The Maximum Winning Probability $P_{n,k}$

The following lemma characterizes the relationship between the maximum winner
probability $P_{n,k}$ and the minimum $k$-dominating set of $Q_{n}$. The same
result was showed in [5] for $k=1$.

######  Lemma 11.

Suppose $D$ is a $k$-dominating set of $Q_{n}$ with minimum number of
vertices. Then

$P_{n,k}=1-\frac{|D|}{2^{n}}.$

###### Proof.

Given a $k$-dominating set $D$ of $Q_{n}$, the following strategy will have
winning probability at least $1-\frac{\left|D\right|}{2^{n}}$: For any certain
placement of hats, each player can see all hats but his own, so player $p_{i}$
knows that current placement $h$ is one of two adjacent nodes
$\\{x,x^{(i)}\\}$ of $Q_{n}$. If $x\in D$ (or $x^{(i)}\in D$), he guesses that
the current placement is $x^{(i)}$ (or $x$), otherwise he passes. We claim
that by using this strategy, players win the game when the placement is a node
which is not in $D$. Observe that since $D$ is a $k$-dominating set, for any
node $y\notin D$, $y$ has $l$ neighbors
$y^{(i_{1})},y^{(i_{2})},\ldots,y^{(i_{l})}$ that are in $D$, where $l\geq k$.
According to the strategy desribed, players $p_{i_{1}},\ldots,p_{i_{l}}$ would
guess correctly and all other players will pass. This shows the winning
probability is at least $1-\frac{\left|D\right|}{2^{n}}$.

Next we show that $P_{n,k}\leq 1-\frac{\left|D\right|}{2^{n}}$. Suppose we
have a strategy with winning probability $P_{n,k}$. We prove that there exists
a $k$-dominating set $D_{0}$, such that $|D_{0}|=2^{n}(1-P_{n,k})$. The
construction is straightforward: Let $D_{0}=\\{h\in Q_{n}:h\textrm{ is not a
winning placement}\\}$. Thus $|D_{0}|=N(1-P_{n,k})$. For every winning
placement $h\notin D_{0}$, suppose players $p_{i_{1}},\ldots,p_{i_{l}}$ will
guess correctly ($l\geq k$), consider the placement $h^{(i_{1})}$, which
differs from $h$ only at player $p_{i_{1}}$’s hat, so player $p_{i_{1}}$ will
guess incorrectly in this case, thus $h^{(i_{1})}\in D_{0}$. Similarly
$h^{(i_{2})},\ldots,h^{(i_{l})}\in D_{0}$, therefore $D_{0}$ is a
$k$-dominating set. We have

$|D|\leq|D_{0}|=2^{n}(1-P_{n,k}),$

which implies

$P_{n,k}\leq 1-\frac{\left|D\right|}{2^{n}}.$

Combining these two results, we have $P_{n,k}=1-\frac{\left|D\right|}{2^{n}}$
as desired. ∎

######  Proposition 12.

The following properties hold:

  1. (a)

If $n_{1}<n_{2}$ then $P_{n_{1},k}\leq P_{n_{2},k}$.

  2. (b)

$(n,k)$ is perfect iff there exists a $(k,n)$-regular partition of $Q_{n}$.

  3. (c)

For any $t\in\mathbb{N}$, $P_{nt,kt}\geq P_{n,k}$. As a consequence, if
$(n,k)$ is perfect, $(nt,kt)$ is perfect.

###### Proof.

For part (a), suppose that $D$ is a minimum $k$-dominating set of $Q_{n_{1}}$.
We make $2^{n_{2}-n_{1}}$ copies of $Q_{n_{1}}$, and by combining them we get
a $Q_{n_{2}}$, which has dominating set of size $2^{n_{2}-n_{1}}|D|$. By Lemma
11, $P_{n_{2},k}\geq 1-\frac{2^{n_{2}-n_{1}}|D|}{2^{n_{2}}}=P_{n_{1},k}$.

For part (b), suppose $(U,V)$ is a $(k,n)$-regular partition of $Q_{n}$, note
that $V$ is a $k$-dominating set of $Q_{n}$ and $|V|=\frac{k}{n+k}\cdot
2^{n}$, thus $V$ is a minimum $k$-dominating set of $Q_{n}$. We have that
$P_{n,k}=1-\frac{|V|}{2^{n}}=\frac{n}{n+k}$, which implies that $(n,k)$ is
perfect.

On the other hand, if $(n,k)$ is perfect, suppose $D$ is the minimum
$k$-dominating set, we have $\left|D\right|=\frac{k}{n+k}\cdot 2^{n}$. It can
be observed that $\left(Q_{n}\setminus D,D\right)$ is a $(k,n)$-regular
partition of $Q_{n}$.

For part (c), since $\frac{n}{n+k}=\frac{nt}{nt+kt}$, once $P_{nt,kt}\geq
P_{n,k}$ holds, it’s an immediate consequence that the perfectness of $(n,k)$
implies the perfectness of $(nk,nt)$.

Suppose for $n$ players, we have a strategy $\mathcal{S}$ with probability of
winning $P_{n,k}$. For $nt$ players, we divide them into $n$ groups, each of
which has $t$ players. Each placement $h=(h_{1},h_{2},\ldots,h_{nt})$ of $nt$
players can be mapped to a placement $P(h)$ of $n$ players in the following
way: for Group $i$, suppose the sum of colors in the group is $w_{i}$, i.e.

$w_{i}(h)=\sum_{j=ti-t+1}^{ti}h_{j},\ \ (1\leq i\leq n).$

Let $P(h)=(w_{1}(h),w_{2}(h),\ldots,w_{n}(h))$ be a placement of $n$ players.
Each player in Group $i$ knows the color of all players in $P(h)$ other than
Player $i$, thus he uses Player $i$’s strategy $s_{i}$ in $\mathcal{S}$ to
guess the sum of colors in Group $i$ or passes. Moreover once he knows the
sum, his color can be uniquely determined.

Note that the players in Group $i$ would guess correctly or incorrectly or
pass, if and only if Player $i$ in the $n$-player-game would do. Since the hat
placement is uniformly at random, the probability of winning using this
strategy is at least $P_{n,k}$, thus $P_{nt,kt}\geq P_{n,k}$. ∎

Now we can prove our main theorem:

######  Theorem 1.

For any $d,k,s\in\mathbb{N}$ with $s\geq 2\lceil\lg k\rceil$,
$(d(2^{s}-k),dk)$ is perfect, in particular, $(2^{s}-k,k)$ is perfect.

###### Proof.

It’s an immediate corollary of part (b) of Proposition 12 and Theorem 9. ∎

Remark: By Proposition 4 and Proposition 12(b) there is a simple necessary
condition for $(n,k)$ to be perfect, $n+k=\gcd(n,k)2^{t}$. Theorem 1 indicates
that when $n+k=\gcd(n,k)2^{t}$ and $n$ is sufficiently large, $(n,k)$ is
perfect. The necessary condition and sufficient condition nearly match in the
sense that for each $k$, there’s only a few $n$ that we don’t know whether
$(n,k)$ is perfect. Moreover, the following proposition shows that the simple
necessary condition can’t be sufficient. The first counterexample is $(5,3)$,
it is not perfect while it satisfies the simple necessary condition. But
$(13,3)$ is perfect by Theorem 1 and more generally for all $s\geq 4$,
$(2^{s}-3,3)$ is perfect. We verified by computer program that
$(2^{4}-5,5)=(11,5)$ is not perfect, while by our main theorem
$(2^{6}-5,5)=(59,5)$ is perfect. But we still don’t know whether the case
between them, $(2^{5}-5,5)=(27,5)$, is perfect.

######  Proposition 13.

$(n,k)$ is not perfect unless $2k+1\leq n$ when $n\geq 2$ and $k<n$.

###### Proof.

Suppose $(n,k)$ is perfect. According to part (b) of Proposition 12, we can
find $(U,V)$, a $(k,n)$-regular partition of $Q_{n}$. Suppose $x$ is some node
in $U$, and $y$ is some neighbor of $x$ which is also in $U$, $y$ has $k$
neighbors in $V$. They all differ from $x$ at exactly $2$ bits and one of them
is what $y$ differs from $x$ at, i.e. each of them “dominates” $2$ neighbors
of $x$, one of them is $y$. So $x$ has totally $k+1$ neighbors “dominated” by
$k$ of nodes in $V$. Since all nodes in $V$ are pairwise nonadjacent, these
$k+1$ nodes must be in $U$. Now we have $k+1$ neighbors of $x$ are in $U$ and
$k$ neighbors are in $V$, it has totally $n$ neighbors. We must have $2k+1\leq
n$. ∎

For each odd number $k$, let $s(k)$ be the smallest number such that
$(2^{s(k)}-k,k)$ is perfect. We know that
$s(k)\in[\lceil\lg{k}\rceil,2\lceil\lg{k}\rceil]$. The following proposition
indicates that all $s\geq s(k)$, $(2^{s}-k,k)$ is also perfect.

######  Proposition 14.

If $(2^{s}-k,k)$ is perfect, $(2^{s+1}-k,k)$ is perfect.

###### Proof.

If $(2^{s}-k,k)$ is perfect, by Proposition 12(b) there is a
$(k,2^{s}-k)$-regular partition of $Q_{2^{s}-k}$. Thus by Proposition 5, we
have a $(k,2^{s}-k)$-regular partition of $Q_{2^{s}-k+1}$. Combine this
partition and Theorem 8, we get a $(k,2^{s+1}-k)$-regular partition of
$Q_{2^{s+1}-k}$. Therefore $(2^{s+1}-k,k)$ is perfect. ∎

Using Theorem 1 we can give a general lower bound for the winning probability
$P_{n,k}$. Recall that there’s upper bound $P_{n,k}\leq 1-\frac{k}{n+k}$.

######  Lemma 15.

$P_{n,k}>1-\frac{2k}{n+k}$, when $n\geq 2^{2\lceil\lg k\rceil}-k$.

###### Proof.

Let $n^{\prime}$ be the largest integer of form $2^{t}-k$ which is no more
than $n$. By Theorem 1, $(n^{\prime},k)$ is perfect, i.e.
$P_{n^{\prime},k}=1-\frac{k}{n^{\prime}+k}$. By part (a) of Proposition 12,
$P_{n,k}\geq P_{n^{\prime},k}$. On the other hand we have $n+k<2^{t+1}$, so we
have

$P_{n,k}\geq 1-\frac{k}{n^{\prime}+k}=1-\frac{2k}{2^{t+1}}>1-\frac{2k}{n+k}.$

∎

######  Corollary 16.

For any integer $k>0$, $\lim_{n\rightarrow\infty}P_{n,k}=1$.

##  5 Conclusion

In this paper we investigated the existence of regular partition for boolean
hypercube, and its applications in finding perfect strategies of a new hat
guessing games. We showed a sufficient condition for $(n,k)$ to be perfect,
which nearly matches the necessary condition. Several problems remain open:
for example, determine the minimum value of $s(k)$ such that $(2^{s(k)}-k,k)$
is perfect, and determine the exact value of $P_{n,k}$. It is also very
interesting to consider the case when there are more than two colors in the
game.

## References

  * [1] Joe Buhler, Steve Butler, Ron Graham, and Eric Tressler.  Hypercube orientations with only two in-degrees.  http://arxiv.org/abs/1007.2311, 2010.
  * [2] Steve Butler, Mohammad T. Hajiaghayi, Robert D. Kleinberg, and Tom Leighton.  Hat guessing games.  SIAM J. Discrete Math., 22(2):592–605, 2008.
  * [3] Todd T. Ebert.  Applications of recursive operators to randomness and complexity.  PhD thesis, University of California at Santa Barbara, 1998.
  * [4] Uriel Feige.  You can leave your hat on (if you guess its color).  Technical Report MCS04-03, Computer Science and Applied Mathematics, The Weizmann Institute of Science, 2004.
  * [5] Uriel Feige.  On optimal strategies for a hat game on graphs.  SIAM Journal of Discrete Mathematics, 2010.
  * [6] Hendrik W. Lenstra and Gadiel Seroussi.  On hats and other covers.  http://arxiv.org/abs/cs/0509045, 2005.
  * [7] Maura B . Peterson and Douglas R. Stinson.  Yet another hatt game.  the electronic journal of combinatorics, 17(1), 2010.


See pages 1-last of Reddit_Interactions.pdf