Towards Understanding the Training of GFlowNets: A Theoretical Perspective

arXiv preprint, October 2026

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

arXiv:2610.13711v1 [cs.LG] 9 Oct 2026

Rui Hu, Yu Chen, Zhuoran Li, and Longbo Huang# Institute for Interdisciplinary Information Sciences, Tsinghua University # Correspondence: longbohuang@tsinghua.edu.cn

Abstract. Generative Flow Networks (GFlowNets) learn policies that sample discrete objects in proportion to a positive reward. They are trained by minimizing balance objectives, whose exact satisfaction guarantees correct sampling. However, a comprehensive theory linking nonzero balance loss and approximate stationarity to sampling accuracy, especially under evolving sampling distributions and backward policies, is still lacking. 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 standard smoothness assumptions, with fixed or controlled sampling and a fixed or balance-trained backward policy, the expected loss is 𝑂 (¯ 𝜖2 + 𝑇 −1 ) and expected terminal symmetric KL is 𝑂 (¯ 𝜖 + 𝑇 −1/2 ) under uniform coverage. For a separately updated backward policy, we characterize the sufficient update decay to approach the residual neighborhood and preserve these rates. These results connect balance objectives to sampling accuracy and clarify how parameterization, coverage, and moving components govern GFlowNet training.

1. Introduction Generative Flow Networks (GFlowNets, Bengio et al. (2021, 2023)) have emerged as a promising framework for training generative models that sample objects with probabilities proportional to a positive reward. High-reward objects are therefore sampled frequently, while different high-reward regions retain probability mass. This combination of quality and diversity has made GFlowNets useful in various applications such as molecule generation (Zhu et al., 2023; Koziarski et al., 2024), combinatorial optimization (Zhang et al., 2023), probabilistic inference (Manta et al., 2023; Deleu et al., 2024), text generation (Hu et al., 2024), and image generation (Liu et al., 2025; Yun et al., 2025). GFlowNets transform the sampling problem into a sequential generation process on a directed acyclic graph (DAG). Starting from an initial state, a forward policy constructs an object through a series of local decisions until it reaches a terminal state. The central idea is to view probability mass as flow through the DAG. If the flow is conserved at intermediate states and the terminal flow matches the reward, then the forward policy samples terminal states from the desired reward-proportional distribution. This global property can be enforced through local or trajectory-level balance conditions, leading to the standard Flow Matching (FM, Bengio et al. 2021), Detailed Balance (DB, Bengio et al. 1

Towards Understanding the Training of GFlowNets: A Theoretical Perspective 2023), and Trajectory Balance (TB, Whitammer et al. 2022) objectives. This elegant construction explains what happens when every balance condition is satisfied exactly, but it does not explain what happens during practical training. A parameterized model may attain only a small nonzero loss or approach a stationary point rather than a global minimizer. Moreover, the states, edges, or trajectories used for training may be drawn from an off-policy and time-varying distribution, while the backward policy may be fixed, trained jointly with the balance loss, or updated using a separate criterion. These choices make the objective seen by stochastic gradient descent (SGD) evolve over time. Consequently, to understand GFlowNet training, a systematic study is required to connect loss and stationarity to terminal accuracy while accounting for these moving components. This motivates three essential questions: 1. Does a small balance loss guarantee that the learned terminal distribution is close to the rewardproportional target? 2. When optimization reaches an approximate stationary point, how good is the resulting sampler, and what limits its accuracy? 3. As sampling strategies and backward policies are adapted during training, when can learning still approach the target distribution, and at what rate? Existing studies provide complementary pieces of this picture. Flow-imbalance analyses (Silva et al., 2025a) examine how balance violations affect the generated distribution, while generalization analyses (Krichel et al., 2024; Silva et al., 2025b) study learning from limited observations. Connections to variational inference and entropy-regularized reinforcement learning (Whitammer et al., 2023; Tiapkin et al., 2024), together with advances in loss design (Hu et al., 2025; Fawkes & Hartford, 2026), relate training objectives to distribution discrepancies. However, these relationships do not by themselves connect balance objectives to sampling accuracy. Yu (2025) establishes gradientconvergence results for FM and DB, as well as sample-complexity guarantees for TB. However, the objectives in their analysis differ from the commonly used squared log-ratio loss and do not clarify the quality of parameterized stationary points or the behavior of stochastic training under varying sampling and backward policies. Very recently, Lei et al. (2026) derived total variation guarantees from a uniform residual bound, providing a quantitative measure of sampling accuracy based on balance loss. A comprehensive literature review is available in Appendix A. To answer the above questions, we develop a unified theory for FM, DB, and TB that connects balance loss, stationary-point quality, and finite-time sampling accuracy. Our theoretical results are summarized as follows: 1. Balance loss controls sampling accuracy. For FM, DB, and TB, we bound the terminal symmetric KL by the square root of the expected balance loss, with explicit occupancy-mass and coverage factors. Thus a small loss is informative when the training samples cover the states, edges, or trajectories on which the forward and backward flows disagree. 2. Stationarity implies approximate optimality. We decompose the log-flow imbalance into a gradient-visible tangent component and an orthogonal parameterization residual. This yields an approximate gradient-domination property in which the terminal distribution error is controlled by the gradient norm and a precisely defined parameterization-incompleteness term. Thus, approximate stationarity leads to a nearly accurate sampler. 3. Finite-time convergence with moving training components. We analyze stochastic GFlowNet training when the sampling distribution is fixed or changes in a controlled manner and when 2

Towards Understanding the Training of GFlowNets: A Theoretical Perspective the backward policy is fixed, jointly optimized by the balance loss, or updated by a general rule. With fixed or controlled sampling and a fixed or balance-trained backward policy, the expected balance loss is bounded by 𝑂 (¯ 𝜖2 + 𝑇 −1 ), which gives expected terminal symmetric −1/2 KL of 𝑂 (¯ 𝜖+𝑇 ) under uniform coverage. For a separately updated backward policy, we characterize how fast its update must decay to ensure convergence and to preserve these rates. The remainder of the paper is organized as follows. Section 2 introduces FM, DB, and TB in a unified framework. Section 3 relates their expected balance losses to terminal-distribution mismatch. Section 4 establishes the stationarity-to-optimality guarantee, and Section 5 gives the finite-time convergence analysis. Additionally, we extend the analysis to Sub-Trajectory Balance in Appendix E.

2. Preliminaries Let X be a discrete space with positive reward 𝑅 : X → ℝ>0 . GFlowNet aims to sample 𝑥 ∈ X with Í probability 𝑅 ( 𝑥 )/𝑍 , where 𝑍 := 𝑥 ∈ X 𝑅 ( 𝑥 ) is assumed to be finite. The generation takes place on a DAG G = (S , E) with a unique initial state 𝑠0 . Every state is reachable from 𝑠0 , and the set of terminal states coincides with X. We write T for the set of complete trajectories 𝜏 = ( 𝑠0 , 𝑠1 , . . . , 𝑠𝑛 ( 𝜏 ) ), where 𝑛 ( 𝜏) is the number of edges and 𝑠𝑛 ( 𝜏 ) ∈ X. A flow network is specified by a positive edge flow function 𝐹 : E → ℝ>0 satisfying flow conservation at every nonterminal state other than 𝑠0 : ∑︁ ∑︁ 𝐹 ( 𝑠 ′ → 𝑠) = 𝐹 ( 𝑠 → 𝑠′′ ) . 𝑠′ :( 𝑠′ →𝑠 ) ∈ E

𝑠′′ :( 𝑠→𝑠′′ ) ∈ E

Its state flow 𝐹 ( 𝑠) is defined as the total flow going through state 𝑠. The network is balanced when 𝐹 ( 𝑥 ) = 𝑅 ( 𝑥 ) for every terminal state, in which case 𝐹 ( 𝑠0 ) = 𝑍 and the induced terminal distribution is 𝐹 ( 𝑥 )/ 𝐹 ( 𝑠0 ) = 𝑅 ( 𝑥 )/𝑍 . A flow network induces a forward policy and a backward policy through 𝑃 𝐹 ( 𝑠′ | 𝑠) :=

𝐹 ( 𝑠 → 𝑠′ ) , 𝐹 ( 𝑠)

𝑃 𝐵 ( 𝑠 | 𝑠′ ) :=

𝐹 ( 𝑠 → 𝑠′ ) . 𝐹 ( 𝑠′ )

GFlowNets have different variants, defined by how the flows are parameterized and the corresponding balance losses resulting from different balance conditions. In this paper, we focus on three typical types: Flow Matching (FM), Detailed Balance (DB), and Trajectory Balance (TB). Throughout the discussion, 𝜽 ∈ Θ ⊆ ℝ𝑑 collects the parameters optimized by the balance loss, while 𝝋 denotes the parameters of a backward policy when it is specified separately. For FM, both policies are induced by the edge flows and there is no separate backward block. For TB and DB, when the backward policy is jointly trained by the balance loss, its parameters are included in 𝜽; every occurrence of 𝑃 𝐵 (·; 𝝋) below is then read as 𝑃 𝐵 (·; 𝜽). Flow Matching GFlowNets(Bengio et al., 2021). An FM-GFN uses a positive edge flow function 𝐹 ( 𝑠 → 𝑠′ ; 𝜽). For 𝑠 ∈ S \ { 𝑠0 }, define the forward flow and the backward flow as ( ∑︁ 𝑅 ( 𝑠) ,𝑠 ∈ X 𝐹 → ( 𝑠) := 𝐹 ( 𝑠′ → 𝑠; 𝜽) , 𝐹 ← ( 𝑠) := Í , ′′ , otherwise 𝑠′′ :( 𝑠→𝑠′′ ) ∈ E 𝐹 ( 𝑠 → 𝑠 ; 𝜽) 𝑠′ :( 𝑠′ →𝑠 ) ∈ E

3

Towards Understanding the Training of GFlowNets: A Theoretical Perspective By extending the definition of 𝐹 ← ( 𝑠) to the initial state 𝑠0 , these edge flows induce normalized policies even before the balance conditions hold: 𝑃 𝐹 ( 𝑠 ′ | 𝑠) =

𝐹 ( 𝑠 → 𝑠 ′ ; 𝜽) , 𝐹 ← ( 𝑠)

𝑃 𝐵 ( 𝑠 | 𝑠′ ) =

𝐹 ( 𝑠 → 𝑠 ′ ; 𝜽) . 𝐹 → ( 𝑠′ )

FM enforces the balance condition 𝐹 → ( 𝑠) = 𝐹 ← ( 𝑠) on every non-initial state 𝑠 ≠ 𝑠0 using the pointwise loss  2 1 𝐹 → ( 𝑠) 𝐿FM ( 𝑠) := log ← . 2 𝐹 ( 𝑠) Detailed Balance GFlowNets(Bengio et al., 2023). A DB-GFN uses a positive state flow function 𝐹 ( 𝑠; 𝜽) on nonterminal states, a forward policy 𝑃 𝐹 ( 𝑠′ | 𝑠; 𝜽), and a backward policy 𝑃 𝐵 ( 𝑠 | 𝑠′ ; 𝝋). For ( 𝑠 → 𝑠′ ) ∈ E, define the forward flow and the backward flow as ( 𝑅 ( 𝑠′ ) 𝑃 𝐵 ( 𝑠 | 𝑠′ ; 𝝋) , 𝑠′ ∈ X 𝐹 → ( 𝑠 → 𝑠′ ) := 𝐹 ( 𝑠; 𝜽) 𝑃 𝐹 ( 𝑠′ | 𝑠; 𝜽) , 𝐹 ← ( 𝑠 → 𝑠′ ) := , 𝐹 ( 𝑠′ ; 𝜽) 𝑃 𝐵 ( 𝑠 | 𝑠′ ; 𝝋) , otherwise DB trains their equality on every edge using the pointwise loss  2 1 𝐹 → ( 𝑠 → 𝑠′ ) 𝐿DB ( 𝑠 → 𝑠 ) := log ← . 2 𝐹 ( 𝑠 → 𝑠′ ) ′

Trajectory Balance GFlowNets(Whitammer et al., 2022). A TB-GFN uses a positive estimated total flow b 𝑍 ( 𝜽), a forward policy 𝑃 𝐹 ( 𝑠′ | 𝑠; 𝜽), and a backward policy 𝑃 𝐵 ( 𝑠 | 𝑠′ ; 𝝋). For 𝜏 = ( 𝑠0 , 𝑠1 , . . . , 𝑠𝑛 ( 𝜏 ) ) ∈ T , define the forward flow and the backward flow as 𝐹 → ( 𝜏) := b 𝑍 ( 𝜽)

𝑛 (𝜏) Ö

𝑃 𝐹 ( 𝑠𝑡 | 𝑠𝑡 −1 ; 𝜽) ,

𝐹 ← ( 𝜏) := 𝑅 ( 𝑠𝑛 ( 𝜏 ) )

𝑡 =1

𝑛 (𝜏) Ö

𝑃 𝐵 ( 𝑠𝑡 −1 | 𝑠𝑡 ; 𝝋) ,

𝑡 =1

TB enforces their equality on every complete trajectory using the pointwise loss  2 𝐹 → ( 𝜏) 1 log ← . 𝐿TB ( 𝜏) := 2 𝐹 ( 𝜏) Sampling and Resampling Strategies. In practice, the losses and their gradients are estimated from sampled and possibly reweighted states, edges, or trajectories. We denote the resulting distribution by 𝜇 𝝎 , where 𝝎 collects the related parameters. It may depend on the forward policy, the backward policy, or other hyperparameters and can therefore evolve during training. Backward Policy. For DB-GFN and TB-GFN, the backward policy 𝑃 𝐵 ( 𝑠 | 𝑠′ ; 𝝋) can be chosen freely: any positive policy on the incoming edges gives compatible flows and a forward policy by propagating the terminal rewards backward. In practice, 𝑃 𝐵 is commonly fixed to be uniform or trained jointly using the TB or DB loss. Some recent work (Jang et al., 2024; Gritsaev et al., 2025) also studies separate backward-policy criteria designed to improve exploration or exploitation.

4

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Unified Framework(Hu et al., 2025). For the unified analysis, let O denote the relevant trainingobject space: S \ { 𝑠0 } for FM, E for DB, and T for TB. Write 𝜇 = 𝜇 𝝎 for a normalized training distribution on O. Let 𝐿2 ( 𝜇 ) be the space of real-valued functions on O with finite second moment, identified when they agree 𝜇 -almost surely, with ∑︁ ⟨ 𝑓 , 𝑔⟩𝜇 := 𝜇 ( 𝑜) 𝑓 ( 𝑜) 𝑔 ( 𝑜) , ∥ 𝑓 ∥ 𝜇 := ⟨ 𝑓 , 𝑓 ⟩𝜇1/2 . 𝑜∈ O →

Denote the log-flow imbalance as ℎ𝜽 ( 𝑜) := log 𝐹𝐹 ← (( 𝑜𝑜 )) . The overall objective can be written as L O ( 𝜽) :=

1 1 ∥ ℎ𝜽 ∥ 2𝜇 = 𝔼𝑜∼𝜇 [ ℎ𝜽 ( 𝑜) 2 ] . 2 2

For gradient-based analysis, ℎ𝜽 and its 𝜽-derivatives are square-integrable under 𝜇 , and differentiation may be interchanged with the loss summations in each argument being differentiated; sufficient conditions are given in Appendix D.4.

3. From Balance Loss to Distribution Matching This section connects the balance objectives to the ultimate sampling goal. We first lift the comparison between terminal distributions to complete trajectories and then express the resulting trajectory discrepancy as a weighted sum of the log-flow imbalance ℎ𝜽 . This yields a bound in terms of the expected training loss and the coverage provided by 𝜇 . The proofs are provided in Appendix B. For 𝜏 = ( 𝑠0 , 𝑠1 , . . . , 𝑠𝑛 ( 𝜏 ) ) ∈ T , define the forward and backward trajectory distributions by 𝑝𝐹 ( 𝜏) :=

𝑛 (𝜏) Ö

𝑛 (𝜏)

𝑃 𝐹 ( 𝑠𝑡 | 𝑠𝑡 −1 ) ,

𝑝𝐵 ( 𝜏) :=

𝑅 ( 𝑠𝑛 ( 𝜏 ) ) Ö 𝑍

𝑡 =1

𝑃 𝐵 ( 𝑠𝑡 −1 | 𝑠𝑡 ) ,

𝑡 =1

where parameter arguments are suppressed. The backward trajectory distribution first samples a terminal state from the reward-proportional target and then follows the backward policy to the initial state. To avoid an endless generation process, we assume that both 𝔼 𝑝𝐹 [ 𝑛 ( 𝜏)] and 𝔼 𝑝𝐵 [ 𝑛 ( 𝜏)] are finite. Í For FM and DB on infinite DAGs, we also assume that 𝑜 ∈ 𝜏 | ℎ𝜽 ( 𝑜)| is integrable under both trajectory laws; see Appendix B. Their terminal marginals are ∑︁ ∑︁ 𝑅(𝑥) = 𝑝𝐵 ( 𝜏) , 𝑥 ∈ X. 𝑝⊤ 𝑝𝐹 ( 𝜏) , 𝑝𝑅 ( 𝑥 ) := 𝐹 ( 𝑥 ) := 𝑍

𝜏:𝑠𝑛 ( 𝜏) =𝑥

𝜏:𝑠𝑛 ( 𝜏) =𝑥

The chain rule of KL divergence implies the following lemma. Lemma 3.1. Let 𝑝𝐹 , 𝑝𝐵 , 𝑝⊤ 𝐹 and 𝑝𝑅 be defined as above. We have KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) ≤ KL( 𝑝𝐹 ∥ 𝑝 𝐵 ) ,

KL( 𝑝𝑅 ∥ 𝑝⊤ 𝐹 ) ≤ KL( 𝑝 𝐵 ∥ 𝑝𝐹 ) .

For a training object 𝑜 ∈ O, define its forward and backward occupancy weights by ∑︁ ∑︁ 𝜈𝐹 ( 𝑜) := 𝑝𝐹 ( 𝜏) , 𝜈 𝐵 ( 𝑜) := 𝑝𝐵 ( 𝜏) , 𝜏 ∈ T:𝑜 ∈ 𝜏

𝜏 ∈ T:𝑜 ∈ 𝜏

where, for TB, 𝑜 ∈ 𝜏 means 𝑜 = 𝜏. Define the discrepancy distribution as ∑︁ | 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜)| 𝜈 ( 𝑜) := , where 𝑐𝜈 = | 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜)| . 𝑐𝜈

