acceptodds
Under review as a conference paper at ICLR 2027

Automated Inverse Optimization with LLMs via Verification-Guided Hypothesis Search

Abstract

Inverse optimization (IO) infers latent decision-making models from observed decisions, but classically requires experts to rigidly specify the objective, constraints, and behavioral assumptions prior to estimate model parameters. While recent advances in large language models (LLMs) have enabled automated construction of optimization models from natural language, they struggle in the inverse setting, where the latent model structure must be iteratively inferred from behavioral demonstrations. We formulate automated IO as a structure-aware learning problem, jointly identifying the objective components, latent constraints, behavioral assumptions, and numerical parameters from observed decisions. To address this, we propose VeriHy, an LLM-based framework that performs verification-guided search over competing model hypotheses. VeriHy organizes hypotheses in a directed acyclic graph and uses evidence from successful candidates and counterexamples to guide model refinement and recombination. Experiments across convex, combinatorial, and real-world IO problems show that VeriHy achieves performance competitive with expert-crafted classical methods and significantly outperforms LLM baselines under matched search budgets.

Primary area:
optimization
Keywords:
Inverse Optimization, Hypothesis Search, Large Language Models

Reviews

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

The paper proposes VeriHy, an LLM-based framework for inverse optimization with unknown model structure and parameters. It uses LLM-guided hypothesis search with deterministic fitting and verification to recover objectives, constraints, and behavioral assumptions from observed decisions. The method is evaluated on synthetic convex and combinatorial benchmarks as well as the Amazon Last Mile Routing Challenge.

Critical strengths

The paper studies an interesting problem: replacing expert-crafted specification of inverse optimization models with automated LLM-crafted construction. This is potentially useful, and the paper is well written.

However, the proposed solution lacks sufficient novelty and is not yet convincingly validated; see the concerns below.

Critical weaknesses

1. Limited novelty.

The methodological novelty appears limited. VeriHy follows a familiar iterative LLM-search pattern—proposal, evaluation, selection, and refinement—applied to inverse optimization. While its DAG representation provides domain-specific machinery, I do not see a sufficiently clear new algorithmic principle relative to existing LLM-based search frameworks.

Prior works already adopt closely related LLM-based search architectures. ATHENA uses LLM-based symbolic search to discover utility max problem from observed choice data. LISTEN-U uses an LLM to iteratively refine a parametric utility max problem from natural-language preference information. Particularly relevant, CogFunSearch uses an LLM-powered evolutionary search to discover symbolic models from behavioral data, including the reward max problem form model; its search separately fits model parameters and evaluates candidate models on behavioral data. The paper should discuss these closely related works much more thoroughly and clarify how VeriHy differs methodologically from them.

The paper also provides a formalization of the problem. However, this contribution is primarily a synthesis and adaptation of emerging literatures rather than a new theoretical result.

Overall, I do not find the core methodological contribution sufficiently novel to meet the bar for ICLR.

2. Limited Evidence That the Proposed Search Mechanism Is Necessary

Two of the key structural benchmarks have explicitly characterized and relatively small structural hypothesis spaces: 21 hypotheses for matching and 84 for scheduling. This makes an exhaustive evaluation of the structural hypothesis set appear practical. The paper should therefore compare VeriHy against exhaustive structural search, as well as matched-budget random or best-first search. These controls are particularly important because the proposed contribution centers on verification-guided hypothesis search. Without them, the current results do not clearly establish how much of the gain is attributable to VeriHy’s DAG search rather than to the predefined hypothesis library, deterministic fitting, and verifier.

3. Potential LLM Familiar Task Priors and Insufficient Baselines

The experimental evidence leaves two concerns. First, several benchmarks use familiar optimization problem families such as knapsack, matching, scheduling, and routing. This raises the possibility that the proposal LLM benefits from generic semantic or structural priors about these task families. My concern is whether the search advantage persists when task semantics and candidate components are anonymized or when structurally novel synthetic task families are used.

Second, the baseline design does not cleanly isolate the contribution of VeriHy. The paper should include a controlled self-evolution baseline using the same prompt, information, LLM, fitting/verifier pipeline, and search budget, while replacing VeriHy with a standard iterative self-refinement loop. This would clarify whether the gains come from VeriHy’s specific search design or from generic iterative LLM refinement.

Reference

[1] Personalized Decision Modeling: Utility Optimization or Textualized-Symbolic Reasoning. NeurIPS 2025

[2] LISTEN to Your Preferences: An LLM Framework for Multi-Objective Selection. IJCAI 2026.

[3] Discovering Symbolic Cognitive Models from Human and Animal Behavior. ICML 2025

Conclusion

The paper explores an interesting direction. However, given its limited novelty and several key experimental issues, I do not think the paper meets the ICLR bar. If the authors can adequately address my concerns, tone down the overclaims, reframe the contribution primarily as a search mechanism, and resolve the fundamental experimental issues by providing convincing evidence for the effectiveness of the proposed search mechanism, I would be willing to revise my rating.

Questions for authors
  1. Given how close the architecture is to so many existing literatures, what new algorithmic principle does VeriHy establish?

  2. How much of the reported gain comes specifically from VeriHy’s search design? Could the authors compare against a controlled single-trajectory self-refinement baseline using the same LLM, prompt information, fitting/verifier pipeline, and search budget?

  3. Given that matching and scheduling contain only 21 and 84 structural hypotheses, respectively, how does VeriHy compare with exhaustive search and matched-budget random or best-first search?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 79Jc (Part 1 of 2)

