- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces Reason-Explore-Verify (REV), instantiated as Hierarchical Monte Carlo Tree Search with SMT Gating (HMCTS-SMT). It combines LLM-based problem formulation and decomposition, tree search over candidate decisions, and mandatory satisfiability checks before admitting transitions. The evaluation covers supply-chain optimization using adapted OptiGuide tasks and itinerary planning using ChinaTravel, with Haiku and Sonnet backbones.
Critical strengths
The integration of search with mandatory symbolic checks is sensible. An action cannot override a failed check as the LLM assigns it a high score. The reported OptiGuide improvements are substantial, and the paper includes component ablations and external evaluation rather than relying only on internal solver acceptance. These provide some evidence that the overall system is useful, altho the contribution of the added search remains clear.
Critical weaknesses
- The most important baseline is missing. Appendix E5 states that the OptiGuide variables, constraints, objectives, and what-if changes are already encoded before search. Why not optimize that model directly? For a fixed, correct model, adding assignment constraints only restricts the feasible set. A baseline using the same translation and solver, but without hierarchical search, is needed to establish what HMCTS contributes.
- The implemented needs additional checking/reporting. In case J1, the membership check confirms that a suitable restaurant exists, but does not check that the selected restaurant has the required cuisine, even tho its actual cuisine is avaible in the db. This is a concrete implementation gap, not simply missing external knowledge.
Questions for authors
Q1: how does HMCTS-SMT compare with directly optimizing the same initial symbolic model, using the same solver and comparable total budge? Does search mainly improve formalization, reduce solving cost, or improve solution quality?
Q2: How are selected entities linked to their required attributes in the symbolic updates? Can you quantify how much is the ChinaTravel failure rate comes from the missing binding in case J1, and whether correcting it changes the comparison?
Q3: Please reconcile the reported median gaps with the optimality counts and clarify the budget repair in case J3. Appendix G1 describes optimality through the claimed costs -- is that cost also recomputed from and checked against the returned assignment?
Response to Reviewer 3
We thank the reviewer for the careful analysis, particularly the identification of the Case J.1 attribute-binding gap and the question about direct solver use.
R3.W1 Missing "direct solve" baseline
The revised paper includes LLMFP (Hao et al., 2025) as a baseline — the closest practical formalize-then-solve approach. LLMFP converts the task into executable Z3 code, solves it, and repairs defective stages. On Coffee, LLMFP Sonnet achieves 58.6% validity and 57.5% optimality (median gap 0.02%), confirming that a well-designed formalize-then-solve pipeline can produce near-optimal solutions when it succeeds. However, HMCTS-SMT Sonnet reaches 94.1% validity and 82.4% optimality — outperforming LLMFP by 35.5pp on validity and 24.9pp on optimality. On Facility, LLMFP reaches 67.3% validity and 64.2% optimality versus HMCTS-SMT's 86.7% and 67.3%.
The gap illustrates the value of iterative search: LLMFP's single-shot formalization can fail when the initial encoding is incomplete, and its repair loop has bounded retries. HMCTS-SMT generates and verifies candidates incrementally, recovering from partial encoding errors through alternative branches and bounded model revision.
We acknowledge that among valid plans, LLMFP's optimality gap (0.02%) is narrower than HMCTS-SMT's (0.42%), confirming that when formalize-then-solve succeeds it produces high-quality solutions. The architectural advantage is primarily in robustness (higher validity rate). A solver-only baseline receiving a hand-verified encoding would test Z3's optimization capabilities rather than the planning architecture.
For ChinaTravel and DeepPlanning, direct solving is harder because relevant entities and facts must be retrieved through tool interactions during planning rather than being available upfront (discussed in Section 2.2).
R3.W2 Entity-attribute binding gap (Case J.1)
In this example the user requests "Sichuan cuisine throughout." The failure originates during initial symbolic model construction: the global agent queries the environment, observes that Sichuan cuisine is a valid type in the database, and erroneously sets the corresponding constraint to
True(trivially satisfied). During subsequent search iterations, when the local agent commits a restaurant, the cuisine constraint is already marked as satisfied regardless of the entity's actual cuisine type. The gate returns SAT and the plan passes internal verification despite violating the user's requirement.This is a formalization error by the global agent rather than a structural limitation of the gate: the constraint is not missing but incorrectly encoded as a tautology. We observe this pattern primarily with Haiku, whose weaker reasoning capabilities make it more prone to premature constraint resolution. Sonnet produces correct encodings more reliably.
R3.Q1 What does search improve over direct solving?
Search contributes in three ways: (1) robustness — when the initial formalization is imperfect, alternative branches and model revision provide recovery paths unavailable to single-shot solving; (2) grounding , in domains like ChinaTravel, search interleaves information retrieval with decision-making, acquiring facts not available for upfront formalization; (3) optimization among alternatives — MCTS compares multiple feasible trajectories, selecting the best terminal objective. The ablation (Table 4) confirms that removing MCTS (Greedy) drops optimality from 82.4% to 25.3% on Coffee, while validity decreases more modestly (94.1% → 88.3%), indicating search plays an important role in solution quality.
R3.Q2 Quantifying the attribute-binding failure rate
55% of ChinaTravel Human hard-logic failures (67/122) trace to attraction-type or restaurant-type attribute mismatches. Correcting entity-attribute binding in Δ(a) would not guarantee all 67 become passes (some may have compounding errors), but we estimate it would substantially improve the all-pass rate. We plan to evaluate this fix in the next revision.
R3.Q3 Median gaps, optimality counts, and budget repair
The median gap is computed *conditional on valid plans only, while optimality counts use all n queries as the denominator, a method with fewer valid plans may report a lower conditional gap while having a lower optimality rate. We have clarified this in the revised Appendix H.1.
For Case J.3 (budget repair): when the SMT solver detects UNSAT due to budget exhaustion, the global agent revises the blueprint (e.g., dropping a free-breakfast constraint to free ¥600), and the resulting plan is re-verified under the revised model. The reported cost is recomputed from the terminal assignment and checked against the ground-truth cost function.