# Photorealistic Video Generation with Diffusion Models

Agrim Gupta1,2,∗ Lijun Yu2 Kihyuk Sohn2 Xiuye Gu2 Meera Hahn2 Li Fei-Fei1
Irfan Essa2,3 Lu Jiang2 José Lezama2
1 Stanford University 2 Google Research 3 Georgia Institute of Technology

###### Abstract

We present W.A.L.T, a transformer-based approach for photorealistic video
generation via diffusion modeling. Our approach has two key design decisions.
First, we use a causal encoder to jointly compress images and videos within a
unified latent space, enabling training and generation across modalities.
Second, for memory and training efficiency, we use a window attention
architecture tailored for joint spatial and spatiotemporal generative
modeling. Taken together these design decisions enable us to achieve state-of-
the-art performance on established video (UCF-101 and Kinetics-600) and image
(ImageNet) generation benchmarks without using classifier free guidance.
Finally, we also train a cascade of three models for the task of text-to-video
generation consisting of a base latent video diffusion model, and two video
super-resolution diffusion models to generate videos of $512\times 896$
resolution at $8$ frames per second.

Figure 1: W.A.L.T samples for text-to-video generation. Our approach can
generate high-resolution, temporally consistent photorealistic videos from
text prompts. The samples shown are $512\times 896$ resolution over $3.6$
seconds duration at $8$ frames per second.

00footnotetext: ∗Work partially done during an internship at Google.

##  1 Introduction

Transformers [73] are highly scalable and parallelizable neural network
architectures designed to win the hardware lottery [39]. This desirable
property has encouraged the research community to increasingly favor
transformers over domain-specific architectures in diverse fields such as
language [55, 56, 57, 26], audio [1], speech [58], vision [18, 30], and
robotics [7, 89, 5]. Such a trend towards unification allows researchers to
share and build upon advancements in traditionally disparate domains. Thus,
leading to a virtuous cycle of innovation and improvement in model design
favoring transformers.

A notable exception to this trend is generative modelling of videos. Diffusion
models [67, 69] have emerged as a leading paradigm for generative modelling of
images [33, 16] and videos [36]. However, the U-Net architecture [62, 33],
consisting of a series of convolutional [46] and self-attention [73] layers,
has been the predominant backbone in all video diffusion approaches [33, 16,
36]. This preference stems from the fact that the memory demands of full
attention mechanisms in transformers scale quadratically with input sequence
length. Such scaling leads to prohibitively high costs when processing high-
dimensional signals like video.

Latent diffusion models (LDMs) [61] reduce computational requirements by
operating in a lower-dimensional latent space derived from an autoencoder [75,
72, 20]. A critical design choice in this context is the type of latent space
employed: spatial compression (per frame latents) versus spatiotemporal
compression. Spatial compression is often preferred because it enables
leveraging pre-trained image autoencoders and LDMs, which are trained on large
paired image-text datasets. However, this choice increases network complexity
and limits the use of transformers as backbones, especially in generating
high-resolution videos due to memory constraints. On the other hand, while
spatiotemporal compression can mitigate these issues, it precludes the use of
paired image-text datasets, which are much larger and diverse than their video
counterparts.

We present Window Attention Latent Transformer (W.A.L.T): a transformer-based
method for latent video diffusion models (LVDMs). Our method consists of two
stages. First, an autoencoder maps both videos and images into a unified,
lower-dimensional latent space. This design choice enables training a single
generative model jointly on image and video datasets and significantly reduces
the computational burden for generating high resolution videos. Subsequently,
we propose a new design of transformer blocks for latent video diffusion
modeling which is composed of self-attention layers that alternate between
non-overlapping, window-restricted spatial and spatiotemporal attention. This
design offers two primary benefits: firstly, the use of local window attention
significantly lowers computational demands. Secondly, it facilitates joint
training, where the spatial layers independently process images and video
frames, while the spatiotemporal layers are dedicated to modeling the temporal
relationships in videos.

While conceptually simple, our method provides the first empirical evidence of
transformers’ superior generation quality and parameter efficiency in latent
video diffusion on public benchmarks. Specifically, we report state-of-the-art
results on class-conditional video generation (UCF-101 [70]), frame prediction
(Kinetics-600 [9]) and class conditional image generation (ImageNet [15])
without using classifier free guidance. Finally, to showcase the scalability
and efficiency of our method we also demonstrate results on the challenging
task of photorealistic text-to-video generation. We train a cascade of three
models consisting of a base latent video diffusion model, and two video super-
resolution diffusion models to generate videos of $512\times 896$ resolution
at $8$ frames per second and report state-of-the-art zero-shot FVD score on
the UCF-101 benchmark.

Figure 2: W.A.L.T. We encode images and videos into a shared latent space. The
transformer backbone processes these latents with blocks having two layers of
window-restricted attention: spatial layers capture spatial relations in both
images and video, while spatiotemporal layers model temporal dynamics in
videos and passthrough images via identity attention mask. Text conditioning
is done via spatial cross-attention.

##  2 Related Work

##### Video Diffusion Models.

Diffusion models have shown impressive results in image [67, 68, 52, 33, 61,
38] and video generation [36, 34, 66, 29, 4, 24]. Video diffusion models can
be categorized into pixel-space [36, 34, 66] and latent-space [31, 83, 4, 24]
approaches, the later bringing important efficiency advantages when modeling
videos. Ho et al. [36] demonstrated that the quality of text conditioned video
generation can be significantly improved by jointly training on image and
video data. Similarly, to leverage image datasets, latent video diffusion
models inflate a pre-trained image model, typically a U-Net [62], into a video
model by adding temporal layers, and initializing them as the identity
function [34, 66, 4]. Although computationally efficient, this approach
couples the design of video and image models, and precludes spatiotemporal
compression. In this work, we operate on a unified latent space for images and
videos, allowing us to leverage large scale image and video datasets while
enjoying computational efficiency gains from spatiotemporal compression of
videos.

##### Transformers for Generative Modeling.

Multiple classes of generative models have utilized Transformers [73] as
backbone, such as, Generative adversarial networks [47, 42, 85],
autoregressive [59, 20, 10, 80, 77, 21, 11, 74, 81, 27, 78] and diffusion [2,
53, 22, 87, 41, 50] models. Inspired by the success of autoregressive
pretraining of large language models [55, 56, 57], Ramesh et al. [59] trained
a text-to-image generation model by predicting the next visual token obtained
from an image tokenizer. Subsequently, this approach was applied to multiple
applications including class-conditional image generation [20, 79], text-to-
image [59, 80, 17, 76] or image-to-image translation [21, 77]. Similarly, for
video generation, transformer-based models were proposed to predict next
tokens using 3D extensions of VQGAN [78, 23, 81, 37] or using per frame image
latents [27]. Autoregressive sampling of videos is typically impractical given
the very long sequences involved. To alleviate this issue, non-autoregressive
sampling [10, 11], _i.e_. parallel token prediction, has been adopted as a
more efficient solution for transformer-based video generation [27, 74, 81].
Recently, the community has started adopting transformers as the denoising
backbone for diffusion models in place of U-Net [38, 53, 87, 12, 50]. To the
best of our knowledge, our work is the first successful empirical
demonstration (§ 5.1) of a transformer-based backbone for jointly training
image and video latent diffusion models.

##  3 Background

Diffusion formulation. Diffusion models [67, 33, 69] are a class of generative
models which learn to generate data by iteratively denoising samples drawn
from a noise distribution. Gaussian diffusion models assume a forward noising
process which gradually applies noise ($\boldsymbol{\epsilon}$) to real data
($\boldsymbol{x_{0}}\sim p_{\text{data}}$). Concretely,

$\boldsymbol{x_{t}}=\sqrt{\gamma(t)}\ \boldsymbol{x_{0}}+\sqrt{1-\gamma(t)}\
\boldsymbol{\epsilon},$ (1)

where
$\boldsymbol{\epsilon}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{I}),t\in\left[0,1\right]$,
and $\gamma(t)$ is a monotonically decreasing function (noise schedule) from
$1$ to $0$. Diffusion models are trained to learn the reverse process that
inverts the forward corruptions:

$\mathbb{E}_{x\sim
p_{\text{data}},t\sim\mathcal{U}(0,1),\boldsymbol{\epsilon}\sim\mathcal{N}(\boldsymbol{0},\boldsymbol{I})}\left[\left\|\boldsymbol{y}-f_{\theta}(\boldsymbol{x_{t}};\boldsymbol{c},t)\right\|^{2}\right],$
(2)

where $f_{\theta}$ is the denoiser model parameterized by a neural network,
$\boldsymbol{c}$ is conditioning information e.g., class labels or text
prompts, and the target $\boldsymbol{y}$ can be random noise
$\boldsymbol{\epsilon}$, denoised input $\boldsymbol{x_{0}}$ or
$\boldsymbol{v}=\sqrt{1-\gamma(t)}\ \boldsymbol{\epsilon}-\sqrt{\gamma(t)}\
\boldsymbol{x_{0}}$. Following [63, 34], we use $\boldsymbol{v}$-prediction in
all our experiments.

Latent diffusion models (LDMs). Processing high-resolution images and videos
using raw pixels requires considerable computational resources. To address
this, LDMs operate on the low dimensional latent space of a VQ-VAE [72, 20].
VQ-VAE consists of an encoder $E(x)$ that encodes an input video
$x\in\mathbb{R}^{T\times H\times W\times 3}$ into a latent representation
$z\in\mathbb{R}^{t\times h\times w\times c}$. The encoder downsamples the
video by a factor of $f_{s}=H/h=W/w$ and $f_{t}=T/t$, where $T=t=1$
corresponds to using an image autoencoder. An important distinction from the
original VQ-VAE is the absence of a codebook of quantized embeddings as
diffusion models can operate on continous latent spaces. A decoder $D$ is
trained to predict a reconstruction of the video, $\hat{x}$, from $z$.
Following VQ-GAN [20], reconstruction quality can be further improved by
adding adversarial [25] and perceptual losses [43, 86].

