acceptodds
Under review as a conference paper at ICLR 2027

Learning to Select Partial Assignments for Optimization Modulo Theories

Abstract

Many applications built on satisfiability modulo theories (SMT) need optimal solutions under their existing logical constraints. Optimization Modulo Theories (OMT) provides this capability by optimizing numerical objectives over the formula's satisfying assignments. Its solvers must resolve logical alternatives while finding and establishing the best objective value permitted by the formula. We present NeurOMT, a framework for guiding OMT over linear integer arithmetic by selecting candidate partial assignments. Each candidate assigns truth values to a subset of arithmetic predicates, restricting the search while leaving numerical values open. We train a graph neural network to select among these candidates using the total solver cost of restricted optimization and subsequent exact search. The network scores each candidate from its assigned atoms, their truth values, and the formula representation. The selected assignment guides optimization to obtain an objective bound, followed by exact continuation under the original constraints. Experiments show reductions in total solver-stage time relative to direct Z3 on OMT benchmarks including knapsack and resource-constrained scheduling, with ratios from 11.4% to 94.4%.

Primary area:
optimization
Keywords:
Optimization Modulo Theories(OMT), Graph Neural Network(GNN), Linear Integer Arithmetic (LIA)

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_fYqCOpenReview ↗
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
  1. 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.
  2. 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.
  3. 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.
  4. It is order-invariant and phase-aware, and the formula is encoded once, so scoring many candidates is cheap.
  5. Aggregate speedups reach about 18× on completion time, with wins on more than 90% of instances in all three RCSP classes.
  6. The paper uses three repetitions in randomized order and paired group-bootstrap intervals.
  7. The results include the knapsack E2E ratio above 1 and OptiMathSAT being stronger on two classes.
Critical weaknesses
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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

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/bir_i=t_i/b_i and bˉ=1N∑ibi\bar b=\frac{1}{N}\sum_i b_i, 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/N1/N convention. A therefore negative covariance Cov⁡(bi,ri)\operatorname{Cov}(b_i,r_i) 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).

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.

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

This paper presents NeurOMT, a GNN framework guiding Optimization Modulo Theories (OMT) problems by selecting candidate partial assignments. It uses a GNN to select candidate truth assignments to arithmetic predicates based on the combined cost of restricted optimization and subsequent exact search. Experimental results show remarkable PAR-2 reduction than Z3.

Critical strengths
  1. This paper is well-motivated. This work builds a GNN model to select partial assignments that reduce the total solver cost of finding and certifying a globally optimal solution.
Critical weaknesses
  1. The writing is not sufficiently clear. For example, the experimental setups are not clearly explained.
  2. The experimental evaluation lacks comparisons with closely related learning-based OMT methods.
Questions for authors
  1. What’s the meaning of the caption of Table 1? Like replacement instances, the repaired cohort.
  2. Please compare NeurOMT with the other learning-based OMT methods. Such as Ashera, the author(s) discussed in Sec. 2.2.
  3. In Sec. 4.4, what’s the definition of “frontend” runtime here? Does it include the model runtime?
  4. In Sec. 4.4, could the author(s) analyze the runtime breakdown and identify the main bottleneck? Because Table 2 shows that the proposed method has 1.019 E2E ratio, worse than the baseline.
2 comments

Thank you for your constructive feedback, and we will revise our paper accordingly. We offer further explanation and additional experimental results on your concerns as below and in the revised paper.

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.

Learning-Based OMT Baseline (Q2, W2). We add Ashera as a learning-based OMT solver baseline, with end-to-end PAR-2 costs are shown in Table 1. Results show that NeurOMT outperforms Ashera on all sorts of problems, and Ashera fails to solve any of the problems in Buffer Storage and Completion Time.

Frontend Definition And Analysis of Costs (Q3, Q4). The frontend consists of five parts: parsing, candidate generation (with or without LP), graph construction, GNN encoding and inference. Therefore, GNN model runtime is considered as a part of frontend runtime. 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 5.

Thanks for the response. Some of the corcerns have been addressed, but the writing remain insufficiently clear to me. I therefore need more time to review the revised manuscript and will give new comments during reviewer-AC discussion if necessary. Based on the additional results, I will increase the score, but remains weak reject.

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