𝑜∈ O

5

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Note that for state and edge objectives, the total mass of each occupancy measure is the expected number of corresponding objects along a trajectory, while for trajectories, the total mass is one. Thus 𝑐𝜈 is at most the sum of these two total masses. To connect trajectory-level KL to balance objectives, we decompose the log-density ratio on trajectories into accumulated local imbalances plus a term that is constant across trajectories. Symmetrizing the KL divergence cancels this constant and leaves only the imbalances that the training objective controls, yielding the following theorem. ⊤ Theorem 3.2. If 𝑐𝜈 = 0, then KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) = 0. If 𝑐𝜈 > 0, then

√︄ ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ 𝑐𝜈 2

𝜈 L O ( 𝜽) , 𝜇 ∞

where

𝜈 𝜈 ( 𝑜) := sup . 𝜇 ∞ 𝜇 ( 𝑜) 𝑜∈ O

The ratio ∥ 𝜈/𝜇 ∥ ∞ represents the coverage of the discrepancy distribution by the sampling distribution. We set 𝜈 ( 𝑜)/𝜇 ( 𝑜) = +∞ if 𝜈 ( 𝑜) > 0 = 𝜇 ( 𝑜) and set it to zero if 𝜈 ( 𝑜) = 𝜇 ( 𝑜) = 0. A finite ratio automatically implies that 𝜇 covers the support of 𝜈; otherwise the bound is valid but vacuous. Although 𝜈 is infeasible in practice, the training objective is effective when 𝜇 provides good coverage. √ In particular, a bounded coverage ratio and an expected loss of 𝛿 yield an 𝑂 ( 𝛿) bound on terminal symmetric KL. Trajectory comparisons also underlie the connection between GFlowNets and variational inference (Whitammer et al., 2023). Our coverage factor parallels distribution-mismatch coefficients in RL (Agarwal et al., 2021), where the relevant measure is the difference between forward and backward occupancies. For approximate balance, Lei et al. (2026) derive total-variation guarantees from uniform residual bounds. Theorem 3.2 instead controls terminal symmetric KL through the expected squared log-ratio loss under the training measure. A detailed comparison is provided in Appendix A.1.

4. From Stationarity to Optimality Theorem 3.2 connects distribution error to log-flow imbalance and hence the balance loss. To understand what remains when optimization only reaches a stationary point, we further show that this imbalance can be decomposed into two parts: its projection onto the local tangent space and an orthogonal residual. The loss gradient controls the projected component through an effective Fisher matrix. The orthogonal residual, however, is invisible to first-order optimization, which can be interpreted as a measure of parameterization incompleteness. Therefore, this decomposition offers an approximate stationarity-to-optimality guarantee whose irreducible error is the parameterizationincompleteness term. Below we present the main results, while the proofs are available in Appendix C. For the differentiable imbalance family introduced in Section 2, define the imbalance gradient feature (called the score function below) 𝜓𝜽 ( 𝑜) := ∇𝜽 ℎ𝜽 ( 𝑜) . At a given 𝜽, the score features span the local tangent space  T𝜽 := 𝒖⊤ 𝜓𝜽 (·) : 𝒖 ∈ ℝ𝑑 . Thus ℎ𝜽 + T𝜽 is the local affine model of the imbalance. The distance from this affine space to zero tells us the residual after the best correction in this linearized model.

6

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Definition 4.1 (Parameterization Incompleteness). Let ΠT𝜇 𝜽 denote the orthogonal projection in 𝐿2 ( 𝜇 ) onto T𝜽 . Define the tangent residual by   𝜇 𝑟𝜇,𝜽 := 𝐼 − ΠT ℎ𝜽 . 𝜽 Its parameterization incompleteness under the fixed training measure 𝜇 is 𝜖𝜇 := sup ∥ 𝑟𝜇,𝜽 ∥ 𝜇 = sup min ℎ𝜽 − 𝒖⊤ 𝜓𝜽 𝜇 ∈ [0, +∞] . 𝜽 ∈ Θ 𝒖 ∈ℝ

𝜽∈Θ

𝑑

The residual is orthogonal to every score feature and hence does not appear in the loss gradient. The quantity 𝜖𝜇 bounds its norm over the parameter domain. A small value limits the imbalance that first-order optimization cannot detect under 𝜇 . Proposition 4.2 (Tabular Zero Residual). On a finite DAG, the standard positive tabular models of FM, DB, and TB satisfy ℎ𝜽 ∈ T𝜽 for every 𝜽 ∈ Θ. Consequently, for every sampling measure 𝜇 , 𝑟𝜇,𝜽 = 0

𝜖𝜇 = 0.

in 𝐿2 ( 𝜇 ) ,

Notes on forward-looking parameterizations. Forward-looking GFlowNets (FL-GFNs; Pan et al. 2023) incorporate a given intermediate energy into the balance equations. With the convention 𝑅 ( 𝑥 ) = 𝑒 − 𝐸 ( 𝑥 ) , their state-flow parameterization can be written as 𝐹 ( 𝑠; 𝜽) = 𝑒 − 𝐸 ( 𝑠 ) e 𝐹 ( 𝑠; 𝜽) ,

e 𝐹 (𝑥) = 1

( 𝑥 ∈ X) .

When parameterized independently by the log-flows, FL-GFNs differ only by a fixed translation, so Proposition 4.2 still applies. With Proposition 4.2, 𝜖𝜇 can be viewed as a reasonable measure of parameterization incompleteness. The remainder of the section concerns a general parameterized family. We require two regularity conditions to control the tangent-space component. Assumption 4.3 (Bounded Score Function). There exists 𝑀 > 0 such that, for the discrepancy distribution 𝜈 from Theorem 3.2 and every 𝜽 ∈ Θ under consideration with 𝑐𝜈 > 0, 𝔼𝑜∼𝜈 [∥ 𝜓𝜽 ( 𝑜) ∥ 2 ] ≤ 𝑀, where 𝜈 is induced at the same 𝜽. Assumption 4.4 (Effective Fisher Conditioning). Define the Fisher information as I𝜇 ( 𝜽) := 𝔼𝑜∼𝜇 [ 𝜓𝜽 ( 𝑜) 𝜓𝜽 ( 𝑜) ⊤ ] . There exists 𝜆 > 0 such that, for every 𝜽 ∈ Θ under consideration, I𝜇 ( 𝜽) † 2→2 ≤ where I𝜇 ( 𝜽) † is the Moore–Penrose pseudo-inverse.

7

1 , 𝜆

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Assumption 4.3 controls how large a tangent direction can be on the objects emphasized by 𝜈. Assumption 4.4 requires the nonzero eigenvalues of the Fisher matrix to be uniformly separated from zero. Unlike strict positive definiteness, it permits null directions caused by redundant coordinates and therefore accommodates over-parameterized models. Only the effective parameter subspace matters because null directions have zero first-order effect on the imbalance in 𝐿2 ( 𝜇 ). They need not be invisible outside the support of 𝜇 , which is why coverage remains a separate condition. Lemma 4.5 (Tangent Projection from the Gradient). Let 𝒖∗𝜇 ( 𝜽) := I𝜇 ( 𝜽) † ∇𝜽 L O ( 𝜽) .

Under Assumption 4.4, ⊤

ΠT ℎ𝜽 = 𝒖∗𝜇 ( 𝜽) 𝜓𝜽 , 𝜇

𝜽

∥ 𝒖∗𝜇 ( 𝜽) ∥ 2 ≤

1 𝜆

∥∇𝜽 L O ( 𝜽) ∥ 2 .

This projection parallels feature regression in compatible function approximation and natural policy gradient (Sutton et al., 1999; Kakade, 2001). Here the regression target is the imbalance ℎ𝜽 and the features are its derivatives ∇𝜽 ℎ𝜽 . Accordingly, the effective Fisher is the Gram matrix of imbalance features, and the residual measures local tangent approximation error. Refer to Appendix A.2 for further discussions. Together with conditioning and coverage, this geometry links balance-loss stationarity to terminal sampling accuracy in the following theorem. Theorem 4.6. Suppose Assumptions 4.3 and 4.4 hold. For every 𝜽 ∈ Θ, if 𝑐𝜈 > 0, then √︄ ! 𝜈 𝑀 ∥∇𝜽 L O ( 𝜽)∥ 2 . 𝜖𝜇 + 𝜇 ∞ 𝜆

⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ 𝑐𝜈

If 𝑐𝜈 = 0, the symmetric KL divergence on the left-hand side is zero. The coverage term is understood as +∞ whenever ∥ 𝜈/𝜇 ∥ ∞ = +∞. This theorem bounds distribution mismatch by the gradient norm and a residual term. The factor 𝑀 / 𝜆 describes the conditioning of the visible component, while the coverage ratio controls transfer from training objects to occupancy discrepancies. With finite coverage, the zero-residual tabular case has zero terminal symmetric KL at every stationary point satisfying the assumptions.

5. Convergence Rates of Stochastic GFlowNet Training Section 4 explains when a small gradient implies a small imbalance. We now ask whether stochastic training reaches such a regime, and how quickly. We first fix the sampling distribution, so that tangent geometry directly turns SGD descent into loss contraction. We then allow the sampling distribution to change, and finally allow a separate backward-policy update. The stochastic-optimization, movingobjective, and actor–critic background for is summarized in Appendix A.2; detailed proofs and regularity checks appear in Appendix D. 5.1. Fixed sampling: from geometry to convergence Recall that 𝜽 contains all parameters trained by the balance loss, including the backward parameters for joint balance training. Make the external arguments of the same expected loss explicit: L O ( 𝜽, 𝝎; 𝝋) :=

1 𝔼𝑜∼𝜇𝝎 [ ℎ𝜽,𝝋 ( 𝑜) 2 ] . 2 8

Towards Understanding the Training of GFlowNets: A Theoretical Perspective The separate argument 𝝋 is omitted for joint balance training and for FM; in those cases write ℎ𝜽 in place of ℎ𝜽,𝝋 . For now, 𝝎 and any separate 𝝋 are fixed. Joint balance training simply enlarges the optimization block: its backward-policy update is part of the descent on the same objective. Let F𝑡 contain the history before iteration 𝑡 and write 𝔼𝑡 = 𝔼[ · | F𝑡 ]. All current parameters are F𝑡 -measurable, and L𝑡 := L O ( 𝜽𝑡 , 𝝎𝑡 ; 𝝋𝑡 ) denotes their current loss. The balance update satisfies 𝜽𝑡+1 = 𝜽𝑡 − 𝜂𝑡 𝒈𝑡 ,

𝔼𝑡 ∥ 𝒈𝑡 ∥ 22 ≤ ∥∇𝜽 L𝑡 ∥ 22 + 𝜎2 .

𝔼𝑡 𝒈𝑡 = ∇𝜽 L𝑡 ,

(1)

This derivative holds the sampling distribution and any separate backward parameters fixed, including when they change between iterations below. We assume 𝔼L0 < ∞, finite second moments of all updates, and finite score second moments. All constants are deterministic and independent of 𝑡 . Assumption 5.1 (Smooth stochastic objective). The oracle satisfies equation 1. For some 𝐿 > 0, the loss has an 𝐿-Lipschitz gradient jointly in the arguments that change, on a convex admissible region containing every actual update segment. Assumption 5.2 (Uniform tangent geometry). For the residual and Fisher matrix defined in Section 4, there exist 𝜖¯ ≥ 0 and 𝜆 > 0 such that, almost surely at every iterate, ∥I𝜇𝝎𝑡 ( 𝜽𝑡 ) † ∥ 2→2 ≤

∥ 𝑟𝜇𝝎𝑡 ,𝜽𝑡 ∥ 𝜇𝝎𝑡 ≤ 𝜖¯,

1 . 𝜆

Both quantities use 𝜓𝜽 = ∇𝜽 ℎ, with any separate backward parameters fixed at their current values. Here 𝜖¯ bounds the residual along training, including changes in the external arguments. The projection identity gives an approximate Polyak–Łojasiewicz (PL) inequality: Lemma 5.3 (Approximate PL geometry). Under Assumption 5.2, at every iterate, 2L𝑡 ≤ 𝜖¯2 +

1 𝜆

∥∇𝜽 L𝑡 ∥ 22 .

(2)

Thus the gradient detects loss above the residual level. Note that for a sufficiently small step-size, smoothness gives expected descent of order 𝜂𝑡 ∥∇𝜽 L𝑡 ∥ 22 , up to an 𝑂 ( 𝜂𝑡2 ) noise term. The lemma therefore converts this into contraction of L𝑡 outside an 𝑂 (¯ 𝜖2 ) residual neighborhood. Theorem 5.4 (SGD with fixed sampling). Suppose Assumptions 5.1 and 5.2 hold. If 𝜇 is fixed and 𝑃 𝐵 is fixed or jointly balance-trained, there exist 𝑎, 𝑡0 , 𝐶 > 0 such that 𝜂𝑡 = 𝑎/( 𝑡 + 𝑡0 ) yields 𝔼L𝑇 ≤ 𝐶 𝜖¯2 +

𝐶 𝑇 + 𝑡0

.

(3)

To convert loss convergence into terminal accuracy, we require: Assumption 5.5. Assume 0 < 𝑍 < ∞. Almost surely at every iterate, policies are normalized and positive on allowed edges, and flow quantities in ℎ are finite and positive. Forward trajectories reach a terminal state and backward trajectories reach 𝑠0 almost surely. For FM and DB, trajectory sums of | ℎ | are integrable under both 𝑝𝐹,𝑡 and 𝑝𝐵,𝑡 . For 𝐵¯, 𝐶¯𝜈 < ∞, uniformly in 𝑡 , ¯, 𝑐𝜈,𝑡 ≤ 𝐵

𝜈𝑡 𝜇 𝝎𝑡

≤ 𝐶¯𝜈

whenever 𝑐𝜈,𝑡 > 0.

∞