##  4 W.A.L.T

###  4.1 Learning Visual Tokens

A key design decision in video generative modeling is the choice of latent
space representation. Ideally, we want a shared and unified compressed visual
representation that can be used for generative modeling of both images and
videos [74, 82]. The unified representation is important because joint image-
video learning is preferable due to a scarcity of labeled video data [34],
such as text-video pairs. Concretely, given a video sequence
$x\in\mathbb{R}^{(1+T)\times H\times W\times C}$, we aim to learn a low-
dimensional representation $z\in\mathbb{R}^{(1+t)\times h\times w\times c}$
that performs spatial-temporal compression by a factor of $f_{s}=H/h=W/w$ in
space and a factor of $f_{t}=T/t$ in time. To enable a unified representation
for both videos and static images, the first frame is always encoded
independently from the rest of the video. This allows static images
$x\in\mathbb{R}^{1\times H\times W\times C}$ to be treated as videos with a
single frame, _i.e_. $z\in\mathbb{R}^{1\times h\times w\times c}$.

We instantiate this design with the causal 3D CNN encoder-decoder architecture
of the MAGVIT-v2 tokenizer [82]. Typically the encoder-decoder consists of
regular 3D convolution layers which cannot process the first frame
independently [81, 23]. This limitation stems from the fact that a regular
convolutional kernel of size $(k_{t},k_{h},k_{w})$ will operate on
$\left\lfloor\frac{k_{t}-1}{2}\right\rfloor$ frames before and
$\left\lfloor\frac{k_{t}}{2}\right\rfloor$ frames after the input frames.
Causal 3D convolution layers solve this issue as the convolutional kernel
operates on only the past $k_{t}-1$ frames. This ensures that the output for
each frame is influenced solely by the preceding frames, enabling the model to
tokenize the first frame independently.

After this stage, the input to our model is a batch of latent tensors
$z\in\mathbb{R}^{(1+t)\times h\times w\times c}$ representing a single video
or a stack of $1+t$ independent images (Fig. 2). Different from [82], our
latent representation is real-valued and quantization-free. In the section
below we describe how our model jointly processes a mixed batch of images and
videos.

###  4.2 Learning to Generate Images and Videos

Patchify. Following the original ViT [18], we “patchify” each latent frame
independently by converting it into a sequence of non-overlapping $h_{p}\times
w_{p}$ patches where $h_{p}=h/p$, $w_{p}=w/p$ and $p$ is the patch size. We
use learnable positional embeddings [73], which are the sum of space and time
positional embeddings. Position embeddings are added to the linear projections
[18] of the patches. Note that for images, we simply add the temporal position
embedding corresponding to the first latent frame.

Window attention. Transformer models composed entirely of global self-
attention modules incur significant compute and memory costs, especially for
video tasks. For efficiency and for processing images and videos jointly we
compute self-attention in windows [73, 27], based on two types of non-
overlapping configurations: spatial (S) and spatiotemporal (ST), _cf_. Fig. 2.
Spatial Window (SW) attention is restricted to all the tokens within a latent
frame of size $1\times h_{p}\times w_{p}$ (the first dimension is time). SW
models the spatial relations in images and videos. Spatiotemporal Window (STW)
attention is restricted within a 3D window of size $(1+t)\times
h_{p}^{\prime}\times h_{w}^{\prime}$, modeling the temporal relationships
among video latent frames. For images, we simply use an identity attention
mask ensuring that the value embeddings corresponding to the image frame
latents are passed through the layer as is. Finally, in addition to absolute
position embeddings we also use relative position embeddings [49].

Our design, while conceptually straightforward, achieves computational
efficiency and enables joint training on image and video datasets. In contrast
to methods based on frame-level autoencoders [24, 4, 27], our approach does
not suffer from flickering artifacts, which often result from encoding and
decoding video frames independently. However, similar to Blattmann et al. [4],
we can also potentially leverage pre-trained image LDMs with transformer
backbones by simply interleaving STW layers.

###  4.3 Conditional Generation

To enable controllable video generation, in addition to conditioning on
timestep $t$, diffusion models are often conditioned on additional conditional
information $\boldsymbol{c}$ such as class labels, natural language, past
frames or low resolution videos. In our transformer backbone, we incorporate
three types of conditioning mechanisms as described in what follows:

Cross-attention. In addition to self-attention layers in our window
transformer blocks, we add a cross-attention layer for text conditioned
generation. When training models on just videos, the cross-attention layer
employs the same window-restricted attention as the self-attention layer,
meaning S/ST blocks will have SW/STW cross-attention layers (Fig. 2). However,
for joint training, we only use SW cross-attention layers. For cross-attention
we concatenate the input signal (query) with the conditioning signal (key,
value) as our early experiments showed this improves performance.

AdaLN-LoRA. Adaptive normalization layers are an important component in a
broad range of generative and visual synthesis models [52, 16, 54, 44, 19,
53]. A simple way to incorporate adaptive layer normalization is to include
for each layer $i$, an MLP layer to regress a vector of conditioning
parameters $A^{i}=\texttt{MLP}(\boldsymbol{c}+\boldsymbol{t})$, where
$A^{i}=\texttt{concat}(\gamma_{1},\gamma_{2},\beta_{1},\beta_{2},\alpha_{1},\alpha_{2})$,
$A^{i}\in\mathbb{R}^{6\times d_{\texttt{model}}}$, and
$\boldsymbol{c}\in\mathbb{R}^{d_{\texttt{model}}}$,
$\boldsymbol{t}\in\mathbb{R}^{d_{\texttt{model}}}$ are the condition and
timestep embeddings. In the transformer block, $\gamma$ and $\beta$ scale and
shift the inputs of the multi-head attention and MLP layers, respectively,
while $\alpha$ scales the output of both the multi-head attention and MLP
layers. The parameter count of these additional MLP layers scales linearly
with the number of layers and quadratically with the model’s dimensional size
($\texttt{num\\_blocks}\times d_{\texttt{model}}\times 6\times
d_{\texttt{model}}$). For instance, in a ViT-g model with $1$B parameters, the
MLP layers contribute an additional $475$M parameters. Inspired by [40], we
propose a simple solution dubbed AdaLN-LoRA, to reduce the model parameters.
For each layer, we regress conditioning parameters as

$\displaystyle\small A^{1}$
$\displaystyle=\small\texttt{MLP}(\boldsymbol{c}+\boldsymbol{t}),$
$\displaystyle\small A^{i}$ $\displaystyle=\small
A^{1}+W_{b}^{i}W_{a}^{i}(\boldsymbol{c}+\boldsymbol{t})\quad\forall i\neq 1,$
(3)

where $W_{b}^{i}\,{\in}\,\mathbb{R}^{d_{\texttt{model}}\times r}$,
$W_{a}^{i}\,{\in}\,\mathbb{R}^{r\times(6\times d_{\texttt{model}})}$. This
reduces the number of trainable model parameters significantly when
$r\,{\ll}\,d_{\texttt{model}}$. For example, a ViT-g model with $r\,{=}\,2$
reduces the MLP parameters from $475$M to $12$M.

Self-conditioning. In addition to being conditioned on external inputs,
iterative generative algorithms can also be conditioned on their own
previously generated samples during inference [3, 65, 13]. Specifically, Chen
et al. [13] modify the training process for diffusion models, such that with
some probability $p_{\text{sc}}$ the model first generates a sample
$\boldsymbol{\tilde{z}_{0}}=f_{\theta}(\boldsymbol{z_{t}};\boldsymbol{0},\boldsymbol{c},t)$
and then refines this estimate using another forward pass conditioned on this
initial sample:
$f_{\theta}(\boldsymbol{z_{t}};\texttt{stopgrad}(\boldsymbol{\tilde{z}_{0}}),\boldsymbol{c},t)$.
With probability $1-p_{\text{sc}}$, only a single forward pass is done. We
concatenate the model estimate with the input along the channel dimension and
found this simple technique to work well when used in conjunction with
$\boldsymbol{v}$-prediction.

Method | K600 FVD$\downarrow$ | UCF FVD$\downarrow$ | params. | steps
---|---|---|---|---
TrIVD-GAN-FP [51] | 25.7±0.7 | – | – | 1
Video Diffusion [36] | 16.2±0.3 | – | 1.1B | 256
RIN [41] | 10.8 | – | 411M | 1000
TATS [23] | – | 332±18 | 321M | 1024
Phenaki [74] | 36.4±0.2 | – | 227M | 48
MAGVIT [81] | 9.9±0.3 | 76±2 | 306M | 12
MAGVITv2 [82] | 4.3±0.1 | 58±2 | 307M | 24
W.A.L.T-L _Ours_ | 3.3±0.0 | 46±2 | 313M | 50
W.A.L.T-XL _Ours_ | – | 36±2 | 460M | 50

Table 1: Video generation evaluation on frame prediction on Kinetics-600 and
class-conditional generation on UCF-101.

###  4.4 Autoregressive Generation

For generating long videos via autoregressive prediction we also train our
model jointly on the task of frame prediction. This is achieved by
conditioning the model on past frames with a probability of $p_{\text{fp}}$
during training. Specifically, the model is conditioned using
$c_{\text{fp}}=\texttt{concat}(m_{\text{fp}}\circ\boldsymbol{z_{t}},m_{\text{fp}})$,
where $m_{\text{fp}}$ is a binary mask. The binary mask indicates the number
of past frames used for conditioning. We condition on either $1$ latent frame
(image to video generation) or $2$ latent frames (video prediction). This
conditioning is integrated into the model through concatenation along the
channel dimension of the noisy latent input. During inference, we use standard
classifier-free guidance with $c_{\text{fp}}$ as the conditioning signal.

###  4.5 Video Super Resolution