Thank you for such a constructive review and for pointing out a clear path forward: reframing VeriHy primarily as a verification-guided structure-search framework for inverse optimization, where the LLM acts as a pluggable proposal policy (M1 to M3) alongside our deterministic policy (M0). We fully embrace this framing and have run the exact controlled experiments you requested.

Q1: What new algorithmic principle does VeriHy establish, and how does it differ from CogFunSearch, ATHENA, and LISTEN-U?

We agree that the overarching propose, evaluate, select, and refine loop is an established paradigm and that our formalization is a synthesis rather than a standalone theorem; we will temper our claims accordingly.

What makes our setting fundamentally challenging, and largely unaddressed by prior work, is tackling general inverse optimization when both the objective function and the feasible region (constraints) are simultaneously unknown. To solve this coupled discovery problem without blind trial and error, VeriHy introduces a distinct algorithmic principle: pricing structural edits directly via the counterexample subgradient of the inverse-optimization loss, coupled with deductive constraint falsification.

Specifically, for a block-linear hypothesis, our counterexample evidence score dˉk\bar{d}_k (Eq. 11) measures the negative gradient of the IO suboptimality loss with respect to an inactive objective block kk on current counterexamples. Mathematically, this is the reduced cost of introducing column (objective block) ψk\psi_k into the active model. Meanwhile, latent constraints are pruned via deductive falsification: any observed expert decision violating constraint cc rules out every hypothesis containing cc. Together, this turns joint objective and constraint discovery into a column and row generation procedure over the model space, where each candidate structure is refitted via an inner IO solver and verified on held-out decisions. Generic LLM evolutionary loops, by contrast, only observe a scalar fitness score per program and lack any gradient-like signal indicating which missing component explains current errors.

We will also be transparent about the empirical role of pricing: on small closed libraries, pricing speeds up convergence by roughly two fewer fits without changing the final structure, whereas on larger constrained libraries, the sign of pricing is decisive (5/5 vs. 1/5 exact recovery). Across all settings, consistent accuracy gains come from pairing modular hypothesis search with inner IO fitting, constraint falsification, and admission validation.

This joint uncertainty over objectives and combinatorial constraints also separates VeriHy from CogFunSearch, ATHENA, and LISTEN-U, which we will discuss in depth in Section 2:

  • CogFunSearch evolves symbolic cognitive models from behavioral data using per-program parameter fitting and a scalar log-likelihood, modeling stochastic choices over a few discrete actions without combinatorial constraints.
  • ATHENA performs LLM-guided symbolic discovery of utility functions over discrete choice sets followed by individual-level parameter refinement.
  • LISTEN-U iteratively refines a parametric multi-objective utility from natural-language preference feedback.

In all three frameworks, an agent picks from a small, explicitly given set of alternatives, and the feasible set is known a priori. In VeriHy, decisions are arg⁡max⁡\arg\max solutions over an exponentially large combinatorial space whose constraints are themselves hidden. Evaluating even a single hypothesis requires solving a cutting-plane bilevel IO problem, and the search must simultaneously explain why the expert preferred yiy_i (the objective) and why competing alternatives were excluded (the latent constraints).

Our breakdown against generic LLM-evolution baselines (EoH, MCTS-AHD, OpenEvolve, ShinkaEvolve) shows why decoupling these two unknowns in the search state is critical. Those baselines recover the exact joint structure in only 7 to 13 of 36 runs (with 73 to 94% feasible predictions), whereas VeriHy recovers 33/36 (and deterministic M0 recovers 32/36) with 100% feasibility. Their final programs explain why: evolutionary loops often find the right constraints (26 to 34/36 runs) or the right objective (up to 22/36 runs), but almost never both together, because rewriting monolithic code forces them to rediscover one part while mutating the other. In VeriHy, each search node maintains a factored state (Φ,G,R)(\Phi, G, R) updated via local typed edits, preserving verified constraints across descendants while the objective continues to refine (GG recovered in 36/36 runs, Φ\Phi in 33/36).

Revising overclaims: We will rewrite the Abstract and Introduction to present VeriHy squarely as a verification-guided structure-search framework for joint objective and constraint inverse optimization, supporting pluggable (deterministic or LLM) proposal policies.

AuthorsOpenReview ↗

Response to Reviewer 79Jc (Part 2 of 2)

Q2: Controlled single-trajectory self-refinement baseline. Following your exact specification, we implemented a single-trajectory self-refinement baseline using the identical LLM (gpt-4o-mini), task prompt, initialization seeds, admission validator, IO fitter, verifier, and 30-fit budget. At each iteration, the LLM sees the complete history of evaluated hypotheses (including validation scores, loss terms, and rejected proposals) and proposes the next full hypothesis (Φ,G,R)(\Phi, G, R), stopping after 3 consecutive steps without a new admissible hypothesis, without VeriHy's DAG state, parent selection, or counterexample reduced-cost pricing:

Method (36 runs each)KnapsackSchedulingMatchingExact (Φ,G)(\Phi, G)Mean FitsTokens / Run
Single-trajectory Self-Refine1.66%1.05%1.17%22/3612.545k
VeriHy-M10.05%0.81%0.93%33/3616.823k

