# Unifying Generative Models with GFlowNets

Dinghuai Zhang  Ricky T. Q. Chen  Nikolay Malkin  Yoshua Bengio

###### Abstract

There are many frameworks for deep generative modeling, each often presented
with their own specific training algorithms and inference methods. We present
a short note on the connections between existing deep generative models and
the GFlowNet framework (Bengio et al., 2021b), shedding light on their
overlapping traits and providing a unifying viewpoint through the lens of
learning with Markovian trajectories. This provides a means for unifying
training and inference algorithms, and provides a route to construct an
agglomeration of generative models.

Machine Learning, ICML

##  1 Preliminaries about GFlowNets

From a probabilistic modeling viewpoint, generative flow network (GFlowNet)
(Bengio et al., 2021a) is one kind of generative models that aims to sample
$\mathbf{x}$ in proportion to a given reward function $R(\mathbf{x})$.
Recently, the community has experienced a progressive expansion of the concept
of GFlowNets (Malkin et al., 2022; Zhang et al., 2022; Deleu et al., 2022;
Jain et al., 2022). Concretely, a GFlowNet would sample a Markovian trajectory
$\tau=(s_{0},s_{1},\ldots,s_{n})$ with length $n$. If not specially specified,
we use the notation $\mathbf{x}=s_{n}$ for the final state of the trajectory.
This process has a natural connection to reinforcement learning (Sutton &
Barto, 2005). All the states $s$ construct a directed acyclic graph (DAG) in
the latent state space. Each trajectory starts from the same (abstract)
initial state $s_{0}$ and runs to a different end point $s_{n}$. The flow
function $F(\tau)\in\mathbb{R}_{+}$ defined in Bengio et al. (2021b) can be
understood by an analogy of water amount in a water flow. Ideally, we want the
amount of flow leading to $\mathbf{x}$ equals the given reward:
$\sum_{\tau=(s_{0},\cdots,\mathbf{x})}F(\tau)=R(\mathbf{x})$.

GFlowNet has several training criterion. We start from the flow matching
condition (Eq. 1). Define $F(s,s^{\prime})\triangleq\sum_{(s\to
s^{\prime})\in\tau}F(\tau)$ as the edge flow function and
$F(s)\triangleq\sum_{s\in\tau}F(\tau)$ as the state flow function. It’s easy
to see that

$\displaystyle\sum_{s}F(s,s^{\prime})=\sum_{s^{\prime\prime}}F(s^{\prime},s^{\prime\prime}),$
(1)

as both side of the term equals $F(s^{\prime})$. If one parametrizes the
GFlowNet with the edge flow function $F_{\theta}(\cdot,\cdot)$, then Eq. 1
would be used as training loss (_i.e._ ,
$L(\theta,s^{\prime})=\left(\sum_{s}F_{\theta}(s,s^{\prime})-\sum_{s^{\prime\prime}}F_{\theta}(s^{\prime},s^{\prime\prime})\right)^{2}$).

The detailed balance condition of GFlowNet writes

$\displaystyle F(s)P_{F}\left(s^{\prime}\mid
s\right)=F(s^{\prime})P_{B}\left(s\mid s^{\prime}\right),$ (2)

where $P_{F}(s^{\prime}|s)$ and $P_{B}(s|s^{\prime})$ are referred to as the
forward and backward policy for the transition between different states. We
can separately parametrize three models for
$F_{\theta}(\cdot),P_{F}(\cdot|\cdot;\theta),P_{B}(\cdot|\cdot;\theta)$. The
detailed balance condition is closely related to the flow matching condition,
in the sense that $P_{F}(s^{\prime}|s)={F(s,s^{\prime})}/{F(s)}$ and
$P_{B}(s|s^{\prime})=F(s,s^{\prime})/F(s^{\prime})$. It suffices to determine
a GFlowNet by determining its forward policy in theory.

What’s more, the general trajectory balance condition of GFlowNet (Malkin et
al., 2022) wants to match GFlowNet’s forward trajectory $P_{F}(\tau)$ and the
backward trajectory $P_{B}(\tau)$, where

$\displaystyle P_{F}(\tau)$
$\displaystyle=\prod_{t=0}^{n-1}P_{F}\left(s_{t+1}|s_{t}\right)$ (3)
$\displaystyle P_{B}(\tau)$
$\displaystyle=\frac{R\left(\mathbf{x}\right)}{Z}\prod_{t=0}^{n-1}P_{B}\left(s_{t}|s_{t+1}\right).$
(4)

Here $Z=\sum_{\mathbf{x}}R(\mathbf{x})$ is the normalizing factor. We also
write $P_{B}(\tau|\mathbf{x})=\prod_{t=0}^{n-1}P_{B}\left(s_{t}\mid
s_{t+1}\right)$.

##  2 Hierarchical Variational Autoencoders

The evidence lower bound for bottom-up hierarchical VAEs (HVAEs) (Ranganath et
al., 2016) reads

