acceptodds
Under review as a conference paper at ICLR 2027

Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization

Abstract

Neural solvers provide fast solutions to graph combinatorial optimization problems, but training alone does not guarantee solution quality. Exact methods guarantee optimality but can be prohibitively expensive. We propose Neural Fixed-Parameter Tractable (N-FPT), a neural-model-agnostic framework that uses parameterized algorithms to improve neural solutions without retraining and guide learning. It restricts neural advice to a treewidth modulator and completes the bounded-treewidth remainder exactly. It returns and certifies the best achievable solution under any valid advice, improving the neural solution whenever a better compatible completion exists. We prove this guarantee and global optimality under perfect advice. Its incremental-confidence N-FPT (NIC-FPT) and randomized-deferral N-FPT (NRD-FPT) variants consolidate neural advice. Beyond inference, N-FPT feedback becomes available as neural decisions make exact completion tractable. From that state onward, it supplies what final solution rewards lack: the first decision that rules out every optimal completion and alternatives that preserve one. One exact computation supplies reusable guidance for continuations from that state, even when neural samples miss its optimum. Experiments across graph combinatorial optimization problems demonstrate solution-quality gains with different neural models and robustness to graph-size and distribution shifts. The learned completion model reaches optimal completions more often than reinforcement learning (RL) alone, without an exact solver at inference. N-FPT thus uses graph structure to improve neural solutions and guide learning toward optimal completion.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
fixed-parameter tractability, learning-augmented algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_sp4QOpenReview ↗
Rating
2(−1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper introduces N-FPT, an approach for improving solutions on neural combinatorial optimisation problems based on neural advice, assuming that a treewidth decomposition can be made. With perfect advice, the method guarantees optimality. The paper also presents NIC-FPT and NRD-FPT variants, which use incremental confidence and random deferral respectively in order to improve the solutions of imperfect advice. The approaches can also be used to provide feedback to neural models during training. The paper demonstrates that the method is useful for improving neural approximations without retraining through several experiments.

Based on the strengths outlined in S1 and S2, I recommend acceptance, as I believe the ideas presented to be useful to the NCO community. However, the paper would be greatly strengthened by addressing the weaknesses outlined in W1 and W2. In particular, it is important to understand how the method compares to alternative, less informed post-hoc solution improvement approaches, and to understand the method's limitations.

Critical strengths
  • [S1]: The proposed NIC-FPT and NRD-FPT methods provide useful approaches for improving the performance of neural approximations, building on a useful theoretical foundation.
  • [S2]: The use of N-FPT for providing feedback in the training process is an interesting insight, and demonstrably improves the performance of the trained solvers.
Critical weaknesses
  • [W1]: The proposed method has some important trade-offs which are not the subject of much discussion or analysis. In particular, graph width is a severe limiting factor due to the exponential relationship, but no analysis is provided to demonstrate which problem types or graph types for which this becomes restrictive. Furthermore, the dependence of improvement of N-FPT on advice quality has not been investigated. Without these analyses, it is difficult to determine the settings in which N-FPT is practical.
  • [W2]: No baselines are provided for other post-hoc solution improvement approaches.
  • [W3]: The writing is convoluted and difficult to parse throughout the paper. I recommend that much of the writing, especially the introduction, should be rewritten with a focus on clarity to avoid the abstruse, telegraphic language and ensure that terms are properly defined and precisely used.
Questions for authors
  • [Q1]: The improvements in Table 1 seem quite small in some cases. Can you provide confidence intervals for these values?
  • [Q2]: Can you explain why you have chosen to use regular graphs for some experiments, and RGG/King graphs for others?
  • [Q3]: It is my understanding that the problem formulation only allows for problems where the solution is constructed by selecting an unordered node subset. Is there any way to extend the paradigm to ordered sequences (e.g. TSP), or does that prohibit the tree decomposition?
  • [Q4]: Are there any further limitations to your proposed method?
  • [Q5]: How does your method compare to more traditional post-hoc improvement methods, such as beam search?
6 comments
AuthorsOpenReview ↗

[Authors Response (1/3)]

We thanks the reviewer for their time and effort. We especially appreciate the recognition on the impact of this work to the NCO community. This indeed is our motivation.

Within the limited time, we response by priority based on our understanding to the reviewer's comment.

W1 and Q4: width, advice quality, and limitations.

Width. A natural concern is that exact computation grows exponentially with the width of the graph, so that wide graphs would make N-FPT impractical. However, N-FPT never runs the dynamic program at the width of the input graph. We first choose a target width (Appendix B.8), and then remove a modulator so that every remaining bag fits this width. The cost of exact completion is therefore exponential only in the chosen target width and linear in the number of bags, whatever the width of the input graph (lines 156–161). A wider graph changes only the size of the modulator, that is, how many decisions the neural solver makes. The two parts therefore share the computation: the neural solver decides the vertices that would make exact computation too expensive, and the dynamic program optimizes every other decision exactly. Our dense settings, such as regular graphs of degree 16 and BA graphs (Table 10), test this regime directly.

The target width decides how the two parts share the work: a larger target width shrinks the modulator and trades more exact computation for better solutions. To test this trade-off, we applied N-FPT to two diffusion-based solvers, SDDS (SOTA) and DiffUCO, on their 800 graphs of the standard RB-small benchmark:

Modelη\etaAverage: alone →\to N-FPTGain [95% CI]Improved / worsenedBest of 30: alone →\to N-FPTGain [95% CI]Improved / worsened
SDDS1019.6046→19.606019.6046 \to 19.6060+0.0014 [+0.0004,+0.0030]+0.0014\ [+0.0004, +0.0030]13 / 019.9150→19.915019.9150 \to 19.9150+0.0000 [+0.0000,+0.0000]+0.0000\ [+0.0000, +0.0000]0 / 0
SDDS6519.6046→19.792019.6046 \to 19.7920+0.1875 [+0.1645,+0.2116]+0.1875\ [+0.1645, +0.2116]364 / 019.9150→19.977519.9150 \to 19.9775+0.0625 [+0.0462,+0.0800]+0.0625\ [+0.0462, +0.0800]50 / 0
DiffUCO1019.3769→19.384319.3769 \to 19.3843+0.0074 [+0.0035,+0.0123]+0.0074\ [+0.0035, +0.0123]34 / 019.6675→19.675019.6675 \to 19.6750+0.0075 [+0.0025,+0.0138]+0.0075\ [+0.0025, +0.0138]6 / 0
DiffUCO6519.3769→19.706719.3769 \to 19.7067+0.3298 [+0.2965,+0.3649]+0.3298\ [+0.2965, +0.3649]414 / 019.6675→19.847519.6675 \to 19.8475+0.1800 [+0.1525,+0.2075]+0.1800\ [+0.1525, +0.2075]139 / 0

Raising η\eta from 10 to 65 shrinks the modulator from 48% to 13% of the vertices, and the average gain of N-FPT rises from 0.0014 to 0.1875 for SDDS and from 0.0074 to 0.3298 for DiffUCO. Even the average gain of 0.0014 has a 95% confidence interval above zero. In every row, N-FPT makes no graph worse, as Proposition 3.1 guarantees.

Advice quality. Since the neural solver decides the modulator, the final solution depends on the quality of its advice, and we study this dependence in four ways. In theory, Eq. (2) and Proposition 3.1 show that N-FPT returns the best achievable completion of any advice: a global optimum when the advice is perfect, and never a worse solution than the neural solver's own. Across solvers, Eq. (2) shows that the gain of N-FPT equals the completion loss, the value that a solver loses when it completes its own advice; in the table above, DiffUCO, the weaker model, gains more than SDDS in all four comparisons. In a controlled comparison, N-FPT and NIC-FPT or NRD-FPT run the same exact completion and differ only in advice quality, and better advice gives better results (Table 1). Under distribution shift, solvers tested away from their training distribution give worse advice, and N-FPT still recovers part of the loss (Figs. 3 and 9–12). This dependence motivates the rest of the paper: two inference-time methods and one training method, each of which improves the advice.

Limitations. The main limitation is: our method based on the shape of tree decomposition. However, finding the thinnest tree decomposition is NP-hard itself. The practically fast way remains heuristics, despite prior empirical work [4] has shown that they are strong. Thinner tree decomposition can certainly help our framework on both modulator size and the practical runtime, yet that falls into another research direction. Another angle to interpret the limitation is: Which graph and problem types admit small modulators. In parameterized complexity, this is an exciting but extremely challenging direction.

AuthorsOpenReview ↗

[Authors Response (2/3)]

Post-hoc comparison (W2 & Q5) We clarify that it is not our focus to integrate beam search with neural networks. It requires extra engineering effort beyond our focus: showing that our methods can improve both training and inference ability for neural solvers for combinatorial optimization tasks.

To meet the reviewer's curiosity, we apply the standard beam search as the post-hoc process, that is after training neural model, we use it to score the available nodes and keep the best 20, we select the best moves, and repeat the standard beam search procedure. Within the limited time and computation budget, we run quick tests on the subset regular graph dataset, in total 80 instances, and 20 for each settings.

SettingNIC-FPT, averageN-Beam, averageNRD-FPT, best of 20N-Beam, best of 20
SS291.488290.956297.600295.050
SD172.845172.323178.900176.900
LS368.522368.325377.650373.200
LD230.020229.584235.950233.650

Presentation (W3). We agree with the reviewer that the writing should be improved. We aimed to explain the more complex procedures through visual illustrations and plain language, but the presentation still has room for improvement. Following the reviewer's advice, we will revise the writing, especially the introduction. We thank the reviewer for this helpful note.

Other questions:

Q1. Confidence intervals for Table 1. Most of the small values in Table 1 are the average gains of N-FPT alone. By Eq. (2), the gain of N-FPT equals the completion loss, the value that the neural solver loses when it completes its own advice, so a small gain means that the neural solver already completes its advice almost optimally. Proposition 3.1 also guarantees that, for the same advice, this gain is never negative. NIC-FPT and NRD-FPT go further and improve the advice itself. For GNN+RL, whose N-FPT gains in Table 1 are the smallest, the table below reports each gain over the standalone solver with a 95% confidence interval over the 300 pairs of test graph and training seed in each setting:

SettingN-FPT, average gainNIC-FPT, average gainNRD-FPT, best-of-20 gain
SS+0.027 [+0.023,+0.031]+0.027\ [+0.023, +0.031]+0.21 [+0.09,+0.32]+0.21\ [+0.09, +0.32]+2.22 [+2.04,+2.40]+2.22\ [+2.04, +2.40]
SD+0.004 [+0.003,+0.006]+0.004\ [+0.003, +0.006]+0.01 [−0.06,+0.09]+0.01\ [-0.06, +0.09]+2.33 [+2.16,+2.50]+2.33\ [+2.16, +2.50]
LS+0.036 [+0.032,+0.041]+0.036\ [+0.032, +0.041]+0.15 [+0.03,+0.27]+0.15\ [+0.03, +0.27]+3.37 [+3.17,+3.58]+3.37\ [+3.17, +3.58]
LD+0.005 [+0.003,+0.008]+0.005\ [+0.003, +0.008]+0.01 [−0.08,+0.10]+0.01\ [-0.08, +0.10]+3.05 [+2.83,+3.27]+3.05\ [+2.83, +3.27]

The intervals of N-FPT and NRD-FPT win in every setting, and neither method does worse than the standalone solver on any of the 300 pairs. On SD and LD, the gains of N-FPT round to zero in Table 1; however, their intervals still stay above zero. Even where the gain is this small, N-FPT certifies every returned solution as the best achievable completion of its advice.

NIC-FPT changes the advice by design: in each round, NIC-FPT fixes the vertices that most samples select, and the next round redraws only the decisions that remain open. The final advice of NIC-FPT therefore differs from the advice of the standalone solver. If NIC-FPT used the same advice as the standalone solver, its gain could never be negative, exactly as Proposition 3.1 guarantees and as the N-FPT column shows. A vertex that most samples select can still be a poor choice, so the advice of NIC-FPT is rarely worse than an independent sample; even so, the average gain of NIC-FPT over the standalone solver is still positive, and stronger than N-FPT in every setting. For GFlowNet, across the three training seeds, we have the same statistical observation. We will add these intervals to Appendix B.

Q3. Other problems such as TSP. The tree decomposition does not prohibit ordered solutions. N-FPT needs only a dynamic program over a tree decomposition that accepts fixed decisions. By Courcelle's theorem (lines 46–48) and its extension to optimization [1, 2], such programs exist for every problem expressible in monadic second-order logic, which includes Hamiltonian cycles. For TSP specifically, Bodlaender et al. [3] give a deterministic dynamic program over a tree decomposition whose running time is single exponential in the treewidth and polynomial in the graph size. TSP is therefore fixed-parameter tractable parameterized by treewidth, and N-FPT can directly use this dynamic program to complete neural advice for TSP. Adapting the advice and the dynamic program to tours requires design changes and experiments that we leave to future work.

We hope our explanation meets the reviewer's expectation, and if possible, can lead to a positive reconsideration. We thank for your time and effort.

AuthorsOpenReview ↗

[Authors Response (3/3)]

[1] Courcelle, Information and Computation, 1990.

[2] Arnborg, Lagergren, and Seese, Journal of Algorithms, 1991.

[3] Bodlaender, Cygan, Kratsch, and Nederlof, Information and Computation, 2015.

[4] Maniu, Senellart, and Jog, ICDT, 2019.

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

This paper introduces N-FPT, a learning augmented fixed-parameter tractable framework for combinatorial optimization problems on graphs. The authors demonstrate this framework on the maximum independent set, maximum cut and minimum vertex cover problems. The framework combines standard neural solvers with a (treewidth) parameterized dynamic program. To this end, on a fixed tree decomposition obtained via the min-degree heuristic, they solve a MILP to find MηM_\eta, the smallest vertex set whose removal from every bag in the tree decomp. reduces the bag's width to a given η\eta. Then, they use a neural solver to obtain SθS_\theta, a valid solution. SθS_\theta is restricted to MηM_\eta, and used as "advice". Subsequently the dynamic program operates exactly only on nodes outside MηM_\eta according to the given advice.

In their formulation, they reduce the advice regret term (that cannot be reduced using exact completion) by introducing two prediction wrappers. NIC-FPT runs KK neural samplers per round, across RR rounds, then commits any vertex whose selection count crossed threshold κ=0.8K\kappa = 0.8K, conditioning further samples on these committed vertices only. NRD-FPT starts from a complete valid sample instead, defers each selected vertex with probability p=0.8p = 0.8, and resamples the released vertices before the next iteration. The experiments in section 3 seem to show that N-FPT alone is unable to drive gains over other methods, while NIC-FPT and NRD-FPT provide most of the empirical heft.

Section 4 then introduces feedback based training for neural completion. During trajectory sampling, when a state asa_s is reached from which the problem becomes tractable, the dynamic program builds a shared state representation of all possible completions from asa_s, which results in finding the first subsequent completion that eliminates every optimal completion. The training data consists of partial assignments paired with the set of next selections that preserve a surviving optimum, and training is done using standard policy learning. The authors compare to REINFORCE on ∼300\sim 300 node RGG and King graphs across twelve settings.

Critical strengths
  1. Section 4's training with feedback is the strongest contribution of this paper imo. The shared dynamic programming characterization of which next move helps best preserve the optimum is a strong RL training signal. Their training signal (1) keeps mistakes localized to particular decisions and (2) does not need an exact oracle on the whole trajectory. Further, they are able to represent Os\mathcal{O}_s (full set of optimal completions with feedback) in polynomial space even if ∣Os∣|\mathcal{O}_s| is exponential.

  2. The experiments broadly cover two neural architectures, three optimization problems, five graph families (albeit synthetic data), four size configurations and across-family generalization. This is a pretty thorough benchmark. Moreover, the authors control on several variables separately: model architectures, training graph families, a0a_0 (initial assignments), optimizer updates, seeds, etc.

Critical weaknesses
  1. One issue I have with the current experiment setup is that no benchmarking has been done against real-world datasets. Angelini & Ricci-Tersenghi (Nature MI 2022) proposed that difficult benchmarks were required for neural combinatorial optimization; Böther et al. (ICLR 2022) partly contributed to this effort by building such a suite. Zhang et al. (NeurIPS 2023), which this paper uses as its primary neural solver, moved from Erdos-Renyi graphs to RB and SATLIB. Even Li et al. (IJCAI 2026) stratified their experiments into “easy” real-world graphs and “hard” synthetic graphs. Wu et al. (“Unrealized Expectations”, TMLR 2026) experimented with Zhang et al.’s GFlowNet and showed that it does not beat a degree-based greedy algorithm on standardized MIS instances.

The authors chose a benchmark set that overlaps with what Angelini etc. call insufficient. The reported “robustness to graph size and distribution shift” measures within synthetic families whose treewidth behaviour is not that heterogenous. Ideally, they should experiment with RB, SATLIB and Li et al.’s “easy” real world graphs. DIMACS would perhaps be another good choice.

  1. The tree decomposition, MILP, dynamic program with advice algorithm, and bounded-width dynamic program pipeline is lifted from Li et al. 2026. The paper’s neural sampler contributions, NIC-FPT and NRD-FPT, are not really novel additions so much as engineering. Section 3 as a whole is not that novel.

  2. N-FPT by itself is not much of a contribution for the MIS and MVC problems. This follows from the results in Table 1, where GFlowNet and GNN-RL averages don’t see much of an increase. The paper’s empirical results rest on NIC-FPT and NRD-FPT, which are heuristic and iterative-repair wrappers over N-FPT and by themselves don’t provide any guarantees. There should be an ablation that runs any of the two wrappers without treewidth DP and then compares the solutions obtained.

  3. Even within the synthetic regimes that this paper experiments with, Section 3’s experiments use 800-1200 node graphs whereas Section 4 is limited to around 300 nodes. It is unclear whether the method and results in Section 4 carry over to the graphs in Section 3, or whether they would hit the 2 million state cap (Appendix B7) frequently. There also needs to be more transparent reporting of the rate at which the state cap(s) is/are hit (broken down by graph family and size of |a_0|).

  4. The RL-alone baseline in Section 4 seems to be a weak one. The baseline is REINFORCE with leave-one-out on K=4 trajectories per update. It is perhaps a simpler variance-reduction trick and noisier than a learned-value method (such as PPO). K=4 is also a very low number of samples. There is also no warmstart and the policy is initialized from random weights and made to discover a good enough node selection strategy from scratch on the MIS problem. If we want to keep REINFORCE as a baseline here, there should atleast be a value baseline (a second learned network whose value is subtracted from return R) and an entropy bonus (to reward being uncertain). Additionally, it would be nice to have a lambda ablation.

Questions for authors
  1. Is the omission of real-world datasets from your benchmark intentional? If so, how would you defend that, given that earlier works in the literature try to address this?

  2. How is “perfect advice” really defined here? It is not empirically measured in the paper. How do we guarantee consistency, i.e., what fraction of test graphs have a aθa_\theta consistent with Gurobi’s optimum on MηM_\eta?

  3. The MILP is excluded from the FPT bound. The 1 second per instance figures that we see in the paper are for the 800-1200 node graphs from Section 3. My understanding is that that regime might be more well-behaved. Is there a worst-case characterization study for this (e.g. graphs where the TD is wide and not min-degree)? What is the modulator size ∣Mη∣|M_\eta| as a fraction of ∣V∣|V| across test graphs?

  4. NIC-FPT seems to use around 100 forward passes per instance (5 rounds x 20 samples) and NRD-FPT uses 5 passes. STANDALONE best of 20 uses 20. Does NIC-FPT have a larger sampling budget advantage over STANDALONE best of 20? Could you report STANDALONE best of 100 and best of 5 alongside the current numbers for better understanding?

  5. Braverman et al. 2024 (APPROX, learning augmented MIS) and Dong et al. 2025 (ITCS, learning augmented max cut) have not been compared against empirically or theoretically, although they are quite recent in the literature. How would your method perform against these?

8 comments
AuthorsOpenReview ↗

[Authors Response (1/3)]

We thank the reviewer for the comments on identifying N-FPT feedback as the strongest contribution of the paper, and finding our experiments thorough and well controlled. We believe the main concerns come from two readings of the paper. First, the reviewer views Section 3 as the pipeline of Li et al. [1] and describes NIC-FPT and NRD-FPT as "wrappers" that add only engineering. The term "wrapper" is unclear to us, so we explain below what the two methods do and why we designed them. Second, the reviewer appears to read Section 4 as a benchmark of RL algorithms. We address both points in turn.

First, the novelty of Section 3 and the role of NIC-FPT and NRD-FPT.

We build on the dynamic program of Li et al. [1], and we credited it in lines 55–58. However, Li et al. use it to improve existing heuristics and treat the heuristic's advice as fixed. The final solution therefore depends on the quality of the advice, which Li et al. do not study.

Our paper contributes the missing learning insights of this framework. Under N-FPT, the dynamic program optimizes every decision outside the modulator, so the advice is the neural solver's only influence to the final solution. The dynamic program cannot improve the advice, because the advice is its input. We therefore ask how the quality of the advice determines the final solution, and how to improve the advice. Section 3 improves the advice at inference time without retraining, and Section 4 improves the advice through training. Section 3 answers these questions with three insights, each supported by our experiments.

1. Better advice is a free win to close the remaining gap. Eq. (2) splits the neural solver's gap to the global optimum into advice regret (the loss caused by the decisions fixed on the modulator), and completion loss (the loss from the neural solver's decisions on the remaining vertices). For any valid advice, N-FPT returns the best achievable completion directly and with a guarantee, which removes the completion loss. N-FPT therefore never does worse than the neural solver (with the same advice), and it returns a global optimum when the advice is perfect, meaning that the advice agrees with some global optimum (Proposition 3.1). However, only better advice can reduce the advice regret (lines 175–176). NIC-FPT and NRD-FPT target exactly this points, using the neural solver's own samples without retraining: NIC-FPT fixes the vertices that most samples select and resamples the rest, while NRD-FPT randomly defer selected vertices of a sample and resamples them. Since both methods improve only the advice, each returns the best achievable completion of its final advice, with the guarantees of Proposition 3.1 (lines 185–187; Appendix B.10). The concern in Weakness 3 that the two methods lack guarantees therefore does not apply. And indeed, this needs engineering efforts as the reviewer recognized.

