acceptodds
Under review as a conference paper at ICLR 2027

REASON, EXPLORE, VERIFY: a neuro-symbolic architecture for constrained long-horizon planning

Abstract

Large Language Models (LLMs) can interpret natural-language goals and generate plausible action sequences, but remain unreliable for constrained long-horizon planning. Errors can accumulate across decisions, locally plausible actions can eliminate feasible continuations, and generated plans can violate numerical, logical, or temporal requirements. We introduce Reason–Explore–Verify (REV), a neuro-symbolic architecture that combines hierarchical problem formulation, explicit trajectory exploration, and formal verification of candidate decisions. We instantiate REV as Hierarchical Monte Carlo Tree Search with SMT Gating (HMCTS-SMT), which integrates hierarchical LLM agents, LLM-guided Monte Carlo tree search, and Satisfiability Modulo Theories solving. Each search node maintains an agentic state and a branch-specific symbolic constraint state. A selected action creates a successor only if its symbolic update preserves satisfiability, making symbolic verification a mandatory transition condition rather than an optional tool or post hoc check. We evaluate HMCTS-SMT on supply-chain optimization and travel planning, covering optimization-oriented and feasibility-oriented settings. Across these tasks, HMCTS-SMT improves plan validity and solution quality over direct generation approach and search-based LLM baselines. These results demonstrate the effectiveness of combining hierarchical decomposition, explicit exploration, and transition-level symbolic verification for constrained long-horizon planning.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Neuro-symbolic AI, Long-horizon planning, Large Language Models, Monte Carlo Tree Search

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_fbSkOpenReview ↗
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?

1 comment

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.

Reviewer_EyUTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes REV, instantiated as HMCTS-SMT, for constrained long-horizon planning with LLMs. It combines hierarchical decomposition, PUCT-guided MCTS, and SMT-based transition verification. Candidate feasibility checks are deferred until actions are selected for expansion, while bounded revision supports failure recovery. Experiments report improved validity and optimality on OptiGuide and higher all-pass rates on ChinaTravel. Coffee ablations support the contributions of verification, hierarchy, and exploration.

Critical strengths
  1. The joint planning state provides a clear representation of the environment state, hierarchical subgoals, and branch-local symbolic constraints.
  2. SMT-based transition gating separates formal admissibility from action-value estimation and rejects symbolically inconsistent updates before creating successor nodes.
  3. The framework integrates symbolic modeling, hierarchical decomposition, local action generation, tree search, and terminal constrained optimization into a unified planning procedure.
Critical weaknesses
  1. HMCTS-SMT incurs substantial latency, averaging 582 seconds per query on ChinaTravel Human with Sonnet. Although some OptiGuide comparisons with ToT have similar call counts, performance under matched token or time budgets remains insufficiently evaluated, particularly against ReAct and LLM-Modulo.
  2. The formal guarantee is limited to the active symbolic encoding, as the authors acknowledge. SMT satisfiability therefore does not ensure that all user requirements are captured or that action updates accurately represent the environment, limiting end-to-end reliability.
  3. The paper identifies VerMCTS as its closest predecessor. However, the current comparisons provide limited evidence for the additional benefits of the proposed planning-specific extension over existing verifier-guided search approaches.