$\displaystyle\log p(\mathbf{x})\geq\textrm{ELBO}(p,q)$ (5)
$\displaystyle\triangleq\mathbb{E}_{q(\mathbf{z}_{1:L}|\mathbf{x})}\left[\log
p(\mathbf{x},\mathbf{z}_{1:L})-\log q(\mathbf{z}_{1:L}|\mathbf{x})\right]$ (6)
$\displaystyle=\mathop{\mathbb{E}}_{q(\mathbf{z}_{L}|z_{L+1})\cdots
q(\mathbf{z}_{1}|\mathbf{z}_{2})}\left[\log
p(\mathbf{z}_{1})+\sum_{i=1}^{L}\log\frac{p(\mathbf{z}_{i+1}|\mathbf{z}_{i})}{q(\mathbf{z}_{i}|\mathbf{z}_{i+1})}\right],$
(7)

where we denote $\mathbf{x}:=\mathbf{z}_{L+1}$. It is well known that this
hierarchical ELBO can also be represented as
$\mathcal{D}_{\mathrm{KL}}\left(q(\mathbf{z}_{1:L}|\mathbf{x})\|p(\mathbf{z}_{1:L}|\mathbf{x})\right),$
where $p(\mathbf{z}_{1:L}|\mathbf{x})\propto
p(\mathbf{x}|\mathbf{z}_{1:L})p(\mathbf{z}_{1:L})$ and
$\mathbb{D}_{\mathrm{KL}}$ denotes the KL divergence. In GFlowNets, we also
aim to match the forward trajectory policy which ends with data $\mathbf{x}$
with the corresponding backward trajectory policy, _i.e._ ,
$P_{F}(\tau)\approx P_{B}(\tau)$, conditioning on the event
$\\{\mathbf{x}\in\tau\\}$, _i.e._ , $\mathbf{x}$ is the last state of $\tau$.
Note that we have $P(\mathbf{x}|\tau)=\mathbbm{1}\\{\mathbf{x}\in\tau\\}$. A
slight difference between HVAEs and GFlowNets is that $\mathbf{z}_{1:L}$, the
latent variables of the hierarchical VAE, does not include $\mathbf{x}$.

######  Observation 1.

HVAE is a special kind of GFlowNets in the following sense: each trajectory is
in the form of
$\tau=(\mathbf{z}_{1},\mathbf{z}_{2},\cdots,\mathbf{z}_{L},\mathbf{z}_{L+1}=\mathbf{x})$.
The decoder of VAE, which samples
$\mathbf{z}_{1}\to\cdots\to\mathbf{z}_{L}\to\mathbf{z}_{L+1}$, corresponds to
the forward policy; the encoder samples
$\mathbf{x}\to\mathbf{z}_{L}\to\cdots\to\mathbf{z}_{1}$, and corresponds to
the backward policy.

With $\mathbf{x}=\mathbf{z}_{L+1}$, we could then write

$\displaystyle
P_{F}(\tau)=p(\mathbf{z}_{1})\prod_{i=1}^{L}p(\mathbf{z}_{i+1}|\mathbf{z}_{i}),$
(8) $\displaystyle
P_{B}(\tau)=p_{d}(\mathbf{x})\prod_{i=1}^{L}q(\mathbf{z}_{i}|\mathbf{z}_{i+1}),$
(9)

where $p_{d}(\mathbf{x})=\frac{R(\mathbf{x})}{Z}$ is the true target density.
We can see the $i$-th state in a GFlowNet trajectory $s_{i}$ corresponds to
$\mathbf{z}_{i}$. A subtle difference is that in Bengio et al. (2021b) we
additionally have an abstract initial state $s_{0}$ which has no concrete
meaning for some simplicity reasons. We ignore this difference here.

The following proposition reveals an equivalence between the two perspectives
in Observation 1.

######  Proposition 2.

Training hierarchical latent variable models with the KL-trajectory balance
$\mathcal{D}_{\mathrm{KL}}\left(P_{B}(\tau)\|P_{F}(\tau)\right)$ is equivalent
to training HVAEs by maximizing its ELBO.

We remark that there is also top-down modeling for hierarchical VAE (Sønderby
et al., 2016; Child, 2021), where the inference model takes the factorization
form of
$q(\mathbf{z}_{1}|\mathbf{x})\prod_{i=1}^{L-1}q(\mathbf{z}_{i+1}|\mathbf{z}_{i})$.
However, we do not discuss it here as it does not have much connection to
GFlowNets, although it has more application power in practice.

##  3 Diffusion Models & SDEs

Behavior of deep latent variable model in its infinite depth regime is studied
by Tzen & Raginsky (2019). In short, if the encoder and decoder take the
following form

$\displaystyle p(\mathbf{z}_{i+1}|\mathbf{z}_{i})$
$\displaystyle=\mathcal{N}\left(\mathbf{z}_{i+1};\mathbf{z}_{i}+h\mathbf{f}_{i}(\mathbf{z}_{i}),hg^{2}_{i})\right),$
(10) $\displaystyle q(\mathbf{z}_{i}|\mathbf{z}_{i+1})$
$\displaystyle=\mathcal{N}(\mathbf{z}_{i};\mathbf{z}_{i+1}+h\large(-\mathbf{f}_{i+1}(\mathbf{z}_{i+1})$
(11) $\displaystyle\quad+g^{2}_{i+1}\nabla\log
p_{i+1}(\mathbf{z}_{i+1})\large),hg^{2}_{i+1}),$ (12)