Generating high-resolution videos with a single model is computationally
prohibitive. Following [35], we use a cascaded approach with three models
operating at increasing resolutions. Our base model generates videos at
$128\times 128$ resolution which are subsequently upsampled twice via two
super resolution stages. We first spatially upscale the low resolution input
$\boldsymbol{z^{\text{lr}}}$ (video or image) using a depth-to-space
convolution operation. Note that, unlike training where ground truth low-
resolution inputs are available, inference relies on latents produced by
preceding stages (_cf_. teaching-forcing). To reduce this discrepancy and
improve the robustness of the super-resolution stages in handling artifacts
generated by lower resolution stages, we use noise conditioning augmentation
[35]. Concretely, noise is added in accordance with $\gamma(t)$, by sampling a
noise level as $t_{\text{sr}}\sim\mathcal{U}(0,t_{\text{max\\_noise}})$ and is
provided as input to our AdaLN-LoRA layers.

Method | Cost (Iter$\times$BS) | FID$\downarrow$ | IS$\uparrow$ | params. | steps
---|---|---|---|---|---
BigGAN-deep [6] | - | 6.95 | 171.4 | 160M | 1
LDM-4 [61] | 178k$\times$1200 | 10.56 | 103.5 | 400M | 250
DiT-XL/2 [53] | 7000k$\times$256 | 9.62 | 121.5 | 675M | 250
ADM [16] | - | 7.49 | 127.5 | 608M | 2000
MDT [22] | 6500k$\times$256 | 6.23 | 143.0 | 676M | 250
MaskDiT [87] | 1200k$\times$1024 | 5.69 | 178.0 | 736M | 40
RIN [41] | 600k$\times$1024 | 3.42 | 182.0 | 410M | 1000
simple diffusion [38] | 500K$\times$2048 | 2.77 | 211.8 | 2B | 512
VDM++ [45] | - | 2.40 | 225.3 | 2B | 512
W.A.L.T-L _Ours_ | 437k$\times$1024 | 2.56 | 215.1 | 460M | 50

Table 2: Class-conditional image generation on ImageNet 256$\times$256. We
adopt the evaluation protocol and implementation of ADM [16] and report
results without classifier free guidance.

Aspect-ratio finetuning. To simplify training and leverage broad data sources
with different aspect ratios, we train our base stage using a square aspect
ratio. We fine-tune the base stage on a subset of data to generate videos with
a $9:16$ aspect ratio by interpolating position embeddings.

##  5 Experiments

In this section, we evaluate our method on multiple tasks: class-conditional
image and video generation, frame prediction and text conditioned video
generation and perform extensive ablation studies of different design choices.
For qualitative results, see Fig. 1, Fig. 3, Fig. 4 and videos on our project
website. See appendix for additional details.

###  5.1 Visual Generation

Video generation. We consider two standard video benchmarks, UCF-101 [70] for
class-conditional generation and Kinetics-600 [9] for video prediction with
$5$ conditioning frames. We use FVD [71] as our primary evaluation metric.
Across both datasets, W.A.L.T significantly outperforms all prior works (Tab.
1). Compared to prior video diffusion models, we achieve state-of-the-art
performance with less model parameters, and require $50$ DDIM [68] inference
steps.

patch size $p$ |  FVD$\downarrow$ |  IS$\uparrow$
---|---|---
1 | 60.7 | 87.2
2 | 134.4 | 82.2
4 | 461.8 | 63.9

(a)

st window |  FVD$\downarrow$ |  IS$\uparrow$ | sps
---|---|---|---
$5\times 4\times 4$ | 56.9 | 87.3 | 2.24
$5\times 8\times 8$ | 59.6 | 87.4 | 2.00
$5\times 16\times 16$ | 55.3 | 87.4 | 1.75
full self attn. | 59.9 | 87.8 | 1.20

(b)

$p_{\text{sc}}$ |  FVD$\downarrow$ |  IS$\uparrow$
---|---|---
0.0 | 109.9 | 82.6
0.3 | 76.0 | 86.5
0.6 | 60.0 | 86.8
0.9 | 61.4 | 87.1

(c)

$r$ |  FVD$\downarrow$ |  IS$\uparrow$ | params
---|---|---|---
2 | 60.7 | 87.2 | 313 M
4 | 56.6 | 87.3 | 314 M
16 | 55.5 | 88.0 | 316 M
64 | 54.4 | 87.9 | 324 M
256 | 52.5 | 88.5 | 357 M

(d)

|  FVD$\downarrow$ |  IS$\uparrow$
---|---|---
w/o qk norm [14] | 59.0 | 86.8
w/o latent norm | 67.9 | 87.1
w/o zero snr [48] | 91.0 | 84.2
full method | 60.7 | 87.2

(e)

$c$ |  rFVD$\downarrow$ |  FVD$\downarrow$ |  IS$\uparrow$
---|---|---|---
4 | 37.7 | 86.4 | 84.9
8 | 17.1 | 75.4 | 86.3
16 | 8.2 | 67.0 | 86.0
32 | 3.5 | 83.4 | 82.9

(f)

Table 3: Ablation experiments on UCF-101 [70]. We compare FVD and inception
scores to ablate important design decisions with the default setting: L model,
$1\times 16\times 16$ spatial window, $5\times 8\times 8$ saptiotemporal (st)
window, $p_{\text{sc}}=0.9$, $c=8$ and $r=2$.

Image generation. To verify the modeling capabilities of W.A.L.T on the image
domain, we train a version of W.A.L.T for the standard ImageNet class-
conditional setting. For evaluation, we follow ADM [16] and report the FID
[32] and Inception [64] scores calculated on $50$K samples generated in $50$
DDIM steps. We compare (Table 2) W.A.L.T with state-of-the-art image
generation methods for $256\times 256$ resolution. Our model outperforms prior
works without requiring specialized schedules, convolution inductive bias,
improved diffusion losses, and classifier free guidance. Although VDM++ [45]
has slightly better FID score, the model has significantly more parameters
(2B).

###  5.2 Ablation Studies

We ablate W.A.L.T to understand the contribution of various design decisions
with the default settings: model L, patch size 1, $1\times 16\times 16$
spatial window, $5\times 8\times 8$ spatiotemporal window,
$p_{\text{sc}}=0.9$, $c=8$ and $r=2$.

Patch size. In various computer vision tasks utilizing ViT[18]-based models, a
smaller patch size $p$ has been shown to consistently enhance performance [18,
84, 8, 28]. Similarly, our findings also indicate that a reduced patch size
improves performance (Table LABEL:tab:patch_size).

Window attention. We compare three different STW window configurations with
full self-attention (Table LABEL:tab:window). We find that local self-
attention can achieve competitive (or better) performance while being
significantly faster (up to $2\times$) and requiring less accelerator memory.

Self-conditioning. In Table LABEL:tab:self_cond we study the influence of
varying the self-conditioning rate $p_{\text{sc}}$ on generation quality. We
notice a clear trend: increasing the self conditioning rate from $0.0$ (no
self-conditioning) to $0.9$ improves the FVD score substantially ($44\%$).

AdaLN-LoRA. An important design decision in diffusion models is the
conditioning mechanism. We investigate the effect of increasing the bottleneck
dimension $r$ in our proposed AdaLN-LoRA layers (Table LABEL:tab:adaln_lora).
This hyperparameter provides a flexible way to trade off between number of
model parameters and generation performance. As shown in Table
LABEL:tab:adaln_lora, increasing $r$ improves performance but also increases
model parameters. This highlights an important model design question: given a
fixed parameter budget, how should we allocate parameters - either by using
separate AdaLN layers, or by increasing base model parameters while using
shared AdaLN-LoRA layers? We explore this in Table 4 by comparing two model
configurations: W.A.L.T-L with separate AdaLN layers and W.A.L.T-XL with
AdaLN-LoRA and $r=2$. While both configurations yield similar FVD and
Inception scores, W.A.L.T-XL achieves a lower final loss value, suggesting the
advantage of allocating more parameters to the base model and choosing an
appropriate $r$ value within accelerator memory limits.

Model | AdaLN |  FVD$\downarrow$ |  IS$\uparrow$ | params. | final loss
---|---|---|---|---|---
L | separate | 34.6 | 90.2 | 458M | 0.274
XL | LoRA-2 | 36.7 | 89.4 | 460M | 0.268
Table 4: Parameter matched comparison between AdaLN-LoRA and per layer adaln
layers. See text for details. Figure 3: Qualitative evaluation. Example videos
generated by W.A.L.T from natural language prompts at $512\times 896$
resolution over $3.6$ seconds duration at $8$ frames per second. The W.A.L.T
model is able to generate temporally consistent photorealistic videos that
align with the textual prompt.

Noise schedule. Common latent diffusion noise schedules [61] typically do not
ensure a zero signal-to-noise ratio (SNR) at the final timestep, i.e., at
$t=1,\gamma(t)>0$. This leads to a mismatch between training and inference
phases. During inference, models are expected to start from purely Gaussian
noise, whereas during training, at $t=1$, a small amount of signal information
remains accessible to the model. This is especially harmful for video
generation as videos have high temporal redundancy. Even minimal information
leakage at $t=1$ can reveal substantial information to the model. Addressing
this mismatch by enforcing a zero terminal SNR [48] significantly improves
performance (Table LABEL:tab:misc_improvements). Note that this approach was
originally proposed to fix over-exposure problems in image generation, but we
find it effective for video generation as well.

Autoencoder. Finally, we investigate one critical but often overlooked
hyperparameter in the first stage of our model: the channel dimension $c$ of
the autoencoder latent $z$. As shown in Table LABEL:tab:tokenizer, increasing
$c$ significantly improves the reconstruction quality (lower rFVD) while
keeping the same spatial $f_{s}$ and temporal compression $f_{t}$ ratios.
Empirically, we found that both lower and higher values of $c$ lead to poor
FVD scores in generation, with a sweet spot of $c=8$ working well across most
datasets and tasks we evaluated. We also normalize the latents before
processing them via transformer which further improves performance.

In our transformer models, we use query-key normalization [14] as it helps
stabilize training for larger models. Finally, we note that some of our
default settings are not optimal, as indicated by ablation studies. These
defaults were chosen early on for their robustness across datasets, though
further tuning may improve performance.

