acceptodds
Under review as a conference paper at ICLR 2027

The Amortization Ceiling: Why Learned Policies Do Not Replace Search in Constraint-Satisfaction Graph Generation

Abstract

When a combinatorial objective is expensive to evaluate, a learned policy is meant to replace the evaluation: train once, decide cheaply thereafter. We study this amortization question in a controlled testbed: generate a graph whose five structural metrics (clustering, mean path length, modularity, spectral gap, degree assortativity) jointly fall within target tolerance bands, using degree-preserving edge swaps. True-metric evaluation is costly and the constraints are coupled. We benchmark eleven learned methods in thirteen configurations (imitation, value regression, policy gradients, generative flow networks, differentiable guidance, planning, a transplanted autoregressive architecture, and LLM-evolved heuristics), eleven under one unified protocol, against references at every level of the search hierarchy. Three findings follow. (1) No residual-free policy significantly beats random at any tolerance. A learner beats random only inside a narrow, protocol-sensitive niche (unimodal in tolerance tightness, concentrating on a locally computable binding constraint, and confined to small-to-mid sizes and the training family), and only for a learner that itself pays the per-decision measurement cost. (2) A ceiling: no learned method approaches true-metric greedy at any tightness or budget, and the best recovers under a quarter of the greedy-random gap on band average, at greedy's own cost. (3) The ceiling is structural: most candidate edits (96.7%) share their endpoint-degree view with another candidate, the failure localizes to assortativity, and the joint target space is thin, with a slice certified infeasible in advance by an unconditional spectral-modularity bound. A worst-case theorem shows that locally indistinguishable edits with provably different global effects exist, so bounded-radius scorers incur constant relative regret. Here, good moves are measured, not predicted; the certificate and the collision statistic are computable before any training. We distill the boundary into a testable binding-locality criterion: amortization can help to the extent that the binding constraint's increment is locally computable.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph generation, network science, combinatorial optimization, amortized optimization, graph neural networks, negative results, benchmark

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_VZrDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Consider several characteristics of a graph; each characteristic is a real number (for instance, the clustering coefficient or mean path length). Fix target value for each characteristic. We aim to construct a graph with a fixed number of vertices N, such that its characteristics values are close to the targets. We start from some graph constructed by warm-start technique (we could start with random graph instead). Our only allowed way to change the graph is double-edge swap: remove edges (a, b),(c, d), add edges (a, d),(c, b).