where we assume all $\mathbf{z}_{i}$ have the same number of dimensionality as
$\mathbf{x}$ and $h=1/L$, then the hierarchical model is equivalent to a
stochastic process in its diffusion limit ( $h\to 0$). Huang et al. (2021);
Kingma et al. (2021); Song et al. (2021) also study connections between
hierarchical variational inference on latent variable models and diffusion.

Consider a stochastic differential equation (SDE) (Øksendal, 1985) and its
reverse time SDE (Anderson, 1982)

$\displaystyle\mathop{}\\!\mathrm{d}\mathbf{x}$
$\displaystyle=\mathbf{f}(\mathbf{x})\mathop{}\\!\mathrm{d}t+g(t)\mathop{}\\!\mathrm{d}\mathbf{w}_{t},$
(13) $\displaystyle\mathop{}\\!\mathrm{d}\bar{\mathbf{x}}$
$\displaystyle=\left[\mathbf{f}(\bar{\mathbf{x}})-g^{2}(t)\nabla_{\bar{\mathbf{x}}}\log
p_{t}(\bar{\mathbf{x}})\right]\mathop{}\\!\mathrm{d}\bar{t}+g(t)\mathop{}\\!\mathrm{d}\bar{\mathbf{w}}_{t},$
(14)

where $\mathbf{f}(\cdot)$ and $g(\cdot)$ are given and
$\mathbf{x},\mathbf{w}\in\mathbb{R}^{D}$, and
$\bar{\mathbf{x}},\bar{t},\bar{\mathbf{w}}_{t}$ denote the reverse time
version of $\mathbf{x},t,\mathbf{w}_{t}$. We define
$\mathbb{P}_{h}(\mathbf{x}_{t+h}|\mathbf{x}_{t})$ to be the transition kernel
induced by the SDE in Eq. 13:
$\mathbf{x}_{t+h}=\mathbf{x}_{t}+\int_{t}^{t+h}f(\mathbf{x}_{\tau})\mathop{}\\!\mathrm{d}\tau+\int_{t}^{t+h}g(\tau)\mathop{}\\!\mathrm{d}\mathbf{w}_{\tau}$,
where $h$ denotes an infinite small time step. We then make the following
observation.

######  Observation 3.

SDE is a special case of GFlowNets, in the sense that GFlowNet states take the
time-augmented form $s=(\mathbf{x}_{t},t)$ for some $t$, the SDE models the
forward policy of GFlowNets (_i.e._ , how states should move forward) while
the reverse time SDE models the backward policy of GFlowNets (_i.e._ , how
states should move backward). In this case, a trajectory is in the form of
$\\{\mathbf{x}_{t}\\}_{t=0}^{1}$.

Note that we cannot directly treat any $\mathbf{x}_{t}$ to be GFlowNet state,
because theory of GFlowNets requires the graph of all latent states is a DAG
(_i.e._ , cannot possess circles). This state augmenting operation also
induces that in SDE case, the latent state graph of GFlowNets could not be
arbitrary DAG, since any $(\mathbf{x},t)\to(\mathbf{x}^{\prime},t^{\prime})$
with $t\geq t^{\prime}$ is forbidden. Without loss of generality, we assume
$\mathbf{x}_{t}$ state already contain time stamp in itself in the following
context111This is equivalent to define
$\tilde{\mathbf{x}}_{t}=(\mathbf{x}_{t},t)$ and conduct discussion with
$\tilde{\mathbf{x}}_{t}$ instead..

We next point out an analogy between stochastic processes property and
GFlowNet property:

######  Observation 4.

Such property of stochastic process

$\displaystyle\int
p(\mathbf{x}_{t-h},t-h)\mathbb{P}_{h}(\mathbf{x}_{t}|\mathbf{x}_{t-h})\mathop{}\\!\mathrm{d}\mathbf{x}_{t-h}$
(15) $\displaystyle\quad=\int
p(\mathbf{x}_{t},t)\mathbb{P}_{h}(\mathbf{x}_{t+h}|\mathbf{x}_{t})\mathop{}\\!\mathrm{d}\mathbf{x}_{t+h}=p(\mathbf{x}_{t},t),$

could be interpreted as GFlowNets flow matching condition:

$\displaystyle\sum_{s}F(s,s^{\prime})=\sum_{s{{}^{\prime\prime}}}F(s^{\prime},s{{}^{\prime\prime}})\triangleq
F(s^{\prime}),$ (16)

for any $s^{\prime}$, where we also have
$F(s,s^{\prime})=F(s)P_{F}(s^{\prime}|s)$.

We point out that Eq. LABEL:eq:diffusion_markov is a standard starting point
for deriving the Fokker-Planck equation:

######  Proposition 5 (Øksendal (1985)).

Taking the limit as $h\rightarrow 0$, Eq. LABEL:eq:diffusion_markov implies

$\begin{split}\partial_{t}p(\mathbf{x},t)=&-\nabla_{\mathbf{x}}\left(p(\mathbf{x},t)\mathbf{f}(\mathbf{x},t)\right)\\\
&+\frac{1}{2}\nabla_{\mathbf{x}}^{2}\left(p(\mathbf{x},t)g^{2}(\mathbf{x},t)\right).\end{split}$
(17)

