acceptodds
Under review as a conference paper at ICLR 2027

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

10 views

Abstract

Generative Flow Networks (GFlowNets) learn policies that sample discrete objects in proportion to a strictly positive reward. Existing guarantees typically assume exact balance, whereas practical training reaches only a small loss or a stationary point under evolving sampling distributions and backward policies. To bridge this gap, we develop a unified theory for Flow Matching, Detailed Balance, and Trajectory Balance in this regime. We first bound terminal symmetric KL by the square root of the expected balance loss. Then, we show that approximate stationarity controls this distribution error up to a tangent-space residual measuring parameterization incompleteness. Finally, we establish finite-time convergence under fixed or controlled sampling and fixed, balance-trained, or separately updated backward policies. Under the stated smoothness and tangent-geometry conditions, with fixed or controlled sampling and a fixed or balance-trained backward policy, the expected loss is and expected terminal symmetric KL is under uniform coverage. For a separately updated backward policy, we characterize sufficient update decay for approaching the residual neighborhood and for preserving these rates. These results connect balance objectives to sampling accuracy and clarify how parameterization, coverage, and moving components govern GFlowNet training.

Primary area:
learning theory
Keywords:
GFlowNets, Theory, Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_eQ78OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

GFlowNets are generative models that learn to sample from a distribution p∗(x)=R(x)/Zp^*(x)=R(x)/Z, where Z=∑x∈XR(x)Z=\sum_{x\in\mathcal X}R(x), over a discrete space X\mathcal X. They do so by learning a flow on a directed acyclic graph with a source node s0s_0 supplying ZZ, terminal nodes x∈Xx\in\mathcal X absorbing R(x)R(x), and intermediate nodes satisfying flow conservation. Different ways of parameterizing and learning such flow give rise to three methods: Flow Matching (FM), Detailed Balance (DB), and Trajectory Balance (TB). The paper provides a unified theoretical analysis of the training of GFlowNets under these three paramterizations. In particular, it establishes three main results:

  • Result 1 (Thm 3.2): A small expected loss implies that the learned distribution is close to the target distribution, provided the training samples sufficiently cover the relevant parts of the graph.

  • Result 2 (Thm 4.6): A small gradient of the expected loss also implies that the learned distribution is close to the target, provided the model can adequately correct its balance errors through gradient parameter updates and is sufficiently well-conditioned.

  • Result 3 (Theorems 5.4, 5.9, and 5.12): Under additional assumptions, SGD is shown to converge toward a small expected loss at a rate they quantify.

Critical strengths
  • The paper provides a unified theoretical framework for understanding the training of GFlowNets across FM, DB, and TB, connecting balance loss, stationarity, and SGD convergence to sampling accuracy.
Critical weaknesses
  • The theoretical guarantees rely on several strong assumptions, e.g. bounded sampling coverage (∥ν/μ∥∞\left\lVert\nu/\mu\right\rVert_{\infty} in the paper), a small parameterization residual (ϵμ\epsilon_{\mu} in the paper), and good conditioning of the effective Fisher matrix (λ\lambda in the paper). The paper does not establish whether these assumptions hold for general neural-network GFlowNets.
Questions for authors
  • Could the authors comment on how reasonable the assumptions on sampling coverage, the parameterization residual, and effective Fisher conditioning are for practical neural-network GFlowNets? In particular, can these assumptions be theoretically justified for non-tabular models, or did the authors observe that they are empirically verified during training?
3 comments
AuthorsOpenReview ↗

Responses to Reviewer eQ78 (1/1)

Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Before addressing your specific questions, we would like to highlight our major revisions:

  1. We have improved the loss-to-distribution bound to a linear bound given by KL(pF⊤∣∣pR)+KL(pR∣∣pF⊤)≤2κ2∥ν/μ∥∞LO(θ)\mathrm{KL}(p_F^\top||p_R) + \mathrm{KL}(p_R||p_F^\top) \leq 2\kappa^2\lVert\nu/\mu\rVert_\infty \mathcal{L}_{\mathcal{O}}(\theta) through carefully analyzing the occupancy mass cνc_\nu to demonstrate that cν∼KLc_\nu \sim \sqrt{\mathrm{KL}}. Consequently, the stationary-to-optimality bound and the finite-time convergence rate can be enhanced accordingly.

  2. We have added a new section for numerical experiments to verify the theories discussed in Sections 3 and 4. We trained TB, DB, and FM GFlowNets on a small DAG and evaluated the expected loss, gradient norm, and terminal symmetric KL during training. By plotting the data points on logarithmic axes, we observed that the symmetric KL-loss points align along a line with a slope of approximately 1, whereas the loss-gradient norm points align along a line with a slope of approximately 2. These results are consistent with Theorem 3.4 and Lemma 4.4, respectively, and together illustrate Theorem 4.5.