For TB, 𝑐𝜈,𝑡 ≤ 2 automatically; finite DAGs also ensure the FM/DB mass bound and integrability. 9

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Corollary 5.6. Under Assumption 5.5, the loss bound (3) implies, for some 𝐶 > 0,   𝐶 ⊤ . 𝔼 KL( 𝑝⊤ ¯+ √ 𝐹,𝑇 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹,𝑇 ) ≤ 𝐶 𝜖 𝑇 + 𝑡0

(4)

This follows from Theorem 3.2 and Theorem 5.4. See Appendix D.2 for a detailed discussion. For a different loss function, Yu (2025) establishes best-iterate gradient convergence for FM and DB of 𝑂 (𝑇 −1/2 ) and 𝑂 (𝑇 −1/3 ), respectively, while our result provides 𝑂 (𝑇 −1/2 ) last-iterate global convergence

for FM, DB and TB. A detailed comparison is provided in Appendix A.1. 5.2. Changing sampling: retaining net descent When training samples follow the evolving policies, changing 𝜇 changes the weights in the objective. Even a successful balance step can therefore be partly offset by the next sampling update. Write Δ𝑡𝜔 := 𝝎𝑡+1 − 𝝎𝑡 . We make the following assumptions on the evolving sampling distribution. Assumption 5.7. For 𝐶𝜔 > 0, almost surely at every iterate, √︁ ∥∇𝝎 L𝑡 ∥ 2 ≤ 𝐶𝜔 2L𝑡 . Assumption 5.8. For constants 𝐾𝜃 , 𝐾2 ≥ 0, almost surely at every iterate, ∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝐾𝜃 𝜂𝑡 ∥∇𝜽 L𝑡 ∥ 2 , 𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 𝐾2 𝜂𝑡2 (∥∇𝜽 L𝑡 ∥ 22 + 𝜎2 ) . For fixed sampling, these conditions are vacuous and the constants are zero. Assumption 5.7 follows from bounded ℎ and a bounded sampling score ∥∇𝝎 log 𝜇 𝝎 ( 𝑜) ∥ 2 . Assumption 5.8 includes direct on-policy parameter copying, but modifications such as exploration mixtures, tempering, or delayed updates require their own sensitivity and update bounds. Appendix D.4 gives sufficient conditions for these two assumptions. Together with the PL inequality, these bounds leave net descent when 𝐶 𝜔 𝐾𝜃 𝜌 := √ < 1. 𝜆

Theorem 5.9 (SGD with controlled sampling). Suppose Assumptions 5.1, 5.2, 5.7, and 5.8 hold and 𝜌 < 1. If there is no separate backward update (FM, or TB/DB with fixed or jointly balance-trained 𝑃 𝐵 ), then, for suitable 𝑎, 𝑡0 > 0, 𝜂𝑡 = 𝑎/( 𝑡 + 𝑡0 ) gives the loss bound (3) and, under Assumption 5.5, the terminal bound (4). Practical interpretation of the drift condition. Theorem 5.9 identifies 𝜌 < 1 as a sufficient condition for retaining the baseline rates under changing sampling. To obtain a smaller 𝜌, we can apply fixed exploration mixtures, tempering and experience replay to reduce 𝐶𝜔 , or incorporate damped updates or target updates to reduce 𝐾𝜃 . Refer to Appendix D.5 for a detailed discussion. 5.3. Separate backward updates: controlling the extra drift For TB and DB, updating 𝝋 by another criterion changes the balance equations and need not decrease the balance loss. Define
1/2 𝑧𝑡 := 𝔼𝑡 ∥ 𝝋𝑡+1 − 𝝋𝑡 ∥ 22 , 𝑑𝑡 := (𝔼 𝑧𝑡2 ) 1/2 . Similar to the sampling parameters, we make the following assumptions. 10

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Assumption 5.10. For 𝐶 𝜑 > 0, almost surely at every iterate, √︁ ∥∇𝝋 L𝑡 ∥ 2 ≤ 𝐶 𝜑 2L𝑡 . Assumption 5.11. For constants 𝐾𝜃 , 𝐾𝜑 , 𝐾2 ≥ 0, almost surely at every iterate, ∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝐾𝜃 𝜂𝑡 ∥∇𝜽 L𝑡 ∥ 2 + 𝐾𝜑 𝑧𝑡 ,   𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 𝐾2 𝜂𝑡2 (∥∇𝜽 L𝑡 ∥ 22 + 𝜎2 ) + 𝑧𝑡2 . For fixed sampling, these conditions are vacuous and the constants are zero. Theorem 5.12 (SGD with separate backward updates). Suppose Assumptions 5.1,5.2, 5.7, 5.10, and 5.11 hold, with 𝜌 < 1. For suitable 𝑎, 𝑡0 , 𝑐, 𝐶 > 0, 𝜂𝑡 = 𝑎/( 𝑡 + 𝑡0 ) yields 𝑧2

𝔼𝑡 L𝑡+1 ≤ (1 − 𝑐𝜂𝑡 )L𝑡 + 𝐶𝜂𝑡 𝜖¯2 + 𝐶𝜂𝑡2 + 𝐶 𝑡 .

(5)

𝜂𝑡

1. If 𝑑𝑡 = 𝑜 ( 𝜂𝑡 ), then lim sup 𝔼L𝑡 ≤ 𝐶 𝜖¯2 . In particular, 𝑑𝑡 = 𝑂 ( 𝑡 − 𝑏 ) with any 𝑏 > 1 suffices. 𝑡 →∞

2. If 𝑑𝑡 = 𝑂 ( 𝜂𝑡3/2 ), equivalently 𝑑𝑡 = 𝑂 ( 𝑡 −3/2 ), then 𝔼L𝑇 = 𝑂 (¯ 𝜖2 + 𝑇 −1 ). 3. If 𝑑𝑡 = 𝑂 ( 𝑡 − 𝑏 ) with 1 < 𝑏 < 3/2, then 𝔼L𝑇 = 𝑂 (¯ 𝜖2 + 𝑇 −2( 𝑏 −1) ). Under Assumption 5.5, case (i) gives an 𝑂 (¯ 𝜖) neighborhood for expected terminal symmetric KL. In cases (ii) and (iii), the expected terminal symmetric KL is bounded, respectively, by 𝑂 (¯ 𝜖 + 𝑇 −1/2 ) and 𝑂 (¯ 𝜖 + 𝑇 − ( 𝑏 −1) ). The three additive terms in equation 5 separate representation error, SGD noise, and backward-policy drift. After taking expectation, the last is 𝐶𝑑𝑡2 /𝜂𝑡 . For the expected loss to approach the residual neighborhood it suffices that this be 𝑜 ( 𝜂𝑡 ); to retain the baseline rate it suffices that it be 𝑂 ( 𝜂𝑡2 ), the same order as SGD noise.

6. Conclusion In this paper, we develop a unified theory that connects balance loss, approximate stationarity, and sampling accuracy for FM, DB, and TB. We bound terminal symmetric KL by the square root of the expected balance loss and characterize stationary-point quality through a tangent-space residual that vanishes for standard positive tabular models. Under suitable regularity, coverage, and conditioning assumptions, we establish finite-time convergence guarantees and quantify how sampling and backward-policy drift must be controlled to preserve them. Our findings clarify the conditions under which optimization progress leads to accurate reward-proportional sampling, marking a significant advancement in understanding the training of GFlowNets. This insight is valuable for further algorithmic development and real-world applications. Moreover, our analysis builds upon and enhances existing function-approximation and distribution-shift techniques from RL and optimization, indicating their potential applicability to a broader range of fields. However, the guarantees outlined in this paper depend on adequate coverage, well-conditioned effective tangent geometry, and controlled drift. These factors require further verification in practical implementations, particularly when neural networks are involved. We recognize these limitations and view them as important directions for future research, despite the challenges they present.

11

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

References Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021. URL https://jmlr.org/papers/v22/19-736.html. Bengio, E., Jain, M., Korablyov, M., Precup, D., and Bengio, Y. Flow network based generative models for non-iterative diverse candidate generation. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 27381–27394. Curran Associates, Inc., 2021. URL https: //proceedings.neurips.cc/paper_files/paper/2021/file/e614f646836aaed9f89ce58e837e2310-Paper.pdf. Bengio, Y., Lahlou, S., Deleu, T., Hu, E. J., Tiwari, M., and Bengio, E. Gflownet foundations. The Journal of Machine Learning Research, 24(1):10006–10060, 2023. URL https://jmlr.org/papers/v24/22-0364.html. Borkar, V. S. Stochastic approximation with two time scales. Systems & Control Letters, 29(5):291–294, 1997. URL https://doi.org/10.1016/S0167-6911(97)90015-3. Bottou, L., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018. URL https://doi.org/10.1137/16M1080173. Chen, X. and Zhao, L. Finite-time analysis of single-timescale actor-critic. In Advances in Neural Information Processing Systems, volume 36, 2023. URL https://papers.nips.cc/paper_files/paper/2023/hash/ 160adf2dc118a920e7858484b92a37d8-Abstract-Conference.html. Deleu, T., Nouri, P., Malkin, N., Precup, D., and Bengio, Y. Discrete probabilistic inference as control in multi-path environments. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL https://openreview.net/forum?id=3C69sU1YkK. Deleu, T., Nouri, P., Bengio, Y., and Precup, D. Relative trajectory balance is equivalent to trust-pcl, 2025. URL https://arxiv.org/abs/2509.01632. Ding, Y., Zhang, J., and Lavaei, J. On the global optimum convergence of momentum-based policy gradient. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 1910–1934. PMLR, 2022. URL https://proceedings.mlr.press/v151/ding22a.html. Fatkhullin, I., Barakat, A., Kireeva, A., and He, N. Stochastic policy gradient methods: Improved sample complexity for Fisher-non-degenerate policies. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9827–9869. PMLR, 2023. URL https://proceedings.mlr.press/v202/fatkhullin23a.html. Fawkes, J. and Hartford, J. $f$-trajectory balance: A loss family for tuning GFlownets, generative models, and LLMs with off- and on-policy data. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=sDfu0qN6Y6. Feng, J., Wei, K., and Chen, J. Global convergence of natural policy gradient with hessian-aided momentum variance reduction, 2024. URL https://arxiv.org/abs/2401.01084v2. Preprint, version 2. GFNOrg. torchgfn: A PyTorch library for GFlowNets, version 2.4.1, 2026. URL https://github.com/GFNOrg/torchgfn/tree/v2.4.1. Source implementation, accessed September 21, 2026. 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. URL https://openreview.net/forum?id=Xj66fkrlTk. Hernandez-Garcia, A., Saxena, N., Volokhova, A., Koziarski, M., Sharma, D., Viviano, J. D., Carrier, P. L., and Schmidt, V. gflownet, 2024. URL https://github.com/alexhernandezgarcia/gflownet.

12

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Hu, E. J., Jain, M., Elmoznino, E., Kaddar, Y., Lajoie, G., Bengio, Y., and Whitammer, E. S. Amortizing intractable inference in large language models. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Ouj6p4ca60. Hu, R., Zhang, Y., Li, Z., and Huang, L. Beyond squared error: Exploring loss design for enhanced training of generative flow networks. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=4NTrco82W0. Hu, R., Chen, Y., and Huang, L. Finite-time convergence analysis of actor-critic with evolving reward. In Forty-third International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=hocdjAEAIm. Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: //proceedings.neurips.cc/paper_files/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf. Jang, H., Jang, Y., Kim, M., Park, J., and Ahn, S. Pessimistic backward policy for GFlownets. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=L8Q21Qrjmd. Kakade, S. M. A natural policy gradient. In Advances in Neural Information Processing Systems, volume 14, 2001. URL https://proceedings.neurips.cc/paper_files/paper/2001/hash/ 4b86abe48d358ecf194c56c69108433e-Abstract.html. Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2144–2203. PMLR, 09–12 Jul 2020. URL https://proceedings.mlr.press/v125/kaledin20a.html. Karimi, H., Nutini, J., and Schmidt, M. Linear convergence of gradient and proximal-gradient methods under the Polyak–Łojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases, pp. 795–811. Springer, 2016. URL https://doi.org/10.1007/978-3-319-46128-1_50. Konda, V. R. and Tsitsiklis, J. N. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2):796–819, 2004. URL https://doi.org/10.1214/105051604000000116. Koziarski, M., Rekesh, A., Shevchuk, D., van der Sloot, A., Gaiński, P., Bengio, Y., Liu, C.-H., Tyers, M., and Batey, R. Rgfn: Synthesizable molecular generation using gflownets. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 46908–46955. Curran Associates, Inc., 2024. doi: 10.52202/079017-1488. URL https://proceedings.neurips.cc/paper_files/paper/2024/file/ 53704142f230054140418ecd8857f391-Paper-Conference.pdf. Krichel, A., Malkin, N., Lahlou, S., and Bengio, Y. On generalization for generative flow networks, 2024. URL https://arxiv.org/abs/2407.03105. Lahlou, S., Deleu, T., Lemos, P., Zhang, D., Volokhova, A., Hernández-García, A., Ezzine, L. N., Bengio, Y., and Malkin, N. A theory of continuous generative flow networks. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 18269–18300. PMLR, 2023. URL https://proceedings.mlr.press/v202/lahlou23a.html. Lei, Z., Shreekumar, A., Rosenthal, J., Song, R., Cardenas, A. A., Fremont, D. J., Xu, D., Ukkusuri, S., and Celik, Z. B. Stable gflownets with tv monitoring and probabilistic guarantees, 2026. URL https://arxiv.org/abs/2605.01729. Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous Control with Deep Reinforcement Learning. In International Conference on Learning Representations, 2016. URL https://arxiv.org/abs/1509.02971.

13

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Liu, C., Zhu, L., and Belkin, M. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85–116, 2022. URL https://doi.org/10.1016/j.acha.2021.12.009. Liu, Y., Zhang, K., Başar, T., and Yin, W. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/hash/ 56577889b3c1cd083b6d7b32d32f99d5-Abstract.html. Liu, Z., Xiao, T. Z., Liu, W., Bengio, Y., and Zhang, D. Efficient diversity-preserving diffusion alignment via gradient-informed GFlownets. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=Aye5wL6TCn. Madan, K., Rector-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. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 23467–23483. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/madan23a.html. Malek, I., Laajil, A., Sharma, A., Moulines, E., and Lahlou, S. Loss-guided auxiliary agents for overcoming mode collapse in gflownets. In Proceedings of the Fortieth AAAI Conference on Artificial Intelligence and Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence and Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’26/IAAI’26/EAAI’26. AAAI Press, 2026. URL https://doi.org/10.1609/aaai.v40i29.39613. Manta, D. C., Hu, E. J., and Bengio, Y. GFlownets for causal discovery: an overview. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023. URL https://openreview.net/forum?id=25D2NyVVpr. Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. nature, 518 (7540):529–533, 2015. URL https://www.nature.com/articles/nature14236. Morozov, N., Maksimov, I., Tiapkin, D., and Samsonov, S. Revisiting non-acyclic GFlowNets in discrete environments. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 44887–44910. PMLR, 13–19 Jul 2025. URL https://proceedings.mlr.press/v267/morozov25a.html. Olshevsky, A. and Gharesifard, B. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 61(2):980–1007, 2023. doi: 10.1137/22M1483335. URL https://doi.org/10.1137/22M1483335. Pan, L., Malkin, N., Zhang, D., and Bengio, Y. Better training of GFlowNets with local credit and incomplete trajectories. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 26878–26890. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/v202/pan23c.html. Raykov, Y. and Veiga, R. Information-geometric forward policy training in gflownets, 2026. URL https://arxiv.org/abs/2608.03967. Robbins, H. and Monro, S. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3): 400–407, 1951. doi: 10.1214/aoms/1177729586. URL https://projecteuclid.org/euclid.aoms/1177729586. Schaul, T., Quan, J., Antonoglou, I., and Silver, D. Prioritized Experience Replay. In International Conference on Learning Representations, 2016. URL https://arxiv.org/abs/1511.05952. Silva, T., Alves, R. B., de Souza da Silva, E., Souza, A. H., Garg, V., Kaski, S., and Mesquita, D. When do GFlownets learn the right distribution? In The Thirteenth International Conference on Learning Representations, 2025a. URL https://openreview.net/forum?id=9GsgCUJtic.