Equivalence between detailed balance and score matching. At the end of this
section, we investigate such a setting where we want to model our own reverse
process:

$\displaystyle\mathop{}\\!\mathrm{d}\mathbf{x}$
$\displaystyle=\left[\mathbf{f}(\mathbf{x})-g^{2}(t)\mathbf{s}(\mathbf{x},t)\right]\mathop{}\\!\mathrm{d}\bar{t}+g(t)\mathop{}\\!\mathrm{d}\bar{\mathbf{w}}_{t},$
(18)

where
$\mathbf{s}(\cdot,\cdot):\mathbb{R}^{D}\times\mathbb{R}\to\mathbb{R}^{D}$ is a
neural network, and $\mathbf{f}(\cdot)$ and $g(\cdot)$ are
given222$\mathbf{f}(\mathbf{x}),\mathbf{s}(\mathbf{x})$ could also be written
as $\mathbf{f}(\mathbf{x}_{t},t),\mathbf{s}(\mathbf{x}_{t},t)$ in a more
strict/general way.. We propose to use the detailed balance criterion of
GFlowNet to learn this neural network. From the above discussion, we can see
there is an analogy about $F(s_{t})\approx p_{t}(\mathbf{x})$. We show the
validity of such strategy in the following proposition.

######  Proposition 6.

GFlowNets’ detailed balance condition

$\displaystyle\begin{split}&\lim_{h\rightarrow 0}\frac{1}{\sqrt{h}}\huge(\log
p_{t}(\mathbf{x}_{t})+\log P_{F}(\mathbf{x}_{t+h}|\mathbf{x}_{t})-\\\
&\quad\log p_{t+h}(\mathbf{x}_{t+h})+\log
P_{B}(\mathbf{x}_{t}|\mathbf{x}_{t+h})\huge)=0,\end{split}$ (19)

$(\forall\mathbf{x}_{t}\in\mathbb{R}^{D},\forall t\in(0,1))$ is equivalent to

$\displaystyle{\boldsymbol{\epsilon}}^{\top}\left(\mathbf{s}(\mathbf{x}_{t},t)-\nabla_{\mathbf{x}}\log
p_{t}(\mathbf{x})\right)=0,\forall{\boldsymbol{\epsilon}},\mathbf{x}_{t}\in\mathbb{R}^{D},\forall
t\in[0,1],$

which is the optimal solution to score matching:

$\displaystyle\min_{\mathbf{s}}\mathbb{E}_{\mathbf{x}\sim
p_{t}}\mathbb{E}_{\boldsymbol{\epsilon}}\left[{\boldsymbol{\epsilon}}^{\top}\nabla_{\mathbf{x}}\mathbf{s}(\mathbf{x}){\boldsymbol{\epsilon}}+\frac{1}{2}\left({\boldsymbol{\epsilon}}^{\top}\mathbf{s}(\mathbf{x},t)\right)^{2}\right],\forall
t.$

##  4 Exact Likelihood Models

Autoregressive (AR) models sample $p(\mathbf{x}_{1:i+1}|\mathbf{x}_{1:i})$
sequentially for every dimension $i$ to generate a vector data $\mathbf{x}$.
In Zhang et al. (2022), the authors use an AR-like (with a learnable ordering)
model to parametrize the GFlowNet. Indeed, if we define every (forward) action
of GFlowNets is to add one pixel to the current state, and the backward policy
is to turn one pixel into so-called “void" state, then AR models could be seen
as GFlowNets. As a formal example, we analyze AR models with natural ordering.

######  Observation 7.

Autoregressive model is a special kind of GFlowNets when

  * •

$s_{t}:=\mathbf{x}_{1:t}$ is the GFlowNet state;

  * •

$P_{F}(s_{t+1}|s_{t})=p(\mathbf{x}_{1:i+1}|\mathbf{x}_{1:i})$ is the forward
policy;

  * •

$P_{B}(s_{t}|s_{t+1})=\delta\\{s_{t}\ \textrm{is the first}\ t\text{
dimensions of}\ s_{t+1}\\}$,

where $\delta\\{\cdot\\}$ is the Dirac Delta distribution for continuous
variables, and is the indicator function for discrete cases.

This modeling makes the latent graph of the GFlowNet to be a tree;
alternatively, if we allow learnable ordering as in Zhang et al. (2022), the
latent space is a general DAG. This is related to non-autoregressive modeling
methods in NLP community (Gu et al., 2018).

Normalizing flow (Dinh et al., 2015) (NF) is another way to sequentially
construct desired data. It first samples $\mathbf{z}_{1}$ from a base
distribution (usually the standard Gaussian), and then doing a series of
invertible transformations $\mathbf{z}_{i+1}=\mathbf{f}(\mathbf{z}_{i})$ until
we finally get $\mathbf{x}:=\mathbf{z}_{L+1}$, where $L$ denotes the number of
transformation layers.

######  Observation 8.

NF is a special kind of GFlowNets where deterministic forward and backward
policies (except the first transition step), and $s_{t}=\mathbf{z}_{t}$ are
GFlowNet states.

In this scenario, NF is a GFlowNet whose forward policy is to sample from the
base distribution at the first step (hence a stochastic step), and conduct
deterministic invertible transformations afterwards. We next discuss maximum
likelihood estimation (MLE) of such models.