Below, we briefly respond to your comments and questions.

Sampling Coverage

On a finite object space, if μt=(1−α)pt+αq,α>0,qmin⁡:=min⁡oq(o)>0,\mu_t=(1-\alpha)p_t+\alpha q, \qquad \alpha>0,\qquad q_{\min}:=\min_o q(o)>0, then ∥ν/μ∥∞≤1/(αqmin⁡)\left\lVert\nu/\mu\right\rVert_{\infty}\leq 1/(\alpha q_{\min}) whenever the discrepancy is nonzero.

For TB with exponentially many trajectories, the coverage factor Cν=∥ν/μ∥∞C_\nu=\left\lVert\nu/\mu\right\rVert_{\infty} can be sharpened by restricting the comparison to the function space containing the TB imbalances, rather than requiring coverage of individual trajectories. To be precise, define ϕ(τ):=(1,(1{e∈τ})e∈E,(1{sn(τ)=x})x∈X)⊤,HTB:=span⁡{ϕj(⋅)}j,\phi(\tau):=\left(1,\left(\mathbf{1}\lbrace e\in\tau\rbrace\right)_{e\in\mathcal{E}}, \left(\mathbf{1}\lbrace s_{n(\tau)}=x\rbrace\right)_{x\in\mathcal{X}}\right)^\top, \mathcal{H}_{\mathrm{TB}}:=\operatorname{span}\lbrace\phi_j(\cdot)\rbrace_j, and for any distribution ρ\rho, denote the covariance matirx as Σρ:=Eρ[(ϕ−Eρϕ)(ϕ−Eρϕ)⊤],\Sigma_\rho:=E_\rho[(\phi-\mathbb E_\rho\phi)(\phi-\mathbb E_\rho\phi)^\top], the coverage factor is CTB(ν,μ):=sup⁡f∈HTBVar⁡ν(f)Var⁡μ(f)=λmax⁡(Σμ†/2ΣνΣμ†/2),C_{\mathrm{TB}}(\nu,\mu):=\sup_{f\in\mathcal H_{\mathrm{TB}}}\frac{\operatorname{Var}_\nu(f)}{\operatorname{Var}_\mu(f)}=\lambda_{\max}(\Sigma_\mu^{\dagger/2}\Sigma_\nu\Sigma_\mu^{\dagger/2}), which can be controlled to the order of dim(HTB)\mathrm{dim}(\mathcal H_{\mathrm{TB}}) under careful design.

We have included the this improved coverage factor and corresponding discussions in Appendix B.1 of our revision.

Parameterization Geometry

The assumptions regarding bounded residuals and the eigenvalues of the Fisher matrix are commonly referenced in the theoretical analysis of the natural policy gradient and natural actor-critic methods in reinforcement learning (e.g., [1][2][3]), where the residuals parellels the compatiable function approximation error. We acknowledge that establishing a uniform bound for ϵμ\epsilon_\mu and λ\lambda throughout the training process is difficult to justify theoretically. However, numerical experiments indicate that PL condition, which directly arises from these assumptions, is well-preserved during training. This provides empirical evidence for the validity of these assumptions.


We hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!

[1] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Neurips 2020.

[2] Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum-based policy gradient. AISTATS 2022.

[3] Ganesh, Swetha, Jiayu Chen, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. UAI 2025.

Thank you for your response. I will maintain my score, as I value the theoretical unification the paper proposes.

That said, the experiments do not fully resolve my concern about whether the assumptions hold for practical neural GFlowNets. The experiments use a single graph with 25 states, whereas the applications listed in your introduction involve much larger state spaces. Moreover, your appendix states that “Each state has a trainable 16-dimensional embedding.” It is unclear whether the observed behavior extends to models that compute representations from state features over such large state spaces, where maintaining a separate trainable embedding for every possible state may be impractical...

Thank you for clarifying this concern. In the revision, we replaced the per-state trainable embedding with a non-tabular model that computes representations from fixed 8-dimensional random state features using a two-layer message-passing GNN. All GNN and edge-scoring parameters are shared across states, so the number of trainable parameters is independent of the state-space size. We reran all TB, DB, and FM experiments with this model, and observed the same qualitative loss–discrepancy and gradient–loss relationships. This addresses the specific concern that the previous evidence depended on maintaining a separate trainable embedding for every state, and also hints the behaviors for larger state spaces. We have updated the experimental description, figures, and appendix accordingly.

