acceptodds
Under review as a conference paper at ICLR 2027

Discrete Flow Matching for Extremal Graph Search with Zero-Shot Size Transfer

Abstract

Many existing neural systems for mathematical discovery of extremal combinatorial structures alternate between generation and local search, retraining a generative model on the best refined constructions. This model is typically parametrized as an autoregressive transformer over a serialization of the object, which is a questionable choice for graphs: vertex symmetry is not necessarily encoded, and edge decisions cannot be revised within the autoregressive sampling pass. This work instead draws on graph neural networks and discrete flow matching: a permutation-equivariant pair network predicts all edge decisions at once, and iterative denoising lets each be revisited as the rest of the graph changes. The same weights can generate graphs of different sizes. We show that this reuse works: generators trained on smaller graphs construct optimal -free graphs at unseen sizes, before local search, and in up to 49% less training time than training at each target size. Reward fine-tuning further improves their value as search starts, with gains extending beyond the fine-tuning size. One selected adapted generator produces a 137-edge -free graph on 42 vertices before local search, matching the best-known count without training at that size. To the best of our knowledge, this is the first time a learned approach attains this bound. Experiments on Ramsey construction demonstrate zero-shot size transfer under a second constraint family.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
discrete flow matching, graph neural networks, zero-shot transfer, patternboost, equivariance

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_S7WsOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper combines a permutation-equivariant Pairformer with discrete flow matching within a PatternBoost-style loop for extremal graph search. The generator iteratively revises edge decisions and reuses its weights across graph sizes. Reward fine-tuning further optimizes the quality of proposals after local search. Experiments cover C4C_4-free edge maximization and Ramsey construction. Notably, a frozen model trained on 33 vertices directly generates optimal C4C_4-free graphs on 34–37 vertices, while an adapted model produces a 42-vertex graph with 137 edges, matching the best-known lower bound. A bounded-size expressivity result provides structural motivation for the architecture.

Critical strengths
  1. The 33-vertex checkpoint is selected using only training-size performance and generates optimal graphs at several unseen sizes before local search. This is a substantive demonstration that learned construction behavior can remain useful beyond the training size. Although optimal samples are rare, verified constructions are valuable outcomes in this setting.
  2. Reward fine-tuning improves mean refined quality across almost all tested adaptation/evaluation settings. The distinction between raw and refined outputs also reveals that less frequently feasible proposals can nevertheless become better search starts. Density-matched, extension, and random-start controls provide useful evidence that learned graph structure contributes to the results.
Critical weaknesses
  1. The structural basis and scope of transfer remain unclear. The strongest results concern C4C_4-free graphs, whose low-order structural constraints closely match the pair-based architecture. The density and extension controls are useful, but they do not establish whether successful graphs at different sizes belong to a common construction family. Given the more limited transfer under Ramsey constraints, it remains unclear how much of the success depends on structures specific to the C4C_4 task. This limits the transfer results' broader implications.
  2. The adaptation and efficiency comparisons do not fully separate the effects of optimization, additional data, and model selection. RL receives fresh search feedback, whereas the denoising control uses a fixed corpus. Consequently, the comparison does not establish whether RL offers an advantage over continuing the PatternBoost loop with updated data under the same additional search budget. Moreover, Table 3 reports the costs of selected pipelines, excluding model-selection costs, and the adapted models are selected based on target-size results. The reported training-time savings do not establish an overall efficiency advantage.
Questions for authors
  1. Do the high-quality graphs found at training and unseen sizes belong to the same construction families, or have simple extension relationships? Beyond the extension control in Appendix F.5, to what extent could these structural relationships explain the observed transfer?
  2. RL receives fresh search feedback, whereas the denoising control uses a fixed corpus. Would the gains persist against continuing the PatternBoost loop with an updated corpus under the same additional sampling and local-search budget?
  3. Would the training-time savings in Table 3 remain after including model-selection costs, or when the adaptation size is chosen without evaluating candidate models at the target size?
3 comments

We thank the reviewer for their positive assessment and thoughtful questions.

Q1 and W1: Structural relationships and scope. Some observed optima are related by vertex extensions, but they do not form a single chain. Deleting a vertex links the observed n=35n=35, n=34n=34 and some n=33n=33 optima. However, none of the five observed n=36n=36 optimum classes contains the n=35n=35 optimum, while two of the three n=37n=37 optimum classes contain an observed n=36n=36 optimum.