About MLE training. AR models and NFs are usually trained with MLE. Albeit the
likelihood of general GFlowNets is intractable, we can estimate its lower
bound:

$\displaystyle\log p_{T}(\mathbf{x})$
$\displaystyle=\int_{\mathbf{x}\in\tau}P_{F}(\tau)\mathop{}\\!\mathrm{d}\tau$
(20)
$\displaystyle=\log\mathbb{E}_{P_{B}(\tau|\mathbf{x})}\left[\frac{P_{F}(\tau)}{P_{B}(\tau|\mathbf{x})}\right]$
(21)
$\displaystyle\geq\mathbb{E}_{P_{B}(\tau|\mathbf{x})}\left[\log\frac{P_{F}(\tau)}{P_{B}(\tau|\mathbf{x})}\right]$
(22)
$\displaystyle=-\mathcal{D}_{\mathrm{KL}}\left(P_{B}(\tau|\mathbf{x})\|P_{F}(\tau)\right),$
(23)

which could be again seen as one kind of trajectory balance as in Proposition
2. An IWAE-type bound (Burda et al., 2016) is also applicable. If the backward
policy is a fixed one (_i.e._ , deterministic and without learnable
parameters), we can directly use $\log P_{B}(\tau|\mathbf{x})-\log
P_{F}(\tau)$ as a sample based tractable training loss for
$\mathbf{x}\in\mathcal{D}$, with $\tau\sim P_{B}(\tau|\mathbf{x})$.
Furthermore, if we use AR natural ordering, then $P_{B}(\tau|\mathbf{x})$ only
contains one trajectory, therefore $\log P_{B}(\tau|\mathbf{x})-\log
P_{F}(\tau)$ is the same thing as the MLE loss of AR models. On the other
hand, if the backward policy is learnable, one may need REINFORCE (Williams,
2004) or reparametrization trick (Kingma & Welling, 2014) to optimize with
regard to $P_{B}$, making it a variational distribution over trajectories.

We summarize that both AR models and NFs are GFlowNets with tree-structured
latent state graphs, making every terminating state could only be reached by
one trajectory.

##  5 Learning a Reward Function from Data

Energy-based model (EBM) can be used as the (negative log) reward function for
GFlowNets training. We could use any GFlowNet modeling including those
discussed in previous sections, and jointly train it together with an EBM. For
instance, in the EB-GFN algorithm (Zhang et al., 2022) a GFlowNet is used to
amortize the computational MCMC process of the EBM contrastive divergence
training. The two models (EBM and GFlowNet) are trained alternately.

Generative adversarial network (GAN) is closely related to EBM (Che et al.,
2020), while its algorithm is more computationally efficient. However, though
it may look reasonable at first glance, we cannot directly use the
discriminator $D(\mathbf{x})$ as the reward for GFlowNets training. If so, at
the end of a perfect training, we would get an optimal discriminator
$D^{*}(\mathbf{x})=\frac{p_{d}(\mathbf{x})}{p_{d}(\mathbf{x})+p_{g}(\mathbf{x})}$
and optimal GFlowNet generator distribution $p_{g}(\mathbf{x})\propto
D^{*}(\mathbf{x})$. This cannot induce $p_{g}(\mathbf{x})=p_{d}(\mathbf{x})$.
In fact, if $p_{g}(\mathbf{x})=p_{d}(\mathbf{x})$, we will have
$D^{*}(\mathbf{x})\equiv 1/2$ and
$p_{g}(\mathbf{x})=p_{d}(\mathbf{x})\equiv\text{constant}$, which is
impossible for general data with unbounded support. To fill this gap, we
instead design the following algorithm that makes much more sense.

######  Proposition 9.

An alternate algorithm which trains the discriminator to distinguish between
generated data and true data, and trains the GFlowNet with negative energy as

$\log\frac{D(\mathbf{x})}{1-D(\mathbf{x})}+\log p_{g}(\mathbf{x})$ (24)

would result in a valid generative model.

Nonetheless, we unfortunately do not have access to the value of
$p_{g}(\mathbf{x})$ if the generator is a general GFlowNet, which makes this
algorithm an intractable one.

##  6 Conclusion

We have interpreted existing generative models as GFlowNets with different
policies over sample trajectories. This provides some insight into the
overlaps between existing generative modeling frameworks, and their connection
to general-purpose algorithms for training them. Furthermore, this unification
implies a method of constructing an agglomeration of varying types of
generative modeling approaches, where GFlowNet acts as a general-purpose glue
for tractable inference and training.