2. A well-trained neural solver leaves little completion loss. We deliberately trained strong neural solvers to test whether the framework still helps when the neural solver is hard to improve. Its best-of-20 result already exceeds the 600-second Gurobi reference in three of the four settings in Table 1. By Eq. (2), the gain of N-FPT over the neural solver equals the completion loss. The small gains of N-FPT alone on MIS and MVC therefore show that these strong solvers already complete their advice nearly optimally, and N-FPT certifies that each unchanged solution is the best achievable completion of its advice (lines 237–239). The remaining gap is advice regret, which NIC-FPT and NRD-FPT still reduce (Table 1). Where the completion loss is larger, N-FPT alone recovers it, including on MIS: the average independent set size rises from 122.45 to 123.86 on WS-SS and from 219.89 to 221.30 on HK-SD (Tables 4 and 6), and the average cut rises from 1944.50 to 1967.72 on Reg-SS MaxCut (Table 2).

3. The gains hold across neural solvers and distribution shifts. With the same settings, NIC-FPT and NRD-FPT improve two neural solvers trained with different objectives, GFlowNet and GNN+RL (Table 1). The framework also helps when the advice becomes unreliable on unseen distributions. We compare each transferred solver (trained on different distributions) with a GFlowNet trained on the target distribution itself. Across 24 within-family and 96 cross-family test settings, N-FPT improves the transferred solutions, NIC-FPT and NRD-FPT further narrow the gap to this target-trained GFlowNet, and in several settings they surpass it (Figs. 3 and 9–12; lines 247–254). This costs huge amount of computing hours and we have not frequently seen similar experiments in similar work.