The 137-edge n=42n=42 construction contains none of the eight tested source/adaptation maximum classes as an induced subgraph. These checks exclude specific extension relationships, but do not determine broader construction-family membership or explain the transfer mechanism. The original training corpora were also not retained. We will keep broader transfer claims limited, given the stronger evidence for C4-free graphs than for Ramsey constraints.

Q2 and W2: Continued PatternBoost with fresh feedback. Yes, the gains persist in this comparison. Starting from the same three n=33n=33 checkpoints, we compared continued PatternBoost with reward fine-tuning at n=36n=36, giving each 100,000 additional proposals, the same local search and 2,000 updates. For continued PatternBoost, each round samples 10,000 new graphs from the current model and improves them with local search. We then train on the best 100 graphs from that round together with an archive of up to 50 elite graphs, using 200 updates of the original flow-matching objective. We repeat this for ten rounds, so the training data are refreshed as the model changes. After adaptation, we evaluate the final models at n=36,37,40,42n=36,37,40,42 without further training.

Evaluation size nnContinued PBReward fine-tuning
3699.95 ± 0.13106.44 ± 0.17
37103.75 ± 0.15109.32 ± 0.09
40115.22 ± 0.19119.61 ± 0.10
42122.93 ± 0.18126.65 ± 0.22

Values are mean edges after local search ± SD across source seeds, using 10,000 fresh attempts per model and size. Reward fine-tuning improves this mean in every seed at every size, although raw feasibility decreases. It produces no raw feasible samples at n=40,42n=40,42. Adaptation takes about 119 minutes versus 106 for continued PatternBoost on A40.

Q3 and W2: Selection cost and efficiency. Yes, the efficiency gains also hold in our new comparison without grid-based checkpoint selection. We fixed the pretraining and fine-tuning sizes at 25 and 40, retained all three seeds’ final models, and compared against training directly at size 40. Fine-tuning uses 100,000 additional proposals and 2,000 updates. Each final model is evaluated on 10,000 fresh samples with the same local search.

At n=40n=40Pretrain 25 → fine-tune 40Train directly at 40
Best edges after local search124121
Mean edges after local search115.56 ± 4.74115.59 ± 0.17
Raw feasibility (%)037.46 ± 13.71
Total time per seed (A40 hours)17.8433.88

Best denotes the maximum across three seeds; means and feasibility show mean ± SD across seeds. All samples are feasible after local search. Timings include the full pretraining, fine-tuning and evaluation costs.

We still obtain similar average quality after local search and better best constructions with 47% less execution time, although fine-tuning varies more across seeds and relies more on local search. This comparison uses a fixed recipe at previously studied sizes. Of course, it still does not include the historical cost of finding that recipe. We will also clarify that the original Table 3 timings exclude model selection.

We thank the reviewer again for their useful comments, which helped us to further improve our work.

The author resolved my concern, and I will keep my score of 3.

We are glad that our response resolved the reviewer's concerns and thank them again for their initial valuable review.

Reviewer_TY4qOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates discrete flow matching for extremal graph search, with an emphasis on zero-shot generalization across graph sizes. The authors integrate a permutation-equivariant Pairformer with discrete flow matching to enable iterative refinement of graph structures. They further introduce reward-based fine-tuning to improve the quality of generated candidates based on local search outcomes. Experiments on C4-free and Ramsey graph construction demonstrate promising results, particularly in generating high-quality solutions at unseen graph sizes without additional training.

Critical strengths
  1. The paper addresses an interesting and meaningful problem with potential implications for AI-assisted mathematical discovery. Learning to construct extremal graphs is a challenging task, and investigating whether graph generators can generalize beyond their training sizes is a worthwhile research direction.

  2. I particularly appreciate the focus on zero-shot size transfer, as training separate models for different graph sizes can be computationally expensive and may limit their practical applicability.

  3. The reported results are encouraging, especially the ability to generate high-quality constructions at unseen graph sizes without additional training. The experiments on both C4-free and Ramsey graph construction also provide useful evidence of the potential of the proposed approach.

Critical weaknesses
  1. The paper points out some limitations of autoregressive graph generation, but it is less clear why existing graph generation approaches cannot address these issues. I would like to see a more concrete discussion of the research gap and what motivates this particular design.

  2. The method itself could be better justified. Most of its components, including Pairformer, discrete flow matching, and reward fine-tuning, are adopted from existing work. While combining them for extremal graph search is reasonable, I find the methodological contribution somewhat limited. It is also unclear which component is mainly responsible for the observed zero-shot transfer.

  3. Another concern is the experimental comparison. Most of the experiments are conducted within the authors' own framework, with relatively few comparisons against alternative graph generation methods. More competitive baselines and controlled ablations would make the results more convincing.

  4. The related work section is rather brief. Some closely related graph generation and generative search methods are mentioned without much discussion of their differences from this work. I think this part deserves more attention, particularly given the use of several existing techniques.