Questions for authors
  1. Could the authors compare performance under matched token or time budgets, extend token reporting to all evaluated methods, and provide corresponding API costs?
  2. Could the authors include adapted versions of LATS [1] and VerMCTS [2] as additional baselines under comparable settings?
  3. Given the single run per query, could the authors repeat the evaluation and report variability to assess the stability of the improvements?
  4. Presentation and consistency issues: (a) Figure 1 needs refinement (font consistency, layout); (b) several data inconsistencies exist between text and tables (e.g., Section H.1 reports 61.3% vs. Table 8's 61.2%);

[1] Andy Zhou et al. Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models. ICML, 2024.

[2] David Brandfonbrener et al. VerMCTS: Synthesizing Multi-Step Programs using a Verifier, a Large Language Model, and Tree Search. 2024.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 2

Response to Reviewer 2

We appreciate the reviewer's recognition of the joint planning state, SMT-based transition gating, and the unified planning procedure. We address each concern below.

R2.W1 Latency and matched-budget evaluation

The revised paper adds full token and API-cost reporting for all OptiGuide methods in Tables 12 and 13 (Appendix G). On Coffee, HMCTS-SMT Sonnet costs 103.86, compared to LATS Sonnet at 94.31 and ToT Sonnet at 68.93. On Facility, HMCTS-SMT Sonnet costs 33.38 , lower than ToT (51.38) and LATS (54.96) due to fewer iterations (11.3 avg. calls/query vs. 30.1 and 35.7). In both cases, HMCTS-SMT delivers substantially higher validity and optimality for comparable or lower cost.

The ChinaTravel latency (582s mean, 320s median with Haiku) is higher, reflecting longer planning horizons and the cost of 300+ solver calls per query. Full runtime statistics are reported in Table 11 (Appendix J).

Regarding matched-budget comparison: we acknowledge this gap. A naïve matched-budget baseline (e.g., giving ReAct 450 independent attempts) is not standard and raises the question of what selection criterion to use without an external verifier. More importantly, ReAct failures on these tasks are systematic — the same constraint categories are violated consistently across runs (see the variability study in Table 10, where only 44% of queries ever produce an invalid plan, indicating structural rather than stochastic failures). Independent repetition does not address systematic constraint violations; MCTS combined with the SMT gate does, though computation grows with blueprint depth. We have noted matched-compute baselines as an explicit direction for future work in Section 9.

R2.W2 Formal guarantee limited to active encoding

This is correct and we state it explicitly. The prefix-satisfiability invariant (Proposition 1) guarantees consistency with the active encoding, not that the encoding captures all user requirements or that Δ(a) faithfully represents the environment transition. The revised paper now includes a detailed failure analysis (Appendix K, Table 14) quantifying where this limitation manifests in practice. On ChinaTravel Human, 38% of hard-logic failures come from missing attraction-type attribute bindings and 17% from missing restaurant-type bindings — cases where the SMT gate checks entity existence but does not pin the selected entity to its required attribute. This is a concrete, addressable gap in the symbolic update design, not a fundamental limitation of the architecture. We identify strengthening attribute-level bindings in Δ(a) as a clear next step.

R2.W3 Limited comparison with VerMCTS

We now provide a detailed conceptual comparison with VerMCTS in Appendix D. The key distinction is that VerMCTS operates on artifacts with formally defined syntax and semantics (Dafny/Coq programs), where the verifier can evaluate partial constructions directly. HMCTS-SMT operates on natural-language planning trajectories, where the semantic-to-formal interface must be constructed and maintained by the global agent. This introduces planning-specific challenges: environment-symbol correspondence, branch-local constraint accumulation, and optimization among feasible trajectories. A direct experimental comparison is not feasible because VerMCTS's domain (program/proof synthesis) does not overlap with ours. We acknowledge VerMCTS as the closest algorithmic predecessor and frame our contribution as extending this principle to constrained planning from natural language.

R2.Q1 Matched token/time budgets and API costs

See R2.W1 above. Tables 12–13 now report per-method token counts and API costs for all OptiGuide experiments.

R2.Q2 LATS and VerMCTS baselines

LATS is now included as a baseline on OptiGuide (Tables 1, 12, 13). With Sonnet, LATS achieves 78.4% validity and 29.7% optimality on Coffee — substantially higher than ToT (10.3% / 2.2%) and ReAct (61.2% / 19.4%), but well below HMCTS-SMT (94.1% / 82.4%) at comparable API cost. This confirms that MCTS-based exploration improves validity over flat baselines, but without symbolic verification it cannot close the optimality gap. For VerMCTS, see R2.W3.

R2.Q3 Variability across repeated runs

We have added a variability study (Table 10, Appendix I.3): 50 Coffee queries × 10 runs

  • Validity: 86.20% ± 2.57% (stable)
  • Optimality: 66.80% ± 6.55% (moderate variance at the binary optimal/suboptimal threshold)
  • Plan-cost median CV: 0.87% (costs remain near-optimal even when the optimality label flips)
  • 86% of queries reach optimal in at least one of 10 runs; 56% are optimal in all 10

The variability is concentrated at the optimal/suboptimal boundary, not substantially affect the validity or cost conclusions.

R2.Q4 Figure 1 and data inconsistencies

Inconsistency is corrected between Section H.1 and Table 8 (61.3% → 61.2%), and refined Figure 1 for font consistency and layout clarity.

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

This paper introduces a neuro-symbolic architecture, Reason-Explore-Verify (REV), that is instantiated as Hierarchical Monte Carlo Tree Search with SMT Gating (HMCTS-SMT). REV is composed of a global LLM which formulates the problem into a symbolic model and subgoal decomposition, a local LLM that proposes candidate actions, the MCTS that explores candidate actions, and a SMT solver that verifies if a selected action preserves the satisfiability of the accumulated constraints. The framework is evaluated on supply chain optimization and travel planning problems from OptiGuide and ChinaTravel. The results show that the proposed framework improves the plan validity and solution quality compared with direct generation approach and search-based LLM baselines.

Critical strengths
  • The experiments, especially the ablation study, clearly show the effectiveness of each component in the framework. By including results of both validity and optimality, the results show that the SMT gate, hierarchy, and MCTS all contribute to both the validity and optimality in planning problems.
Critical weaknesses
  • The contribution of the proposed is not clear or strong enough. As mentioned by the authors, VerMCTS already uses formal verification to reject invalid partial expansions during MCTS. Prior works, for example “Fast and Accurate Task Planning using Neuro-Symbolic Language Models and Multi-level Goal Decomposition”, also combines LLM-based subgoal decomposition, MCTS, and symbolic action checking. The main contribution here seems to be the use of branch-specific SMT constraints, but I’m not convinced that this is a substantial novel or meaningful addition. Especially, the discussion of many closely related planning works and the distinctions are missing from the related works or introduction.
  • The paper claims a distinction of the proposed framework is that it maintains evolving theories across search branches. However, the benefit of this design is not clearly demonstrated. In OptiGuide, the LLM is already asked to encode the full objective, constraints, and requested changes before search begins, what does the proposed framework add over passing this encoded model directly to the solver? The paper does not include this comparison, so it is difficult to judge whether the additional search is helpful under this setting.
Questions for authors
  • Could the authors clarify the main methodological contribution over existing frameworks?
  • Could the authors update the related works and introduction for more detailed prior work discussions?
  • Could the authors compare with more baselines under same conditions and report performance and computation cost comparisons, as they include more closely related works? For example, LLMFP (“Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming”) on Coffee and Facility tasks or NeSy Planning baseline included in the ChinaTravel benchmark. More comparable baselines should be selected after a more extensive literature review.
  • Could the authors add another baseline of using the initially encoded model plus the solver to solve for the OptiGuide questions and provide detailed analysis of the results? If the later corrections or additions improve the results, could the authors separate the benefits of the repair process from hierarchy and MCTS?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 1

Response to Reviewer 1

We thank the reviewer for the engagement with the technical details. We address each point below.

R1.W1 Contribution over VerMCTS and Multi-Level Goal Decomposition

We agree that the individual components are established techniques and do not claim novelty for any single one. The contribution is the specific integration for constrained long-horizon planning — a problem class that neither VerMCTS nor Multi-Level Goal Decomposition addresses in the same way.

  1. vs. VerMCTS: VerMCTS verifies partial programs with formally defined syntax. HMCTS-SMT verifies partial plans from natural language, where the formal model must be constructed from the task description and each action translated into a symbolic update — introducing environment-symbol correspondence, action-update fidelity, and hierarchical progress tracking, none of which arise in program synthesis. A detailed comparison is provided in Appendix D.

  2. vs. Multi-Level Goal Decomposition (Kwon et al., 2025): This work delegates subproblems to different mechanisms (including MCTS and symbolic planners), but subproblems are solved independently — incorrect decompositions or unsupported actions can propagate because they are not validated against a shared formal state, and the MCTS component relies solely on neural priors with no mechanism to reduce hallucination. HMCTS-SMT maintains a branch-local symbolic theory that accumulates across all subgoals, catching constraint violations before successors are created (Section 2.2).

  3. The binding principle: Verification and search are structurally inseparable — no tree transition exists without SMT approval. The gate G(s,a) = I[SAT(Φ(s) ∧ Δ(a))] is a hard precondition for successor creation, not optional feedback. The ablation (Table 4, −Gate) confirms removing this binding drops validity by 9.1pp and optimality by 11.7pp on Coffee.

R1.W2 — Why not pass the OptiGuide encoded model directly to the solver?

We added LLMFP (Hao et al., 2025) as a baseline, representing the closest practical formalize-then-solve approach. LLMFP Sonnet achieves 58.6% validity and 57.5% optimality on Coffee versus HMCTS-SMT's 94.1% and 82.4%. The gap is primarily in validity, showing that single-shot formalization is brittle even with repair loops, whereas HMCTS-SMT's hierarchical search provides recovery through alternative branches and bounded revision.

We acknowledge that for a perfectly encoded model, direct solving would suffice. The point of HMCTS-SMT is that it produces correct formalizations more reliably through iterative search and verification.

R1.Q1 Main methodological contribution

The contribution is verifier-authoritative transitions over coupled agentic and symbolic states: each node carries both an environment-facing state and a branch-local symbolic theory (Eq. 4–5), only SAT transitions create successors, and admissibility (binary, SMT-based) is separated from utility (continuous, MCTS-based). The novelty is the transition rule that makes formal verification a mandatory condition for tree expansion in a hierarchical planning setting.

R1.Q2 Updated related work

Section 2 is reorganized into three subsections (LLM-guided trajectory search, LLM-assisted formalization, verification-controlled generation and search) with added discussions of PDDLEGO, LASP, Multi-Level Goal Decomposition, LLMFP, Formal-LLM, and other works.

R1.Q3 Additional baselines

The revised paper adds LATS (78.4% valid, 29.7% optimal on Coffee Sonnet — confirming MCTS alone cannot close the gap) and LLMFP (58.6% valid, 57.5% optimal — strongest formalize-then-solve baseline, still 35.5pp below HMCTS-SMT on validity). We also add DeepPlanning Shopping Planning (Level 3, n=20) as a third benchmark, where HMCTS-SMT achieves 50% success rate vs. ReAct's 20%.

R1.Q4 Separating the benefits of repair from hierarchy and MCTS

The ablation (Table 4) separates −Gate, −Hierarchy, and Greedy. Revision statistics are reported in Table 11 (mean 0.7 restarts on ChinaTravel Human Sonnet; 78/154 queries need no revision). We will include a dedicated "Full with max_restarts=0" ablation in the final version to isolate the repair mechanism's contribution.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.