(Values report penalized test regret averaged over N∈{50,100,200}N \in \{50, 100, 200\} and 4 seeds.) Despite consuming nearly 2x as many tokens (its prompt carries the full history), self-refinement recovers the exact structure in only 22/36 runs. On Knapsack in particular, it fails in 12/12 runs (retaining spurious distractor blocks alongside the true objective in 10/12 runs, and converging to a wrong structure with ~9.6% regret in 2/12 runs), whereas VeriHy-M1 recovers the exact structure in 33/36 runs.

Q3: Exhaustive enumeration and matched-budget search on the 21/84-hypothesis spaces. After admission filtering, the valid spaces contain 15 (Matching), 60 (Scheduling), and 69 (Knapsack) hypotheses; VeriHy evaluates 13.1, 15.4, and 21.8 of them on average. Running exhaustive enumeration, matched-budget random search, and matched-budget CKS-style best-first search (always expanding the lowest-J node over all its neighbors) on the exact same pipeline across all 36 runs yields:

Search Strategy (identical pipeline)Regret %Exact (Φ,G)(\Phi, G)Mean Fits
VeriHy-M10.6033/3616.8
Exhaustive enumeration0.7231/3648.0
Random search (matched budget)1.1318/3615.6
Best-first search (all neighbors, matched budget)1.8622/3616.8

We agree that exhaustive search is practical on spaces of size 15-69 and will include it in the main table. VeriHy achieves slightly better recovery than exhaustive search (33/36 vs. 31/36, avoiding occasional validation overfitting across all 69 candidates) using 2.9x fewer expensive IO fits, while decisively outperforming random and best-first search at the same budget. Structure selection itself is necessary: on a new structural convex benchmark with 8 candidate attribute terms (255 hypotheses), fitting the entire library yields 0/12 exact recoveries (distractors are kept), whereas VeriHy-M0 recovers 12/12 in 37.5 fits, matching exhaustive enumeration (255 fits).

Honest limitation on scaling: When we expanded that synthetic library up to 17 distractor terms (≈106\approx 10^6 hypotheses), recovery degraded beyond ~8 candidate terms (≤1/4\le 1/4 seeds within a 60-200 fit budget), primarily because top-down pruning from the full library and validation selection on 50 decisions favor slightly over-complete models. We will report this scaling boundary explicitly in the paper rather than claiming scalability to arbitrary library sizes.

W3: Ruling out LLM semantic priors on familiar problem families. We verified through three checks that our results do not stem from the LLM memorizing textbook problem families (knapsack, matching, scheduling):

  1. Deterministic policy M0: M0 never receives any text descriptions or component names, yet matches VeriHy-M1 in 34/36 runs (0.62% vs. 0.60% regret, 32/36 exact recovery).
  2. Full prompt anonymization: We re-ran VeriHy-M1 across all 36 runs after stripping all domain semantics (replacing every component, constraint, set, and field name with opaque tokens like component_i and constraint_i, replacing descriptions with bare algebraic expressions, and using a generic task prompt: "an expert repeatedly makes a discrete decision from a finite feasible set..."). Performance was virtually unchanged: 0.61% regret (vs. 0.60%), 33/36 exact recovery (identical test regret in 34/36 runs), with similar token usage (24k vs. 23k).
  3. Structurally neutral synthetic benchmark: Our new 255-hypothesis structural convex benchmark uses abstract algebraic attribute features (a,b,ab,d,ad,bd,a2,d2a, b, ab, d, ad, bd, a^2, d^2) with no connection to any classic named problem family, and VeriHy-M0 recovers 12/12 structures.

We appreciate your concrete feedback; it helped us sharpen our core claims and provide the exact controlled evidence needed to validate the search mechanism.

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

The paper proposes VeriHy for inverse optimization when objective components, constraints, and behavioral assumptions are uncertain. An LLM proposes model hypotheses, deterministic optimization routines fit their parameters, and validation feedback guides refinement and fusion within a hypothesis DAG. Experiments cover synthetic convex and combinatorial problems and real-world delivery routing, reporting decision quality, search efficiency, and structural recovery.

Critical strengths
  1. The problem setting is meaningful. Allowing uncertainty in model structure addresses a limitation of parameter estimation within a fixed optimization model. Separating LLM proposals from numerical fitting and held-out evaluation is a sensible design.

  2. The reported combinatorial results are promising. VeriHy achieves low penalized regret across knapsack, scheduling, and matching tasks. Evaluating structural recovery alongside predictive performance is also useful, since accurate predictions alone do not establish recovery of the underlying model.

Critical weaknesses
  1. The experiments do not consistently evaluate the method defined in the main text. Sections 3–4 define hypotheses as objective components, constraints, and behavioral assumptions, with numerical fitting delegated to fixed routines. However, Appendix A.1 states that the convex benchmarks contain only one structural model, while Appendix F.1 describes searching over parameter-estimation programs. Thus, the convex results appear to evaluate estimator discovery rather than the proposed structural search. There is another discrepancy in matching: Section 5.1 mentions latent constraints such as forbidden edges, but Appendix A.2.2 describes known degree constraints and a search over objective components and behavior models. These differences make it unclear which results support the central claims.

  2. The evaluation does not isolate the value of the LLM or the proposed search mechanisms. Appendix B defines a deterministic evidence-guided policy, M0, but no comparison against it is reported. There are also no controlled ablations of counterexample feedback, fusion, or behavioral diversity. This is particularly important because matching has only 21 structural hypotheses and scheduling has 84 before admission and redundancy filtering. Exhaustive enumeration and simple search baselines would provide informative references. Without these controls, the gains could largely come from the component libraries, admission checks, or fitting routines. The routing experiment does not resolve this concern: it introduces Claude Code for algorithm implementation, but provides insufficient detail about the search configuration, fitting procedure, and within-zone reconstruction to attribute the reported score to VeriHy.