[1] Li et al., IJCAI 2026.

AuthorsOpenReview ↗

[Authors Response (2/3) – part 1]

Second, Section 4: the RL baseline, graph size, and state cap.

The reviewer asks for a stronger RL baseline, experiments on larger graphs, and the rate at which the state cap is hit. These requests would suit a benchmark of RL algorithms, where the goal is the strongest algorithm on the largest graphs. Section 4 asks a different question: can N-FPT use graph structure to give the neural solver a better way of training than the classical RL with final reward?

Why the final reward is not enough. For neural combinatorial optimization tasks, RL trains on its sampled trajectories with final reward, which scores only the complete solution. The reward therefore cannot tell which decision ruled out every optimal completion, or which alternative decision would have kept one. Here, an optimal completion means a best achievable completion of the decisions made so far. Classical RL design cannot pinpoint this fine-grained credit assignment for combinatorial optimization tasks.

Why an exact solver alone does not help. A natural fix is to label each decision with an exact solver. However, this fix fails for two reasons. Calling the exact solver after every decision of every trajectory means solving an NP-hard problem, and proving optimality, each time (lines 290–292). Moreover, the one optimal completion that the exact solver returns cannot judge a decision that leads to a different optimal completion (lines 319–321). Listing all optimal completions does not scale either: in a graph made only of separate edges, the number of maximum independent sets doubles with each edge (lines 321–323).