14

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Silva, T., Souza, A. H., Rivasplata, O., Garg, V., Kaski, S., and Mesquita, D. Generalization and distributed learning of GFlownets. In The Thirteenth International Conference on Learning Representations, 2025b. URL https://openreview.net/forum?id=PJNhZoCjLh. Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2 edition, 2018. URL http://incompleteideas.net/book/the-book-2nd.html. Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, 1999. URL https://proceedings.neurips.cc/paper_files/paper/1999/hash/ 464d828b85b0bed98e80ade0a5c43b0f-Abstract.html. Tiapkin, D., Morozov, N., Naumov, A., and Vetrov, D. P. Generative flow networks as entropy-regularized rl. In International Conference on Artificial Intelligence and Statistics, pp. 4213–4221. PMLR, 2024. URL https://proceedings.mlr.press/v238/tiapkin24a.html. Whitammer, E. S., Jain, M., Bengio, E., Sun, C., and Bengio, Y. Trajectory balance: Improved credit assignment in gflownets. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 5955–5967. Curran Associates, Inc., 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/ 27b51baca8377a0cf109f6ecc15a0f70-Paper-Conference.pdf. Whitammer, E. S., Lahlou, S., Deleu, T., Ji, X., Hu, E. J., Everett, K. E., Zhang, D., and Bengio, Y. GFlownets and variational inference. In The Eleventh International Conference on Learning Representations, 2023. URL https://arxiv.org/abs/2210.00580. Yu, T. Secrets of gflownets’ learning behavior: A theoretical study, 2025. URL https://arxiv.org/abs/2505.02035. Yun, T., Zhang, D., Park, J., and Pan, L. Learning to sample effective and diverse prompts for text-to-image generation. In 2025 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 23625–23635. IEEE, 2025. URL https://openaccess.thecvf.com/content/CVPR2025/html/Yun_Learning_ to_Sample_Effective_and_Diverse_Prompts_for_Text-to-Image_Generation_CVPR_2025_paper.html. Zhang, D., Dai, H., Whitammer, E. S., Courville, A., Bengio, Y., and Pan, L. Let the flows tell: Solving graph combinatorial problems with gflownets. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 11952–11969. Curran Associates, Inc., 2023. doi: 10.52202/075280-0522. URL https://proceedings.neurips.cc/paper_files/ paper/2023/file/27571b74d6cd650b8eb6cf1837953ae8-Paper-Conference.pdf. Zhu, Y., Wu, J., Hu, C., Yan, J., hsieh, k., Hou, T., and Wu, J. Sample-efficient multi-objective molecular optimization with gflownets. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 79667–79684. Curran Associates, Inc., 2023. doi: 10.52202/075280-3487. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/ fbc9981dd6316378aee7fd5975250f21-Paper-Conference.pdf.

15

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

Appendix

A Related Work and Technical Perspective

17

A.1 Theoretical Progress in GFlowNets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 A.2 Connections to Reinforcement Learning and Optimization . . . . . . . . . . . . . . . . . 19 B Proofs for Section 3

21

C Proofs for Section 4

23

D Proofs for Section 5

26

D.1 Geometry and a common descent estimate . . . . . . . . . . . . . . . . . . . . . . . . . . 26 D.2 Fixed and controlled sampling rates

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

D.3 Separate backward updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 D.4 Sufficient conditions for sensitivity, sampling, and coverage . . . . . . . . . . . . . . . . . 28 D.5 Sampling stabilisation: exploration, replay, and stale targets . . . . . . . . . . . . . . . . 29 E Extension to Sub-Trajectory Balance

32

E.1 From SubTB loss to terminal-distribution accuracy

. . . . . . . . . . . . . . . . . . . . . 32

E.2 From SubTB stationarity to optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 E.3 Convergence of stochastic SubTB training . . . . . . . . . . . . . . . . . . . . . . . . . . 35

16

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

A. Related Work and Technical Perspective We review the theoretical development of GFlowNets, emphasizing results on sampling accuracy and learning, and then explain how our analysis connects to techniques in reinforcement learning and optimization. A.1. Theoretical Progress in GFlowNets Foundations and connections to other theories. The foundations of GFlowNets characterize reward-proportional sampling through consistent flows on a construction graph (Bengio et al., 2021, 2023). Flow Matching (FM) and Detailed Balance (DB) impose local consistency, while Trajectory Balance (TB) enforces consistency along complete generation paths (Whitammer et al., 2022). Under the corresponding support and reward-matching conditions, exact balance yields the target terminal distribution. Sub-Trajectory Balance (SubTB) interpolates between edge and complete-trajectory constraints, providing intermediate scopes for credit assignment (Madan et al., 2023). Appendix E extends our analysis to SubTB under its stated conditions. These results establish the correctness of balanced solutions; understanding an imperfectly trained, parameterized sampler requires additional analysis. Connections to other inference and learning frameworks clarify these objectives. Whitammer et al. (2023) establish expected-gradient identities between balance objectives and variational inference under specified trajectory distributions and choices of the differentiated parameter block. Tiapkin et al. (2024) reformulate GFlowNet learning as entropy-regularized RL using a particular reward and regularizer structure. More recently, Deleu et al. (2025) identify an equivalence between Relative Trajectory Balance and the KL-regularized RL method Trust-PCL. Loss-design theory further connects regression penalties to distributional objectives: Hu et al. (2025) relate expected regression gradients to gradients of divergences between flows on minimal cuts under an appropriate sampling structure. Fawkes & Hartford (2026) develop an 𝑓 -trajectory-balance family with corresponding on-policy 𝑓 -divergence gradients and target-preserving off-policy minima under their conditions. Such identities illuminate optimization signals and loss design, but require further arguments to characterize parameterized stationary points or finite-time sampling accuracy. Imbalance sensitivity and representational limits. Silva et al. (2025a) investigate how balance violations affect sampling accuracy. Their Theorem 1 bounds terminal total variation (TV) for a specified perturbation of an initially balanced network, obtained by adding and propagating flow. The bounds reveal dependence on the flow scale and target mass of downstream terminal states. This is a sensitivity result for the stated perturbation construction, rather than a general bound on arbitrary expected training loss. They also characterize expressiveness limitations of GFlowNets using 1-WL graph neural networks, propose more expressive look-ahead policies, and introduce flow consistency in subgraphs (FCS) as a distributional diagnostic with theoretical connections to TV. Their representational results concern which distributions a model class can express. Our tangent residual instead measures imbalance unexplained by local parameter derivatives at the current model. Generalization, coverage, and statistical guarantees. Krichel et al. (2024) formalize generalization and reward-perturbation stability and empirically study generalization to longer trajectories. Their stability proposition assumes globally minimized TB, a fixed uniform backward policy, and reward functions with equal total mass; the length-generalization experiments do not establish an unrestricted extrapolation guarantee. Silva et al. (2025b) develop data-dependent PAC-Bayesian bounds using bounded FCS risk, together with oracle bounds for terminal KL and DB-based risk 17

Towards Understanding the Training of GFlowNets: A Theoretical Perspective under their sampling and regularity assumptions. Their Proposition 4.2 also bounds terminal TV through an expected squared trajectory log-density ratio and a distribution-mismatch factor involving 𝜒2 divergence. Its expectation samples terminal states from a chosen distribution and then backward trajectories; the ratio uses normalized target probabilities. Our training measure can instead weight states, edges, or complete trajectories, with normalization terms eliminated by symmetrization. Thus, coverage-dependent links between average discrepancy and sampling error already exist. Their analysis motivates Subgraph Asynchronous Learning, which divides training across smaller subnetworks. Our contribution is a common occupancy-discrepancy analysis for FM, DB, and TB, and its connection to stationary-point quality and stochastic optimization. The population bounds here complement statistical generalization guarantees: coverage alone does not justify substituting empirical loss for population loss. Comparison with Yu (2025). Yu studies four aspects of learning behavior—convergence, sample complexity, implicit regularization, and robustness—using the following objectives1 (interpreted under our notations): →

←

2

𝐿ˆFM ( 𝑠) = ( 𝐹 ( 𝑠) − 𝐹 ( 𝑠)) ,

 →

𝐹 ( 𝑠) 𝐿ˆDB ( 𝑠) = ← −1 𝐹 ( 𝑠)

2

 →

,

𝐹 ( 𝑠) 𝐿ˆTB ( 𝑠) = ← −1 𝐹 ( 𝑠)

2 .

These definitions differ from the squared log-ratio objectives used in practical implementations (Hernandez-Garcia et al., 2024; GFNOrg, 2026) and in this paper. Different losses have different weighting and gradients, so their convergence statements are not interchangeable. Under tabular parameterization, fixed sampling and fixed backward policies, Yu’s Theorems 2 and 3 give 𝑂 (𝑇 −1/2 ) and 𝑂 (𝑇 −1/3 ) rates for the expected minimum squared gradient norm of FM and DB over all 𝑇 iterates. In contrast, our Theorem 5.4 give 𝑂 (𝑇 −1/2 ) rate for the expected terminal symmetric KL of the 𝑇 ’s iterate of FM, DB and TB. Comparison with Lei et al. (2026). Lei et al. study loss sensitivity, showing that small terminal TV need not prevent large balance loss, and develop guarantees in the converse direction. Their Theorem 3.5 bounds TV by 1 − 𝑒−2𝑐 when every squared TB residual is at most 𝑐2 ; the corresponding FM/DB bound is 1− 𝑒−2𝐿𝑐 for maximum trajectory length 𝐿. Their Theorem 3.6 provides a probabilistic certificate using independent forward trajectories and backward trajectories initialized from the target distribution. Its global form requires target-terminal samples; restricted-target sampling yields a subgraph certificate. They also propose adaptive reference flows to stabilize training, analyzing the associated fidelity trade-off. Relative to Lei et al., our distributional statement uses expected squared log-ratio loss under a general, possibly off-policy training measure and controls terminal symmetric KL through occupancy mass and coverage. It does not require their uniform pointwise residual condition, but it can be vacuous under poor coverage and is a population inequality rather than a finite-sample certificate. The two analyses therefore control different error metrics under different hypotheses; neither gives an unconditional tightness ordering. Extensions of the underlying environment. Other theoretical work broadens the modeling setting. Lahlou et al. (2023) formulate generalized GFlowNets using measurable spaces, flow measures, and Markov kernels, extending balance conditions and sampling correctness to continuous and hybrid 1 There is a typo in their definition of TB loss, where the backward probabilities are missing.

18

Towards Understanding the Training of GFlowNets: A Theoretical Perspective spaces under assumptions including finite absorption. Morozov et al. (2025) revisit discrete nonacyclic environments, clarifying flow definitions, the role of backward policies, and the relationship between total flow and expected trajectory length. They also analyze fixed-backward training and stability issues when the backward policy is learned. These extensions address structural questions beyond the discrete DAG setting used here; transferring our approximate-balance and optimization analysis to them requires revisiting the occupancy and trajectory assumptions. A.2. Connections to Reinforcement Learning and Optimization Compatible approximation, natural gradients, and approximate PL geometry. Compatible function approximation regresses advantages onto policy-score features, connecting least-squares coefficients to natural policy gradients (NPG) (Sutton et al., 1999; Kakade, 2001). For general policy classes, transferred approximation error evaluates this regression under a comparator policy’s occupancy, making distribution shift part of the optimality analysis (Agarwal et al., 2021). Under Fisher nondegeneracy and bounded transferred error, Liu et al. (2020) analyze NPG through compatible regression and a comparator-policy KL potential. For momentum policy gradient, Ding et al. (2022) derive a bound on the optimality gap by an approximation floor plus a multiple of the gradient norm. Related analyses develop this route for stochastic policy gradients (Fatkhullin et al., 2023) and NPG with Hessian-aided momentum variance reduction (Feng et al., 2024). In the context of GFlowNets, the regression target is log-flow imbalance and the features are its parameter derivatives. The residual is local to the tangent space and measured under the training distribution, unlike transferred advantage error under a comparator occupancy. The feature Gram matrix is the Gauss–Newton matrix of the squared-imbalance loss with the training measure fixed, and need not be a policy Fisher. Raykov & Veiga (2026) use the forward trajectory Fisher to precondition GFlowNet balance-loss gradients. This Fisher coincides with the imbalance Gram matrix for the forward-only TB block under on-policy weighting with backward policy and source flow held fixed; their decomposition and approximation guarantees concern update geometry rather than approximation-dependent gradient domination. A lower bound on the nonzero Gram eigenvalues turns the projection identity into an approximate PL inequality: squared gradient norm controls loss above the tangent-residual floor. This also connects to nonlinear least-squares and tangent-kernel analyses (Karimi et al., 2016; Jacot et al., 2018; Liu et al., 2022). Stochastic-gradient baselines and objective drift. The fixed-sampling part of Section 5 belongs to the classical stochastic-approximation lineage initiated by Robbins and Monro (Robbins & Monro, 1951) and developed for recursive algorithms and stochastic optimization in later treatments (Bottou et al., 2018). Conditional unbiasedness and a second-moment bound for the balance-gradient oracle, together with smoothness, give the usual expected-descent recursion. In our setting, the effective Fisher lower bound and the tangent residual turn this recursion into an approximate Polyak– Lojasiewicz inequality: the loss contracts until it reaches the parameterization residual floor, with an 𝑂 (𝑇 −1 ) loss rate under harmonic stepsizes. The terminal-distribution bound then takes a square root, giving the 𝑂 (𝑇 −1/2 ) rate in Corollary 5.6. This is a population result for the stated training measure, rather than a generic claim that every nonconvex SGD trajectory converges globally. When the sampling law changes with the iterate, or the backward policy is updated seperately, the objective seen by the SGD oracle thus evolves during training. Two-time-scale stochastic approximation provides the classical limiting-ODE and finite-time perspectives for coupled updates (Borkar, 1997; Konda & Tsitsiklis, 2004; Kaledin et al., 2020). The controlled-gradient and controlled-sampling assumptions in Section 5.2 and Section 5.3 make the first- and second-moment effects of this drift 19

Towards Understanding the Training of GFlowNets: A Theoretical Perspective explicit. This interpretation is related to small-gain analyses of single-timescale actor–critic methods (Olshevsky & Gharesifard, 2023; Chen & Zhao, 2023) and to finite-time analyses with an evolving reward or objective (Hu et al., 2026), but the constants here are defined for the GFlowNet sampling measure and its imbalance features.

20

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

B. Proofs for Section 3 Proof of Lemma 3.1. The chain rule for relative entropy, applied to the terminal-state map 𝜏 ↦→ 𝑠𝑛 ( 𝜏 ) , gives ∑︁
KL( 𝑝𝐹 ∥ 𝑝𝐵 ) = KL( 𝑝⊤ 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + 𝐹 ( 𝑥 )KL 𝑝𝐹 (· | 𝑠𝑛 ( 𝜏 ) = 𝑥 ) ∥ 𝑝 𝐵 (· | 𝑠𝑛 ( 𝜏 ) = 𝑥 ) 𝑥∈X

≥ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) , KL( 𝑝𝐵 ∥ 𝑝𝐹 ) = KL( 𝑝𝑅 ∥ 𝑝⊤ 𝐹) +

∑︁

𝑝𝑅 ( 𝑥 )KL 𝑝𝐵 (· | 𝑠𝑛 ( 𝜏 ) = 𝑥 ) ∥ 𝑝𝐹 (· | 𝑠𝑛 ( 𝜏 ) = 𝑥 )

𝑥∈X

⊤

≥ KL( 𝑝𝑅 ∥ 𝑝𝐹 ) . □ Proof of Theorem 3.2. For FM and DB, the integrability condition in Section 3 and Tonelli’s theorem give ∑︁ ∑︁ ∑︁ ( 𝜈𝐹 ( 𝑜) + 𝜈 𝐵 ( 𝑜))| ℎ𝜽 ( 𝑜)| = 𝔼 𝑝𝐹 | ℎ𝜽 ( 𝑜)| + 𝔼 𝑝𝐵 | ℎ𝜽 ( 𝑜)| < ∞. 𝑜∈𝜏

𝑜∈ O

𝑜∈𝜏

This condition is automatic on a finite DAG. It justifies the signed sum interchange below by Fubini’s theorem, since | 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)| ≤ 𝑝𝐹 ( 𝜏) + 𝑝𝐵 ( 𝜏). For TB, objects are complete trajectories, so no such interchange is needed. If 𝑐𝜈 = 0, then 𝑝𝐹 = 𝑝𝐵 and the TB claim is immediate. Otherwise, it suffices to consider finite coverage ratio and finite loss, since the claimed bound is vacuous in the remaining cases. Then √︄ ∑︁ 𝜈 | 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)| | ℎ𝜽 ( 𝜏)| = 𝑐𝜈 𝔼𝜈 | ℎ𝜽 | ≤ 𝑐𝜈 2 L O ( 𝜽) < ∞, 𝜇 ∞

