Path-dependent Discrete Amortized Inference

Summary

This paper studies amortized samplers for discrete, compositional targets and argues that the Markovian assumption at the heart of Generative Flow Networks (GFlowNets) is a substantive bottleneck. The conceptual move is a discrete analogue of the Hamiltonian Monte Carlo trick of augmenting the state with a momentum variable: the authors "lift" the underlying pointed DAG with a state-conditional latent dynamical system $\{W_t\}$ that evolves via a learned rule $W_t = W_{t-1} + \phi(s_t, W_{t-1})$, allowing the policy to depend on the whole history and so escape the Markovian expressivity ceiling. The paper's technical spine is two-fold. First, Section 3 gives clean expressivity separations: Proposition 3.1 shows that lifted linear policies span strictly larger classes than plain linear ones on a simple LINES environment, and Proposition 3.2 sharpens this to graph-structured targets, exhibiting a small state graph that a 1-WL GNN sampler cannot cover but that a temporally-augmented GNN can. Section 3.3 then illustrates state aliasing under a ReLU parameterization on a sparse LINES target. Second, Section 4 shows that TB, SubTB, and CB objectives extend to the lifted DAG (Proposition 4.5, Corollaries 4.6-4.7), and Proposition 4.8 clarifies that a Markovian $p_B$ forces $p_F$ to admit a Markovian representative. Concretely, the authors propose a rotation-augmented self-referential weight matrix (SRWM) as the $\phi$ head. Experiments across set generation, sequence design (synthetic and SIX6/PHO4), hypergrid, LINES, LRW, Ising, preference learning, and bit sequences report improvements over a matched Markovian baseline. The contribution is conceptually appealing and the expressivity story is the strongest part. That said, the manuscript is uneven: several equations, table entries, figure captions, and notational conventions do not line up; multiple experimental targets and evaluators are described only up to citation; and comparisons stay narrow (only Markovian vs. path-dependent, with no head-to-head against contemporary exploration/aliasing techniques for GFlowNets).

Strengths

• Conceptual contribution. The HMC-style lifting analogy is neatly transferred to a discrete, compositional setting, and the reformulation as a lifted pointed DAG (Definition 4.1) is a clean object that plugs directly into existing GFlowNet theory. Extending TB/SubTB/CB objectives to the lifted DAG (Proposition 4.5 and Corollaries 4.6-4.7) means the framework is immediately usable rather than requiring a new learning paradigm.
• Expressivity results. Proposition 3.1 gives a concrete, verifiable separation for linear policies on the LINES environment, and Proposition 3.2 exhibits a small graph where 1-WL GNNs provably cannot represent the target but a temporally-augmented GNN can. These are the kind of clean minimal-counterexample results that make the failure mode of Markovian GFlowNets tangible.
• State-aliasing story. Section 3.3 turns "state aliasing" from a slogan into a concrete illustration: the sparse LINES target with $R(q_2)=1000\,R(q_1)$ demonstrates why a ReLU sampler struggles to separate $p_2$ and $p_3$, and the accompanying KL curve makes the aliasing gap quantitative.
• $p_B$-$p_F$ coupling result. Proposition 4.8 is a subtle and useful observation: a Markovian $p_B$ constrains the optimal $p_F$ to a Markovian equivalence class, giving practitioners a lever (choice of $p_B$) that mechanistically decides whether the lifted framework can express non-Markovian equilibria.
• Breadth of empirical validation. The experiments span set generation, synthetic and biological sequence design, hypergrid, sparse LINES, LRW, Ising, preference learning, and bit sequences, and include ablations on the SRWM rotation matrix and the link function. The consistency of the direction of improvement across so many benchmarks lends credence to the qualitative headline.

Weaknesses