Questions for authors
  1. What is the main research gap that distinguishes this work from existing graph generation approaches?

  2. Can the authors provide more direct comparisons or ablations to clarify the contributions of the individual components, particularly to zero-shot size transfer?

4 comments
AuthorsOpenReview ↗

Response to Reviewer TY4q (1/2)

We thank the reviewer for their careful reading and valuable comments and suggestions. Let us group related questions and weaknesses below.

Q1, W1 and W4: Motivation, research gap and related work. The research question we want to address is whether learned extremal search can reuse a model across graph sizes, rather than train a new model for each size. We study how good the resulting constructions are compared with alternative generators, and whether adapting a pretrained model can save computation over training from scratch. Our contribution lies in adapting the combination of PairFormer, discrete flow matching and reward fine-tuning to these questions and testing it across sizes.

We agree that the related work deserves more attention. We will expand the discussion of objectives, vertex permutations and size transfer, including GraphARM [1], which learns an autoregressive node ordering, and ConStruct [2], which enforces structural constraints during generation. Axplorer [3] directly addresses learned extremal search, and we have now included it as a baseline.

The reviewer is also right to question our discussion of AR limitations. Our new AR baseline does transfer across sizes and achieves higher mean quality after local search, while flow finds better best constructions at all six tested sizes under matched training-presentation and proposal budgets. We will revise the motivation to acknowledge this tradeoff and refer to the full comparison in moAW (Q1).

AuthorsOpenReview ↗

Response to Reviewer TY4q (2/2)

Q2, W2 and W3: Component ablations and baselines. We agree with the reviewer that the novelty of the individual components is limited, and that their contributions could (and should) have been ablated more thoroughly. PairFormer gives us equivariant pair representations and shared parameters across sizes, while discrete flow matching allows whole-graph generation and revision of edge decisions. To test how much these choices matter, we added the following comparisons.

AR baselines. We evaluated Axplorer with its own search/training loop, as well as an Axplorer-inspired AR model within our PatternBoost loop. At n=40n=40, we obtain:

ModelBest edges after local searchMean edges after local searchRaw feasibility (%)
Native Axplorer113106.30 ± 0.020
AR within our loop114113.29 ± 0.56100
Flow121115.48 ± 0.2534.14

Best denotes the maximum across three seeds; means show mean ± SD across seeds. Training presentations and proposal budgets are matched. Native Axplorer retains its own loop, while the second baseline compares generators within ours. At this size, flow achieves both higher mean quality and better best constructions. Further sizes are reported in mEzV (Q1).

Architecture and equivariance. Replacing gated triangle attention with triangle multiplication and ordinary row attention reduces mean quality after local search at the training size, from 97.62 to 95.17 edges at n=35n=35, and the best construction from 105 to 101 edges (moAW, W1 and W2).

We also added positional features to PairFormer, removing enforced equivariance while keeping its parameter count unchanged. This model still transfers, with broadly comparable mean quality after local search, but the equivariant model finds better best constructions at every tested size. At n=42n=42, for example, their best graphs have 129 versus 124 edges. Equivariance therefore helps best construction quality in this comparison, although it is not necessary for the transfer observed after local search (mEzV, Q2).

Training objective and sampling depth. Keeping the PairFormer backbone and training it autoregressively gives high feasibility but substantially weaker construction quality at the same intermediate training stage; size-transfer evaluation remains pending (mEzV, Q2). Increasing the number of flow sampling steps improves quality at both training and unseen sizes, at higher sampling cost (moAW, W1 and W2).

Reward fine-tuning. Compared with continuing PatternBoost using fresh search results and the same additional proposal and update budgets, reward fine-tuning achieves higher mean quality after local search in every seed at the adaptation size and all three larger sizes (S7Ws, Q2). A separate fixed 25→40 recipe also gives similar mean quality and better best constructions than training directly at 40, using 47% less execution time including pretraining (S7Ws, Q3).

These results show that size transfer is not exclusive to our architecture. They also identify advantages in best construction quality and show that reward fine-tuning improves on continued PatternBoost. We do not isolate a single component responsible for transfer, but the new comparisons give a clearer picture of what each design choice contributes. We will revise the paper around these findings and expand the related-work discussion accordingly.