Reviewer_zUUjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a unified theoretical analysis of the training dynamics of Generative Flow Networks (GFlowNets). It studies three common balance objectives, including Flow Matching (FM), Detailed Balance (DB), and Trajectory Balance (TB). The authors first establish bounds relating the expected balance loss to the symmetric KL divergence between the generated distribution and the reward-proportional target distribution. They then analyze approximate stationary points by decomposing the flow imbalance into a tangent-space component and a parameterization residual. Based on this analysis, the paper derives finite-time convergence guarantees under fixed or controlled sampling distributions and different backward-policy update strategies. The results clarify how sampling coverage, parameterization properties, and evolving training components affect the convergence and sampling accuracy of GFlowNets.

Critical strengths

(1) Comprehensive and unified theoretical framework. The paper studies FM, DB, and TB within a common analytical framework, connecting balance objectives to terminal sampling accuracy and optimization behavior. It also extends the analysis to Sub-Trajectory Balance in the appendix. This unified treatment provides a useful perspective on several widely used GFlowNet training objectives.

(2) Meaningful analysis of approximate stationarity. The paper introduces a tangent-space decomposition of the log-flow imbalance to characterize the relationship between stationary points and sampling accuracy. The resulting bound separates optimization error from parameterization incompleteness, providing insight into why a small gradient does not always imply accurate sampling. The zero-residual result for standard tabular GFlowNets further strengthens this analysis.

(3) Convergence guarantees under evolving training components. Beyond fixed sampling distributions, the paper considers changing sampling distributions and backward policies that are jointly or separately updated. It establishes finite-time convergence rates under explicit assumptions and characterizes how the magnitude of backward-policy updates affects these rates. These results address important aspects of practical GFlowNet training that are not captured by fixed-objective analyses.

Critical weaknesses

(1) The main convergence results rely on restrictive assumptions about the parameterization geometry and sampling coverage. In particular, Assumption 5.2 requires a uniformly bounded tangent-space residual and a uniform lower bound on the nonzero eigenvalues of the effective Fisher matrix throughout training. Although Proposition 4.2 establishes a zero-residual property for standard tabular GFlowNets, it remains unclear whether these conditions can be satisfied by neural GFlowNets with shared parameters. Moreover, the terminal distribution bounds depend on a coverage ratio between the training distribution and the forward-backward occupancy discrepancy, which may become large or difficult to control under practical sampling strategies. While these assumptions are explicitly stated, the paper provides limited guidance on how to verify or enforce them in realistic settings. This substantially limits the extent to which the theoretical guarantees explain the behavior of practical neural GFlowNet training.

(2) The convergence analysis in Section 5 builds substantially on standard approximate Polyak–Łojasiewicz (PL) geometry and stochastic optimization arguments. Once the tangent-space residual and effective Fisher conditioning assumptions imply an approximate PL inequality, the resulting loss convergence rate of O(ϵˉ2+T−1)O(\bar{\epsilon}^2+T^{-1}) follows from relatively standard SGD analysis. The corresponding terminal distribution convergence rate of O(ϵˉ+T−1/2)O(\bar{\epsilon}+T^{-1/2}) is then obtained by combining this result with the loss-to-distribution bound. Although the paper extends the analysis to changing sampling distributions and separately updated backward policies, these results also rely on explicit assumptions that control the drift of the training objective. The analysis would be more compelling if it provided deeper GFlowNet-specific insights into when these conditions hold and how different training strategies affect convergence beyond the general stochastic optimization framework. Therefore, the independent theoretical contribution of the finite-time convergence results is somewhat limited compared with the broader unified analysis.

Questions for authors

Could the authors provide numerical experiments on small DAGs or tabular GFlowNets to evaluate the practical relevance of the theoretical bounds? In particular, it would be useful to compare the observed terminal symmetric KL divergence with the bound in Theorem 3.2 and examine how sampling coverage affects its tightness. Additional experiments varying the sampling strategy or backward-policy update frequency could also help verify whether the convergence behavior follows the predictions of Section 5. Such evaluations would strengthen the connection between the theoretical analysis and practical GFlowNet training.

3 comments
AuthorsOpenReview ↗

