Image Inpainting via Tractable Steering of Diffusion Models
Authors: Anji Liu
Mathias Niepert
Guy Van den Broeck
Venue: ICLR 2024 poster (2024)
Keywords: Probabilistic Methods
Tractable Probabilistic Models
Diffusion Models
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: Diffusion models are the current state of the art for generating photorealistic images. Controlling the sampling process for constrained image generation tasks such as inpainting, however,  remains challenging since exact conditioning on such constraints is intractable. While existing methods use various techniques to approximate the constrained posterior, this paper proposes to exploit the ability of Tractable Probabilistic Models (TPMs) to exactly and efficiently compute the constrained posterior, and to leverage this signal to steer the denoising process of diffusion models. Specifically, this paper adopts a class of expressive TPMs termed Probabilistic Circuits (PCs). Building upon prior advances, we further scale up PCs and make them capable of guiding the image generation process of diffusion models. Empirical results suggest that our approach can consistently improve the overall quality and semantic coherence of inpainted images across three natural image datasets (i.e., CelebA-HQ, ImageNet, and LSUN) with only ~10% additional computational overhead brought by the TPM. Further, with the help of an image encoder and decoder, our method can readily accept semantic constraints on specific regions of the image, which opens up the potential for more controlled image generation tasks. In addition to proposing a new framework for constrained image generation, this paper highlights the benefit of more tractable models and motivates the development of expressive TPMs.