How N-FPT overcomes both failures. N-FPT solves the remaining problem only once, as soon as the neural solver's decisions make it tractable, and stores the result in one shared dynamic-programming record. N-FPT then checks every later decision against this record with no further calls (lines 327–342). The record also holds every optimal completion onwards, so a decision that leads to any of them is judged correctly. As the reviewer notes, the record uses polynomial space even when the number of optimal completions is exponential. Early in training, nearly all sampled trajectories miss every optimal completion (lines 452–454). For each such trajectory, the final reward gives only a low score, whereas N-FPT identifies the first decision that ruled out every optimal completion and the alternative decisions that would have kept an optimal completion reachable. N-FPT can calibrate the bad trajectories to a better place as more accurate training signals for RL.

The RL baseline. The reviewer suggests PPO, a learned value baseline, and an entropy bonus. These changes improve how the policy learns from the final reward, but none of them tells the policy which decision ruled out every optimal completion. N-FPT feedback supplies this information in Eq. (4), which can be added to any of these methods. We therefore compare the same RL method with and without N-FPT feedback, with architectures, training graphs, starting assignments, optimizer updates, and seeds matched, as the reviewer also notes (lines 376–377, 1127–1138). Both methods also train from scratch, so the absence of a warm start affects them equally. The baseline itself is competitive. Like [2, 3, 4], it uses a graph neural network that selects vertices one at a time, and it scores each of its four sampled solutions against the average reward of the other three (lines 360–361), the baseline of Kool et al. [6]. The reviewer cites Wu et al. [5], who report that GFlowNet does not beat a degree-based greedy algorithm on standard MIS instances. Our RL baseline passes this test: it beats min-degree greedy in every setting (lines 428–429; Fig. 6). Therefore, our baselines are strong enough.

N-FPT feedback still improves on this baseline in all twelve settings, raising the rate of reaching the best achievable value by up to 33.5 percentage points (lines 416–417). On the 100 test graphs of each setting, the solver trained with N-FPT feedback also finds a better solution than the baseline on 49 to 78 graphs and a worse one on only 2 to 19, a difference that is statistically significant in all twelve settings (Fig. 6; Appendix A.4).

AuthorsOpenReview ↗

[Authors Response (2/3) – part 2]

Graph size. Section 4 measures how often the trained solver reaches an optimal completion, so the optimal value must be proven for every test graph (line 1144). At the sizes of Section 3, the Gurobi references are not certified optima (lines 1060–1061), so we cannot certify their true optimal solutions, and this is why NP-hard problem is challenging. At 270 to 330 vertices, Gurobi proves the optimal value for every test graph, yet the graphs remain hard for neural models: from an empty start, the RL baseline fails to reach an optimal completion on most test graphs (Fig. 5).

The state cap. The state cap applies only during training. When a training graph exceeds the cap, that graph stays in training with the RL term alone (lines 1141–1143), exactly as in the RL baseline. The cap therefore only reduces the amount of feedback and cannot favor our method. At test time, the trained solver uses no exact solver (lines 1145–1146), so the cap does not limit inference.

Of the 500 training graphs per family, feedback is available for 466 (93%) RGG and 474 (95%) King graphs with an empty start, 482 (96%) and 480 (96%) with two starting selections, and 500 (100%) and 496 (99%) with ten. The other graphs exceed the cap of 200,000 valid assignments per bag. The stored record needs at most 17,380 states per graph, far below its cap of 2,000,000.

That is, if we only allow normal RL training, it is highly likely that RL will sample some bad trajectories. And this is indeed beyond control. Therefore, our N-FPT can usually be used as a calibrator, it can help RL correct at some point, and unlock higher probability of hitting optimal solutions as our results showed in the paper.