## References

  * Anderson (1982) Anderson, B. D. O.  Reverse-time diffusion equation models.  _Stochastic Processes and their Applications_ , 12:313–326, 1982.
  * Bengio et al. (2021a) Bengio, E., Jain, M., Korablyov, M., Precup, D., and Bengio, Y.  Flow network based generative models for non-iterative diverse candidate generation.  _Neural Information Processing Systems (NeurIPS)_ , 2021a.
  * Bengio et al. (2021b) Bengio, Y., Deleu, T., Hu, E. J., Lahlou, S., Tiwari, M., and Bengio, E.  GFlowNet foundations.  _arXiv preprint 2111.09266_ , 2021b.
  * Burda et al. (2016) Burda, Y., Grosse, R. B., and Salakhutdinov, R.  Importance weighted autoencoders.  _arXiv preprint 1509.00519_ , 2016.
  * Che et al. (2020) Che, T., Zhang, R., Sohl-Dickstein, J., Larochelle, H., Paull, L., Cao, Y., and Bengio, Y.  Your gan is secretly an energy-based model and you should use discriminator driven latent sampling.  _Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Child (2021) Child, R.  Very deep vaes generalize autoregressive models and can outperform them on images.  _International Conference on Learning Representations (ICLR)_ , 2021\.
  * Deleu et al. (2022) Deleu, T., G’ois, A., Emezue, C. C., Rankawat, M., Lacoste-Julien, S., Bauer, S., and Bengio, Y.  Bayesian structure learning with generative flow networks.  _Uncertainty in Artificial Intelligence (UAI)_ , 2022.
  * Dinh et al. (2015) Dinh, L., Krueger, D., and Bengio, Y.  Nice: Non-linear independent components estimation.  _arXiv preprint 1410.8516_ , 2015.
  * Gu et al. (2018) Gu, J., Bradbury, J., Xiong, C., Li, V. O. K., and Socher, R.  Non-autoregressive neural machine translation.  _International Conference on Learning Representations (ICLR)_ , 2018\.
  * Huang et al. (2021) Huang, C.-W., Lim, J. H., and Courville, A. C.  A variational perspective on diffusion-based generative models and score matching.  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Jain et al. (2022) Jain, M., Bengio, E., García, A., Rector-Brooks, J., Dossou, B. F. P., Ekbote, C. A., Fu, J., Zhang, T., Kilgour, M., Zhang, D., Simine, L., Das, P., and Bengio, Y.  Biological sequence design with GFlowNets, 2022.
  * Kingma & Welling (2014) Kingma, D. P. and Welling, M.  Auto-encoding variational bayes.  _International Conference on Learning Representations (ICLR)_ , 2014\.
  * Kingma et al. (2021) Kingma, D. P., Salimans, T., Poole, B., and Ho, J.  Variational diffusion models.  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Malkin et al. (2022) Malkin, N., Jain, M., Bengio, E., Sun, C., and Bengio, Y.  Trajectory balance: Improved credit assignment in GFlowNets.  _arXiv preprint 2201.13259_ , 2022.
  * Øksendal (1985) Øksendal, B.  Stochastic differential equations.  _The Mathematical Gazette_ , 77:65–84, 1985.
  * Ranganath et al. (2016) Ranganath, R., Tran, D., and Blei, D. M.  Hierarchical variational models.  _International Conference on Machine Learning (ICML)_ , 2016.
  * Sønderby et al. (2016) Sønderby, C. K., Raiko, T., Maaløe, L., Sønderby, S. K., and Winther, O.  Ladder variational autoencoders.  _Neural Information Processing Systems (NIPS)_ , 2016.
  * Song et al. (2019) Song, Y., Garg, S., Shi, J., and Ermon, S.  Sliced score matching: A scalable approach to density and score estimation.  _Uncertainty in Artificial Intelligence (UAI)_ , 2019.
  * Song et al. (2021) Song, Y., Durkan, C., Murray, I., and Ermon, S.  Maximum likelihood training of score-based diffusion models.  _Neural Information Processing Systems (NeurIPS)_ , 2021.
  * Sutton & Barto (2005) Sutton, R. S. and Barto, A. G.  Reinforcement learning: An introduction.  _IEEE Transactions on Neural Networks_ , 16:285–286, 2005\.
  * Tzen & Raginsky (2019) Tzen, B. and Raginsky, M.  Neural stochastic differential equations: Deep latent gaussian models in the diffusion limit.  _arXiv preprint 1905.09883_ , 2019.
  * Williams (2004) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8:229–256, 2004.
  * Zhang et al. (2022) Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A. C., and Bengio, Y.  Generative flow networks for discrete probabilistic modeling.  _International Conference on Machine Learning (ICML)_ , 2022.

##  Appendix A Proofs

###  A.1 Proposition 2

###### Proof.

We have

$\displaystyle\mathcal{D}_{\mathrm{KL}}\left(P_{B}(\tau)\|P_{F}(\tau)\right)$
$\displaystyle=\mathbb{E}_{p_{d}(\mathbf{x})q(\mathbf{z}_{1:L}|\mathbf{x})}\left[\log\frac{p_{d}(\mathbf{x})q(\mathbf{z}_{1:L}|\mathbf{x})}{p(\mathbf{z}_{1:L})p(\mathbf{x}|\mathbf{z}_{1:L})}\right]$
$\displaystyle=-\mathbb{E}_{p_{d}(\mathbf{x})}\mathbb{E}_{q(\mathbf{z}_{1:L}|\mathbf{x})}\left[\log\frac{p(\mathbf{x},\mathbf{z}_{1:L})}{q(\mathbf{z}_{1:L}|\mathbf{x})}\right]+\mathbb{E}_{p_{d}(\mathbf{x})}\left[\log
p_{d}(\mathbf{x})\right]$
$\displaystyle=-\mathbb{E}_{p_{d}(\mathbf{x})}\left[\textrm{ELBO}(p,q)\right]-\mathcal{H}[p_{d}(\cdot)].$