Published as a conference paper at ICLR 2024
IMAGE INPAINTING VIA TRACTABLE STEERING OF DIFFUSION MODELS
Anji Liu', Mathias Niepert", Guy Van den Broeck'
DDepartment of Computer Science. University of California, Los Angeles 2 Department of Computer Science, University of Stuttgart liuanji (cs. ucla. edu, mathias, miepert@simtech uni stuttgart.de, guyvdbêcs cs. ucla. edu,
ABSTRACT
Diffusion models the current state of the art for generating photorealistic images. Controlling the sampling process for constrained image generation tasks such inpainting, however, remains challenging since exact conditioning on such constraints is intractable. While existing methods use various techniques to approximate the constrained posterior, this paper proposes exploit the ability of Tractable Probabilistic Models (TPMs) to exactly and efficiently compute the constrained posterior, and leverage this signal steer the denoising process of diffusion models. Specifically, this paper adopts class of expressive TPMs termed Probabilistic Circuits (PCs). Building upon prior advances, we further scale up PCs and make them capable of guiding the image generation process of diffusion models. Empirical results suggest that our approach can consistently improve the overall quality and semantic coherence of inpainted images across three natural image datasets (i.e., CelebA-HQ, ImageNet, and LSUN) with only 10% additional computational overhead brought by the TPM. Further, with the help of an image encoder and decoder, our method can readily accept semantic constraints on specifie regions of the image, which opens up the potential for more controlled image generation tasks. In addition to proposing new framework for constrained image generation, this paper highlights the benefit of more tractable models and motivates the development of expressive TPMs.
INTRODUCTION
Thanks to their expressiveness, diffusion models have achieved state-of-the-arr results in generating photorealistic and high-resolution images (Ramesh et al. 2022 Nichol & Dhariwal 2021 Rombach et al. 2022). However, steering unconditioned diffusion models toward constrained generation tasks such image inpainting remains challenging. diffusion models do not by design support efficient computation of the posterior sample distribution under many types of constraints (Chung et al.) 2022). This results in samples that fail to properly align with the constraints. For example, in image inpainting, the model may generate samples that are semantically incoherent with the given pixels.
Prior works approach this problem mainly by approximating the (constrained) posterior sample distribution. However, due to the intractable nature of diffusion models, such approaches introduce high bias (Lugmayr al. 2022 Zhang et al., 2023a Chung al. 2022) the sampling process,
which diminishes the benefit of using expres-xxpeessvve diffusion models.
Having observed that the lack of tractability hinders us from fully exploiting diffusion models in constrained generation tasks, we study the converse problem: what is the benefit of models that by design support efficient constrained generation? This paper presents positive evidence by showing that Probabilistic Circuits (PCs) (Choi et al. 2020), a class of expressive Tractable Probabilistic Models that support efficient computation of arbitrary marginal probabilities, can efficiently steer the denoising process of diffusion models towards high-quality inpainted images. We will define a class constraints that includes inpainting constraints for which we can provide the following guarantee. For any constraint in this class, given sample H; noise level t, we show that PC trained on noise-free samples (i.e., p(Xn)) ) can be used to efficiently compute p( ( x,, c), which is a key step in the sampling process of diffusion models. This PC-computed distribution then

---

Published as a conference paper at ICLR 2024
Colaiin
pou (KofN,, xt)
Tiramisu
pnAr(ãafx.. x
L
P(MulNa, x
Prima N.,
not
Denaising process
219
== 217
201 == 100
1=0
21 217
[= 201
== 100
==
Figure I: Illustration of the steering effect the TPM on the diffusion model. The same random seed is used by the baseline (CoPaint: Zhang et al. (2023a)) and approach. At every time step, given the image at the previous noise level, Tiramisu reconstructs To with both the diffusion model and the TPM, and combines the two distributions by taking their geometrie mean (solid arrows). The images then go through the noising process to generate the input for the previous time step (dashed arrows).
be used to effectively guide the denoising process, leading to photorealistic images that adhere to the constraints. Figure illlstrates the steering effect of PCs in the proposed algorithm Tiramisu (Tractable Image Inpainting via Steering Diffusion Models). Specifically, we plot the reconstructed image by the diffusion model (the first row of Tiramisu) and the PC (the third row) at five time steps during the denoising process. Compared to the baselines, Tiramisu generates more semantically coherent images with the PC-provided guidance. In summary, this paper has three main contributions:
A new scheme for controlled image generation. This is the first paper that demonstrates the possibility of using TPMs for controling/coontraiinngg the generation process of natural and high-resolution images. This not only opens up new avenues for controlled image generation, but also highlights the potential impact of non- standard learning architectures (e.g.. PCs) on modern image generation tasks.
Competitive sample quality and runtime. Empirical evaluations on three challenging high-rest righ-resolution natural image datasets (i.e., CelebA-HQ, ImageNet, and LSUN) show that the proposed method Tiramisu consistently improves the overall quality of inpainted images while introducing only ~ 10% additional computational overhead, which the joint effort of (i) further scaling up PC models based on prior art, and (ii) an improved custom GPU implementation for PC training and inference.
more general form, independent soft-evidence constraints include tasks beyond image inpainting. As an illustrative example, we demonstrate that Tiramisu is capable of fusing the semantics of image patches from a set reference images and generating images conditioned such semantic constraints. This highlights the potential of Tiramisu on more challenging controlled image generation tasks.
Potential for more complex controlled generation tasks.
PRELIMINARIES
Denoising Diffussio Probabilistic Models A diffusion model et et al. 2020 Sohl Sohl--ickstein et al. 2015) defined on variables Xo is latent variable model of the form pe zv := pe @oo. ) J where U1.2" are the latent variables and the joint distribution Po (o(x)))) is defined as a Markov chain termed the reverse/denoise process:
T
(e( p(#r)
II
po (o
For continuous variables Fo.r, the initial and transition probabilities of the Markov chain typically use Gaussian distributions: p(ær) ;= (xTr 0, po( (x;) := N( (x t), Es (x f)). where 14 and Σg are the mean and covariance parameters, respectively. The key property that distinguishes diffusion models from other latent variable models such as hierarchical Variational Autoencoders (Vahdat & Kautz 2020) is the fact that they have a prespecified approximate pos- terior q (xp) := I q( (2;-) This is called the forward or diffusion process. For continuous variables, the transition probabilities also defined as Gaussians: q(27//0441)
2

---

Published as a conference paper at ICLR 2024
(az v1 1, B,I), where {6r) is noise schedule. Training is done by maximizing the
ELBO of po (zo) with the variational posterior q(F1:1 (zo). See Kingma et al. (2021) for more details.
While it is possible to directly model pe( p= (r)) with neural network, prior works discovered that the following parameterization leads to better empirical performance (Ho et al. 2020):
po 1 (.a)) = EB,, ( x:e) po ( (2+),
where p0 (24) (mo; (2t,, 1), Ex 1)) is parameterized by neural network and ((0;-1 -o, 24)) has simple closed-form expression (Ho et al. 2020). Following the definition of the denoising process, sampling from a diffusion model boils down to first sampling from p(ær) and then recursively sampling -1. Zo according to po p0(22-112 12)).
Tractable Probabilistic Models
Tractable Probabilistic Models (TPMs) are class of generative models that by design support efficient and exact computation certain queries (Poon & Domingos
2011 Kisa al., 2014. Choi et al. 2020 Correia et al.) 2023 Sidheekk et al.) 2023 Rahman et al.
2014
Kulesza et al. 2012). Depending on their structure, TPMs support various queries ranging from
marginal/conditional probabilities conditioning on logical constraints (Vergari et al. 202 Bekker
ct al. 2015). Thanks to their tractability, TPMs enable a wide range of downstream applications such
constrained language generation (Zhang al. 2023b), knowledge graph link prediction (Loconte)
ctt al. 2023), and data compression (Liu et al. 2022a).
GUIDING DIFFUSION MODELS WITH TRACTABLE PROBABILISTIC MODELS
Given diffusion model trained for unconditional generation, our goal is to steer the model to generate samples given different conditions/constraints without the need for seecispecific fine-tuning. In the following, we focus on the image inpainting task to demonstrate that TPMs can guide diffusion models toward more coherent samples that satisfy the constraints.
The goal of image inpainting is to predict the missing pixels given the known pixels. Define X/K (resp. X as the provided (resp. missing) pixels. We aim to enforce the inpainting constraint X x on every denoising step pe p0 (x)) (Vt E ,)). Plugging in Equation (2). the conditional
probabilities are written as:
AI E 1,..,, T
po(#;-1 mx/)
Σ ((ax:-1/20: ax.) po (o (x), m/)).
where the first term on the right- hand side is independent of z/i To sample coherent inpainted images, we need to draw unbiased samples from po (æo la,, ar)). Applying Bayes' rule, we get
1
Po (Zol Ør, an)) = Pe pe (2)) p(a [o)) ž po (z)) 1 = =b),
(3)
where [-]] is the indicator function and Z is normalizing constant. One simple strategy to sample from Equation (3) is by rejection sampling: sample unconditionally from pe (ão|z;; (i.c., the learned denoising model) and reject samples with z/ * z/. However, this is impractical since the acceptance rate could be extremely low. Existing algorithms use approximation strategies to compute or sample from Equation (3). For example, Lugmayr et al. (202)) proposes set . ax after sampling T (- leaving के untouched; Zhang et al. (202aa) and Chung et al. (022)) relax the hard inpainting constraint to minay |: x and use gradient-base methods to gradually enforce it.
This paper explores the possibility of drawing unbiased samples from pa (Co (e,, æh) given TPM- represented distribution p=(2)). . By applying Bayes' rule from the other side, we have
1 po (o Fe x))) = Z qxx (o)) po po ( ( Z II (())(=)) pe (
1[ xb] (4)
where is a normalizing constant, of is the ith variable in 24, and the factorization of qxx (an) follows the definition of the diffusion process in Section 2 Although the right-hand side seems to be impractical to compute due to the normalizing constant, we will demonstrate the following sections that there exists class of expressive TPMs that can compute it efficiently and exactly.
From the diffusion model and the TPM, we have obtained two versions of the same distribution p( p(žolzz , x<)) Thanks to the expressiveness of neural networks, the distribution approximated by the diffusion model (i.c., Eq. By; termed PDM (oo xe xx)) encodes high-fidelity images. However, due
Note that diffusion models can only approximate this distribution.
3

---

Published as a conference paper at ICLR 2024
to the inability compute the exact conditional probability, (DM( æ²) could lead to images incoherent with the constraint (Zhang et al., 2023a). . In contrast, the TPM- IPM-generated distribution (i.e., Eq. 4 termed PrPm (orpM(@olee)) (2,, x represents images that potentially better align with the given pixels. Therefore, PDM (0g) Rt, x;,2%) and pTPM (ip my ag) can be viewed as distributions trained for the same task yet with different biases. Following prior arts (Grover & Ermon 2018 ZZhng et al.) 2023b), we combine both distributions by taking the weighted average of the logits of every variable in Øo. hoping to get images that are both semantically coherent and have high fidelity:
(5) where a E (0, 1) is mixing hyperparameter. In summary, as key step of image inpainting with diffusion models, we compute p( [z,, (x)) from both the diffusion model and TPM, and use their weighted geometric mean in the denoising process. We note that the use of TPMs is independent of the design choices related to the diffusion model, and thus can be built upon any prior approach.
po Dt; ab)) x PDM (āo |et, xz)) PTPM (oo 2t; xrb)
4 PRACTICAL IMPLEMENTATION WITH PROBABILISTIC CIRCUITS
The previous section introduces how TPMs could help guide the denoising process of diffusion models toward high-quality inpainted images. While promising, a key question is whether PTPM (at, ax)) (Eq. f can be computed efficiently and exactly? We answer the question in its affirmative by showing that a class of TPMs termed Probabilistic Circuits (PCs) (Choi et al.) 2020) can answer the query while being expressive enough to model natural images. In the following, we first provide background on PCs (Sec. 4.1b. We then describe how they are used to compute PTPM (Zo xt ab) (Sec. 4.2).
4.1 BACKGROUND ON PROBABILISTIC CIRCUITS
Probabilistic Circuits (PCs) (Choi et al. 2020) are an umbrella term for a wide variety of TPMs, including classic ones such Hidden Markov Models (Rabiner & Juang 1986) and Chow-Liu Trees (Chow & Liu 1968) as well as more recent ones including
Networks (Poon &
Domingos 2011) J. Arithmetic Circuits (Shen al. 2016), and Cutset Networks (Rahman 2014).
We define the syntax and semantics of PCS as follows.
Definition 1 (Probabilistic Circuits). A PC p(X) represents a distribution over X via a parameterized Directed Acyclic Graph (DAG) with a single root node n,. There are three types of nodes in the DAG: input, product, and sum nodes. Input nodes define primitive distributions over some variable X E X, while sum and product nodes merge the distribu- tions defined by their children, denoted (n) to build more complex distributions. Specifically, the distribution encoded by every node is defined recursively as
0.0
0.6
0.0
LO
LD
0.6
ULE
0.7
N2
O
DB
088
plouiafarn) 007
Figure 2: An example PC over boolean variables XI...., X1, Sum parame- ters are labeled on the corresponding edges. The probability of every node given input E is labeled blue on top of the corresponding node.
(xx
n is an input node,
Pn (=(x):== :=
Iociin()) (x( Encin(n) On,e Pe(x:)
ni is product node, (6) n is a sum node,
where (x) is an univariate input distribution (e.g., Gaus-
sian, Categorical), and 6n,c denotes the parameter corresponds to edge (n, Intuitively, sum nodes and product nodes encode mixture and factorized distributions of their children, respectively. To ensure that a PC models a valid distribution, we assume the child parameters of every sum node n (i.e., (0n,c) (Ein()))) sum up to 1. The size of PC p. denoted [p]. is the number of edges in its DAG.
Figure 2 shows an example PC over boolean variables Xi...., X4, where O @, and θ represent input, product, and sum nodes, respectively. The key to guaranteeing the tractability of PCs to add proper structural constraints to their DAG structure. Specifically, this paper considers smoothness and decomposability, which are required by the inference algorithm that will be introduced in Section 4.2
Definition (Smoothness and Decomposability)) Define the scope d(n) of node n as the collection of variables defined by all its descendent input nodes. A PC is smooth if for every sum node n, its children have the same scope: Ve,, C2 E in(n), Φ(c)) = o(c²); it is decomposable if for every
product node its children have disjoint scopes: Ver,c2 C2 in(n) (c1 A c2), ((G)) O ((02) Ø.
4

---

Published as a conference paper at ICLR 2024
Answering queries with PCs amounts computing certain functions recursively in postorder (i.e., feedforward) or preorder (i.e., backward) on its DAG. For example, computing the likelihood p(æ) boils down to forward pass the PC: we first assign probability to every input node n by evaluating its density/mass function fn (2), and then do a feedforward pass (children before parents) of all sum and product nodes, computing their output probabilities following Equation (6). Finally, the output value of the root node is the target likelihood. In Figure 2 the output probability of every node for the query p(x1 (223344) is labeled blue on top of it.
As hinted by its definition, the set of learnable parameters in PCs includes (i) parameters of the sum edges and (ii) parameters of the imput nodes/distributions. All parameters can be jointly learned using an Expectation Sitiuttion-Mximzztttonn based algorithm that aims to maximize the average log-likelihood of all samples in dataset D: EEED log Pr (1r). Details of the EM algorithm is provided in Appendix C.1
4.2 COMPUTING CONSTRAINED POSTERIOR DISTRIBUTION
Recall from Section and Equation that at every denoising step, we need to compute PTPM (ăol Dt, .τ)) with the PC. This section proposes an algorithm that computes PTPM ( ab) given a PC p(z)) in linear time w.r.t. its size. Specifically, we first demonstrate how Equation 4 can
be converted to a general form of queries we define as independent soft-evidence constraints. We then establish an efficient inference algorithm for this query class.
After closer inspection of Equation (4) we observe that both g(æ; (zo) and 1 = =01 can be
considered as constraints factorized over every variable. Specifically, with w, (xb)) == q q( (
X1 E X and w; (z6) == [ = -7}] otherwise, PTPM (To (z,, æx))) can be equivalently expressed as
@r Tt, a = Z II (x p( (o)) where Z == EII wi (5%) p(āo). 20
(7)
We call w; the soft-evidence constrain of variable Xj it defines a prior belief of its value. In the extreme case of conditioning on hard evidence, Wiy becomes an indicator that puts all weight on the conditioned value. Recall from Section that diffusion models parameterize pe (Øo (x,) as a fully- factorized distribution. In order to compute the weighted geometric mean of PDM @To aaa, ab) and PrPm (0o) xr,, .²)) (cf. Eq. ) we need to also compute the univariate distributions preM (5t aa,, ab)) for every X E Xo. While this seems to suggest the need to query the PC at least |Xol times, we propose algorithm that only needs a forward and backward pass to compute all target probabilities.
The forward pass Similar to the likelihood query algorithm introduced in Section 4.1 we traverse all nodes in postorder and store the output of every node n fw,. For sum and product nodes, the output is computed following Equation (6): the output of every input node that encodes distribution of X6 defined as fwn := Ens In (x)) uy (xb). where fn is defined in Equation (
The backward pass The backward pass consists of two steps: (i) traversing all nodes in preorder (parents before children) to compute the backward value bk,, (ii) computing the target probabilities using the backward value of all input nodes. For ease of presentation, we assume the PC alternates between sum and product layers, and all parents of any input node are product nodes First, we compute the backward values by setting bk,, of the root node to 1, then recursively compute the backward value of other nodes as follows:
E Empppp(n) (0m.n fwn fin//umm) bkm n is a product node, Em Emepa(n) bkm
bk,
is input or sum node,
where pa(n) is the set of parents of node Next, for every i, we gather all input nodes defined on Xi. denoted St, and compute ( æe, xT)) := 2 Exes, bk, fo (=b)) w; (2(g). We justify the correctness of this algorithm in the following theorem, whose proof is provided in Appendix AA]
Theorem 1. For any smooth and decomposable PC x(X) and univariate functions {w; (X.)).
define p' p((x) = 1 II, w; wx(x:)) p(x), where the normalizing constant Z = En II. w. (2,) p(x). Assume all variables in X are categorical variables with C' categories, the ubove-describee algorithm computes y/ (zx) for every variable X, and its every assignment x; in time 0(p) + [X] C) (1p)).
2 Every PC that does not satisfy such constraints can be transformed into one in linear time since (i) consecutive sum or product nodes can he merged without changing the PC's semantic, and (ii) we can add dummy product with one child between any pair of sum and input nodes.
5