Questions for authors
  1. What exactly is searched in the convex experiments: model structures, fitting methods, or executable estimator programs? How does this implementation correspond to Sections 3–4? Please also clarify which matching experiments contain unknown constraints.

  2. How does VeriHy compare with M0, random search, and exhaustive enumeration using the same fitting and verification pipeline? For the 21- and 84-hypothesis settings, what fraction of the admissible space is actually evaluated?

  3. Which components explain the gains? Comparisons without counterexample summaries, fusion, and behavioral-diversity selection would help distinguish their contributions. Which proposal level, M1–M3, is used in each reported experiment?

  4. Could you specify the routing implementation and evaluation protocol, including the validation split, Claude model and budget, parameter fitting, within-zone reconstruction, and whether baseline scores were reproduced under the same protocol? Please also report the number of independent runs and variability for the main results.

3 comments
AuthorsOpenReview ↗

Response to Reviewer qb1U (Part 1 of 3)

Thank you for a sharp and constructive review. Your observations regarding consistency between our methodological framing and our experiments are spot-on, and we have run new controlled experiments to address them directly.

Q1: Structural search in Convex and unknown constraints in Matching.

  • Convex: You are right that in the original convex benchmarks (Appendix A.1), the forward optimization structure is fixed and each node represents an estimator program h:(U,Y)↦θ^h:(U,Y)\mapsto\hat{\theta} (selected from KKA, MOM, feasible-set center and ensembles, or synthesized by the LLM; evidence comes from training cross-validation). While this uses the same propose-fit-verify loop, it tests estimator discovery rather than structural search. We will state this distinction clearly, present the estimator benchmark as a secondary study, and add a new structural convex benchmark directly aligned with Section 3. Here, decisions lie on the simplex, and the objective combines a known baseline with an unknown subset of 8 candidate attribute terms (3 true terms and 5 distractors such as a⋅da\cdot d and a2a^2, giving 255 candidate structures; feasible set known; fitted via KKA across N∈{50,100,200}×4N \in \{50, 100, 200\} \times 4 seeds):
MethodExact Φ\PhiMean FitsRel. Regret % (N=50/100/200N=50 / 100 / 200)
VeriHy-M012/1237.50.07 / 0.09 / 0.04
VeriHy-M19/1239.50.07 / 0.07 / 0.05
Exhaustive enumeration (255)*12/12255 / 255 / 50*0.07 / 0.09 / 0.04
Random search (matched budget)6/1239.50.74 / 0.25 / 0.05
Full library, no search (direct KKA)0/121.01.41 / 0.81 / 0.30

Structural search is essential here: fitting the full library without search retains spurious distractor terms and suffers 6-20x higher regret. (*At N=200N=200, each KKA fit takes ~7 minutes, so exhaustive search hit its 6-hour cap after 50 hypotheses; it still found the true model because the true subset happened to appear early in the enumeration order.) VeriHy matches the exhaustive optimum using ~6.5x fewer fits at N=50,100N=50, 100 (the 3 M1 misses are slight supersets that hit the 40-fit budget).

  • Matching and Scheduling constraints: Thank you for catching the discrepancy in Section 5.1. In the main matching grid (Table 2, m=20m=20), the degree constraints are known, and the search operates over 3 objective components x 3 behavioral models (21 hypotheses). We will correct the misleading sentence in Section 5.1. Latent forbidden-edge constraints appear in our constrained matching variant (8 objective components and 3 optional constraints), which we will move into the main text as our larger-library benchmark. Meanwhile, Scheduling in the main grid contains genuinely unknown constraints (the precedence topology chosen from {∅,QA,QB,QC}\{\emptyset, Q_A, Q_B, Q_C\}), and VeriHy recovers the exact constraint set GG in 12/12 scheduling runs (36/36 across all combinatorial runs).

Q2: Comparison against M0, Random, and Exhaustive search, and fraction of space evaluated. Evaluating all methods on the exact same admission, fitting, and verification pipeline (penalized test regret %, mean over 4 seeds):

MethodKnapsack (50/100/20050/100/200)Scheduling (50/100/20050/100/200)Matching (50/100/20050/100/200)Exact (Φ,G)(\Phi, G)
M0 (deterministic, no LLM)0.10 / 0.04 / 0.020.76 / 0.47 / 1.420.95 / 0.65 / 1.1732/36
VeriHy-M10.10 / 0.04 / 0.020.76 / 0.61 / 1.070.95 / 0.65 / 1.1733/36
Exhaustive enumeration0.08 / 0.04 / 0.021.04 / 0.75 / 1.720.95 / 0.65 / 1.1731/36
Random (matched budget)0.25 / 0.06 / 0.072.20 / 2.20 / 2.620.95 / 0.65 / 1.1718/36
Best-first (matched budget)2.40 / 2.75 / 2.471.77 / 2.08 / 2.590.85 / 0.65 / 1.1722/36

After admission filtering, the valid hypothesis spaces contain 15 (Matching), 60 (Scheduling), and 69 (Knapsack) structures. On average, VeriHy-M1 evaluates 13.1 (87%), 15.4 (26%), and 21.8 (32%) hypotheses respectively (M0 evaluates 13.1, 17.2, and 21.6).