Here $\mathcal{H}[p_{d}(\cdot)]$ denotes the entropy of the target
distribution, which is a constant w.r.t. GFlowNet parameters. ∎

###  A.2 Proposition 5

###### Proof.

First notice

$\displaystyle\partial_{t}p(\mathbf{x},t)\triangleq\lim_{h\to
0}\frac{1}{h}\left(p(\mathbf{x},t+h)-p(\mathbf{x},t)\right)=\lim_{h\to
0}\frac{1}{h}\left(\int
p(\mathbf{x}^{\prime},t)\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime}-p(\mathbf{x},t)\right).$

Then for any function $w(\mathbf{x})$, we have

$\displaystyle\quad\int
w(\mathbf{x})\partial_{t}p(\mathbf{x},t)\mathop{}\\!\mathrm{d}\mathbf{x}$
$\displaystyle=\int w(\mathbf{x})\lim_{h\to 0}\frac{1}{h}\left(\int
p(\mathbf{x}^{\prime},t)\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime}-p(\mathbf{x},t)\right)\mathop{}\\!\mathrm{d}\mathbf{x}$
$\displaystyle=\lim_{h\to 0}\frac{1}{h}\Large(\int w(\mathbf{x})\int
p(\mathbf{x}^{\prime},t)\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime}\mathop{}\\!\mathrm{d}\mathbf{x}-\int
w(\mathbf{x}^{\prime})p(\mathbf{x}^{\prime},t)\int\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})\mathop{}\\!\mathrm{d}\mathbf{x}\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime}\Large)$
$\displaystyle=\lim_{h\to 0}\frac{1}{h}\int
p(\mathbf{x}^{\prime},t)\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})\left(w(\mathbf{x})-w(\mathbf{x}^{\prime})\right)\mathop{}\\!\mathrm{d}\mathbf{x}\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime}$
$\displaystyle\triangleq\int
p(\mathbf{x}^{\prime},t)\sum_{n=1}w^{(n)}(\mathbf{x}^{\prime})D_{n}(\mathbf{x}^{\prime})\mathbf{x}^{\prime}$
$\displaystyle=\int
w(\mathbf{x}^{\prime})\sum_{n=1}\left(-\frac{\partial}{\partial\mathbf{x}^{\prime}}\right)^{n}\left(p(\mathbf{x}^{\prime},t)D_{n}(\mathbf{x}^{\prime})\right)\mathop{}\\!\mathrm{d}\mathbf{x}^{\prime},$

where $D_{n}(\mathbf{x}^{\prime})=\lim_{h\to
0}\frac{1}{hn!}\int\mathbb{P}_{h}(\mathbf{x}|\mathbf{x}^{\prime})(\mathbf{x}-\mathbf{x}^{\prime})^{n}\mathop{}\\!\mathrm{d}\mathbf{x}$
and the last step uses integral by parts. This tells us

$\displaystyle\partial_{t}p(\mathbf{x},t)=\sum_{n=1}\left(-\frac{\partial}{\partial\mathbf{x}}\right)^{n}\left(p(\mathbf{x},t)D_{n}(\mathbf{x})\right)=-\nabla_{\mathbf{x}}\left(p(\mathbf{x},t)\mathbf{f}(\mathbf{x},t)\right)+\frac{1}{2}\nabla_{\mathbf{x}}^{2}\left(p(\mathbf{x},t)g^{2}(\mathbf{x},t)\right),$

which is essentially the Fokker-Planck equation.

∎

###  A.3 Proposition 6

From the above SDEs, we know that the forward and backward policy is

$\displaystyle\mathbf{x}_{t+h}$
$\displaystyle=\mathbf{x}_{t}+\mathbf{f}(\mathbf{x}_{t})h+\sqrt{h}g(t)\cdot{\boldsymbol{\delta}}_{F},$
$\displaystyle\mathbf{x}_{t}$
$\displaystyle=\mathbf{x}_{t+h}+\left[g^{2}(t+h)\mathbf{s}(\mathbf{x}_{t+h})-\mathbf{f}(\mathbf{x}_{t+h})\right]h+\sqrt{h}g(t+h){\boldsymbol{\delta}}_{B},$

where
${\boldsymbol{\delta}}_{F},{\boldsymbol{\delta}}_{B}\sim\mathcal{N}(0,\mathbf{I}_{D})$.
Since we know $h\to 0$, the left and right side of Eq. 19 become

$\displaystyle\log P_{F}(\mathbf{x}_{t+h}|\mathbf{x}_{t})-\log
P_{B}(\mathbf{x}_{t}|\mathbf{x}_{t+h})$ $\displaystyle=-\frac{D}{2}\log(2\pi
g^{2}_{t}h)-\frac{1}{2g_{t}^{2}h}\|\Delta\mathbf{x}-h\mathbf{f}_{t}\|^{2}$
$\displaystyle+\frac{D}{2}\log(2\pi
g^{2}_{t+h}h)+\frac{1}{2g_{t+h}^{2}h}\|\Delta\mathbf{x}-h\mathbf{f}_{t+h}+hg^{2}_{t+h}\mathbf{s}(\mathbf{x}_{t+h})\|^{2},$
$\displaystyle\log p_{t+h}(\mathbf{x}_{t+h})-\log p_{t}(\mathbf{x}_{t})$
$\displaystyle=\Delta\mathbf{x}^{\top}\nabla_{\mathbf{x}}\log
p_{t}(\mathbf{x})+O(h),$