---

Published as a conference paper at ICLR 2024
5 TOWARDS HIGH-RESOLUTION IMAGE INPAINTING
Another key factor determining the effectiveness of the PC-guided diffusion model is the expressive- ness of the PC p(Xo). i.e., how well it can model the target image distribution. Recent advances have significantly pushed forward the expressiveness of PCs (Liu et al. 2022b) 2023), leading to competitive likelihoods on datasets such as CIFAR (Krizhevsky et al. 2009) and down-sampled ImageNet (Deng et al. 2009), which allows us to directly apply the guided inpainting algorithm to them. However, there still gap towards directly modeling high-resolution (c.g., 256 x 256) image data. While it is possible that this could be achieved in the near future given the rapid development of PCs, this paper explores an alternative approach where we use a (variational) auto-encoder to transform high-resolution images to a lower-dimensional latent space. Although in this way we lose the "full tractability" over every pixel, as we shall proceed to demonstrate, decent approximation can still be achieved. The key intuition is that the latent space concisely captures the semantic information of the image, and thus can effectively guide diffusion models toward generating semantically coherent images; fine- aene-grained details such as color consistency of the neighboring pixels can be properly handled by the neural-netwrrk-bassee based diffusion model. This is empirically justified in Section 66.
Define the latent space of the image X, as Zo- We adopt Vector Quantized Generative Adversarial Networks (VQ-GANs) (Esser et al., 2021). which are equipped with an encoder q (z (azo) and a decoder p( (mo) =z)). to transform the images between the pixel space and the latent space We approx- imate PTPM (To æt; =5) (Eq. 7 by first estimating рTPM (žo (2,, ax)) with a PC p(Zo) trained on the latent space and the VQ-GAN encoder; this latent-space conditional distribution is then converted back to the pixel space. Specifically, the latent-space conditional probability is approximated via
PTPM xr, x0)
II
i (Z)) p(ão), where wf( := Z
EII W/ (E6) To J
g( 0o), (8)
Z
where Z and {Zi} are normalizing constants and q (0)) is the VQ-GAN encoder. It is safe to assume the independence between the soft evidence for different latent variables (i.c., wz²) since every latent variable produced by VQ-GAN corresponds to a differennt image patch, which corresponds to a different set of pixel-space soft constraints (i.e., W:). In practice, we approximate w (2t) by performing Monte Carlo sampling over 2n (i.e., sample To following II, wy (zt). and then feed them through the VQ-GAN encoder). Finally, PTPM (æo ar, af) is approximated by Monte Carlo estimation of PrPM (Zu x.)))))))) == E Bggo-rrrx(-]jr.te
(2))
||(20) |,)], where p(žo) Zn) is the VQ-GAN decoder. We observe that as few as 4-8 samples lead to significant performance gain across various datasets and mask types. See Appendix B for details of the design choices.
Another main contribution of this paper is to further scale up PCs based on Liu et al. 2022b 2023) to
achieve likelihoods competitive with GPTs (Brown et al. 2020) on the latent image space generated by VQ-GAN. Specifically, for 256 x 256 images, the latent space typically consists of 16 x 16 = 256 categorical variables each with 2048-16384 categories. While the number of variables is similar to datasets considered by prior PC learning approaches, the variables are much more semantically complicated (c.g., patch semantic vs. pixel value). We provide the full learning details including the model structure and the training pipeline in Appendix C.2
In summary, similar to the pixel-space guided inpainting algorithm introduced in Section 3 and 4.2, its spaee variant also computes PTPM @2o az,, =²) to guide the diffusion model PDM @C 2y ) with Equation (5), except that it is approximated using a latent-space PC combined with VQ-GAN.
EXPERIMENTS
In this section, we take gradual steps to analyze and illustrate our method Tiramisu (Tractable Image Inpainting via Steering Diffusion Models). Specifically, we first qualitatively investigate the steering effect of the TPM on the denoising diffusion process (Sec. 6.I).. Next, we perform an empirical evaluation three high-resolution image datasets with six large-hole masks, which significantly challenges its ability to generate semantically consistent images (Sec. (.2). Finally, inspired by the fact that Tiramisu can handle arbitrary constraints that can be written as independent soft evidence (cf. Sec. (.2)). we test it on new controlled image generation task termed image semantic fusion, where the goal fuse parts from different images and generate images with semantic coherence and high
fidelity (Sec. 6.3) Code is available at ht bttpp:: //qqtuttubb/. com/ SeLL-SttrAA/// / rammsu
"We adopt VQ-GAN since it has discrete latent space, which makes PC training casier.

---

Published as a conference paper at ICLR 2024
Table 1: Quantative results on three datasets: CelebA-HQ (Liu al. 2015). ImageNet (Deng et al. 2009). and LSUN- Yu et al. 2015). We report the average LP IPS value (lower is better) (Zhang et al. 2018) across 100 inpainted images for all settings, Bold indicates the best result.
Tasks
Algorithms
Dataset
Mask
Tiramisu (ours)
CoPaint
RePaint
DDNM
DDRM
DPS
Resampling
Left
0.189
0.185
0.195
0.254
0.275
0.201
0.257
Top
0.187
0.182
0.187
0.248
0.267
0.187
0.251
Espandt
0.454
0.468
0.504
0.597
0.682
0.466
0.613
CdlebA-HQ
Expand2
0.442
0.455
0,480
0.686
0.434
0.601
V-strip
0.487
0.502
0,517
0.625
0.724
0.535
0.647
H-strip
0.484
0.488
0.517
0.626
0.731
0.492
0.639
Wide
0.069
0,072
0.075
0.112
0.132
0.078
0.128
Left
0.286
0.289
0.296
0.410
0.369
0.327
0.369
Top
0.308
0,312
0.336
0.427
0.373
0.343
0.368
Expand1
0.616
0.623
0.691
0.786
0.726
0.621
0.711
ImageNet
Expand2
0.597
0.607
0.692
0.799
0.724
0.618
0.721
V-strip
0.646
0.654
0.741
0.851
0.761
0.637
0.759
H-strip
0.657
0.660
0.744
0.851
0.753
0.647
0.774
Wide
0.125
0.128
0.127
0.198
0.197
0.132
0.196
Left
0.285
0.287
0.314
0.345
0.366
0.314
0.367
Top
0.310
0.323
0.347
0.376
0.368
0.355
0.372
Expandl
0.615
0.637
0.676
0.716
0.695
0.641
0.699
LSUN-Bedroom
Expand2
0.635
0.641
0.720
0.691
0.638
V-strip
0.672
0.676
0.711
0.760
0.721
0.674
0.725
H-strip
0.679
0,686
0.722
0.766
0.726
0.674
0.724
Wide
0.116
0.115
0.124
0.135
0,204
0.108
0,202
Average
0,421
0.427
0.459
0.532
0.531
0.434
0,514
6.1 ANALYSIS OF THE TPM--ROVIDEE GUIDANCE
Since we are largely motivated by the ability of TPMs to generate images that better match the semantics of the given pixels, it is natural to examine how the TPM-generated signal guides the difffusion model during the denoising process. Recall from Section 3 that every denoising step t, the
reconstruction distributions PDM (2 Øt =²) and pTPM (To Ør, x are computed/estimate using the diffusion model and the TPM, respectively. Both distributions are then merged into p(Co (z,, ab)) (Eq. (5)) and are used to generate the image at the previous noise level (i.e., 2t-1). In all experiments, adopt CoPaint (Zhang et al. 2023a) generate PDM x5)). which is independent of the design choices related to the TPM. Therefore, qualitatively comparing the denoising process of Tiramisu and CoPaint allows
examine the steering effect provided by the TPM.
Figure I visualizes the denoising process of Tiramisu by plotting the images corresponding to the expected values of the aforementioned distributions (i.e., PDM (3o [t, 2b),, PTPM (ø x,, zff). and p(ão|z, z))). To minimize distraction, we first focus on image pairs of the DM- and TPM-generated image pairs the same column. Since they are generated from the same input image 24, comparing the image pairs allows us to examine the built-in inductive biases in both distributions. For instance, in the celebrity face image, we observe that the contour of the facial features sharper for the TPM-generated image. This is more obvious in images at larger time steps since the guidance provided by the TPM is accumulated throughout the denoising process.
Next, we look at the second row (i.e., p la,, axf)) of Tiramisu. Although blurry, global semantics appear at the early stages of the denoising process. For example, on the right side, we can vaguely see two ostriches visible at time step 217. In contrast, the denoised image at t 217 for CoPaint does not contain much semantic information. Conditioning on these blurred contents, the diffusion model can further fill in fine-grained details. Since the image semantics denoising steps, we only need to query the TPM at early time steps, which also significantly reduces the computational overhead of Tiramisu. See Section 6.2 for quantitative analysis. As result, compared to the baseline, Tiramisu can generate inpainted images with higher quality.
be generated in a few
6.2 COMPARISON WITH THE STATE OF THE ART
In this section, we challenge Tiramisu against state-of-the-an art diffusion- inpainting algorithms on three large-scale high-resolution image datasets: CelebA-HQ (Liu et al.) 2015). ImageNet (Deng) et al. 2009), and -UN-Bedrooo (Yu et al. 2015). To further challenge the ability of Tiramisu to generate semantically coherent images, original image since it is very likely for inpainting algorithms to ignore the given visual cues and generate semantically inconsistent images. Details of the masks be found in Appendix D
seven types of masks that reveal only 5-20% of the
7