Figure 4: Examples of consistent 3D camera motion (5.1 secs). Prompts: _camera
turns around a{blue jay, bunny}, studio lighting, $360^{\circ}$ rotation_.
Best viewed in video format.

###  5.3 Text-to-video

We train W.A.L.T for text-to-video jointly on text-image and text-video pairs
(Sec. 4.2). We used a dataset of $\sim$970M text-image pairs and $\sim$89M
text-video pairs from the public internet and internal sources. We train our
base model at resolution $17\times 128\times 128$ (3B parameters), and two
$2\times$ cascaded super-resolution models for $17\times 128\times
224\rightarrow 17\times 256\times 448$ (L, 1.3B, $p=2$) and $17\times
256\times 448\rightarrow 17\times 512\times 896$ (L, 419M, $p=2$)
respectively. We fine-tune the base stage for the $9:16$ aspect ratio to
generate videos at resolution $128\times 224$. We use classifier free guidance
for all our text-to-video results.

####  5.3.1 Quantitative Evaluation

Evaluating text-conditioned video generation systems scientifically remains a
significant challenge, in part due to the absence of standardized training
datasets and benchmarks. So far we have focused our experiments and analyses
on the standard academic benchmarks, which use the same training data to
ensure controlled and fair comparisons. Nevertheless, to compare with prior
work on text-to-video, we also report results on the UCF-101 dataset in the
zero-shot evaluation protocol in Table 5 [24, 66, 37]. Also see supplement.

Joint training. A primary strength of our framework is its ability to train
simultaneously on both image and video datasets. In Table 5 we ablate the
impact of this joint training approach. Specifically, we trained two versions
of W.A.L.T-L (each with $419$M params.) models using the default settings
specified in § 5.2. We find that joint training leads to a notable improvement
across both metrics. Our results align with the findings of Ho et al. [36],
who demonstrated the benefits of joint training for pixel-based video
diffusion models with U-Net backbones.

Scaling. Transformers are known for their ability to scale effectively in many
tasks [55, 14, 5]. In Table 5 we show the benefits of scaling our transformer
model for video diffusion. Scaling our base model size leads to significant
improvements on both the metrics. It is important to note, however, that our
base model is considerably smaller than leading text-to-video systems. For
instance, Ho et al. [34] trained base model of $5.7$B parameters. Hence, we
believe scaling our models further is an important direction of future work.

Method | IS ($\uparrow$) | FVD ($\downarrow$)
---|---|---
CogVideo (Chinese) [37] | 23.6 | 751.3
CogVideo (English) [37] | 25.3 | 701.6
MagicVideo [88] | - | 699.0
Make-A-Video [66] | 33.0 | 367.2
Video LDM [4] | 33.5 | 550.6
PYoCo [24] | 47.8 | 355.2
W.A.L.T _(Ours)_ 419M (video only) | 26.8 | 598.8
W.A.L.T _(Ours)_ 419M (video + image) | 31.7 | 344.5
W.A.L.T _(Ours)_ 3B (video + image) | 35.1 | 258.1

Table 5: UCF-101 text-to-video generation. Joint training on image and video
datasets in conjunction with scaling the model parameters is essential for
high quality video generation.

Comparison with prior work. In Table 5, we present a system-level comparison
of various text-to-video generation methods. Our results are promising; we
surpass all previous work in the FVD metric. In terms of the IS, our
performance is competitive, outperforming all but PYoCo [24]. A possible
explanation for this discrepancy might be PYoCo’s use of stronger text
embeddings. Specifically, they utilize both CLIP [57] and T5-XXL [60]
encoders, whereas we employ a T5-XL [60] text encoder only.

####  5.3.2 Qualitative Results

As mentioned in § 4.4, we jointly train our model on the task of frame
prediction conditioned on $1$ or $2$ latent frames. Hence, our model can be
used for animating images (image-to-video) and generating longer videos with
consistent camera motion (Fig. 4). See videos on our project website.

##  6 Conclusion

In this work, we introduce W.A.L.T, a simple, scalable, and efficient
transformer-based framework for latent video diffusion models. We demonstrate
state-of-the-art results for image and video generation using a transformer
backbone with windowed attention. We also train a cascade of three W.A.L.T
models jointly on image and video datasets, to synthesize high-resolution,
temporally consistent photorealistic videos from natural language
descriptions. While generative modeling has seen tremendous recent advances
for images, progress on video generation has lagged behind. We hope that
scaling our unified framework for image and video generation will help close
this gap.

## Acknowledgements

We thank Bryan Seybold, Dan Kondratyuk, David Ross, Hartwig Adam, Huisheng
Wang, Jason Baldridge, Mauricio Delbracio and Orly Liba for helpful
discussions and feedback.

