- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes NeuroMT, a framework that speeds up Optimization Modulo Theories (OMT) over quantifier-free linear integer arithmetic by temporarily restricting the formula with a partial truth assignment (a cube) over its arithmetic atoms. Candidate cubes come from 73 hand-designed construction templates. These vary the seed (objective-, variable-, clause-, capacity- or conflict-centered), the coverage ratio, and whether phases come from a greedy score or an LP relaxation. Cheap Boolean and integer-bound propagation filters the candidates, which are then deduplicated. A heterogeneous GNN encodes the formula once, using objective, variable, atom and clause nodes. It scores each candidate from pooled embeddings of its true and false atoms plus scalar features. The scorer is trained with soft targets derived from Z3 resource counts of the full pipeline (restricted solve plus continuation), normalized by direct solving. At inference, the top candidate is used only if its score exceeds that of the empty assignment by a calibrated margin. The restricted optimum v then serves as a bound, and Z3 continues on F ∧ (obj > v) after popping the cube, which preserves exactness (Prop. 1). On 1,000 test formulas each for knapsack and three RCSP-derived classes, the solver-stage PAR-2 ratios against direct Z3 are 0.886, 0.056, 0.298 and 0.348. Ablations compare against a fixed best template, random selection and alternative encoders, and an OptiMathSAT comparison is run on 100 sampled instances per class. End-to-end gains are much smaller once frontend time is included: 1.019 on knapsack and 0.445 on completion time.
Critical strengths
- The cube is used only to obtain a bound and is removed via push/pop before continuation. A selection can therefore help even when it excludes every global optimum, and the result stays exact.
- Training uses the cost of the whole pipeline rather than imitation of optimal solutions. This captures the trade-off between a cheap but weak bound and an expensive but strong one.
- The loss is a per-instance soft-target cross-entropy that does not overweight instances with many candidates. A calibrated margin provides a conservative fallback to direct solving.
- It is order-invariant and phase-aware, and the formula is encoded once, so scoring many candidates is cheap.
- Aggregate speedups reach about 18× on completion time, with wins on more than 90% of instances in all three RCSP classes.
- The paper uses three repetitions in randomized order and paired group-bootstrap intervals.
- The results include the knapsack E2E ratio above 1 and OptiMathSAT being stronger on two classes.
Critical weaknesses
- There might be a possible selection bias in the test set. Z3 solves only 920/579/564/670 instances, yet the guided solver is reported to certify all 1,000 in every class. Table captions mention “replacement instances” with one run and a “repaired cohort conditioned on successful guided solves”, and the bootstrap intervals condition on this cohort. If test instances on which NeuroMT failed were replaced, the headline ratios and the “certifies optima on every instance” claim are biased. This must be resolved, as it could invalidate the main results.
- Weak evidence that the learned selector matters. Indeed, a) The fixed best template beats the GNN on completion time (0.048 vs 0.056) and buffer storage (0.290 vs 0.298). b) A no-message-passing encoder gets within a few points on buffer storage. c) No per-instance oracle is reported, and it is unclear whether the “best template” was chosen on validation or test data. d) Much of the scheduling gain may therefore come from the restrict-then-continue scheme rather than from the learned selection.
- The headline metric hides frontend cost. On completion time, the frontend takes about 12.2s against 1.7s of solver time. On knapsack, the E2E ratio is 1.019 with interval [0.984, 1.057], i.e. no end-to-end gain. The abstract and contributions should foreground E2E numbers.
- Some of the results for the knapsack seems weak and puzzling. Indeed, the median ratio is 1.000, NeuroMT wins on only 32.5% of instances, and the resource ratio is 1.002. The model is trained on resource counts, yet wall time drops while resource counts do not. This suggests a measurement artifact or that the selector rarely switches away from direct solving. The sentence claiming NeuroMT “favors harder instances” does not follow from the resource statistic.
- The baseline appears to be insufficient for the following reasons: a) OptiMathSAT is evaluated only on 100 instances sampled from those Z3 solved, which biases the sample toward Z3. Even so, it clearly wins on buffer storage (1.28 vs 9.02 s) and knapsack. b) There seem to be no comparison with Ashera or with Masina & Sebastiani. c) There is no comparison with MIP/CP solvers (e.g. Gurobi, CP-SAT, HiGHS), which are natural for knapsack and scheduling. d) There is no comparison with tuned Z3 configurations or with an LP-rounding-only heuristic.
- The scope seems a bit too narrow. Indeed, only two benchmark families are used, with 40 training formulas per scheduling class drawn from the same templates as the test set. There are no standard OMT benchmarks and no out-of-distribution evaluation; the size split coincides with templates seen during training. The 30 s budget makes PAR-2 dominated by Z3 timeouts.
- The novelty appears rather modest. Indeed, bounding via a restricted subproblem and then continuing exactly is a standard incumbent/warm-start strategy, as in neural diving, predict-and-search (Han et al., ICLR 2023) and cube-and-conquer (Heule et al., 2011). The contribution is mainly cost-based selection over a hand-crafted template portfolio. Related learning-for-SMT work such as FastSMT (Balunović et al., NeurIPS 2018) and MachSMT (Scott et al., TACAS 2021) is not discussed.
- The training cost has not been reported, indeed, the labeling requires executing every unique candidate (up to 73) per training formula through Z3. The total compute and its scalability are not reported.
- The exactness argument is correct but straightforward. The empirical claims are the concern. The test cohort seems conditioned on NeuroMT success, the headline metric excludes frontend time, the learned selector does not consistently beat a fixed template, and baselines are limited.
Questions for authors
Q0) Answer to the weaknesses discussed above if not supported by the following questions.
Q1) Please define “replacement instances” and “repaired cohort” precisely. How many test instances were replaced per class, by what criterion, and what are the Table 1 and Table 3 numbers on the original, unfiltered test sets?
Q2) Was the “best template” in Table 5 selected on validation or test data? Please report the per-instance oracle cost (best candidate in S(I)) and the fraction of instances where the margin rule falls back to direct solving.
Q3) What is the average number of unique candidates per instance after deduplication? Please break down frontend time into parsing, LP, propagation, graph construction and inference, and explain why it reaches about 12 s on completion time.
Q4) What was the total offline compute for labeling? Are labels from a single run or averaged, and how were timeouts handled during labeling?
Q5) On knapsack, why does wall time drop by about 11% while Z3’s resource count is unchanged? Could the push/pop scope or the extra assertions change Z3’s preprocessing or tactic selection?
Q6) How is time split between the restricted solve and the continuation? How often is the restricted optimum already globally optimal, i.e. the continuation is immediately UNSAT?
Q7) Algorithm 1 returns “unresolved” if the restricted solve times out, instead of falling back to direct solving with the remaining budget. How often does this happen, and why was this design chosen?
Q8) How sensitive are the results to τ, ϵ, the 0.75 quantile in q_i, and knapsack pretraining? What happens if scheduling models are trained from scratch?
Q9) The cost labels are Z3-specific. Do selections transfer to OptiMathSAT or another backend, or would relabeling be required?
Q10) Why was the OptiMathSAT comparison restricted to 100 Z3-solved instances, and with what settings was OptiMathSAT run? Can it be run on the full test sets?
Q11) Do the gains persist with larger budgets (e.g. 300 s), where Z3 times out less often and PAR-2 is less dominated by penalties?
Q12) Can you show cross-template or cross-size generalization (train on one template, test on another), or results on standard OMT-LIA benchmarks?
3 comments
Labelling And Training Costs (Q4, W8). Table 4 reports the costs on labelling, training and fine-tuning. Labelling is the main offline cost, with a range from 82.75h on buffer storage to 600.34h on knapsack, and it builds a reusable training corpus. Training and fine-tuning share reasonable costs.
Frontend Statistics (Q3). The frontend consists of five parts: parsing, candidate generation (with or without LP), graph construction, GNN encoding and inference. On average, there are 62.56 unique candidates per instance for knapsack, 22.99 for completion time, 10.84 for buffer storage and 13.37 for flow balancing. The main bottleneck on frontend runtime is parsing time and we make an improvement by switching to a more lightweight parser. On knapsack, the end-to-end PAR-2 ratio is now reduced to 0.936, better than the baseline, and detailed revised frontend-backend cost is shown in Table 6.
Restricted Solve And Continuation (Q6, Q7). The time proportion of the restricted solve is 11.4% on knapsack, 27.7% on completion time, 98.5% on buffer storage and 81.8% on flow balancing. Among these instances, 3.2% of optima obtained by the restricted solving equals global optima on knapsack problems; the corresponding percentage is 99.1% for completion time, 100% for buffer storage and 98.6% for flow balancing. In our approach, the two stages share a global time budget, thus there is no remaining budget left if the restricted solve times out.
Hyperparameter Sensitivity And Scheduling Models Trained From Scratch (Q8). We perform a series of experiments where τ, ϵ, the quantile q each varies, as shown in Table 8. Scheduling models trained from scratch are shown as the diagonal baseline of cross-task generalization experiments in Figure 4. Results suggest that our current knapsack-pretraining approach substantially reduces the cost of training from scratch with only a modest loss in performance.
We thank the authors for the clarifications and answers. My evaluation remains the same.
Thank you for your constructive feedback, and we will revise our paper accordingly. Our response is to address the highlighted issues and clarify some facts concisely.
Replacements In The Dataset (Q1, W1). The replacements are made only on instances which both NeurOMT and Direct Z3 failed to solve in 60 seconds. Therefore, the replaced instances do not help distinguish the performance among two approaches, and we consider the replacement as a repaired cohort on the dataset. We report results separately for the unchanged and replacement portions of the dataset in Table 3. Statistics show that NeurOMT has a better relative performance on the unchanged subset, suggesting that the replacements did not unfairly favor NeurOMT.
Ablations on learned selector (Q2, W2). a) The best fixed template may vary among datasets; our learned selector shows a kind of generalization on different datasets. Even in a single dataset, the best fixed template can only guarantee an average performance instead of instance-wise, sTable performance. Our learned selector therefore outperforms it on knapsack and flow balancing. b) Table 7 compares different encoders. We agree that message passing has a modest incremental effect on buffer storage. The no-message control still uses the same candidate set, node features, pooling, and learned scoring head; thus this ablation isolates graph propagation rather than the entire selection method. c) The best fixed template is chosen on the validation set in each dataset, and we complement per-instance oracle solver times in Table 2. d) The random template results exactly shows the improvements with only the designed templates and restrict-then-continue scheme. The learned selector remarkably outperforms it on all four datasets, demonstrating the fact that the learned selector does matter.
Headline Metric For Frontend Cost (W3). We agree and now Table 1 reports E2E results as well as the separation is shown in Table 5.
Questions On Knapsack Results (Q5, W4). We analyze the instance-wise results, finding out NeurOMT wins on 32.5% knapsack instances with 47.4% ties and only 20.1% losses, and direct solving is not chosen on 59.6% knapsack instances and 100% for other datasets. We also notice that the instance-wise PAR-2 ratio is 0.982 which is higher than the summed PAR-2 ratio 0.886, proving that the improvements made by NeurOMT are mainly from the instances more costly as directly shown in newly added Figure 5. We prove it in Appendix G.2 and copy the formula as below. Writing ri=ti/bi and bˉ=N1∑ibi, we have $ \operatorname{Cov}(b_i,r_i) = \frac{1}{N}\sum_{i}{b_i r_i - \bar{b}\bar{r}} $ and therefore $ R_{\mathrm{mean}}-R_{\mathrm{total}} = \bar{r} - \frac{\sum_{i}{b_i r_i}}{\sum_{i}{b_i}} = -\frac{\operatorname{Cov}(b_i,r_i)}{\bar b}, $ where covariance uses the 1/N convention. A therefore negative covariance Cov(bi,ri) indicates that instances more costly for direct Z3 tend to contribute stronger relative gains.
Because we collect resource limit only on non-timeout instances, the resource ratio is 1.002. We also run all instances until solved, on which the ratio will become 0.993. We agree that push/pop scope may also cause ineviTable extra resource costs but it is only used in the restricted solving.
SOTA Solver Baseline (Q10, W5). We complement full-set OptiMathSAT results and add Ashera, partial-assignment enumeration OptiMathSAT (Masina & Sebastiani, 2025) as additional OMT solver baselines. MIP/CP Solvers including CP-SAT and HiGHS/CBC/SCIP are also considered into comparison. Detailed results are shown in Table 1.
Generalization (Q12, W6). Cross-size generalization performance is already shown in Figure 5; we complement cross-template generalization experiments and results are displayed in Figure 4. Actually, the knapsack problems come from our handcrafted generator, while the other benchmark comes from the public dataset (Kasslin & Berg, 2025). Note that the model is trained on the knapsack problems and fine-tuned on the others. The performance also shows a kind of generalization.
Novelty And Related Learning-For-SMT Work (W7). We agree that the partial assignment framework itself is a common methodology as in neural diving, predict-and-search (Han et al., ICLR 2023) and cube-and-conquer (Heule et al., 2011). However, our template design and GNN scoring are motivated by recommender systems: heuristic templates quickly select promising assignments from the exponentially large state space, serving as a pre-ranking stage, while the GNN provides fine-ranking. We also add citations on related Learning-For-SMT work such as FastSMT (tailored to tactic generation) and MachSMT (tailored to algorithm selection).