---

Published as a conference paper at ICLR 2024
CelebA-HQ
ImageNet
LSUN -uNdooooo
Left
Expand1 Expand2
V-strip
Left
Expand1
Expand2
V-strip
Left
Expandl
Expand2
V-strip
Origin
Resample
DPS
DDRM
DDNM
RePaint
CoPaint
Tiramisu
(ours)
Figure 3: Qualitative results on all three adopted datasets. We compare Tiramisu against six diffusion-
based inpainting algorithms. Please refer to Appendix E.2 for more qualitative results.
Methods We consider the six following diffusion-based inpainting algorithms: CoPaint (Zhang et al.
2023a), RePaint (Lugmayr al. 2022), DDNM (Wang et al. 2022), DDRM (Kawar al. (0222)
DPS (Chung et al. 22022) and Resampling (Trppe et al. 2022). Although not exhaustive, this set of methods summarizes recent developments in image inpanningg and can be deemed as state-of-the
We base our method Tiramisu on CoPaint (i.e., generate PDM (Zol ab)) with CoPaint). Please see the appendix for details on Tiramisu (Appx. and C.2
and the baselines (Appx. DD). Quantitative and qualitative results Table the average LPIPS values (Zhang al., 2018) on all x = dataset-mask configurations. First, Tiramisu outperforms CoPaint in 18 out 21 settings, which demonstrates that the TPM-provided guidance consistently improves the quality of generated images. Next, compared all baselines, Tiramisu achieves the best LPIPS value on 14 out of 21 settings, which indicates its superiority over the baselines. This conclusion is further supported by the sample inpainted images shown in Figure 3. which suggests that Tiramisu generates more semantically consistent images. See Appx. E.2 for
samples and Appx. E.T
for user studies.
Computational efficiency As illustrated in Section 6.1 we use PC to steer the denoising steps only in earlier stages. While engaging PCs in more denoising steps could lead to bet- ter performance, the runtime is also increased accordingly. To better understand this tradeoff, we use CelebA + the Expandl mask as an example analyze this tradeoff. As shown in Fig- ure 4 as we use PCs in more denoising steps, the LPIPS score first decreases and then increases, suggesting that incorporating PCs in moderate amount of steps gives the best performance (around 20% this case). One explanation to this phenomenon Figure 4: Performance and runtime.
0.48
130
LPISS Rustime
125
0.47
PIPS
Runtime
115
0.46
110
10
20
30
40
denoising stops using
is that in later denoising stages, the diffusion model mainly focuses refining details. However, PCs are better at controlling the global semantics of images in earlier denoising stages. We then focus on the computation time. When using PCs in 20% of the denoising steps, the additional computational overhead incurred by the TPM is around 10s, which is only 10% of the total computation time.
6.3 BEYOND IMAGE INPAINTING
The previous sections demonstrate the effectiveness of using TPMs on image inpainting tasks. A nat- ural follow-up question is whether this framework can be generalized to other controlled/constrriiee image generation tasks? Although the potential extending Tiramisu to more complicated tasks by showing its capability to fuse the semantic information from various input patches/fragments. Specifically, consider the case of
do not have definite answer, this section demonstrates
8

---

Published as a conference paper at ICLR 2024
Semantic coherence
Somantic coherence
Figure 5: CelebA-HQ qualitative results for the semantic fusion task. In every sample, reference images together with their masks are provided to Tiramisu. The task is to generate images that (i) semantically align with the ummasked region of both reference images, and (ii) have high fidelity. For every input, we generate five samples with different levels of semantic coherence. The left-most images are the least semantically constrained and barely match the semantic patterns of the reference images. In contrast, the right-most images strictly match the semantics of the reference images.
latent-space soft evidence constraints {wf J. (i.e., Eq. (8)). For various recent autoencoder models such as VQ-GAN, the latent variables of size Hi x Wi are encoded from images of size H x W. Intuitively, every latent variable encodes the semantic of every wy can be viewed as a constraint on the semantics of the corresponding image patch.
Hi x W/Wj image patch. Therefore,
We introduce a controlled image generation task called semantic fusion, where are given several reference images each paired with a mask. The goal is to generate images that (i) semantically align with the unmasked region of every reference image, and (ii) have high quality and fidelity. Semantic fusion can be viewed as a preliminary task for more general controlled image generation since any type of visual word information (e.g., language condition) can be transferred constraints on (wā }
Figure 5 shows qualitative results of Tiramisu on semantic fusion tasks. For every set of reference im- ages, we generate five samples with different semantic coherence levels by adjusting the temperature of every soft evidence function w (b)) See Appendix F for more details.
7 RELATED WORK AND CONCLUSION
Existing approaches for image inpainting can be divided into two classes: supervised methods and unsupervised methods. Specifically, supervised approaches require the model to be explicitly trained on inpainting tasks, while unsupervised approaches do not require task-specific training. Supervised
methods are widely used for Variational Autoencoders (Peng et al. [021 Zheng et al. 2019 Guo
et al.] 2019), Generative Adversarial Networks (lizuka et al.) 22077 ZZao et al. G et al. 2019).
and Transformers (Yu et al. 2021]: Wan et al. (0021). A major problem of supervised inpainting algorithms is that they are highly biased toward mask types observed during training and often
need to be fine-tuned individually for every inpainting task (Xiang et al. 2023). However, since approximating the probability of masked pixels given known pixels is highly intractable for these models, we are unfortunately restricted to supervised inpainting approaches.
Recent developments in diffusion models (Ho et al. 2020 Song al., 2020) open up the possibility for unsupervised inpainting as these models provide potential ways to approximate the constrained posterior. Specifically, the existence of variables different noise levels allows us to blend in information from the known pixels to the denoising process of the diffusion models (Song & Ermon 2019. Avrahami et al. 2022 Kawar al. (022).. Additionally, techniques such as resampling images at higher noise levels (Lugmayr et al. 2022) and using partial filtering to approximate the constrained posterior (Trippe et al. 2022) greatly contribute to generating high-quality images.
The transition from supervised to unsupervised inpainting methods is clear example that demon- strates the benefits of using more tractable models. Based on this observation, this paper seeks to further exploit tractable models. Specifically, we study the "extreme case", where use TPMs that can exactly compute the constrained posterior. Empirical results suggest that TPMs can effectively improve the quality of inpainted images with only 10% additional computational overhead.

---

Published as a conference paper at ICLR 2024
Acknowledgemmnts This work was funded in part by the DARPA PTG Program under award HR001 12220005, the DARPA ANSR program under award 1A8750-23-2-0004 NSF grants #IIS- 1943641, #1IS-1956441, #CCF- 1PFF-18371999 129, and gift from RelationalAL. GVdB discloses financial interest RelationalAL. Mathias Niepert acknowledges funding by Deutsche Forschungsgemeinschan (DFG, German Research Foundation) under Germany's ' Excellence Strategy EXC and support by the Stuttgart Center for Simulation Science (SimTech).
Reproducibility statement To facilitate reproducibilityy we have clearly stated the proposed PC inference algorithm in Section 4.2 Algorithmic details including the choice of hyperparameters are provided A
Formal proof of Thm. i provided in Appendix[A] We provide the code to train the PCs and to generate inpainted images at athtpps: /tt::///gtthu com/ com/ UCLA- StarAI/ Tiramisu
[land
REFERENCES
Omri Avrahami, Dani Lischinski, and Ohad Fried. Blended diffusion for text-driven editing of natural images. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 18208-18218, 2022.
Jessa Bekker, Jesse Davis, Arthur Choi, Adnan Darwiche, and Guy Van den Broeck. Tractable learning for complex probability queries. Advances in Neural Information Processing Systems, 28, 2015.
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. 2020.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. oct 2020. URL httt:t//staaaa.... ucla
/dd./papers/Prrrciircc
pdf
YooJung Choi, Meihua Dang. and Guy Van den Broeck. Group fairness by probabilistic modeling with latent fair decisions. In Proceedings of the AAAI Conference Artificial Intelligence. volume 35, pp. 12051-12059 2021.
CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, 14(3):462-463) 467, 1968.
Hyungjin Chung. Jeongsol Kim, Michael T Mccann, Mare Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. arXiv preprint arXiv:2209.144 14687, 2022.
Alvaro HC Correia, Gennaro Gala, Erik Quaeghebeur, Cassio de Campos, and Robert Peharz. Continuous mixtures tractable probabilistic models. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7244-7252, 2023.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248 255. Ieee, 2009.
Patrick Esser, Robin Rombach, and Bjorn Ommer. Taming transformers for high- image synthesis. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12873-12883, 2021.
Aditya Grover and Stefano Ermon. Boosted generative models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Zongyu Guo, Zhibo Chen, Tao Yu, Jiale Chen, and Sen Liu. Progressive image inpainting with full-resolution residual network. In Proceedings of the 27th acm international conference on multimedia, pp. 2496-2504, 2019.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851 2020.
10

---

Published as a conference paper at ICLR 2024
Satoshi lizuka, Edgar Simo-Serra and Hiroshi Ishikawa. Globally and locally consistent image completion. ACM Transactions on Graphics (ToG), 36(4):1-14, 2017.
Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restoration models. Advances in Neural Information Processing Systems, 35:23593-23606, 2022.
Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances in neural information processing systems, 014-1666-227707, 2021.
Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3):123-- 2012.
Anji Liu, Stephan Mandt, and Guy Van den Broeck. Lossless compression with probabilistic circuits. In Proceedings of the International Conference Learning Representations (ICLR), 2022a.
Anji Liu, Honghua Zhang, and Guy Van den Broeck. Scaling up probabilistic circuits by latent variable distillation. In The Eleventh International Conference on Learning Representations, 2022b.
Xuejie Liu, Anji Liu, Guy Van den Broeck, and Yitao Liang. Understanding the distillation process from deep generative models to tractable probabilistic circuits. In International Conference on Machine Learning, pp. 21825-21833 PMLR, 2023.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
Lorenzo Loconte, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. How to turn your knowledge graph embeddings into generative models via probabilistic circuits. arXiv preprint arXiv:2305. 15944, 2023.
Andreas Lugmayr, Martin Danelljan, Andres Romero, Fisher Yu, Radu Timofte, and Lue Van Gool. Repaint: Inpainting using denoising diffusion probabilistic models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14461-11471, 2022.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning, pp. 8162-8171. PMLR, 2021.
Robert Peharz, Robert Gens, Franz Pernkopf, and Pedro Domingos. the latent variable interpreta- tion in sum sum- product networks. IEEE transactions pattern analysis and machine intelligence, 39 (10):2030-2044, 2016.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic eircuits. In International Conference on Machine Learning, pp- 7564-7574. PMLR, 2020.
Jialun Peng, Dong Liu, Songcen Xu, and Houqiang Li. Generating diverse structure for image inpainting with hierarchical va-vae. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 10775-10784, 2021.
Hoifung Poon and Pedro Domingos. Sum-product networks: new deep architecture. In Proceedings of the Seeeth- Conference on Uncertainty in Artificial Intelligence, pp. 337-346, 2011.
Lawrence Rabiner and Büinhhwang Juang. An introduction to hidden markov models. ieee assp magazine, 3(1):4-16, 1986.
11

