- 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
-
Given how close the architecture is to so many existing literatures, what new algorithmic principle does VeriHy establish?
-
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?
-
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
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 , 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) | Knapsack | Scheduling | Matching | Exact | Mean Fits | Tokens / Run |
|---|---|---|---|---|---|---|
| Single-trajectory Self-Refine | 1.66% | 1.05% | 1.17% | 22/36 | 12.5 | 45k |
| VeriHy-M1 | 0.05% | 0.81% | 0.93% | 33/36 | 16.8 | 23k |
(Values report penalized test regret averaged over 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 | Mean Fits |
|---|---|---|---|
| VeriHy-M1 | 0.60 | 33/36 | 16.8 |
| Exhaustive enumeration | 0.72 | 31/36 | 48.0 |
| Random search (matched budget) | 1.13 | 18/36 | 15.6 |
| Best-first search (all neighbors, matched budget) | 1.86 | 22/36 | 16.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 ( hypotheses), recovery degraded beyond ~8 candidate terms ( 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):
- 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).
- 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).
- Structurally neutral synthetic benchmark: Our new 255-hypothesis structural convex benchmark uses abstract algebraic attribute features () 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.
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 (Eq. 11) measures the negative gradient of the IO suboptimality loss with respect to an inactive objective block k on current counterexamples. Mathematically, this is the reduced cost of introducing column (objective block) ψk into the active model. Meanwhile, latent constraints are pruned via deductive falsification: any observed expert decision violating constraint c rules out every hypothesis containing c. 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:
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 argmax 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 yi (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) updated via local typed edits, preserving verified constraints across descendants while the objective continues to refine (G recovered in 36/36 runs, Φ 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.