Responses to Reviewer zUUj (1/2)

Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Before addressing your specific questions, we would like to highlight a major revision: the loss-to-distribution bound can be improved to a linear form of KL(pF⊤∣∣pR)+KL(pR∣∣pF⊤)≤2κ2∥ν/μ∥∞LO(θ)\mathrm{KL}(p_F^\top||p_R)+\mathrm{KL}(p_R||p_F^\top)\leq2\kappa^2\lVert\nu/\mu\rVert_\infty\mathcal{L}_{\mathcal{O}}(\theta) by carefully analyzing the occupancy mass cνc_\nu to demonstrate that cν∼KLc_\nu \sim \sqrt{\mathrm{KL}}. Consequently, the stationary-to-optimality bound and the finite-time convergence rate can be enhanced accordingly.

In addition to this major change, we have also conducted numerical experiments and revised several paragraphs and sections in response to your specific comments and questions. You can find our detailed responses below, and the changes are highlighted in blue in the revised document.

Q1

We have added a new section for numerical experiments to verify the theories discussed in Sections 3 and 4. We trained TB, DB, and FM GFlowNets on a small DAG and evaluated the expected loss, gradient norm, and terminal symmetric KL during training. By plotting the data points on logarithmic axes, we observed that the symmetric KL-loss points align along a line with a slope of approximately 1, whereas the loss-gradient norm points align along a line with a slope of approximately 2. These results are consistent with Theorem 3.4 and Lemma 4.4, respectively, and together illustrate Theorem 4.5.

We also evaluate the effects of sampling coverage on the loss-to-distribution bounds. The behavior policy we use for sampling training objectives is a mixture of the current forward policy and uniform exploration of a portion of ϵ\epsilon. The observed trend is consistent accross ϵ∈{0,0.25,0.5}\epsilon\in\lbrace0, 0.25, 0.5\rbrace, but the larger-exploration runs, particularly ϵ=0.5\epsilon=0.5, exhibit a better approximately linear loss–discrepancy relationship This is because more uniform exploration results in smaller variations of the coverage ratio ∥ν/μ∥∞\lVert\nu/\mu\rVert_\infty, making the linear relation easier to observe. These extensive results are provided in Appendix F.

Regarding the theoretical results presented in Section 5, conducting numerical experiments to verify them is challenging. The main obstacle is that the desired learning rate ηt=at+t0\eta_t=\frac{a}{t+t_0} requires intractable constants aa and t0t_0. Additionally, the standard SGD with this learning rate schedule differs significantly from common practices using advanced optimizers like Adam. We acknowledge this limitation in our theory. However, this theoretical-empirical gap is rooted in the field of optimization, which is beyond the scope of this paper.

W1.1 Parameterization Geometry

The assumptions regarding bounded residuals and the eigenvalues of the Fisher matrix are commonly referenced in the theoretical analysis of the natural policy gradient and natural actor-critic methods in reinforcement learning (e.g., [1][2][3]). We acknowledge that establishing a uniform bound throughout the training process is difficult to justify theoretically. However, numerical experiments indicate that the PL condition, which directly follows from these assumptions, is well-preserved during training. This provides empirical support for the validity of these assumptions.


[1] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Neurips 2020.

[2] Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum-based policy gradient. AISTATS 2022.

[3] Ganesh, Swetha, Jiayu Chen, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. UAI 2025.

AuthorsOpenReview ↗

Responses to Reviewer zUUj (2/2)

W1.2 Sampling Coverage

On a finite object space, if μt=(1−α)pt+αq,α>0,qmin⁡:=min⁡oq(o)>0,\mu_t=(1-\alpha)p_t+\alpha q, \qquad \alpha>0,\qquad q_{\min}:=\min_o q(o)>0, then ∥ν/μ∥∞≤1/(αqmin⁡)\left\lVert\nu/\mu\right\rVert_{\infty}\leq 1/(\alpha q_{\min}) whenever the discrepancy is nonzero.

For TB with exponentially many trajectories, the coverage factor Cν=∥ν/μ∥∞C_\nu=\left\lVert\nu/\mu\right\rVert_{\infty} can be sharpened by restricting the comparison to the function space containing the TB imbalances, rather than requiring coverage of individual trajectories. To be precise, define ϕ(τ):=(1,(1{e∈τ})e∈E,(1{sn(τ)=x})x∈X)⊤,HTB:=span⁡{ϕj(⋅)}j,\phi(\tau):=\left(1,\left(\mathbf{1}\lbrace e\in\tau\rbrace\right)_{e\in\mathcal{E}}, \left(\mathbf{1}\lbrace s_{n(\tau)}=x\rbrace\right)_{x\in\mathcal{X}}\right)^\top, \mathcal{H}_{\mathrm{TB}}:=\operatorname{span}\lbrace\phi_j(\cdot)\rbrace_j, and for any distribution ρ\rho, denote the covariance matirx as Σρ:=Eρ[(ϕ−Eρϕ)(ϕ−Eρϕ)⊤],\Sigma_\rho:=E_\rho[(\phi-\mathbb E_\rho\phi)(\phi-\mathbb E_\rho\phi)^\top], the coverage factor is CTB(ν,μ):=sup⁡f∈HTBVar⁡ν(f)Var⁡μ(f)=λmax⁡(Σμ†/2ΣνΣμ†/2),C_{\mathrm{TB}}(\nu,\mu):=\sup_{f\in\mathcal H_{\mathrm{TB}}}\frac{\operatorname{Var}_\nu(f)}{\operatorname{Var}_\mu(f)}=\lambda_{\max}(\Sigma_\mu^{\dagger/2}\Sigma_\nu\Sigma_\mu^{\dagger/2}), which can be controlled to the order of dim(HTB)\mathrm{dim}(\mathcal H_{\mathrm{TB}}) under careful design.