---

Published as a conference paper at ICLR 2024
Tahrima Rahman, Prasanna Kothalkar, and Vibhav Gogate. Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part II 14, pp. 630-645. Springer, 2014.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint 22Kv:2220.00/225, 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 confer- ence on computer vision and pattern recognition, pp. 10684- 10695, 2022.
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabillistcc models. Advances in Neural Information Processing Systems, 2016.
Sahil Sidheekh, Kristian Kersting, and Sriraam Natarajan. Probabilistic flow circuits: towards unified deep models for tractable probabilistic inference. In Uncertainty Artificial Intelligence, pp. 1964-1973. PMLR, 2023.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pp. 2256-2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Seore-based generative modeling through stochastic differential equations. arXiv preprint 1eXiv:2011.134555 2020.
Roman Suvorov, Elizaveta Logacheva, Anton Mashikhin. Anastasia Remizova, Arsenii Ashukha, Aleksei Silvestrov, Naejin Kong, Harshith Goka, Kiwoong Park, and Victor Lempitsky. Resolution- robust large mask inpainting with fourier convolutions. In Proceedings of the IEEÉ/CVF winter conference on applications of computer vision, pp. 1149-2159, 2022.
Brian Trippe, Jason Yim, Doug Tischer, David Baker, Tamara Broderick, Regina Barzilay, and Tommi Jaakkola. Diffusion probabilistic modeling of protein backbones in 3d for the motif- scaffolding problem. arXiv preprint arXiv:2206.. 04119, 2022.
Arash Vahdat and Jan Kautz. Nvac: A deep hicrarchical variational autoencoder. Advances in neural information processing systems, 33: 33:19667-19679 2020.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. Advances in Neural Information Processing Systems, 34:13189-13200 2021.
Ziyu Wan, Jingbo Zhang, Dongdong Chen, and Jing Liao. High-fidelity pluralistic image completion with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4692 4701, 2021.
Yinhuai Wang, Jiwen Yu, and Jian Zhang. Zero-shot image restoration using denoising diffusion null-space model. In The Eleventh International Conference on Learning Representations, 2022.
Hanyu Xiang, Qin Zou, Muhammad Ali Nawaz, Xianfeng Huang, Fan Zhang, and Hongkai Yu. Deep learning for image inpainting: survey. Pattern Recognition, 134:109046, 2023.
Fisher Yu, Yinda Zhang, Shuran Song, Ari Seff, and Jianxiong Xiao. Lsun: Construction of a large- scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv: 2015.
Yingchen Yu, Fangneng Zhan, Rongliang Wu, Jianxiong Pan, Kaiwen Cui, Shijian Lu, Feiying Ma, Xuansong Xie, and Chunyan Miao. Diverse image inpainting with bidirectional and autoregressive transformers. In Proceedings of the 29th ACM International Conference on Multimedia, pp. 69-78, 2021.
12