We thank the reviewer again for their valuable suggestions, which have helped us to gain a deeper understanding of the problem that our work addresses.

[1] Kong et al. Autoregressive Diffusion Model for Graph Generation. ICML, 2023.

[2] Madeira et al. Generative Modelling of Structurally Constrained Graphs. NeurIPS, 2024.

[3] Alfarano and Charton. Axplorer. Research report and software, 2026.

Reviewer_TY4qOpenReview ↗

Comment

The author resolved my concern, and I raised my score.

We are glad that our response resolved the reviewer's concerns and thank them again for their valuable initial review.

Reviewer_mEzVOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Authors present a graph generator for PatternBoost-style extremal search that replaces the autoregressive transformer with a permutation-equivariant Pairformer trained by discrete flow matching. All possible edges are updated in parallel and can be revised during sampling, and shared weights allow evaluation at different graph sizes

Critical strengths

S1: Replacing the autoregressive generator with an equivariant, iteratively denoised one is a natural fit for graphs, since edge decisions no longer depend on an arbitrary vertex order and can be revised as the rest of the graph forms.

S2: Zero-shot size transfer for learned extremal search is a very interesting and under-explored direction, and the paper shows that a generator trained on smaller graphs can produce optimal C4C_4-free graphs at unseen sizes

S3: The experimental results seem to be carefully and honestly reported, while open about where comparisons are not matched in compute.

Critical weaknesses

W1: One of the author's central claims; that an equivariance and revisable generator suits graphs better than an autoregresive transformer, is not tested directly.

W2: The fine-tuned results are picked from a large grid of checkpoints using evaluations at the target size itself. I believe that claiming the best-known bound is matched without training at that size is misleading as the directly trained baselines get far less selection.

W3: Each component is taken from prior work, which the paper credits and cites. But the contribution lies mostly in plugging these into the PatternBoost loop.

Questions for authors

Q1: Can you re-run the PatternBoost transformer under the same local search and training budget as your generator?

Q2: Can you ablate the two motivating proparties separately, e.g., a non-equivariant flow model and an equivariant autoregressive generator, to show which one drives the gains?

5 comments
AuthorsOpenReview ↗

Response to Reviewer mEzV (1/2)

We thank the reviewer for their positive assessment and useful suggestions.

Q1 and W1: Matched PatternBoost comparison. We agree that this comparison is needed. We used an Axplorer-inspired AR model within our PatternBoost loop, since our earlier experiments with our implementation of the original PatternBoost transformer gave weaker results. Both generators use the same local search, training presentations and proposal budget. We trained each method separately at each size with three seeds, then evaluated each final model using 10,000 fresh samples followed by the same local search.

Size nnBest flowBest ARMean flowMean ARRaw feasible flow (%)Raw feasible AR (%)
20464645.96 ± 0.0145.63 ± 0.5797.18100
25636160.15 ± 3.4460.98 ± 0.0038.01100
30857875.90 ± 5.4777.96 ± 0.0115.89100
3610898101.79 ± 0.2697.98 ± 0.0021.50100
40121114115.48 ± 0.25113.29 ± 0.5634.14100

Best and Mean columns report edge counts after local search. Best denotes the maximum across all three seeds while means show mean ± SD across seeds. Raw feasibility is averaged across seeds.

We find an interesting tradeoff: AR generates feasible graphs very reliably and achieves higher average quality at n=25,30n=25,30, but flow finds better best constructions at every size above n=20n=20. At n=36,40n=36,40, flow also has higher means. Despite its high raw feasibility, AR repeatedly generates a small set of graphs: at the smaller sizes, we observe only 43–49 distinct labelled graphs per 10,000 draws. For comparison, at n=30n=30, flow produces approximately 1,589 distinct labelled feasible graphs per 10,000 raw samples on average across seeds. We think that these results still support the claim that our setup "suits graphs better", however we will present it in a more balanced way.

AuthorsOpenReview ↗

Response to Reviewer mEzV (2/2)

Q2 and W1: Equivariance and generation objective. We thank the reviewer for the suggestion of ablating these properties directly, as they allowed us to gain new insights into our method.

Equivariance. To directly test the contribution of equivariance while keeping our backbone, we added fixed sinusoidal vertex-position features to PairFormer, removing enforced equivariance while preserving its parameter count and allowing size transfer. We trained both models at n=30n=30 and evaluated 10,000 samples per model and size:

Size nnBest equivariantBest positionalMean equivariantMean positionalRaw feasible equivariant (%)Raw feasible positional (%)
30858275.90 ± 5.4780.51 ± 1.5315.89398.987
33969485.69 ± 4.7087.60 ± 1.131.6630
3610910595.97 ± 4.1396.92 ± 1.200.0130
3711210799.52 ± 3.9999.99 ± 1.1100
40121117110.52 ± 3.85110.18 ± 1.0400
42129124117.98 ± 3.65117.12 ± 0.8600

Best and mean values are edge counts after local search, with maxima across three seeds and mean ± SD across seeds. Raw feasibility is averaged across seeds. The positional model also transfers, with broadly comparable mean quality after local search, but the equivariant model finds better best constructions at every tested size. This ablation suggests that the contribution of equivariance is rather modest.

Training objective. We also trained an equivariant autoregressive PairFormer. Similar to the AR baselines, we observed high feasibility but substantially weaker construction quality than flow matching at the same training stage. This, together with the equivariance ablation, suggests that the discrete flow matching (DFM) objective is an essential driver of success in our method.

W2: Training and model selection. We agree that target-size model selection needs to be distinguished from training at that size. The 137-edge n=42n=42 construction was found without gradient updates at n=42n=42, but we selected the checkpoint using evaluations at that size. The directly trained baselines received a smaller selection budget. We will make this imbalance explicit and clarify that the reported timings exclude model selection. We want to however point out, that the gains persist without evaluating a huge grid: our fixed 25→40 experiment across three seeds is reported in S7Ws (Q3 and W2).

W3: Contribution. Finally, we agree that the individual components are established. What we study is whether their combination can find good extremal constructions beyond the training size, and how local search and reward fine-tuning affect this transfer. The new comparisons help clarify this: AR can also transfer, enforced equivariance is not strictly necessary (but helps), and reward fine-tuning improves quality at both the adaptation size and larger sizes compared with continued PatternBoost (see S7Ws, Q2). We will revise the manuscript to make these findings and the scope of our contribution clearer.

We thank the reviewer again for their thoughtful suggestions, which helped us to improve our work.

Thank you for the detailed rebuttal and new experiments, which partially address my concerns.

Regarding W1/Q1/Q2, while the flow generator finds stronger best graphs, the new results show that autoregressive and non-equivariant baselines also transfer across sizes with comparable or higher average quality after local search, and the equivariant autoregressive ablation has no reported numbers or transfer test. Regarding W2/W3, the grid-free size-40 run fine-tunes at the target size rather than an unseen size. As I believe that the zero-shot results remain valuable -- I will keep my score of 3.

Reviewer_moAWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper tackles the problem of extremal graph discovery using PatternBoost (alternating generation and local search). The authors take a permutation-equivariant pair network (triangle-attention Pairfomer) and train it with a denoising objective (discrete flow matching).

The architecture is permutation-equivariant and size-independent, and can therefore directly applied to any graph size. The authors claim and show empirically that trained movels generalize to larger graph sizes than they were directly optimized on. Second, the authors use reward fine-tuning based on the quality of the graph discovered via local search around a sample. The paper shows that the reward fine-tuning improvements transfer across graph sizes too.

The authors empirically demonstrate the proposed method on C4-free edge maximisation and Ramsey construction.

Critical strengths
  1. The main strength is the strongly justified synthesis of equivariant generation using a GNN (pair-former architecture, Section 3.2) and search-guided RL fine-tuning (Section 3.3). The motivation that early edge commitments can be revised via discrete flow matching (Section 3.1, Eq. 5) and that any vertex-ordering bias is removed through permutation equivariance (Appendix A.3) is strong, and is further supported by the expressivity results for C4C_4 move costs (Proposition 1 in Section 3.5 and Appendix B).

  2. The extensive empirical evidence for the claims is convincing for both zero-shot generation of optimal graphs (Section 4.1, Table 1, and Table 2 for Ramsey graphs) and generalisation across sizes (the 700-setting adaptation grid in Section 4.2, Figure 2, and Appendices E–G), reaching the best-known 137-edge C4C_4-free bound at n=42n=42 before local search (Figure 1b, Table 3), which is a remarkable point in itself.

Critical weaknesses
  1. While acknowledged in the limitations (Section 5), the paper is missing learned ablations to disentangle how much of the benefit comes from the iterative revision of the flow-matching objective (Section 3.1) versus how much comes from the triangle-attention architecture choice (Section 3.2).

  2. Beyond the target-size PatternBoost comparisons (Table 3) and the heuristic density and extension controls (Appendix F.5, Table 14), the paper lacks a comparison on generalisation across sizes against competitive learned baselines, as well as architecture and iterative training ablations (such as varying the number of denoising steps KK or testing a simpler GNN backbone).