The question is what sequence of swaps to do, to get from our starting graph to a graph with characteristics close to the targets. We assume that evaluation of graph characteristics is costly. A typical solution is to firstly do some training (which involve computing graphs' characteristics) to get a policy of choosing swaps. The policy itself must not involve recomputing graph characteristics of each after-swap candidate (such policies are called residual-free). So once we spend lots of compute on policy, we can use it at low computational cost – that is, given new target vector we can try to achieve the target by starting from warm-start graph and sequentially choosing swaps according to policy.

The main result of the paper: no residual-free policy beats random significantly. Second result: no learned method approaches greedy method (which just choose best swap based on true characteristics).

Critical strengths

If I understood the main results correctly, it seems interesting. Unfortunately, the exposition is very hard to follow, so I am not even sure that I understood the main results correctly.

Critical weaknesses

The paper is very hard to read. Here is some suggestions on how to improve readability (I wrote it only for several lines, after that I gave up – similar comments apply throughout the paper):

  1. Line 155 - define m_k
  2. Line 157 - “the loose tail is at issue” - not clear what it means.
  3. Line 159 - define N (it is defined only in the legend of Figure 1b). What is <k>? Why is it 6 (not 5 as k before was used as index for components of the target vector).
  4. Protocol is supposedly described in lines 159-161. It is not clear what protocol consists of - I get we start from warm-start graph of size N, but what is episode, how many candidates are generated, what is meant by greedy here, etc.
  5. Lines 179-181 - more specific definitions of beam and MH/SA
Questions for authors
1 comment

Thank you for the line-by-line comments. We used them as a checklist when rewriting §3, which now defines the task and the protocol before any result. Your reading of the two main results is correct, with two refinements at the end.

  • m_k (l. 155). Now m_j(G), the value of metric j on graph G, with base tolerance ε_j and target value c*_j. The scaled residual is z_j = |m_j(G) - c*_j| / ε_j, and the worst-scaled residual is W(G) = max_j z_j (Eq. 1). A target is satisfied at band scale u when W <= u.
  • "the loose tail is at issue" (l. 157). Removed. "Loose bands" means only u in {1.2, 1.5, 2.0}.
  • N and ⟨k⟩ (l. 159). N is the number of nodes and ⟨k⟩ the mean degree, both defined at the start of §3. Metrics are indexed by j, so k no longer has two meanings. N = 200 and ⟨k⟩ = 6 define the benchmark cell. This is a benchmark choice, and a size-by-degree grid covers N from 100 to 800 and ⟨k⟩ from 4 to 10 (App. C).
  • The protocol (ll. 159-161). See the paragraph "One episode" and Table 1. A warm-start pipeline builds one start graph per target. An episode is at most T = 60 double-edge swaps. At each step the candidate-generation rule draws 32 candidate swaps, 16 uniform and 16 bridge-biased. Greedy measures the five metrics of K = 8 of them and applies the one with the lowest weighted-L1 score, a weighted sum of the z_j. A target counts as satisfied if any graph visited in the episode is within the band. Table 2 gives each method's decision rule.
  • Beam and the samplers (ll. 179-181). Beam keeps 4 graphs, expands each by 6 measured candidates and ranks by W. The two samplers propose one swap per step and accept it by a Metropolis rule with W as the energy. One runs at fixed temperature 0.1, and SA cools from 0.3 to 0.01. A rejected proposal leaves the graph unchanged. We renamed the first from "MH" to "Metropolis-style search (MS)" because its restricted proposal does not guarantee the usual stationary distribution. Both draw their own uniform proposals, not the 32 candidates (Table 1).

Your first result holds under the benchmark protocol (Protocol A): no tested swap policy that skips measuring its candidates beats random significantly. The revision calls such policies "candidate-oracle-free" in place of "residual-free". In a new matched protocol (Protocol B, §4.2), imitation learners whose demonstrations continue toward the tightest band do beat random: DAgger by 18.7 and BC by 10.3 percentage points (pp) in twelve-band mean satisfaction, the share of targets satisfied averaged over the twelve bands. Their training uses more teacher calls (the expert's candidate calls) and a different training distribution than the paper's common settings (§5.1).

Your second result also holds: each tested learned method stays below greedy. In Protocol B, greedy ranked by W and the value learner (a learned scorer that measures its candidates) share start graphs and measure K = 6 candidates each. Greedy leads by 29.3 pp in the twelve-band mean [25.1, 33.7]. It ranks the immediate W, while the learner predicts the best W that a depth-3 beam reaches. A learner given the exact per-candidate metric changes that greedy measures still trails by 11.9 pp (§4.2, §5.1).

Reviewer_FDXYOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper explores a reason why learned policies are not as effective as search for the problem of graph generation subject to constraints. The empirical study relies on a given vector of tolerances that the final solution must abide by, including clustering coefficient, mean path length, modularity, normalized Laplacian spectral gap, and degree assortativity.

Critical strengths

There are no strengths in this paper.

Critical weaknesses

To preface my weaknesses, I want to state that the paper reads like incomprehensible AI slop, so I decided to run it through GPT-Zero, which stated that "the chance this entire text is AI is 86%". The subject matter of the paper is interesting and the combinatorial optimization community has theories on why machine learning in general seems to fall behind classical heuristics for constrained optimization problems (including the referenced constraint-satisfaction graph generation problem). However, this paper adds nothing to the discussion and only obfuscates its own intended message. The authors benchmark eleven learned methods using a vector tolerances, but the values for each tolerance is chosen to be (0.05, 0.30, 0.05, 0.03, 0.05) without any reason given and the specific tolerances themselves also seem arbitrary, so it is not clear what conclusion to draw from this paper. The paper is also densely packed with statements that sound potentially reasonable but are very difficult to unpack and, once you unpack them, you realize that it is just AI-generated slop. For example, the statement "most of the metrics are global: a swap's effect is in general knowable only by re-evaluating them, at ~110ms per candidate, which is the cost truthful search pays every step and a learned policy exists to avoid" I can go out of my way to impart meaning to this claim, but the whole paper is full of strange statements like this and it makes the paper very unclear. There is a right way to use AI to help write papers, and this is not it.

Questions for authors

In Finding 1, you state that the benefit is unimodal in tolerance tightness and go on to say the benefit is 0 for loose bands, peaking in a mid-tight window, and closing again at extreme tightness. What do these terms mean? What is a mid-tight window or extreme tightness?

1 comment

Thank you for the review. We rewrote the paper in response to the readability concern. Section 3 now defines the task, the five metrics, the tolerances and the episode before any result. The introduction poses one question, and each results section is headed by its answer.

Why these tolerances. They are a fixed benchmark setting, not derived from the choice of metrics, and the revision says so (§3). Each base tolerance is about 12-18% of the interquartile range of its metric over 396 real networks (App. A.1). We also tested five other tolerance profiles on the same start graphs, and greedy search stays ahead of the two learners tested there (the value learner and BC) under all six. In that test the learners were not re-trained for each profile while greedy ranks with the new tolerances, so it shows the ordering for frozen learners only (§4.2).

What conclusion to draw. The learned policies we tested stay below greedy search. The main evidence is a matched comparison (Protocol B). Greedy and a value learner, a learned model that scores candidate swaps after measuring them, get the same start graphs, the same number of measured candidates and the same residual: the largest error among the five metrics, each divided by its tolerance. Greedy is ahead by 29.3 percentage points (pp) in twelve-band mean satisfaction, the share of targets satisfied averaged over the twelve tolerance bands. The 95% interval is [25.1, 33.7], and both methods use the same number of oracle calls. Their rankings still differ in horizon: greedy scores a candidate's immediate residual, while the learner predicts the best residual that a depth-3 beam reaches from it (§4.2). Changes that help the learners do not close the gap. A learner given the exact per-candidate change of all five metrics is still 11.9 pp below greedy. Imitation learners trained on demonstrations that continue toward tighter bands beat random but not greedy (§5.1). A certificate and a witness search help separate infeasible targets from search failure (§6). These conclusions concern the tested methods and protocols. We do not claim that learning cannot work on joint constraints.

Relation to combinatorial optimization. You are right that the gap between machine learning and classical heuristics is a known theme in that community. §2 now cites the work that re-examines learned solvers against strong classical references under explicit budgets (Angelini & Ricci-Tersenghi 2023; Böther et al. 2022; Liu et al. 2023). What the paper adds for this graph generation task is a quality-cost comparison under matched conditions.

The example sentence. We removed it, and the paper states the cost directly. One oracle call, a recomputation of the five metrics, takes about 111.5 ms per candidate at 200 nodes in our benchmark. A policy that measures no candidate avoids this per-candidate recomputation, although other runtime costs remain. A learner that does make the calls has to justify them by better choices (§1, §4.1).

Band terms (your question). The band scale u multiplies every tolerance, so a smaller u is tighter. "Mid-tight window" meant the middle bands where the value learner beat random, and "extreme tightness" meant the bands near u = 0.1. Both phrases are gone. Under the benchmark protocol (Protocol A), the gain over random of the value learner's positional-encoding variant survives Holm's correction at u = 0.5, 0.4 and 0.35 (the "supported bands"). It does not survive at u = 0.45, so we no longer describe a continuous window. The tightest band is u = 0.1, and "loose bands" refers only to u in {1.2, 1.5, 2.0}, covered by a separate four-seed check (§4.1, App. G).

Reviewer_QSfGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks whether learned policies can replace true-metric search when generating graphs that satisfy a joint constraint on five structural properties, all held inside per-metric tolerance bands at some tightness u. The action space is degree-preserving double-edge swaps on an N-node graph, warm-started from a target-aware WS construction, and the generator has T=60 swaps per episode to drive the worst-scaled residual into band. True-metric evaluation of a candidate costs about 110ms.

Eleven learned methods are run under one unified protocol in thirteen configurations, covering imitation (BC, DAgger), value regression (plain and with spectral PE), policy gradient (REINFORCE, PPO, SCST), GFlowNets, differentiable surrogate guidance, surrogate MPC, an architecture transplant from DMGG, and an LLM-evolved scoring function. These are benchmarked against random, true-metric greedy (K=8 candidates per step), beam, MH and SA samplers, and dK-1/dK-2 nulls. Only value regression beats random significantly, within a mid-tight tolerance window peaking at 12 to 14.5 pp. The authors then argue that the ceiling (window closing at loose bands, tight bands, etc.) is structural, and offer certain diagnostics: one-step improvement regresses on local candidate features with R²=0.009; 96.7% of candidate swaps share their endpoint-degree view with another candidate; long-horizon state values are predictable (R² up to 0.83) while adjacent-action ranking is not; the failure localizes to assortativity, the one metric whose increment is closed-form in endpoint degrees.

Finally, they prove an unconditional partition-uniform bound, which certifies a slice of the joint target space infeasible before any training. A worst-case theorem shows bounded-radius scorers incur constant relative regret on a two-expander construction.

Critical strengths
  1. The experimental sweep covers eleven methods in thirteen configurations, all under one unified pair protocol. It covers the standard neural CO families, such as imitation, value regression, policy gradient, GFlowNets, differentiable guidance, surrogate MPC, etc. Further, the chosen statistics are run properly. This includes deltas paired at the seed level, with bootstrap confidence intervals and paired t-tests. The main result peak faces an exact max-statistic sign-flip over 24 band x variant configurations.

  2. Lemma 2 is exhaustively verified and properly derived. The atlas check covers all 995 connected graphs, under 771,016 partitions with zero violations and max excess 2.2 x 10^-16. I think the partition-uniform certificate is a useful tool independent of this paper.

  3. Greedy search substantially outperforms the tested learned methods, including models that retain expensive candidate measurements. This is relevant to researchers considering learned alternatives to direct search, and is a useful negative result.

Critical weaknesses
  1. Table 1 lists “PPO” as a method but it is not really PPO. Appendix D states the configuration does one update per episode with old log-probs from the same forward pass, so the clipped ratio is one and the update reduces to REINFORCE + value baseline + entropy. This has been mentioned in Appendix D, but may still mislead a reader.

  2. Greedy ranks K=8 candidates by a weighted-L1 potential with λ2\lambda_2 weighted 3x; beam and the value learner rank by the worst-scaled residual that defines satisfaction. Appendix A says that this makes greedy's dominance "conservative", but this then means that the scoring function varies across arms. A similar issue arises in Finding 6, where search depth and scoring function are varied together.

  3. Target feasibility and solver failure are conflated at tight u. The certificate explains 10 to 12% of unreached targets and a 10510^5-swap simulated annealing re-search recovers 3% of 100 sampled unreached targets (appendix K). The remainder of the unreached set is therefore empirically unreachable by every solver tested rather than provably infeasible. While Appendix K maintains this distinction carefully, the main-text framing of an “amortization ceiling” does not, and consequently conflates a methodological verdict on learned policies with a feasibility property of the target distribution.

  4. The GFlowNet strengthening study is run at 6 configurations x 2 seeds x 3 bands, against the main benchmark’s 10 seeds x 12 bands. Finding 7’s claim of robustness across modalities, tuning, and framing is accordingly supported by a collection of probes each of which is individually underpowered relative to the headline comparison, and the aggregate conclusion exceeds what any single probe establishes.

Questions for authors
  1. Appendix A states that greedy search and the value learner use different scoring objectives. Evaluate greedy search under both objectives, the weighted sum and the largest normalized error, using the same candidate count and step budget as the value learner. Does greedy retain its advantage under both objectives?

  2. The imitation models are evaluated at tighter thresholds than those used to stop their expert demonstrations. Compare the current training procedure with demonstrations that continue to a tight evaluation threshold, keeping the total training budget fixed. Does imitation still fail when it is trained on the behavior required at evaluation?

2 comments

Thank you for the detailed review. Below, pp means percentage points of twelve-band mean satisfaction, the share of targets satisfied averaged over the twelve tolerance bands. Brackets are 95% bootstrap intervals.

PPO (W1). You are right that this configuration was not really PPO. With one update per episode it is REINFORCE with a value baseline, and we now call it REINFORCE (PPO form). The multi-epoch clipped PPO we added improves on it by 4.9 pp and is 5.9 pp below random (§5.1; intervals in App. D).

Scoring functions (W2, Q1). Yes, greedy retains its advantage under both objectives. The new matched protocol, Protocol B, gives greedy and the value learner the same stored start graphs, candidate-generation rule and oracle, with K = 6 measured candidates per step, over 20 seeds and 380 targets. Greedy reaches 63.2% with the weighted-L1 score and 64.6% with W, the residual that defines satisfaction. The value learner reaches 35.3%. Greedy ranked by W (W-greedy below) is ahead by 29.3 pp [25.1, 33.7]. One difference is left: greedy ranks each candidate's immediate W, while the value learner predicts the best W a depth-3 beam reaches from it. On Finding 6, beam ranked by W is 13.0 pp above W-greedy but uses 1,423 oracle calls against 421. Truncated at 421 calls, beam minus greedy is -1.3 pp [-3.4, +0.8]. The paper no longer reads the beam result as an effect of depth (§4.2).

Feasibility vs. solver failure (W3). The main text now keeps the two apart. §7 defines "amortization ceiling" as the measured gap between the tested learned policies and greedy search on the same targets, which is a statement about methods, not about feasibility. For feasibility we added a witness search, a long simulated-annealing search with about 60 times W-greedy's oracle calls. It finds a witness, a graph that satisfies u = 0.1, for 45 of 50 sampled Protocol B targets, and each witness is checked by replay. W-greedy satisfies 9 of the 50, so most are feasible at the tightest band but unreached by greedy. Why greedy fails is not settled: for 15 of the 41 it misses, a path of at most 60 swaps is confirmed, but each uses swaps outside greedy's proposal set (§6, App. D). The SA re-search (3 of 100 targets) used rebuilt start graphs and an uncalibrated cooling schedule, so it does not bound how many unreached targets are feasible (App. M).

Underpowered probes (W4). We reran the GFlowNet strengthening study at the scale of the main comparison (Protocol B, 20 seeds, twelve bands), with the configuration selected on separate validation seeds. The selected combination is 1.2 pp below random [-2.5, +0.1] and 32.6 pp below W-greedy. DMGG-factorized and the MH and SA samplers were rerun at the same scale and also stay below W-greedy (App. C). We no longer claim robustness across modalities, tuning and framing: §7 states that these studies do not combine into general architectural robustness.

Tight demonstrations (Q2). With demonstrations that continue toward the tight threshold, imitation beats random but trails W-greedy. We compare an expert that stops at u = 1.0 (current) with one that aims for u = 0.1 (tight), given the same 60-step cap, training targets, optimizer updates and budget of teacher calls (the expert's candidate calls). Tight demonstrations raise DAgger by 15.5 pp [12.1, 19.1] and BC by 9.5 pp. Tight DAgger and tight BC then beat random by 18.7 and 10.3 pp. They remain 12.7 and 21.1 pp below W-greedy (§5.1; intervals in App. C). The gains are consistent with longer, deeper demonstrations: the tight expert stops after 53 to 58 swaps on average, the current expert after 8 to 9. Re-training at T = 240 does not close the gap. Tight DAgger changes by -1.2 pp [-3.6, +1.3] and stays 13.4 pp below W-greedy (App. C). All four imitation arms use more teacher calls and a different training distribution than the paper's common settings, so they are not a controlled comparison with those learners.

The certificate. One correction: the inequality is not new. For two parts it is that of Fasino & Tudisco (2017, eq. 12), and for more parts it follows McDiarmid & Skerman (2020, Lemma 6.1). We claim only its use as an infeasibility test before search (§2, §6).

Results on the mixed pool and at other graph sizes follow in a second comment.

Additional results for Reviewer QSfG: the mixed pool and other graph sizes

This comment adds three results to our first one. Terms are as there: a witness is a graph that satisfies the stated band, W-greedy is greedy ranked by the residual W, and pp refers to twelve-band mean satisfaction (averaged over the twelve bands).

Unreached targets of the mixed pool (W3). We first classified all 747 targets of the mixed pool. At u = 1.0, 596 are unreached by every solver. The certificate excludes 59 of them and a new degree-sequence bound excludes one more, which leaves 536 undetermined. The witness search was then run on a stratified sample of the undetermined targets, not on all of them. Of the 116 sampled at u = 1.0, it finds a witness for 22: 18 of 55 generator-derived mix targets, 3 of 15 real-network targets, 1 of 6 WS targets and none of 40 uniform-box targets. These 22 targets are feasible for their start graph's degree sequence, although every tested solver missed them. For the others the search found no witness within its budget, and their feasibility remains unknown (App. M, Table 30).

Witness search on the size-by-degree grid (N from 100 to 800, mean degree 4 to 10). In the 12 cells with N = 100, 200 and 400, the witness search finds a witness at u = 0.1 for 211 of 240 sampled targets. W-greedy satisfies 46 of the same 240. At N = 800 and mean degree 4, 6 and 8, it finds a witness for 11 to 16 of 20 targets per cell, where W-greedy satisfies 1 or 2. The cell N = 800, mean degree 10 has 12 targets from 6 of the 10 seeds (7 with a witness, 1 satisfied by W-greedy). These seeds are not a random subset, so the count is not an estimate of a rate. The search budget was calibrated at N = 200 and is not rescaled with N. Counts are therefore compared within a cell only, and a missing witness is not evidence of infeasibility (App. C, Table 12).

Tight BC and tight DAgger on the size-by-degree grid (the 8 cells with N = 200 and 800). In point estimates, both tight learners are above random and below W-greedy in every cell. Tight BC is below W-greedy by 12.5 to 23.2 pp, and its interval excludes zero in every cell. Tight DAgger is below W-greedy by 2.8 to 16.8 pp. Two intervals include zero, both at N = 800, and they belong to different contrasts. One is W-greedy minus tight DAgger at mean degree 4: +2.8 pp [-0.5, 6.9]. The other is tight BC minus random at mean degree 6: +1.5 pp [-1.5, 4.4]. The N = 800 cells with mean degree 4 and 8 use 10 seeds, and the other six cells use 20 (App. C, Table 13).

Scope. The two 10-seed cells and the 12-target witness cell are smaller than the others because their runs did not finish before the revision deadline. Protocol B was not extended beyond N = 800, and §7 lists this as future work.

Comments on the paper

1 comment

Dear Reviewers and AC,

Thank you for your thoughtful reviews and suggestions. We are revising the paper and plan to upload the revised PDF by November 17, followed by point-by-point responses to each review. Before then, we wanted to share a brief update on the main changes and the experiments still underway.

Main changes in the revision:

  1. We have reorganized the paper around a central question: can a learned policy replace the per-candidate metric evaluation required by search? The revised paper focuses on three findings. First, the learned policies we tested do not outperform greedy search. Second, several controlled changes improve the learners, but the gap remains under a matched protocol. Third, combining a certificate with a witness search helps distinguish infeasible targets from cases where search fails to find a solution.

  2. We added a matched protocol that gives greedy and the value learner the same score basis, the same number of candidates (K = 6), and identical start graphs. Greedy still performs better by 29.3 percentage points across all 20 seeds, while requiring less computation.

  3. We also tested several ways to improve the learners: using demonstrations that reach the tightest band, providing the learner with exactly the per-candidate quantities available to greedy, and training with a proper multi-epoch clipped PPO. All three changes help, but none eliminates the gap. Even the best-informed learner remains 11.9 points behind greedy.

  4. To better understand whether the targets can actually be reached, we ran a long simulated-annealing search. It found satisfying graphs at the tightest band for 45 of 50 sampled targets, suggesting that most of these targets are feasible. We have also clarified that a failure by greedy only means it could not find a solution within its proposal set, not that the target is infeasible.

  5. We now describe the tolerances as a fixed benchmark setting. To give readers a sense of their scale, we compare them with the spread of the five metrics across 396 real networks. The default tolerances correspond to roughly 12–18% of each metric's interquartile range. We also checked six alternative tolerance profiles and found that the ordering of methods remains unchanged.

  6. We have corrected the attribution of the modularity-spectral-gap inequality to Fasino & Tudisco (2017) and McDiarmid & Skerman (2020). Our contribution is to use this inequality as a pre-search infeasibility test. We have also made the terminology more consistent throughout the paper, particularly for protocols, bands, and method names.

  7. We substantially rewrote the paper for readability. The task, the two protocols, and every method are now defined in one setup section before any result is reported, and each results section opens with the question it answers. We shortened long sentences, defined every term at first use, and moved narrow side results and secondary statistics to the appendix so that the main text follows the three findings.

Experiments still underway (no results reported here):

  • A larger GFlowNet study covering more configurations and seeds.
  • A size × mean-degree grid (N = 100 to 800, mean degree 4 to 10, with 20 seeds per cell).
  • Retraining the learners with longer episodes (T = 120 and 240, compared with the current T = 60).
  • A witness search for the unreached targets in our 747-target mixed pool, along with a degree-sequence bound on path length.

We had also planned two additional extensions: tight-demonstration imitation at N = 800 and experiments at N = 2000. Unfortunately, these will not be completed in time for the revision due to computational constraints. We will make this limitation clear in the paper.

Thank you again for your time and feedback.

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.