[2] Khalil et al., NeurIPS 2017.

[3] Barrett et al., AAAI 2020.

[4] Ahn et al., ICML 2020.

[5] Wu et al., TMLR 2026.

[6] Kool et al., ICLR Workshop 2019.

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

The paper addresses graph combinatorial optimization (CO) problems by combining neural solvers with exact dynamic programming. The proposed method, Neural Fixed-Parameter Tractable (N-FPT), operates on a partial solution to a CO problem and finds the best possible completion using a dynamic program. The partial solution can be obtained by using an existing neural CO method and strategically discarding parts of the solution so the remainder has bounded treewidth. This effectively allows N-FPT to improve on the base neural CO method at inference time without retraining. The paper also proposes sampling variants (NIC-FPT and NRD-FPT) which improve the partial solution itself. Finally, the paper shows how N-FPT can be used to improve RL training for neural CO by providing additional feedback. The approach is validated on the commonly used CO problems maximum independent set, minimum vertex cover, and maximum cut, using synthetic graphs.

Critical strengths
  • S1: The presented method is both novel and interesting. N-FPT takes a predicted CO solution from an existing method, discards part of it, and optimally completes what remains. This effectively constitutes an inference-time trick for improving solution quality, expanding on an established research direction.
  • S2: The paper shows how N-FPT can be used to improve RL training for neural CO. While this method of RL training is no longer standard, I consider these insights an interesting addition to the field.
  • S3: The experimental results on N-FPT feedback in section 4 convincingly demonstrate the improvement it provides over RL training.
Critical weaknesses

Major weaknesses:

  • W1: No comparison based on diffusion baselines (e.g. SDDS [4]) which are much stronger than GFlowNets. I would like to see whether the proposed approach can still improve these stronger models. A comparison based on diffusion models should be possible; the approach is model agnostic as stated in the introduction, and appendix E states explicitly that diffusion models can be used. The question is not so much whether the proposed method and its variants achieve state of the art, but whether they can be fruitfully combined with state of the art methods.
  • W2: No controlled inference compute budget. N-FPT often only slightly improves over the baseline while usually using substantially more computation time according to appendix C. Since there is a tradeoff between compute budget and solution quality, an experiment that grants all methods the same or similar computation time on the same hardware would provide a fairer comparison. Table 1 already shows best-of-NN results; here NN can be adjusted to adjust the compute budget of each method. Also, no computation times are currently given for NIC-FPT and NRD-FPT.

Minor weaknesses:

  • W3: Nonstandard datasets/graph generation parameters. Using the established RB small/RB large/BA small/BA large datasets as used by e.g. [1, 2, 3, 4] would have made comparisons with other works much easier. There is benefit in evaluating on both sparse and dense graphs, but this could have still been done while using the aforementioned datasets: The established BA large setting (800 to 1200 nodes, m = 4) is already similar to this paper's BA LS dataset (1000 to 1200 nodes, m = 3), and a denser variant could still have been added. The authors should motivate why they chose to deviate from the established parameters or cite other works that use the same datasets.
  • W4: The paper does not discuss the limitations of the introduced method and its variations.
  • W5: While the experimental results in tables 1 and 2 are averaged over three training seeds, standard deviations are not reported. This information is particularly important as in some settings the differences between the results are very small.