---

Published as a conference paper at ICLR 2024
Guanhua Zhang, Jiabao Ji, Yang Zhang, Mo Yu, Tommi Jaakkola, and Shiyu Chang. Towards coherent image inpainting using denoising diffusion implicit models. arXiv preprint arXiv:2304.03322, 2023a.
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference on Machine Learning, pp. 40932- 40945. PMLR. 2023b.
Richard Zhang, Phillip Isola, Alexei Efros, Eli Shechtman, and Oliver Wang. The unreasonable effectiveness of deep features as perceptual metric. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 586-595, 2018.
Shengyu Zhao, Jonathan Cui, Yilun Sheng, Yue Dong. Xiao Liang. Eric, Chao Chang, and Yan Xu. Large scale image completion via co-modulated generative adversarial networks. In International Conference on Learning Representations, 2020.
Chuanxia Zheng, Tat-Jen Cham, and Jianfei Cai. Pluralistic image completion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1438-1447, 2019.
13

---

Published as a conference paper at ICLR 2024
Supplementary Material
A PROOF OF THEOREM
The proof contains two main pairs: (i) shows that the forward pass computes Ez, II, wy (ab) p(aro). and (ii) demonstrates the backward pass computes the conditional probabilities prPM (2)) [z (2, z.)).
Correctness of the forward pass We show by induction that the forward value fw,, of every node computes Ex, IsE (x(x%) p((0))-
Base case: input nodes. By definition, for every input node defined on variable Xi ((n). its forward value is Eιo Wi (x²) (x.p).
Inductive case: product nodes. For every product node n, assume the forward value of its every child node satisfies fw, = Emo IhEo(e) w;(z)) Pm Pm())) (#o). Note that the forward value of product
nodes is computed according to Equation (6),
we have
fwn
II
fWe.
cEin(n)
II cEin(n) ae iEo(c)
Σ
II
wr(ah) pa(xo);
=
II
II
w;(aa)) Pe((x)),
2o cEin(n) (EO(C)
(x(z))
II (x()))
2o iEo(n)
nEin(n)
II
we (x)) Pa (xr);
EE((n)
where (a) follows from the fact that scopes of the children Φ(c) are disjoint, and the child PCs (er)) are defined disjoint sets; (b) follows from the fact that <(n) Useinos) Φ(c); (c) follows the definition in Equation (6).
Inductive case: sum nodes. Similar to the case of product nodes, for every sum node n, we assume the forward value of its children satisfies the induction condition. We have
fHn = Σ
On,c
fwe:
cEin(n)
Σ On,e
Σ
wi(2)) Pe(aro), iEo(C)
II
cEin(n)
II
Σ
Ón.e - Po(20))
iEo (Ed(n)
eEin(n)
(
Σ
II
wi(x))
wi
Pm (xo),
(C)(n)
where (a) holds since Vc E in(n), o(c) ((n), and (b) follows from Equation 6).
Therefore, the forward value every node n is defined by fw, = Ez, IIE wx(xi) Pm (xx).
Correctness of the backward pass We first provide an intuitive semantics for the backward value bk, of every node: for every node if its forward value fu,, were to set to fw', (the other inputs of the PC remains unchanged), the value at the root node n, would change to (1 bk,) fwn, + bk, fun." fw'//fw,, In the following, we prove this result by induction over the root node.
Base case: the PC rooted at n. Denote bk""" as the backward value of node n w.r.t. the PC rooted at ny. Since by definition bk" 1, have that when the value of is changed to fw the root node's
14

---

Published as a conference paper at ICLR 2024
value becomes
(1 bk,)) fun. + bk, fwn ff fn/n-
Inductive case: sum node. Suppose the statement holds for all children of a sum node m. Define bk as the backward value of edge (n, c) for the PC rooted m. Following the definition of the backward values, we have E LeEin(m) bk bk When the value of n is changed fw the value of m becomes:
Σ mEin(m)
mmo fw =
Σ eEin(m)
mm.c- [[1 bkū)) fwe + bkY fwe W///fWn]
m fwet
mm,e bky fwe (fw 1),
eEin(m)
cEin(m)
fWm
fum
mm
Iwe (EW', Iwnn 1):
Om,e fWc
cEin(m)
ffm
bk fum (fW///WW - 1),
eEin(m)
bkr
= (1 bk
fwm + bk fWm fu,,/ ffnn
Inductive case: product node. Suppose the statement holds for all children of product node m. Thanks to decomposability, at most one of m''s children can an ancestor n. Denote this child as e'. When the value of n is changed to fw the value of m becomes:
II
fw
II
fWe [[1 bkz Iwe bky fwe [W/]/
cEin(m))cce
cEin(m).cgee
(a)
II fwa [(1 - ) fuc + bk"" fwz fu/,/ /fn]],
cEin(m).ccte
(1 - bkk)) fwe + bk" fwe fuly/
where (a) holds since bkl tion (6)
bky and (b) follows from the definition of product nodes in Equa-
Next, assume that the input nodes are all indicators in the form of 1[X, = x.). In fact, any discrete univariate distribution can be represented as mixture (sum node) of indicators. By induction, we can show that the sum of backward values of all input nodes corresponding to a variable X; is 1, since sum nodes only "divide" the backward value, and product nodes preserve the backward value sent to them. By setting the value of the input node [X; æı), we are essentially computing Hi W (xzz)) [X; = -;} p(x)). Therefore, the backward values of these input nodes are proportional the target conditional probability PrPm (it Dr, (2/ x/))
We are left with proving that the sum of backward values of all input nodes corresponding to variable X, equals 1. To see this, consider the subset nodes whose scope contains X,. This subset of nodes represents a DAG with the root node as the only source node and input nodes of variables X; as the sink. Consider the backward algorithm as computing flows the DAG. For every node non-sink node, the amount of flow it accepts equals the amount it sends. Specifically, product nodes send all their flow to their only child node (according to decomposability. at most one child a product node contains X, in its scope); for every sum node the sum of flows sent its children equal to the flow receives. Since the flow sent by all source nodes equals the flow received by all sink nodes, we conclude that the backward values of the input nodes for variable X; sum up to 1.
15

---

Published as a conference paper at ICLR 2024
B DESIGN CHOICES FOR HIGH-RESOLUTION GUIDED IMAGE INPAINTING
In all experiments, we compute w (2)) by first drawing samples from Ž II, w w and then feed them to the VQ-GAN's encoder. For every sample, we get distribution over variable Zj. w (2( (z6) is then computed as the mean of the four distributions. In the following decoding phase that computes Frrm (oo (r,, =b)) == R (-Ia., a3) (p(@)) Eo]], we draw 8 random samples from prPM ( (at, mt))
to estimate prPM (Tol a.y. ).))
In the following, we describe the hyperparameters of the adopted VQ-GAN for all three datasets:
Table 2: Hyperparameters of the adopted VQ-GAN models for Tiramisu.
CelebA-HQ
ImageNet LSUN-Bedroom
# latent variables
16 x 16
16 x 16
16 X 16
Vocab size
1024
16384
16384
Additional hyperparameters of Tiramisu For the distribution mixing hyperparameter a (cf. Section 3). we use an exponential decay schedule from with temperature parameter Specifically, the mixing hyperparameter at time step T is
(b-a) exp( (- (-X. +
We further define cutoff parameter feut such that when S leuts the TPM guidance is not used. In all experiments, we used the first three samples in the validation set to tune the mixing hyperparameters. Hyperparameters are given in the following table. all settings, we have 250.
Table 3: Mixing hyperparameters of Tiramisu.
CelebA-HQ
ImageNet -SUN-Bedroom
0.8
0.8
0.8
1.0
1.0
1.0
2.0
2.0
2.0
brut
200
235
235
C PC LEARNING DETAILS
C.I THE EM PARAMETER LEARNING ALGORITIM
As illustrated by Definition when performing a feedforward evaluation (i.e., Equation (6)). PC takes as input sample and outputs its probability (x). Given dataset D, our goal learn set of PC parameters (including sum edge parameters and input node/distribution parameters) to maximize the MILE objective: ExED log p.. (a:). The Sxpectation-Maxiiiaaa natural way to learn PC parameters since PCs can be viewed as latent variable models with hierarchically nested latent space (Pcharz et al. 2016). There are two interpretations of the EM learning algorithm for PCs: one based on gradients (Peharz et al. 2020) and the other based new concept called circuit flows (Choi et al. 2021 We use the gradient-basee interpretation since is easier to understand.
algorithm
Note that the feedforward computation of PCs is differentiable and can modeled by a computation graph. Therefore, after computing the log-likelihood log Pa(r)) (xr) of sample æ, we can efficiently compute its gradient with respect to all PC parameters via the backpropagation algorithm. Given mini-batch of samples, we use the backpropagation algorithm to accumulate gradients for every parameter. Take sum parameters as an example. Define the cumulative gradient of On,c as Jn,e, the updated parameters (On,eteein(n) for every sum node given by:
Dn.c On.o.
On. +- (1 a)) a)) On.c + a Emein(n) In.m 6n,m'
where (0, 1] is the step size. For input nodes, since only use categorical distributions that can be equivalently represented as a mixture over indicator leaves (i.c., a sum node connecting these indicators), optimizing leaf parameters is equivalent the sum parameter learning process.
16

---

Published as a conference paper at ICLR 2024
C.2 DETAILS THE PC LEARNING PIPELINE
PC structure We adopt variant of the original PD structure proposed in Poon & Domingos (201T). Specifically, starting from the whole image, the PD structure gradually uses product nodes to horizontally vertically split the variable scope into half. As result, the scope of every node represents patch (of variable size) in the original image. We use categorical input nodes in accordance with the VQ-GAN's latent space. We treat the set of parameters belonging nodes with the same scope as the parameters of the scope. Based on the original structure, we further tie the parameters representing every pixel and every x 2 patch. Since the marginal distribution of every latent variable should be similar thanks to the spatial invariance of images.
Parameter learning This paper uses the latent variable distillation (LVD) technique (Liu al. 2022b 2023 to initiate the PC parameters before further fine-tuning them with the E.M algorithm described in Appendix [C.]] Intuitively, LVD provides extra supervision PC optimizers through semantic-awan latent variable assignments extracted from deep generative models. We refer readers the original papers for more details.
After initializing PC parameters with LVD, we further fine-tune the parameters with EM with the following hyperparameters:
Table 4: Hyperparameters of EM fine-tuning process.
Name
Value
Step size
1.0
Batch size
20000
Pseudocount
0.1
# iterations
200
D DETAILS OF THE MAIN EXPERIMENTS AND THE BASELINES
Adopted Masks Six of the seven adopted mask types are shown in Figure (gray indicates masked region). We adopt the wide masks from Lugmayr et al. (2022); Suvorov et al. (2022). There are 100 masks generated by uniformly sampling from polygonal chains dilated by a high random width and rectangles of arbitrary aspect ratios.
Left
Top
Expund
The "wide" masks
can be downloaded from
Expand2
V-strip
H-strip
http:riiie.oooll..ooooooooooo com wtw.://oco...m....///// com11 Skty:11AAnSS/11133000000000
Figure 6: Used masks.
which is provided
by Lugmayr et al. 2022).
For all inpainting algorithms, we adopt the same diffusion model checkpoint pretrained by Lugmayr et al.] (2022) (for CelebA-HQ) and OpenAl (for ImageNet and LSUN- com/openai//uided guidedu diffusion). The links to the check-
Pretrained Models
Bedroom; ht ttttps: //gtttub..... com/ http:/ppnnaaiiggee points for all three datasets are listed below.
CelebA-HQ:
ImageNet:
httpss//ppenajpubllc........... wi windows.net//li1 htt.ootww.../aaaaaoa////222.22..
jul - 201-2001/2566x2 diffusion.pt and
LSUN-Bedroom: wttpph/wwhhhtnooe/..a.aaaallllla
jul
Data
For CelebA-HQ and LSUN-Bedroom, use the first 100 images in the validation set. We
adopt the validation split of CelebA-HQ following Suvorov et al. (2022). For ImageNet, we use random validation image for the first 100 classes.
17

---

Published as a conference paper at ICLR 2024
Table 5: User study results. We report the vote difference (%), i.c., [percentage of votes Tiramisu] [percentage of votes to the baseline]. The higher the vote difference value, the more the annotators prefer images generated by Tiramisu compared the baseline.
Tasks
Algorithms
Dataset
Mask
Tiramisu (ours) CoPaint
RePaint
DPS
Expand1
Reference Reference
22
CelebA-HQ
Wide
26
22
Expandl
Reference Reference
32
24
ImageNet
Wide
14
Expand1
Reference Reference
LSUN-Bedroom
Wide
-6
E ADDITIONAL EXPERIMENTS
E. USER STUDY
Since image inpainting is an ill-posed problem and LPIPS alone may not be sufficient to indicate the performance of each algorithm, we recruited human evaluators to evaluate the quality of inpainted images. Specifically, for every baseline method, we sample inpainted image pairs from the baseline and Tiramisu using the same inputs (source image and mask). For every image pair, the evaluator is provided with both inpainted images and is tasked to select the better one based the following criterion: images that visually look more natural and without artifacts (c.g., blurry, distorted). A screenshot of the interface is shown in Figure 7
The user study is conducted on the three strongest baselines based on their overall LPIPS scores: CoPaint (Zhang al. (023a), RePaint (Lugmayr al. 2022), and DPS (Chung al.. 2022). We use two mask types for comparison: "expand1" and "wide". For every comparison, we report the vote difference (%), which is the percentage of votes Tiramisu subtracted by that of the baseline. A positive vote difference value means images generated by Tiramisu are preferred compared to the baselines, while negative value suggests that the baseline is better than Tiramisu.
We adopt the three most competitive baselines, i.c., CoPaint, RePaint, and DPS, based on their average L.IPS scores [T. For all three datasets, we conduct user studies on two types of masks: "expand1" and "wide". Results are shown in Table 5 The vote difference scores are mostly high, indicating the superior inpainting performance of Tiramisu. Additionally, we observe that Tiramisu generally performs better with the "expandl" mask (with larger to-be-inpainted regions), which suggests that Tiramisu may be more helpful in the case large-hole image inpainting.
E.2 ADDITIONAL QUALITATIVE RESULTS
Please refer Figure
10 for additional qualitative results on all three adopted datasets.
F DETAILS OF THE SEMANTIC FUSION EXPERIMENT
The mixing hyperparameters the same described in Appendix
B
The VQ-GAN encoder first generates embedding for every latent variable Zi, and it is then discretized with the VQ codebook by selecting the ID in the codebook that has the minimum L.2 distance with e. We soften this process by setting (ī) = exp(-Ile - e Aar). where e, the jth embedding in the codebook, and Aet is the temperature that controls the semantic coherence level of the generated images. The closer Age is the higher the coherence level.
18

---

Published as a conference paper at ICLR 2024
Image Inpainting Evaluator
Candidate 1
Candidate
inpainted image:
Candidate
Candidate
Please select the better image based the following criterion: images that visually look natural and without artifacts (e-g,, blurry, distorted).
Submit Results
Figure 7: User study interface.
19

---

Published as a conference paper at ICLR 2024
Image
Resample
DPS
DDRM
DDNM
RePaint
CoPaint
Tiramisu
Left
Top
Expand1
Expand2
V-strip
H-strip
Figure 8: Additional qualitative results on CelebA-HQ with six mask types.
20

---

Published as a conference paper at ICLR 2024
Image
Resample
DPS
DDRM
DDNM
RePaint
CoPaint
Tiramisu
Left
Тop
Expand1
Expand2
V-strip
H-strip
Figure 9: Additional qualitative results ImageNet with six mask types.
21

---

Published as a conference paper at ICLR 2024
Image Resample
DPS
DDRM
DDNM
RePaint
CoPaint
Tiramisu
Left
Top
Expand1
Expand2
V-strip
H-strip
Figure 10: Additional qualitative results on LSUN-Bedroood Bedroom with six mask types.
22


Reviews:
[{"review_id": "wgrrcLA7zo", "reviewer": "Reviewer_yw5k", "summary": "This paper proposes to use TPM for conditional image generation, specifically image inpainting, in diffusion models. Previous methods usually use a hard pixel reset or gradient backward to enforce the image to be coherent with the input image for image inpainting using pre-trained diffusion models. This paper, on the other hand, attempts to utilize the TPM along with the diffusion models to enforce the image to be coherent. At each timestep, the proposed method reconstructs the $x_0$ with both the diffusion model and TPM and takes the geometric mean to get the output. Results are compared on multiple datasets including CelebA, LSUN-Bedroom, and ImageNet.", "questions": "From Figure 1 and Table 3, there are some hyper-parameters specifically tuned for different datasets especially $t_{cut}$ which has also been applied in many previous works, could the authors provide an ablation study over the selection of the hyper-parameters?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The use of TPM for the conditional generation of diffusion models is interesting.\n2. The overall quantitative results look good compared to previous methods.", "weaknesses": "1. The comparison only contains six different masks. In real application, the cases where the images are masked by some texts or patterns are also very common. It would be ideal to see more comparisons of such masks in arbitrary shapes.\n2. The table only contains LPIPS for quantitative measurement, however, as image inpainting is an ill-posed problem, a user study would be beneficial in this case as previous works such as [1][2] perform.\n\n[1] Towards Coherent Image Inpainting Using Denoising Diffusion Implicit Models\\\n[2] Repaint: Inpainting using denoising diffusion probabilistic models", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IJedVQ5xq1", "reviewer": "Reviewer_fJmV", "summary": "This paper introduces a novel method that integrates Tractable Probabilistic Models, particularly Probabilistic Circuits, to address the challenges in controlling diffusion models for image inpainting tasks. This approach aims to achieve more precise and efficient inpainting by leveraging the exact computation of constrained posteriors provided by TPMs.​", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper appears to present a novel approach to the problem of image inpainting using diffusion models. The integration of Tractable Probabilistic Models (TPMs), specifically Probabilistic Circuits (PCs), to guide the denoising process of diffusion models is an inventive combination of existing ideas. \nThis creative synergy seems to address the intractability issue inherent in exact conditioning required for tasks like inpainting. Additionally, the paper builds upon prior advances to scale up PCs for guiding the image generation process, which could be considered an original contribution in terms of improving and extending existing methodologies.", "weaknesses": "1. The TPMs seem to be a general design, while this work constrain the application to image inpainting only, I am not sure about the intuition of this specific application. How about the potential of this method for general conditional generation? \n\n2. In section 6.2, it says \"we only need to incorporate guidance from the TPM in the early denoising stages to control the global semantics of the image; fine-grained details can be later refined by the diffusion model. As a result, TPM is only required in the first ∼20% denoising steps\". Here, more experimental analysis of the TPM steps are expected, including the effect on generation quality, semantic coherence, and computational efficiency.\n\n3. Limitations and Failure Cases: A discussion of the method's limitations and failure cases are not addressed in this research, which would be beneficial for the application of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FLb1y47QJ9", "reviewer": "Reviewer_rz93", "summary": "This paper investigated image inpainting using a pre-trained diffusion model by using the proposed TPM approach to enforce the inpainting constraints. Unlike repaint or copaint that either enforce the inpainting constraints through the time travel technique or gradient-based methods to optimize, this paper proposes to model p_\\theta{x_0} by PC, which turns the computation into a normalized multiplication of the model weight based on the graph. The proposed method was combined with copaint and compared with existing methods. The LPIPS value got slightly improved on three commonly used datasets: CelebA-HQ, ImageNet, LSUN-Bedroom. Visual examples were presented and computing cost was discussed.", "questions": "Will code be released upon publication of this work?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Inpainting using pre-trained diffusion is an interesting direction to explore and modeling p_\\theta{x_0} provides an alternative angle to look into this problem. \n- The presentation is clear and results show the potential of the proposed method. On the three datasets, CelebA-HQ, ImageNet, LSUN-Bedroom, with masks of different shapes or at different positions, the proposed approach achieved higher LPIPS scores mostly. \n- A practical approximation to apply the proposed methods for high-resolution imprinting was discussed and proposed.", "weaknesses": "- The computing cost is related to the size of the hole as well as the network architecture. As authors have mentioned, it also related to resolution. So instead of claiming 10% additional computation overhead, a detailed analysis is more helpful. \n- Number-wise the improvement on LPIPS value compared to CoPaint, or even RePaint is minor. How about other metrics? Or user studies?\n- Section 4.2 reads slightly disconnected from Section 4.1, especially the introduction of the equation 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sFKgqJ67ra", "reviewer": "Reviewer_dUar", "summary": "This paper introduces a method of incorporating Probabilistic Circuits (PCs) into diffusion models, with the authors claiming that this approach can encourage diffusion models to generate structurally more coherent images in image inpainting.", "questions": "1) I cannot fully understand the details of the method proposed in this paper (e.g., how were the weights in the PC obtained). I would appreciate it if the authors could provide pseudocode to enhance the method's readability further.\n\n2) LPIPS alone may not be sufficient to assess the quality of generated images. We recommend that the authors report metrics such as FID, U-IDS, etc.\n\n\nIf I have misunderstood, please point it out.\n\nI am very willing to improve the rating after reading your rebuttal and considering the opinions of other reviewers.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In this paper, the Tractable Probabilistic Models (TPMs) are first introduced into the task of controllable image inpainting. Experimental results demonstrate that this approach encourages the model to generate higher-quality samples with only a limited computational cost increase.\nThe experimental results seem visually plausible.", "weaknesses": "1) The readability of this paper is relatively low. We believe that the author should explain in the introduction and method sections whether the method proposed is training or non-training. If it is the former, the loss function and the parts of the network that need to be updated should be stated explicitly. If it is the latter, the pseudo-code of the algorithm should be given.\n\n2) The experimental section lacks metrics. \n\n3) Have the authors tried irregular masks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)