## References

  * Agostinelli et al. [2023] Andrea Agostinelli, Timo I Denk, Zalán Borsos, Jesse Engel, Mauro Verzetti, Antoine Caillon, Qingqing Huang, Aren Jansen, Adam Roberts, Marco Tagliasacchi, et al.  MusicLM: Generating music from text.  _arXiv:2301.11325_ , 2023.
  * Bao et al. [2022] Fan Bao, Chongxuan Li, Yue Cao, and Jun Zhu.  All are worth words: a vit backbone for score-based diffusion models.  In _NeurIPS 2022 Workshop on Score-Based Methods_ , 2022.
  * Bengio et al. [2015] Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer.  Scheduled sampling for sequence prediction with recurrent neural networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Blattmann et al. [2023] Andreas Blattmann, Robin Rombach, Huan Ling, Tim Dockhorn, Seung Wook Kim, Sanja Fidler, and Karsten Kreis.  Align your latents: High-resolution video synthesis with latent diffusion models.  In _CVPR_ , 2023.
  * Bousmalis et al. [2023] Konstantinos Bousmalis, Giulia Vezzani, Dushyant Rao, Coline Devin, Alex X Lee, Maria Bauza, Todor Davchev, Yuxiang Zhou, Agrim Gupta, Akhil Raju, et al.  Robocat: A self-improving foundation agent for robotic manipulation.  _arXiv preprint arXiv:2306.11706_ , 2023.
  * Brock et al. [2018] Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale GAN training for high fidelity natural image synthesis.  In _ICLR_ , 2018.
  * Brohan et al. [2022] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, et al.  Rt-1: Robotics transformer for real-world control at scale.  _arXiv preprint arXiv:2212.06817_ , 2022.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 9650–9660, 2021.
  * Carreira et al. [2018] Joao Carreira, Eric Noland, Andras Banki-Horvath, Chloe Hillier, and Andrew Zisserman.  A short note about Kinetics-600.  _arXiv:1808.01340_ , 2018.
  * Chang et al. [2022] Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William T Freeman.  MaskGIT: Masked generative image transformer.  In _CVPR_ , 2022.
  * Chang et al. [2023] Huiwen Chang, Han Zhang, Jarred Barber, AJ Maschinot, José Lezama, Lu Jiang, Ming-Hsuan Yang, Kevin Murphy, William T Freeman, Michael Rubinstein, et al.  Muse: Text-to-image generation via masked generative transformers.  In _ICML_ , 2023.
  * Chen et al. [2023] Junsong Chen, Jincheng Yu, Chongjian Ge, Lewei Yao, Enze Xie, Yue Wu, Zhongdao Wang, James Kwok, Ping Luo, Huchuan Lu, et al.  Pixart-$\backslash alpha$: Fast training of diffusion transformer for photorealistic text-to-image synthesis.  _arXiv preprint arXiv:2310.00426_ , 2023.
  * Chen et al. [2022] Ting Chen, Ruixiang Zhang, and Geoffrey Hinton.  Analog bits: Generating discrete data using diffusion models with self-conditioning.  _arXiv preprint arXiv:2208.04202_ , 2022.
  * Dehghani et al. [2023] Mostafa Dehghani, Josip Djolonga, Basil Mustafa, Piotr Padlewski, Jonathan Heek, Justin Gilmer, Andreas Peter Steiner, Mathilde Caron, Robert Geirhos, Ibrahim Alabdulmohsin, et al.  Scaling vision transformers to 22 billion parameters.  In _International Conference on Machine Learning_ , pages 7480–7512. PMLR, 2023.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _CVPR_ , 2009.
  * Dhariwal and Nichol [2021] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat GANs on image synthesis.  In _NeurIPS_ , 2021.
  * Ding et al. [2021] 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.  In _NeurIPS_ , 2021.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _ICLR_ , 2020.
  * Dumoulin et al. [2016] Vincent Dumoulin, Jonathon Shlens, and Manjunath Kudlur.  A learned representation for artistic style.  _arXiv preprint arXiv:1610.07629_ , 2016.
  * Esser et al. [2021] Patrick Esser, Robin Rombach, and Bjorn Ommer.  Taming transformers for high-resolution image synthesis.  In _CVPR_ , 2021.
  * Gafni et al. [2022] 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 _European Conference on Computer Vision_ , pages 89–106. Springer, 2022.
  * Gao et al. [2023] Shanghua Gao, Pan Zhou, Ming-Ming Cheng, and Shuicheng Yan.  Masked diffusion transformer is a strong image synthesizer.  _arXiv:2303.14389_ , 2023.
  * Ge et al. [2022] Songwei Ge, Thomas Hayes, Harry Yang, Xi Yin, Guan Pang, David Jacobs, Jia-Bin Huang, and Devi Parikh.  Long video generation with time-agnostic VQGAN and time-sensitive transformer.  In _ECCV_ , 2022.
  * Ge et al. [2023] Songwei Ge, Seungjun Nah, Guilin Liu, Tyler Poon, Andrew Tao, Bryan Catanzaro, David Jacobs, Jia-Bin Huang, Ming-Yu Liu, and Yogesh Balaji.  Preserve your own correlation: A noise prior for video diffusion models.  _arXiv preprint arXiv:2305.10474_ , 2023.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  _Advances in neural information processing systems_ , 27, 2014.
  * Google [2023] Google.  PaLM 2 technical report.  _arXiv:2305.10403_ , 2023.
  * Gupta et al. [2022] Agrim Gupta, Stephen Tian, Yunzhi Zhang, Jiajun Wu, Roberto Martín-Martín, and Li Fei-Fei.  MaskViT: Masked visual pre-training for video prediction.  In _ICLR_ , 2022.
  * Gupta et al. [2023] Agrim Gupta, Jiajun Wu, Jia Deng, and Li Fei-Fei.  Siamese masked autoencoders.  _arXiv preprint arXiv:2305.14344_ , 2023.
  * Harvey et al. [2022] William Harvey, Saeid Naderiparizi, Vaden Masrani, Christian Weilbach, and Frank Wood.  Flexible diffusion modeling of long videos.  _Advances in Neural Information Processing Systems_ , 35:27953–27965, 2022.
  * He et al. [2022] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.  Masked autoencoders are scalable vision learners.  In _CVPR_ , 2022.
  * He et al. [2023] Yingqing He, Tianyu Yang, Yong Zhang, Ying Shan, and Qifeng Chen.  Latent video diffusion models for high-fidelity long video generation.  _arXiv preprint arXiv:2211.13221_ , 2023.
  * Heusel et al. [2017] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  GANs trained by a two time-scale update rule converge to a local nash equilibrium.  In _NeurIPS_ , 2017.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  In _NeurIPS_ , 2020.
  * Ho et al. [2022a] Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al.  Imagen video: High definition video generation with diffusion models.  _arXiv:2210.02303_ , 2022a.
  * Ho et al. [2022b] Jonathan Ho, Chitwan Saharia, William Chan, David J Fleet, Mohammad Norouzi, and Tim Salimans.  Cascaded diffusion models for high fidelity image generation.  _JMLR_ , 23(1):2249–2281, 2022b.
  * Ho et al. [2022c] Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J Fleet.  Video diffusion models.  In _ICLR Workshops_ , 2022c.
  * Hong et al. [2022] Wenyi Hong, Ming Ding, Wendi Zheng, Xinghan Liu, and Jie Tang.  CogVideo: Large-scale pretraining for text-to-video generation via transformers.  _arXiv:2205.15868_ , 2022.
  * Hoogeboom et al. [2023] Emiel Hoogeboom, Jonathan Heek, and Tim Salimans.  simple diffusion: End-to-end diffusion for high resolution images.  In _ICML_ , 2023.
  * Hooker [2021] Sara Hooker.  The hardware lottery.  _Communications of the ACM_ , 64(12):58–65, 2021\.
  * Hu et al. [2021] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  Lora: Low-rank adaptation of large language models.  In _ICLR_ , 2021.
  * Jabri et al. [2023] Allan Jabri, David J Fleet, and Ting Chen.  Scalable adaptive computation for iterative generation.  In _ICML_ , 2023.
  * Jiang et al. [2021] Yifan Jiang, Shiyu Chang, and Zhangyang Wang.  Transgan: Two pure transformers can make one strong gan, and that can scale up.  _Advances in Neural Information Processing Systems_ , 34:14745–14758, 2021.
  * Johnson et al. [2016] Justin Johnson, Alexandre Alahi, and Li Fei-Fei.  Perceptual losses for real-time style transfer and super-resolution.  In _ECCV_ , 2016.
  * Karras et al. [2019] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In _CVPR_ , 2019.
  * Kingma and Gao [2023] Diederik P Kingma and Ruiqi Gao.  Understanding the diffusion objective as a weighted integral of elbos.  _arXiv:2303.00848_ , 2023.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lee et al. [2021] Kwonjoon Lee, Huiwen Chang, Lu Jiang, Han Zhang, Zhuowen Tu, and Ce Liu.  Vitgan: Training gans with vision transformers.  _arXiv preprint arXiv:2107.04589_ , 2021.
  * Lin et al. [2023] Shanchuan Lin, Bingchen Liu, Jiashi Li, and Xiao Yang.  Common diffusion noise schedules and sample steps are flawed.  _arXiv preprint arXiv:2305.08891_ , 2023.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 10012–10022, 2021.
  * Lu et al. [2023] Haoyu Lu, Guoxing Yang, Nanyi Fei, Yuqi Huo, Zhiwu Lu, Ping Luo, and Mingyu Ding.  Vdt: General-purpose video diffusion transformers via mask modeling.  _arXiv preprint arXiv:2305.13311_ , 2023.
  * Luc et al. [2020] Pauline Luc, Aidan Clark, Sander Dieleman, Diego de Las Casas, Yotam Doron, Albin Cassirer, and Karen Simonyan.  Transformation-based adversarial video prediction on large-scale data.  _arXiv:2003.04035_ , 2020.
  * Nichol and Dhariwal [2021] Alexander Quinn Nichol and Prafulla Dhariwal.  Improved denoising diffusion probabilistic models.  In _International Conference on Machine Learning_ , pages 8162–8171. PMLR, 2021.
  * Peebles and Xie [2022] William Peebles and Saining Xie.  Scalable diffusion models with transformers.  _arXiv:2212.09748_ , 2022.
  * Perez et al. [2018] Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville.  Film: Visual reasoning with a general conditioning layer.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training.  2018\.
  * Radford et al. [2019] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9, 2019.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _ICML_ , 2021.
  * Radford et al. [2023] Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever.  Robust speech recognition via large-scale weak supervision.  In _International Conference on Machine Learning_ , pages 28492–28518. PMLR, 2023.
  * Ramesh et al. [2021] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  In _ICML_ , 2021.
  * Roberts et al. [2019] Adam Roberts, Colin Raffel, Katherine Lee, Michael Matena, Noam Shazeer, Peter J Liu, Sharan Narang, Wei Li, and Yanqi Zhou.  Exploring the limits of transfer learning with a unified text-to-text transformer.  2019\.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _CVPR_ , 2022.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-Net: Convolutional networks for biomedical image segmentation.  In _MICCAI_ , 2015.
  * Salimans and Ho [2022] Tim Salimans and Jonathan Ho.  Progressive distillation for fast sampling of diffusion models.  _arXiv preprint arXiv:2202.00512_ , 2022.
  * Salimans et al. [2016] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen.  Improved techniques for training GANs.  In _NeurIPS_ , 2016.
  * Savinov et al. [2021] Nikolay Savinov, Junyoung Chung, Mikolaj Binkowski, Erich Elsen, and Aaron van den Oord.  Step-unrolled denoising autoencoders for text generation.  _arXiv preprint arXiv:2112.06749_ , 2021.
  * Singer et al. [2022] Uriel Singer, Adam Polyak, Thomas Hayes, Xi Yin, Jie An, Songyang Zhang, Qiyuan Hu, Harry Yang, Oron Ashual, Oran Gafni, et al.  Make-a-video: Text-to-video generation without text-video data.  _arXiv:2209.14792_ , 2022.
  * Sohl-Dickstein et al. [2015] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In _ICML_ , 2015.
  * Song et al. [2020] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  _arXiv preprint arXiv:2010.02502_ , 2020.
  * Song and Ermon [2019] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  In _NeurIPS_ , 2019.
  * Soomro et al. [2012] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  UCF101: A dataset of 101 human actions classes from videos in the wild.  _arXiv:1212.0402_ , 2012.
  * Unterthiner et al. [2018] Thomas Unterthiner, Sjoerd van Steenkiste, Karol Kurach, Raphael Marinier, Marcin Michalski, and Sylvain Gelly.  Towards accurate generative models of video: A new metric & challenges.  _arXiv:1812.01717_ , 2018.
  * Van Den Oord et al. [2017] Aaron Van Den Oord, Oriol Vinyals, et al.  Neural discrete representation learning.  In _NeurIPS_ , 2017.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _NeurIPS_ , 2017.
  * Villegas et al. [2022] Ruben Villegas, Mohammad Babaeizadeh, Pieter-Jan Kindermans, Hernan Moraldo, Han Zhang, Mohammad Taghi Saffar, Santiago Castro, Julius Kunze, and Dumitru Erhan.  Phenaki: Variable length video generation from open domain textual description.  _arXiv:2210.02399_ , 2022.
  * Vincent et al. [2008] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol.  Extracting and composing robust features with denoising autoencoders.  In _Proceedings of the 25th international conference on Machine learning_ , pages 1096–1103, 2008.
  * Wu et al. [2021] Chenfei Wu, Lun Huang, Qianxi Zhang, Binyang Li, Lei Ji, Fan Yang, Guillermo Sapiro, and Nan Duan.  Godiva: Generating open-domain videos from natural descriptions.  _arXiv preprint arXiv:2104.14806_ , 2021.
  * Wu et al. [2022] Chenfei Wu, Jian Liang, Lei Ji, Fan Yang, Yuejian Fang, Daxin Jiang, and Nan Duan.  Nüwa: Visual synthesis pre-training for neural visual world creation.  In _European conference on computer vision_ , pages 720–736. Springer, 2022.
  * Yan et al. [2021] Wilson Yan, Yunzhi Zhang, Pieter Abbeel, and Aravind Srinivas.  VideoGPT: Video generation using VQ-VAE and transformers.  _arXiv:2104.10157_ , 2021.
  * Yu et al. [2022a] Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu.  Vector-quantized image modeling with improved VQGAN.  In _ICLR_ , 2022a.
  * Yu et al. [2022b] 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:2206.10789_ , 2022b.
  * Yu et al. [2023a] Lijun Yu, Yong Cheng, Kihyuk Sohn, José Lezama, Han Zhang, Huiwen Chang, Alexander G Hauptmann, Ming-Hsuan Yang, Yuan Hao, Irfan Essa, et al.  MAGVIT: Masked generative video transformer.  In _CVPR_ , 2023a.
  * Yu et al. [2023b] Lijun Yu, José Lezama, Nitesh B Gundavarapu, Luca Versari, Kihyuk Sohn, David Minnen, Yong Cheng, Agrim Gupta, Xiuye Gu, Alexander G Hauptmann, et al.  Language model beats diffusion–tokenizer is key to visual generation.  _arXiv preprint arXiv:2310.05737_ , 2023b.
  * Yu et al. [2023c] Sihyun Yu, Kihyuk Sohn, Subin Kim, and Jinwoo Shin.  Video probabilistic diffusion models in projected latent space.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 18456–18466, 2023c.
  * Zhai et al. [2022] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer.  Scaling vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12104–12113, 2022.
  * Zhang et al. [2022] Bowen Zhang, Shuyang Gu, Bo Zhang, Jianmin Bao, Dong Chen, Fang Wen, Yong Wang, and Baining Guo.  Styleswin: Transformer-based gan for high-resolution image generation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 11304–11314, 2022.
  * Zhang et al. [2018] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _CVPR_ , 2018.
  * Zheng et al. [2023] Hongkai Zheng, Weili Nie, Arash Vahdat, and Anima Anandkumar.  Fast training of diffusion models with masked transformers.  _arXiv:2306.09305_ , 2023.
  * Zhou et al. [2022] Daquan Zhou, Weimin Wang, Hanshu Yan, Weiwei Lv, Yizhe Zhu, and Jiashi Feng.  Magicvideo: Efficient video generation with latent diffusion models.  _arXiv preprint arXiv:2211.11018_ , 2022.
  * Zitkovich et al. [2023] Brianna Zitkovich, Tianhe Yu, Sichun Xu, Peng Xu, Ted Xiao, Fei Xia, Jialin Wu, Paul Wohlhart, Stefan Welker, Ayzaan Wahid, et al.  RT-2: Vision-language-action models transfer web knowledge to robotic control.  In _CoRL_ , 2023.