𝜏∈ T

by Cauchy–Schwarz and change of measure. Thus the signed sums below are absolutely convergent in every nonvacuous case. According to Lemma 3.1, we have ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ KL( 𝑝𝐹 ∥ 𝑝 𝐵 ) + KL( 𝑝 𝐵 ∥ 𝑝𝐹 ) ∑︁ 𝑝𝐹 ( 𝜏) ( 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)) log = . 𝑝𝐵 ( 𝜏) 𝜏∈ T

For FM-GFN, we have 𝑛 (𝜏)

∑︁ 𝑝𝐹 ( 𝜏) 𝐹 → ( 𝑠𝑡 ) 𝑍 log = log ← + log 𝑝𝐵 ( 𝜏) 𝐹 ( 𝑠𝑡 −1 ) 𝑅 ( 𝑠𝑛 ( 𝜏 ) ) 𝑡 =1

=

𝑛∑︁ (𝜏)

ℎ𝜽 ( 𝑠𝑡 ) + log

𝑡 =1

𝑍 , 𝐹 ← ( 𝑠0 )

where the last equality uses 𝐹 ← ( 𝑠𝑛 ( 𝜏 ) ) = 𝑅 ( 𝑠𝑛 ( 𝜏 ) ). For DB-GFN, we have 𝑛 (𝜏)

log

∑︁ 𝑝𝐹 ( 𝜏) 𝑍 = ℎ𝜽 ( 𝑠𝑡 −1 → 𝑠𝑡 ) + log . 𝑝𝐵 ( 𝜏) 𝐹 ( 𝑠0 ; 𝜽) 𝑡 =1

21

Towards Understanding the Training of GFlowNets: A Theoretical Perspective For TB-GFN, we have log

𝑍 𝑝𝐹 ( 𝜏) = ℎ𝜽 ( 𝜏) + log . 𝑝𝐵 ( 𝜏) b 𝑍 ( 𝜽)

In every case, the log-density ratio is the sum of the relevant imbalances along 𝜏 plus a term that Í does not depend on 𝜏. Since 𝜏 ∈ T ( 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)) = 0, this constant cancels in the symmetrized expression. Therefore, ∑︁

( 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)) log

𝜏∈ T

=

∑︁

𝑝𝐹 ( 𝜏) 𝑝𝐵 ( 𝜏)

( 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏))

=

ℎ𝜽 ( 𝑜)

𝑜∈𝜏

𝜏∈ T

∑︁

∑︁

( 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜)) ℎ𝜽 ( 𝑜) .

𝑜∈ O

If 𝑐𝜈 = 0, the last display is zero, so the nonnegative symmetric KL divergence is also zero. Suppose 𝑐𝜈 > 0. If ∥ 𝜈/ 𝜇 ∥ ∞ = +∞, the loss bound is immediate in the extended sense under the coverage convention preceding Theorem 3.2. Otherwise, finiteness of the ratio implies that 𝜇 covers the support of 𝜈, and ∑︁ ( 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜)) ℎ𝜽 ( 𝑜) 𝑜∈ O

≤

∑︁

| 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜)| | ℎ𝜽 ( 𝑜)|

𝑜∈ O

= 𝑐𝜈

∑︁

𝜈 ( 𝑜)| ℎ𝜽 ( 𝑜)|

𝑜∈ O

≤ 𝑐𝜈

√︄ ∑︁

𝜈 ( 𝑜) ℎ𝜽 ( 𝑜) 2

𝑜∈ O

√︄

∑︁

= 𝑐𝜈

𝜇 ( 𝑜)

𝑜∈ O

√︄ ≤ 𝑐𝜈

𝜈 ( 𝑜) ℎ𝜽 ( 𝑜 ) 2 𝜇 ( 𝑜)

∑︁ 𝜈 𝜇 ( 𝑜) ℎ𝜽 ( 𝑜) 2 𝜇 ∞ 𝑜∈ O

√︄ = 𝑐𝜈 2

𝜈 L O ( 𝜽) . 𝜇 ∞

□

22

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

C. Proofs for Section 4 All functions below are evaluated on their relevant supports, and all flows and policy probabilities are positive there. Proof of Proposition 4.2. We show for each objective that the tabular tangent space contains the current imbalance pointwise. The claim for every 𝜇 then follows immediately. For DB and TB, first hold the backward policy fixed. If independent backward coordinates are included in 𝜽, assign zero to their direction; the same construction remains in the enlarged tangent space. FM. Give every edge 𝑒 an independent coordinate 𝑧𝑒 = log 𝐹 ( 𝑒). For a non-initial state 𝑠, the FM imbalance is ℎ ( 𝑠) = log 𝐹 → ( 𝑠) − log 𝐹 ← ( 𝑠) . For an incoming edge 𝑒 = ( 𝑟 → 𝑠) and an outgoing edge 𝑒 = ( 𝑠 → 𝑟 ), respectively, 𝜕ℎ ( 𝑠) 𝐹 ( 𝑒) = → > 0, 𝜕𝑧 𝑒 𝐹 ( 𝑠)

𝜕ℎ ( 𝑠) 𝐹 ( 𝑒) =− ← , 𝜕𝑧 𝑒 𝐹 ( 𝑠)

where the outgoing-edge term is absent when 𝑠 is terminal. Choose one incoming edge 𝑒𝑠 = ( 𝑝 ( 𝑠) → 𝑠) for every training state and order the states topologically. In the Jacobian submatrix formed by these columns, column 𝑒𝑠 has a nonzero diagonal entry in row 𝑠 and can have one additional nonzero entry only in the earlier row 𝑝 ( 𝑠). This triangular submatrix has nonzero diagonal, so the Jacobian has full row rank. Its range is therefore all functions on the FM training states, including ℎ. DB. Use independent log-state-flow coordinates for nonterminal states and independent softmax logits for the forward policy at each nonterminal state. Let ℎ ( 𝑠, 𝑠′ ) be the DB imbalance. Set 𝑉 ( 𝑥 ) = 0 for terminal states and define, in reverse topological order, 𝑉 ( 𝑠) = 𝔼𝑠′ ∼ 𝑃 𝐹 (· | 𝑠 ) [ ℎ ( 𝑠, 𝑠′ ) + 𝑉 ( 𝑠′ )] , ′

′

′

𝐴 ( 𝑠, 𝑠 ) = ℎ ( 𝑠, 𝑠 ) + 𝑉 ( 𝑠 ) − 𝑉 ( 𝑠) .

(6) (7)

Then 𝔼𝑠′ ∼𝑃𝐹 (· | 𝑠 ) [ 𝐴 ( 𝑠, 𝑠′ )] = 0,

ℎ ( 𝑠, 𝑠′ ) = 𝑉 ( 𝑠) − 𝑉 ( 𝑠′ ) + 𝐴 ( 𝑠, 𝑠′ ) .

A direction 𝑉 in the log-state-flow coordinates contributes 𝑉 ( 𝑠) − 𝑉 ( 𝑠′ ), with 𝑉 ( 𝑠′ ) = 0 for a terminal child. A logit direction 𝐴 contributes 𝐴 ( 𝑠, 𝑠′ ) − 𝔼𝑟∼ 𝑃 𝐹 (· | 𝑠 ) [ 𝐴 ( 𝑠, 𝑟 )] = 𝐴 ( 𝑠, 𝑠′ ) .