The paper presents NEUROMT, a learned selector for partial truth assignments in optimization modulo linear integer arithmetic. It generates candidate assignments over arithmetic predicates, scores them with a graph neural network trained on the measured cost of restricted optimization followed by exact continuation, and sends only the selected candidate to Z3. After obtaining an incumbent, the method removes it and searches the original formula for a better solution, preserving exactness when the optimization calls finish. On generated knapsack and resource-constrained scheduling benchmarks, the method reduces solver-stage PAR-2 relative to direct Z3. End-to-end results are mixed on knapsack and favorable on the three scheduling classes.

Critical strengths
  • Candidate alternatives are compared in formula context. The GNN encodes the formula once and scores each concrete candidate using the assigned atoms and their phases. This shares formula processing across candidates and avoids treating a construction rule as equally useful on every instance.
  • The implementation integrates the learned selector with a complete solver workflow. It generates candidates from 73 construction templates, deduplicates identical assignments, uses inexpensive propagation checks to filter detectable conflicts, shares the formula encoding across candidate scores, and uses Z3 push/pop to apply and then remove the selected restriction. The whole approach is well engineered.
  • The evaluation is comprehensive and honest. It uses certified optima and PAR-2 penalties for timeouts, reports solver-stage and end-to-end costs separately, and includes instance-level and group-bootstrap analyses. The end-to-end scheduling ratios are 0.445 for completion time, 0.360 for buffer storage, and 0.466 for flow balancing versus direct Z3. These are substantial gains on the tested distributions, while the paper appropriately shows that the result does not carry over to knapsack end to end.
  • The experimental protocol has several careful controls. The main learned-versus-direct comparison uses the same Z3 backend and test sets, keeps related parent or capacity variants together in data splits, randomizes method order, repeats timing measurements, applies a shared solver deadline, and reports paired group-bootstrap intervals. The paper also includes candidate-selection and encoder ablations. These choices make the reported within-distribution comparisons more informative, although the repaired-cohort and offline-cost questions remain open.
Critical weaknesses
  • Neural guidance for OMT predates this work, including Ashera. The paper distinguishes its approach, but the contribution is an incremental extension of neural-guided OMT.
  • Frontend costs are substantial. On knapsack, the end-to-end PAR-2 ratio is 1.019 versus direct Z3, so the complete method is slightly slower. The paper identifies frontend reduction as future work but does not suggest a remedy.
  • The paper does not report the cost of evaluating all candidate assignments to create training labels, or the total offline training and label-generation cost. These costs matter for deciding when the method pays off.
  • Table 1 and the appendix refer to a repaired cohort and replacement instances, but do not explain the repairs, replacement selection, or their effect on the paired comparison.
  • Direct Z3 is the main baseline. OptiMathSAT is compared on a 100-instance subset, and there is no direct comparison with Ashera. The paper does include random selection and a dataset-level best-template ablation, but lacks a stronger instance-conditioned, non-learning selection baseline.
Questions for authors
  1. The frontend can dominate runtime, and the end-to-end knapsack result is slightly worse than direct Z3. Which components account for most of the frontend time, and what concrete changes could reduce it? Please report end-to-end results after any such changes, or clarify whether the current gains require repeated use that amortizes this overhead.
  2. Beyond random selection and choosing one best template for the whole dataset, did you evaluate instance-conditioned non-learning baselines for choosing a candidate partial assignment? For example, can a simple LP-based or objective-and-clause heuristic select candidates effectively without training a GNN?
  3. How much total solver time was used to label the candidate assignments and train each selector, and how many test instances or repeated uses are needed to amortize that cost?
  4. What does “repaired cohort” mean in Table 1 and the bootstrap analysis? How many instances were replaced, why were they replaced, and how were replacements selected?
2 comments

Thanks for your constructive feedback.

Comparing to Existing Neural-guided OMT Approaches. Ashera pioneered neural guidance for OMT, and focuses on the numeric values. Our work focuses on key linear propostions and boolean variables which provide the backend solver with a more flexible search space. It also uses generation templates to provide a structured, sTable candidate space. As shown in experiment results added in Table 1, NeurOMT outperforms Ashera (reimplemented according to their research paper) on all sorts of problems, and Ashera fails to solve any of the problems in buffer storage and completion time, showing probably better generalization and scalability.

Frontend Costs. We appreciate your insight and 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 5.

Labelling And Training Costs. 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.

Replacements in The Dataset. 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.

Non-learning Baseline. We add per-instance oracle solver times as a theoretical ceiling for any selection among the templates, as shown in Table 2.

SOTA Solver Baseline. 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.

Thank you for the response and edits to the paper. I'm keeping my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.