Revisiting Non-Acyclic GFlowNets in Discrete Environments
Authors: Nikita Morozov
Ian Maksimov
Daniil Tiapkin
Sergey Samsonov
Venue: ICML 2025 poster (2025)
Keywords: generative flow networks
gflownets
non-acyclic gflownets
sampling
reinforcement learning
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods

Abstract: Generative Flow Networks (GFlowNets) are a family of generative models that learn to sample objects from a given probability distribution, potentially known up to a normalizing constant. Instead of working in the object space, GFlowNets proceed by sampling trajectories in an appropriately constructed directed acyclic graph environment, greatly relying on the acyclicity of the graph. In our paper, we revisit the theory that relaxes the acyclicity assumption and present a simpler theoretical framework for non-acyclic GFlowNets in discrete environments. Moreover, we provide various novel theoretical insights related to training with fixed backward policies, the nature of flow functions, and connections between entropy-regularized RL and non-acyclic GFlowNets, which naturally generalize the respective concepts and theoretical results from the acyclic setting. In addition, we experimentally re-examine the concept of loss stability in non-acyclic GFlowNet training, as well as validate our own theoretical findings.

Revisiting Non-Acyclic GFlowNets in Discrete Environments
Nikita Morozov
lan Maksimov
Daniil Tiapkin
Sergey Samsonov
Abstract
2025) and fine-tuning of large language models and dif- fusion models (Hu et al., 2023; Venkatraman et al., 2024; Uehara et al., 2024; Zhang et al., 2025; Lee et al., 2025). The detailed theoretical foundations of GFlowNets in dis- crete environments were developed in (Bengio et al., 2023). While the majority of GFlowNet literature considers the discrete setting, it is possible to apply the methodology of continuous GFlowNets (Lahlou et al., 2023) to sampling problems more general spaces.
Generative Flow Networks (GFlowNets) are a family of generative models that learn to sample objects from a given probability distribution, po- tentially known up to normalizing constant. In- stead of working in the object space, GelowNets proceed by sampling trajectories in an appro- priately constructed directed acyclic graph en- viromment, greatly relying on the acyclicity of the graph. In our paper, we revisit the theory that relaxes the acyclicity assumption and present simpler theoretical framework for non-acyclic GelowNets in discrete environments, Moreover, we provide various novel theoretical insights re- lated to training with fixed backward policies, the nature of flow functions, and connections be- tween entropy-regularic GelowNets, which naturally generalize the re- spective concepts and theoretical results from the acyclic setting. In addition, we experimentally re-examine the concept of loss stability in non- acyclic GFlowNet training, as well as validate our own theoretical findings.
The main idea behind the generation process in GelowNets lies in sampling trajectories in the appropriately constructed directed acyclic graph environment instead of working di- rectly in the object space. A standard intuition behind this process is sequence of actions applied in order to construct composite object from "blocks". One of the limitations of this setting is that it requires acyclicity. While this limitation can be naturally interpreted in, e.g., molecule generation setting, it can confine the practical design of GFlowNet envi- ronments, as well as restrict the applicability of GFlow in other scenarios. A motivational example for non-acyclic GFlowNets presented by (Brunswic al., 2024) is related to modeling distributions over objects with intrinsic sym- metries. Consider class of environments where states elements of some group, e.g. symmetric group or Rubik's s Cube group. The transitions are given via generating set of this group, thus corresponding to applying the group opera- tion on the current state and some element of the generating set, which leads to the existence of cycles. While in some cases an acyclic environment can be designed to generate group elements, such environments of "algebraic" origin naturally contain cycles, thus falling under the area of our study. In addition, there is growing body of work that connects GFlowNets and Reinforcement Learning (Tiapkin et al., 2024; Mohammadpour et al., 2024; Deleu et al., 2024; He et al., 2024). Most RL environments contain cycles, thus understanding how GFlowNets can be applied in cyclic en- vironments and connecting them to RL in such cases be crucial step towards further bridging two research fields.
RL and non-acyclic
1. Introduction
Generative Flow Networks (GFlowNets, Bengio et al., 2021) are models that aim to sample discrete objects from distribu- tions known proportionally up to constant. They operate by constructing an object through sequence of stochastic transitions defined by forward policy. GFlowNets have been successfully applied in various areas, starting from molecule generation (Bengio et al., 2021: Shen et al., 2024; Koziarski et al., 2024; Cretu et al., 2025) and biological sequence design (Jain et al., 2022; Kim et al., 2024) to com- binatorial optimization (Zhang et al., 2023a;b; Kim al.,
Equal contribution 'HSE University, Moscow, Russia CCMAP CNRS -éole polytechnigue Institut Polytechnique de Paris, 128, Palaiseau, France Uniiversité Paris-Saclay, CNRS, LMO, 91405, Orsay, France. Correspondence to: Nikita Morozov Homorozov@hsc.mut
To the best of our knowledge, methodological aspects of working with non-acyclic environments in GFlowNets were previously considered only in the recent work of (Brunswic et al., 2024). The latter paper, similarly to (Lahlou et al., 2023), uses the machinery of measurable spaces and mea- sure theory, which is harder to build new extensions and
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
methodology upon. We believe that simplicity is a key merit of the theory behind discrete GFlowNets (Bengio et al., 2023) when compared to their general state counterparts. Thus, the main aim of our paper is to revisit the theory of non-acyclic GFlowNets within a discrete state space, simplifying the constructions of (Brunswic et al., 2024) and providing additional theoretical and methodological insights into training Gets in this setting. The main contribu- tions of the paper can be summarized as follows:
more intuitive construction. Let T be set of all trajectories (so - 81 -> ... -> Sn, -> 85) from so to 5,, where we use R2 to denote the length of the trajectory т. We use a convention sx,+1 = 8y. We say that T terminates in s if its last transition is 8 + 85- Such transitions are called termi- nating, and the states that have an outgoing edge into sf are called terminal states. The set of terminal states coincides with X. and the probability distribution of interest R(x)/ Z is defined on it, where R(xx) > O is called GFlowNet reward and 2 = Exex R(x) is an unknown normalizing constant. In addition, for any state we denote in(s) to be the set of states s' such that there is an edge s' + 8 E & (parents), and out(s) to be the set of states s' such that there is an edge - 8 E (children).
1. We present simple and intuitive way to build theory of non-acyclic GelowNets in discrete environments from scratch. In addition to simplicity, our construction in- troduces and clarifies a number of key points regarding similarities and dissimilarities between acyclic and non- acyelic discrete GFlowNets that were not explored in (Brunswic et al., 2024), in particular regarding the nature of flows and importance of backward policies.
The main goal of GFlowNets is find a distribution P over T such that for any X, probability that T ~ P termi- nates in coincides with R(x)/ Z. This property is called the reward matching condition. GFlowNets operate with Markovian distributions over trajectories (see (Bengio et al., 2023) for a definition and discussion) using the following key components:
2. We show that when the backward policy is fixed, the loss stability introduced by (Brunswic et al., 2024) does not impact the result of the optimization procedure. The latter becomes important only when the backward policy is also being trained.
3. When backward policy is trained, we show that learn- ing a non-acyclic GFlowNet with the smallest expected trajectory length is equivalent to learning a non-acyclic GFlowNet with the smallest total flow. In addition, we way to approach
1. a forward policy Pr(s' | s), which is a distribution over children of each state;
2. a backward policy PB(s| | s'), which is a distribution over parents of each state;
propose state flow regularization the arising optimization problem.
3. state/edge flows F(s), F(s + s'), which coincide with an unnormalized probability that trajectory t passes through state/edge.
4. We empirically show that the scale in which flow error is computed in the loss plays crucial role in its stability. However, we also show that using unstable loss with the proposed state flow regularization can lead to better sampling quality.
Pr. Pn. and F are connected through the trajectory bulance conditions:
5. Finally, we generalize the key theoretical result of (Tiap- kin et al., 2024) on the equivalence between GFlowNets and entropy-regullriized RI. to the non-acyclic setting. Source code: gittbb.oomGGieaarree/oooeeeeeee
12- P(T) = II
nhe PB(se I 18441), (I)
PF (s)) = II
t=
t=0
detailed balance conditions:
2. Backkrrund
F(s s1) =( 1s) =s)= F(s))P(sss)) (2)
2.1. GFlowNets
and flow matching conditions:
This section presents necessary notations and theoretical background on GFlowNets. GFlowNets treat the problem of sampling from a probability distribution over discrete space X' as a sequential decision-making process in a di- rected acyelic graph (DAG) G = ES,E), where is a finite state space and & C S x S is a finite set of edges (or transitions). There is a special initial state so with no in- coming edges and special sink stute 8f with no outgoing edges. The commonly used variant of notation does not include a sink state $y. yet we prefer to use a variant with 8,, since it was also used in the previous work on non- acyelic GelowNets (Brunswic et al., 2024) and leads to a
F(s) Σ F(s Σ F(s" -(s)+s)) s)) (3) s"Ein(()
8' s'Eout(s)
All of these objects are completely and uniquely specified if one fixes either 1) edge flow F(s - s'), 2) initial flow F(so) and Pr. 3) initial flow F(so) and Pp. If flows satisfy F(s 8T) = R(s)., trajectory distribution defined by the corresponding forward policy will satisfy the reward match- ing condition (Bengio et al., 2023). In practice, a neural network is used to parameterize the forward policy (and, optionally, the backward policy and the flows). Then, it
2

---

Revisiting Non-Acyclic GFlowNets in Diserete Environments
trained minimize some loss function that would enforce the reward matching condition. For example, Detailed Bal- ance loss (Bengio et al., 2023) is defined on all transitions + 8' E E as:
bounded by the total normalized state flow
[2,
Σ
F(s),
(6)
F(50)
8ES((80.87)
Ls - 2') A log Po( ) Fo(s')Pu(s s0,0) {
and using a stable loss with a regularizer that controls the total flow, e-g., the norm of the edge flow matrix, can be used to learn an acyclic flow (Theorem 1).
(4)
Reward matching is enforced by substituting F(x - 9)) Fo(s)) 8y.0) = R(x) in the loss. Although the optimization task typically admits multiple solutions, fixing the backward policy results in a unique solution in terms of
3. Theory of GelowNets in Discrete Non-Acyclic Environments
3.1. Environment
F and Pp (Bengio et al., 2023).
All definitions regarding the environment can be introduced similarly to the setting of acyelic GFlowNets (see Sec- tion 2.1) with one main difference: graph 9 can now contain cycles. In addition to finiteness, we make two technical assumptions on the structure of g:
2.2. GelowNets in Non-Acyclic Environments
(Brunswic et al., 2024) state that fundamental results of GFlowNet theory also apply in the case when the environ- ment graph G may contain cycles, and all definitions from the acyclic case remain valid and extend to the non-acyclic case. However, we will further show that this is not exactly true, e.g..flws cannot be consistently defined as unnormal- ized visitation probabilities.
Assumption 3.1. 0) graph G is finite; 1) There is a special
initial state so with no incoming edges and special sink state s with no outgoing edges; 2) For any state s E S there exists a path from Sp to s and a path from s to sy-
More specifically, (Brunswic et al., 2024) argue that if (3) holds for an edge flow, as well as F(s + 8y) = Rss) for terminating transitions, the forward policy induced by the
Next, we formally define trajectories:
Definition 3.2. A sequence
(so +
Sn, + Sn,+1 = sy) is called a trajectory of length n, E N if all transitions 8 + St41 E E, {o...., nn). Then T is a set of all finite-length trajectories that start in so and finish in 8y-
flow PP(s' | 8) F(a-te) satisfies the reward matching condition. Thus, standard GFlowNet losses, such as Flow Matching (FM, Bengio et al., 2021). Detailed Balance (DB, Bengio et al., 2023), and Trajectory Balance (TB, Malkin et al., 2022) can be applied in non-acyclic environments.
F(*)
In the above definition and further, we use a convention Sn, +1 = 8y- While G itself is always finite, the main difference with acyclic GFlowNets is that T can be infinite, and T can contain trajectories of arbitrary length.
However, (Brunswic et al., 2024) point out that the main dis- tinction between non-acyclic and acyclic GFlowNets is that in the non-acyclic setting, expected trajectory length E[[r]] (denoted as a sampling time in (Brunswic et al., 2024)) can be arbitrarily large because of the cycles, while in the acyelic setting it is always bounded. To tackle this issue, a concept of loss stability is introduced. A loss is called stable if adding a constant to the flow along a cycle can never decrease the loss, and otherwise, it is called unstable (Definition 3). It is shown that FM, DB, and TB are unstable (Theorem 3), which can lead to arbitrarily large sampling time when utilized for training. In contrast, a family of losses that are provably stable is presented (Theorem 4). Moreover, the authors show that there are stable variants of FM and DB losses, such as stable DB loss, which we denote as SDB:
3.2. Backward Policy and Trajectory Distribution
There are several equivalent ways to introduce probability distributions over trajectories in GFlowNets. One of the common approaches is to start by introducing trajectory flows (Bengio et al., 2023). The main theoretical advantage of the approach based on trajectory flows is that it allows for non-Markovian flows, see (Bengio et al., 2023). At the same time, Markovian flows are primarily considered in GFlowNets literature, and in our paper, we only consider this setting. Instead of starting from the definition of the flow, more intuitive approach is to begin with the defini- tions of the forward and backward policies.
Definition 3.3. A forward policy (s s) consistent with G is family of conditional probability distributions over s' E out(s) defined for each E S \ {sy), Similarly, a backward policy (p s') consistent with g is a family of conditional probability distribution over s E in(s'), defined for each s' E E {sp)
(sne(s + +s))= & log(1 + = (s, 8', ())(1 (s))s) 8(5,8,00) 0) & (s/1s,))) Fo(s') 0),
(5)
where E and 17 are hyperparameters. addition, (Brunswic et al., 2024) show that the expected trajectory length is
3

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
In the subsequent parts of the paper, we always assume that the considered Pr PB are consistent with & and do not specify this fact explicitly. Definition 3.3 is consistent with the definitions of forward and backward policies in acyclic GetowNets (Bengio et al., 2023, Definition 4). Note that the structure of 9 is symmetric with respect to an interchange between initial state 80 and sink state sy and reversion of all edges in G. Thus, starting with either Pp or Pg is equivalent. We prefer to start from backward policy PB in subse- quent derivations. Using PB. we define probability dis-
One can see that the flow matching condition (3) does not hold for states and since 1 * 0.5. Instead, let us calculate the expected number of visits for each edge s
Σ (=0
1s+ = 8,8+1 8
We visualize the corresponding numbers on the plot below:
88
tribution P over T = (80- + according to
8n- 84) T
It is easy to check that the flow matching conditions (3) are now satisfied. Next, we formally define:
P(T)= II Pn(Se 84+1) t=
(7)
Definition 3.5. Let PB(s s') be a backward policy, such that PB(s s') > 0 for any edge s -+ s' E Then, given a final flow F(sy) > O, we define state and edge flows as
In such a case, we say that the trajectory distribution PP()) induced by PB. In the following lemma, we show that (()) is a correctly defined probability distribution over T.
F(s + 2 ETOP
1lsc
= 3, 81411 = s'}
Lemma 3.4. Let PB(s| | s') be a backward policy, such that
my Σ t=0
PB(s| s') > for any edge s s' EEE E. Then
F(8) 2 F(s)) ETwp(r)
11 = 8}
(8)
P(T) defined in (7) is a probability distribution over
T, thut is, ErET P(T)= = 1.
We say that the flows defined above are induced by the backward policy PB and final flow F(sy).
Moreover, its expected trajectory length is always finite B,-p|n,]= = ErET n, P(T)) < -00.
It is important to note that if G does not contain cycles, the expected number of visits in (8) coincides with visitation probability, thus Definition 3.5 agrees with the usual under- standing of flows in the acyclic GFlowNet literature. Next, we show that state and edge flows defined in (3.5) satisfy the detailed balance and flow matching conditions (2) - (3).
In fact, the condition PB(s| s') > 0 together with Assump- tion 3.1 allows us to ensure that the sequence 8, is a finite state-space absorbing Markov chain. Given this assumption, the proof of Lemma 3.4 almost coincides with the proof of the fact that the states of such a Markov chain are transient, see, e.g., (Douc et al., 2018). For completeness, we provide the proof in Appendix A.I.
Proposition 3.6. Flows F defined in Definition 3.5 satisfy:
F(s)
FFF(s
Σ F(s s') (b)
Σ J(5" E s):
3.3. State and Edge Flows
('ouu(s))
8" in(e)
Given a probability distribution P(7) induced by PB. our next aim is to define state and edge flows. Before proceeding with valid construction, we provide some intuition about our definitions. Let us first show that, contrary to the acyclic NetowNets, we cannot define edge flows as visitation prob- abilities P({r E T s + s' E T)) In particular, we show that such a definition does not satisfy the flow matching con- ditions (3). Indeed, consider an example from (Brunswic et al., 2024):
for each E S $5. Moreover, identity (a) holds for su, and (b) holds for sj.
2. F(s + 80) F(s))pps s') for any - s E E.
3. F(so)= = F(s))
We provide the proof in Appendix A.2. In the next propo- sition, we show that there is a one-to-one correspondence between a pair (PB, (PB,F(s) F(sy)) and edge flows F. Its proof provided in Appendix A.3.
80
0.5
b
0.5
1 81
Proposition 3.7. Let F E E R20 be function that satisfies the flow matching conditions (3), Define the corre- sponding backward policy by the relation
The number above each edge s s' is PB(S s'). Con- sider the distribution P(T) defined by (7). Let us plot the visitation probability for each edge:
PB(s 80) = =(s / Σ
F(s" + =s)).
s'Ein(s')
Then F are edge flows induced by PB and F(8)) Σ Ex F(s" -t 88).
0.5
80
b
81
4

---

Revisiting Non-Acyclic GFlowNets in Diserete Environments
3.4. Forward Policy and Detailed Balance
following proposition shows how the reward matching con- dition can be formulated in terms of flows.
is well-known in acyclic GFlowNets theory (Bengio et al., 2023) that there exists a unique forward policy Pp for any backward policy PB that induces the same probability dis- tribution over T. The main implication of this fact is that by fixing rewards R(x), x E X' and a backward policy PB[(5] s') for each state s' E S {50, sy}, one automat- ically fixes a trajectory distribution P(r) that satisfies the reward matching condition (Malkin et al., 2022). How- ever, sampling from a such distribution is intractable since it requires starting from a terminal state sampled from the reward distribution. Thus, during GFlowNet training, one tries to find forward policy, which always allows tractable sampling of trajectories by construction, that will match this trajectory distribution P(r). One can note that this bears similarities with hierarchical variational inference (Malkin al., 2023). In the following proposition, we show that this result also holds for non-acyclic GFlowNets.
Proposition 3.10. Let ( s') > 0 be a backward policy, F(s;) > 0 a final flow, and R(x) > 0 GFlowNet rewards. If edge flows F(s - 5') induced by Pa and F(sr) satisfy:
F(x ( R(x) VI + 555 +
(9)
the trajectory distribution P induced by PB (7) satisfies the reward matching condition, i.e. PT~ples = x] R Then, the same trajectory distribution induced by the unique corresponding forward policy Pp, thus also satisfying the reward matching condition.
Proof. Notice that an edge leading into sy can be vis- ited only once; thus, F(x - 85) coincides with a prob- ability I Prop Pnaplnn, times the final flow F(sy). In addition, we have F(sy) Exein(ey) F(x + 81) P Proplsn, = x] F(x + +s)/F((s)) = R(x)/Z.
x] that a trajectory terminates in
Exex R(x) = Z, thus
Proposition 3.8. Given any backward policy PB((5 1&)> 0, there exists a unique forward policy Pp(s') 8) such that
P(r) = II Pb( 8441) = II Pr (1))))))))))))))))))))))))))))) TTET.
Proposition 3.10 also implies F(so) = F(8s) = E and PB(2 sy) = R(x)/2 by Proposition 3.6.
t=
t=0
Moreover, it satisfies the detailed balance conditions
An important fact from the literature on acyclic GFlowNets (Malkin et al., 2022; Bengio et al., 2023) that was overlooked in the work of (Brunswic al., 2024), but holds in the non-acyclic case well, is that it is gener- ally easy to manually pick backward policy such that the induced trajectory distribution will satisfy the reward match- ing condition. A simple and natural choice is to take PB(2 | sy) = R(x)/2 for sy and fix PB(s 8') = 1/| in(ss)) (s)) for all other states. It is worth mentioning that Z is generally unknown, but this issue is circumvented in GFlowNets by learning unnormalized flows making 2 itself learnable parameter depending on the chosen loss function (Malkin et al., 2022; Bengio et al., 2023; Madan et al., 2023). More- over, Proposition 3.8 shows the uniqueness of the corre- sponding Pp. Thus, we state the main practical corollary of this result:
F(s) s) = F(s')Pu(s ss), Vs + E
with the state flow F defined in (8).
The proof is provided in Appendix A.4. Conversely, the fol- lowing proposition shows that if a triplet F, Pr. PB satisfies the detailed balance conditions (2), it will be consistent with all previous definitions and propositions.
Proposition 3.9. Let F: S + Rz and let Pp(8'(s) > O, Pis(s(s)== > 0 be forward and backward policies. such that the detailed balance conditions (2) are satisfied. Then Pp and PB induce the same trajectory distribution:
Th.
The
P(r) = II (
III (t), TTET.
t=0
Moreover, then F are state flows induced by PB and F(st).
Corollary 3.11. When a backward policy PB > 0 is fixed, any loss from the acyelic GFlowNet literature (Bengio et al., 2021; Malkin et al., 2022; Bengio et al., 2023; Madan et al., 2023) can be used to learn the corresponding forward pol- icy Pp in the non-acyclic case as well. Lemma 3.4 and Proposition 3.8 imply that there is always unique solution with a finite expected trajectory length, thus the stability of the loss (Brunswic et al., 2024) does not play factor.
For proof, we refer to Appendix A.5. The above proposi- tions directly generalize their counterparts from the non- acyelic setting (Bengio et al., 2023). Note that, due to the symmetries between 8p and 8y in G up to changing direc- tion of edges, we could start from the forward policy and trajectory distribution induced by it in (7), and then prove the uniqueness of the corresponding backward policy PB.
The main disadvantage of learning with a fixed backward policy in non-acyclic GFlowNets that does not arise in acyclic GFlowNets is the fact that the expected trajectory length [n+] of a manually chosen PB can be large. A natural way to circumvent this issue to consider a
3.5. Training Non-Acyclic GFlowNets
Now, we proceed with the main learning problem in GFlowNets: finding a forward policy that matches the re- ward distribution over terminal states R(x)/2,x E X. The
5

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
learnable backward policy, which is also a widely em- ployed choice in acyelic GFlowNet literature (Malkin et al., Jang et al., 2024a; Gritsaev et al., 2025). However, (Brunswic et al., 2024) made an important discovery by pointing out that standard losses from acyelic GFlowNet literature are not stable (Theorem 3), meaning that the ex- pected trajectory length can grow uncontrollably during training. The concept of stability was introduced with re- spect to learnable edge flows (Definition 3), which implies that the corresponding backward policy also changes during training. Using a stable loss, e.g. (5), was proposed as way to approach this issue. At the same time, we argue that efficient training of a non-acyclic GFlowNet with controlled expected trajectory length in case of a learnable PB is pos- sible without utilizing stable losses. The next proposition is a simple corollary of Definition 3.5:
where À > 0 is hyperparameter that controls trade-off between an expected trajectory length and an accuracy of matching the reward distribution. As in (4), reward match- ing is enforced by substituting PB(s)) sy:0) (xx).
Note that the DB loss is defined on individual transitions, and during training, it is optimized across transitions collected by a training policy. A standard choice is to optimize over transitions from trajectories sampled using Pe, yet the training policy can be chosen differently, or, in RL terms, training can be done in an on-policy or off-po fashion, see (Tiapkin et al., 2024). Note that different states might appear with different frequencies in the loss depending on a training policy, which can lead to a bias the optimization problem (II). We discuss this phenomenon in more detail, as well as potential ways to mitigate it, in Appendix B.
Proposition 3.12. Given a trajectory distribution P, its
Finally, it is important to mention that flow-based regu- larizers in the non-acyclic case were already proposed in Theorem of (Brunswic et al., 2024), but only for the sta- ble loss setup. Moreover, they were introduced in order to find an acyelic flow. Our paper further explores and sheds new light on this phenomenon, showing that training can be carried out even when unstable loss is utilized with regularization. Moreover, when the total flow is minimized, one can ensure the smallest possible expected trajectory length. It is also worth pointing out that the idea of intro- ducing a constrained optimization problem to accommodate for cycles in GFlowNets was mentioned in (Deleu, 2025).
expected trajectory length is equal to the normalized total flow:
Bawp(ur]= F(st)
Σ F(s).
(10)
sES
The proof is presented in Appendix A.6. This result is refinement of Theorem 2 of (Brunswic et al., 2024), which states only 's' inequality in (10). Thus, we believe one of our key contributions to pointing out the following fact:
Learning a non-acyclic GFlowNet with the smallest expected trajectory length is equivalent to learning a non-acyclic GFlowNet with the smallest total flow.
3.6. Connections with Entropy-Regularized RL
A recent line of works (Tiapkin et al., 2024; Delcu et al., 2024) studied connections between GelowNets and RL, showing that the GFlowNet learning problem is equivalent to an entropy-regularizzed RL (Neu et al., 2017; Geist et al., 2019) problem in an appropriately constructed deterministic MDP, given that the backward policy is fixed. We show that the same result holds for non-acyclic GelowNets as well.
We also believe that exploiting this equivalence is a crucial direction for future research on non-acyclic GFlowNets. We further explore particular solution, which suggests the use of a state flow as regularizer in the existing GFlowNet losses. We consider an example of the detailed balance loss DB (4). In this case, Proposition 3.9 implies that learning a non-acyclic GelowNet with the smallest expected trajec- tory length can be formulated as the following constrained optimization problem:
Let G be a graph of a non-acyclic GFlowNet, R a GelowNet reward, and PB > a fixed backward policy that satisfies the reward matching condition. Let F be the flow induced by PP with F(s,) Z, and Pp be unique forward policy corresponding to Pp. (see Proposition 3.8). Define a deter- ministic MDP Mg induced by a graph G. where the state space S coincides with vertices of G, the action space A, for each state s corresponds to out(s), and the transition kernel is defined as transition in the graph P(s' | 8,, a) = IT(a = 8'), a E out(s). We use no discounting (7 = 1.0) and set RL rewards for terminating transitions r(2, sy) log R(x), and for all other transitions r(s, s') - log Pn s'). Then, the following statement holds.
min F.Po,PB
Σ F(s)
(11)
log F(s)Pp(s' 5)
subject to
=0, V s' E
F(s)PPp 85)
F(s)) $4) = R(x),
- 8 EE
As an approximate way to solve (11), one can use DB (4) with state flow regularization:
1og Fo(s)Pp(s' s, + >FFss),
Theorem 3.13 (Generalization of Theorem I (Tiapkin et al., 2024)). The optimal policy ( 8) for the entropy- (12)
Fo(e))P((s|s
6

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
regularized MDP Mg with coefficient 1 is equal to Pr(s') | 8) for all & {sy},s' Ass- Moreover, reg- ularized optimal value V (s) and Q-value Q2-1 8') coincide with log F(s) and log F(s + +') respectively for all 8 + s' E.
hypergrid 7x7
10
full
The proof and all missing definitions are provided in Ap- pendix A.7. Note that the proof of (Tiapkin et al., 2024) cannot be directly transferred to the non-acyelic setting since it is based on induction over the topological ordering of vertices of G, which exists only for acyclic graphs.
10
10
10
training trajectorics
moze trajectery reteeeeryy lenaah
60
US. 2lng P- ficts
40
SCB, train
DS mang trai
4. Experiments
DS. dlog A- 0.002, train
20
exparess
fooed
In addition to verifying our theoretical findings, one of the goals of our experimental evaluation is to examine the scal- ing hypothesis that we put out:
10a
10
10
training trajectories
Figure I. Comparison of non non-acyclle acyelic GFlowNet training losses on small hypergrid environment. We use DE or SDB to specify the utilized loss, log J or AF to specify the flow scale used to compute the error in the loss, and use À C to specify the usage of the proposed state flow regularization. Top: evolution of T,² distance between empirical distribution of samples and target distribution. Bottom: evolution of mean length of sampled trajectories.
Scaling hypothesis. When PR is trainable, the main factor that plays a crucial role in loss stability in practice, i.e., the controlled mean trajectory length of the trained non-acyclic GFlowNet, is the scale in which the eгror between flows is computed. Indeed, the standard D3 loss (4) operates in log-flow scale A log F, while standard SDB (5) operates in flow scale AF. We hypothesize that using log-flow scale losses without regularization can lead arbitrarily large trajectory length, while flow scale losses are biased towards solutions with smaller flows and thus do not suffer from this issue.
still achieves a high average reward despite resulting in mode collapse. For instance, recent works argue that mea- suring the deviation of mean sample reward from the true expected reward > R(x) 2 results in a better metric, see, e.g., (Shen et al., 2023) for detailed motivation. In addi- tion, we employ other metrics to track sampling accuracy depending on the environment, which we discuss in detail below.
R(z)
In this section, we use DB or SDB to specify the utilized loss, A log F or A to specify the flow scale used to compute the error, and use = C' to specify the strength of the proposed state flow regularization (see Section 3.5). For example, (DB, A log in the legend corresponds to (4), (SDB, A.F) corresponds to (5) and (DB, A log F, À C) corresponds to (12). Detailed discussion on loss scaling and stability is provided in Appendix B.2.
In both environments, we consider two settings: training with a fixed backward policy PB that is almost uniform and using trainable PB- In the second case, the initial log flow log Fo(s)) = log Ze is also being learned. Thus, we can examine its convergence to the logarithm of the true normalizing constant log 2. See Appendix B.3 for details.
4.1. Experimental Setting
We consider two discrete environments for experimen- tal evaluation: 1) non-acyclic version of the hypergrid environment (Bengio et al., 2021) that was introduced in (Brunswic et al., 2024); 2) non-acyclic permutation gen- eration environment from (Brunswic et al., 2024) with a harder variant of the reward function. Experimental details presented in Appendix C.
4.2. Hypergrids
We start with non-acyclic hypergrid environ- ments (Brunswic et al., 2024). These environments are small enough that the normalizing constant Z can be computed exactly, and the trained sampler can be efficiently evaluated against the exact reward distribution. States points with integer coordinates E {O...., H - -1) inside a D-dimensional hypercube with side length H, plus two auxiliary states So and sy. Possible transitions correspond to increasing or decreasing any coordinate by without exiting the grid. Moreover, each state has terminating
Mean sample reward was used as metric in (Brunswic et al., 2024), with higher values considered better. However, we point out that this does not always represent sampling accuracy from the reward distribution R/Z. Indeed, the model that learned to sample from the highest-reward mode
7

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
hypergrid 20x20x20x20
hypergrid 20x20x20X20
hypergrid 20x20x20x20
350
DR, AF
500,
7.5
06, Algg 0.000
mcan trajectory langth
Mlng
5.0
250
2.5
Full empincalll L'
200
0.0
-2.5
Nigg. 0.001
100
AF
5.0, Algg 1 0.001
expected artor
50
-7.5
50B, Zlog7, D.001
SD0, ATT
d- 0.0001
U:00 1og2
10-1
0.
-10.0
10
30
10"
10
100
10
10'
10"
training trajectories
training trajectories
training trojectories
Figure 2. Comparison of non-acyclic GFlowNet training losses on a larger hypergrid environment. We use DB or SDB to specify the utilized loss, A log F or AFF specify the flow scale used compute the error in the loss, and use À C' to specify the usage of the proposed state flow regularization. Left: evolution of L' distance between an empirical distribution of samples and target distribution. Middle: evolution of mean length of sampled trajectories. Right: evolution of the trained initial log flow log Ze.
Table 1. Comparison on the permutation environment. (()) L' is the L distance between the true and empirical distribution of fixed point probabilities C(K)). AR is the relative error of mean reward proposed in (Shen et al., 2023), A log 2 is log Ze log 2|. Mean and std values are computed over 3 random seeds. Blue indicates the best metrie, red indicates the smallest expected trajectory length.
8
20
Loss
C(k) L'
AR +
A log 2 4
B[n=]]
C(k) L' 4
AR +
A log 2 +
E/m-]
DE, AF
0.215 10.198
0.214 10.066
0.814 20.828
2.43 20.28
0,453 a0.002
0.343 10.000
42.98 10.000
2.00 10.00
SDB, AF
0.031 10.012
0.046 10.023
0.074 10.025
3.32 10.15
0.452 10.001
0.343 10.000
42.98 10.000
2.01 10.00
DB, A log. F, x 10
0.036 10.015
0.056 10.024
0.018 10.010
2.80 20:04
0.041 10.002
0.064 10.000
0.023 a0 005
3.23 10.00
SDB, log F, X 10-3
0.037 #0.013
0.056 +0.019
0.020 #0.015
2.79 20.04
0.0-1 #0.002
0.064 40.000
0.026 50.003
3.22 #0.00
DB, A log F, A 10-5
0.005 :0.000
0.001 +0.000
0.005 50 004
4.31 20:05
0.017 H0.002
0. 0..3 #0.002
0. 0.003 -o 003
7.55 80.50
SDB, A log F, A 10 5
0.005 +0.001
0.002 +0.000
0.006 +0.008
4.36 +0.00
0.0144 +0.001
0. +0.001
0.005 +0.005
7.31 +0.07
transition sy, thus X' = S {su, sy). The reward function has modes near the grid corners, separated by wide troughs with very small rewards. To measure sampling accuracy, total variation distance is computed between the true reward distribution R(z)/Z and an empirical distribution of the last 2 10 samples seen in training, which coincides with 1 of the _ distance on discrete domains.
PB. Finally, interesting note is that using an unstable DB loss in A log F scale without state flow regularization can still result in a small expected trajectory length, as we see in this experiment. However, we further show that this is not the case for a larger environment.
Next, we consider a larger 20 20 x 20 x 20 hypergrid. An expected trajectory length induced by the chosen fixed backward policy is several orders of magnitude larger than for a smaller grid, making this approach impractical. While one can try to manually find a fixed PB with a smaller expected trajectory length, this is generally a challenging problem, thus, we consider only the setting of trainable PB here. Our findings are presented in Figure 2. Similarly to 7x grid, we find that learning in AF scale results in a biased policy both for DB and SDE, and this bias is noticeably larger than in the smaller grid. In A log F scale, both DB and SDB employed with state flow regularization learn to correctly sample from the reward distribution. While all methods converge to similar expected trajectory length, AF scale losses have smaller n,, the middle of the training even when employed without regularization, which supports our scaling hypothesis. In addition, Figure 4 in Appendix D
2
We begin our analysis with a 7 x 7 grid to study the ef- feets of learning under a fixed backward policy compared to a trainable backward policy. Since the environment is small, it is possible to find the flows induced by the fixed PB exactly, thus also its expected trajectory length, see Ap- pendix B.4. Figure 1 presents the results. First, we note that both (D3, A log and (SDB, AF) with fixed PB con- verge to the true expected trajectory length induced by the fixed backward policy, which is in line with Corollary 3.11. However, for all losses, using trainable PB allows us to find a solution with a smaller trajectory length. In addition, we observe that using a loss in AJ scale results in slower convergence and slight bias in the learned forward policy than in the case of A log F scale, for both fixed and learned
8

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
shows that for both losses in A log F scale, mean length of sampled trajectories tends to infinity when the training is done without state flow regularization. Finally, we note that A log F losses correctly learn the true normalizing constant 2, while AF losses perform worse.
tion, we see that using a smaller regularization coefficient À on the one hand results in a model with larger expected trajectory length, but on the other hand, results in model that better matches the reward distribution. Finally, we per- form the same experiment as for hypergrids (Figure 1) with a fixed PB compared to a trainable PB on small permuta- tions of length n = 4, and make similar observations to the ones presented in Section 4.2. The results are presented in Figure 6 in Appendix D.
4.3. Permutations
Next, we consider the environment corresponding to the Cayley Graph of the symmetrie group Sn, (group of permu- tations on n clements {1, ...2,...,... m.)) from (Brunswic et al.,
4.4. Discussion
2024). Each state s E S {50,85) 3 J is a permutation of fixed length (s(1). s(n)) and there are n possible transitions that correspond swapping a pair of adjacent elements sk) and sk + 1). plus transition that corre- sponds to a circular shift of the permutation to the right (.))..... sn - 1)). In addition, each state has ter- minating transition s + sy. GFlowNet reward utilized in the experiments of (Brunswic et al., 2024) is [[s(1) = 1]. We argue that this results in fairly simple task, and a trivial forward policy exists that just applies circular shift until is in the first position. We opt for using more complex reward distribution in our experiments and define GFlowNet reward in terms of the number of fixed points in permuta- tion Rs)) = ( Σ [fs( = =)))
The key observations from our experimental evaluation are:
1. Learning with fixed PB is possible without sta- ble losses and regularization, however, manually picking Pp with small B[n+] is challenging;
2. When Pn is trained, our results empirically support the scaling hypothesis, showing that even the stan- dard DB in AF scale is stable; however, non-acyclic GFlowNets trained with AF scale losses often fail to accurately match the reward distribution;
3. Both DB and SDB in A log F scale result in better matching the reward distribution but need to be uti- lized with state flow regularization to ensure small expected trajectory length B[mz]]
Since with the growth of n. the number of states n! quickly becomes too large to compute total variation distance as it track convergence of num-
was done for hypergrid, ber of statisties to their true respective values. Firstly, we compute the relative error between the mean reward of
5. Conclusion
In our paper we extended the theoretical framework of GFlowNets to encompass non-acyelic discrete environ- ments, revisiting and simplifying the previous constructions by (Brunswic et al., 2024). In addition, we provided a number of theoretical insights regarding backward policies and the nature of flows in non-acyclic GFlowNets, general- ized known connections between GFlowNets training and regulay-rggllriized RL to this setting, and experimentally re-examined the importance of the concept of loss stability proposed in (Brunswic et al., 2024).
GFlowNett samples and the true expected reward as it was proposed in (Shen et al., 2023). Secondly, denote C(k) as the probability that a permutation sampled from the re- ward distribution has i fixed points. We compute the I
error between the vector (C(0), C(I),..,, C(n)) ((n)) and its empirical estimate over the last 10a samples seen in training. Finally, we track the convergence of the trained log Zg to the true value of log Z. In Appendix C. we show how true reference values of these quantities can be efficiently computed.
Future work could explore applying other losses from acyclic GFlowNet literature (Madan et al., 2023; Silva et al., 2024; Hu et al., 2025) to the non-acyclit setting. Based on Theorem 3.13, another promising direction to ap- ply known RL techniques and algorithms to Gets in the non-acyclic case, following their success for acyelic GFlowNets (Tiapkin et al., 2024; Mohammadpour et al., 2024; Lau et al., 2024; Morozov et al., 2024). Finally, envi- ronments where all states are terminal, i.e., have a transition into $,, naturally arise in the non- non-acyclic case. Then, special modifications can be introduced to improve the propagation of the reward signal during training (Deleu et al., 2022; Pan et al., 2023; Jang et al., 2024b).
Table presents the results for n and n 20. Here, PB is trained in all cases. While for n 8, the environment is still relatively small, = 20 results in more challenging environment with ~ 2.4-10 10 states, thus the trained neural network needs to generalize to states unseen during training in order to match the reward distribution. Firstly, we note that while AF scale losses can learn the reward distribution to some capacity for n 8, they fail for n = 20. How- ever, in all cases, they converge small E[n.), supporting our scaling hypothesis. On the other hand, we find that GFlowNets training with A log F losses and state flow reg- ularization converges to low values of reward distribution approximation errors for both n = and n = 20. In addi-
9

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
Acknowledgements
environments. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
We would like to thank Leo Maxime Brunswic for the help- ful discussion and providing implementation details of the paper (Brunswic et al., 2024). This work was supported by the Ministry of Economic Development of the Russian Federation (code 11-139-66879-1-00000 supported in part through computational resources of HPC facilities at HSE University (Kostenetskiy et al., 2021).
Douc, R., Moulines, E.,, Priouret, P., and Soulier, P. Markov chains. Springer Series in Operations Research and Fi- nancial Engineering. Springer, 2018. ISBN 978-3-319. 97703-4.
This research was
Geist, M., Scherrer, B., and Pietquin, O. A theory of regu- larized markov decision processes. In International Con- ference on Machine Learning, pp. 2160-2169, PMLR, 2019.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Gritsaev, T., Morozov, N., Samsonov, S., and Tiapkin, D. Optimizing backward policies in GFlownets via trajectory likelihood maximization. In The Thirteenth International Conference on Learning Representations, 2025.
References
He, H., Bengio, E., Cai, Q., and Pan, L. Random policy evaluation uncovers policies of generative flow networks. 2024.
Bengio, E., Jain, M., Korablyov, M., Precup, D., and Ben- gio, Y. Flow network based generative models for non- iterative diverse candidate generation. Advances in Neu- ral Information Processing Systems, 34:27381-27394. 2021.
arXiv preprint arXiv:2406.0220
Hu, E. J., Jain, M., Elmoznino, E.,, Kaddar, Y., Lajoie, G., Bengio, Y., and Malkin, N. Amortizing intractable infer- ence in large language models. In The Twelfth Interna- tional Conference Learning Representations, 2023.
Bengio, Y., Lahlou, S., Deleu, T., Hu, J., Tiwari, M., and Bengio, E. Gflownet foundations. Journal of Machine Learning Research, 24(210):1-55, 2023.
Hu, R., Zhang, Y., Li, Z., and Huang, L. Beyond squared error: Exploring loss design for enhanced training of generative flow networks. The Thirteenth International Conference on Learning Representations, 2025.
Bertsekas, D. Dynamic programming and optimal control: Volume I, volume 4. Athena scientific, 2012.
Jain, M., Bengio, E., Hernandez-Garcia, A., Rector- -Booos, J., Dossou, B. F., Ekbote, C. A., Fu, J., Zhang, T., Kil- gour, M., Zhang, D., al. Biological sequence design with gflownets. In International Conference on Machine Learning, pp. 9786-9801. PMLR, 2022.
Brunswic, L., Li, Y., Xu, Y., Feng, Y., Jui, S., and Ma, L. A theory of non-acyclic generative flow networks. In Proceedings of the AAA/ Conference on Artificial Intelli- gence, volume 38, pp. 11124-11131, 2024.
Comtet, L. Advanced Combinatories: The Art of Finite and Infinite Expansions. Reidel, 1974.
Jang, H., Jang, Y., Kim, M., Park, J., and Ahn, S. Pessimistic backward policy for GFlowNets. In Advances Neural Information Processing Systems, volume 37, pp. 107087- 107111, 2024a.
Cretu, M., Harris, C., Igashov, I., Schneuing, A., Segler, M., Correia, B., Roy, J., Bengio, E., and Lio, P. SynFlowNet: Design of diverse and novel molecules with synthesis constraints. In The Thirteenth International Conference Learning Representations, 2025.
Jang, H., Kim, M., and Ahn, S. Learning energy decompo- sitions for partial inference in GFlownets. In The Twelfth International Conference on Learning Representations, 2024b.
Deleu, T. Generative flow networks: Theory and applications to structure learning. arXiv preprint arXiv:2501.05498, 2025.
Kemeny, J. G. and Snell, J. L. Finite markov chuins, vol- ume 26. van Nostrand Princeton, NJ, 1969.
Deleu, T., Góis, A., Emezue, C., Rankawat, M., Lacoste- Julien, S., Bauer, S., and Bengio, Y. Bayesian structure learning with generative flow networks. In Uncertainty in Artificial Intelligence, pp. 518-528. PMLR. 2022.
Kim, H., Kim, M., Yun, T., Choi, S., Bengio, E., Hernández- García, A., and Park, J. Improved off-policy reinforce- ment learning in biological sequence design. arXiv preprint arXiv:2410.044:0 2024.
Deleu, T. Nouri, P., Malkin, N., Precup, D., and Bengio, Y. Discrete probabilistic inference as control in multi-path
Kim, M., Choi, S., Kim, H., Son, J., Park, J., and Bengio, Y. Ant colony sampling with GFlowNets for combinatorial
10

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
optimization. In International Conference on Artificial Intelligence and Statistics. PMLR, 2025.
Neu, G., Jonsson, A., and Gómez, V. A unified view of entropy-regularizee markov decision processes. arXiv preprint 1rxXiv:705.077999: 2017.
Kostenetskiy, P., Chulkevich, R., and Kozyrev, V. Hpe resources of the higher school of economics. In Journal of Physics: Conference Series, volume 1740, pp. 012050. IOP Publishing, 2021.
Pan, L., Malkin, N., Zhang, D., and Bengio, Y. Better training of gflownets with local credit and incomplete trajectories. In International Conference Machine Learning, pp.
PMLR, 2023.
Koziarski, M., Rekesh, A., Shevchuk, D., van der Sloot, A., Gainski, P., Bengio, Y., Liu, C., Tyers, M., and Batey, R. Rgfn: Synthesizable molecular generation using gflownets. Advances in Neural Information Processing Systems, 37:46908 46955, 2024.
Shen, M. W., Bengio, E.,, Hajiramezanali, E., Loukas, A., Cho, K., and Biancalani, T. Towards understanding and improving gflownet training. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMI..org. 2023.
46955,
Lahlou, S., Deleu, T., Lemos, P., Zhang, D., Volokhova, A., Hernández-Garcia, A., Ezzine, L. N., Bengio, Y., and Malkin, N. theory of continuous generative flow net- works. In International Conference on Machine Learning, pp. 18269-18380 PMLR, 2023.
Shen, T., Seo, S., Lee, G., Pandey, M., Smith, J. R., Cherkasov, A., Kim, W. Y., and Ester, M. TacoGFN: Target-conditioned GFlowNet for structure-based drug design. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Lau, E., Lu, S., Pan, L., Precup, D., and Bengio, E. Qgfn: Controllable greediness with action values. Advances in neural information processing systems, 644566668,, 2024.
Silva, T., de Souza da Silva, E., and Mesquita, D. On divergence measures for training gflownets. Advances Neural Information Processing Systems, 37:75883- 75913, 2024.
Lee, S., Kim, M., Cherif, L., Dobre, D., Lee, J., Hwang, S. J., Kawaguchi, K., Gidel, G., Bengio, Y., Malkin, N., and Jain, M. Learning diverse attacks on large language models for robust red-teaming and safety tuning. In The Thirteenth International Conference on Learning Repre- sentations, 2025.
Tiapkin, D., Morozov, N., Naumov, A., and Vetrov, D. P. Generative flow networks as entropy-regulatized rl. In International Conference on Artificial Intelligence and Statistics, pp. 4213-4221. PMLR, 2024.
Uehara, M., Zhao, Y., Biancalani, T., and Levine, S. Un- derstanding reinforcement learning-basse based fine-tuning of diffusion models: A tutorial and review. arXiv preprint arXh::2407.13744 2024.
Madan, K., Reetor-Brooks J., Korablyov, M., Bengio, E., Jain, M., Nica, A. C., Bosc, T., Bengio, Y., and Malkin, N. Learning gflownets from partial episodes for improved convergence and stability. International Conference on Machine Learning, pp. 23467-23483, PMLR, 2023.
Venkatraman, S., Jain, M., Scimeca, L., Kim, M., Sendera, M., Hasan, M., Rowe, L., Mittal, S., Lemos, P., Bengio, E., Adam, A., Rector-Brooks, J., Bengio, Y., Berseth, G., and Malkin, N. Amortizing intractable inference in diffusion models for vision, language, and control. Neural Information Processing Systems (NeurIPS), 2024.
Malkin, N., Jain, M., Bengio, E., Sun, C., and Bengio, Y. Trajectory balance: Improved credit assignment in gflownets. Advances in Neural Information Processing Systems, 35:5955-5967, 2022.
Zhang, D.,, Dai, H., Malkin, N., Courville, A. C., Bengio, Y., and Pan, L. Let the flows tell: Solving graph combi- natorial problems with gflownets. In Advances in Neural Information Processing Systems, volume 36, pp. 11952- 11969, 2023a.
Malkin, N., Lahlou, S., Deleu, Ji,
Ji, X., Hu, E. J., Ev- erett, K. E., Zhang, D., and Bengio, Y. GFlownets and variational inference. In The Eleventh International Con- ference Learning Representations, 2023.
Zhang. D., Zhang. Y., Gu, J., Zhang, R., Susskind, J. M., Jaitly, N., and Zhai, S. Improving gflownets for text- to-image diffusion alignment. Transactions on Machine Learning Research, 2025, ISSN 2835-8856.
Mohammadpour, S., Bengio, E., Frejinger, E., and Bacon, P.-L. Maximum entropy gflownets with soft l-laarning In International Conference on Artificial Intelligence and Statistics, pp. 2593-2601, PMLR, 2024.
Zhang, D. W., Rainone, C., Peschl, M., and Bondesan, R. Robust scheduling with gflownets. In The Eleventh International Conference on Learning Representations, 2023b.
Morozov, N., Tiapkin, D., Samsonov, S., Naumov, A., and Vetrov, D. Improving gflownets with monte carlo tree search. arXiv preprint arXiv:2406. 33655, 2024.

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
A. Proofs
A.1. Proof of Lemma 3.4
Consider a random walk on 9 with reversed edges transition probabilities given by backward policy. Specifically, we define Markov chain (x such that X, of a.s. and P[X; s X,-1 s11 PB(s s'). Let also
PIX; so X,,1 so] i.e., 5g is absorbing state. We want show that
1. The random walk terminates at 8o with probability 1: P[3n: : X, = so] = 1;
2. The expected length of a walk finite: E[m-] EI 1(x; # s0}] < oc.
In particular, the first statement implies that P(-) is a correct probability measure over finite trajectories since for any (50, .... Sn, Sn,,8 8y)
it holds
P((X, n. +1, -I...,,, = =+|= II
Pa(es -
==
and we have
P(X n. , Xo) = = - E T;
Xo) = (X.,)
= Xn. =sp]
TET
since the events
Xo) }} do not intersect for different
First consider any intermediate state S {80.8) 84) and define Markov chain {Yr with the same transition probabilities as (x,) with Y, a.s. We define p, & P/an 0: Y, s), i.e. the probability that {Y,) returns to s. First, notice that ps < 1. Indeed, based assumptions on G. there exists at least one path from so to 8, and furthermore, there exists such path without cycles. In this case, we have
PI
Yo) = r| = II PB(s: s141) >0
00: by the condition on PB((1] (') > 0 for - s' E E. Notice that (I.,, Y)) = n 0: Y, =}} => 00 since the trajectory of the random walk has already reached Su, it will never return to s. Thus, p. = P > 0: Y, = =s] < 1.
Next, for each state s E S \ {sp. sy} we define N, & Die I[X, s} as the number of visits state encountered by the original process. Also, let us define N₁ A Eie I[Y; = 8} as the number of visits state s during the backward random walk that starts s. We notice that
E N.
= P(k > 0: X = 3) S ENN)
where the first equation is due to the strong Markov property. At the same time, we have P(N; > k] PP. ..... > 0: Yn, 8] and, by Markov property, we have P[N > ki p Thus
E
Σ km
P(N > k] = Σ
< +0c.
1 Ps
k= 0
Finally, we have
E [n,
Σ 1[Xx
#
=
Σ (
Σ k=
1{Xx = =}
=
Σ
[[NN <
Σ
E[N < +00.
(
(F.
The first statement of the Lemma directly follows from the finiteness of the expected length of the walk, because otherwise has an infinite length with non-zero probability, leading contradiction.
12

---

Revisiting Non-Acyclic GFlowNets in Diserete Environments
A.2. Proof of Proposition 3.6
First, we prove the flow matching conditions. We have
F(s =() E,
Σ 1s: 8, 8141 =
814111=87 =03
[s,
Er
1ss 8, 8,41 5 nt
1
Mr
n++
F(s) F(ss) E
Σ
Ifs, = tf F(ss))
E,
Σ
1s, = $s nt
Next, note that the following equations hold for any trajectory T and any s E
S
{so. $y):
1sa =}
Σ e'Ein(>)
1( = 8", =
Σ
11
84+1 6'}.
s'Eout(s)
Then for 8 E E {
ny
F(s) [ F(y))
Br
Σ
Σ
160-1= = 00
= = 14
t=1
8" (in))
+1+1
Σ
F(sy)
E
Σ
1| = s5 s} n4
F(s" + s).
<*Ein(s)
<"iinss)
Similarly for any s S 8 { {sy}:
F(s) = F(s))Bn
Er
Σ
= -
t= s'Eout(s)
Σ F(sy)Enr
E,
Ifst s, = nt
Σ s'Enu((s)
F(s - s').
(s))
Next, we prove the key relation F(s 5 = F(s')PB(s s').
We have
nr
F(s + =() F(s, En-
E,
Σ 1==0
I(s = -,, = =s'} | n2
= =Es
Ez [[(( = =8, 8,4111 = s'} 12
= Fmn
P(s = 8,41 = =6 =
(0) F(sy) En,
P(S1+1 =8 |n |P))P(s = 86+1
= =
Fn,
P(#+1 = 11 Pals 8')= =(s))Pss 15).
Here (a) we used the Markov property of trajectory distribution. Finally, by definition, F(so) is equal to, F(ss) multiplied by the expected number of times 7 visits sp, where the latter is always so we have F(so) = F(s,).
A.3. Proof of Proposition 3.7
Since F(s + +s) satisfies the flow matching conditions, we define
F(()
Σ
=(s
= Σ F(s" - s).
s' (s)
5 in(s)
13

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
Next, take PB(s| 8 F(s + + F)/((s)) Let denote f be flows from Definition 3.5 that induced by PB and F(sy) (which correspond to expected number of visits with respect to the trajectory distribution P innduced by PB). We aim to prove that F and f coincide.
By Proposition 3.6 and definition of PB. have
F(d') F(s')
F(s - 8') = =
F(s
where we denote C(s) = F(s) In addition, by Proposition 3.6, f satisfies the flow matching conditions, thus
F(s)
Σ
F(s
Σ
F(s" 8).
8f ('E))(())
in(s)
Combining these statements, for any S {sy} we have
-(s)=C())F())
E C(d)F(s+
s'Eout(s)
The first equation is by definition of (s)) and the second equation is due to the flow matching conditions. Thus we have system of linear equations with respect to C(s):
V& E S {8y).
Σ 8' (oout(s)
C( -()
In addition, F(sy) is equal to, by definition, F(sy) multiplied by the expected number of times 7 ~ P visits sy. where the latter is 1, so we have F(sy) F(sy), thus an additional equation is C(sy) In total, we have |S] variables and [S] equations, and are interested in strictly positive solutions. Firstly, there exists trivial solution C(s) for each E S, which is only constant solution since C'(s))= 1.
Next, suppose there exists a non-constant solution Cs(s.. Denote Smax = argmax,es C² which will be a proper subset of S. Let us consider two cases. First, suppose & Smax- Let = (8o + + - 8n, - +8) be any trajectory that visits some state in Smax. Then there exists an index S n, such that st Smax and 8t+1 & Smax. Then we have
Edccon((o)) O(s)F(ss + s') Excou((s)) C(s)) + 5)) Excou((o) F(st s') 1. ((st)
C(ss)F((s))
F(st)
The inequality is due to three facts: (i) C(s) 0 Vs E 8, (ii) 8 Smaxs and thus C(s.) 2 C(s') for any s' S, and (iii) the inequality is strict for at least one edge 8; - 1 such that C"(s1+1) (st),, and it implies contradiction.
Second, suppose sy E Smax- Then, denote Smin = argmin,es C'(s), which will be proper subset of S. Similarly to the previous case, let be any trajectory that visits some state Smin- Then there exists an index t S n, such that 8 E Smin and 8 & Smin- Then we have
Edcouu((r) F(s)) +6)) 5') Excoutss)) ((s))((st + +) Excoue(o)) F(st 5') C(s))((st)
F(s))
F((e)
Thus, in this case, there is also a contradiction. Therefore C(s) = is a unique solution, meaning that F(s) = =((s). Finally for any s + S'SES E
( + 8') F(s - 5o).
F and f coincide, thus the proposition is proven.
A.4. Proof of Proposition 3.8
Let us proof existence and uniqueness a corresponding forward policy. Let F be the flow induced by the backward policy (3.5).
14

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
Uniqueness. Suppose that such forward policy Pp exists, then probability distributions over 7 induced by PB and Pp coincide. Then
F(s + =
By
1ss = 8, 8,4111 = o8} nr
1=
dr
= =
B, [1[1 = 8, 8,41 2/7 nrl
1=0
n4
= F(s)))En,
Σ
P(s -8, 5,411 = nz))
1=
nr
= F(s
P(s = n, [,) =s 1s = s, m2)
1=0
Bhe
= F(ss))
Σ
P(s: = =
= PF(5' = =(()PPE(s 1s).
[=U
Then we have PBs 8) F(s)PE(s' s) and PF(s' = s))/((s), thus we finish the proof of uniqueness presented above.
Existence. Take
Pr(s' 8) F(s')P((s18)
F(s 88)
F(s)
F(s)
This is always a valid probability distribution since F(s) = -E F(s - s'). Next, for any T E T we have
the
thr F(st + 8441)
I[ F(si - s(41)
II PB((: St41)
II t=
F(s++1)
F(s+11)
t=
where the first equation due to Proposition 3.6. Next, note that
m,
F(so) = F(s)) E,
Σ 1=0
1ss = sot =o}
= F(s)) 1 F(s)).
Then
TT Flss 8(41) Ih F(s++1)
F(so) I1 F(ss s F(ss)
m F(s: - s6+1)
nhe
II Pp(5441 st).
Ih F(s))
1 F(st)
Thus the existence is proven. Finally, the detailed balance conditions follow from the proof of uniqueness.
A.5. Proof of Proposition 3.9
Consider an edge function F(s + = s). It is positive since F(s) > 0 and PF(s' (s) > 0 by the statement
of the proposition. Since Pp(. 8) is a valid probability distribution over out out(s). (s), we have
Σ F(s
Σ d'Eout(s)
F(s)Pa(s' (s) F(s)
Σ
Pe(s' (s) =s)=F(())
('Eou((s)
of Eo)t(s)
Similarly, since Pp(- 8) valid probability distribution over in(s), and F, PF and Pp. satisfy the detailed balance conditions, we have
Σ F(s" s)=
Σ
Σ F(s)PB(s" [s)=
Σ
Pe(s" 8) = F(s).
e'Ein(s)
Eii((s)
s"Ein(s)
e"Ein(s)
Thus f satisfies the flow matching conditions. In addition
F(s)Pr(s' 8) F(s F(8
+s) F(8) F(s)) Extein(or F(s" - 5.)
Pn(s1
15

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
Thus, applying Proposition 3.7 to F, get that it is edge flow induced by Pg. thus F is also the state flow induced by PB and F(sy).
Next, consider any trajectory
(Sp. $1, s1.... S 84) E ET..T. By the detailed balance conditions we have
F(s)) P( PF(st+1 8t)
F(so)
Pa(se 8141) Il t=0
II t=0
Pf(s
s II
Pr(5 1s)).
F(s++1)
F(sf)
t=0
==0
The final equation is due the fact that state flow F is induced by PB and F(sy), we have F(sy) F(so) by Proposition 3.6. Thus the proposition is proven.
A.6. Proof of Proposition 3.12
We first note that not including so and s in the sum is just matter of the definition of trajectory length presented in 2.1, where we do not count the first and the final state towards it. Using the fact that the length of trajectory is the sum of the numbers of visits to each individual state in the graph, we obtain that
#1+1
R-+1
F(s)
E, E,-p [n7] E,
Σ
Σ
Ifs, =s
Σ
E,
Σ 1=0
Ifst = 8)
E +EST(
F(ss)
t=0
A.7.
RL and Theorem 3.13
Background on Entropy-Regularized RL. Let,Mr be a deterministic MDP induced by a graph 9 with a state space corresponding to vertices of G, the action space Ag for each state s corresponds to outgoing edges of s, associated with (s), and let À > 0 be regularization coefficient. We define policy æ as a mapping from each state & to probability measure π (-|ss) over A..
Then, for any policy т, define the regularized value function for all + 8 as follows
Bhe Σ
(x(
EYNPS
E
r(st, 8441) + XH((T(-(s:)) so =
(13)
and VT (sy) = O, where is Shannon entropy, PT is a trajectory distribution induced by the following the policy æ: 8, ~ (-18)-1) for 2 and the starting state 8o is fixed as s (not to confused with the initial state G), and n,, is a length of trajectory defined as n, min ( k 2 0 sk+1 = sy). Overall, is not clear if the value function a well-defined function when discounting is used (7 = 1). We call this problem regularized shortest path problem, akin shortest path and stochastic shortest path problem (Bertsekas, 2012, Chapter 3). A policy n is called optimal if it maximizes V (so).
Lemma A.1. Assume that (i) graph satisfies Assumption 3.1 and (ii) for any S, Ay it holds r(s, s') I 0 and r(s,&) 8') = 0 if and only if in(s') Also, assume that for any optimal policy x² it holds B (1r] < +00.
Then, regularized shortest path problem admits a unique solution, and the value of its solution satisfies soft optimal Bellman equations
VT(a) & Alog
Σ exp ('Enu((s)
(14)
where the optimal policy can be derived as n* (als) x exp(1/A (s)
Proof. Let us define number visits of vertex & and an edge 8, 8' in G on a given trajectory as (= I
and n (s, ) = - L(s, s, St+1 = s'}. In the analogy with occupancy measures in RL, we employ the notation dt (s) A E, (s)] and d (s, s') è E, (s, for an expected number of visits. This definition also corresponds to the flow function the reversed graph (see Definition 3.5) with the "backward policy" æ. The condition on expected trajectory
16

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
length of optimal policies implies that consider only policies ग such that d= (s) +00 for any 8 E S {s0, 87). and, as result, d' (s, s') +00.
Next, we rewrite the value function in the initial state as follows
(50 = Σ E ((s, + +A ((()))(((()))))
*ES)(ss) s'Eout(s)
sES
Then, we notice that d' (x, = n (8'1))
dt (s) thus we can rewrite the value the following form
(su) E Σ (ss,)')(sss')
> E d= (s.ss') log d= (s s'Eni((s)
Σ d= (s.s'')
sES((a)) s'Ennt(s)
#ES E'Ent(())
R(d*)
As function of dd (s, s'), we see that the first term in the expression above is linear whereas the second one is relative conditional entropy (Neu et al., 2017) that is strongly concave. Given that the set of all admissible d' s') is polytope that is defined as family of negative functions that satisfies the flow matching conditions (see Proposition 3.6)
K. é d: 1
E d'sss'/=
E d'(s",s). 8'Eln(s)
d(so. = ('Euu(()o)
Σ
Σ d"Eln(sy)
d(s". sy) )1)
s'Eout(s)
where the flow and policy have one-to-one corresponds due to Proposition 3.7 in the reversed graph. Since the set K. is a polytope, optimization of V (so) over occupancy measures is a strictly convex problem and thus admits a unique solution d² that corresponds to unique policy x².
Before proving the optimal Bellman equations, we want to show that n² satisfies N² (s'[s) for any s S, s' out(s). To do it, we explore the gradients of the regularizer, using computations done in (Neu et al., 2017), Section A.4: (d"(e,")) log (s') (). In particular, it implies that as (Tslss) + 0, then Vv=+R(dd") + +oc, thus the optimal policy x² cannot satisfy T (s'[s) (s) 0 since it will violate the optimality conditions.
amia"
Next, we want to prove that the value of the optimal policy satisfies soft optimal Bellman equations. First, we notice that the usual Bellman equations still hold since n, is stopping time
(x(s, = r(s, 5 VX
(+)))=
(())))) + XH(((-1))) d'Eout(s)
Σ
with an additional initial condition V/ = 0, by the proprieties of conditional expectation. Let us consider a regularized policy improvement operation, defined
p(s')0((s,'') + + AHCOO) } exp (oottox00))) n' (-1s) A arg ('Eou((s)
Σ
Then we want to show that V (so) 2 (so) if the policy is positive: =(s'ss) 0 all S, s' E out(s). We start from general inequality that holds for any s E
V (s) - (s)
Σ
H's'(s) (s, + XH((T(--ss)
Σ (()1s))0((ss))++ +
d'Eout(e)
e'Eout(e)
Σ ())n)(()
(s, x
Σ {( + of (x)t)())
Σ
x'(8)1s)(((ss (-((7((-15)
Σ ((s)s) XH((T((1s)) +
('Eout(s)
8' (our(())
> Σ
<(s'ss) - = Σ
<'
(5') - (5
s*Eout(s)
e'Eout(s)
17

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
After rollouts, have
(50 (5o) (50) 2 Pyp V (5))
Since the policy is positive, then Lemma 3.4 in the reversed graph implies that d' ('),)))))))))) (s) too and thus all values and Q-values are finite: (*(s, > -o for any E S, E (u)(s). It implies that x' is also positive. Thus, its trajectories are finite with probability and yields V (so) 2 (su). Finally, applying policy improvement to 'T we conclude the statement.
Proof of Theorem 3.13. Let P be the trajectory distribution induced by the GelowNet backward policy and P7 be the trajectory distribution induced by RL policy и. Then we rewrite the value function (13) in the following form using the tower property of conditional expectation to replace entropy with negative logarithm of the policy
V (50) = E
Σ r(s;, St41) log (5 sc)
Notice that there is no coefficient in front of entropy and reward because we set y = 1, A = by the theorem statement. Using simple algebraic manipulations
I (xpp((((,, I π (5 82)
( = ET log exp(r(st, 8411) - log (8++1 st) = =Erupy log
Next, we notice that r(s, 8') log (s)())') for all non-terminal s' and, r(8,85) = -log R(s) = log Pn 188) + log 2 for terminal transitions due to the reward matching condition. Thus,
I (8 st)
(50) log 2 E. log
log Z - KL(PT
I PB(st stt1)
Here is trajectory distribution induced by PB (7). We note that the final equation is the same as the one in Proposition 1 of (Tiapkin et al., 2024) for the acyelic case.
Thus, an optimal policy n' that maximizes (sa) is the one that minimizes (IPPP By Lemma 3.4, the expected trajectory length of any optimal policy x² that matches P is finite. Thus, by Proposition 3.8, there exists a unique forward policy Pp that induces the same trajectory distribution as Pp. which is equivalent to achieving zero KL-divergence. Thus, x* coincides with Pp. and we conclude the statement by the uniqueness of the solution (see Lemma A. To apply Lemma A. without loss of generality, we can assume that the GFlowNet reward function R is normalized, i.e., = and log R(xx) Indeed, since a terminating transition + sf always visited exactly once, is equivalent subtracting log Z from all terminal rewards, which does not change the optimal policy and modifies all values by the same constant.
Next, consider soft optimal Bellman equations (14) for non-terminating transitions
s') = log PB(s 80) + log s'Eout(s')
Σ
exp(Qi=1(6',"))
Let us show that Qi= (8, = log F(s +') s') will satisfy the equations.
los + 5') = log F(5') + log Pa(s 8') log
Σ
F(s' - -5") + log Pa(s ss)
e"Eout(e")
log PB(5 5') log
Σ
exp(log F(s' + 8")).
s ('Euu((s")
Here we used equations from Proposition 3.6. For terminating transitions we simply have (s, = r(8, = log R(s) = log F(s + sy). Since there exists unique solution to soft optimal Bellman equations, we have proven ( = log F(s + s'). As for state flows, we have
V (8) = log
Σ (s, = log s e'Eot)())
Σ
exp(log F(s + +s)) = log F(s).
8' ('Eo
Thus the proof is concluded.
18

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
B. Algorithmic Details
B.1. Training Policy and Flow Weighting
Recall the optimization problem in (11):
Σ F(s)
min F P
#ESt(ED.er}
log F(s)Pr(s' s) 2
subject to
= 0, P(s')PB(s (
Y8 -
((()s)) = R(x).
Va 438
Now, suppose that training with DB loss (4) and state flow regularization (12) done on on-policy, i.e. trajectories are collected using the trained policy Pp. Let write down the expected gradient of the loss summed over trajectory (note that regularization is not applied F(so) and F(sy))
log Fo(s)Pp($141 se, 0)
2
E PF
vo
+
A
AaFFll)
Fo( (Pt 18+1,0) 0)
1=0
1=1
which can be rewritten as
nx
Ep
VOLDB(S + s(+1) + AE
Σ
VeFo(s))
The first term is the expected gradient of the standard DB loss. As for the second term, note that if Fo is exactly the state flow induced by Pp, we have
ENTPP
Σ VoFo(s))
= ETNPY
Σ
=
=
(
1=0
nr Σ
VoFo(s) Lyyp)
115t =}
#ESi(Eneer}
1=0
Fo(s) voFo(s) = 2Fo(88)
1
Vo
Σ
Fo(s)2
Fo(sg) <ES((50=>7)
(
This implies that on-policy training tries to minimize the sum of squared state flows rather than the sum of state flows. This happens due to the fact that the trajectory distribution that is used to collect data for training (induced by Pp in this case) visits certain states more often than others, thus a weight is given to the flow in each state equal to the expected number of visits. However, if (s(s 80) fixed to uniform over \ {80, 8 (see Section and Appendix B.3), this issue can be circumvented by applying the flow regularizer only in the first state of each sampled trajectory. Then, equal weight will be given to (s) in each state in the expected loss, thus will be minimizing the of state flows. However, in experiments we noticed that this does not significantly influence the results, we leave exploring this phenomenon as further research direction.
B.2, Loss Scaling and Stability
In this section, provide a more detailed explanation of our scaling hypothesis (see Section 4). Let consider GFlowNet that learns F, Pp and Pg- Since these quantities are predicted by a neural network, standard way is to make it predict logits for the forward policy, logits for the backward policy, and the logarithm of the state flow. Flow functions are always positive, thus, predicting them in log scale is a natural approach (Bengio et al., 2021; 2023). Then, for any transition s - s' define two quantities:
AlggF(s. 800) A log Fo(s) + log (s 0) log Fo(s)) log PB(s)s',0)
(15)
A (s, 8', exp(log Fo(s) + log Pe (s'(ss,))) exp(log + log Pa(s|s',0)
19

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
20
10
DB,
SDB,
DB, AlogF
8
SDB, Alog
15
L(log F.g..11 111
Lllog 1)
10
5
2-
0
-5
10
-10
5
log
log
Figure Plots for DB and SDB losses in AJ and log F scales with fixed predicted log backward flow and varying predicted log forward flow. More specifically, green curve y (x 1)?, red curve is y (e" e²)² brown curve is y log + (x 1) 0.001e"), blue curve y = log [ + (c" - =+)))) (1 0.001c
The first is the difference between the predicted logarithms of the flows in the forward and backward direction log FF. log FB. while the second is the difference between predicted flows in the forward and backward direction Fr FB. Then, the standard DB loss (4) is
Lna(s + 8') = Alog F88,6'
and the SDB loss (4) proposed (Brunswic et al., 2024) is
(sus(s - - = (e, 0))) (1 *Fo()))
However, for both losses, one can either replace Alog F with A or the other way around. For visualization, let us fix the predicted log backward flow FB be, e.g., 1, and plot the losses with respect to the varying value of the predicted log forward flow Fy. The plots are presented in Figure 3. One note that argument log Fp decreases, both losses in A scale quickly plateau, thus their derivative goes zero. From the optimization perspective, this means that when the predicted log flow needs to be increased, the gradient step will be very small since the derivative of the loss is almost zero. On the other hand, when the predicted log flow needs to be decreased, the gradient step will be larger since losses have much higher derivatives in the corresponding regions. In combination with Proposition 3.12, this gives a possible explanation to the stability of A scale losses: they are biased towards underestimation of the flows and, as a result, biased towards solutions with smaller expected trajectory length. We note that the same reasoning can be applied to the stable flow matching loss proposed in (Brunswic al., 2024) since it also operates with differences between flows in A scale.
However, as we show in our experimental evaluation (Section 4), this comes at the cost of learning GFlowNets that match the reward distribution less accurately.
B.3. Fixed PB and Trainable PB
In non-acyclic environments, Sp and sy generally are fictive states that do not correspond to any object. Then Pr(sy corresponds to the probability to terminate a trajectory in state s, while Pp(s so) corresponds to the probability that a trajectory starts in the state s. Thus, the choice (so) is crucial in the design of the environment. this set is large, e.g.. coincides with intractable. However, in this case PB(S0 s) has to be trainable, otherwise, it may be impossible satisfy the detailed balance conditions for transitions 5o s.
{so, 8y), one has to fix Pr(s sn) to some distribution, e.g. uniform, otherwise learning becomes
In our experiments, we consider two settings: training with a fixed Pn and using trainable Pn.
In case of fixed Pg. we consider the case when out(sp) ) = [smitt) where Sinit is some fixed state E S $50, Thus the first transition for all trajectories is to go from Sp to Sinit- Then, for any s E S {so- 8,, Siitt Pr. (- 8) is uniform over the parents of s, while PB(s) smit) = 1 - for some small E > and PB(s siiit) = e/(in(s sma) - 1) for other transitions
Sinit
20

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
For trainable PB. we consider the case when out(su) 8 \ {50,8y) Here we fix the first forward transition probability Pr(s| 8o) to be uniform over S (so, 85). . In this case, Da loss for the first transition takes special form:
Coa + +) - log Zq - -oo--og11 {so, sy - log PB(50 s, - log Fa(s)
(16)
where log 2g - log |S \\ (fo.s}} corresponds to log (so) + log Pp(s so). An important note is that log Fa( for optimal solutions always coincides with log 2; thus, usually harmful apply state flow regularization (12) to it.
B.4. Solving Small Environments Exactly
Suppose we have a fixed backward policy Pg and a final flow F(sy). Then, induced flows F and the corresponding forward policy Pp can obtained exactly for small environments. Consider the following system of linear equations with respect to F(s) that arises from Proposition 3.6:
F(b) Excon((s) (a(s18)((6)) As E
(17)
F(0)) =F(s)).
The system has |S] variables and |S] equations. F(s) = F(s) is solution, where F(s) are state flows induced by PB and F(s)), and the uniqueness of the solution follows from Proposition 3.7. Thus, by solving the system, one can exactly find induced state flows. Then, by Proposition 3.6 and Proposition 3.8, edge flows and Pp. can also be exactly expressed as
- = Ps( ds)(''), PF(8' {8 = (n(8 ()F(())F(())
Finally, by Corollary 3.12, one can find the expected trajectory length of the induced trajectory distribution P as:
[n=]
Σ
F(s).
F(8f) (ES)(50:35)
Interestingly, the system (17) also be explained from the Markov Chain perspective. Let take the graph with reversed edges, add a loop from 8o to itself, and use PB to define Markov Chain with the following transition matrix: P(so | sa) 1, P(s | s') PB(s s') if there is an edge + 8', and P(s | s') = 0 otherwise. It will be an absorbing Markov Chain, with an only absorbing state so since it is reachable from any other state by Assumption 3.1. The transition matrix can written in the following way:
Q
R 1
P
where Q is a [ by |S] matrix and R is (S| 1 by matrix. Its fundamental matrix N, i.e., such matrix that Ns.e' is equal to the expected number of visits non-absorbing state s' before being absorbed when starting from non-absorbing state 8, can be obtained as:
N = (1-=11-))
k=
where I - Q is always invertible (Kemeny& & Snell, 1969, Theorem 3.2.1). One can note that normalized flows F(s)/F(s)) coincide with the expected number of visits to when starting from 8y, thus coincide with the row of matrix N corresponding to sy. Finally, notice that (I Q) coincides with the transposed matrix of the truncated system (17) (with the exception of the variable and the equation corresponding to sp), thus, such system has a unique solution (T=))(T-Q) ()--i---eeee eee, = F(s,) N esy- where Cay is a vector of size [S] - that has 1 on the position corresponding to sy and 0 on all others. The variable corresponding to so should be handled separately, but it is easy to see F(so) = Ee PB(s ss)F((s') F(so).
C. Experimental Details
C.1. Loss Choice
While (Brunswic et al., 2024) used the original flow matching loss (Bengio et al., 2021) for experimental evaluation, it was previously shown to less computationally efficient and provide slower convergence than other GFlowNet losses (Malkin
21

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
al., 2023; Madan al., 2023) in the acyclic case, so we carry out experimental evaluation with the more broadly employed detailed balance loss (Bengio al., 2023). Moreover, flow matching loss does not admit explicit parameterization of backward policy, as well as training with fixed backward policies, thus not allowing to study some of the phenomena we explore in the experiments.
In addition, we note that the proposed state flow regularization (12) can be potentially applied with other GFlowNet losses that learn flows, e.g. SubTB (Madan et al., 2023), or with the modification of DB proposed in (Deleu et al., 2022) that implicitly parametrizes flows as F(s) = RR(s) s).
C.2. Hypergrids
Formally, S\ {so, fy} is a set of points with integer coordinates inside a D-dimensional hypercube with side length H:
{(s'..... | {0, (0....... H - 1}}. - Sy and s are auxiliary states that do not correspond to any point inside the grid. Possible transitions correspond increasing or decreasing any coordinate by without exiting the grid. In addition, for each state E (80, 8y) there is a terminating transition s - 8y. GFlowNet reward at (s ,.,,,, sD is defined
8²
D < H
8¹
R(s) - Ro + R1
II
T 0.25
<
0.5
+ RR
II
0.3
0.5 < 0.4
H -
where 0 < Ro < R₁= < Rg. (Brunswic et al., 2024) do not specify reward parameters used in their experiments, so we use the parameters from the acyclic version of the environment studied in (Malkin et al., 2022), i.e. (Ro 1003 R1 0.5, R2= = 2.0).
The utilized metric is:
Σ TEX
R(x)/2 (xx),
2
where T (z) is the empirical distribution of last 2 10 samples seen in training (endpoints of trajectories sampled from Pp).
All models are parameterized by MLP with 2 hidden layers and 256 hidden size, which accept a one-hot encoding of as input. Fo (s), (s s, 0), (s s', 0) share the same backbone, with different linear heads predicting the logarithm of the state flow, the logits of the forward policy and the logits of the backward policy. In the case of the fixed PB. Sinit corresponds to the center of the grid, and we take E = 10 (see Appendix B.3).
We train all models on-policy. We use Adam optimizer with a learning rate of 10-3 and a batch size of 16 (number of trajectories sampled at each training step). For log Z, we use larger learning rate of 10-2 (see (Malkin et al., 2022)). All models are trained until 2 10th trajectories are sampled, and the empirical sample distribution T(x) computed over the last 2- 10a samples seen in training. For SDB we set & 1.0 and r) 10-3 3. We found that using larger values of can lead to smaller expected trajectory length, but also significantly interfere with the sampling fidelity of the learned GFlowNet, thus we opt for these values in our experiments.
C.3. Permutations
All models are parameterized by MLP with 2 hidden layers and 128 hidden size, which accept one-hot encoding of s as input. Fo (s), Pr((' s. 8), (T.(s s', share the same backbone, with different linear heads predicting the logarithm of the state flow, the logits of the forward policy and the logits of the backward policy. In the case of the fixed PB, Sinit corresponds to the permutation (n, n - 1, 1,...,,, 1), and we take E = 10-8 (see Appendix B.3).
We train all models on-policy. We use Adam optimizer with a learning rate of 10-3 and a batch size of 512 (number of trajectories sampled at each training step). We found that using small batch sizes can significantly hinder training stability for this environment; thus, we opt for larger value. All models are trained for 109 iterations. For log Z, we use larger learning rate of 10-2 (see (Malkin et al., 2022)). To compute A log Z we take the average value of log Zn over the last 10 training checkpoints. Empirical distribution ((k) is computed over the last 10 samples seen in training. For SDB we set = 1.0 and 7 = 10-3, We found that using larger values of can lead to smaller expected trajectory length, but also significantly interfere with the sampling fidelity of the learned GFlowNet, thus we opt for these values in our experiments.
Suppose that T1, Fm is set of GFlow Net samples (terminal states of trajectories sampled from Pp). Then, the empirical
22

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
L1 error of fixed point probabilities is defined as:
((k) Σ
(k) = k}
k= 1=1
and the relative error of mean reward is defined
[[R(2)) Ei= R(zi)
[[((r)
where [[[(x)] = ExEx R(x) R(x)
We compute mean reward over 10 samples.
2
C.3.1. REWARD DISTRIBUTION PROPERTIES
We define the GFlowNet reward as R(s) quantities:
m(s(k) k}). We are interested in the true values of three
1. normalizing constant 2 2= R(x),
2. true expected reward [B[[(x)] = EnEx R(x) R(x) 2 2
3. fixed point probabilities C(k) P = =]) k) with respect to the reward distribution.
While computing sums over all permutations is intractable for above some threshold, below, we show that for this particular reward, analytical expressions for these quantities can be derived.
First, we will derive the formula for the total number of permutations length n with exactly fixed points, which we will denote as ( n). In combinatorics, such permutations are known as partial derangements, and the quantity is known as rencontres numbers (Comtet, 1974, p. 18)). Note that
11 (2) D(0, |(0, - k).
D n)
since choosing permutation with i fixed points coincides with choosing i positions for fixed points, and permuting the remaining elements such that there are fixed points among them. So let us start with the derivation of D n). Denote S; to be the set of permutations on n elements that has fixed point on position i. Then, by the mecluson--xxllssin principle, we have
SS U...U...
Σ St1
Σ icj
Ssns +
Σ Kijc
ns
n + +...+ (-1)n+1|S) [S1 C... Sal
n
n
(n 3)! + (-1) n2 0!
(n 1)! -
(n - 2) +
2
1) n! n
(-1)st1
Σ 111
Then
11))++1
n
(-1)
D)0.n) n! 1-1-11 111 U... US nl n2.
n!
i!
i!
Thus, we have
D(k,n) = (1) (m) D(0, n - k)= = kl(n k:)!
n!
a-k (-1)²
k (-1)t
(n - k))
n!
1=0 i!
ilk!
Finally, all of the quantities we are interested in are easily expressed through D(k, n):
1. - - D(k, n) cxp(k/
2. E[R(z)] = Eizo
k= D(k, n)) (xp(k/2) exp(k/2)
3. C(k) = D(k, n) exp(k/2)
For reference, the formula yields values of log 2 3.8262, 11.2533, 42.9843 for n 4, 8, and n 20 respectively.
23

---

Revisiting Non-Acyclic GFlowNets in Discrete Environments
D. Additional Plots
hypergrid 20x20x20x20
hypergrid 20x20x20x20
10"
4000
Alog
3500
SDB, Alog
D0, A
full empirical L error
mean trajectory length
3000
A. 0.001
2500
2000
DB, AlogF
500, dlog
1500
F. A
1000
SD8, Alog 0.001
true expected error
0
10a
10a
10
10a
10a
10
training trajectories
training trajectories
Figure 4. Left: evolution of L distance between empirical distribution of samples and target distribution. Right: evolution of mean length of sampled trajectories. Here we note that when A log F scale losses are employed without state flow regularization, mean trajectory length tends infinity. Plots are not full since training is done on-policy. Thus, the time needed for full training also grows according the length of trajectories.
hypergrid 20x20x20x20
hypergrid 20x20x20x20
10"
DB, Alog
D6, Alog ==
400
DR, Alog 0.000
full empitical L error
tra trajectory length
DB, Aloo 0,0001
300
D8, F. 0.1
teantra
200
DB, =
=00001
Nog 0.0001
100
true expected error
10-1
104
105
10
104
10a
10f
training trajectories
training trajectories
Figure 5. Left: evolution of L distance between empirical distribution of samples and target distribution. Right: evolution of length of sampled trajectories. Here, we see the effects of state flow regularization of different strength X. Larger values of A lead to smaller mean trajectory length, however, if À is large, the obtained forward policy will he significantly biased.
permutations of length
permutations of length 4
109
mean trajectory temgth
SDB, aF, Fg
10-1
20-
$26, M. train
C(K) empirical
D8, AlogF, train Ps
Mven
15
F. 0,001, Pg
10-2
trae espected emro/ / fised P.
10-
10-3
10a
10
10
10c
102
training trajectories
training trajectories
Figure 6. Comparison of non-acyclic GFlowNet training losses on a small permutation environment. Left: evolution Lı distance between true and empirical distribution of fixed point probabilities C(k). Right: evolution of mean length of sampled trajectories. The results are similar to the same experiment on hypergrids (Figure I), with the only difference that here SDB loss in AJ scale here has fast convergence with trainable backward policy.
24


Reviews:
[{"review_id": "4388CZ5wyW", "reviewer": "Reviewer_Mo9C", "summary": "This paper revisits the theoretical framework of Generative Flow Networks (GFlowNets) in non-acyclic discrete environments, where the traditional assumption of acyclicity is relaxed. The authors propose a simplified and more intuitive formulation of non-acyclic GFlowNets that extends prior work by Brunswic et al. (2024). The contributions of the paper include:\n\n- A more straightforward theory for non-acyclic GFlowNets, avoiding more complex measure-theoretical framing for discrete state-space contexts. Furthermore, the theory explores the connection between Entropy-regularized RL and GFlowNets, extending previously known results to the non-acyclic setting. \n- Refining the understanding of loss stability and convergence:\n  - Challenging the need for modified stable losses when the backward policy (PB) is fixed.\n  - It proves that when PB is trainable, minimizing the expected trajectory length is equivalent to minimizing the total flow.\n  - Introducing state flow regularization as a means to stabilize non-acyclic GFlowNet training.\n- Meaningful empirical results validate the theory and explore an interesting question regarding the scaling effects of loss functions and trajectory length control (log-scale errors impact expected trajectory length).\n\nOverall, the paper combines key novel theoretical results and simplifies previous results with a combination of theoretical and empirically grounded work.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to express our gratitude to the reviewer for the very detailed review and valuable suggestions. We are pleased that the reviewer acknowledged the contributions of our paper, novelty and soundness of our theoretical results, as well as the strengths of our experimental design.\n\nRegarding the weakness outlined by the reviewer (and question 4), we agree that the motivation and applicability of non-acyclic GFlowNets are crucial points. In addition to possible ideas related to Bayesian networks and graphical models mentioned by the reviewer, below we present a number of potential use cases that seem highly relevant from our perspective. While some of them are mentioned in the introduction of our paper, we recognize that putting more emphasis on this will further strengthen the presentation and motivation of our work.\n\n1. One example, which was also discussed in [1], is related to modeling distributions over objects with intrinsic symmetries. Consider a class of environments where states are elements of some group, and transitions are given via a generating set of this group, thus corresponding to applying the group operation on the current state and some element of the generating set. An example is an environment induced by Rubik’s cube, where states are possible arrangements of a Rubik’s cube, and actions correspond to rotating a face of a cube. Another one is the permutation task studied in our paper (Section 4.3). While in some cases an acyclic environment can be designed to generate group elements, such environments of “algebraic” origin naturally contain cycles, thus falling under the area of our study.\n2. Next example is related to potential use cases of GFlowNets where one is more interested not in the objects sampled from the reward distribution, but in the trained policy itself. One can consider RL environments where the reward is sparse and given only at the end of a trajectory, but similarly to GFlowNets formulate a problem of finding a policy that will end up in terminal states with probabilities proportional to the exponent of the reward, thus promoting diversity and exploration. Most RL environments contain cycles, and the GFlowNet environments considered in our work are almost arbitrary finite discrete deterministic MDPs with sparse rewards. Thus, our work makes another step towards bridging two research fields. Moreover, the approach presented in our work aims at finding a policy with the smallest expected trajectory length, which may be of additional interest in RL applications.\n3. One can consider regular acyclic environments where GFlowNets are utilized, e.g. molecular graph generation environments, but introduce an option to remove some part of the current object during generation, not only add new parts, leading to cycles in the environment. A possible intuition behind this design choice is allowing the model to correct “mistakes” it can potentially make in the generation process, thus leading to a more expressive class of policies. \n\nNext, while we do cite some of the references mentioned by the reviewer, we agree that including a more active discussion in the paper on connections to previous GFlowNet literature will help further contextualize our contributions. We thank the reviewer for the suggestion and the proposed references, and will incorporate them in a revision of our paper.\n\nFinally, we highly appreciate the detailed questions from the reviewer and are happy to answer them. Firstly, we note that the proposed state flow regularization could indeed be potentially applied with different divergence-based objectives. The applicability of the proposed regularization depends on the utilized parameterization of a GFlowNet rather than the exact divergence used to compute the loss. The parameterization has to include the state (or edge) flow, so our regularization cannot be applied with trajectory-level losses that only involve learning $P_F$ and $P_B$, but can be applied with transition and sub-trajectory level losses that also include learning of the flows. Secondly, stable losses in [1] were also derived from specific $f$-divergences, so the analysis of [2] could indeed be potentially extended to explain exploration vs exploitation trade-offs in non-acyclic GFlowNets, as well as provide a deeper theoretical analysis of our scaling hypothesis. Finally, we believe that there should be no issue in applying the FCS metric in the non-acyclic case, as Equation 8 from [3] still holds for our construction. In addition, extending the analysis of [3] on propagation of errors in flow networks to the non-acyclic case will be a non-trivial task, thus posing another interesting direction for future research.\n\nReferences:\\\n[1] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024\\\n[2] Hu et al. Beyond Squared Error: Exploring Loss Design for Enhanced Training of Generative Flow Networks. ICLR 2025\\\n[3] Silva et al. When do GFlowNets learn the right distribution? ICLR 2025", "claims_and_evidence": "| **Claim** | **Evidence** |\n| --- | --- |\n| Non-acyclic GFlowNets can be formulated with a simpler and more intuitive framework than prior work. | The authors introduce a discrete-state formulation, avoiding measure-theoretic complexity. |\n| A fixed backward policy removes the need for loss stability conditions. | Theoretical results and empirical evaluations show that standard training remains stable under a fixed PB. |\n| When PB is trainable, minimizing expected trajectory length is equivalent to minimizing total flow. | The authors prove this equivalence mathematically. |\n| ∆F and ∆logF losses effects on trajectory length | Experiments show that ∆F and ∆logF losses estimated trajectory length and metrics. |\n| GFlowNets in non-acyclic environments are equivalent to entropy-regularized RL. | A generalization of Tiapkin et al. (2024) proves this connection formally. |", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria align well with the problem of training non-acyclic GFlowNets. The authors use well-established benchmark datasets, such as hypergrid and permutation-based environments, appropriate for validating their theoretical claims. The evaluation setup effectively tests the impact of different loss functions, backward policies, and flow stability in non-acyclic settings.  \n\nHowever, additional experiments on larger-scale, real-world applications (e.g., molecule generation, Bayesian structure learning) would further strengthen the paper’s empirical contributions.", "theoretical_claims": "Yes, the theoretical claims were checked, and the proofs appear correct.  \n\nThe paper provides a well-structured derivation of non-acyclic GFlowNet, proving key results related to trajectory length minimization, state flow regularization, and equivalence to entropy-regularized RL. The mathematical arguments are logically consistent and align with prior GFlowNet research.  \n\nThe results are a meaningful extension of Brunswic et al. (2024) and Tiapkin et al. (2024), and I did not find any critical flaws in the derivations.", "experimental_designs_or_analyses": "The paper presents well-structured experiments evaluating the impact of different loss functions, backward policies, and trajectory length control in non-acyclic GFlowNets. The chosen environments (hyper grid and permutation-based tasks) are standard benchmarks for testing GFlowNet behavior, and the experiments effectively highlight the role of loss stability, scaling effects, and state flow regularization.  \n\nKey strengths of the experimental design:  \n- Controlled comparisons between different loss formulations (∆F vs. ∆logF).  \n- Analysis of trajectory length effects, demonstrating how different regularization methods impact stability.  \n- Clear ablations on the role of the backward policy (fixed vs. trainable).  \n\nHowever, the paper lacks experiments on larger, real-world applications. Overall, the experimental design is well-motivated and supports the theoretical claims, but further empirical validation on complex, real-world tasks would make the findings more compelling.", "relation_to_broader_scientific_literature": "The paper simplifies and expands on two key previous theoretical results for GFlowNet, particularly the theory of non-acyclic GFlowNets and the connection with entropy-regularized RL. It expands ideas on the role of fixed and trained backward policy in the stability of GFlowNet training in this context and provides broad empirical evidence. It has the potential to clarify existing practices and provide theoretical grounding for algorithmic design.", "essential_references_not_discussed": "The paper provides a strong theoretical foundation for non-acyclic GFlowNets. Still, it could further contextualize its contributions within recent advances in backward training, generalized training strategies, and correctness of learned distributions.\n\n1. Backward Training in GFlowNets  \nGiven that the paper investigates the role of PB in non-acyclic formulations, discussing these approaches would strengthen its connection to existing literature:\n  - *Pessimistic Backward Policy for GFlowNets* (Jang et al., NeurIPS 2024) i\n  - *Looking Backward: Retrospective Backward Synthesis for Goal-Conditioned GFlowNets* (He et al.) \n  - *Optimizing Backward Policies via Trajectory Likelihood Maximization* (Gritsaev et al.) \n\n2. Generalized Training Strategies and Divergence Losses  \nBeyond standard log-squared losses, recent works explore alternative loss functions for GFlowNets:\n  - *Beyond Squared Error: Exploring Loss Design for Enhanced Training of Generative Flow Networks* (Hu et al., ICLR 2025) \n  - *On Divergence Measures for Training GFlowNets* (Silva et al., NeurIPS 2024) \n\n3. Correctness of Learned Distributions  \n  - *When do GFlowNets learn the right distribution?* (Silva et al., ICLR 2025) examines the stability of GFlowNets under balance violations and introduces the Flow Conservation Score (FCS) metric.", "other_strengths_and_weaknesses": "In my view, the main weakness is that non-acyclic GFlowNets are not well motivated. The reader unfamiliar with GFlowNets literature might see this as simply theoretical details of the theory. Connecting these ideas to broader ideas in ML and probabilistic models, particularly issues regarding inference and representational power of graphical models with and without cycles (e.g. Bayesian Nets, Markov Random Fields; Loopy BP, Bethe Approximation) could give a better context to why care about cycles. \n\nOverall, I find this paper interesting and insightful for generative modeling researchers, introducing simpler and more intuitive theory for non-acyclic GFlowNets.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Impact of non-acyclic formulation on generalized divergence training\n   - Recent works [1,2] have explored training using f-divergence objectives, including variance reduction techniques, expanding the connection with variational inference. \n   - How does the non-acyclic formulation impact variance reduction techniques for divergence-based training?  \n   - Could state flow regularization interact with generalized divergence-based objectives, such as f-divergences, in an on-policy setting?  \n\n2. Effect of log-scale errors on generalized loss functions\n   - The paper presents insights into loss scaling in non-acyclic GFlowNets, for example, showing that ∆logF losses require flow regularization.  \n   - Recent studies [2] suggest that different loss functions correspond to different divergence measures, affecting *exploration vs. exploitation trade-offs*.  \n   - Could the results on *log-scale loss* guide designing *alternative divergence-based losses* beyond squared error?  \n\n3. Correct distributional learning:\n   - Recently, the stability of GFlowNet to minor flow errors has been studied, and a flow consistency in sub-graphs (FCS) [3] metric has been proposed to evaluate whether GFlowNets genuinely learn the correct distribution.  \n   - Does the non-acyclic formulation lead to systematic balance violations in some settings?\n   - How could the FCS metric (or similar ideas of distributional consistency for subgraphs) be applied to evaluate non-acyclic GFlowNets?\n\n4. From a practical point of view, why would someone choose to use a non-acyclic formulation of GFlowNet rather than the acyclic one, given that a large enough acyclic state graph could represent most distributions of interest? \n\nThese questions aim to clarify how the proposed non-acyclic formulation interacts with a wider variety of training strategies (generalized divergences, variance reduction), the theoretical aspects of distributional correctness in GFlowNets, and the practical implications of this formulation. \n\nReferences:\n[1] Silva et al. On Divergence Measures for Training GFlowNets. NeurIPS 2024. \n[2] Hu et al.. Beyond Squared Error: Exploring Loss Design for Enhanced Training of Generative Flow Networks. ICLR 2025. \n[3] Silva et al. When do GFlowNets learn the right distribution? ICLR 2025.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RT4PgquHbV", "reviewer": "Reviewer_c5qu", "summary": "This paper offers a new perspective on the theory of GFlowNets in the cas where the state space is no longer acyclic. The author analyzed an existing theory of non-acyclic GFlowNets and provide insights as to when their proposed approach is necessary, and show that under an appropriate regularization, all existing losses used in the GFlowNet literature transfer (which were exclusively derived for acyclic state spaces) to the non-acyclic case.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their constructive feedback and valuable suggestions, and are happy to provide further details.\n\nFirstly, we thank the reviewer for the provided reference to [1]. While Proposition 4.1.3 does not state minimality of the expected trajectory length of the solution, it does indeed present a similar constrained optimization problem to the one introduced in Eq. 11 in our work.\n\nSecondly, we agree with the comments and suggestions regarding the formulation of the reward matching condition, and thank the reviewer for pointing out typos and inconsistencies related to it. We note that depending on the adopted structure of the environment in acyclic GFlowNet construction, reward matching can be formulated differently. If terminal states in the graph have no outgoing edges and their set coincides with the target space of interest $X$, the reward matching condition is formulated as $F(x) = R(x)$, e.g., see [2]. However, if one considers the graph structure with a sink state $s_f$, which is the construction adopted in our work, and terminating transitions $x \\to s_f$ indicate the end of the trajectory (rather than reaching a terminal state), the reward matching condition has to be formulated as $F(x \\to s_f) = R(x)$ because the state $x$ can both happen to be in the middle or in the end of a trajectory. In this case, $P(\\tau \\mid x \\in \\tau)$ indeed is not the terminating state distribution, as pointed out by the reviewer. We will incorporate the suggested fixes in the revision of our paper.\n\nFinally, we agree that the applicability of non-acyclic GFlowNets is a crucial question. There are several examples of such applications mentioned in the introduction of our paper, but we recognize that putting more emphasis on them will further strengthen the presentation and motivation of our work, and we will gladly incorporate this in the paper. Below we provide a more detailed discussion of some examples:\n\n1. One example, which was also discussed in [3], is related to modeling distributions over objects with intrinsic symmetries. Consider a class of environments where states are elements of some group, and transitions are given via a generating set of this group, thus corresponding to applying the group operation on the current state and some element of the generating set. An example is an environment induced by Rubik’s cube, where states are possible arrangements of a Rubik’s cube, and actions correspond to rotating a face of a cube. Another one is the permutation task studied in our paper (Section 4.3). While in some cases an acyclic environment can be designed to generate group elements, such environments of “algebraic” origin naturally contain cycles, thus falling under the area of our study.\n2. Next example is related to potential use cases of GFlowNets where one is more interested not in the objects sampled from the reward distribution, but in the trained policy itself. One can consider RL environments where the reward is sparse and given only at the end of a trajectory, but similarly to GFlowNets formulate a problem of finding a policy that will end up in terminal states with probabilities proportional to the exponent of the reward, thus promoting diversity and exploration. Most RL environments contain cycles, and the GFlowNet environments considered in our work are almost arbitrary finite discrete deterministic MDPs with sparse rewards. Thus, our work makes another step towards bridging two research fields. Moreover, the approach presented in our work aims at finding a policy with the smallest expected trajectory length, which may be of additional interest in RL applications.\n3. Finally, one can consider regular acyclic environments where GFlowNets are utilized, e.g. molecular graph generation environments, but introduce an option to remove some part of the current object during generation, not only add new parts, leading to cycles in the environment. This idea is also briefly mentioned in [1]. A possible intuition behind this design choice is allowing the model to correct “mistakes” it can potentially make in the generation process, thus leading to a more expressive class of policies. \n\nReferences:\\\n[1] Tristan Deleu. Generative Flow Networks: Theory and Applications to Structure Learning. 2025\\\n[2] Malkin et al. Trajectory balance: Improved credit assignment in GFlowNets. NeurIPS 2022\\\n[3] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024", "claims_and_evidence": "Claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed method makes sense for the problem at hand.", "theoretical_claims": "The theoretical claims are correct.", "experimental_designs_or_analyses": "The experimental designs and analyses are sound.", "relation_to_broader_scientific_literature": "This submission challenges some findings made by (Brunswic et al., 2024), and provides a new perspective on GFlowNets in the case where the state space is non-acyclic anymore. They show that in the case where $P_{B}$ is fixed, the stable versions of the losses proposed by (Brunswic et al., 2024) is not necessary. They also show a stronger result regarding the expected length of the trajectories (in Proposition 3.11, as opposed to an inequality in prior work). They state and empirically verify a \"scaling hypothesis\" that shows that prior losses working in flow space as in (Brunswic et al., 2024) lead to lower expected trajectory lengths, but often fail to get a good approximation of the target distribution.\n\n---\n\nBrunswic, L., Li, Y., Xu, Y., Feng, Y., Jui, S., and Ma, L. A theory of non-acyclic generative flow networks. AAAI 2024.", "essential_references_not_discussed": "Not an essential reference, especially since this was released on Arxiv only a few weeks before the submission deadline, but the constrained optimization formulation in Eq 11 (motivating the flow regularization) is similar to Proposition 4.1.3 of (Deleu, 2025). This result appears in a 200 pages PhD thesis and does not seem to have been published prior to this. The authors should only include that if they deem necessary.\n\n---\n\nDeleu, T. Generative Flow Networks: Theory and Applications to Structure Learning. 2025.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- Lines 101-102: This is not what the reward matching condition corresponds to. The reward matching condition of [Bengio et al., 2023] corresponds to $F(x \\rightarrow s_{f}) = R(x)$ (and its variant $F(x)P_{F}(s_{f}\\mid x) = R(x)$ in the case of the DB condition). In fact, this is exactly the condition later stated in line 74 or 86, and (almost) correctly stated in eq 9. The condition in the submission $P(\\{\\tau \\mid x\\in\\tau\\}) = R(x) / Z$ is the desiderata of GFlowNets (i.e., its terminating state distribution is proportional to $R$). Note that even $P(\\{\\tau \\mid x\\in\\tau\\})$ is *not* the terminating state distribution: the terminating state distribution is the marginal over trajectories that terminate in $x$, in the sense mentioned in line 89.\n- Typo $s$ instead of $s’$ in line 125, $s’$ instead of $s$ in line 128.\n- Typo $R(s)$ instead of $R(s_f)$ in eq 9 and line 249.\n\n---\n\nBengio, Y., Lahlou, S., Deleu, T., Hu, E. J., Tiwari, M., and Bengio, E. GFlowNet Foundations. JMLR, 2023", "questions_for_authors": "- It seems like in many applications involving GFlowNets, the state space is a design choice made by the practitioners which as full control over, as long as the terminal states are the elements of the sample space. This is very different from RL, where the MDP is often modeling the real-world that we don't have much control over. Therefore, it seems like in most cases the state space can be designed to be acyclic, where the standard theory of GFlowNets hold and no considerations regarding the expected length of the trajectories is necessary. Case in point, the two environments studied in this submission (which are based on prior work) are designed specifically to be non-acyclic; but we could very well design them being acyclic (hypergrid is often studied in the acyclic case). Can you give a practical example of an environment where non-acyclicity is necessary for GFlowNets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mdCH4DaiD1", "reviewer": "Reviewer_6mHF", "summary": "The paper introduces a new theory of Non-Acyclic GFlowNet. The main intuition is that in the non-acyclic case, the visiting probability of an edge doesn't follow the flow matching constraint, because it doesn't take into account the cycles. Rather, the expected number of visits satisfies the FM, making it the appropriate quantity to define a flow. Another important idea is that the length of the trajectories is proportional to the total states flow.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly appreciate the feedback from the reviewer and are happy to answer their questions. We are pleased that the reviewer acknowledged the contributions of our paper and found it very well written.\n\nFirstly, we would like to note that we actually implement the permutation task with a more complex reward function compared to [1], not with a simpler one (see lines 366-374 in Section 4.3 and Appendix C.3.1 for further details). \n\nSecondly, the case of continuous state spaces was explored in [1], while the goal of our work was to focus on the discrete case and show how the theory and results of [1] can be simplified and expanded in discrete environments. While our own construction can be potentially extended to the continuous case following an approach similar to the one introduced in [2], it will indeed require fundamental adaptations, i.e., considering general measurable spaces instead of finite graphs. An interesting question here is whether the refined results we demonstrate in our paper compared to [1] (e.g. nature of flows, training with fixed backward policies, equality instead of inequality in Proposition 3.11) can be demonstrated in the continuous case as well, or whether they are specific to the discrete case and do not hold/need a different interpretation  for continuous spaces. We consider this to be a crucial direction for future research.\n\nFinally, we agree that the idea to truncate/prevent cycles in trajectories used for training seems natural. In addition, we note that [1] followed a similar approach, but bounded the maximum length of trajectories used in training instead of removing cycles from them. However, this may come with a number of potential issues. Using a distribution over trajectories in training that is different from the one parameterized by the forward policy will mean that the training is done off-policy, which is a viable choice for GFlowNet algorithms, and it is indeed possible that truncating cycles during training will lead to improved stability. Yet, during inference, if one wants to obtain samples from the target distribution using the learned policy, one has to faithfully run the generation process following the policy until a terminating transition is sampled, and using some form of truncation may lead to a bias. In addition, even if the truncation is used in training, there is no guarantee how the true expected trajectory length of the learned policy will behave if the regularization is removed. We hypothesize that it will still be growing if a $\\Delta \\log F$ scale loss is used without regularization (like in Figure 4), but it is difficult to say for sure without explicit empirical validation of different truncation strategies. We also find this to be an interesting direction for future research.\n\nReferences:\\\n[1] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024\\\n[2] Lahlou et al. A theory of continuous generative flow networks. ICML 2023", "claims_and_evidence": "All the claims are mathematically proven in appendix. Experimental evidence supports the provided theory.", "methods_and_evaluation_criteria": "The paper evaluates its methodology on two distinct tasks: non-acyclic hypergrid and permutations. Hypergrid is widely recognized and frequently used in Generative Flow Network research. The permutation task was first presented by Brunswic et al. (2024), though this paper implements it with a simplified reward structure. Both the selected tasks and the evaluation metrics are appropriate and meaningful for assessing the method's performance.", "theoretical_claims": "all good", "experimental_designs_or_analyses": "all good", "relation_to_broader_scientific_literature": "Brunswic et al. (2024) were the first who addressed non-acyclic GFlowNets, introducing the concept of stable loss and developing stabilized versions of conventional training objectives. The current paper refines several assertions made by Brunswic et al., specifically: clarifying that visitation probability adheres to flow matching, writing Proposition 3.11 to show it represents an equality rather than merely an inequality, and demonstrating that non-acyclic GFlowNets can be effectively trained using unstable losses when proper regularization is applied. Additionally, this work expands upon Tiapkin et al. (2024) by establishing connections between GFlowNets and Entropy-Regularized Reinforcement Learning within non-acyclic contexts.", "essential_references_not_discussed": "not to my knowledge", "other_strengths_and_weaknesses": "Strength: The paper is very well written!\n\nWeaknesses: The paper could benefit from more experimental settings", "other_comments_or_suggestions": "NA", "questions_for_authors": "- Can this theoretical framework be extended to continuous state spaces without significant modifications, or would it require fundamental adaptations?\n\n- If we constrain training trajectories to be acyclic (either by preventing cycles during sampling or by truncating cyclic segments post-sampling), does this approach improve training stability and convergence? Furthermore, does such training naturally lead to fewer cycles during inference, even when regularization mechanisms are removed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All the reviewers agree that the paper should be accepted, and so do I.
Decision: Accept (poster)