The combined direction is exactly ℎ ( 𝑠, 𝑠′ ) on every edge, proving that the DB imbalance lies in the tabular tangent space. TB. Use the coordinate 𝑧 = log b 𝑍 and independent softmax logits for the forward policy. For each edge, define ( ′ | 𝑠) log 𝑅 ( 𝑠′ ) , 𝑠′ ∈ X , 𝑃 ( 𝑠 𝐹 ℓ ( 𝑠, 𝑠′ ) := log − 𝑃 𝐵 ( 𝑠 | 𝑠′ ) 0, 𝑠′ ∉ X . The reward term is evaluated only at terminal states. Every complete trajectory 𝜏 = ( 𝑠0 , . . . , 𝑠𝑛 ( 𝜏 ) ) has the additive imbalance 𝑛∑︁ (𝜏) ℎ ( 𝜏) = 𝑧 + ℓ ( 𝑠𝑡 −1 , 𝑠𝑡 ) . (8) 𝑡 =1

23

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Set 𝑉 ( 𝑥 ) = 0 for every terminal state and define, in reverse topological order, 𝑉 ( 𝑠) = 𝔼𝑠′ ∼ 𝑃 𝐹 (· | 𝑠 ) [ ℓ ( 𝑠, 𝑠′ ) + 𝑉 ( 𝑠′ )] , ′

′

′

(9) (10)

𝐴 ( 𝑠, 𝑠 ) = ℓ ( 𝑠, 𝑠 ) + 𝑉 ( 𝑠 ) − 𝑉 ( 𝑠) .

The advantage is centered under 𝑃 𝐹 (· | 𝑠). Since ℓ ( 𝑠, 𝑠′ ) = 𝑉 ( 𝑠) − 𝑉 ( 𝑠′ ) + 𝐴 ( 𝑠, 𝑠′ ), summing along any trajectory gives 𝑛∑︁ (𝜏) ℎ ( 𝜏) = 𝑧 + 𝑉 ( 𝑠0 ) + 𝐴 ( 𝑠𝑡 −1 , 𝑠𝑡 ) . (11) 𝑡 =1

Choose the direction in the normalizer coordinate to be 𝑧 + 𝑉 ( 𝑠0 ) and the logit direction on edge ( 𝑠, 𝑠′ ) to be 𝐴 ( 𝑠, 𝑠′ ). Centering makes the corresponding softmax-score direction equal to 𝐴 ( 𝑠, 𝑠′ ), so the resulting trajectory direction is exactly ℎ ( 𝜏). This argument does not require equal trajectory lengths. The value is defined once per state, which makes merged paths consistent, and assigning zero value to every terminal handles multiple terminal states. Thus the TB imbalance lies in the tabular tangent space even though the number of trajectories may exceed the number of parameters. For FM, DB, and TB, we have proved ℎ𝜽 ∈ T𝜽 pointwise for every 𝜽. Hence its orthogonal residual is zero in every 𝐿2 ( 𝜇 ) and the supremum defining 𝜖𝜇 is zero. □ Proof of Lemma 4.5. Fix 𝜽 and define the linear operator ( Ψ𝜽 𝒖) ( 𝑜) = 𝒖⊤ 𝜓𝜽 ( 𝑜) .

Ψ𝜽 : ℝ𝑑 → 𝐿2 ( 𝜇 ) ,

By construction, Range( Ψ𝜽 ) = T𝜽 . Its adjoint and Gram matrix are Ψ𝜽∗ 𝑓 = 𝔼𝜇 [ 𝜓𝜽 ( 𝑜) 𝑓 ( 𝑜)] ,

Ψ𝜽∗ Ψ𝜽 = I𝜇 ( 𝜽) .

The standard pseudoinverse formula for the orthogonal projection onto the range of a finitedimensional linear operator gives 𝜇 ΠT = Ψ𝜽 I𝜇 ( 𝜽) † Ψ𝜽∗ . (12) 𝜽 By the square-integrability and differentiation conventions in Section 2, the operator above is bounded and differentiation may pass through the loss expectation, with 𝜇 and any separate 𝝋 fixed. Hence 1 2

Ψ𝜽∗ ℎ𝜽 = 𝔼𝜇 [ 𝜓𝜽 ( 𝑜) ℎ𝜽 ( 𝑜)] = ∇𝜽 𝔼𝜇 [ ℎ𝜽 ( 𝑜) 2 ] = ∇𝜽 L O ( 𝜽) .

Substituting this identity into Equation 12 yields ⊤

ΠT ℎ𝜽 = Ψ𝜽 𝒖∗𝜇 ( 𝜽) = 𝒖∗𝜇 ( 𝜽) 𝜓𝜽 . 𝜇

𝜽

The Moore–Penrose solution is the minimum-norm coefficient among all coefficients representing this projection. Assumption 4.4 then gives ∥ 𝒖∗𝜇 ( 𝜽) ∥ 2 ≤ ∥I𝜇 ( 𝜽) † ∥ 2→2 ∥∇𝜽 L O ( 𝜽) ∥ 2 ≤

1 𝜆

∥∇𝜽 L O ( 𝜽) ∥ 2 . □

24

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Proof of Theorem 4.6. If 𝑐𝜈 = 0, then 𝜈𝐹 ( 𝑜) = 𝜈 𝐵 ( 𝑜) for every 𝑜, and the signed occupancy bound established in the proof of Theorem 3.2 in Appendix B implies that the symmetric KL divergence is zero. Suppose henceforth that 𝑐𝜈 > 0, so the discrepancy distribution 𝜈 is well defined. If ∥ 𝜈/ 𝜇 ∥ ∞ = +∞, the claimed bound holds in the extended sense under the coverage convention preceding Theorem 3.2. Otherwise, finiteness of this ratio implies that 𝜇 covers the support of 𝜈, so the changes of measure below are valid. The same signed occupancy bound from Appendix B and the definition of 𝜈 give ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ∑︁
≤ 𝜈𝐹 ( 𝑜) − 𝜈 𝐵 ( 𝑜) ℎ𝜽 ( 𝑜) ≤ 𝑐𝜈 𝔼𝑜∼𝜈 | ℎ𝜽 ( 𝑜)| . 𝑜∈ O

By Definition 4.1 and Lemma 4.5, ⊤

ℎ𝜽 ( 𝑜) = 𝑟𝜇,𝜽 ( 𝑜) + 𝒖∗𝜇 ( 𝜽) 𝜓𝜽 ( 𝑜) .

For the residual component, Cauchy–Schwarz and importance sampling yield √︃ 2 ] 𝔼𝜈 | 𝑟𝜇,𝜽 | ≤ 𝔼𝜈 [ 𝑟𝜇,𝜽 √︄   =

𝔼𝜇

𝜈 2 𝑟 𝜇 𝜇,𝜽

√︄ 𝜈 ∥ 𝑟𝜇,𝜽 ∥ 𝜇 𝜇 ∞

≤ √︄

𝜈 𝜖𝜇 . 𝜇 ∞

≤

For the tangent component, Assumption 4.3 and Lemma 4.5 imply 𝔼𝜈 𝒖∗𝜇 ( 𝜽)⊤ 𝜓𝜽 ( 𝑜) ≤ ∥ 𝒖∗𝜇 ( 𝜽) ∥ 2 𝔼𝜈 ∥ 𝜓𝜽 ( 𝑜) ∥ 2 ≤

𝑀 ∥∇𝜽 L O ( 𝜽) ∥ 2 . 𝜆

Combining the two component bounds proves √︄

!

𝜈 𝑀 𝜖𝜇 + ∥∇𝜽 L O ( 𝜽) ∥ 2 . 𝜇 ∞ 𝜆

⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ 𝑐𝜈

□

25

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

D. Proofs for Section 5 We use the parameter blocks and conditional expectations defined in Section 5. Constants denoted by 𝐶 may increase between inequalities but are independent of 𝑡 and 𝜖¯. D.1. Geometry and a common descent estimate Proof of Lemma 5.3. The setup in Section 5 makes 𝒖 ↦→ 𝒖⊤ ∇𝜽 ℎ a bounded map from ℝ𝑑 into 𝐿2 ( 𝜇 ). Its range is finite-dimensional and hence closed, even when O is infinite. The interchange of differentiation and summation assumed in Section 2 gives ∇𝜽 L O = 𝔼𝜇 [ ℎ∇𝜽 ℎ], so the projection identity of Lemma 4.5 still applies. At the current parameters, write 𝑮 = ∇𝜽 L O , 𝐼 = I𝜇 ( 𝜽), and let Π be the 𝐿2 ( 𝜇 ) tangent projection. Lemma 4.5 gives the coefficient 𝒖∗ = 𝐼 † 𝑮 , so ∥ Πℎ ∥ 2𝜇 = 𝒖∗⊤ 𝐼𝒖∗ = 𝑮 ⊤ 𝐼 † 𝑮. Since 𝑟 = ℎ − Πℎ is orthogonal to Πℎ, Pythagoras and Assumption 5.2 yield 2L O = ∥ 𝑟 ∥ 2𝜇 + 𝑮 ⊤ 𝐼 † 𝑮 ≤ 𝜖¯2 +

∥ 𝑮 ∥ 22

.

𝜆

□ A common one-step estimate. We prove a recursion under the conditions of Theorem 5.12. Without a separate backward update, set 𝑧𝑡 = 0 and omit the backward sensitivity condition; the sampling bounds then reduce to Assumption 5.8. With fixed sampling, omit the sampling block and set its constants to zero. Write 𝑥𝑡 = ∥∇𝜽 L𝑡 ∥ 2 , Δ𝑡𝜃 = 𝜽𝑡+1 − 𝜽𝑡 , and Δ𝑡𝜑 = 𝝋𝑡+1 − 𝝋𝑡 . Joint smoothness gives 𝔼𝑡 L𝑡+1 ≤ L𝑡 − 𝜂𝑡 𝑥𝑡2 + ⟨∇𝝎 L𝑡 , 𝔼𝑡 Δ𝑡𝜔 ⟩ + ⟨∇𝝋 L𝑡 , 𝔼𝑡 Δ𝑡𝜑 ⟩  𝐿  + 𝔼𝑡 ∥ Δ𝑡𝜃 ∥ 22 + ∥ Δ𝑡𝜔 ∥ 22 + ∥ Δ𝑡𝜑 ∥ 22 . (13) 2 All gradients on the right are F𝑡 -measurable; no independence between updates is needed. The sensitivity and update bounds, together with ∥𝔼𝑡 Δ𝑡𝜑 ∥ 2 ≤ 𝑧𝑡 , bound the two drift terms by √︁ √︁ 𝐶 𝜔 𝐾𝜃 𝜂𝑡 2L𝑡 𝑥𝑡 + ( 𝐶𝜔 𝐾𝜑 + 𝐶 𝜑 ) 2L𝑡 𝑧𝑡 . √ √ Lemma 5.3 implies 2L𝑡 ≤ 𝜖¯ + 𝑥𝑡 / 𝜆 . With 𝛿 = 1 − 𝜌 > 0, the one-step bound becomes 𝔼𝑡 L𝑡+1 ≤ L𝑡 − 𝛿𝜂𝑡 𝑥𝑡2 + 𝐶𝜂𝑡 𝜖¯𝑥𝑡 + 𝐶 (¯ 𝜖 + 𝑥𝑡 ) 𝑧𝑡 + 𝐶𝜂𝑡2 ( 𝑥𝑡2 + 𝜎2 ) + 𝐶𝑧𝑡2 . Young’s inequality bounds the mixed terms as 𝐶𝜂𝑡 𝜖¯𝑥𝑡 + 𝐶 (¯ 𝜖 + 𝑥𝑡 ) 𝑧𝑡 ≤

𝑧2 𝜂𝑡 𝑥𝑡2 + 𝐶𝜂𝑡 𝜖¯2 + 𝐶 𝑡 . 4 𝜂𝑡 𝛿

Choose 𝜂∗ > 0 sufficiently small that 𝜂∗ ≤ 1 and the quadratic term 𝐶𝜂𝑡2 𝑥𝑡2 is at most 𝛿𝜂𝑡 𝑥𝑡2 /4 whenever 𝜂𝑡 ≤ 𝜂∗ . Absorbing 𝐶𝑧𝑡2 and the fixed noise constant gives 𝑧2

𝛿

𝔼𝑡 L𝑡+1 ≤ L𝑡 − 𝜂𝑡 𝑥𝑡2 + 𝐶𝜂𝑡 𝜖¯2 + 𝐶𝜂𝑡2 + 𝐶 𝑡 . 2 𝜂𝑡

(14)

Using 𝑥𝑡2 ≥ 𝜆 (2L𝑡 − 𝜖¯2 ) yields 𝑧2

𝔼𝑡 L𝑡+1 ≤ (1 − 𝑐𝜂𝑡 )L𝑡 + 𝐶𝜂𝑡 𝜖¯2 + 𝐶𝜂𝑡2 + 𝐶 𝑡 ,

𝑐 = 𝜆 (1 − 𝜌) > 0.

(15)

𝜂𝑡

Decrease 𝜂∗ if needed so that 𝑐𝜂∗ ≤ 1/2. Finite second moments of the updates imply integrability of 𝑥𝑡2 by conditional Jensen and (1), and of 𝑧𝑡2 by definition. Starting from 𝔼L0 < ∞, (15) therefore gives finite expected loss at each finite time and justifies taking total expectation. 26

Towards Understanding the Training of GFlowNets: A Theoretical Perspective D.2. Fixed and controlled sampling rates A scalar comparison. Choose 𝑎 > 1/𝑐, 𝑡0 ≥ max{1, 𝑎/𝜂∗ }, and 𝜂𝑡 = 𝑎/( 𝑡 + 𝑡0 ). For any 0 < 𝛼 ≤ 1, a nonnegative sequence satisfying 𝑢𝑡+1 ≤ (1 − 𝑐𝜂𝑡 ) 𝑢𝑡 +

𝐶

( 𝑡 + 𝑡0 ) 1+𝛼

obeys 𝑢𝑡 ≤ 𝐷/( 𝑡 + 𝑡0 ) 𝛼 for sufficiently large 𝐷. Indeed, choose 𝐷 ≥ 𝑡0𝛼 𝑢0 and ( 𝑐𝑎 − 𝛼) 𝐷 ≥ 𝐶 . With 𝑘 = 𝑡 + 𝑡0 , induction and convexity of 𝑘 ↦→ 𝑘 − 𝛼 give 𝑢𝑡+1 ≤

𝐷 𝑐𝑎𝐷 − 𝐶 𝐷 𝛼𝐷 𝐷 − ≤ 𝛼 − 1+𝛼 ≤ . 𝛼 1+ 𝛼 𝑘 𝑘 ( 𝑘 + 1) 𝛼 𝑘 𝑘

The contraction factors are nonnegative by the choice of 𝑡0 . Proofs of Theorems 5.4 and 5.9. In (15), set 𝑧𝑡 = 0; fixed sampling also gives 𝜌 = 0. Take total expectation and choose 𝐴 ≥ 𝐶 /𝑐 for the coefficient of 𝜂𝑡 𝜖¯2 . Then 𝑢𝑡 = (𝔼L𝑡 − 𝐴𝜖¯2 )+ satisfies 𝑢𝑡+1 ≤ (1 − 𝑐𝜂𝑡 ) 𝑢𝑡 + 𝐶𝜂𝑡2 .

The scalar comparison with 𝛼 = 1 proves (3). FM is included because both policies are induced by 𝜽; joint backward training is included because its parameters belong to the same descent block. These arguments require finite-dimensional parameters, not a finite object space. The tabular zero-residual specialization in Section 5 is restricted to finite DAGs. □ Conversion to terminal accuracy. We first justify the bound of Theorem 3.2 under Assumption 5.5 on a countable DAG. Fix the current parameters and suppress 𝑡 . Almost-sure termination makes 𝑝𝐹 , 𝑝𝐵 probability distributions on finite complete trajectories, with backward terminal marginal 𝑝𝑅 . For FM and DB the integrability condition is ∑︁ ∑︁ 𝔼𝜏∼ 𝑝𝐹 | ℎ ( 𝑜)| + 𝔼𝜏∼ 𝑝𝐵 | ℎ ( 𝑜)| < ∞. 𝑜∈𝜏

𝑜∈𝜏

Í Tonelli’s theorem identifies this quantity with 𝑜 ( 𝜈𝐹 ( 𝑜) + 𝜈 𝐵 ( 𝑜))| ℎ ( 𝑜)|. It therefore justifies the signed sum interchange in Appendix B. The telescoping identities hold on each finite trajectory, and their trajectory-independent constants cancel because 𝑝𝐹 , 𝑝𝐵 are normalized. Thus the same signed bound holds for terminal symmetric KL. For TB, there is no interchange between trajectory and object sums. The identity log( 𝑝𝐹 / 𝑝𝐵 ) = ℎ + log( 𝑍 /b 𝑍 ) and normalization give the signed bound directly. Its absolute convergence follows from ∑︁ √︁ | 𝑝𝐹 ( 𝜏) − 𝑝𝐵 ( 𝜏)| | ℎ ( 𝜏)| ≤ 𝑐𝜈 2𝐶¯𝜈 L O < ∞ 𝜏

when 𝑐𝜈 > 0; when 𝑐𝜈 = 0, 𝑝𝐹 = 𝑝𝐵 . In all three cases, the change of measure and Cauchy–Schwarz argument of Theorem 3.2 is valid on the countable object space. With the deterministic bounds from Assumption 5.5, Jensen’s inequality now gives √︁ √︁   ⊤ ¯ ¯ 𝔼 KL( 𝑝⊤ 𝐹,𝑇 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹,𝑇 ) ≤ 𝐵 2𝐶 𝜈 𝔼 L𝑇 √︁ ≤ 𝐵¯ 2𝐶¯𝜈 𝔼L𝑇 . 27

Towards Understanding the Training of GFlowNets: A Theoretical Perspective This also holds when 𝑐𝜈,𝑇 = 0, since the terminal discrepancy is then zero. Substituting (3) proves (4); the same conversion applies to the bounds below. For TB, 𝑐𝜈,𝑡 ≤ 2 follows from normalization alone. For FM and DB, Tonelli’s theorem gives ∑︁ 𝑐𝜈,𝑡 ≤ ( 𝜈𝐹,𝑡 ( 𝑜) + 𝜈 𝐵,𝑡 ( 𝑜)) = 𝔼𝜏∼ 𝑝𝐹,𝑡 𝑛 ( 𝜏) + 𝔼𝜏∼ 𝑝𝐵,𝑡 𝑛 ( 𝜏) . 𝑜

A deterministic uniform bound on this sum of expectations, conditional on the current parameters, suffices for 𝐵¯. Finiteness at each iterate alone does not give a uniform constant. On a finite DAG of maximum path length 𝐻 , one may take 𝐵¯ = 2 𝐻 for FM and DB; the absolute-imbalance integrability condition also holds automatically. D.3. Separate backward updates Proof of Theorem 5.12. Taking total expectation in (15) uses 𝑑𝑡2 = 𝔼𝑧𝑡2 = 𝔼∥ 𝝋𝑡+1 − 𝝋𝑡 ∥ 22 . With the stepsize and residual shift from Appendix D.2, 𝑢𝑡+1 ≤ (1 − 𝑐𝜂𝑡 ) 𝑢𝑡 + 𝐶𝜂𝑡2 + 𝐶

𝑑𝑡2 , 𝜂𝑡

𝑢𝑡 = (𝔼L𝑡 − 𝐴𝜖¯2 )+ .

(16)

If 𝑑𝑡 = 𝑜 ( 𝜂𝑡 ), the additive term is 𝜂𝑡 𝜉𝑡 for a deterministic sequence 𝜉𝑡 → 0. For any 𝜀 > 0, eventually 𝜉𝑡 ≤ 𝑐𝜀, so ( 𝑢𝑡+1 − 𝜀)+ ≤ (1 − 𝑐𝜂𝑡 ) ( 𝑢𝑡 − 𝜀)+ . Í Since 𝑡 𝜂𝑡 = ∞, the product of contraction factors tends to zero. Hence lim sup𝑡 𝑢𝑡 ≤ 𝜀, and letting 3/2 𝜀 ↓ 0 proves the first claim. If 𝑑𝑡 = 𝑂 ( 𝜂𝑡 ), the additional forcing is 𝑂 ( 𝜂𝑡2 ); the scalar comparison with 𝛼 = 1 proves the second claim, absorbing any finite initial segment into the constant. The terminal bounds follow from Appendix D.2. □ Intermediate decay rates. Under the hypotheses of Theorem 5.12, if 𝑑𝑡 = 𝑂 ( 𝑡 − 𝑏 ) with 1 < 𝑏 < 3/2, then 𝔼L𝑇 = 𝑂 (¯ 𝜖2 + 𝑇 −2( 𝑏 −1) ) . Indeed, the forcing in (16) is 𝑂 (( 𝑡 + 𝑡0 ) −2 + ( 𝑡 + 𝑡0 ) 1−2𝑏 ). The scalar comparison applies with 𝛼 = 2( 𝑏 − 1) ∈ (0, 1). Under Assumption 5.5, the expected terminal symmetric KL is consequently 𝑂 (¯ 𝜖 + 𝑇 − ( 𝑏 −1) ). D.4. Sufficient conditions for sensitivity, sampling, and coverage The following examples verify individual conditions used above; they do not replace the remaining hypotheses of the theorems. The derivative identities use the interchange convention in Section 2, with the external arguments made explicit in Section 5. For a countable object space, a sufficient condition for that interchange is local domination of each derivative of the summand 𝜇 𝝎 ( 𝑜) ℎ𝜽,𝝋 ( 𝑜) 2 /2 by a summable sequence on a parameter neighborhood, with finite loss at one point of that neighborhood. The mean value theorem and dominated convergence then justify differentiating the sum in each relevant coordinate. The square-integrability of ℎ and its 𝜽-derivatives also ensures that the tangent operator in Appendix C is bounded and that 𝔼𝜇 [ ℎ∇𝜽 ℎ] is finite by Cauchy–Schwarz. On a finite object space these conditions hold for continuously differentiable, finite imbalances and sampling probabilities on a parameter neighborhood.

28

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Direct sensitivity bounds. Holding sampling fixed, Cauchy–Schwarz gives   1/2 √︁ ∥∇𝝋 L O ∥ 2 = ∥𝔼𝜇 [ ℎ∇𝝋 ℎ] ∥ 2 ≤ 2L O 𝔼𝜇 ∥∇𝝋 ℎ ∥ 22 . A uniform bound on the second factor supplies 𝐶 𝜑 . For DB, ∇𝝋 ℎ is the negative backward log-policy score on an edge; for TB it is the sum of these negative scores along the trajectory. Uniformly bounded edge scores suffice for DB. For TB they suffice if 𝔼𝜏∼𝜇𝝎𝑡 𝑛 ( 𝜏) 2 is uniformly bounded; this follows in particular from bounded trajectory lengths. This second moment under the training distribution is distinct from the occupancy mass condition under 𝑝𝐹,𝑡 , 𝑝𝐵,𝑡 . For neural policies, these bounds concern derivatives with respect to the network parameters and do not follow from softmax normalization alone. For differentiable sampling probabilities on a fixed positive support, let 𝑠𝜔 ( 𝑜) = ∇𝝎 log 𝜇 𝝎 ( 𝑜). If ∥ 𝑠𝜔 ( 𝑜)∥ 2 ≤ 𝑆𝜔 and | ℎ ( 𝑜)| ≤ 𝐵ℎ uniformly, then ∥∇𝝎 L O ∥ 2 =

1 𝑆𝜔 𝐵 ℎ 𝑆𝜔 𝐵ℎ √︁ 2L O . ∥𝔼𝜇 [ ℎ2 𝑠𝜔 ] ∥ 2 ≤ 𝔼𝜇 | ℎ | ≤ 2 2 2

Thus 𝐶𝜔 = 𝑆𝜔 𝐵ℎ /2 suffices. Bounded sampling scores alone do not ensure this square-root bound for unbounded imbalances. Affine sampling updates. Suppose Δ𝑡𝜔 = 𝐴𝑡 Δ𝑡𝜃 + 𝐵𝑡 Δ𝑡𝜑 , where 𝐴𝑡 , 𝐵𝑡 are F𝑡 -measurable and their operator norms are bounded by 𝑘𝜃 , 𝑘 𝜑 . Conditional Jensen and the balance oracle give ∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝑘𝜃 𝜂𝑡 ∥∇𝜽 L𝑡 ∥ 2 + 𝑘 𝜑 𝑧𝑡 , 𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 2𝑘2𝜃 𝜂𝑡2 (∥∇𝜽 L𝑡 ∥ 22 + 𝜎2 ) + 2𝑘2𝜑 𝑧𝑡2 . Hence Assumption 5.11 holds with 𝐾𝜃 = 𝑘𝜃 , 𝐾𝜑 = 𝑘 𝜑 , and 𝐾2 = 2 max{ 𝑘2𝜃 , 𝑘2𝜑 }; omit the backward term when that block is absent. This includes parameter copying 𝝎𝑡 = 𝜽𝑡 , but the sensitivity bound and 𝜌 < 1 remain separate requirements. A nonlinear parameter map must satisfy the conditionalmean bound directly: a Lipschitz increment bound alone controls second moments, not the mean’s Taylor remainder. D.5. Sampling stabilisation: exploration, replay, and stale targets This subsection gives representative ways to verify the hypotheses of Theorem 5.9, relating familiar exploration, replay, and target-update mechanisms to its constants. Omit any separate backward update and write 𝑥𝑡 = ∥∇𝜽 L𝑡 ∥ 2 . Collect lag, refresh, and perturbation terms in ∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝐾𝜃 𝜂𝑡 𝑥𝑡 + 𝑏𝑡 ,

(17)

𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 𝐾2 𝜂𝑡2 ( 𝑥𝑡2 + 𝜎2 ) + 𝑣𝑡 .

(18)

When 𝑏𝑡 = 𝑣𝑡 = 0, these are exactly Assumption 5.8; otherwise they must be absorbed into its bounds; retaining them as forcing terms requires a corresponding extension of the descent analysis. Sampling sensitivity. Uniform-random exploration is familiar from 𝜀-greedy policies (Sutton & Barto, 2018); GFlowNet exploration also uses noisy policies and tempering (Malek et al., 2026). We analyse an 𝜀-noisy mixture over complete training objects: choose a fixed exploration distribution 𝑞 with probability 𝜀exp , and the current sampler otherwise. For 0 ≤ 𝜀exp < 1, let (𝜀)

𝜇 𝝎 = (1 − 𝜀exp ) 𝑝𝝎 + 𝜀exp 𝑞,

L𝜀 = (1 − 𝜀exp )Lfresh + 𝜀exp L𝑞 . 29

(19)

Towards Understanding the Training of GFlowNets: A Theoretical Perspective √︁ If ∥∇𝝎 Lfresh ∥ 2 ≤ 𝐶𝜔,fresh 2Lfresh , then ∥∇𝝎 L𝜀 ∥ 2 ≤

√︁

√︁ 1 − 𝜀exp 𝐶𝜔,fresh 2L𝜀 .

(20)

Thus fixed exploration changes 𝐶𝜔 , while the underlying update rule determines 𝐾𝜃 and 𝐾2 . For exploration mixed at each action, the induced trajectory law is a product of local mixtures; its sensitivity follows from the resulting trajectory score. Temperature scaling, also called softmax or Boltzmann exploration (Sutton & Barto, 2018; Malek et al., 2026), flattens a sampling distribution at temperatures above one. For logits ℓ𝝎 ( 𝑜) and fixed Í 𝜏 > 0 such that 𝑍𝜏 ( 𝝎) := 𝑜 exp( ℓ𝝎 ( 𝑜)/𝜏) < ∞ on the parameter region under consideration, and with differentiation permitted through this normalizing sum, (𝜏)

𝑝𝝎 ( 𝑜) = Í

exp( ℓ𝝎 ( 𝑜)/𝜏) , ′ 𝑜′ exp( ℓ𝝎 ( 𝑜 )/𝜏)

∇𝝎 log 𝑝𝝎( 𝜏 ) ( 𝑜) =

1 𝜏

 ∇𝝎 ℓ𝝎 ( 𝑜) − 𝔼 𝑝 (𝜏) ∇𝝎 ℓ𝝎 ( 𝑜′ ) . 𝝎

(21)

Both requirements are automatic for finitely many continuously differentiable logits. On a countable object space, a uniform local bound ∥∇𝝎 ℓ𝝎 ( 𝑜) ∥ 2 ≤ 𝐺 together with 𝑍𝜏 ( 𝝎0 ) < ∞ at a reference point suffices locally: on a convex neighborhood of radius 𝑟 about 𝝎0 , 𝑒ℓ𝝎 ( 𝑜 )/𝜏 ≤ 𝑒𝐺𝑟/𝜏 𝑒ℓ𝝎0 ( 𝑜 )/𝜏 ,

∇𝝎 𝑒ℓ𝝎 ( 𝑜 )/𝜏

2

≤

𝐺 𝐺𝑟/𝜏 ℓ𝝎 ( 𝑜 )/𝜏 𝑒 0 . 𝑒 𝜏

These summable bounds justify both normalization and its derivative. Finiteness at one temperature does not imply finiteness at a higher temperature: logits ℓ ( 𝑛) = −2 log 𝑛, 𝑛 ≥ 1, are normalizable at 𝜏 = 1 but not at 𝜏 = 2. If ∥∇𝝎 ℓ𝝎 ( 𝑜)∥ 2 ≤ 𝐺 and | ℎ ( 𝑜)| ≤ 𝐵ℎ uniformly, the score bound 2𝐺 /𝜏 and Appendix D.4 give 𝐶𝜔,𝜏 = 𝐵ℎ 𝐺 /𝜏. For actionwise tempering on trajectories of length at most 𝐻 , summing local scores gives the bound 𝐵ℎ 𝐻𝐺 /𝜏. Fixed tempering leaves 𝐾𝜃 , 𝐾2 determined by the update rule. Experience replay reuses previously collected data, as in DQN (Mnih et al., 2015); prioritized experience replay further changes their sampling weights (Schaul et al., 2016). Freezing both buffer contents and weights gives fixed sampling for the associated empirical objective. For a fixed mixture of replay and fresh samples, 𝜇 𝝎 = (1 − 𝛽 ) 𝑞 + 𝛽 𝑝𝝎 , the same argument gives √︁ 𝐶𝜔,mix = 𝛽 𝐶𝜔,fresh , 0 ≤ 𝛽 ≤ 1. (22) Coverage and the effective Fisher lower bound must be recomputed under the resulting distribution. Changing buffer contents, exploration weights, temperatures, or mixture weights adds drift. A differentiable parameterisation of these changes allows their increments to enter 𝑏𝑡 , 𝑣𝑡 ; direct changes of the sampling measure can instead be bounded in the loss. For replay, the oracle is evaluated against the empirical or mixture objective actually used. Update size and stale targets. If the sampler follows damped balance increments, 𝝎𝑡+1 = 𝝎𝑡 + 𝛼 ( 𝜽𝑡+1 − 𝜽𝑡 ) ,

0 < 𝛼 ≤ 1,

then 𝔼𝑡 Δ𝑡𝜔 = −𝛼𝜂𝑡 ∇𝜽 L𝑡 ,

𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 𝛼2 𝜂𝑡2 ( 𝑥𝑡2 + 𝜎2 ) ,

so 𝐾𝜃 = 𝛼 and 𝐾2 = 𝛼2 . This provides a direct way to limit sampler motion by scaling each new balance increment. 30

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Soft target updates, often called Polyak or exponential moving average (EMA) updates, are used in DDPG (Lillicrap et al., 2016). Here we apply that update rule to a sampling copy; the cited RL target networks are used to form learning targets. With 𝝎𝑡+1 = (1 − 𝛼) 𝝎𝑡 + 𝛼𝜽𝑡+1 and 𝒆𝑡 = 𝜽𝑡 − 𝝎𝑡 , the increment satisfies Δ𝑡𝜔 = 𝛼𝒆𝑡 + 𝛼Δ𝑡𝜃 ,

∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝛼 ∥ 𝒆𝑡 ∥ 2 + 𝛼𝜂𝑡 𝑥𝑡 .

(23)

The tracking condition ∥ 𝒆𝑡 ∥ 2 ≤ 𝜅𝜂𝑡 𝑥𝑡 reduces this to 𝐾𝜃 = 𝛼 (1 + 𝜅) and 𝐾2 = 2𝛼2 (1 + 𝜅2 ). Polyak averaging alone does not provide this tracking condition. Periodic hard target updates in DQN (Mnih et al., 2015) motivate a lazy sampling copy, held fixed between synchronisations. Let 𝐼𝑡 indicate a copy step and 𝒃𝑡 = 𝜽𝑡 − 𝝎𝑡 . Then Δ𝑡𝜔 = 𝐼𝑡 ( 𝒃𝑡 + Δ𝑡𝜃 ) ,

∥𝔼𝑡 Δ𝑡𝜔 ∥ 2 ≤ 𝐼𝑡 (∥ 𝒃𝑡 ∥ 2 + 𝜂𝑡 𝑥𝑡 ) ,

𝔼𝑡 ∥ Δ𝑡𝜔 ∥ 22 ≤ 2 𝐼𝑡 ∥ 𝒃𝑡 ∥ 22 + 2 𝐼𝑡 𝜂𝑡2 ( 𝑥𝑡2 + 𝜎2 ) .

(24)

For a fixed stale copy 𝝎𝑡 = 𝜽𝑡 − 𝑚 , Δ𝑡𝜔 = Δ𝑡𝜃− 𝑚 . A bound on 𝒃𝑡 or on the past update in terms of the current 𝑥𝑡 is therefore required before these rules can be represented by finite 𝐾𝜃 , 𝐾2 . In particular, the period 𝑚 does not imply 𝐾𝜃 = 1/𝑚. Conditionally zero-mean additive update noise preserves the first-order bound and can be accounted for by increasing 𝐾2 , 𝑣𝑡 ; biased noise also contributes to 𝑏𝑡 .

31

Towards Understanding the Training of GFlowNets: A Theoretical Perspective

E. Extension to Sub-Trajectory Balance Sub-Trajectory Balance (SubTB; Madan et al. 2023) interpolates between single-edge and completetrajectory credit assignment. This appendix extends the distributional, stationarity, and convergence results of Sections 3–5 using the additive structure of its imbalance. Coverage, tangent geometry, and drift remain explicit assumptions. Throughout this appendix, the training-object space in the unified notation of Section 2 is O = Osub . Objective and sampling measure. Let Osub be the set of nonempty finite directed subtrajectories, including single edges and complete trajectories. Use a positive state flow 𝐹 ( 𝑠; 𝜽) on nonterminal states and set 𝐹 ( 𝑥 ; 𝜽) = 𝑅 ( 𝑥 ) on terminal states. For 𝜎 = ( 𝑠𝑖 , . . . , 𝑠 𝑗 ) with length ℓ ( 𝜎) = 𝑗 − 𝑖 ≥ 1, define 𝐹 → ( 𝜎; 𝜽) := 𝐹 ( 𝑠𝑖 ; 𝜽)

𝑗 −1 Ö

𝑃 𝐹 ( 𝑠𝑘+1 | 𝑠𝑘 ; 𝜽) ,

𝑘=𝑖

←

𝐹 ( 𝜎; 𝜽, 𝝋) := 𝐹 ( 𝑠 𝑗 ; 𝜽)

𝑗 −1 Ö

(25)

𝑃 𝐵 ( 𝑠𝑘 | 𝑠𝑘+1 ; 𝝋) ,

𝑘=𝑖

𝐹 → ( 𝜎; 𝜽) ℎ𝜽,𝝋 ( 𝜎) := log ← 𝐹 ( 𝜎; 𝜽, 𝝋)

=

𝑗 −1 ∑︁

ℎDB 𝜽,𝝋 ( 𝑠𝑘 , 𝑠𝑘+1 ) .

𝑘=𝑖

The last equality follows by telescoping the intermediate state flows. A single edge gives DB, and a complete trajectory gives TB with b 𝑍 = 𝐹 ( 𝑠0 ; 𝜽). As in the main text, independently specified backward parameters are held fixed under a 𝜽 derivative, whereas jointly balance-trained backward parameters are part of 𝜽. We suppress fixed parameter arguments below and write ℎ𝜽 and ℎ when no ambiguity can arise. For a complete trajectory 𝜏 = ( 𝑠0 , . . . , 𝑠𝑛 ), normalized length weights can be written as 𝛾

𝑤𝑖 𝑗 ( 𝜏) := Í

𝛾 𝑗−𝑖 0≤ 𝑎<𝑏 ≤ 𝑛 𝛾

𝑏− 𝑎

0 ≤ 𝑖 < 𝑗 ≤ 𝑛,

,

𝛾 > 0.

Here 𝛾 denotes the SubTB weighting parameter, distinct from the effective Fisher lower bound 𝜆 . Given a trajectory sampling law 𝑞𝝎 , the induced normalized distribution on subtrajectories is ∑︁ 𝛾 𝜇 𝝎 ( 𝜎) := 𝔼𝜏∼𝑞𝝎 𝑤𝑖 𝑗 ( 𝜏)1{𝜏𝑖: 𝑗 = 𝜎 } . (26) 0≤ 𝑖< 𝑗 ≤ 𝑛 ( 𝜏 )

Its loss is the unified balance objective L O ( 𝜽, 𝝎; 𝝋) = 12 𝔼𝜇𝝎 [ ℎ2𝜽,𝝋 ], equivalently the expected weighted sum of subtrajectory losses. For each fixed finite trajectory, 𝛾 ↓ 0 gives the uniform average of its edge losses and 𝛾 → ∞ gives its complete-trajectory loss. The induced sampling weights, as well as the imbalance formula, matter for these DB/TB limits. Passing a limit through an expectation on an unbounded trajectory space requires an integrable dominating function. The results below also allow other normalized subtrajectory distributions, including those constructed from incomplete episodes. For a fixed sampling law, write 𝜇 = 𝜇 𝝎 and suppress the fixed external arguments of L O . Sampling is held fixed when differentiating the balance loss, as in Section 5. E.1. From SubTB loss to terminal-distribution accuracy Fix a deterministic, parameter-independent rule P that partitions every complete trajectory into consecutive nonempty blocks: 0 = 𝑖0 < 𝑖1 < · · · < 𝑖𝑚 = 𝑛 ( 𝜏) ,

P ( 𝜏) = {𝜏𝑖𝑟 −1 :𝑖𝑟 : 1 ≤ 𝑟 ≤ 𝑚 } . 32

Towards Understanding the Training of GFlowNets: A Theoretical Perspective This rule is used only to organize the proof; the training distribution may still average over all overlapping subtrajectories. For the forward and backward trajectory laws of Section 3, define the block occupancies ∑︁ ∑︁ 𝜈𝐹 ( 𝜎) := 𝑝𝐹 ( 𝜏) , 𝜈 𝐵 ( 𝜎) := 𝑝𝐵 ( 𝜏) . 𝜏: 𝜎 ∈ P ( 𝜏 )

𝜏: 𝜎 ∈ P ( 𝜏 )

In this subsection, 𝜈𝐹 , 𝜈 𝐵 , and the quantities below implicitly refer to this fixed rule P. Set ∑︁ | 𝜈𝐹 ( 𝜎) − 𝜈 𝐵 ( 𝜎)| 𝑐𝜈 := | 𝜈𝐹 ( 𝜎) − 𝜈 𝐵 ( 𝜎)| , 𝜈 ( 𝜎) := 𝑐𝜈

𝜎∈ O

when 𝑐𝜈 > 0. The zero-denominator conventions are those of Theorem 3.2. Since every block contains at least one edge, 𝑐𝜈 ≤ 𝔼 𝑝𝐹 |P ( 𝜏)| + 𝔼 𝑝𝐵 |P ( 𝜏)| ≤ 𝔼 𝑝𝐹 𝑛 ( 𝜏) + 𝔼 𝑝𝐵 𝑛 ( 𝜏) . (27) Proposition E.1 (SubTB loss and terminal mismatch). Suppose the positive forward and backward policies induce probability laws 𝑝𝐹 , 𝑝𝐵 on complete trajectories, 0 < 𝑍 < ∞, and 𝐹 ( 𝑠0 ) is finite and positive. Í Assume finite expected block counts and integrability of 𝜎 ∈ P ( 𝜏 ) | ℎ ( 𝜎)| under both laws. If 𝑐𝜈 = 0, then ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) = 0.