| T2V (base)
---|---
Input | $5\times 16\times 28$
Spatial window | $1\times 16\times 28$
Spatiotermporal window | $5\times 8\times 14$
Training steps | 250000
Batch size | 512
lr schedule | Constant
Optimizer | Adafactor
lr | 0.00005

Table 6: Hyperparameters for aspect-ratio finetuning.

##  Appendix A Implementation Details

For the first stage, we follow the architecture and hyperparameters from Yu et
al. [82]. We report hyperparameters specific for training our model in Table
8. To train the second stage transformer model, we use the default settings of
$1\times 16\times 16$ spatial window, $5\times 8\times 8$ spatiotemporal
window, $p_{\text{sc}}=0.9$, $c=8$ and $r=2$. We summarize additional training
and inference hyperparameters for all tasks in Table 8. The UCF-101 model
results reported in Tables 1 and 4 are trained for $60,000$ steps. We perform
all ablations on UCF-101 with $35,000$ training steps.

Aspect-ratio finetuning. To simplify training and leverage broad data sources
with different aspect ratios, we train the base stage using a square aspect
ratio. We fine-tune the base the stage on a subset of data to generate videos
with a $9:16$ aspect ratio. We interpolate the absolute and relative position
embeddings and scale the window sizes. We summarize the finetuning
hyperparameters in Table 6.

Long video generation. As described in § 4.4, we train our model jointly on
the task of frame prediction. During inference, we generate videos as follows:
Given a natural language description of a video, we first generate the initial
$17$ frames using our base model. Next, we encode the last $5$ frames into $2$
latent frames using our causal 3D encoder. Providing $2$ latent frames as
input for subsequent autoregressive generation helps ensure that our model can
maintain continuity of motion and produce temporally consistent videos.

UCF-101 Text-to-Video. We follow the evaluation protocol of prior work [24],
and adapt their prompts to better describe the UCF-101 classes.

##  Appendix B Additional Results

###  B.1 Image Generation

We compare (Table 7) W.A.L.T with state-of-the-art image generation methods
for $256\times 256$ resolution with classifier free guidance. Unlike, prior
work [53, 22, 87] using Transformer for diffusion modelling, we did not
observe significant benefit of using vanilla classifier free guidance. Hence,
we report results using the power cosine schedule proposed by Gao et al. [22].
Our model performs better than prior works on the Inception Score metric, and
achieves competitive FID scores. Fig. 5 shows qualitative samples.

Method | Cost (Iter$\times$BS) | FID$\downarrow$ | IS$\uparrow$ | Params. | Steps
---|---|---|---|---|---
LDM-4 [61] | 178k$\times$1200 | 3.60 | 247.7 | 400M | 250
DiT-XL/2 [53] | 7000k$\times$256 | 2.27 | 278.2 | 675M | 250
ADM [16] | - | 3.94 | 215.8 | 608M | 2000
MDT [22] | 6500k$\times$256 | 1.79 | 283.0 | 676M | 250
MaskDiT [87] | 1200k$\times$1024 | 2.28 | 276.6 | 736M | 40
simple diffusion [38] | 500K$\times$2048 | 2.44 | 256.3 | 2B | 512
VDM++ [45] | - | 2.12 | 267.7 | 2B | 512
W.A.L.T-L _Ours_ | 437k$\times$1024 | 2.40 | 290.5 | 460M | 50

Table 7: Class-conditional image generation on ImageNet 256$\times$256. We
adopt the evaluation protocol and implementation of ADM [16] and report
results with classifier free guidance.

| ImageNet | UCF-101 | K600 | T2V (base) | T2V (2$\times$) | T2V (2$\times$2$\times$)
---|---|---|---|---|---|---
First Stage |  |  |  |  |  |
Input | $1\times 256\times 256$ | $17\times 128\times 128$ | $17\times 128\times 128$ | $17\times 128\times 128$ | $17\times 256\times 448$ | $17\times 512\times 896$
$f_{s},f_{t}$ | 8, - | 8, 4 | 8, 4 | 8, 4 | 8, 4 | 8, 4
Channels | 128 | 128 | 128 | 128 | 128 | 128
Channel multiplier | 1,1,2,4 | 1, 2, 2, 4 | 1, 2, 2, 4 | 1, 2, 2, 4 | 1, 2, 2, 4 | 1, 2, 2, 4
Training duration | 270 epochs | 2000 epochs | 270000 steps | 1000000 steps | 1000000 steps | 1000000 steps
Batch size | 256 | 256 | 256 | 256 | 256 | 256
lr schedule | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine
Optimizer | Adam | Adam | Adam | Adam | Adam | Adam
Second Stage |  |  |  |  |  |
Input | $1\times 32\times 32$ | $5\times 16\times 16$ | $5\times 16\times 16$ | $5\times 16\times 16$ | $5\times 32\times 56$ | $5\times 64\times 112$
Layers | 24 | 28 | 24 | 52 | 40 | 24
Hidden size | 1024 | 1152 | 1024 | 9216 | 1408 | 1024
Heads | 16 | 16 | 16 | 16 | 16 | 16
Training duration | 350 epochs | 60000 steps | 360 epochs | 550000 steps | 675000 steps | 275000 steps
Batch size | 1024 | 256 | 512 | 512 | 512 | 512
lr schedule | Cosine | Cosine | Cosine | Cosine | Cosine | Cosine
Optimizer | AdamW | AdamW | AdamW | Adafactor | Adafactor | Adafactor
lr | 0.0005 | 0.0005 | 0.0005 | 0.0002 | 0.0005 | 0.0005
EMA | $\checkmark$ | $\checkmark$ | $\checkmark$ | ✗ | ✗ | ✗
Patch size | 1 | 1 | 1 | 1 | 2 | 4
AdaLN-LoRA | ✗ | 2 | 2 | 2 | 2 | 2
Diffusion |  |  |  |  |  |
Diffusion Steps | 1000 | 1000 | 1000 | 1000 | 1000 | 1000
Noise schedule | Linear | Linear | Linear | Linear | Linear | Linear
$\beta_{0}$ | 0.0001 | 0.0001 | 0.0001 | 0.0001 | 0.0001 | 0.0001
$\beta_{1000}$ | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02
Sampler | DDIM | DDIM | DDIM | DDIM | DDIM | DDIM
Sampling steps | 50 | 50 | 50 | 50 | 50 | 50
Guidance | ✗ | ✗ | ✗ | $\checkmark$ | $\checkmark$ | $\checkmark$

Table 8: Training and evaluation hyperparameters.

###  B.2 Video Generation

We show samples for Kinetics-600 frame prediction in Fig. 6.

Figure 5: ImageNet class-conditional generation samples.

Figure 6: Frame prediction samples on Kinetics-600. Top: ground-truth, where
unobserved frames are shaded. Bottom: generation.

###  B.3 Image-to-Video

As noted in Section 4.4, we train our model jointly on the task of frame
prediction, where we condition on $1$ latent frame. This allows us to leverage
the high quality first frame from the image generator as context for
predicting subsequent frames. For qualitative results see videos on our
project website.


# Optimal Generation of Strictly
Increasing Binary Trees and Beyond

Olivier Bodini LIPN
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-Nord 0000-0002-1867-667X<EMAIL_ADDRESS>paris13.fr LIPN
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-NordLAGA
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-Nord Francis Durand LIPN
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-Nord 0009-0004-4146-0289 francis.durand@ens-paris-
saclay.fr LAGA
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-Nord Philippe Marchal LAGA
Villetaneuse, FranceInstitut Galilé
Université Sorbonne Paris-Nord 0000-0001-8236-5713<EMAIL_ADDRESS>paris13.fr

##  1 Introduction