• Table 1 mislabels the reported $K$ values. The text reports set generation results for $K \in \{16, 32\}$ (with cardinalities $\sim 10^{14}$ and $\sim 10^{18}$), but Table 1's second row is labeled $K=24$. Either the row label is wrong or the text and cardinality claim are; a reader cannot tell which configuration was actually run.
• Suspicious duplicate in Table 2. The Markovian FCS for Syn-16 and SIX6 are both reported as $0.165 \pm 0.006$ — the same mean and the same SD on two unrelated tasks. This is very likely a copy-paste error and should be re-checked, since a wrong SIX6 baseline would distort the reported PD gain.
• Missing SRWM update equation. The paragraph that introduces the "modified SRWM" announces an update rule "with the form:" but never displays it. The mapping from the $(3d+1)$-dimensional output to key/value/query-like slow weights and $\beta_t$ is left implicit, hurting reproducibility of the central methodological novelty.
• Notation collisions. $W_t$ is described as both a vector in $\mathbb{R}^d$ (Definition 4.1, recurrent-policy paragraph) and a $d\times d$ matrix (SRWM paragraph). $\sigma$ is used for both the sigmoid and the "normalized ELU link function" of Eq. (23). $\xi$ appears in the same sentence as both a measure and its own density. The composition of the "two-layer" ReLU network is written $f_1 \circ f_2$ with three weight matrices $\mathbf{W}_o, \mathbf{W}_1, \mathbf{W}_2$. Individually these are small; collectively they hurt trust in the derivations.
• Directional slip in the proof of Proposition 3.2. The proof paragraph argues that the path-dependent class contains the Markovian class ($\mathcal{R}_M \subseteq \mathcal{R}_P$), but concludes with $\mathcal{R}_P(\mathcal{S}) \subseteq \mathcal{R}_M(\mathcal{S})$ — the reverse inclusion. The subscripts appear swapped.
• Overstatement in Proposition 4.8's paraphrase. The prose says "the optimal $p_F$ ... is Markovian", but the proposition establishes only that a Markovian representative exists on the unlifted DAG, not uniqueness. A more accurate phrasing would help readers not overread the theorem.
• Limited baseline comparison. All Section 5 comparisons pit path-dependent against a plain Markovian baseline of matched parameter count. The paper frames its method as complementary to Local Search GFlowNets (Kim et al., 2024b), Adaptive Teachers (Kim et al., 2025b), Q-GFN (Lau et al., 2024), action abstractions (Boussif et al., 2024), and sibling-augmented GFlowNets (Madan et al., 2025), yet no head-to-head numbers are offered. Without a stronger baseline it is hard to know whether path-dependence buys something over other cheap exploration/aliasing fixes.
• Statistical significance not discussed. Several reported gaps are within one or two standard deviations (e.g., Table 3's largest row: $0.274 \pm 0.074$ vs. $0.236 \pm 0.092$), and Table 4 reports SDs of $0.000$ with no comment on precision. No hypothesis tests, effect sizes, or seed counts are provided for most tables.
• Compute cost is only qualitatively addressed. Section F.1 acknowledges the $O(d^3)$ per-step cost of the SRWM's rotation matrix and mitigates it by choosing $d=32$, but the "faster learning convergence" claim is never expressed in wall-clock or FLOP-normalised terms, so it is unclear whether the SRWM overhead per step is amortised in end-to-end training time.
• Presentation errors and unlabeled results. Table 3 has no row labels for the three sample sizes claimed in the text; Figure 12's caption promises RINGS/SINUSOIDAL LRW results but the panel labels list a GridWorld rotation-matrix ablation; the LRW terminal set is written $[-M,M]^{15}$ with $M$ never given a value; Proposition E.3 cites itself; and the "aperiodicity" claim confuses "run for exactly $T$ steps" with the self-loop that actually gives aperiodicity.

Reproducibility & code

The evidence gathered from a read of the released materials (code was inspected but not executed) indicates that the code bundle is promised in the supplement but the paper leaves many methodological knobs unspecified in text. The pattern is that headline numbers rely on the code for exact reproduction rather than on the manuscript alone.

• Targets defined only up to citation or symbolic form. The utility function $u$ for set generation, the utility functions $u,v$ for the Syn-$S$ sequence targets, the affinity oracle used for SIX6/PHO4, the target for bit sequences (cited to Malkin et al., 2022, Section 5.3.1 without restating), and the reference distribution for the Ising task at $d=64$ are all left implicit. Given tight reported SDs (as small as $0.000$ in Table 4), any drift in target definition places a reproduction outside the reported bands.
• Undocumented evaluation protocols. Table 4 reports a "distance to target distribution" whose definition is never given; the Ising row at $d=64$ has state space of size $2^{64}$ but the paper does not describe how FCS subsets $B$ are chosen or how the reference probabilities are estimated; the "Top-20 $R(x)$" mode-discovery metric in Figure 11(b) is not defined precisely (window? cumulative? per-episode?).
• Missing hyperparameter grids. Figure 10 sweeps parameter count "by expanding the latent dimension $d$" but the concrete $d$ values (and matched Markovian ReLU widths) at each abscissa are not disclosed. The 3-layer leaky ReLU Markovian baseline is documented only up to depth, with no widths or parameter counts stated for any benchmark, even though the entire empirical case rests on capacity matching. The LRW task never states $M$ (the box radius) or the Fourier positional-encoding parameters. Table 3 rows for preference learning are unlabeled with respect to sample size.
• Seed and confidence-band bookkeeping. Only Table 5 states the seed count (three runs). Elsewhere (Tables 1-4, Figures 6, 10, 12, 13, 14) $\pm$ values or shaded bands are shown without stating the number of seeds or the dispersion protocol (min/max, $\pm$1 SD, $\pm$2 SD), making it impossible to reason about statistical significance from the paper alone.
• Code availability statement is thin. The supplement is pointed to only in prose ("We provide computer code for reproducing our experiments in the supplement.") without a URL, repository name, license, or explicit listing of which experiments the code covers. Given how much the manuscript defers to the code, a more concrete availability statement is important.

Recommended Changes

Essential.

• Fix Table 1's $K$ labeling. Reconcile the "$K \in \{16, 32\}$" claim in the set-generation prose with the "$K=16, 24$" rows in Table 1, so the reported values, cardinalities, and $K$ configurations agree.
• Re-check the SIX6 Markovian entry in Table 2. Verify against the underlying runs whether the exact match with the Syn-16 baseline ($0.165 \pm 0.006$) is real or a copy-paste slip, and correct if needed.
• Display the SRWM update equation and state explicitly how the $(3d+1)$ output slots decompose into slow weights (key/value/query analogues) and the scalar $\beta_t$, so the central methodological novelty can be reimplemented from the text.
• Fix the inclusion in the proof of Proposition 3.2. Correct $\mathcal{R}_P(\mathcal{S}) \subseteq \mathcal{R}_M(\mathcal{S})$ to $\mathcal{R}_M(\mathcal{S}) \subseteq \mathcal{R}_P(\mathcal{S})$ (or the argument that produces it).
• Resolve the notation collisions for $W_t$ (vector vs. matrix), $\sigma$ (sigmoid vs. ELU-link), and $\xi$ (measure vs. density) with distinct symbols; also correct the composition order and matrix-count of the "two-layer" ReLU network in Section 3.3 and the shape of $\mathbf{W}_{\text{MLP},2}$ in Section F.1.
• Rephrase Proposition 4.8's paraphrase. Replace "the optimal $p_F$ ... is Markovian" with a statement that a Markovian representative on $\mathrm{SG}$ exists, so readers do not overread uniqueness.
• Reconcile Figure 12's caption with its panels, correct the LRW terminal-set exponent ($[-M,M]^{15}$ → $[-M,M]^{d}$ with $d$ named and $M$ set), fix Proposition E.3's self-citation, and rewrite the "aperiodicity" justification so it invokes the $\mathbf{0}$ self-loop rather than the fixed horizon $T$.
• Pin the targets and evaluators. State $u$ (set generation), $(u, v)$ (Syn-$S$), the SIX6/PHO4 oracle and preprocessing, the bit-sequence target and metric, and the FCS estimator used for the Ising rows (including how the reference distribution is obtained at $d=64$).
• Document the sweep grid and baseline sizes. For Figure 10, list the $d$ values (and matched Markovian ReLU widths) at each abscissa. For every benchmark, tabulate the widths and resulting parameter counts of both Markovian and PD models so the capacity match is auditable.
• Report seeds and dispersion protocol consistently across all tables and figures, and comment on statistical significance for the tighter tables (Table 3 in particular).
• State the code-availability details. Include a URL/repository name (anonymised if needed), a license, and a listing of which experiments the released code covers.

Suggested.

• Add stronger baselines on at least one core benchmark (e.g., hypergrid or bit sequences) — Local Search GFlowNets, Q-GFN, action abstractions, or sibling-augmented GFlowNets — to substantiate the "path-dependence complements existing techniques" framing.
• Report wall-clock or FLOP-normalised training curves on at least one representative benchmark to substantiate "faster learning convergence" given the SRWM's $O(d^3)$ per-step overhead.
• Add a controlled exploration experiment with a well-defined mode-coverage metric (baseline comparison, seeds, error bars) to back the abstract's "improved state space exploration" claim.
• Tighten the mechanistic rotation-matrix intuition. Specify how $\mathbf{R}$ multiplies $\mathbf{W}_t$ (one-sided vs. similarity transform) and either derive or hedge the causal link between eigenvector rotation and mitigation of the ReLU aliasing effects of Section 3.3.
• Restate reused symbols ($\leadsto$ for reaching intermediate states, $\{s_o\}$ vs. $\mathcal{S}_o^{\star}$ as the absorbing set in Section D) and add a short symbol glossary; the proofs would read much more smoothly.