We have included the this improved coverage factor and corresponding discussions in Appendix B.1 of our revision.

W2

Although Section 5 of this paper is based on the standard SGD analysis under the PL condition, it does provide GFlowNet-specific insights through extensions to changing sampling (Section 5.2) and separate backward update (Section 5.3). In these sections, we establish the conditions for the changing distribution and the separate backward updates to ensure convergence, specifically the drift condition ρ<1\rho < 1 and the decay rates for the backward update dtd_t.

The drift condition ρ=CωKθλ<1\rho=\frac{C_\omega K_\theta}{\sqrt{\lambda}}<1 can be managed through practical techniques such as exploration mixtures, experience replay, and damped updates. We have discussed their effects on the factor ρ\rho in Appendix D.5. For instance, incorporating an exploration mixture with a parameter ϵ\epsilon scales ρ\rho by a factor of 1−ϵ\sqrt{1 - \epsilon}, while using a τ\tau-temperature for the behavior policy scales ρ\rho by a factor of 1τ\frac{1}{\tau}. Thus, there are always training configurations satisfying this drift condition given other constants fixed. Although it is challenging to determine a specific training configuration that satisfies this condition in practice due to some intractable constants, this analysis provides a potential explanation for why these techniques are employed to stabilize training.

The decay rates dtd_t can be easily controlled through the learning rate, especially since the gradient is bounded—a condition typically ensured through gradient clipping in practice. Therefore, the conditions outlined in Theorem 5.11 offer a theoretical understanding of how quickly the backward policy can change to ensure the convergence of GFlowNet training and when this becomes a bottleneck. Together, these findings provide valuable insights into the design of GFlowNet training algorithms.

It is also important to note that the assumptions we made in these sections are general and cover most practical scenarios. In our revision, we provide a detailed discussion of each of these assumptions in Appendix D.4.

However, there remains a gap between our finite-time convergence results and practical GFlowNet training, particularly considering that our vanilla SGD employs an O(1/t)O(1/t) learning rate schedule as opposed to more advanced optimizers like Adam used in practice. This gap primarily resides in the area of optimization and is beyond the scope of this paper. Nonetheless, our results offer the first terminal distribution convergence guarantee for GFlowNets, addressing both changing sampling and separate backward updates.


We hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!

Dear Reviewer zUUj,

Thank you again for your review. We have revised the experiments and updated the paper today. The new experiments replaced the original MLP model by a GNN model with fixed random state features, so that the number of trainable parameters is independent of the state-space size. This addresses the specific concern that the previous evidence depended on maintaining a separate trainable embedding for every state, and also hints the behaviors for larger state spaces.

As the rebuttal period is approaching its end, we would greatly appreciate it if you could take a moment to review our responses to your comments. We hope that our clarifications have adequately addressed your concerns. If so, we would be grateful if you could consider updating your rating accordingly. If you have any remaining concerns or questions, please feel free to let us know, and we would be happy to address them.

The authors

Reviewer_ByNEOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper develops a unified gradient-based analysis of Flow Matching, Detailed Balance, and Trajectory Balance. It first relates expected squared log-imbalance loss to terminal symmetric KL through the occupancy discrepancies distribution of forward/backward polices. It then projects the log-imbalance onto the local tangent space spanned by its parameter derivatives, yielding a bound on terminal distribution error in terms of the loss gradient norm and an orthogonal residual. Finally, under several key assumptions, it derives SGD loss convergence and corresponding terminal-distribution guarantees when using fixed or changing sampling distribution and separately updated backward policies.