We read these numbers candidly: Matching is small enough that every method converges to the same structure. On Scheduling and Knapsack, however, VeriHy achieves slightly better accuracy than exhaustive enumeration (33/36 vs. 31/36 exact recovery; 0.81% vs. 1.17% scheduling regret, as exhaustive search occasionally overfits the validation set across all 60-69 candidates) while requiring 3-4x fewer expensive IO fits on these two problems (2.9x overall), and substantially outperforming random and CKS-style best-first search at the same budget.

AuthorsOpenReview ↗

Response to Reviewer qb1U (Part 2 of 3)

Q3: Component ablations, proposal levels (M1-M3), and run variability.

To isolate which components drive performance, we re-ran controlled ablations across all 36 runs of the main combinatorial grid (measuring exact (Φ,G)(\Phi, G) recovery and the average number of fits needed to first reach the true structure):

Configuration (36 runs each)Exact (Φ,G)(\Phi, G)Fits to First True Structure
M0 (full deterministic policy)32/368.6
M0 without admission validator27/369.5 (misses true structure in 5 runs)
M0 with unsigned (∣⋅∣\lvert\cdot\rvert) pricing33/368.6
M0 without cross-branch fusion32/367.9
M0 with Jaccard (instead of behavioral) diversity32/368.2
M0 without evidence ranking (random admissible edit)34/369.3
VeriHy-M1 (full LLM-guided policy)33/367.8
VeriHy-M1 without counterexample evidence in prompt31/369.9

Test regret remains within 0.02 percentage points across all ablations. We will report this nuanced picture transparently in the paper:

  1. On compact closed libraries, the admission validator is the single most impactful component for final recovery (preventing degenerate or non-identifiable models from polluting selection), while counterexample evidence pricing accelerates convergence (~2 fits sooner under M1) without altering the asymptotic endpoint.
  2. Signed vs. unsigned pricing shows no difference on small libraries, but is decisive on our larger constrained-matching library (8 objective blocks + 3 optional constraints, 5 seeds), where exact recovery drops from 5/5 to 1/5 under unsigned pricing (and behavioral vs. Jaccard diversity drops from 5/5 to 3/5).
  3. Fusion has no measurable effect on these benchmarks (triggering on only 14 of 603 nodes and never sitting on the winning lineage), and we will state this plainly rather than overclaiming its contribution.

Clarification of proposal levels (M1-M3):

  • Combinatorial benchmarks: All main runs use M1 (structured edits over the component library).
  • Convex benchmarks: Use M1 over the estimator library plus optional LLM synthesis of new estimator code.
  • Routing benchmark: Uses free-form hypothesis synthesis by a coding agent, in the spirit of M2/M3 but outside the controlled M0-M3 interface. This is the open-ended regime M2/M3 target, where no complete library exists and a strong LLM must propose new structural terms directly; we will label it as such rather than as a controlled M2/M3 evaluation.