where
$g_{t}=g(t),\mathbf{f}_{t}=\mathbf{f}(\mathbf{x}_{t}),\Delta\mathbf{x}=\mathbf{x}_{t+h}-\mathbf{x}_{t}=\sqrt{h}g_{t}{\boldsymbol{\epsilon}},{\boldsymbol{\epsilon}}\sim\mathcal{N}(0,\mathbf{I}_{D})$.
Therefore,

$\displaystyle\lim_{h\to 0}\frac{1}{\sqrt{h}g_{t}}(\log$ $\displaystyle
p_{t+h}(\mathbf{x}_{t+h})x-\log
p_{t}(\mathbf{x}_{t}))={\boldsymbol{\epsilon}}^{\top}\nabla_{\mathbf{x}}\log
p_{t}(\mathbf{x}),$ $\displaystyle\lim_{h\to 0}\frac{1}{\sqrt{h}g_{t}}(\log$
$\displaystyle P_{F}(\mathbf{x}_{t+h}|\mathbf{x}_{t})-\log
P_{B}(\mathbf{x}_{t}|\mathbf{x}_{t+h}))$ $\displaystyle=\lim_{h\to
0}\frac{D}{\sqrt{h}g_{t}}(\log g_{t+h}-\log
g_{t})-\frac{1}{2g_{t}^{3}h^{3/2}}\left(hg_{t}^{2}\|{\boldsymbol{\epsilon}}\|^{2}+h^{2}\|\mathbf{f}_{t}\|^{2}-2h^{3/2}g_{t}{\boldsymbol{\epsilon}}^{\top}\mathbf{f}_{t}\right)$
$\displaystyle\phantom{aaaaaaaaaaaaa}+\frac{1}{2g_{t}g_{t+h}^{2}h^{3/2}}\left(hg_{t}^{2}\|{\boldsymbol{\epsilon}}\|^{2}-2h^{3/2}g_{t}{\boldsymbol{\epsilon}}^{\top}\mathbf{f}_{t+h}+2g_{t}g_{t+h}^{2}h^{3/2}{\boldsymbol{\epsilon}}^{\top}\mathbf{s}(\mathbf{x}_{t+h})\right)$
$\displaystyle=\lim_{h\to
0}{\boldsymbol{\epsilon}}^{\top}\left(\frac{\mathbf{f}_{t}}{g_{t}^{2}}-\frac{\mathbf{f}_{t+h}}{g_{t+h}^{2}}\right)+{\boldsymbol{\epsilon}}^{T}\mathbf{s}(\mathbf{x}_{t+h})={\boldsymbol{\epsilon}}^{T}\mathbf{s}(\mathbf{x}_{t}),$

with some smoothness assumptions on $g(t)$ and
$\mathbf{f}(\mathbf{x}_{t})/g(t)$. This tells us that in order to satisfy the
detailed balance criterion, we need to satisfy

$\displaystyle{\boldsymbol{\epsilon}}^{\top}\left(\mathbf{s}(\mathbf{x}_{t},t)-\nabla_{\mathbf{x}}\log
p_{t}(\mathbf{x})\right)=0,\forall{\boldsymbol{\epsilon}},\mathbf{x}_{t}\in\mathbb{R}^{D},\forall
t\in[0,1].$

Since ${\boldsymbol{\epsilon}}$ could take any value, this is equivalent that
the model $\mathbf{s}$ should match with score function
$\nabla_{\mathbf{x}}\log p(\mathbf{x})$. Also, note that this is exactly
sliced score matching (Song et al., 2019), which has a more practical
formulation

$\displaystyle\mathbb{E}_{\boldsymbol{\epsilon}}\mathbb{E}_{\mathbf{x}\sim
p}\left[{\boldsymbol{\epsilon}}^{\top}\nabla_{\mathbf{x}}\mathbf{s}(\mathbf{x}){\boldsymbol{\epsilon}}+\frac{1}{2}\left({\boldsymbol{\epsilon}}^{\top}\mathbf{s}(\mathbf{x})\right)^{2}\right].$

###  A.4 Proposition 9

When both models (the GFlowNet and the discriminator) are trained perfectly,
we have

$\displaystyle
D^{*}(\mathbf{x})=\frac{p_{d}(\mathbf{x})}{p_{d}(\mathbf{x})+p_{g}(\mathbf{x})},$

and thus

$\displaystyle
p_{g}(\mathbf{x})\propto\exp\left(\log\frac{D^{*}(\mathbf{x})}{1-D^{*}(\mathbf{x})}+\log
p_{g}(\mathbf{x})\right)=\exp\left(\log\frac{p_{d}(\mathbf{x})}{p_{g}(\mathbf{x})}+\log
p_{g}(\mathbf{x})\right)=p_{d}(\mathbf{x}).$

Hence it is a valid generative model algorithm.