Critical strengths
  1. The theoretical results apply to several standard GFlowNet training objectives, including FM, DB, and TB. This unified treatment provides a common perspective for connecting balance loss, and terminal sampling accuracy.

  2. The analysis considers multiple training settings, including fixed or evolving sampling distributions and backward policies updated using a separate criterion. Under the stated assumptions, it characterizes how sampling changes and backward-policy updates affect convergence, extending the analysis beyond fixed-objective training.

Critical weaknesses
  1. The claim contribution of connection between balance loss and terminal sampling accuracy is overstated, and actually a required intermedtate result for the derivation of the following result. The connection can be established more easity and straighforward through total variattion and marginalization, which are well-known for TB, FM and DB. It is therefore a afternative reformulation rather than new theoretical discovery.

    For example, for TB, a direct argument gives TV⁡(pF⊤,pR)≤CLTB2\operatorname{TV}(p_F^\top,p_R) \le\sqrt{\frac{C\mathcal L_{\mathrm{TB}}}{2}}, with C=∥ν/μ∥∞C=\|\nu/\mu\|_\infty. A corresponding bound holds for FM/DB with an additional maximum-trajectory-length factor when lengths are bounded.

    Consequently, once the loss convergence result in Theorem 5.4 is established, terminal TV convergence follows through a straightforward transfer argument. To be spefific, Theorem 5.4 gives $ \mathbb E[\mathcal L_T] \le A\bar\epsilon^2+\frac{B}{T+t_0}$. Therefore, E[TV⁡(pF,T⊤,pR)]≤Cˉ2(Aϵˉ2+BT+t0)≤CˉA2ϵˉ+CˉB21T+t0\mathbb E[\operatorname{TV}(p_{F,T}^\top,p_R)]\le\sqrt{\frac{\bar C}{2} \left(A\bar\epsilon^2+\frac{B}{T+t_0}\right)}\le \sqrt{\frac{\bar C A}{2}}\bar\epsilon +\sqrt{\frac{\bar C B}{2}}\frac1{\sqrt{T+t_0}}.

    Hence, E[TV⁡(pF,T⊤,pR)]=O(ϵˉ+T−1/2)\mathbb E[\operatorname{TV}(p_{F,T}^\top,p_R)]=O(\bar\epsilon+T^{-1/2}).

  2. The tangent–residual decomposition is generic to nonlinear least-squares problems. It describes a limitation of local first-order information at a given parameter value, rather than a failure shared by every first-order optimization method. Its derivation does not require structural properties specific to GFlowNets. Consequently, the decomposition itself does not reveal challenges unique to GFlowNet training, limiting its significance as a GFlowNet-specific theoretical contribution.

  3. Much of the analysis relies on the discrepancy distribution ν\nu, which is defined through differences between forward and backward occupancies. However, enumerating all such discrepancies generally faces essentially the same computational difficulty as enumerating the corresponding global flow values. Expressing the guarantees through ν\nu therefore largely reformulates the original difficulty in terms of another global quantity. Consequently, the results offer an alternative perspective on the difficulty of GFlowNet training, but provide limited additional insight into the underlying computational bottleneck.

  4. Compared to Section 5.1, Sections 5.2 and 5.3 require several strong assumptions whose validity is not established for a representative practical training algorithm.

  5. The terminal-distribution convergence guarantee O(ϵˉ+T−1/2)O(\bar\epsilon+T^{-1/2}) is weak relative to the assumptions required to obtain it.

Questions for authors

Applicability of Theorem 5.9: Which concrete on-policy or adaptive sampling scheme, initialization region, and parameterized model satisfy all hypotheses throughout training?

6 comments
AuthorsOpenReview ↗

Responses to Reviewer ByNE (1/3)

Thank you for your time and effort in reviewing our paper! We are grateful for your constructive suggestions, which have significantly guided our improvements. Before addressing your specific questions, we would like to highlight our major revisions:

  1. We have improved the loss-to-distribution bound to a linear bound given by KL(pF⊤∣∣pR)+KL(pR∣∣pF⊤)≤2κ2∥ν/μ∥∞LO(θ)\mathrm{KL}(p_F^\top||p_R) + \mathrm{KL}(p_R||p_F^\top) \leq 2\kappa^2 \left\lVert\nu/\mu\right\rVert_{\infty} \mathcal{L_O}(\theta) through carefully analyzing the occupancy mass cνc_\nu to demonstrate that cν∼KLc_\nu \sim \sqrt{\mathrm{KL}}. Consequently, the stationary-to-optimality bound and the finite-time convergence rate can be enhanced accordingly.

  2. We have added a new section for numerical experiments to verify the theories discussed in Sections 3 and 4. We trained TB, DB, and FM GFlowNets on a small DAG and evaluated the expected loss, gradient norm, and terminal symmetric KL during training. By plotting the data points on logarithmic axes, we observed that the symmetric KL-loss points align along a line with a slope of approximately 1, whereas the loss-gradient norm points align along a line with a slope of approximately 2. These results are consistent with Theorem 3.4 and Lemma 4.4, respectively, and together illustrate Theorem 4.5.