Questions for authors

Why an autoregressive baseline could not also be evaluated for zero-shot size transfer? In principle, a Transformer does not require extra parameters to generate longer sequences if equipped with relative positional encodings and a prefix-compatible (e.g., vertex-by-vertex or upper-triangular column-wise) edge serialization, or via autoregressive GNNs. Testing whether an autoregressive model can generalise simply by extending the generation sequence would add extra strength to the paper's core motivation in Section 1.

1 comment

We thank the reviewer for their careful reading, their generally positive assessment of our work and the useful suggestions.

Q1: Can an autoregressive model transfer across sizes? Agreed, the limitations we pointed out concern the used graph serialization rather than autoregressive (AR) generation itself. We appreciate reviewer's suggestion of column-wise edge serialization with rotary positional embeddings. We now trained a model using this serialization on n=30n=30 under matched training-presentation and proposal budgets for three training seeds. We then evaluated the same final models at six sizes without further training, using 10,000 fresh samples per model and size:

Evaluation size nnBest ARBest flowMean ARMean flow
30828581.11 ± 1.1075.90 ± 5.47
33959689.17 ± 1.2085.69 ± 4.70
3610610998.65 ± 1.3495.97 ± 4.13
37109112101.89 ± 1.1599.52 ± 3.99
40119121111.72 ± 0.73110.52 ± 3.85
42127129118.54 ± 0.73117.98 ± 3.65

Reported results represent edge counts after local search. Best denotes the maximum across all three seeds, while mean columns show mean ± SD across seeds.

We find the results quite interesting: The suggested baseline in fact does show zero-shot generalization behavior, and it even achieves higher average quality after local search. The flow models however find better best constructions at every tested size. We want to point out that the higher mean quality comes at a cost: At n=30n=30, AR's raw feasibility is 99.87% versus 15.89% for flow, but its output is much less diverse: at most 58 distinct labelled feasible graphs per 10,000 draws, versus approximately 1,589 for flow on average. At larger sizes, both depend heavily on local search: AR has no raw feasible samples at n=36,37,40,42n=36,37,40,42, and flow has none at n=37,40,42n=37,40,42 in this comparison. We will revise the motivation to acknowledge that AR can transfer and discuss this tradeoff between average quality, diversity and best constructions.

W1 and W2: Architecture and iterative sampling.

Architecture. We agree that both the architectural choices and the training objective should have been ablated more thoroughly. Regarding the architecture: We trained a simpler architecture, which replaces gated triangle attention with triangle multiplication and ordinary row attention under matched budgets. We obtained mean edges after local search of 95.17±0.08 versus 97.62±0.43 for PairFormer at n=35n=35, across three seeds. Raw feasibility is 27.37% versus 34.06% and best edge counts 101 vs 105. This supports the backbone choice at the training size, without isolating its contribution to size transfer. Due to the different attention mechanisms, the networks also differ in size (1.10M versus 1.24M parameters).

Training objective: We refer to our response to reviewer mEzV (Q2) regarding a controlled ablation which keeps the PairFormer backbone while replacing the discrete flow matching objective by an autoregressive one.

Sampling depth: For the same three n=33n=33 flow models, we varied the number of sampling steps KK using 10,000 samples per model and size:

Size nnSteps KKRaw feasibility (%)Refined mean edgesSampling seconds
331081.29 ± 0.018.3
334081.86 ± 0.1730.1
33160.18386.71 ± 0.71120.2
336429.14790.17 ± 0.81476.5
371095.48 ± 0.029.4
374096.04 ± 0.1436.9
37160.007100.67 ± 0.76146.3
37647.407104.94 ± 0.76579.6
4210114.12 ± 0.0311.6
4240114.61 ± 0.1545.4
42160118.45 ± 0.72181.3
42640.150123.30 ± 0.83722.6

We can clearly see how a higher step count substantially improves both raw feasibility and quality after local search. Sampling seconds refers to generating 10,000 graphs on an A40 GPU.

We thank the reviewer again for their useful suggestions and are happy to answer further questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General rebuttal comment

We thank the reviewers for their very valuable reviews and follow-ups. We appreciate their suggestions of additional ablations, which helped us to gain a better understanding of our work. We are pleased that our rebuttal resolved most of their concerns. Upon acceptance, we will incorporate all additional ablations and new insights into the camera ready version of the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.