Revisiting Non-Acyclic GFlowNets in Discrete Environments

Nikita Morozov, Ian Maksimov, Daniil Tiapkin, Sergey Samsonov

Introduction

Generative Flow Networks (GFlowNets) have emerged as a powerful framework for sampling discrete objects proportionally to a reward function. Traditionally, GFlowNets have been restricted to Directed Acyclic Graphs (DAGs), ensuring that the construction process eventually terminates. However, many practical domains—ranging from molecular design to puzzle-solving—feature reversible actions or inherent symmetries that naturally form cycles.

Recent attempts to extend GFlowNets to non-acyclic environments introduced complex measure-theoretic formulations and suggested that standard GFlowNet losses are inherently unstable in the presence of cycles. This work simplifies the theoretical foundation of non-acyclic GFlowNets and demonstrates that standard losses, when properly regularized, are both stable and highly effective.

Theoretical Foundations: Flows as Expected Visits

In acyclic environments, state and edge flows represent the probability of visiting a specific state or transition. In cyclic graphs, where a state can be visited multiple times, this interpretation fails. This paper redefines state flow $F(s)$ and edge flow $F(s \to s')$ as the expected number of visits to a state or edge during a trajectory.

This shift leads to a critical mathematical insight: the expected length of a trajectory is exactly equal to the normalized total flow in the network. Specifically, $E[\text{length}] = \sum_{s \in \mathcal{S}} F(s) / Z$, where $Z$ is the partition function. This equivalence implies that minimizing the total flow is mathematically identical to seeking the shortest expected trajectory length, providing a principled way to prevent infinite loops in cyclic environments.

The "Stability" Myth and the Scaling Hypothesis

Prior research claimed that standard losses, such as Detailed Balance (DB), were unstable in cyclic graphs, leading to divergent trajectory lengths. The authors identify that this perceived instability is primarily a matter of numerical scaling rather than a fundamental theoretical flaw.

Standard GFlowNet losses typically operate on a log-flow scale ($\Delta \log F$). In contrast, the "stable" losses proposed in previous work operate on a linear flow scale ($\Delta F$). While linear-scale losses (referred to here as SDB) inherently under-predict flows—which keeps trajectories short—they often fail to accurately match the target reward distribution in complex environments. By using the standard log-scale DB loss with a simple state flow regularization term ($\lambda \sum F(s)$), the authors achieve both distributional accuracy and trajectory efficiency.

Experimental Evaluation

The proposed approach was evaluated on challenging non-acyclic environments, including high-dimensional hypergrids and large permutation groups.

High-Dimensional Hypergrids

In a 20x20x20x20 hypergrid, agents must navigate a massive state space with reversible moves. As shown in Figure 4, the standard DB loss with log-scaling and state flow regularization (orange line) converges rapidly to the true expected error, significantly outperforming linear-scale "stable" losses.

Empirical $L^1$ error on a 20x20x20x20 hypergrid. The log-scale DB loss with regularization (orange) achieves the lowest error.

Simultaneously, the regularization term successfully manages trajectory lengths. Figure 5 illustrates that while unregularized or poorly scaled methods may result in excessively long paths, the regularized log-scale DB loss maintains efficient, short trajectories.

Mean trajectory length during training on the 20x20x20x20 hypergrid. Regularization (orange and grey) effectively bounds the expected length.

Permutation Environments

The results were even more pronounced in the permutation environment (Cayley graph of the symmetric group). In a space of approximately $2.4 \times 10^{18}$ states (permutations of length 20), linear-scale losses failed to capture the reward distribution. The regularized log-scale DB loss, however, accurately matched the target distribution while keeping trajectory lengths between 3 and 7 steps.

Conclusion and Future Work

This work demystifies non-acyclic GFlowNets by providing a cleaner theoretical framework and debunking the necessity of specialized "stable" losses. By recognizing the equivalence between total flow and trajectory length, the authors show that standard GFlowNet techniques can be safely applied to cyclic environments with minimal modification.

Furthermore, the formal bridge established between non-acyclic GFlowNets and entropy-regularized Reinforcement Learning (RL) suggests a promising path for future research: leveraging mature RL algorithms to further enhance the training and scalability of GFlowNets in complex, cyclic domains.

Summary updated

BibTeX
@inproceedings{morozov2025revisiting,
  author = {Nikita Morozov and Ian Maksimov and Daniil Tiapkin and Sergey Samsonov},
  title = {{Revisiting Non-Acyclic GFlowNets in Discrete Environments}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=czqxB524oo},
}
Figure