Otherwise, if ∥ 𝜈/𝜇 ∥ ∞ < ∞ and L O < ∞, then ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ∑︁ ≤ ( 𝜈𝐹 ( 𝜎) − 𝜈 𝐵 ( 𝜎)) ℎ ( 𝜎)

(28)

𝜎∈ O

√︄ ≤ 𝑐𝜈 2

𝜈 LO. 𝜇 ∞

Without finite coverage, the loss bound is understood as vacuous. Proof. The additive identity in equation 25 and the partition property give Î𝑛 ( 𝜏 ) −1 ∑︁ 𝑃 𝐹 ( 𝑠𝑘+1 | 𝑠𝑘 ) 𝐹 ( 𝑠0 ) 𝑘=0 . ℎ ( 𝜎) = log Î𝑛 ( 𝜏 ) −1 𝑃 ( 𝑠 | 𝑠 ) 𝑅 ( 𝑠 ) 𝐵 𝑘 𝑘 +1 𝑛 ( 𝜏 ) 𝜎 ∈ P (𝜏) 𝑘=0 Thus log( 𝑝𝐹 ( 𝜏)/ 𝑝𝐵 ( 𝜏)) is this sum plus log( 𝑍 / 𝐹 ( 𝑠0 )). The latter is constant in 𝜏 and cancels in the symmetric trajectory KL. Integrability permits interchanging trajectory and block sums, so ∑︁ KL( 𝑝𝐹 ∥ 𝑝𝐵 ) + KL( 𝑝𝐵 ∥ 𝑝𝐹 ) = ( 𝜈𝐹 ( 𝜎) − 𝜈 𝐵 ( 𝜎)) ℎ ( 𝜎) . 𝜎∈ O