Tree-like data structures are fundamental in computer science, serving as
critical tools for modeling phenomena, testing, and creating diverse and
representative datasets that enable effective training of machine learning
frameworks by exposing models to a wide range of possible input scenarios.
Recognizing the necessity for random samplers of these structures, a
comprehensive body of work has emerged offering algorithms for generating
simple tree families. These algorithms, ranging from general approaches like
the Recursive method and Boltzmann sampler [3] to specific ones like the BBJ
algorithm for binary trees [2], excel in efficiency and minimal randomness
usage. Despite the abundance of techniques for simple trees, the random
generation of increasing trees—a vital component in priority queue
management—remains underexplored. This gap is attributed to their non-uniform
internal structure, challenging the creation of homogeneous algorithms. Our
paper introduces a groundbreaking algorithm for the optimal generation of
strictly increasing binary trees, leveraging a novel approach pioneered by Ph.
Marchal [4] that ensures both entropy and time efficiency and we prove here
random bit complexity. Additionally, we present an enhanced algorithm that
adopts an innovative approximation schema for the recursive method. This
method is tailored for all weighted unary-binary increasing trees,
guaranteeing minimal randomness consumption. This dual approach not only
advances the field of random increasing tree generation but also sets a new
standard for algorithmic efficiency and randomness optimization. The next
section is devoted to presenting the first algorithm and evaluating its cost.
Section 3 addresses the second algorithm, which represents an improvement of
the recursive method through the use of a Monte Carlo process. The final
section demonstrates how the second method can be adapted to operate within a
more general framework.

##  2 An Ad Hoc Approach for Sampling Strictly Increasing Trees

Before introducing the first algorithm, let us make a first easy but important
observation. Strictly increasing binary trees are intimately related to
permutations (this has been known for a long time). Given a sequence of
distinct real numbers in the interval [0,1], we can derive a permutation based
on the relative order of the sequence, and thus an increasing tree in the
following way. Starting with the position of the smallest number in the
sequence, we place a 1 at this position in the permutation (and at the same
time, we create a root for the tree), and continue this process until all the
numbers have been placed (in the permutation and in the binary tree). If the
sequence alternates between increasing and decreasing values, the resulting
permutation will also alternate and the tree will be a strictly increasing
binary tree. Furthermore, suppose the sequence is chosen randomly and
uniformly. In that case, the permutation reflects a uniform distribution of
all possible permutations and the binary tree constructed is uniform among
binary trees of size $n$. This leads us to look for an algorithm that
generates a random, uniform, and alternating sequence, which in turn allows us
to construct a uniform alternating permutation and hence a uniform strictly
increasing binary tree.

Algorithm 1 Generate an Alternating Permutation of Size $n$

1:$n>1$

2:$D,Y\leftarrow\text{arrays of size }n$

3:$p\leftarrow\lfloor\log_{2}(n)\rfloor+1$

4:while precision on $Y$ is not sufficient do

5: $p\leftarrow p+1$

6: while $Y$ is empty do

7: $r\leftarrow U_{0}\text{with }p\text{ digits.}$

8: $D[0]\leftarrow 1-\sin^{2}\left(\frac{\pi}{2}r\right)$

9: for $i\leftarrow 0$ to $n-2$ do

10: $r\leftarrow U_{i+1}\text{with }p\text{ digits.}$

11: $D[i+1]=r^{2}(1-D[i])$

12: $\alpha\leftarrow\sqrt{\frac{1-D[n-1]}{1-D[0]}}$

13: $threshold\leftarrow\frac{1}{\alpha+\alpha^{-1}}$

14: $proba\leftarrow\text{rand()}$

15: if $proba\leq threshold$ then

16: $Y\leftarrow(1-D[0],D[1],1-D[2],\ldots)$

17: else if $threshold<proba\leq 2\cdot threshold$ then

18: $Y\leftarrow(1-D[n-1],D[n-2],1-D[n-3],\ldots)$

19: else

20: restart

21: Sort $Y$ to determine if its elements are strictly ordered

22:return the alternating sequence associated with $Y$

This algorithm is essentially a rewritten version of Marchal’s algorithm,
modified to bypass inefficient trigonometric calculations. More precisely, by
making the following change of variable
$C_{n}=\sin^{2}\left(\frac{\pi}{2}X_{n}\right)$ where $X_{n}$ is the sequence
described in [4], we do not alter the properties of the sequence and we
significantly improve the computation. We refer the reader to the initial note
by Marchal [4] for the proof of his algorithm’s validity. A key point is that
the algorithm uses a rejection procedure but it is proved in [4] that the
rejection probability is bounded above by $1-\frac{2}{3\pi}$ (which is
independent of $n$).

The remaining issue concerns the random-bit complexity. Naturally, for each
uniform i.i.d. random variable $U_{i}$, we aim to generate only enough digits
to ensure sufficient precision, thus avoiding any order ambiguity in the final
sequence.

As a preliminary, the number of strictly increasing binary trees of size $n$
is asymptotically equivalent to $2\left(\frac{2}{\pi}\right)^{n+1}n!$. Thus,
the entropy is $n\log_{2}(n)+\frac{2n}{\pi}+o(n)$. As we draw $n$ uniform
variables, we need at least $\log_{2}(n)$ bits of precision to be coherent
with the entropy.

Now, note that $D[n]$ converges when $n$ goes to the infinity to the
distribution

$Q:=\sum_{n=0}^{\infty}(-1)^{n}\prod_{i=0}^{n}U_{i}^{2}$

Indeed, we can derive from the algorithm the following induction:
$Q=U^{2}(1-V^{2}Q)$ where $U$ and $V$ are i.i.d. uniform distributions on
$[0,1]$. Consequently, the density function $d(z)$ of $Q$ follows the
functional equation:

$d(z)=\int_{z}^{1}\frac{1}{2\sqrt{t}}\cdot\frac{d(1-z/t)}{t}\,dt.$

To our knowledge, solving this equation is not straightforward. For that, let
us start from the density of the random variable $Q_{0}=U^{2}(1-V^{2})$, which
is:

$d(z):=\frac{\arctan\left(\frac{\sqrt{1-z}}{\sqrt{z}}\right)}{2\sqrt{z}},$

from which we can observe that the iteration $Q_{n+1}=U^{2}(1-V^{2}Q_{n})$
generates random variables whose density is alternatively a polynomial in
$A:=\arctan\left(\frac{\sqrt{1-z}}{\sqrt{z}}\right)$ and in
$\bar{A}:=\arctan\left(\frac{\sqrt{z}}{\sqrt{1-z}}\right)$, divided by
$\sqrt{z}$. Moreover, the polynomials follow a quite simple recurrence which
alternates

$P_{n+1}(\bar{A})=\int_{\bar{A}}^{\frac{\pi}{2}}P_{n}(A)\,dA$

and

$P_{n+1}(A)=\int_{0}^{A}P_{n}(\bar{A})\,d\bar{A}.$

So, the limiting polynomial follows the functional equation

$\int_{0}^{x}\left(\int_{x}^{\frac{\pi}{2}}P(t)\,dt\right)dx=P(x),$

from which we derive that the limiting distribution admits two solutions
depending on the parity on $n$: $\frac{2\sqrt{1-z}}{\pi\sqrt{z}}$ and
$\frac{2\sqrt{z}}{\pi\sqrt{1-z}}$. Therefore, we can conclude that the density
of the limiting random variable is

$ds(z)=\frac{\left(\frac{\sqrt{1-z}}{\sqrt{z}}\right)+\left(\frac{\sqrt{z}}{\sqrt{1-z}}\right)}{\pi}.$

In order to evaluate the required precision, let us assume that all the $D[i]$
are independent and identically distributed and follow the symmetrized
distribution $Q$ of density $ds(z)$ This statement is not strictly true;
however, it is asymptotically acceptable. This acceptability arises because
the dependency between $D[i]$ and $D[j]$ decreases exponentially fast as the
distance $|j-i|$ increases. This property follows directly from

$Q:=\sum_{n=0}^{\infty}(-1)^{n}\prod_{i=0}^{n}U_{i}^{2}$

and is really important because it implies that the errors do not accumulate.

Let $\delta$ denote the number of digits of precision (in base 2). Then, the
probability $P_{n,\delta}$ that there is no ambiguity in a calculation of the
alternating sequence of size $n$ with $\delta$ digits of precision is given
by:

$P_{n,\delta}:=n![z^{n}]\prod_{i=1}^{2^{\delta}-1}\left(1+z\frac{ds\left(\frac{i}{2^{\delta}}\right)}{\sum_{i=1}^{2^{\delta}-1}ds\left(\frac{i}{2^{\delta}}\right)}\right),$

Now, putting $N:=2^{\delta}$ and
$p_{i,n}:=\frac{ds\left(\frac{i}{N}\right)}{\sum_{i=1}^{N-1}ds\left(\frac{i}{N}\right)}$,
when $n$ is large, $\sum_{i=1}^{N-1}ds\left(\frac{i}{N}\right)/N$ tends to
$1$, and $\sum_{i=1}^{N-1}p_{i,n}^{2}$ is asymptotically equivalent to
$\frac{1}{n}\int_{1/n}^{1-1/n}ds(x)dx$, which simplifies to
$\sum_{i=1}^{N-1}p_{i,n}^{2}\sim\frac{2\ln(n)}{\pi^{2}n}$. Consequently,
$P_{n,\delta}$ is asymptotically equivalent to
$1-\frac{N(N-1)}{2}\frac{2\ln(n)}{\pi^{2}n}$. Indeed, the extraction $[z^{n}]$
is nothing more than the $PSet_{n}$ of the $B(\boldsymbol{p})=\sum p_{i,n}$
where the $p_{i,n}$ are seen as $n-1$ different atoms and it is well known
that $PSet_{n}$ can be expressed as a multivariate polynomial in the
$B(\boldsymbol{p}^{i})$. Moreover the two dominant contributions are
$\frac{B(\boldsymbol{p})^{n}}{n!}-\frac{B(\boldsymbol{p}^{2})B(\boldsymbol{p})^{n-2}}{2(n-2)!}$.
Finally, to achieve a probability of rejection $\varepsilon$, we require
$\delta=2\log_{2}(n)+\log_{2}(\ln(n))+\kappa+\log_{2}{\varepsilon}$. Thus, the
required precision is proportional (factor 2) to the entropy. It is worth
noting that improving the precision by one unit halves the risk of ambiguity.

This algorithm is highly efficient, but it cannot be extended to other types
of increasing trees. The following section introduces a more flexible
approach.

##  3 Toward an Efficient Recursive Methods Without Preliminary Calculations