In addition to these major changes, we have also revised several paragraphs and sections in response to your specific comments and questions. You can find our detailed responses below, and the changes are marked in blue in our revised document.

W1

We respectfully disagree with the assertion that the connection between total variation (TV) and the GFN loss is a "well-known" result. While some prior research may hint at their relationship, a rigorous bound has yet to be established. One such results is Proposition 4.2 of [1], where their TB-like loss requires the true target distribution pRp_R, differing from the standard TB loss by a constant of log⁡(Z/Z^)\log(Z/\hat{Z}). This constant is eliminated by symmetrizing the KL divergence in our analysis.

In contrast, the concurrent work in reference [2] does establish a rigorous loss-to-TV bound; however, their result requires a uniform bound on the errors for every training object, while our approach utilizes the expected loss under a general, potentially off-policy training measure.

Furthermore, TV bounds can be derived from our symKL bounds combined with Pinsker's Inequality, which states that TV≤12KL\mathrm{TV}\leq\frac{1}{2}\sqrt{\mathrm{KL}} (corresponding to your bound TV≤CLTB2\mathrm{TV}\leq\sqrt{\frac{C\mathcal{L}_{TB}}{2}}), or the Bretagnolle–Huber bound TV≤1−exp⁡(−KL)\mathrm{TV}\leq\sqrt{1-\exp(-\mathrm{KL})} (corresponding to the loss-to-TV bound in [2]). We have provided a detailed comparison with existing theoretical results in Appendix A.1 of our revision.

We sincerely hope that you can reevaluate the novelty and significance of our loss-to-distribution result.

W2

As stated at the beginning of Section 4, the purpose of this section is to establish the properties of (approximate) stationary points of the TB, DB, and FM losses under standard parameterizations, rather than examining the training behaviors of any specific optimization methods. To accomplish this, we introduce the tangent-residual decomposition. Specific to GFlowNets, we show in Proposition 4.2 that the standard positive tabular parameterization of GFlowNets—including TB, DB, FM, and their forward-looking versions— exhibits zero residual, indicating exact optimality at stationary points. Consequently, for a general parameterization of GFlowNets, this residual serves as a measure of its incompleteness. These findings suggest that the unique structure of GFlowNets does not pose additional challenges to its training. Therefore, we believe that this is a significant result for the theory of GFlowNets.

[1] Tiago Silva, Amauri H Souza, Omar Rivasplata, Vikas Garg, Samuel Kaski, and Diego Mesquita. Generalization and distributed learning of GFlownets. ICLR 2025.

[2] Zengxiang Lei, Ananth Shreekumar, Jonathan Rosenthal, Ruoyu Song, Alvaro A. Cardenas, Daniel J. Fremont, Dongyan Xu, Satish Ukkusuri, and Z. Berkay Celik. Stable gflownets with tv monitoring and probabilistic guarantees. arxiv 2605.01729.

AuthorsOpenReview ↗

Responses to Reviewer ByNE (2/3)

W3

To the best of our knowledge, we are the first to provide a loss-to-distribution guarantee under general training measures. Unlike existing results that require exact balance across each training objective to ensure an accurate terminal distribution, or the concurrent work[2] that necessitates a uniform upper bound on losses for every training objective, we only require the expected loss to be controlled with respect to the discrepancy distribution ν\nu. It is misleading to summarize the former as "enumerating global flow values" while ours as "enumerating the discrepancies". This is a substantial improvement rather than merely a reformulation.

