Revisiting Non-Acyclic GFlowNets in Discrete Environments

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.

Firstly, 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).

Secondly, 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.

Finally, 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.

References:
[1] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024
[2] Lahlou et al. A theory of continuous generative flow networks. ICML 2023

We are grateful to the reviewer for their constructive feedback and valuable suggestions, and are happy to provide further details.

Firstly, 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.

Secondly, 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.

Finally, 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:

1. 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.
2. 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.
3. 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.

References:
[1] Tristan Deleu. Generative Flow Networks: Theory and Applications to Structure Learning. 2025
[2] Malkin et al. Trajectory balance: Improved credit assignment in GFlowNets. NeurIPS 2022
[3] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024

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.

Regarding 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.

1. 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.
2. 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.
3. 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.

Next, 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.

Finally, 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.

References:
[1] Brunswic et al. A Theory of Non-Acyclic Generative Flow Networks. AAAI 2024
[2] Hu et al. Beyond Squared Error: Exploring Loss Design for Enhanced Training of Generative Flow Networks. ICLR 2025
[3] Silva et al. When do GFlowNets learn the right distribution? ICLR 2025