We aim at generating a random strictly increasing binary tree with an exact
size of $n$. The generating function for our combinatorial family satisfies
the non-linear differential equation $T^{\prime}(z)=T^{2}(z)+1$ and let us
denote by $t_{n}$ the number of trees of size $n$. Utilizing the symbolic
method for combinatorial structures, we derive a recursive method algorithm
for our purpose. Our approach is now to avoid the exact and costly computation
of $t_{n}$ by a well-controlled approximation process, which paves the way for
a systematic and efficient algorithm to generate these structures, as shown in
Algorithm 2.

Algorithm 2 Generating $T$ of Size $n$ with the recursive method

1:If $n=1$ : Return the tree with one leaf labeled $1$

2:_Intelligently_ generate $M\in\\{0,1,..,n-1\\}$ the size of the left son of
$T$. Note that $P(M=m)$ has to be proportional to
$\binom{n-1}{m}t_{m}t_{n-1-m}$.

3:Generate recursively $T^{\prime}$ and $T^{\prime\prime}$ of size $m$ and
$n-1-m$ and return $T$ with $T^{\prime}$ as a left son and $T^{\prime\prime}$
as a right son with the indexes ”shuffled” among the $n-1$ remaining atoms.

There are a few problems with this generation scheme: How do we compute the
$t_{n}$’s? The classical way to do so is to pre-compute all of them but doing
so requires at least $\Omega(n^{2})$ in space and even more in time.
Generating $M$ can also be an issue, the classical way to generate $M$ would
require computing all the $t_{n}$’s and inverting the probability function
which can be ineffective.

We describe a way to compute only the necessary bits of precision of $t_{n}$
and a way to generate $M$ without the exact knowledge of $t_{n}$, solving the
two issues.

##  4 Generating $M$, the size of the left son

###  4.1 Having a direct expression for $t_{n}$

The differential equation $T^{\prime}(z)=T^{2}(z)+1$ can be integrated in
$T(z)=\tan(z)$ because $T(0)=0$ (there is no strictly increasing binary tree
of size $0$).

We can hence use the tangent development: $\tan(z)=\sum_{k\geq
1}\frac{4^{k}(4^{k}-1)|B_{2k}|}{(2k)!}z^{2k-1}$ with
$|B_{2k}|=\frac{2(2k)!\zeta(2k)}{(2\pi)^{2k}}$ being the absolute value of the
Bernoulli numbers, and $\zeta$ being the Riemann’s zeta function. So we can
extract the number of strictly increasing binary trees of size $n$. If $n$ is
even, $t_{n}=0$ because $\tan$ is odd, and for $n=2k-1$,
$t_{2k-1}=(2k-1)!\frac{2(4^{k}-1)\zeta(2k)}{\pi^{2k}}$.

In the following, we assume that $n=2l-1$ is odd since there is nothing to
generate if $n$ is even.

Since $P(M=m)$ is proportional to $\binom{n-1}{m}t_{m}t_{n-m-1}$, so
$P(M=m)=0$ when $m$ is even. So we can write, for $m=2k-1$, that $P(M=m)$ is
proportional to
$\binom{2l}{2k-1}\frac{(2k-1)!2(4^{k}-1)4^{k}\zeta(2k)}{(2\pi)^{2k}}\frac{(2(l-k)-1)!(4^{l-k}-1)4^{l-k}\zeta(2(l-k))}{(2\pi)^{2(l-k)}}$.
We can simplify this expression and get rid of the constant terms, we get that
$P(M=2k-1)$ is proportional to
$f_{k}:=(4^{k}-1)\zeta(2k)(4^{l-k}-1)\zeta(2(l-k))$, with
$k\in\\{1,2,..,l-1\\}$.

Since $\zeta(2k)=\sum_{i\geq 1}\frac{1}{i^{2k}}$, by truncating the sum,
$\zeta(2k)\geq 1+\frac{1}{4^{k}}$. This leads to the following bound on
$f_{k}$:
$f_{k}\geq(4^{k}-1)(1+\frac{1}{4^{k}})(4^{n-k}-1)(1+\frac{1}{4^{n-k}})$, i.e.
$f_{k}\geq(4^{k}-\frac{1}{4^{k}})(4^{n-k}-\frac{1}{4^{n-k}})$. With this lower
bound and the fact that $(f_{k})$ are symmetric decreasing from $1$ to
$\lfloor\frac{l}{2}\rfloor$, we can bound $f_{k}$.

######  Lemma 1.

For $k\in\\{1,2,..,l-1\\}$, $f_{1}\geq f_{k}\geq
f_{\lfloor\frac{l}{2}\rfloor}$ and
$\frac{f_{1}}{f_{\lfloor\frac{l}{2}\rfloor}}\leq\frac{4\pi^{4}}{45}\leq 9$

This lemma implies a Monte-Carlo method for sampling $M$.

Algorithm 3 Generate $M$ such that $P(M=2k-1)$ is proportional to $f_{k}$

1:Generate $X\in\\{1,2,..,l-1\\}$.

2:Test $Uf_{1}\leq f_{X}$ where $U$ is a uniform random number in $[0,1]$, if
true return $M=X$, else generate another $X$ and start again.

Lemma 1 implies that Algorithm 3 has a constant reject.

######  Lemma 2.

Algorithm 3 has a running time of $O(\log(n))$

This lemma is not only due to the fact that the reject is constant but also to
the fact that it is possible to compute only the first bits of $f_{1}$,
$f_{k}$, and $U$ and check whether we can conclude that $Uf_{1}\leq f_{X}$ or
$Uf_{1}>f_{X}$. If we cannot conclude, we can add the next bits and recheck
until we can accept or reject $X$ as $M$.

It is possible to compute only the first bits of
$f_{k}=(4^{k}-1)\zeta(2k)(4^{l-k}-1)\zeta(2(l-k))$ because we can truncate
$\zeta(2k)=\sum_{i\geq 1}\frac{1}{i^{2k}}$ to a finite order.

With this method of generating $M$, we can state the complexity of Algorithm
2.

######  Theorem 1.

Algorithm 2 has a running time of $O(n\log(n))$, which is optimal.

The algorithm is optimal because of the Shannon entropic principle: It is not
possible to generate a strictly increasing binary tree of size $n$ ($n$ odd)
with less than $\log_{2}(t_{n})$ random bits, so the best sampling algorithm
will run in at least $\log_{2}(t_{n})=\Omega(n\log(n))$

##  5 Adapting the Algorithm for Different Families of Binary-Increasing Trees

###  5.1 Binary Trees

Consider various families of increasing binary trees, each characterized by
distinct generating functions; for instance, non-plane binary trees have
$T^{\prime}(z)=\frac{T^{2}(z)}{2}+1$, leading to
$T(z)=\frac{\tan(z/\sqrt{2})}{\sqrt{2}}$. For all families of binary-
increasing trees with generating functions of the form $T^{\prime}=aT^{2}+c$
as described in Algorithm 2, the algorithm remains applicable. This is due to
the consistent structure shared by these trees, characterized by having one
more leaf than internal nodes.

###  5.2 Binary-Unary Trees

For a family with generating function
$T^{\prime}(z)=a(T(z)+\alpha)^{2}+a\gamma^{2}$, where $a,c>0$ and $b\geq 0$,
we focus on those written as $T^{\prime}(z)=a(T(z)+\alpha)^{2}+a\gamma^{2}$,
the case $T^{\prime}(z)=a(T(z)+\alpha)^{2}-a\gamma^{2}$ being similar. The
algorithm generates trees of size $n$ with
$t_{n}\sim\frac{n!a^{n}\gamma^{n+1}}{(\frac{\pi}{2}-\tan^{-1}(\frac{\alpha}{\gamma}))^{n+1}}$,
allowing effective recursive generation. And

$t_{n}=n!a^{n}\gamma^{n+1}\left(\sum_{k\geq
0}\frac{(-1)^{n+1}}{(\tan^{-1}(\frac{\alpha}{\gamma})-\pi(k+\frac{1}{2}))^{n+1}}+\frac{(-1)^{n+1}}{(\tan^{-1}(\frac{\alpha}{\gamma})+\pi(k+\frac{1}{2}))^{n+1}}\right)$

is still computable by truncating its expression.

Algorithm 4 Generating $T$ of Size $n$ for Binary-Unary Trees

1:If $n=1$ : Return the tree with one leaf colored in one of the $c$ colors.

2:For $n>1$ : The tree can have a unary root with probability
$\frac{bt_{n-1}}{t_{n}}$ or a binary root.

3:Let $X$ be a Bernoulli variable with parameter $\frac{bt_{n-1}}{t_{n}}$; if
$X=1$, call the algorithm recursively with parameter $n-1$ and return the tree
consisting of a unary root and labeled $1$ with $T^{\prime}$ as its only son.

4:Generate $M\in\\{0,1,..,n-1\\}$ with $P(M=m)$ proportional to
$\binom{n-1}{m}t_{m}t_{n-1-m}$.

5:Generate recursively $T^{\prime}$ and $T^{\prime\prime}$ of size $m$ and
$n-1-m$ and return $T$ with $T^{\prime}$ as a left son and $T^{\prime\prime}$
as a right son with the indexes ”shuffled” among the $n-1$ remaining axioms.

## References

  * [1]
  * [2] Axel Bacher, Olivier Bodini & Alice Jacquot (2017): _Efficient random sampling of binary and unary-binary trees via holonomic equations_.  Theor. Comput. Sci. 695, pp. 42–53, 10.1016/J.TCS.2017.07.009.
  * [3] Philippe Duchon, Philippe Flajolet, Guy Louchard & Gilles Schaeffer (2004): _Boltzmann Samplers for the Random Generation of Combinatorial Structures_.  Combinatorics, Probability and Computing 13(4–5), p. 577–625, 10.1017/S0963548304006315.
  * [4] Ph. Marchal (2012): _Generating random alternating permutations in time $n\log n$_.  Available at https://www.math.univ-paris13.fr/~marchal/altperm1.pdf.  Unpublished note.