Lemma 3.1 gives the first inequality and the case 𝑐𝜈 = 0. For 𝑐𝜈 > 0, the last sum is at most 𝑐𝜈 𝔼𝜈 | ℎ |. Cauchy–Schwarz and change of measure give the second inequality. □ Single-edge partitions recover the DB occupancy construction, while a single block per trajectory recovers the TB construction and gives 𝑐𝜈 ≤ 2. Intermediate partitions give the same identity. Summing all overlapping subtrajectories would count an edge ( 𝑠𝑘 , 𝑠𝑘+1 ) exactly ( 𝑘 + 1) ( 𝑛 − 𝑘) times, so those occurrence counts cannot replace block occupancies in this proof. The training objective may nevertheless average all overlapping subtrajectories through equation 26. Different fixed partitions can have different coverage ratios. The single-edge partition is available for positive all-length weights, subject to coverage by the trajectory sampling law; the complete-trajectory partition is natural at the TB endpoint. For restricted or incomplete sampling, the proposition is informative only when the chosen partition has finite discrepancy coverage. 33

Towards Understanding the Training of GFlowNets: A Theoretical Perspective E.2. From SubTB stationarity to optimality Use the score, tangent space, residual, and effective Fisher matrix from Section 4, now with the SubTB imbalance ℎ: T𝜽 := {𝒖⊤ 𝜓𝜽 (·) : 𝒖 ∈ ℝ𝑑 },

𝜓𝜽 ( 𝜎) := ∇𝜽 ℎ𝜽 ( 𝜎) ,

I𝜇 ( 𝜽) := 𝔼𝜇 [ 𝜓𝜽 𝜓⊤ 𝜽 ].

𝑟𝜇,𝜽 := ( 𝐼 − ΠT ) ℎ𝜽 , 𝜇

𝜽

Let 𝜖𝜇 := sup𝜽 ∈ Θ ∥ 𝑟𝜇,𝜽 ∥ 𝜇 . Assume finite loss and score second moments and justify differentiation under the expectation, for example by local summable domination on a countable object space. These requirements hold pointwise for finite positive smooth tabular models. Proposition E.2 (SubTB stationarity bound). Under the hypotheses of Proposition E.1, suppose 𝑐𝜈 > 0, ∥ 𝜈/𝜇 ∥ ∞ < ∞, and 1 𝔼𝜈 ∥ 𝜓𝜽 ( 𝜎) ∥ 2 ≤ 𝑀, ∥I𝜇 ( 𝜽) † ∥ 2→2 ≤ . 𝜆

Then

√︄

!

𝜈 𝑀 𝜖𝜇 + ∥∇𝜽 L O ∥ 2 . 𝜇 ∞ 𝜆

⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ 𝑐𝜈

(29)

Proof. As in Lemma 4.5, the normal equations give 𝒖∗𝜇 ( 𝜽) = I𝜇 ( 𝜽) † ∇𝜽 L O ,

∥ 𝒖∗𝜇 ( 𝜽) ∥ 2 ≤ 𝜆 −1 ∥∇𝜽 L O ∥ 2 .

The projection identity is ΠT𝜇 𝜽 ℎ𝜽 = ( 𝒖∗𝜇 ) ⊤ 𝜓𝜽 , so ℎ𝜽 = 𝑟𝜇,𝜽 + ( 𝒖∗𝜇 ) ⊤ 𝜓𝜽 . Finite coverage transfers the residual from 𝐿2 ( 𝜇 ) to the occupancy discrepancy. Applying the signed bound in Proposition E.1 and bounding the two components separately gives ⊤ KL( 𝑝⊤ 𝐹 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹 ) ≤ 𝑐𝜈 𝔼𝜈 | ℎ𝜽 | √︄

!

𝜈 ∥ 𝑟𝜇,𝜽 ∥ 𝜇 + 𝑀 ∥ 𝒖∗𝜇 ∥ 2 . 𝜇 ∞

≤ 𝑐𝜈

The claim follows from the definition of 𝜖𝜇 . If 𝑐𝜈 = 0, Proposition E.1 already gives zero terminal mismatch. □ Proposition E.3 (Tabular zero residual for SubTB). On a finite DAG, independent nonterminal logstate-flows and independent forward softmax logits give ℎ𝜽 ∈ T𝜽 pointwise at every positive parameter setting. Therefore 𝜖𝜇 = 0 for every sampling measure 𝜇 . The statement also holds with independent backward coordinates jointly trained by the balance loss. Proof. For the current DB edge imbalances, the construction in Appendix C defines 𝑉 ( 𝑥 ) = 0 on terminal states and 𝑉 ( 𝑠) = 𝔼𝑠′ ∼ 𝑃 𝐹 (· | 𝑠 ) [ ℎDB ( 𝑠, 𝑠′ ) + 𝑉 ( 𝑠′ )] ,

𝐴 ( 𝑠, 𝑠′ ) = ℎDB ( 𝑠, 𝑠′ ) + 𝑉 ( 𝑠′ ) − 𝑉 ( 𝑠) .

The advantage has zero conditional mean under 𝑃 𝐹 . Give the log-state-flow coordinates direction 𝑉 and the forward-logit coordinates direction 𝐴. This single direction 𝒖 satisfies 𝒖⊤ ∇ℎDB ( 𝑠, 𝑠′ ) = ℎDB ( 𝑠, 𝑠′ ) on every edge. Summing along any subtrajectory gives ℎ ( 𝜎) = 𝑉 ( 𝑠 𝑖 ) − 𝑉 ( 𝑠 𝑗 ) +

𝑗 −1 ∑︁ 𝑘=𝑖

34

𝐴 ( 𝑠𝑘 , 𝑠𝑘+1 )

Towards Understanding the Training of GFlowNets: A Theoretical Perspective and, by equation 25, 𝒖⊤ ∇ℎ ( 𝜎) =

𝑗 −1 ∑︁

𝒖⊤ ∇ℎDB ( 𝑠𝑘 , 𝑠𝑘+1 ) = ℎ ( 𝜎) .

𝑘=𝑖

The endpoint term 𝑉 ( 𝑠 𝑗 ) remains when the subtrajectory ends at an internal state. The same statewise construction works for overlapping segments and different lengths. Independent backward coordinates, if present, receive direction zero. Thus ℎ𝜽 belongs pointwise to T𝜽 and the projection residual vanishes under every 𝜇 . □ Forward-looking SubTB. For the fixed-energy parameterization of Pan et al. (2023), write 𝐹 ( 𝑠; 𝜽) = 𝑒− 𝐸 ( 𝑠 ) e 𝐹 ( 𝑠; 𝜽), with 𝐸 ( 𝑥 ) = − log 𝑅 ( 𝑥 ) and e 𝐹 ( 𝑥 ) = 1 on terminals. Direct substitution gives Î 𝑗 −1 e 𝐹 ( 𝑠𝑖 ; 𝜽) 𝑘=𝑖 𝑃 𝐹 ( 𝑠𝑘+1 | 𝑠𝑘 ) ℎ ( 𝜎) = log + 𝐸 ( 𝑠 𝑗 ) − 𝐸 ( 𝑠𝑖 ) . (30) Î 𝑗 −1 e 𝐹 ( 𝑠 𝑗 ; 𝜽) 𝑘=𝑖 𝑃 𝐵 ( 𝑠𝑘 | 𝑠𝑘+1 ) For a single edge this is FL-DB. Along a longer segment the intermediate energy evaluations cancel, leaving its endpoint difference. The effective terminal flow remains 𝑅 ( 𝑥 ), so the distributional proof is unchanged. With 𝐸 fixed, the independent coordinates log 𝐹 ( 𝑠) = log e 𝐹 ( 𝑠) − 𝐸 ( 𝑠) differ by a translation with identity derivative, and Proposition E.3 applies to the translated tabular model. 𝑓𝜽 ( 𝑠) = log e 𝐹 ( 𝑠; 𝜽), the energy term contributes no parameter derivative. If only For a neural log-flow e the log-flow output is shifted, with the policy maps and 𝜇 fixed, the score features, tangent space, and Fisher are unchanged at a fixed parameter. However, the imbalance being projected changes and need not lie in that tangent space. Along actual training, the iterates and sampling law can change, so the residual and uniform conditioning assumptions must still be checked for e 𝑓𝜽 − 𝐸. The given energy is distinct from our imbalance-dependent tangent witness 𝑉 . Learned or externally changing energies add derivative or drift terms and require a separate analysis.

E.3. Convergence of stochastic SubTB training Let L𝑡 = L O ( 𝜽𝑡 , 𝝎𝑡 ; 𝝋𝑡 ). The balance update differentiates the pointwise SubTB loss while holding sampling and any separate backward parameters fixed. The following conditions specify exactly which parts of Section 5 must be checked for this objective: 1. The SubTB oracle satisfies equation 1; the initial expected loss is finite, and the loss is jointly smooth on the admissible update region as in Assumption 5.1. Loss derivatives can be interchanged with expectations, and the required update and score second moments are finite. 2. Almost surely along training, ∥ 𝑟𝜇𝝎𝑡 ,𝜽𝑡 ∥ 𝜇𝝎𝑡 ≤ 𝜖¯ and ∥I𝜇𝝎𝑡 ( 𝜽𝑡 ) † ∥ 2→2 ≤ 1/ 𝜆 , with deterministic uniform constants. √ 3. For changing sampling, the SubTB loss satisfies Assumptions 5.7 and 5.8, with 𝐶𝜔 𝐾𝜃 / 𝜆 < 1. With a separate backward update, also require Assumption 5.10 and use Assumption 5.11 instead of Assumption 5.8. Fixed sampling omits the sampling block and has 𝜌 = 0. 4. For terminal-distribution conclusions, the hypotheses of Proposition E.1 hold at every iterate for one fixed partition rule, and 𝑐𝜈,𝑡 ≤ 𝐵¯, ∥ 𝜈𝑡 / 𝜇 𝝎𝑡 ∥ ∞ ≤ 𝐶¯𝜈 whenever 𝑐𝜈,𝑡 > 0, with deterministic finite bounds. In particular, the last item includes integrability of the absolute block-imbalance sum under both current trajectory laws. Finite DAGs ensure finite block counts and pointwise integrability, but do not automatically give a uniform coverage or conditioning bound. 35

Towards Understanding the Training of GFlowNets: A Theoretical Perspective Corollary E.4 (SubTB training rates). Under items 1–3, with fixed or jointly balance-trained 𝑃 𝐵 , suitable 𝑎, 𝑡0 > 0 and 𝜂𝑡 = 𝑎/( 𝑡 + 𝑡0 ) give 𝔼L𝑇 = 𝑂 (¯ 𝜖2 + 𝑇 −1 ) . If item 4 also holds, then ⊤ 𝔼[KL( 𝑝⊤ 𝜖 + 𝑇 −1/2 ) . 𝐹,𝑇 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹,𝑇 )] = 𝑂 (¯

(31)

For a separately updated backward policy, define 𝑧𝑡 , 𝑑𝑡 as in Section 5. Under items 1–3, 𝑧2

𝔼𝑡 L𝑡+1 ≤ (1 − 𝑐𝜂𝑡 )L𝑡 + 𝐶𝜂𝑡 𝜖¯2 + 𝐶𝜂𝑡2 + 𝐶 𝑡

(32)

𝜂𝑡

3/2 for suitable 𝑐, 𝐶 > 0. Consequently 𝑑𝑡 = 𝑜 ( 𝜂𝑡 ) gives lim sup𝑡 𝔼L𝑡 = 𝑂 (¯ 𝜖2 ); 𝑑𝑡 = 𝑂 ( 𝜂𝑡 ) preserves the 𝑂 (¯ 𝜖2 + 𝑇 −1 ) loss bound; and 𝑑𝑡 = 𝑂 ( 𝑡 − 𝑏 ), 1 < 𝑏 < 3/2, gives 𝑂 (¯ 𝜖2 + 𝑇 −2( 𝑏 −1) ). Under item 4, these imply, −1/2 respectively, an 𝑂 (¯ 𝜖) terminal neighborhood, an 𝑂 (¯ 𝜖+𝑇 ) terminal bound, and an 𝑂 (¯ 𝜖 + 𝑇 − ( 𝑏 −1) ) terminal bound.

Proof. Projection and Pythagoras give 2L𝑡 = ∥ 𝑟𝜇𝝎𝑡 ,𝜽𝑡 ∥ 2𝜇𝝎𝑡 + (∇𝜽 L𝑡 ) ⊤ I𝜇𝝎𝑡 ( 𝜽𝑡 ) † ∇𝜽 L𝑡 ≤ 𝜖¯2 + 𝜆 −1 ∥∇𝜽 L𝑡 ∥ 22 . The common descent proof in Appendix D.1 uses only this inequality, the unbiased oracle, joint smoothness, and the specified sensitivity and update bounds. Applying it to L O proves equation 32, with 𝑧𝑡 = 0 when no separate backward update is present. The scalar recursion arguments in Appendix D give the stated rates with the same stepsize choices. Finally, Proposition E.1 and Jensen’s √︁ ⊤ ⊤ inequality yield 𝔼[KL( 𝑝𝐹,𝑇 ∥ 𝑝𝑅 ) + KL( 𝑝𝑅 ∥ 𝑝𝐹,𝑇 )] ≤ 𝐵¯ 2𝐶¯𝜈 𝔼L𝑇 . □ Length moments and the limits of the extension. For a separately parameterized backward policy, 𝑗 −1 ∑︁ ∇𝝋 ℎ ( 𝜎 ) = − ∇𝝋 log 𝑃 𝐵 ( 𝑠𝑘 | 𝑠𝑘+1 ; 𝝋) . 𝑘=𝑖

If each edge score has norm at most 𝑆 𝐵 , then 𝔼𝜇𝝎𝑡 ∥∇𝝋 ℎ ∥ 22 ≤ 𝑆2𝐵 𝔼𝜇𝝎𝑡 ℓ ( 𝜎) 2 . A uniform second-moment bound on sampled subtrajectory lengths therefore supplies the backward sensitivity constant through Cauchy–Schwarz. Analogous bounded endpoint log-flow scores and forward edge scores control the balance-score second moment. These moments concern the training law 𝜇 𝝎𝑡 ; they are distinct from block-count and integrability conditions under 𝑝𝐹,𝑡 , 𝑝𝐵,𝑡 . Bounded imbalance and sampling scores give the sampling sensitivity bound as in Appendix D.4. On countable spaces, local summable domination of derivatives is one sufficient way to justify the required interchanges of differentiation and expectation. Changing 𝛾 affects coverage, conditioning, and noise through 𝜇 𝝎𝑡 ; these constants need not be uniform in 𝛾 . Tabular zero residual alone does not ensure convergence. Fixed-energy FL-SubTB in equation 30 obeys the same conditional guarantees, and replay and Polyak targets retain the qualifications of Appendix D.5.

36

Related documents

• Mixture of GFlowNets#1341888
• Mixture of GFlowNets#1318976
• GFlowNets and variational inference#798523
• GFlowNets and variational inference#797110
• Towards Understanding the Training of GFlowNets: A Theoretical Perspective#1298207