{"id":"9c046091-bc79-43d2-bab8-44cad2e5cde3","arxiv_id":"2502.07735","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"In cyclic discrete environments, GFlowNet flows are expected visit counts, and training a non-acyclic GFlowNet with the smallest expected trajectory length is equivalent to minimizing total flow.","lead":"This paper rebuilds the theory of GFlowNets for finite state graphs that contain cycles, defining flows as expected visit counts and showing the standard training losses still have a unique reward-matching solution. It also proves that in cyclic environments, the shortest expected sampling time and the smallest total flow are the same target, and generalizes the known equivalence between GFlowNets and entropy-regularized reinforcement learning to this setting.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.11 overreaches: the Flow Matching loss (Bengio et al., 2021) never involves the fixed backward policy PB, so its non-acyclic optima form a continuum of reward-matching policies and it cannot learn the unique corresponding PF; the core theorems are otherwise sound.","rationale":"I verified the paper's core theory in good faith before settling on a concern. Lemma 3.4 is sound: with PB > 0 on all edges, the reversed walk has return probability p_s < 1 for every intermediate state (a simple s0-to-s path reversed gives a positive-probability escape to the absorbing s0), so expected visit counts are bounded by geometric series and absorption is almost sure. Definition 3.5's flows pass the flow-matching and detailed-balance tests in Proposition 3.6 (the Fubini step is justified by finite expected length). Proposition 3.7's converse is correct: the ratio C(s) satisfies a linear system whose only positive solution is constant, via the max/min argument; the case analysis correctly separates sf ∈ Smax from sf ∉ Smax using F > 0 on all edges. Proposition 3.8's telescoping product works because F(s0) = F(sf). Proposition 3.10 is correct, and a nice consequence of almost-sure absorption is that the termination distribution of the PB-induced process equals PB(· | sf), so reward matching requires PB(x | sf) = R(x)/Z, a known-Z constraint that is standard and acknowledged. Theorem 3.13 checks out: V = log Z − KL(P^π_T || P), the KL minimizer is the unique PF, and Q = log F satisfies the soft Bellman equations via Proposition 3.6. The theory is genuinely sound, and the reader's high confidence in the framework is justified, as is the paper's reproducible code and the Figure 1 demonstration that DB and SDB with fixed PB converge to the predicted expected trajectory length. My concern targets the universal quantifier of Corollary 3.11. FM (Bengio et al., 2021) is listed explicitly but is a functional of flows alone: its zero set is the continuum of flow-matching flows with the correct terminal values, parameterized by circulations, so it cannot select the unique PB-induced PF; the objective is PB-independent. Appendix C.1's own admission that FM does not admit a backward-policy parameterization contradicts the corollary's breadth. The claim is true for DB, TB, and SubTB, whose objectives involve PB and whose zero sets encode detailed or trajectory balance, and the experiments support exactly those losses. I recommend CONDITIONAL acceptance: qualify Corollary 3.11 to PB-sensitive losses, since the overstatement is in the paper's main practical claim, not in its theorems.","tokens_in":29710,"tokens_out":44729,"duration_ms":383293,"concrete_test":"Analytical check on the minimal 2-cycle graph s0 → b, b → c, c → b, b → sf, c → sf: fix a strictly positive, reward-compatible PB. Solve the linear system (17) in Appendix B.4 to get the unique expected-visit-count flow F*, then add δ to both F(b → c) and F(c → b). This perturbed flow still satisfies flow matching (3) and the terminal constraint F(x → sf) = R(x), so it has exactly zero Flow Matching loss, while inducing a different PF(s′ | s) = F(s → s′)/F(s); this settles analytically that FM's optimum is non-unique and cannot identify the Proposition 3.8 policy. Empirical confirmation: train FM with two different fixed, reward-compatible backward policies on the 7×7 hypergrid from identical initialization; since the FM objective is PB-independent, the runs yield identical dynamics and the same final sampler, showing the PB-specific 'corresponding' PF is not learned.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The core framework — Lemma 3.4, Definition 3.5, Propositions 3.6–3.10 — is internally consistent and correct under the stated PB > 0 assumption; I verified the absorbing-Markov-chain argument, the detailed-balance identity for expected visit counts, and the uniqueness argument in Proposition 3.7. The load-bearing problem is in Corollary 3.11, the paper's 'main practical corollary' and the claim the reader singles out. It asserts that with fixed PB > 0, 'any loss from the acyclic GFlowNet literature (Bengio et al., 2021; Malkin et al., 2022; Bengio et al., 2023; Madan et al., 2023)' learns the unique forward policy PF induced by PB. The Flow Matching loss (Bengio et al., 2021) is excluded from this claim's scope: FM is defined solely on flows F(s), F(s → s′) and never involves PB. Its global optima are all edge flows satisfying flow matching (3) plus the terminal constraint F(x → sf) = R(x). In a cyclic graph this set is a continuum — adding a circulation around any cycle (e.g., δ to both F(b → c) and F(c → b)) preserves flow matching and terminal rewards — and each point defines a different reward-matching policy PF(s′ | s) = F(s → s′)/F(s). Only one point is the expected-visit-count flow of Proposition 3.8; FM has no mechanism to single it out, since the objective is PB-independent. The paper's own Appendix C.1 concedes FM 'does not admit explicit parameterization of a backward policy, as well as training with fixed backward policies,' which contradicts the corollary's breadth. The claim does hold for PB-sensitive losses whose zero set enforces detailed balance or trajectory balance (DB, TB, SubTB), and Figures 1 and Table 1 are consistent with that narrower claim. The strict-positivity assumption flagged by the reader is indeed the foundational premise, but it is explicit, easily satisfied (softmax output; uniform-over-parents), and the theory degrades gracefully when some edges have zero PB, so I do not regard it as a vulnerability.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a theory of GFlowNets on discrete graphs that may contain cycles. Starting from a strictly positive backward policy P_B, the authors define state and edge flows as expected visit counts under the induced trajectory distribution (Definition 3.5), prove that these flows satisfy flow matching and detailed balance (Proposition 3.6), establish a one-to-one correspondence between flows and pairs (P_B, F(s_f)) (Proposition 3.7), and show that every fixed P_B determines a unique forward policy P_F with the same trajectory distribution (Proposition 3.8). Proposition 3.10 gives a reward-matching condition, and Corollary 3.11 claims that any loss from the acyclic GFlowNet literature can be used to learn this P_F in the non-acyclic case. The paper further proposes a state-flow regularizer for training with a learnable backward policy, connects non-acyclic GFlowNets to entropy-regularized RL (Theorem 3.13), and reports experiments on cyclic hypergrids and permutation generation.","tokens_in":30105,"tokens_out":15905,"duration_ms":147063,"significance":"If the results are correct, the paper provides a substantially simpler and more intuitive foundation for non-acyclic GFlowNets than the measure-theoretic treatment of Brunswic et al. (2024), clarifies the central role of the backward policy, and supplies a practical regularizer that can control expected trajectory length. The appendices contain detailed proofs, and the paper includes code, exact computations on small environments, and a careful experimental comparison of loss scales, which are all strengths. The main practical corollary, however, is overstated as written, and this affects a load-bearing claim of the paper.","major_comments":[{"comment":"Corollary 3.11 states that with a fixed P_B > 0, 'any loss from the acyclic GFlowNet literature (Bengio et al., 2021; Malkin et al., 2022; Bengio et al., 2023; Madan et al., 2023)' can be used to learn the corresponding forward policy P_F in the non-acyclic case. This is not true for the Flow Matching loss (Bengio et al., 2021), which is explicitly listed. FM is defined solely on edge/state flows and never involves P_B. In a cyclic graph, any edge flow satisfying the flow matching conditions (3) and the terminal condition F(x → s_f) = R(x) is a global FM optimum; adding a circulation around a directed cycle preserves these constraints and yields a continuum of distinct forward policies P_F(s'|s) = F(s → s')/F(s). Only one of these is the expected-visit-count flow of Definition 3.5 that Proposition 3.8 associates with the fixed P_B, and FM contains no term that can select it. The paper's own Appendix C.1 concedes that FM 'does not admit explicit parameterization of a backward policy, as well as training with fixed backward policies,' which contradicts the breadth of the corollary. The corollary should be restricted to losses that actually involve P_B (e.g., DB, TB, SubTB), or the claim should be reformulated to specify which losses are covered; as stated, the main practical corollary of the paper is internally inconsistent.","section":"Section 3.5, Corollary 3.11"}],"minor_comments":[{"comment":"In Eq. (12) the regularizer is written as λ F_θ(s), but since the network parameterizes the log-flow, the authors should state explicitly that this means λ·exp(log F_θ(s)) to avoid ambiguity about the scale of the regularization.","section":"Section 3.5, Eq. (12)"},{"comment":"The constrained optimization problem in (11) is over strictly positive backward policies; because the positivity constraint is an open condition, the infimum of the total flow may not be attained. The authors should clarify whether (11) is meant as an infimum or whether additional compactness assumptions are intended.","section":"Section 3.5, Eq. (11)"},{"comment":"The statement that FM 'does not admit explicit parameterization of a backward policy, as well as training with fixed backward policies' should be reconciled with Corollary 3.11; at present the appendix explicitly excludes the FM loss from the setting in which the corollary is claimed to hold.","section":"Appendix C.1"},{"comment":"For n = 20, the rows for DB ΔF and SDB ΔF report ΔlogZ ≈ 42.98 with zero standard error, indicating that these runs completely fail to estimate the normalizing constant. The authors should add a note that these configurations are included primarily for the trajectory-length comparison and are not competitive for reward matching.","section":"Table 1"},{"comment":"The scaling hypothesis is supported by a heuristic gradient argument about the derivative of losses in ΔF scale. The authors should state clearly in the main text that this is an explanatory hypothesis rather than a proven statement, since the paper does not provide a theoretical guarantee for the stability of ΔF-scale losses.","section":"Appendix B.2"}],"recommendation":"major_revision","confidential_remarks":"The core theoretical construction is sound and the experiments are generally well executed. The main problem is the overstated Corollary 3.11, which the authors should be able to fix by amending the claim to cover only losses that involve the backward policy, or by providing an additional argument for why FM's continuum of optima does not undermine the stated conclusion. This is a load-bearing point because the corollary is presented as the main practical implication of the fixed-P_B theory."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time. This paper gives a clean discrete-state foundation for non-acyclic GFlowNets, and the core machinery is genuinely good. The expected-visit-count definition of flows (Def. 3.5) is the right move, and the equality between expected trajectory length and normalized total flow (Prop. 3.12) is a real improvement over the earlier inequality in Brunswic et al. The proof of Prop. 3.7, with the uniqueness argument via the linear system, is careful and checkable. Theorem 3.13, extending the entropy-regularized RL equivalence to cyclic graphs, is also a solid contribution since the acyclic proof does not transfer directly. I verified the absorbing-Markov-chain reasoning in Lemma 3.4 and the detailed-balance identity for expected visit counts; they hold under the stated PB > 0 condition, which is explicit and not a hidden trap.\n\nThe soft spot is Corollary 3.11, and the stress-test note is right that it overreaches. The claim that \"any loss from the acyclic GFlowNet literature\" works with a fixed backward policy is false for the Flow Matching loss (Bengio et al., 2021). FM is defined purely on flows; it never sees the backward policy. Its global optima are any edge flow satisfying flow matching and the terminal reward constraint, and on a cyclic graph that is a continuum, with a circulation around any cycle corresponding to a different reward-matching forward policy. FM has no mechanism to select the unique expected-visit-count flow of Prop. 3.8. The paper's own Appendix C.1 concedes that FM does not admit explicit parameterization of a backward policy, which undercuts the corollary's breadth. The corollary does hold for PB-sensitive losses like DB, TB, and SubTB, and the experiments are consistent with that narrower claim. So this is a localized flaw, not a collapse of the theory, but it needs fixing: either restrict the corollary to losses that involve the backward policy or explain why FM is a special case.\n\nMinor issues: the hypergrid figures in the main text lack error bars (the permutation table has them, which helps), and the state flow regularizer is heuristic, though the scaling hypothesis in Appendix B.2 gives a plausible mechanism. Neither undermines the central contribution.\n\nThis paper deserves serious refereeing. I would push for a revision that qualifies Corollary 3.11, and then accept. The theory is solid, the presentation is clear, and the experimental work supports the main practical claims.","headline":"Solid, checkable theory for non-acyclic GFlowNets with one overbroad corollary that should be qualified before publication.","tokens_in":30761,"tokens_out":1338,"would_cite":true,"duration_ms":13039,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GFlowNets can train on cyclic graphs if the backward path is always available","keywords":["GFlowNets","non-acyclic environments","discrete state spaces","backward policy","expected visit counts","detailed balance","loss stability","entropy-regularized reinforcement learning"],"falsifier":"Take a finite cyclic graph with edges $s_0 \\to a$, $a \\to a$, and $a \\to s_f$. Set $P_B(a \\mid a) = 1$, $P_B(a \\mid s_f) = 1$, and $P_B(s_0 \\mid a) = 0$. Then the only finite trajectory from $s_0$ to $s_f$ has induced probability zero and the reversed walk is trapped in the self-loop, so the sum of induced trajectory probabilities is $0$ instead of $1$, violating Lemma 3.4 exactly when strict positivity is dropped.","tokens_in":1698,"feed_emoji":"🔁","tokens_out":4074,"duration_ms":78174,"temperature":0.7,"pith_summary":"This paper claims that GFlowNets do not actually need acyclic graphs in discrete settings, provided every edge has a positive backward probability. It constructs flows as expected numbers of visits of a reversed random walk, which stay finite and satisfy detailed balance and flow matching even with cycles. The consequence is that with a fixed backward policy, every standard acyclic GFlowNet loss learns the correct forward policy, so special stable losses are only needed when the backward policy is trained. The paper also proves that expected trajectory length equals normalized total flow, proposes state flow regularization to control that length, and extends the known equivalence between GFlowNets and entropy-regularized RL to cyclic environments.","feed_headline":"GFlowNets train on cyclic graphs with positive backward paths","feed_subtitle":"A strictly positive backward policy makes standard losses valid and keeps trajectory lengths finite.","key_machinery":"The reversed random walk with a strictly positive backward policy $P_B$: starting at the sink $s_f$ and stepping backward through edges with probabilities $P_B(s \\mid s')$, with $s_0$ absorbing. Its expected edge and state visit counts define the flows; Lemma 3.4 guarantees that the walk is absorbed almost surely with finite expected length. This makes flows finite, yields detailed balance $F(s \\to s') = F(s') P_B(s \\mid s')$, and turns standard GFlowNet losses into valid training objectives for cyclic graphs.","core_discovery":"The central claim is Corollary 3.11: when a backward policy $P_B > 0$ is fixed, any loss from the acyclic GFlowNet literature can be used to learn the corresponding forward policy in a non-acyclic environment. The mechanism is to define flows not as probabilities of visiting an edge but as expected numbers of visits under the reversed random walk. Those expected visit counts are finite because strict positivity makes the reversed chain absorbing at $s_0$, and they satisfy detailed balance and flow matching. Consequently reward matching and uniqueness of the forward policy hold, and the positive backward distribution automatically keeps expected trajectory length finite. The paper additionally proves an exact identity linking expected trajectory length to total state flow, proposes state flow regularization as a practical way to control trajectory length when the backward policy is trained, and generalizes the GFlowNet/entropy-regularized-RL equivalence to cyclic graphs.","pith_inferences":["The strict positivity condition suggests that any practical implementation must initialize the backward policy with full support and clip it away from zero during training; the paper's experiments indeed use a small epsilon for this purpose.","Loss stability is best understood as a property of training dynamics when the backward policy is learnable, not as a requirement for the existence of reward-matching solutions, since a fixed positive backward policy makes all standard losses valid.","The exact identity between expected trajectory length and normalized total flow gives a practical diagnostic: monitor normalized total flow during training as a proxy for sampling cost.","The scaling hypothesis could be tested directly on other GFlowNet losses, such as subtrajectory balance or flow matching, by comparing the same loss in flow scale versus log-flow scale and measuring trajectory length and distribution error."],"forward_implications":["Any acyclic GFlowNet loss, such as flow matching, detailed balance, and trajectory balance, can train a correct sampler on a cyclic graph as long as the backward policy is fixed and strictly positive.","Expected trajectory length equals the normalized total state flow exactly, so minimizing expected sampling length and minimizing total flow are the same optimization target.","State flow regularization allows log-flow-scale losses to keep trajectory lengths bounded while preserving accurate reward matching, whereas flow-scale losses bias toward shorter trajectories but can degrade sampling fidelity.","The equivalence between GFlowNets and entropy-regularized RL carries over to cyclic environments, so RL algorithms and insights transfer to non-acyclic GFlowNet training.","When the backward policy is trained, log-flow-scale losses without regularization can let trajectory length grow without bound; regularization is needed to control it."],"supporting_citations":[{"why":"Introduced GFlowNets and the flow-matching loss that this paper generalizes to cyclic graphs, and supplied hypergrid environment parameters used in the experiments.","marker":"Bengio et al., 2021"},{"why":"Provided trajectory balance, the fixed-backward-policy setup, and the trainable normalizing constant that the paper's Corollary 3.11 relies on.","marker":"Malkin et al., 2022"},{"why":"Established the acyclic GFlowNet foundations, including detailed balance, flow matching, and uniqueness of policies, which the present framework extends to non-acyclic environments.","marker":"Bengio et al., 2023"},{"why":"Introduced the prior non-acyclic GFlowNet theory, the concept of loss stability, the stable detailed balance loss, and the cyclic hypergrid and permutation environments that this paper revisits and simplifies.","marker":"Brunswic et al., 2024"},{"why":"Proved the equivalence between GFlowNets and entropy-regularized RL in acyclic environments, which Theorem 3.13 generalizes to the non-acyclic setting.","marker":"Tiapkin et al., 2024"},{"why":"Supplied the Markov chain transience result used in the proof of Lemma 3.4 to show that the reversed random walk is absorbed with finite expected length.","marker":"Douc et al., 2018"}],"fun_headline_variants":["Cyclic GFlowNets work with fixed positive backward policies","Positive backward policies make GFlowNets valid on cycles","GFlowNets without acyclicity: simpler theory, stable training","Expected visit counts unlock non-acyclic GFlowNet training"],"cache_read_input_tokens":32640,"weakest_assumption_plain":"Everything rests on the backward policy assigning strictly positive probability to every edge of the cyclic graph: if any edge has zero backward probability, the reversed random walk can fail to be absorbed, the induced trajectory measure can stop being a probability distribution, and the flows can diverge.","fun_headline_variants_meta":{"raw":{"variants":["Cyclic GFlowNets work with fixed positive backward policies","Positive backward policies make GFlowNets valid on cycles","GFlowNets without acyclicity: simpler theory, stable training","Expected visit counts unlock non-acyclic GFlowNet training"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000287,"raw_usage":{"total_tokens":1653,"prompt_tokens":883,"completion_tokens":770,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":499,"completion_tokens_details":{"reasoning_tokens":698}},"tokens_in":499,"tokens_out":770,"duration_ms":7139,"temperature":1.0,"reasoning_tokens":698,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:45:30.301938+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a finite cyclic graph with edges $s_0 \\to a$, $a \\to a$, and $a \\to s_f$. Set $P_B(a \\mid a) = 1$, $P_B(a \\mid s_f) = 1$, and $P_B(s_0 \\mid a) = 0$. Then the only finite trajectory from $s_0$ to $s_f$ has induced probability zero and the reversed walk is trapped in the self-loop, so the sum of induced trajectory probabilities is $0$ instead of $1$, violating Lemma 3.4 exactly when strict positivity is dropped.","supporting_citations":[{"cited_title":"Trajectory balance: Improved credit assignment in gflownets","cited_arxiv_id":null,"evidence_quote":"Provided trajectory balance, the fixed-backward-policy setup, and the trainable normalizing constant that the paper's Corollary 3.11 relies on."},{"cited_title":"J., Tiwari, M., and Bengio, E","cited_arxiv_id":null,"evidence_quote":"Established the acyclic GFlowNet foundations, including detailed balance, flow matching, and uniqueness of policies, which the present framework extends to non-acyclic environments."},{"cited_title":"A theory of non-acyclic generative flow networks","cited_arxiv_id":null,"evidence_quote":"Introduced the prior non-acyclic GFlowNet theory, the concept of loss stability, the stable detailed balance loss, and the cyclic hypergrid and permutation environments that this paper revisits and simplifies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proved the equivalence between GFlowNets and entropy-regularized RL in acyclic environments, which Theorem 3.13 generalizes to the non-acyclic setting."},{"cited_title":"Markov chains","cited_arxiv_id":null,"evidence_quote":"Supplied the Markov chain transience result used in the proof of Lemma 3.4 to show that the reversed random walk is absorbed with finite expected length."}],"review_version":1}