Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks

Alexandre Larouche; Audrey Durand

cs.LGJan 28, 2026

Signal from Structure: Exploiting Submodular Upper Bounds in Generative Flow Networks

Authors: Alexandre Larouche, Audrey Durand

Organizations: D´epartement d’informatique et de g´enie logiciel, Universit´e Laval, Qu´ebec, Canada · Mila - Quebec AI Institute, Montr´eal, Canada · Canada CIFAR AI Chair

Abstract

Generative Flow Networks (GFlowNets; GFNs) are a class of generative models that learn to sample compositional objects proportional to their a priori unknown value, their reward. We focus on the case where the reward has a specified, actionable structure, namely that it is submodular. We show submodularity can be harnessed to retrieve upper bounds on the reward of compositional objects that have not yet been observed. We provide in-depth analyses of the probability of such bounds occurring, as well as how many unobserved compositional objects can be covered by a bound. Following the Optimism in the Face of Uncertainty principle, we then introduce SUBo-GFN , which uses the submodular upper bounds to train a GFN. We show that SUBo-GFN generates orders of magnitude more learning signal than classical GFNs for the same number of queries to the reward function. We demonstrate the effectiveness of SUBo-GFN in terms of distribution matching and high-quality candidate generation on graph submodular tasks.

Figures & tables

Panel of Figure 1 — Figure 1: An example DAG with submodular rewards. Submodularity constrains the reward of states, ensuring that there is a diminishing return over time for the reward of later states.

Panel of Figure 2 — Figure 2: An example DAG, showing a pair of trajectories for ${\color[rgb]{1,0,0}\mathcal{T}(p_{x,c})}$ and ${\color[rgb]{0,0,1}\mathcal{T}(c)}$ for $x=\{a,b,c\}$ . This pair of trajectory yields the bound $\operatorname{UB}(\{a,b,c\}|\emptyset,c)=R(\{c\})-R(\emptyset)+R(\{a,b\})$ . The ellipsis ( $\dots$ ) indicates any number of valid transitions are taken. Bold edges and vertices highlight key elements in trajectory.

Figure 3: Normalized coverage of unobserved states (Cor. 4.1 ) w.r.t. the cardinality-actions ratio and the number of sampled trajectories (Assumption 4.1 ) ( $m\in[500,10000]$ ) for fixed $N=1000$ . The dashed line shows the $1:1$ ratio between coverage and query.

Panel of Figure 4 — Figure 4: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for random graphs with $C=15$ .

Panel of Figure 5 — Figure 5: Performance metrics of FL/TB-GFNs and SUBo-GFN variants on random graphs with $C=15$ . Strategies are trained online (dashed line) until the , then trained offline (full line) without further queries to $R$ until the end of the experiment indicated by the $\blacksquare$ .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for ER graphs.

Panel of Figure 7 — Figure 7: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for BA graphs.

Panel of Figure 8 — Figure 8: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for CM-BI graphs.

Panel of Figure 9 — Figure 9: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for CM-POW graphs.

Panel of Figure 10 — Figure 10: Normalized coverage of unobserved terminating states for SUBo-GFN with trajectories collected with $P_{F}$ and the uniform policy (Assumption 4.1 ), against the lower bound (Cor. 4.1 ) for CM-REG graphs.

Panel of Figure 11 — Figure 11: FCS, Top-100 Average Rewards, Loss, and Coverage for SUBo-GFN and FL/TB-GFNs on ER graphs.

Panel of Figure 12 — Figure 12: FCS, Top-100 Average Rewards, Loss, and Coverage for SUBo-GFN and FL/TB-GFNs on BA graphs.

Panel of Figure 13 — Figure 13: FCS, Top-100 Average Rewards, Loss, and Coverage for SUBo-GFN and FL/TB-GFNs on CM-BI graphs.

Panel of Figure 14 — Figure 14: FCS, Top-100 Average Rewards, Loss, and Coverage for SUBo-GFN and FL/TB-GFNs on CM-POW graphs.

Panel of Figure 15 — Figure 15: FCS, Top-100 Average Rewards, Loss, and Coverage for SUBo-GFN and FL/TB-GFNs on CM-REG graphs.

Category	Hyperparameter	Value
GFN Training	Learning Objective	Trajectory Balance [ 22 ]
		Forward Looking Detailed Balance [ 24 ] (FL-GFNs only)
	Query Budget	10,000
	Batch Size (sampling and offline)	16
	Learning Rate ( $P_{F},P_{B},F$ )	$10^{-4}$
	Learning Rate ( $Z$ , TB only)	$10^{-2}$

Appendix

Table 1: Hyperparameter Configuration for GFN Graph Experiments

Generative Flow Networks

Generative Flow Networks learn to sample diverse objects with probabilities proportional to their rewards.

See all 56 papers

Rooted Absorbed Prefix Trajectory Balance with Submodular Replay for GFlowNet Training
Feb 28, 2026Xi Wang, Wenbo Lu, Shengjie WangGenerative Flow Networks RL for Generative Models
Courant Institute School of Mathematics, Computing, and Data Science, New York University
Routing by Reaching: Composition of Pre-trained GFlowNets for Multi-Objective Generation
Feb 25, 2026Seokwon Yoon, Youngbin Choi, Seunghyuk Cho +3Generative Flow Networks Generative Modeling
Department of Computer Science & Engineering, POSTECH, South Korea · Graduate School of Artificial Intelligence, POSTECH, South Korea
GFlowState: Visualizing the Training of Generative Flow Networks Beyond the Reward
Apr 23, 2026Florian Holeczek, Andreas Hinterreiter, Alex Hernandez-Garcia +2Data Visualization Generative Flow Networks
Johannes Kepler University Linz · Mila – Quebec AI Institute · Eidgenössische Technische Hochschule Zürich

Feb 28, 2026J/K move · Enter open · S save

Rooted Absorbed Prefix Trajectory Balance with Submodular Replay for GFlowNet Training

Xi Wang, Wenbo Lu, Shengjie Wang

Courant Institute School of Mathematics, Computing, and Data Science, New York University

Generative Flow Networks RL for Generative Models

Open paper AskPDF arXiv

Generative Flow Networks (GFlowNets) enable fine-tuning large language models to approximate reward-proportional posteriors, but they remain prone to mode collapse, manifesting as prefix collapse and length bias. We attribute this to two factors: (i) weak credit assignment to early prefixes, and (ii) biased replay that induces a shifted, non-representative training flow distribution. We propose Rooted absorbed prefix Trajectory Balance RapTB, an objective that anchors subtrajectory supervision at the root and propagates terminal rewards to intermediate prefixes via absorbed suffix-based backups, providing dense prefix-level learning signals. To mitigate replay-induced distribution shift, we further introduce SubM, a submodular replay refresh strategy that promotes both high reward and diversity. Empirically, on tasks such as molecule generation with LLM using SMILES strings, RapTB combined with SubM consistently improves optimization performance and molecular diversity while preserving high validity. The code is released on https://github.com/ComDec/ChemGFN.

Abstract

Generative Flow Networks

Explore similar work

Rooted Absorbed Prefix Trajectory Balance with Submodular Replay for GFlowNet Training

Routing by Reaching: Composition of Pre-trained GFlowNets for Multi-Objective Generation

GFlowState: Visualizing the Training of Generative Flow Networks Beyond the Reward