Independent runs and variability: All combinatorial results are averaged over 4 independent seeds, and all convex results over 3 independent seeds (4 seeds for the new structural convex benchmark); routing is a single full-dataset evaluation. In the revised tables, we will report mean ± sd across seeds for all multi-seed experiments (for example, on Sched-200, VeriHy achieves 1.07 ± 1.18 vs. EoH's 2.33 ± 0.08). Pooled across all 36 combinatorial runs, VeriHy suffers 0/36 catastrophic failures (>50% regret), whereas competing baselines fail in 3/36 to 25/36 runs.

AuthorsOpenReview ↗

Response to Reviewer qb1U (Part 3 of 3)

Q4: Routing implementation, evaluation protocol, and attribution.

We agree that the appendix description of the routing experiment was too brief to clearly attribute the performance gains. We will add a dedicated, self-contained protocol section to the appendix with the following details:

  • Dataset split and evaluation protocol: We follow the exact official challenge train/test split and evaluation protocol, evaluating on the held-out set of 3,052 routes using the official Amazon scorer. The test set is never touched during search or tuning. All models are built strictly from the official training set: we hold out 30 training routes as a validation set to guide every search decision (scoring each candidate as the mean over 2 LKH-AMZ solver seeds), and run the selected hypothesis once on the 3,052 test routes.
  • Search configuration and budget: The proposer/implementer is Claude Code (Anthropic, 2025) powered by Claude Opus 5.5, exploring a 25-node hypothesis graph. Four root nodes serve as baselines rebuilt on the exact same training split: standard travel-time TSP, the inverse-optimization routing model of Scroccaro et al. (Routing IO, re-implemented), and Stages 1 and 2 of JPT (built from its public codebase). Of the 21 proposed hypotheses, 3 were refuted by counterexample checks before fitting; the other 18 were fitted and scored on the 30 validation routes, and the best-scoring one (n23) was selected. Each node is a declarative configuration of objective and constraint modules compiled into a fixed harness (compile constrained TSP -> LKH-AMZ at 5s per tour -> official scorer). Code synthesis occurs strictly during search; no LLM is invoked at evaluation time.
  • Structure of the selected hypothesis (node n23):
    1. Objective: Stop-level travel time plus a depot-specific zone-to-zone transition cost matrix and area/region penalties learned via inverse optimization (projected subgradient descent on the suboptimality loss over training routes, following the Routing IO formulation).
    2. Constraints: Zone contiguity, cluster and super-cluster neighbor constraints, and pairwise zone precedences extracted from the closest historical training route (using constraint families adapted from JPT's public build phase and refitted on our training split).
    3. Label-free candidate selection: Under these constraints, the model generates two candidate zone orderings (one from the closest historical route and one from station-wide pairwise zone-precedence frequencies), reconstructs each within-zone tour via LKH-AMZ (5s/tour), and selects whichever tour achieves the lower learned IO zone cost (without using ground-truth test labels).
  • What the search discovered and proper attribution: Validation ablations during search showed that removing any of these constraint families degrades performance (with cluster constraints contributing the largest gain), whereas substituting an oracle zone order yields only modest further improvement, pinpointing within-zone sequencing and zone revisits as the primary remaining bottlenecks. We credit the zone-cost IO formulation to Routing IO and the structural constraint families to JPT; VeriHy's contribution is the verification-guided search that discovered how to compose them alongside a label-free IO selection rule, using only the 30 validation routes for selection.

Regarding baseline reproduction in Table 3: under the identical official train/test split, we ran a single full evaluation for the methods with public code (VeriHy's selected node n23, JPT, and Routing IO; the pipelines are deterministic, and our JPT run reproduces its published score), while scores for baselines without public code are reported directly from their respective papers (which we will mark explicitly in Table 3). VeriHy achieves 0.0265, improving over the Routing IO model it builds upon by 12.3% (0.0265 vs. 0.0302) while remaining behind JPT (0.0248), a heavily domain-engineered routing system. We will tone down our claim accordingly from "approaching the challenge-winning result" to "improving upon IO-based routing formulations."

We deeply appreciate your insightful feedback, which substantially strengthened the paper. We hope these new results and clarifications resolve your concerns and warrant a more positive assessment.

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

The paper proposes VeriHy, which is an LLM-guided framework designed for inverse optimization. This framework infers objective components, constraints, and behavioral assumptions based on observations. The authors tried different model structures to fit their parameters, and used validation results to improve performance. Experiments cover synthetic optimization tasks and real-world routing, which demonstrate the effectiveness of the proposed method.

Critical strengths
  1. This paper argues that optimization process includes not only model parameters but also which objectives and constraints can explain the expert decisions.
  2. In the framework, the LLM suggests changes, and the solvers fit and evaluate each model.
Critical weaknesses
  1. The main novelty of this paper is unclear, since several parts of the framework already exist in earlier work. It seems that this paper is only a combination of existing works[123] ([1] is compared as an experiment baseline in this paper, but not clarify the difference of this method). At least the authors should clarify what new mechanism VeriHy introduces beyond adapting these ideas to structural inverse optimization. Otherwise the readers cannot clearly tell the specific contribution of this article.
  2. Section 4.1 (lines 176–178) describes changing model structures, but the experiments try different ways to estimate parameters (Appendix F.1, lines 1202–1207)
  3. This paper does not identify the specific contribution of LLM and DAG.
  4. Several details didn't be provided, including search budgets, routing configurations, etc.

[1] Structure Discovery in Nonparametric Regression through Compositional Kernel Search [2] OptMaster: A DAG-Based Framework for Formulation and Heuristic Discovery in Optimization [3] Learning Programs by Learning from Failures

Questions for authors

Actually, I'm not familiar with this area. However, I tried to read relative paper and identify the contribution of this work. The main concern is weakness 1. I would be glad to raise my score if the authors could address my concern.

2 comments
AuthorsOpenReview ↗

Response to Reviewer dk1L (Part 1 of 2)

Thank you for taking the time to read related literature outside your core area and for giving us a clear path to address your main concern. We fully agree that if VeriHy were merely wrapping an LLM around existing structure-search loops, its contribution would be incremental. In the revision, we will reframe our core contribution clearly: VeriHy is a verification-guided structure-search mechanism for inverse optimization (IO), where the LLM acts as a pluggable proposal policy (M1-M3) alongside a deterministic policy (M0).

To clarify what new algorithmic mechanism VeriHy introduces beyond Compositional Kernel Search (CKS) [1], OptMaster [2], and Learning from Failures (LFF) [3], it helps to look at how structural hypotheses are scored and edited:

First, unlike [1-3], evaluating a single candidate in VeriHy requires solving an inner bilevel inverse-optimization problem. CKS fits continuous kernel parameters via marginal likelihood on regression data; OptMaster takes a known problem specification and executes generated forward heuristics; LFF prunes logic programs against discrete input-output examples. In structural IO, we only observe expert decisions yiy_i without knowing the underlying objective or constraints. A candidate hypothesis (Φ,G,R)(\Phi, G, R) predicts decisions via an arg⁡max⁡\arg\max over a combinatorial feasible set XG(ui)X_G(u_i), so scoring even one structure requires solving a cutting-plane or KKT inverse problem to fit its parameters θ\theta before checking whether it reproduces the expert's choices.

Second, VeriHy uses counterexample subgradients rather than scalar validation scores to decide which objective edit to try next. Because fitting every neighbor via an inner IO solver (as CKS does) is computationally expensive, we score missing objective blocks using the gradient of the IO suboptimality loss on current counterexamples (Eq. 11). This acts as the reduced cost of adding a block, turning objective search into column generation over the block library. Empirically, this guidance reaches the true structure faster on our standard grids (7.8 vs. 9.9 fits for M1), and the sign of the pricing becomes decisive on a larger constrained library (signed vs. unsigned: 5/5 vs. 1/5 seeds on constrained matching). On the small grids it does not change the final structure; the larger gains come from the mechanism as a whole. For example, a CKS-style best-first search (always expanding the lowest-J node over its full neighborhood) on the exact same pipeline and budget recovers the exact structure in 22/36 runs (1.86% regret), vs. 33/36 (0.60%) for VeriHy.

Third, we separate constraint falsification from objective pricing. LFF's failure-driven pruning applies directly to our constraints: a single observed decision violating constraint cc deterministically rules out every hypothesis containing cc. However, this pruning does not work for objective blocks because adding a true objective term can fix some counterexamples while temporarily creating others until weights are refitted. That asymmetry is why VeriHy pairs deductive falsification for constraints with counterexample subgradient pricing for objectives.

Finally, we note that the baseline compared in our experiments is OptMaster [2] (adapted to our interface), rather than CKS [1]. Under the identical setup, OptMaster exceeds 50% regret in 25/36 combinatorial runs and recovers the exact structure in only 6/36 runs (vs. 33/36 for VeriHy). We will add this comparison to Sections 2 and 4.

AuthorsOpenReview ↗

Response to Reviewer dk1L (Part 2 of 2)

Addressing your remaining points (W2-W4):

W2: Alignment between Section 4.1 and the convex experiments (Appendix F.1). You are right. In our original convex benchmarks, the structure is fixed (Appendix A.1), and the search operates over estimator programs h:(U,Y)↦θ^h:(U,Y)\mapsto\hat{\theta} (such as KKA, MOM, or LLM-synthesized estimators). While this uses the same propose-fit-verify loop over a different hypothesis space, it does not test the structural search defined in Sections 3-4. We will state this explicitly, move the estimator-discovery experiment to a secondary role, and add a new structural convex benchmark with genuine structural uncertainty in the objective. Here, decisions lie on the simplex, and the true objective combines a known baseline with an unknown subset of 8 candidate attribute terms (3 true terms and 5 distractors, yielding 255 candidate structures; N∈{50,100,200}×4N \in \{50, 100, 200\} \times 4 seeds):

MethodExact Φ\PhiMean FitsRegret % (N=50/100/200N=50 / 100 / 200)
VeriHy-M012/1237.50.07 / 0.09 / 0.04
VeriHy-M19/1239.50.07 / 0.07 / 0.05
Exhaustive enumeration12/12255*0.07 / 0.09 / 0.04
Random search (matched budget)6/1239.50.74 / 0.25 / 0.05
Full library, no search0/121.01.41 / 0.81 / 0.30

*At N=200N=200, a single KKA fit takes ~7 minutes, so exhaustive enumeration hit its 6-hour cap after 50 hypotheses.

W3: Isolating the contributions of the LLM and the hypothesis DAG. To separate the search mechanism from the language model, we now report M0 (the same search, pricing, fitter and verifier, with deterministic proposals and no LLM). Across the 36 combinatorial runs, M0 gives the same test regret as VeriHy-M1 in 34/36 runs:

Method (identical pipeline & budget)Regret %Exact (Φ,G)(\Phi, G)Mean Fits
VeriHy-M10.6033/3616.8
M0 (deterministic, no LLM)0.6232/3617.3
Exhaustive enumeration0.7231/3648.0
Random search (matched budget)1.1318/3615.6
Best-first search (CKS-style, matched budget)1.8622/3616.8

What this shows: on closed libraries where all building blocks are predefined, the LLM is not the source of accuracy; the verification-guided search mechanism is. Our ablations further show that the admission validator is critical on these grids (dropping recovery from 32/36 to 27/36 when disabled), whereas cross-branch fusion and Jaccard diversity had no measurable effect on final recovery here. The LLM's role lies in the open-ended regime targeted by M2/M3 (such as our real-world routing benchmark), where no complete component library exists and a strong model must synthesize new structural hypotheses from IO data.

Why a hypothesis DAG rather than program evolution: each VeriHy node maintains a complete, modular state (Φ,G,R)(\Phi, G, R) updated via typed local edits. Once a constraint GG is verified, every descendant inherits it while the objective Φ\Phi continues to be refined, and equivalent hypotheses reached via different edit paths are merged and fitted only once. In contrast, program-evolution baselines (EoH, MCTS-AHD, OpenEvolve, ShinkaEvolve) rewrite monolithic code; objective and constraint discoveries made in separate branches must be rediscovered together. Their final models reflect this bottleneck: they recover the right constraints in 26-34/36 runs and the right objective in at most 22/36, but get both simultaneously in only 7-13/36 runs (compared to 36/36 for GG, 33/36 for Φ\Phi, and 33/36 jointly for VeriHy, using 23k tokens vs. 51k-187k). These baselines also differ in other respects, so this is supporting evidence rather than an ablation; the benefit comes from the shared hypothesis state, not from fusion.

W4: Missing experimental budgets and routing details. We will add a complete budget and protocol table to the paper:

  • Combinatorial: up to 30 admitted nodes (stopping early once all admissible edits of representative nodes are exhausted), 4,500s time cap, M1 policy, mean 23k LLM tokens/run (vs. 51k-187k for baselines), 4 seeds.
  • Convex: 40 proposals per run, 3 seeds (4 seeds for the new structural convex benchmark). We will also report solver call counts and wall-clock times.
  • Routing (Table 3): Evaluated once on the official held-out test set (3,052 routes) with the official scorer; every search decision uses only 30 held-out training routes. The proposer is Claude Code (Claude Opus 5.5) over a 25-node graph of declarative hypotheses run by a fixed harness. The selected node combines an IO-learned zone-transition cost with zone-contiguity, cluster-neighbor and precedence constraints. The full protocol is in our reply to Reviewer qb1U (Q4) and will be added to the appendix.

We hope this clarifies our specific contribution, and would be grateful if you would reconsider your evaluation.

Comments on the paper

2 comments

Dear Reviewers,

Please note that the author rebuttal is now available. We kindly ask you to read it, join the discussion, and update the review as soon as possible. Your prompt action will help us proceed to the final decision. Thanks.

Best regards

AC

AuthorsOpenReview ↗

General Response to the AC and All Reviewers

We sincerely thank the AC and all reviewers for their constructive feedback. Three main concerns emerged: (i) novelty relative to structure-search and LLM discovery methods, (ii) whether gains stem from the search mechanism rather than the LLM, library, or fitter, and (iii) consistency between our method and experiments. We addressed each with new controlled experiments and a revised PDF (changes in blue). Since the main text is at the page limit, new experiments appear in Appendix F and are summarized in the main text.

  1. Positioning and Novelty (dk1L, 79Jc)
  • VeriHy is framed as a verification-guided structure-search framework for inverse optimization (IO) with a pluggable proposal policy, from a deterministic evidence-ranked rule (M0) to LLM proposers (M1-M3) (Intro, Sec. 4.1, Fig. 1).
  • Each candidate is fitted via an inner IO problem over a combinatorial feasible set (Sec. 4.2, App. F.2). Objective edits are priced by the counterexample subgradient of the IO suboptimality loss (reduced cost in column generation), while constraints are deductively falsified against observed decisions (row generation).
  • App. F.1 compares VeriHy against CKS, OptMaster, LFF, ATHENA, LISTEN-U, and CogFunSearch.
  • App. F.2 explains the hypothesis DAG, where verified constraints are inherited and equivalent hypotheses merged. Program-evolution baselines find the true constraints in 26-34/36 runs and the true objective in at most 22/36, but recover both simultaneously in only 7-13/36 runs (VeriHy: 33/36). We state transparently that fusion has no measurable effect.
  1. Isolating the Search Mechanism (All Reviewers) Controlled runs sharing identical data, admission validator, fitter, verifier, and budget across 36 combinatorial tasks (App. F.4, summarized in Sec. 5.2):
MethodRegret %Exact (/36)Fits
VeriHy-M10.603316.8
M0 (no LLM)0.623217.3
Exhaustive enumeration0.723148.0
Random, matched budget1.131815.6
Best-first (CKS-style), matched budget1.862216.8
LLM self-refinement (45k vs. 23k tokens)1.302212.5
  • M0 matches M1's test regret in 34/36 runs, and fully anonymized prompts leave M1 unchanged (0.61% regret, 33/36 exact). On closed libraries, accuracy comes from our search and verification loop rather than LLM priors.
  • Component ablations (App. F.5) show that on small grids, the admission validator matters most (32/36 to 27/36 without it), while evidence pricing finds the true structure ~2 fits earlier. On the larger constrained-matching library (4,080 hypotheses, latent forbidden-edge constraints), signed pricing (5/5 vs. 1/5) and behavioral diversity (5/5 vs. 3/5) prove decisive.
  1. Method-Experiment Consistency (qb1U, dk1L)
  • Sec. 4.1 and 5.1 now note that original convex benchmarks fix the structure and search over estimators. A new structural convex benchmark (8 candidate terms, 255 hypotheses; App. F.6) directly tests structure search: M0 recovers 12/12 ground-truth structures in 37.5 fits, matching exhaustive enumeration, while fitting the full library gets 0/12.
  • Sec. 5.1 clarifies that matching assumes known degree constraints while scheduling involves a latent precedence topology.
  • App. F.6 and the Conclusion explicitly state a limitation: recovery degrades with 9-17 distractor terms.
  1. Routing Protocol (qb1U, dk1L)
  • App. A.3 gives the full protocol: 30 held-out training routes guide every search step, and the selected node is run once on the 3,052 official test routes with the official scorer. The proposer is Claude Code (Claude Opus 5.5) over a 25-node graph (4 baseline roots, 21 proposals: 3 refuted, 18 fitted). We also detail the winning hypothesis and its attribution: zone cost from Routing IO, constraint families from JPT.
  • Table 3 now distinguishes our single full-evaluation runs from scores cited from prior papers. Our claim now reads: VeriHy "improves the Routing IO model it builds on by 12.3%, while remaining behind JPT." App. B clarifies that routing operates in the spirit of M2/M3, outside the controlled M0-M3 interface.
  1. Reporting and Reproducibility
  • We report mean ± sd for all main results, add an M0 row, and report runs above 50% regret (0/36 for VeriHy vs. 3-25/36 for baselines; App. F.3).
  • App. F.7 documents search budgets, policies, and token usage for every experiment, and App. A.3 releases the complete routing search graph (every node's hypothesis and validation score).

Overall, the new evidence confirms that VeriHy's gains come from verification-guided search with IO-priced edits rather than LLM priors. While LLM proposals add little over M0 on small closed libraries, they are valuable in open-ended tasks lacking a complete library, such as routing. We thank the reviewers again for helping us strengthen the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.