Furthermore, for TB with exponentially many trajectories, the coverage factor Cν=∥ν/μ∥∞C_\nu=\left\lVert\nu/\mu\right\rVert_{\infty} can be sharpened by restricting the comparison to the function space containing the TB imbalances, rather than requiring coverage of individual trajectories. To be precise, define ϕ(τ):=(1,(1{e∈τ})e∈E,(1{sn(τ)=x})x∈X)⊤,HTB:=span⁡{ϕj(⋅)}j,\phi(\tau):=\left(1,\left(\mathbf{1}\lbrace e\in\tau\rbrace\right)_{e\in\mathcal{E}}, \left(\mathbf{1}\lbrace s_{n(\tau)}=x\rbrace\right)_{x\in\mathcal{X}}\right)^\top, \mathcal{H}_{\mathrm{TB}}:=\operatorname{span}\lbrace\phi_j(\cdot)\rbrace_j, and for any distribution ρ\rho, denote the covariance matirx as Σρ:=Eρ[(ϕ−Eρϕ)(ϕ−Eρϕ)⊤],\Sigma_\rho:=E_\rho[(\phi-\mathbb E_\rho\phi)(\phi-\mathbb E_\rho\phi)^\top], the coverage factor is CTB(ν,μ):=sup⁡f∈HTBVar⁡ν(f)Var⁡μ(f)=λmax⁡(Σμ†/2ΣνΣμ†/2),C_{\mathrm{TB}}(\nu,\mu):=\sup_{f\in\mathcal H_{\mathrm{TB}}}\frac{\operatorname{Var}_\nu(f)}{\operatorname{Var}_\mu(f)}=\lambda_{\max}(\Sigma_\mu^{\dagger/2}\Sigma_\nu\Sigma_\mu^{\dagger/2}), which can be controlled to the order of dim(HTB)\mathrm{dim}(\mathcal H_{\mathrm{TB}}) under careful design. We have included this improved coverage factor and corresponding discussions in Appendix B.1 of our revision.

Therefore, whether for TB, DB, or FM, our results suggest that the training samples should cover a space comparable in size to the underlying DAG, which is reasonable without additional knowledge about the feature space, as suggested by the famous no-free-lunch theorem.

W4

As mentioned in our paper, Assumption 5.6 and Assumption 5.9 stem from a bounded hh and a bounded sampling score ∣∇ωlog⁡μω(o)∣2\lvert\nabla_{\omega}\log\mu_{\omega}(o)\rvert_2. To elaborate, the first assumption is derived from having a bounded reward and a bounded parameterization class, both of which are common in theoretical analyses. The second assumption can be inferred from a bounded sampling policy score ∥∇ωlog⁡πω(s′∣s)∥\|\nabla_{\omega}\log\pi_\omega(s'|s)\|—a condition that holds automatically for softmax policies, particularly when μω\mu_\omega is determined by the policy πω\pi_\omega.

Regarding Assumption 5.7 and Assumption 5.10, these assumptions assert that the sampling distribution is influenced by both the forward policy and the backward policy. Furthermore, this relationship is "Lipschitz," meaning that minor adjustments to either policy will not drastically alter the sampling distribution. This framework encompasses most practical scenarios. We have elaborated on these discussions in Appendix D.4 of our revision.

W5

The improved terminal distribution convergence guarantee is now O(ϵˉ2+T−1)O(\bar{\epsilon}^2+T^{-1}). This result is comparable to the standard SGD convergence result under the PL condition. Specifically for GFlowNet training, we extend this result to include changing sampling (Section 5.2) and separate backward updates (Section 5.3). For changing sampling, we propose the drift condition ρ=CωKθλ<1\rho=\frac{C_\omega K_\theta}{\sqrt{\lambda}}<1 as a sufficient criterion to ensure convergence. For separate backward updates, we derive the decay rates of dtd_t to ensure convergence and to preserve convergence rates. These findings offer valuable insights into the design of GFlowNet training algorithms.

There is potential for further enhancing this convergence rate using advanced optimization techniques or specific improvements tailored for GFlowNets; however, discussing those techniques is beyond the scope of this paper. Nonetheless, our result marks the first terminal distribution convergence guarantee for GFlowNets.

AuthorsOpenReview ↗

Responses to Reviewer ByNE (3/3)

Q1

The key condition for our analysis is ρ=CωKθλ<1\rho=\frac{C_\omega K_\theta}{\sqrt{\lambda}}<1. We have discussed several methods to reduce this factor in Appendix D.5. For instance, incorporating an exploration mixture with a parameter ϵ\epsilon scales ρ\rho by a factor of 1−ϵ\sqrt{1 - \epsilon}, while using a τ\tau-temperature for the behavior policy scales ρ\rho by a factor of 1τ\frac{1}{\tau}. Thus, there are always training configurations satisfying this drift condition given other constants fixed.

However, even for the tabular model, some relative constants such as λ\lambda are hard to compute. As a result, identifying a training configuration that satisfies this condition in practice can be difficult. It is important to note that this condition is only a sufficient one for the convergence result with evolving sampling distributions, specifically designed to fit the current framework for analyzing optimization dynamics. Clarifying this condition further would be an interesting direction for future research.


We hope our response addresses your concerns. If so, we wonder if you could kindly consider raising your score? We will also be happy to answer any further questions you may have. Thank you very much!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.