These additional points are intended to improve the paper and don't play a large part in my decision assessment:

  • W6: The authors only experiment on node subset problems, which by itself is fine as restricting the setting to a particular subclass of graph CO problems is commonly done in the literature. However, the authors should somewhere mention more explicitly that they evaluate on node subset problems exclusively, and discuss what modifications would need to be made to apply their approach to other types of CO problems.
  • W7: The appendix describes parts of the method in more detail, which was useful to me in understanding the method and clearing up remaining questions. However, the information contained therein is somewhat difficult to find, as the main paper often doesn't reference the relevant appendix sections. For example, section 3 should reference algorithm 1 in appendix A, section 4 should reference appendix B.7 etc.
  • W8: It took me a while on my first read to understand what the purpose of section 4 is within the paper (I assume it is intended to show an alternative application for N-FPT, but this isn't stated explicitly). A small adjustment to the section's opening paragraph can rule out any confusion.
  • W9: The paragraph "Consolidated Prediction" describing NIC-FPT and NRD-FPT is quite dense, and in my opinion would benefit from more in-depth explanations.

[1] Sun et al., "Annealed Training for Combinatorial Optimization on Graphs", 2022

[2] Zhang et al., "Let the flows tell: Solving graph combinatorial problems with GFlowNet", 2023

[3] Sanokowski et al., "A diffusion model framework for unsupervised neural combinatorial optimization", 2024

[4] Sanokowski et al., "Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics", 2025

Questions for authors

Q1: For the settings in Table 1, how many of the nodes (or what fraction) are, on average, fixed by the neural advice, and how many are left to be completed with DP?

4 comments
AuthorsOpenReview ↗

[Authors Response (1/3)]

We thank the reviewer for the careful reading and the valuable comments, and for finding N-FPT novel and interesting and the results of Section 4 convincing. We first answer the two major weaknesses, W1 and W2, and then the remaining points.

W1. Combining N-FPT with stronger neural solvers. The reviewer requests experiments to see whether N-FPT can still improve stronger models, such as diffusion models. However, Proposition 3.1 already answers this question for every model, so no further model is needed. For any valid advice from any model, N-FPT returns the best achievable completion of its advice. N-FPT therefore never does worse than the model, improves the solution whenever the model leaves completion loss, and returns a global optimum when the advice is perfect. The guarantee does not depend on how the model was trained, so it covers diffusion models such as DIFUSCO [1] and SDDS [2] in the same way as GFlowNet and GNN+RL.

A stronger model changes only where the remaining gap lies. By Eq. (2), a stronger model leaves less completion loss, so the gain of N-FPT alone shrinks, and the remaining gap is advice regret, which NIC-FPT and NRD-FPT reduce. Our experiments already test this regime. We deliberately trained a strong GFlowNet, with 50 epochs instead of 20 (Appendix B.5), and its best-of-20 result exceeds the 600-second Gurobi reference in three of the four settings of Table 1; NRD-FPT still improves it in every setting.

We chose GFlowNet and GNN+RL because they use different training objectives and output solutions directly, so every gain can be attributed to N-FPT. Stronger pipelines often add decoding or search steps after the neural model, which would mix their gains with ours. Diffusion models such as DIFUSCO [1] belong to this group, since their output becomes a valid solution only after a separate decoding step.

Nevertheless, following the reviewer's request, we applied N-FPT to the solutions of SDDS [2] and DiffUCO [3] on the 800 graphs of their standard RB-small benchmark for MIS, with the settings of the SDDS work, and we will add these results to the appendix:

Modelη\etaAverage: alone →\to N-FPTImproved / worsenedBest of 30: alone →\to N-FPTImproved / worsened
SDDS1019.605→19.60619.605 \to 19.60613 / 019.915→19.91519.915 \to 19.9150 / 0
SDDS6519.605→19.79219.605 \to 19.792364 / 019.915→19.97819.915 \to 19.97850 / 0
DiffUCO1019.377→19.38419.377 \to 19.38434 / 019.668→19.67519.668 \to 19.6756 / 0
DiffUCO6519.377→19.70719.377 \to 19.707414 / 019.668→19.84819.668 \to 19.848139 / 0

With η=10\eta = 10, the target width of our main experiments, both models gain little, and SDDS, the stronger model, gains less than DiffUCO in every comparison, as Eq. (2) predicts. Raising the target width to η=65\eta = 65 shrinks the modulator, so exact completion optimizes more of the decisions, and the gain rises for both SDDS and DiffUCO. In every row, N-FPT makes no graph worse, as Proposition 3.1 guarantees. N-FPT therefore strengthens both models, and the width trades more exact computation for better solutions (lines 156–161).

W2. Computation budget. We believe there is a misunderstanding to the table. The extra time buys what the standalone solver cannot provide at any time budget: a certified solution. We do not claim that N-FPT is faster than the neural solver. And it never was our focus. A trained neural solver is fast, since it runs on a GPU with highly optimized libraries, but it offers no guarantee on solution quality. An exact dynamic program offers this guarantee, but its cost grows exponentially with the width of the graph, so it cannot scale alone. N-FPT combines the two: the neural solver fixes the decisions on the modulator, and the dynamic program completes the rest exactly at a width that we choose, so its cost grows only linearly with the size of the decomposition (lines 156–161).

Granting the standalone solver the same time on the same hardware would therefore compare a method with a guarantee against one without it, on solution value alone. Extra time lets the standalone solver draw more samples, but no number of samples certifies that a solution is the best achievable for its advice, while N-FPT certifies every solution it returns (Proposition 3.1). The sampling budget of NIC-FPT and NRD-FPT is also already matched: for both GFlowNet and GNN+RL, every method in Tables 1 and 2 selects from the same 20 candidate solutions per graph, and the two methods change only how these candidates are drawn (Appendices B.3, B.10). Finally, the small gains of N-FPT alone reflect deliberately strong solvers. By Eq. (2), the gain equals the completion loss, which a strong solver keeps small; where this loss is larger, the gain is larger, as on MaxCut (Table 2) and on WS and HK graphs (Tables 4 and 6).

[1] Sun and Yang, DIFUSCO, NeurIPS 2023.

[2] Sanokowski et al., Scalable Discrete Diffusion Samplers, 2025.

[3] Sanokowski et al., DiffUCO, ICML 2024.

AuthorsOpenReview ↗

[Authors Response (2/3)]

W3. Datasets. We never chose our datasets to avoid comparison with prior work, and our datasets are sufficient for the claims we make. Our goal is to show in practice what Proposition 3.1 guarantees: N-FPT strengthens the neural advice it receives, never does worse, and improves the solution whenever the solver leaves completion loss. Every comparison is therefore paired within one neural model, on the same checkpoints and test graphs (Appendix B.3), so our claims do not only depend on numbers reported in other papers. The cited works themselves also vary their datasets with their goals: Sun et al. add real-world graphs, Zhang et al. add SATLIB and ER graphs, and Sanokowski et al. (DiffUCO) add ER graphs and Gset. For some, we cannot confirm they are using the exact same instances. Our datasets likewise follow our goal: each family comes in four configurations that change size and density separately, small or large and sparse or dense (Table 10), whereas the standard RB and BA sets fix one density setting for each size. This grid tests whether the improvement stays stable as size, density, and family change across five families, and lets the shift experiments separate the effect of size from that of density (Figs. 3, 9–12). We did so to focus on our research focus. The improvement is stable: in every setting, N-FPT either improves the neural solver or certifies that its solutions are already the best achievable completions of their advice, and never does worse. As the reviewer notes, our BA-LS setting is already close to the standard BA-large setting. We will state this motivation in Appendix B.2.

To meet the reviewer's expectation, we add results on the standard RB-small benchmark with SOTA models in this direction. Please refer to our W1 response.

W4. Limitations. We agree and will add an explicit limitations paragraph. The main limitation is the lack of smart ways to build better tree decompositions. For now, we are using the minimum-degree heuristic to build the tree decomposition. Because finding the thinnest tree decomposition itself is NP-hard. Heuristics are our only practical hope. There are prior work has proven this heuristic can balance the quality and the efficiency [5], but it will always be a benefit if we can acquire "thinner" tree decomposition when possible. Yet, this stays outside of the paper's scope, however, we indeed see a very strong potential to look for better decomposition. We want to emphasize, our method never relies on a particular decomposition. It will generally work on many types of graph decompositions.

W5. Standard deviations. Every comparison in Tables 1 and 2 is from the same checkpoints and test graphs, and each average is taken over 6,000 solutions (Appendix B.3), so the spread that matters is that of each method's gain over the standalone solver. For GNN+RL, the table reports each gain with a 95% confidence interval over the 300 pairs of test graph and seed in each setting:

SettingN-FPT, average gainNIC-FPT, average gainNRD-FPT, best-of-20 gain
SS+0.027 [+0.023,+0.031]+0.027\ [+0.023, +0.031]+0.21 [+0.09,+0.32]+0.21\ [+0.09, +0.32]+2.22 [+2.04,+2.40]+2.22\ [+2.04, +2.40]
SD+0.004 [+0.003,+0.006]+0.004\ [+0.003, +0.006]+0.01 [−0.06,+0.09]+0.01\ [-0.06, +0.09]+2.33 [+2.16,+2.50]+2.33\ [+2.16, +2.50]
LS+0.036 [+0.032,+0.041]+0.036\ [+0.032, +0.041]+0.15 [+0.03,+0.27]+0.15\ [+0.03, +0.27]+3.37 [+3.17,+3.58]+3.37\ [+3.17, +3.58]
LD+0.005 [+0.003,+0.008]+0.005\ [+0.003, +0.008]+0.01 [−0.08,+0.10]+0.01\ [-0.08, +0.10]+3.05 [+2.83,+3.27]+3.05\ [+2.83, +3.27]

The intervals of N-FPT and NRD-FPT stay above zero in every setting, even for the N-FPT gain of 0.004 on SD, and neither method does worse than the standalone solver on any of the 300 pairs. For N-FPT, this is the guarantee of Proposition 3.1, which holds for every sample, graph, and seed. NIC-FPT changes the advice by design: it fixes the vertices that most samples select and redraws only the open decisions. Its advice therefore differs from the standalone advice, which is not Proposition 3.1's focus; even so, its average gain is positive in every setting. For GFlowNet, across the three training seeds, the gain of N-FPT is never negative and the gain of NRD-FPT is positive in every setting. Section 4 already reports the full seed ranges and paired sign tests (Figs. 5 and 6; Appendix A.4). We will add these intervals later.

AuthorsOpenReview ↗

[Authors Response (3/3)]

W6. Problem class. Node-subset problems already include many classical NP-hard problems, such as the three we study and minimum dominating set, and many more. The framework also extends beyond this class. N-FPT applies whenever the problem has an exact dynamic program over a tree decomposition, and by Courcelle's theorem and its extension to optimization [3, 4], every problem expressible in monadic second-order logic has one, including edge-based problems such as Hamiltonian cycle. Among our three problems, MaxCut already has an edge-based objective. We want to highlight that it is nontrivial to build framework which can generalize to a wide range of NP-hard tasks, but our framework is able to do this.

W7–W9. Presentation. We truly thank the reviewer for these concrete suggestions on presentation and will revise accordingly. Section 3 will point to Algorithm 1 in Appendix A, and Section 4 to Appendix B.7. Section 4 will open by stating its purpose: N-FPT feedback improves the advice through training, complementing the inference-time methods of Section 3. The paragraph on NIC-FPT and NRD-FPT will describe both methods step by step, following Appendix B.10. We will apply these changes after the busy rebuttal.

Q1. Share of vertices fixed by the advice. The table reports the modulator, whose decisions the advice fixes, for the Table 1 settings and the SDDS runs under W1. On Reg graphs, the advice fixes about 44% of the vertices on sparse graphs and 67% on dense graphs; the dynamic program decides the rest. Denser graphs have larger width, so the advice covers more vertices, as discussed under W4.

Datasetη\etaTest graphsAverage verticesModulator sizeShare fixed by the advice
Reg SS10100855.7370.043.2%
Reg SD10100848.0567.066.9%
Reg LS101001103.0482.843.8%
Reg LD101001097.8737.967.2%
RB-small (SDDS)10800226.6109.148.0%
RB-small (SDDS)65800226.628.512.5%

[3] Courcelle, Information and Computation, 1990.

[4] Arnborg, Lagergren, and Seese, Journal of Algorithms, 1991.

[5] Maniu, Senellart, and Jog, ICDT, 2019.

Thank you for the thorough reply.

Regarding W1: I would like to clarify that I asked for this comparison not because a different training regime has a direct impact on N-FPT, but because the suggested diffusion models are substantially stronger than GFlowNets. It is not clear that increasing GFlowNet's training time can close this gap, therefore testing the same setting. I respectfully disagree with the claim that proposition 3.1 already answers the question for every model. It only guarantees that N-FPT doesn't worsen the solution, not that using N-FPT is worth the additional computation time with every model in practice. Regarding decoding, the gains from decoding or post-hoc search are not mixed with the gains from N-FPT if the decoder or search is applied to the model's output in both cases (with and without N-FPT).

The results you provide show that N-FPT improve over base DiffUCO/SDDS when using η=65\eta = 65, thus partially addressing my concern. However, reiterating a point I made in my initial review, it is unclear whether these improvements still hold under a matched compute budget. In particular, increasing η\eta from 10 to 65 likely increases the computation time needed for exact completion. This makes a fair comparison (e.g. using best of NN-sampling to adjust the base method's computation time) even more important.

Regarding W2: Since the guarantees provided by proposition 3.1 are very weak, they seem to be a small side benefit, rather than a big upside worth buying at substantial additional computation time. I treated them as such in my review. It is unclear how these guarantees could be useful in practice, as the methods of obtaining the neural advice used in the paper provide no guarantee on this advice. In particular, there is no guarantee that the advice is consistent with some globally optimal solution, and we know very little about the best achievable value VG(a)V_G(a).

Yes, proposition 3.1 does guarantee that N-FPT does not worsen the solution, but there is no guarantee that it improves the solution. Notably, drawing additional samples from the base model and choosing the best result also comes with the same guarantee of not worsening the initial solution.

As the authors only partially address one of my main concerns, and do not adequately address the other, I maintain my score.

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

This paper proposes N-FPT, which combines neural solvers with treewidth-based exact optimization. It fixes the modulator decisions of a neural solution and optimizes the remaining decisions through dynamic programming, guaranteeing an optimal completion under the fixed advice. It further improves advice through sample agreement and randomized deferral, and uses the first decision that eliminates all optimal completions and alternatives that preserve one as training feedback. Experiments evaluate inference performance on MIS, MVC, and MaxCut, and show that exact feedback improves an RL baseline on MIS.

Critical strengths

The paper separates solution error into the loss induced by fixed advice and the loss incurred in completing the remaining decisions, clarifying both the opportunities and limits of improvement. This distinction identifies which errors exact completion can eliminate and which require better neural decisions, providing a useful perspective for connecting solution improvement with learning. (§3, Eq. 2; §4)

Critical weaknesses
  • The independent contribution of the key learning signal is not isolated. Exact-completion supervision and first-harmful-selection correction are used together, but there is no RL baseline augmented only with the former. It is therefore unclear whether the reported gains arise from the proposed correction beyond conventional exact-solution supervision. This leaves insufficient experimental support for the main learning contribution. (§4, Eq. 4)
  • Controlled experiments are insufficient to assess inference improvements relative to their computational cost. Consolidation uses additional sampling without comparison against resampling or other improvement methods under matched budgets. The additional benefit of exact DP after consolidation is also not isolated, while the cost and availability of training feedback are insufficiently reported. Consequently, the practical benefits after accounting for additional computation remain unclear. (Tables 1–2, Appendices B.7, B.10, C)
Questions for authors
  1. How much additional improvement does first-harmful-selection correction provide over RL augmented only with exact-completion supervision?
  2. Under matched sampling or runtime budgets, does consolidation outperform independent resampling? What additional benefit does exact DP provide after consolidation?
  3. What are the time and memory costs of preparing exact feedback, and for what proportion of training instances is feedback available?
  4. With identical neural advice and tree decompositions, how does basic N-FPT differ algorithmically from the framework of Li et al. (2026)?
  5. Please explicitly identify the s=0s=0 setting used in the learning experiments and revise the text to distinguish the general formulation of feedback becoming available during a trajectory from the experimentally validated results.
5 comments
AuthorsOpenReview ↗

[Authors Response (1/2)]

We thank the reviewer for the time spent on our paper. Several of the reviewer's concerns come from one misunderstanding of Section 4, which we clarify first.

Why N-FPT feedback cannot be decomposed. Weakness 1 asks for an RL baseline with only the exact-completion part of N-FPT feedback, in order to isolate the first-harmful-selection correction. This request assumes that our method in Section 4 has separate signals. However, our RL feedback design comes from one N-FPT computation. N-FPT computes every optimal completion from a given state; the first harmful selection is the decision with which the solver's own trajectory loses the last of these optimal completions; and the correction consists of the next selections, at the state before that decision, that keep at least one optimal completion (lines 313–318, 327–342). The correction is therefore the exact completion applied at the state that the solver actually reached, and no correction exists without the exact completion. Removing the correction does not isolate a component. It cuts the link between the exact completion and the solver's own trajectory, and what remains is supervision on one stored solution, this decomposition request changes our design, and becomes a complete different method. The exact completion is also not a conventional signal: computing this completion is NP-hard in general, since from an empty starting assignment it is the original optimization problem (lines 290–292). The claim of Section 4 is that N-FPT feedback improves what a plain RL solver learns, and our experiments test exactly this claim: the same RL method with and without N-FPT feedback, with the training signal as the only difference (lines 376–377).

W1&Q1. Plain RL, widely used in this field [1, 2, 3], builds a solution one vertex at a time and learns from the final reward, which for MIS is the size of the independent set. However, the final reward tells the solver neither how far its solution is from the best achievable value nor which decision caused the loss. N-FPT feedback supplies both. Suppose plain RL samples the trajectory A,B,C,DA, B, C, D, and CC is the first harmful selection. N-FPT keeps AA and BB, identifies CC, and teaches the solver to choose a next selection that keeps an optimal completion reachable, such as EE in the optimal completion A,B,E,FA, B, E, F. Supervision on one stored solution cannot give this lesson, since the solver reached the state after AA and BB through its own decisions, and one stored solution need not pass through that state (lines 319–321). The improvement that the reviewer asks about is therefore the improvement of N-FPT feedback over plain RL, which is positive in all twelve settings and reaches 33.5 percentage points in the rate of reaching the best achievable value (lines 416–417). We will explain in Section 4 why the two parts of N-FPT feedback form one signal.

W2&Q2. The question treats consolidation, that is, NIC-FPT and NRD-FPT, as spending a larger sampling budget. However, NIC-FPT and NRD-FPT select from exactly as many candidates as the standalone solver: for both GFlowNet and GNN+RL, every method in Tables 1 and 2 selects from the same 20 candidate solutions per graph (Appendix B.3). The "additional sampling" that the reviewer notes goes into how these 20 candidates are drawn. NIC-FPT fixes the vertices that most samples select, and NRD-FPT keeps some decisions of each candidate and defers the rest; each later round then redraws only the decisions that remain open. Only the 20 candidates of the final round are kept, so "best of 20" means the same in every row (Appendix B.10). The two methods therefore answer an empirical question that more candidates cannot answer: with the same number of candidates, does a better sampling strategy improve the advice? In Table 1, NRD-FPT improves the standalone best of 20 in every setting, for both models.

A standalone solver with more independent samples, such as 100, would change a different quantity, the number of candidates itself. And this change does not contribute to our goal here. Such a comparison would give the standalone solver five times as many candidates as our methods select from, so its outcome would measure the larger number of candidates and say nothing about the sampling strategy. A fair comparison at 100 candidates would also give NIC-FPT and NRD-FPT 100 candidates, which is the comparison of Table 1 at a larger scale. Independent resampling is also compatible with our method: by Proposition 3.1, N-FPT can complete each resampled solution and never returns a worse one. Finally, exact completion is part of NIC-FPT and NRD-FPT by design. By Eq. (2), its benefit after consolidation equals the remaining completion loss, which is never negative, and N-FPT certifies the result as the best achievable completion of the improved advice.

[1] Khalil et al., NeurIPS 2017.

[2] Barrett et al., AAAI 2020.

[3] Ahn et al., ICML 2020.

AuthorsOpenReview ↗

[Authors Response (2/2)]

Q3. The measured time and memory of preparing feedback are not part of any contribution that we claim on this training insight. Weakness 2 counts the cost of training feedback toward the computational cost of the inference improvements in Tables 1 and 2. However, N-FPT feedback is used only during training: at test time, the trained solver constructs its solutions without any exact solver (lines 1145–1146), so the feedback cost adds nothing to inference. Although this cost is unrelated to our claims and does not affect inference, we report it in full. In our experiments, feedback is prepared once for each training graph and starting assignment, before training, and is reused across all epochs (lines 1139–1143). Over the 500 training graphs of each family (each cell lists RGG / King):

Starting selectionsGraphs with feedbackExact completion, seconds, mean (max)Building the shared record, seconds, mean (max)Peak memory
0466 (93%) / 474 (95%)1.38 (11.4) / 1.50 (14.6)0.47 (3.4) / 0.63 (4.7)up to 2.0 GB
2482 (96%) / 480 (96%)1.05 (11.4) / 1.13 (9.1)0.36 (3.2) / 0.49 (3.9)up to 1.9 GB
10500 (100%) / 496 (99%)0.21 (5.0) / 0.49 (7.1)0.10 (1.4) / 0.17 (3.2)up to 1.6 GB

Feedback is therefore available for 93% to 100% of training graphs, and preparing it takes about two seconds or less per graph on average. The shared record needs at most 17,380 states and 1.7 MB per graph, far below its cap of 2,000,000 states. Graphs that exceed the cap of 200,000 valid assignments per bag train with the RL term alone, exactly as in the baseline. Figure 8 (bottom) also reports, for each epoch, the share of sampled trajectories that end below the best achievable value and therefore receive the correction.

Q4. The question fixes the neural advice, which is exactly the quantity our paper improves. We build on the dynamic program of Li et al. [4], as credited in lines 55–58. However, Li et al. use this dynamic program to improve existing heuristics and treat the heuristic's advice as fixed, so their result depends on the quality of the advice. Li et al. do not study how to improve this quality and how the algorithm can improve training. Under N-FPT, the dynamic program optimizes every decision outside the modulator, so the advice is the neural solver's only influence on the final solution, and the dynamic program cannot improve its own input. Our paper therefore asks how the quality of the advice determines the final solution (Eq. (2)) and how to improve the advice: Section 3 improves the advice at inference time with NIC-FPT and NRD-FPT, and Section 4 improves the advice through training. Section 4 also adds a new algorithm: it extends the dynamic program to keep every optimal completion in one shared record and to find the first harmful selection of a trajectory without further exact solves (lines 327–342).

Q5. We are not entirely sure we understand the reviewer's concern, so we first clarify what s=0s = 0 means in our method. In Section 4, ss denotes the step at which a trajectory reaches a state that the exact dynamic program can solve, so that the record of optimal completions becomes available (line 347). The setting s=0s = 0 means that this record is built at the starting assignment a0a_0 itself, before the policy makes any selection. We use s=0s = 0 because our experiments fix starting assignments of zero, two, or ten selections, and a starting assignment may already contain poor choices. Building the record at a0a_0 therefore labels the optimal completions that remain reachable from each given start, whatever its earlier choices, and every trajectory from a0a_0 is supervised toward those optimal completions. All learning experiments use this setting (line 414 and lines 1139–1140). In the revision, we will state the setting directly at the start of the Section 4 experiments: the record of optimal completions is built at the starting assignment a0a_0.

We hope our response helps the reviewer reconsider the evaluation, and we look forward to further discussion.

[4] Li et al., IJCAI 2026.

Thank you for the detailed response. The additional results on feedback preparation costs and availability address my concern on these points, and the explanations clarify the relationship to Li et al. and the s=0s=0 setting used in the learning experiments. I also acknowledge the additional beam search comparison provided in response to Reviewer sp4Q and the clarification that it uses the same trained model and number of final candidates. However, two central concerns remain regarding whether controlled experiments establish the added value of the proposed method.

First, my ablation request is to retain exact computation and compare exact-completion supervision alone against its combination with first-harmful-selection correction. I understand that both signals derive from the same exact computation, but this dependency does not resolve the empirical question about the correction’s incremental contribution. Comparing basic RL with the full N-FPT feedback demonstrates the benefit of the combined feedback, but does not isolate the added value of the correction.

Second, my central concern is to isolate the contribution of the proposed strategy under controlled conditions, rather than to assess time efficiency itself. This was the motivation for my request for comparisons under matched sampling or runtime budgets. Matching the number of final candidates at 20 provides a meaningful control, but does not match the total sampling budget, including solutions generated during intermediate refinement rounds. In SGBS, which the authors cite, intermediate simulation rollouts count toward the total candidate budget (Choo et al., Appendices B–C). The additional beam search comparison is useful, but it does not establish that the total sampling budget is matched on this basis. Consequently, the benefits of consolidation remain insufficiently distinguished from those of additional solution-generation opportunities. Proposition 3.1 guarantees optimal completion under fixed advice, which addresses a different question.

These are my main concerns because they directly affect the assessment of the added value of the proposed learning signal and inference strategy. I therefore maintain my current rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.