- Rating
- 3
- Confidence
- 1
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper explores the statistical scalability of GFlowNets. The primary contributions are the derivation of a theoretical lower bound on regret, followed by first-order and second-order analyses establishing upper bounds for a proposed learning algorithm. These bounds characterise the statistical scalability of GFlowNets in terms of the representation dimension (d), trajectory horizon (H), and number of training trajectories (K), rather than explicitly depending on the potentially enormous size of the underlying state space (|S|). The analysis also identifies a minimum sample requirement related to d, while the second-order upper bound demonstrates logarithmic dependence on the number of training trajectories K. The conclusion is that GFlowNets can remain statistically scalable even with enormous state spaces, provided their underlying value structure can be captured by a compact shared representation. Without such compression, the effective representation dimension d may grow to be comparable to the size of the state space.
Critical strengths
-
The paper addresses a fundamental question of GFlowNets and provides comprehensive theoretical analysis.
-
While the paper is dense with math, I find the non-math parts easy to read, and the paper is well structured and motivated.
Critical weaknesses
-
Assuming the derivations are correct, would the lower and upper bounds derived in the paper, which scale with d, H, and K, sufficiently demonstrate that GFlowNet scalability is not dependent on |S|? First, could d and H themselves scale with |S|, meaning that more complex learning problems may naturally require larger representations and longer trajectories? Second, while the derived bounds do not explicitly depend on |S|, could other characteristics of the state-space structure still be relevant to a tighter characterisation of learning difficulty? Third, |S| and H may be correlated in certain construction graphs, so a large H could also imply a large |S|. I wonder whether the paper sufficiently distinguishes between demonstrating scalability under the stated assumptions and establishing that scalability is fundamentally independent of |S|.
-
Practical significance and empirical demonstration. The paper stops right after the second-order proof. It would be useful to demonstrate, at least through a toy example, what the identified K = Ω(d) sample requirement looks like in practice, particularly how the average regret changes around the data-starved regime. Also, what is considered a practical choice of d, and how would such a compact representation be obtained for an actual GFlowNet task? It would also be interesting to demonstrate whether increasing |S| while keeping d fixed would produce the expected scalability behaviour.
Questions for authors
While my mathematical background does not allow me to fully verify the correctness of the proofs, I find the paper generally interesting. My first question in Weakness 1 is perhaps more about the definitive tone of the paper in claiming that GFlowNet scalability depends on d rather than |S|. The second question is more about gaining a practical understanding of how the theoretical results should be interpreted and evaluated in real-world settings. Nevertheless, I remain positive about the paper.
7 comments
Response to Weakness (Part 2)
-
We thank the reviewer for this constructive suggestion. We agree that empirical illustrations would help demonstrate the practical implications of our theoretical results. We would like to response this from three perspectives:( 1) our theoretical contributions, (2) connections to practical GFlowNet algorithms, and (3) supporting empirical evidence from existing studies.
(1). Since the sources of GFlowNet diffuculty is the enormous size of . The bottlneck can be understood as how to efficiently epxlorate the state space, so that the exact enumerate of all state is avoided. The lower-bound setting eliminates this exploration difficulty by allowing oracle samples directly from the target distribution, so that a regret benchmark is establised. Our upper-bound algorithm has no access to such oracle information and aim at addressing the exploration challenge by constructing a deterministic confidence width, .
-
This bonus leverages information from visited states and the shared low-dimensional Bellman representation to construct globally valid confidence bounds for both visited and unvisited states. Under our assumptions, these bounds yield optimistic value estimates satisfying for all states, thereby enabling efficient exploration of unvisited regions through optimistic policy updates.
-
We acknowledge that our regression formulation is idealized. In practical neural GFlowNets, the representation and its coefficients are jointly represneted by neural networks. The confidence width may not be readlity obtained or automatically guaranteed, when the representation itself is learned by aneural networks.
-
Nevertheless, our analysis provides a theoretical explanation for how neural GFlowNets may succeed in seemingly intractable combinatorial spaces: when the underlying task admits a sufficiently compact representation and the network successfully captures this structure, information acquired from sampled trajectories can generalize to a much larger collection of unvisited states. In other words, without such a compact representation, GFlowNet learning may become computationally intractable. Our confidence-based optimism provides an idealized theoretical mechanism for uncertainty-guided generalization and exploration.
(2). Furthermore, we have added Appendix F: Theoretical Insights into Practical GFlowNet Training, which establishes a direct mathematical connection between our Bellman residual analysis and commonly used GFlowNet training objectives, including Subtrajectory Balance (Sub-TB), Detailed Balance (DB) and Trajectory Balance (TB). In particular, define the optimistic Bellman residual by (we previously use $Q_h^k(\cdot,\cdot) $ ). Using the implicit flow representation , we establish the identity
\begin{aligned} \delta_{\mathrm{SubTB}}^k(\tau_{i:j})&=\log\frac{F_i^k(s_i)P_{\pi^k}(\tau_{i:j}\mid s_i)}{F_j^k(s_j)P_B(\tau_{i:j}\mid s_j)}= \sum_{h=i}^{j-1}\delta_h^k(s_h,s_{h+1}). \end{aligned}
The classical Detailed Balance (DB) and Trajectory Balance (TB) residuals are recovered by taking and , respectively. Consequently, our second-order Bellman residual analysis also yields cumulative flow-balance error bounds associated with these practical training objectives. This correspondence demonstrates that our theoretical framework is closely connected to the flow-consistency principles underlying practical GFlowNet algorithms, even though their neural implementations need not satisfy our fixed-feature assumptions.
-
Response to Weakness (Part 3)
-
(Continue)
(3). A more concrete empirical illustration of exploiting task structure is SUBo-GFN (Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks, Larouche and Durand, 2026), which leverages the submodularity of reward functions.
-
By the diminishing-returns property, for an unobserved terminal object , an element , and , the reward satisfies
.
Since , this provides an optimistic upper bound on the terminal value:
.
The reasoning is that only terminal reward is externally specified by the task, whereas the DAG construction () ad intermediate reward (i.e. the logorithm of backward policy, ) are specified by the users, and are not considered as the sources of learning challenge. Therefore, SUBo-GFN only focus on bounding the terminal values (i.e. rewards) for algorithm simplicity.
-
This inequality allows previously observed rewards to provide upper bounds on the rewards of unvisited combinatorial objects, without explicitly evaluating every terminal state. In their submodular graph experiments, SUBo-GFN reports approximately 30–171 times more terminal states receiving informative training signals than conventional GFlowNets, together with improved distribution-matching performance.
-
This mechanism is conceptually analogous to the optimism bonus in our framework, where the low-dimensional Bellman representation and deterministic regression confidence bound yield
with . Our framework extends this structural generalization to continuation values at every stage, enabling recursive optimism and end-to-end regret analysis under a mathematically tractable low-dimensional Bellman representation assumption.
Therefore, while SUBo-GFN focus on practical implementable under the optimism-under-uncertainty principle, our work formalizes this principle through a more explicit and mathematically tractable low-dimensional Bellman representation assumption, establishing corresponding regret guarantees. This perspective also offers a possible theoretical explanation for the success of GFlowNets that do not explicitly incorporate task-specific structural properties.
We acknowledge that these existing experiments do not directly verify the predicted behavior around or the effect of increasing while holding fixed. Our contribution is a generalized theoretical characterization of these phenomena, and controlled empirical validation remains a valuable direction for future work.
-
Response to Weakness (Part 1)
First of all, we would like to express our sincere gratitude for your encouraging and constructive comments.
We would like organize our response into three aspects (1) notation and representation dimension, (2) the fundamental challenge of GFlowNet learning, and (3) the direct answer your questions.
The d is the per-layer representation dimension of Sh, rather than the whole state space S=∪Sh. Different layers may have different representation dimensions dh; for notational simplicity, we use a common dimension d.
We have uploaded a revised manuscript to make this clearer in the assumption 2.2 (previously Assumption 4.4). Besides, We have also clarified the Bellman representation as $ V(s')=\phi_{h+1}(s')^\top\theta_{h+1}(V)$, instead of the previous notation V(s′)=ϕh(s,s′)⊤θh(V). Since the continuation value depends only on the successor state (s'), the revised formulation explicitly reflects the intended successor-state representation without changing our theoretical analysis.
In the GFlowNet setting, only the reward R over terminal space SH:=X is externally specified by the task. The fundamental challenge is that the terminal state space X can be prohibitively large, making exact marginalization and direct sampling from P⋆(x)=R(x)/Z⋆ computationally intractable. The DAG construction (S0,…,SH−1) and intermediate reward ρ(s,s′) (i.e. the logorithm of backward policy, logπ(s∣s′)) are specified by the users, and therefore are not considered as the sources of challenge.
Our objective is to formally characterize structural conditions under which GFlowNet learning can scale with an effective representation dimension rather than the cardinality of the state space, thereby providing a theoretical pathway toward addressing this challenge. Especially, at the terminal stage, our linear Bellman representation assumption requires
VH(x)=logR(x)=ϕH(x)⊤θH,θH∈Rd,
where potentially d≪∣X∣. The significance of this assumption is that values associated with an enormous number of states can be represented through only d coefficients per stage. Consequently, information collected from visited states can generalize to unvisited states through their shared representation.
Returning to your questions:
d measures the effective representation dimension of each layer, whereas H is the numer of total layers of user-specified DAG construction. So d is a direct alternative of ∣Sh∣, and neither d or ∣Sh∣ depends on H;
As clarified above, the fundamental challenge in GFlowNet learning is the potentially enormous terminal state space (mainly X as the intermediate reward . Therefore, analyzing the state space compressibility provides a direct theoretical approach to understanding when GFlowNet learning can be sample-efficient.
As explained above, d is identified as the compressed dimension for each layer Sh, (especially for SH). Therefore, d and S does not involve H. A large H may give a large set of (S0,…,Sh−1). However, expect X and R, (S0,…,Sh−1) and associated reward ρ(sh,sh+1) is freely specified by the user to facilitate the modeling over (X,R), thereby not considered as the bottleneck of GFlownet learning in general.
Finally, our lower and upper bounds already take your concern into account: both identify regret linear dependence on dH or dH2. Here, dH represents the total representation dimension across all H layers. As demonstraed in our proof precedure, the appearing of factor H or H2, just arises from accumulating the regret contributions at each layer h∈[1,H].