acceptodds
Under review as a conference paper at ICLR 2027

ReCoNav: Reliable Constrained Long-Horizon Vision-and-Language Navigation via a Determination Engine

Abstract

Conventional vision-and-language navigation (VLN) asks an agent to follow a described route to a destination. Practical missions can require multiple ordered visits, with hard constraints and preferences governing both target selection and connecting routes. Existing agents use memories, maps, or constraint-guided planning, but reliably propagating scoped requirements across interpretation, grounding, and complete-route planning remains challenging. We introduce ReCoNav, whose instruction contract models route requirements for joint target and route selection. Its Determination Engine uses scene and task rules to propagate route constraints across interpretation, grounding, and planning. Derived evidence determines choices, verifies judgments, and guides repair; vision-language models supply unresolved semantics. We construct a benchmark of 192 scene-grounded tasks across nine indoor scenes to evaluate joint target and route satisfaction. Existing methods show low satisfaction and frequent timeouts. On 44 constraint-resolving tasks without the added time limit, global scene access helps but remains insufficient: ReCoNav achieves 81.82% full instruction satisfaction, versus 29.55% for the best evaluated existing method given global scene information and 38.64% for direct planning with feedback sharing our scene information, backbone, and solver. Across four backbones, ReCoNav improves satisfaction with fewer model tokens than this feedback baseline; ablations support explicit contract-based planning, global determination, and verification with repair.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Vision-and-Language Navigation, Long-Horizon Planning, Constraint-Aware Planning, Neuro-Symbolic Reasoning, Embodied AI

Reviews

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

The paper introduces ReCoNav, a framework for long-horizon vision-and-language navigation with ordered visits, hard constraints, and preferences. Given a fully-observed scene graph, it translates natural-language instructions into a formal instruction contract. Its Determination Engine combines symbolic rules and route-feasibility queries to resolve target ambiguities, verify interpretations, and guide VLM-based repairs. A constraint-aware solver then generates routes satisfying the resulting specification. Evaluation on 192 tasks across nine indoor scenes, using ground-truth scene graphs, shows improved instruction satisfaction over the evaluated baselines. The main contribution is coordinating instruction interpretation, target grounding, and route planning through shared constraints and verification.

Critical strengths

The authors study an interesting problem. Supporting human preferences and constraints is important for deploying robots in the real world.

Critical weaknesses
  1. The paper is hard to follow despite careful reading. VLN is a broad problem, and it is unclear which subproblem the paper aims to address. Is the main contribution (1) enabling VLN to satisfy additional constraints and preferences, or (2) providing a formal way to verify the translation from natural language to formal specifications? If (1), handling additional natural-language constraints and preferences is not novel in itself, and the distinction from prior work needs clarification. If (2), the paper does not clearly establish the verification foundation: what are the minimal trusted assumptions, and are the checking rules predefined or generated by the VLM? Checking a solution against a VLM-generated specification does not, by itself, verify that the specification correctly captures the original instruction. VLM judgments alone do not constitute formal verification.

  2. The writing needs improvement. For example, the abstract and introduction state that the Determination Engine uses “scene and task rules,” but it is initially unclear whether these rules are predefined by human experts, generated online by a foundation model, or derived from the instruction’s hard constraints and preferences. Their relationship to these constraints and preferences should be explained more clearly. The connection between the stated insight "that uncertainty in individual judgments does not preclude deterministic relations between them (line 89)" and the subsequent description of local rules is also insufficiently explained. A concrete example early in the paper would help clarify the reasoning mechanism and its contribution.

  3. The problem definition does not clearly distinguish between planning over a discrete navigation graph and motion through continuous space. Line 136 defines a collision-free waypoint route, (pi=(s_0,q_1,...,q_n)), but how are the connecting motions constructed, and what assumptions are made about the robot’s ability to follow them? Also, whether eq(4) minimizes the cost of the waypoint only or the entire trajectory is not clear.

  4. The paper should state its assumptions more clearly and earlier. In particular, the task definition should explicitly state that a scene representation obtained through pre-exploration is available before planning. The use of fixed, ground-truth scene graphs in the benchmark should also be highlighted early, as it substantially affects the scope of the problem.

  5. Given the global scene graph and deterministic transitions, the planning component becomes classical symbolic planning or task and motion planning (TAMP). The problem lies in translating natural language into a formal specification, rather than solving the symbolic planning problem itself. After the problem is converted to a formal specification, it is unclear why a classical SAT/SMT-based planner or TAMP solver cannot solve the problem. Prior work, including LLM+P [1] and CaStL [2], already combines language models with formal planning. The paper should clarify this distinction.

  6. Handling additional constraints or preferences expressed in natural language is not, by itself, novel. For example, CaStL [2] uses an LLM to translate constraints into PDDL and Python scripts that add constraints to a downstream SMT-based task and a motion planner. The related work discussion should include these approaches and explain the additional contributions of the proposed scoped constraints, preference handling, and determination mechanism.

[1] Liu et al. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. 2023. [2] Guo et al. CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planning. ICRA 2025.

Questions for authors
  1. Lines 138–139: Could the authors explain (D(v)) more concretely?

  2. Could the authors state more precisely what is new relative to prior work on translating natural-language constraints into formal specifications for symbolic planning?

13 comments
AuthorsOpenReview ↗

Overall Response to Reviewer 4z11

Thank you for recognizing the importance of constrained navigation and for suggesting CaStL [1] and LLM+P [2]. We appreciate prior advances in formal planning. Our work builds on this foundation and investigates how formal reasoning can be used more extensively to improve the reliability of long-horizon VLN.

Overall Response

Research problem. We study constrained long-horizon VLN, where ordered visits, scoped AVOID and distinct-entity COUNT constraints, and preferences must govern decisions throughout navigation. The central challenge is to propagate these requirements across instruction interpretation, grounding, and complete-route planning. Figure 1 illustrates an important consequence: even after semantic and spatial matching identifies candidate targets, route constraints and preferences may determine which target should be selected.

Benchmark. Conventional VLN focuses on route following. We first construct a scene-grounded benchmark to evaluate these requirements and their role in target selection. Existing methods achieve low full-instruction satisfaction, including those given global scene information. These results show that scene access and formal planning alone do not ensure full-instruction satisfaction.

Technical approach. Observation/history-based VLN may lack information about distant targets and connecting routes, motivating maps, memory, and pre-exploration. Map-informed VLM planning, as in MapGPT and NavGPT+ASG, is one possible approach. These findings motivate ReCoNav’s use of formal scene and route evidence throughout the decision process. Rules and solver queries provide explicit feasibility, infeasibility, and preference evidence for interpretation, grounding, and final planning.

Our contributions address this problem at three levels:

  1. Benchmark: A scene-grounded benchmark exposing the central challenge faced by existing methods in constrained long-horizon VLN.
  2. Instruction Contract: A formal task definition that formulates this challenge as a problem solvable by formal solvers.
  3. ReCoNav: A system designed to solve this problem reliably using predefined scene/task rules and solver-derived route evidence to derive, verify, and revise judgments.

The anonymous repository provides implementations, rules, and prompts. The project page provides task examples and real-robot demonstrations.

[1] Guo, Kingston, and Kavraki. CaStL: Constraints as Specifications through LLM Translation for Long-Horizon Task and Motion Planning. ICRA 2025.

[2] Liu et al. LLM+P: Empowering Large Language Models with Optimal Planning Proficiency. 2023.

AuthorsOpenReview ↗

Response to W1

W1. Research scope

  1. Research problem and contributions. The Overall Response clarifies our research problem and three contributions. Here, route constraints refer to visits, their order, scoped avoidance and counts, and preferences, as defined in Section 3.1 (lines 137–138). Spatial constraints such as IN and NEAR restrict candidate domains and are well studied in prior navigation work. Our focus is the remaining gap: propagating route constraints across navigation stages so that they govern both target choices and complete routes.

    We respectfully disagree with the assessment that the paper is hard to follow and does not clearly define its research problem and contributions. The submitted paper explicitly describes both, together with the distinction from spatial grounding:

    Limitations and challenge (Section 1, Limitations of existing approaches, lines 83–85): Identifies the limitations of existing approaches in propagating scoped requirements across navigation stages and states the resulting challenge.

    Contributions (Section 1, final paragraph): States the three contributions: the instruction contract, ReCoNav, and the benchmark.

    Relationship to spatial grounding (Section 2, Spatial and constraint-aware navigation, lines 120–122): Distinguishes semantic and spatial matching from route-constraint reasoning.

  2. Verification and trusted assumptions. Verification is one component of ReCoNav, one of our three contributions alongside the benchmark and instruction contract. ReCoNav is designed to improve VLN reliability through formal reasoning. As stated in Section 1 (lines 88–89), “uncertainty in individual judgments does not preclude deterministic relations between them.” VLM judgments may be uncertain, but we trust the predefined relations imposed by scene and task definitions. This is not only our insight but also our minimal trusted assumption. ReCoNav implements these relations through predefined rules and solver queries to derive judgments, verify their consequences, and provide evidence for repair.

    For example, task semantics define the following rule for visit events x,yx,y:

    BEFORE⁡(x,y)⇒jx<jy.\operatorname{BEFORE}(x,y)\Rightarrow j_{x}<j_{y}.

    In Figure 3, BEFORE(v,v) is a judgment proposed by the VLM. Applying the predefined rule yields jv<jvj_{v}<j_{v}, exposing a contradiction. The conflict does not establish whether the BEFORE relation or its event references were misinterpreted. The engine provides the violated rule, implicated judgments, and source phrase as evidence for the VLM to revise the interpretation.

    Rules also support derivation. The rule Fβ=∅⇒β∉BH\mathcal{F}_{\beta}=\varnothing\Rightarrow\beta\notin\mathcal{B}_{H} excludes a candidate binding when it admits no hard-feasible route. In Figure 3, route queries establish this premise for the bindings to R9 and R10. Excluding them leaves R4 as the unique feasible bedroom target.

    We will make these connections and the verification assumptions more explicit in the revised Introduction.

AuthorsOpenReview ↗

Response to W2

W2. Scene/task rules and the reliability insight

  1. Rules versus VLM judgments. Our insight is that “uncertainty in individual judgments does not preclude deterministic relations between them” (Section 1, lines 88–89). W1 explains this insight and the scene/task rules with examples. Rules are not the judgments extracted by the VLM. They encode the relations those judgments must satisfy according to scene and task definitions. These rules are predefined in the implementation.

    Figure 3(a) explicitly displays the checking relation BEFORE⁡(a,b)⇒ja<jb\operatorname{BEFORE}(a,b)\Rightarrow j_a<j_b separately from BEFORE(v,v). The former is a task-defined rule, and the latter is the VLM judgment being checked.

  2. Core rules. We will further clarify the distinction between rules and judgments and add a complete table of the core rules to the revised paper.

    Rule groupRules
    Instruction contract consistency∃a,b: s=u[a:b]\exists a,b:\ s=u[a:b]
    sf∉Wfs_f\notin\mathcal W_f for fields with a blacklist
    ∣Er∣=1\lvert E_r\rvert=1
    ei≺ej⇒ji<jje_i\prec e_j\Rightarrow j_i<j_j
    ei1≺⋯≺eim≺ei1⇒⊥(m≥1)e_{i_1}\prec\cdots\prec e_{i_m}\prec e_{i_1}\Rightarrow\bot\quad(m\geq1)
    Scene grounding and contract consistencyDi={nj∈N∣match⁡(nj,ei)}\mathcal D_i=\{n_j\in N\mid\operatorname{match}(n_j,e_i)\}
    coref⁡(ei,ej)⇒β(ei)=β(ej)\operatorname{coref}(e_i,e_j)\Rightarrow\beta(e_i)=\beta(e_j)
    ∣Di∣=1 ∧ n∈Di⇒β(ei)=n\lvert\mathcal D_i\rvert=1\ \land\ n\in\mathcal D_i\Rightarrow\beta(e_i)=n
    Di=∅⇒⊥\mathcal D_i=\varnothing\Rightarrow\bot for a required event
    COUNT⁡⋈k(NC,σ)∈H ∧ ⋈∈{=,≥} ∧ k>∣NC∣⇒⊥\operatorname{COUNT}_{\bowtie k}(N_C,\sigma)\in H\ \land\ \bowtie\in\{=,\geq\}\ \land\ k>\lvert N_C\rvert\Rightarrow\bot
    Global binding determinationFβ=∅⇒β∉BH\mathcal F_\beta=\varnothing\Rightarrow\beta\notin\mathcal B_H
    (BH={β} ∨ B∗={β})⇒select⁡(β)(\mathcal B_H=\{\beta\}\ \lor\ \mathcal B_*=\{\beta\})\Rightarrow\operatorname{select}(\beta)
    Complete-route verificationqji∈D(β(ei))q_{j_i}\in D(\beta(e_i)) for required visits
    jg=nj_g=n for the final visit
    ei≺ej⇒ji<jje_i\prec e_j\Rightarrow j_i<j_j for applicable hard orders
    Jσ(π,ω)∩NA=∅J_\sigma(\pi,\omega)\cap N_A=\varnothing for hard AVOID
    ∣Jσ(π,ω)∩NC∣⋈k\lvert J_\sigma(\pi,\omega)\cap N_C\rvert\bowtie k for hard COUNT
    p(π,ω;P)=∑c∈Pwc 1[c is violated]p(\pi,\omega;P)=\sum_{c\in P}w_c\,\mathbf 1[c\text{ is violated}]

    New notation:

    • ss is a retained source phrase, and a,ba,b are lexical boundaries in uu. ErE_r contains the declared events matching event reference rr. sfs_f is the source phrase cited for field ff, and Wf\mathcal W_f is its conservative blacklist.
    • match⁡(n,ei)\operatorname{match}(n,e_i) tests whether ASG entity nn satisfies the target type, label, and spatial qualifiers specified for event eie_i in the contract. coref⁡(ei,ej)\operatorname{coref}(e_i,e_j) means that events eie_i and eje_j explicitly refer to the same target entity.
    • select⁡(β)\operatorname{select}(\beta) denotes adopting binding β\beta.
    • For soft clause cc, wc>0w_c>0 is its violation cost. 1[⋅]\mathbf 1[\cdot] equals one when its condition holds and zero otherwise.

    The anonymous repository provides the implementations and repair procedure.

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

This paper studies constrained long-horizon navigation, where target selection and complete routes must jointly satisfy ordered visits, scoped avoidance constraints, distinct-entity counts, and preferences. ReCoNav represents these requirements as an instruction contract grounded in an Affordance Scene Graph. Its Determination Engine combines local rules and global route queries to resolve target ambiguity, verify commitments, and revise semantic judgments while invalidating dependent conclusions. The authors introduce 192 tasks across nine indoor scenes and evaluate existing navigation methods, adaptations with global scene access, and controls sharing the same backbone and constraint solver. Experiments using ground-truth scene graphs show substantial improvements in instruction satisfaction and lower model-token usage, with targeted ablations supporting route-dependent target determination.

Critical strengths
  1. The coupling of target selection and complete-route constraints addresses a meaningful problem. Locally matching targets need not admit a route satisfying the entire instruction. ReCoNav explicitly reasons over joint target assignments and checks encounters along connecting segments, rather than only requested waypoints. The formulation also carefully distinguishes unknown results from certified infeasibility and makes conclusions conditional on the current interpretation and scene representation.
  2. The benchmark’s semantic validity and long-horizon difficulty need stronger characterization. Tasks are constructed symbolically, filtered for feasibility and target resolution, and then verbalized by language models (Appendix C.1). The paper does not report a dedicated independent assessment of whether the resulting instructions faithfully and unambiguously express the reference contracts. It also lacks distributions of event counts, interacting scopes, candidate assignments, and corresponding performance. Consequently, the results establish effectiveness within the constructed task distribution more clearly than reliability on independently written or increasingly complex instructions. Ground-truth scene graphs are appropriate for isolating reasoning, but the quantitative conclusions should remain scoped to that setting.
Critical weaknesses
  1. The benchmark’s semantic validity and long-horizon difficulty need stronger characterization. Tasks are constructed symbolically, filtered for feasibility and target resolution, and then verbalized by language models (Appendix C.1). The paper does not report a dedicated independent assessment of whether the resulting instructions faithfully and unambiguously express the reference contracts. It also lacks distributions of event counts, interacting scopes, candidate assignments, and corresponding performance. Consequently, the results establish effectiveness within the constructed task distribution more clearly than reliability on independently written or increasingly complex instructions. Ground-truth scene graphs are appropriate for isolating reasoning, but the quantitative conclusions should remain scoped to that setting.
  2. Important implementation details and the contribution of verification/repair remain insufficiently documented. Equation 5 and Appendices B.1–B.3 explain the reasoning semantics, but do not specify the complete implemented rule schemas, binding-search strategy, pruning procedures, or extraction/repair prompts. These details matter for reproducing both accuracy and computational behavior. Moreover, No Verify/Repair already reaches 98.96% and 96.35% Full IS with GPT and Gemini, respectively, versus 100% and 98.44% for the complete system. These results support global determination more strongly than they characterize the additional repair mechanism. Paired correction/regression statistics would clarify when repair helps, when it harms, and whether dependent recomputation is consequential.
Questions for authors
  1. Benchmark validation: How was natural-language equivalence to the reference contracts checked? Please report any independent annotation or audit protocol, ambiguity/error rates, and which components are shared between task validation, the planner, and the evaluator.
  2. Algorithm specification: Can you provide the implemented rule schemas, pseudocode for joint binding and route search, and extraction/repair prompts? What are the typical graph sizes, candidate-assignment counts, solver-call counts, and proportions of certified versus unresolved binding decisions?
  3. Repair attribution: On jointly completed tasks, how many outcomes become correct, remain unchanged, or become incorrect after verification/repair? How often are repairs rule-determined versus VLM-proposed, and how often does dependency invalidation change a downstream binding or route?
  4. Long-horizon coverage: What are the distributions of required visits, active scopes, and candidate bindings? Does the advantage persist on the most complex tasks, and is it stable across seeds when unresolved bindings require the fallback procedure?
8 comments
AuthorsOpenReview ↗

Overall Response to Reviewer BLWh

Thank you for recognizing the importance of our research problem and for suggesting ways to strengthen the benchmark characterization. The anonymous repository provides the prompts and output schemas for Direct and Direct-Feedback, benchmark construction and validation tools, and rule implementations. The project page includes task examples and real-robot demonstration videos. We will add the benchmark construction and validation details, rule and algorithm specifications, and additional experimental results to the revised paper.

W1

  1. Instruction validity. Q1 details how natural-language instructions are generated from feasible scene-grounded contracts, reviewed by GPT-5.6 Sol against their symbolic requirements, revised where needed, and manually inspected. We will add this validation protocol and the revision statistics to the paper.

  2. Long-horizon difficulty. Q4 reports distributions of required visits, simultaneously active scopes, and candidate assignments, together with performance on the most complex tasks. ReCoNav achieves the highest aggregate Full IS among the evaluated controls in all three subsets. Q4 also reports additional three-seed Qwen results, where its overall advantage persists. We will add these distributions and results to the revised paper.

  3. ASG. We use ground-truth ASGs to isolate task reasoning from scene reconstruction errors. Our quantitative findings concern this setting. Developing accurate scene reconstruction is beyond the scope of this work. Our real-robot demonstration uses an ASG built from registered RGB-D using MaskClustering [1], mask-conditioned VLM recognition following OpenVoxel [2], as described in Section 3.2 and Appendix B.5. Robustness to imperfect scene grounding remains an important direction, as discussed in Section 5 through online mapping and incremental ASG construction. We are also interested in extending rules and solver-based verification to ASG construction.

W2

  1. Algorithm specification. Q2 provides the core rules, joint-binding and route-search pseudocode, pruning procedures, and extraction/repair prompts and schemas in the anonymous repository. We will incorporate these algorithm details into the revised appendix.

  2. Role of verification and repair. We study constrained long-horizon VLN and how to propagate route constraints throughout navigation. Our three contributions are a benchmark exposing gaps in existing methods, an instruction contract formalizing the problem underlying these gaps, and ReCoNav, a system designed to solve this problem reliably. Verification and repair are one component of the system. Q3 provides the paired results and a recomputation example, showing that repair and recomputation are consequential.

[1] Yan et al. MaskClustering: View Consensus based Mask Graph Clustering for Open-Vocabulary 3D Instance Segmentation. CVPR 2024.

[2] Huang et al. OpenVoxel: Training-Free Grouping and Captioning Voxels for Open-Vocabulary 3D Scene Understanding. CVPR 2026.

AuthorsOpenReview ↗

Response to Q1

Q1 Benchmark validation

To facilitate evaluation, we construct the benchmark with the goal of making instruction interpretation, target resolution, and complete-route requirements as unambiguous as possible. We first generate scene-grounded instruction contracts with feasible routes and uniquely resolved targets. Gemini 3.7 Flash or GPT-5.6 Sol then generates natural-language instructions from these contracts. GPT-5.6 Sol reviews every instruction against its symbolic requirements, checking omissions, added requirements, scope errors, and ambiguous wording. Before final acceptance, 63/192 instructions (32.81%) were revised or clarified and reviewed again. For example, “the book in the living room with a carpet nearby” was clarified as “the book that is in the living room and has a carpet nearby,” making the modifier attachment explicit. All 192 final instructions passed the GPT-5.6 Sol audit. We also manually inspected the tasks.

Task validation and ReCoNav planning share the ASG geometry, navigation graph, and SMT-based route solver. Evaluation is performed by a separate route evaluator without invoking ReCoNav. It checks the actual waypoint trace against the task’s annotated constraints. The ground-truth annotations created during benchmark construction for scoring are not provided to ReCoNav’s planner, which generates routes using the contract extracted from the instruction.

AuthorsOpenReview ↗

Response to Q2 (Part1)

Q2 (Part 1). Implemented rule schemas

Implemented rule schemas. Our core scene and task rules cover instruction contract consistency, scene grounding, global binding determination, and complete-route verification. The anonymous repository provides their implementations. reconav/method/determination.py also defines RegisteredRule and RuleRegistry, with rule identifiers and callbacks for derivation, verification, deterministic repair, and evidence collection. The navigation pipeline currently invokes the concrete rule procedures directly.

The following table summarizes the core rules in formal notation.

Rule groupRules
Instruction contract consistency∃a,b: s=u[a:b]\exists a,b:\ s=u[a:b]
sf∉Wfs_f\notin\mathcal W_f for fields with a blacklist
∣Er∣=1\lvert E_r\rvert=1
ei≺ej⇒ji<jje_i\prec e_j\Rightarrow j_i<j_j
ei1≺⋯≺eim≺ei1⇒⊥(m≥1)e_{i_1}\prec\cdots\prec e_{i_m}\prec e_{i_1}\Rightarrow\bot\quad(m\geq1)
Scene grounding and contract consistencyDi={nj∈N∣match⁡(nj,ei)}\mathcal D_i=\{n_j\in N\mid\operatorname{match}(n_j,e_i)\}
coref⁡(ei,ej)⇒β(ei)=β(ej)\operatorname{coref}(e_i,e_j)\Rightarrow\beta(e_i)=\beta(e_j)
∣Di∣=1 ∧ n∈Di⇒β(ei)=n\lvert\mathcal D_i\rvert=1\ \land\ n\in\mathcal D_i\Rightarrow\beta(e_i)=n
Di=∅⇒⊥\mathcal D_i=\varnothing\Rightarrow\bot for a required event
COUNT⁡⋈k(NC,σ)∈H ∧ ⋈∈{=,≥} ∧ k>∣NC∣⇒⊥\operatorname{COUNT}_{\bowtie k}(N_C,\sigma)\in H\ \land\ \bowtie\in\{=,\geq\}\ \land\ k>\lvert N_C\rvert\Rightarrow\bot
Global binding determinationFβ=∅⇒β∉BH\mathcal F_\beta=\varnothing\Rightarrow\beta\notin\mathcal B_H
(BH={β} ∨ B∗={β})⇒select⁡(β)(\mathcal B_H=\{\beta\}\ \lor\ \mathcal B_*=\{\beta\})\Rightarrow\operatorname{select}(\beta)
Complete-route verificationqji∈D(β(ei))q_{j_i}\in D(\beta(e_i)) for required visits
jg=nj_g=n for the final visit
ei≺ej⇒ji<jje_i\prec e_j\Rightarrow j_i<j_j for applicable hard orders
Jσ(π,ω)∩NA=∅J_\sigma(\pi,\omega)\cap N_A=\varnothing for hard AVOID
∣Jσ(π,ω)∩NC∣⋈k\lvert J_\sigma(\pi,\omega)\cap N_C\rvert\bowtie k for hard COUNT
p(π,ω;P)=∑c∈Pwc 1[c is violated]p(\pi,\omega;P)=\sum_{c\in P}w_c\,\mathbf 1[c\text{ is violated}]

New notation:

  • ss is a retained source phrase, and a,ba,b are lexical boundaries in uu. ErE_r contains the declared events matching event reference rr. sfs_f is the source phrase cited for field ff, and Wf\mathcal W_f is its conservative blacklist.
  • match⁡(n,ei)\operatorname{match}(n,e_i) tests whether ASG entity nn satisfies the target type, label, and spatial qualifiers specified for event eie_i in the contract. coref⁡(ei,ej)\operatorname{coref}(e_i,e_j) means that events eie_i and eje_j explicitly refer to the same target entity.
  • select⁡(β)\operatorname{select}(\beta) denotes adopting binding β\beta.
  • For soft clause cc, wc>0w_c>0 is its violation cost. 1[⋅]\mathbf 1[\cdot] equals one when its condition holds and zero otherwise.
Reviewer_HemzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies constrained long-horizon navigation with ordered visits, scoped avoidance and distinct-entity counts, and soft preferences. ReCoNav represents instructions as contracts grounded in an affordance scene graph. Its Determination Engine uses local rules and global route queries to resolve target bindings, verify commitments, and repair interpretations while recomputing dependent conclusions. Evaluation uses 192 constructed tasks across nine scenes, primarily with ground-truth scene graphs. Comparisons against direct contract generation and feedback-based planning, together with component ablations across four backbones, show substantial improvements in complete instruction satisfaction.

Critical strengths
  1. The task formulation is a useful contribution in its own right. ReCoNav makes explicit a difficult interaction: the intended target may depend on whether a route can satisfy ordered visits, scoped avoidance, counts, and preferences. Constructing a benchmark for this interaction is worthwhile even when existing VLN systems were not designed to handle all of these requirements. The distinction between feasible, certified infeasible, and unknown solver outcomes is also careful.
  2. The ablations give concrete evidence that global route reasoning helps target selection. Forced-Early retains local grounding, repair, and the shared unresolved-binding fallback. With GPT, adding global queries changes resolving-task successes from 28/89 to 89/89 while leaving the 103 controls unchanged. On Hard44, the advantage over Direct-Feedback persists without the additional wall-time cutoff. These are meaningful results within the provided scene-graph setting.
Critical weaknesses
  1. The description of the main engine comparison leaves an important ambiguity. Section 4.2 and Appendix C.4 establish that Direct and Direct-Feedback share the ASG, backbone, and contract solver. They do not make clear whether Direct-Feedback can retain candidate domains, revise target bindings after infeasibility, or use diagnostics comparable to ReCoNav's evidence-guided repair. Appendix C.3 supplies repair and solver limits, but not a per-method account of binding queries and retries. I therefore cannot tell how strong the direct feedback-based alternative is. Forced-Early supports global target reasoning, and No Verify/Repair tests the added verification and repair stage as a bundle. These are useful controls. They leave less certainty about the incremental benefit of dependency tracking and localized repair over a feedback-based alternative with comparable binding revision and diagnostics.
  2. The benchmark establishes performance within the contract language, with limited evidence about requirements specified independently of that language. Appendix C.1 generates natural-language instructions from validated symbolic tasks across nine scenes, and the quantitative experiments use ground-truth ASGs. This is a sensible controlled test of the proposed task, not a flaw by itself. However, it provides limited evidence about coverage of naturally supplied instructions or imperfect scene grounding. External baseline gaps also need interpretation: their native task models may not express every evaluated operator. I would treat those results as comparisons of complete capabilities rather than clean estimates of reasoning quality.
Questions for authors
  1. Can Direct-Feedback revise entity bindings and search alternative candidates after an infeasible result? Please provide its output schema, feedback contents, and one execution trace, together with the applicable repair and solver-call limits. These details may resolve much of the uncertainty without new experiments.
  2. No Verify/Repair removes verification, evidence-guided repair, and the resulting recomputation together. Can the existing results or execution traces clarify the role of dependency tracking and localized repair within that combined benefit? I am asking for the interpretation supported by the existing evidence, rather than a separate ablation of every component.
  3. For the external comparisons, can you identify supported contract operators and distinguish unsupported requirements from failures on supported ones? A breakdown on a supported subset would help where available; it would supplement, rather than replace, evaluation on the new full task.
4 comments
AuthorsOpenReview ↗

Overall Response to Reviewer Hemz

Thank you for recognizing the contributions of our benchmark and formulation, and for highlighting where the benchmark and baseline comparisons need further clarification. We will incorporate the clarifications into the revised paper and appendix. The anonymous repository provides the prompts and output schemas for Direct and Direct-Feedback, along with benchmark construction and validation tools. The project page includes task examples and real-robot demonstration videos.

W1

  1. Clarification of Direct-Feedback. Direct-Feedback can revise contracts and entity bindings and receives the information needed for repair. Q1 provides its output schema, feedback contents, a successful binding revision, and per-method query and retry limits.

  2. Dependency tracking and repair. Direct-Feedback receives error feedback, while ReCoNav additionally highlights evidence from connected derivations and tracks dependent conclusions for invalidation and recomputation. Q2 provides a recorded execution illustrating both roles. Verification and repair form one component of ReCoNav. Our ablation evaluates their combined contribution within the system, rather than comparing the effectiveness of different repair strategies. How to provide evidence that makes VLM repair more effective is an interesting direction for future research.

W2

  1. Benchmark construction and validation. Our goal is to make instruction interpretation unambiguous for evaluation. We first generate scene-grounded instruction contracts with feasible routes and uniquely resolved targets. Gemini 3.7 Flash or GPT-5.6 Sol then generates natural-language instructions from these contracts. GPT-5.6 Sol reviews every instruction against its symbolic requirements, checking omissions, added requirements, scope errors, and ambiguous wording. Before final acceptance, 63/192 instructions (32.81%) were revised or clarified and reviewed again. For example, “the book in the living room with a carpet nearby” was clarified as “the book that is in the living room and has a carpet nearby,” making the modifier attachment explicit. We also manually inspected the tasks.

  2. ASGs. We use ground-truth ASGs to isolate task reasoning from scene reconstruction errors. Developing accurate scene reconstruction is beyond the scope of this work. Our real-robot demonstration uses an ASG built from registered RGB-D using MaskClustering [1], mask-conditioned VLM recognition following OpenVoxel [2], as described in Section 3.2 and Appendix B.5. Robustness to imperfect scene grounding remains an important direction, as discussed in Section 5 through online mapping and incremental ASG construction. We are also interested in extending rules and solver-based verification to ASG construction.

  3. External baseline comparisons. Our benchmark exposes their limitations in propagating scoped hard and soft constraints across instruction interpretation, scene grounding, and complete-route planning. Q3 provides the corresponding analysis, supported-subset results, and execution examples. We agree that these results primarily reflect the complete capabilities of existing methods in this task setting. Controlled comparisons with Direct-ID-Sequence, Direct, Direct-Feedback, and component ablations provide evidence for the contributions of the instruction contract and the ReCoNav system.

[1] Yan et al. MaskClustering: View Consensus based Mask Graph Clustering for Open-Vocabulary 3D Instance Segmentation. CVPR 2024.

[2] Huang et al. OpenVoxel: Training-Free Grouping and Captioning Voxels for Open-Vocabulary 3D Scene Understanding. CVPR 2026.

AuthorsOpenReview ↗

Response to Q1

Q1. Direct-Feedback specification and execution

Yes. Direct-Feedback can revise entity bindings and try alternative targets after an infeasible result.

Output schema. Direct and Direct-Feedback use the same output schema, summarized below using type notation:

{
  status: "resolved" | "unresolved",
  reason: string,
  semantic_contract: InstructionContract | null,
  bindings: [{
    path: string,
    asg_kind: "object" | "region" | "portal" | "level",
    asg_label: string,
    grounded_ids: integer[]
  }]
}

semantic_contract represents visits, orders, scoped constraints, and preferences. Each binding identifies a referent by its contract path and assigns ASG IDs. For example, this actual entry binds the first intermediate visit to bedroom R7:

{"path": "$.route.via_events[0].target", "asg_kind": "region", "asg_label": "bedroom", "grounded_ids": [7]}

Visit targets use one ID, while AVOID and COUNT referents can denote sets. ReCoNav uses exactly the same InstructionContract schema. Its VLM outputs ASG kind/label correspondences without entity IDs. After grounding and binding resolution, ReCoNav uses the same grounded-contract representation and route-solver interface as Direct.

Feedback. Each revision receives the instruction, start pose, ASG, previous complete output, and diagnostics containing the failure stage, reason, and detail, plus the solver status and reason when available. Diagnostics cover schema, semantic-contract, grounding, contract-to-solver translation, and solver failures. The model returns a complete revised contract and bindings.

One Direct-Feedback execution: task 00824_T3_0006. The instruction is:

Go directly to the bedroom without entering the hallway, then go directly to the bathroom cabinet nearest to the tissue box.

Initial structured output from VLM:

{
  ...
  "bindings": [
    {
      "path": "$.route.via_events[0].target",
      "asg_kind": "region",
      "asg_label": "bedroom",
      "grounded_ids": [7]
    },
    ...
  ]
}

From the start in R2, reaching bedroom R7 requires entering hallway R8 before the bedroom visit, violating the scoped avoidance. The solver returns UNSAT. The revision receives the instruction, original start pose and heading, ASG, previous output, and this mechanical_feedback:

{
  "failure": {
    "stage": "route",
    "reason": "UNSAT",
    "detail": "complete component/event relaxation excludes every hard-feasible route"
  },
  "solver_status": "UNSAT",
  "solver_reason": "complete component/event relaxation excludes every hard-feasible route"
}

The VLM returns a complete revised output. The updated entry in bindings is:

{
  "path": "$.route.via_events[0].target",
  "asg_kind": "region",
  "asg_label": "bedroom",
  "grounded_ids": [
    12
  ]
}

The complete revised output follows the same schema shown above. In this example, the bedroom binding changes from R7 to R12, while the semantic contract and all other binding entries remain unchanged.

Second solver result:

{
  "status": "SAT",
  "query_outcome": "SAT_WITNESS",
  "predicted_contract_replayed": true
}

The route visits R12 before entering R8 and then reaches cabinet 384.

Limits. Both Direct-Feedback and ReCoNav allow at most two LLM revisions after the initial prediction. Both use the same solver configuration: 90 seconds per call and 360 seconds of cumulative solver time. Direct-Feedback makes at most one solver query per attempt, hence at most three queries in total, so the 360-second budget does not further constrain it. ReCoNav can make multiple binding queries, with their solver time accumulated across initial planning and repair rounds. The example uses one revision and two solver queries.

AuthorsOpenReview ↗

Response to Q2

Q2. Dependency tracking and localized repair

We collect repair evidence from connected derivations (Appendix B.2, Eq. (11)) and recompute dependent conclusions after revision (Section 3.3.3, Eq. (8)). Figure 3 illustrates order repair followed by target determination. Below is a detailed runtime trace.

One ReCoNav execution: task 00829_T5_0030. The instruction is:

Go directly to the floor lamp nearest to the switch, then head directly to the cosmetics farthest from the shower tap. From there, go directly to the table lamp, preferably passing through exactly one portal between the cosmetics farthest from the shower tap and the table lamp, and finally go directly to the bathtub.

Initial contract from VLM (constraints.count[0]):

{
  "target": {
    "head_text": "portal",
    "qualifiers": [{
      "relation": "between",
      "references": [
        {
          "head_text": "the cosmetics",
          "qualifiers": [{
            "relation": "farthest_from",
            "references": [{"head_text": "the shower tap", ...}],
            ...
          }],
          ...
        },
        {"head_text": "the table lamp", ...}
      ],
      ...
    }],
    ...
  },
  "comparison": "exactly",
  "value": 1,
  "preference_source_text": "preferably",
  ...
}

In the instruction, “between the cosmetics farthest from the shower tap and the table lamp” specifies the COUNT scope, from the cosmetics visit to the table-lamp visit. The VLM incorrectly also attaches this phrase to the portal as a spatial between qualifier.

The portal's spatial BETWEEN rule implies that its reference “the cosmetics” must be a region. The FARTHEST_FROM rule implies that its owner, the same “the cosmetics” referent, must be an object. From these type requirements, propagation derives an empty set of admissible kinds for the COUNT target:

{
  "key": "grounding.6.possible_kinds",
  "subject": "$.constraints.count[0].target",
  "value": [],
  "rule": "FIXPOINT_SIGNATURE_PROPAGATION"
}

The type-consistency rule requires a grounded referent to have exactly one of four types: object, region, portal, or level. Requiring the same referent to be both a region and an object therefore yields a contradiction. Evidence from connected derivations links this conflict to the two rule-based type requirements and to their premises in the VLM's initial contract shown above. The repair request highlights the requirements, their originating paths, and the implicated interpretation and source phrase (selected fields):

{
  "deterministic_error": [{
    "code": "INCONSISTENT_KIND_REQUIREMENT",
    "assertion": "authoritative kind requirements have a non-empty intersection",
    "expected": "at least one ASG kind",
    "observed": "$.constraints.count[0].target.qualifiers[0]: BETWEEN reference is one of region; $.constraints.count[0].target.qualifiers[0].references[0].qualifiers[0]: FARTHEST_FROM owner is one of object"
  }],
  "readable_error_location": [{
    "path": "$.constraints.count[0].target.qualifiers[0].references[0]",
    "source_text": "the cosmetics farthest from the shower tap",
    "semantic_content": {
      "head_text": "the cosmetics",
      "qualifiers": [{
        "relation": "farthest_from",
        "references": [{"head_text": "the shower tap"}]
      }]
    }
  }]
}

Here, observed records both derived type requirements and their source paths, while readable_error_location provides the relevant interpretation and original phrase. These rule reasons and implicated semantic fields form the localized projection of the connected evidence. They are supplied to the VLM together with the full instruction, current contract (the initial contract in this round), label grounding, and complete legal ASG label vocabulary.

Using the instruction and this evidence, the VLM removes the erroneous spatial between qualifier.

{
  "kind": "nominal",
  "source_text": "portal",
  "head_text": "portal",
  "qualifiers": null
}

The exactly-one comparison, preference marker, temporal scope, visits, and orders remain unchanged. With the revised premise, the engine recomputes type propagation and label grounding. The COUNT target now has kind portal and is grounded to the ASG label portal:

[
  {
    "key": "grounding.6.possible_kinds",
    "subject": "$.constraints.count[0].target",
    "value": ["portal"],
    "rule": "FIXPOINT_SIGNATURE_PROPAGATION"
  },
  {
    "key": "grounding.6.canonical_binding",
    "subject": "$.constraints.count[0].target",
    "value": {
      "head_text": "portal",
      "asg_kind": "portal",
      "asg_label": "portal"
    },
    "rule": "CANONICAL_LEXICAL_EQUALITY"
  }
]

Instance grounding and planning then produce a verified waypoint route visiting the floor lamp, cosmetics, table lamp, and bathtub, with exactly one portal crossed between the cosmetics and table-lamp visits.

AuthorsOpenReview ↗

Response to Q3

Q3. External baseline capabilities and failure modes

Task support has no clear boundary for LLM/VLM-based methods, so we discuss their observed behavior and failure modes. We define supported subsets only for LTL-based pipelines using their implemented operators and grounding predicates.

Instruction following: NavGPT, CA-Nav, GC-VLN, SNav, and DualVLN. These methods navigate from observations and history without a pre-explored global map. Our instructions leave the route open, requiring agents to locate targets and satisfy the complete instruction. In the full benchmark, successes are concentrated in tasks with nearby targets, no intermediate visits, and single-floor feasible routes. Even these tasks can fail through target identification, constraint violations, or exhausted execution budgets. Failures also occur without AVOID, COUNT, or preferences. For “Go to the decorative plant that is in the toilet room and has a shelf nearby” (00873_T1_0001), a feasible route is only 2.87m long. DualVLN stops without reaching the specified target, SNav exhausts its action budget, and NavGPT times out. These methods achieve very low full-instruction satisfaction when applied directly to this benchmark.

Methods using maps or ASGs: MapGPT, NavGPT+ASG, and GC-VLN+ASG. MapGPT builds an online topological map of observed viewpoints, their images, connections, action options, and visit history. An entity-level ASG cannot directly replace this map. It achieves the highest native-interface Full IS, 13/178 (7.30%). However, its viewpoint map records connectivity without explicitly checking scoped route constraints. Failures include scoped constraint violations, not reaching the specified target, and exhausting action or time budgets.

NavGPT+ASG prompts include ASG scene facts and the positions of the agent and available next viewpoints. Selected moves follow the ASG navigation graph. On uncapped Hard44, Full IS increases from 2/44 to 13/44. For example, “Go to the bedroom, entering at most one area from the start until you reach it” (00824_T4_0003), it identifies the direct connection between the living room and bedroom through portal 8 and succeeds, whereas native NavGPT mistakes its current room for the bedroom and stops, failing both the target and count requirements. Most failed runs reach the iteration limit (26/31). In the main comparison, 183/192 runs time out.

GC-VLN+ASG uses the provided ASG to supply scene entities and a geometric map, while retaining GC-VLN’s instruction parser and waypoint planner. Its predicted waypoints are executed on the ASG navigation graph. Hard44 Full IS increases from 0/44 to 3/44, including the bedroom task above. However, its current-floor 2D map and geometric constraints do not provide whole-route COUNT or preference planning. Global scene information alone does not ensure complete-route constraint satisfaction.

LTL-based methods: Lang2LTL-2+ASG and LIMP+ASG. Their released pipelines lack distinct-entity COUNT and soft preferences, required by 98/192 tasks. To ground instruction referents in the ASG, Lang2LTL-2 retrieves entities using embeddings of their labels and descriptions and checks spatial predicates using their coordinates. LIMP matches referents to ASG entity labels and evaluates its 3D spatial predicates using the entity coordinates. The grounding libraries also lack the region/level membership and nearest/farthest predicates used by our benchmark. Portal visit conditions check arrival or proximity, whereas our benchmark requires crossing from one side to the other. LIMP represents rooms as landmarks at their centers, so avoiding a room landmark can still allow a route through other parts of that room.

Excluding the unsupported requirements above leaves 12 tasks for Lang2LTL-2 and 6 for LIMP, with Full IS of 3/12 and 2/6, respectively. All successful runs in these subsets are single-target tasks without additional route constraints. The failures show errors in both translation and grounding. For “Go to the sink without entering the hallway” (00824_T3_0003), Lang2LTL-2 generates a formula that requires visiting the hallway. For “Go to the towel bar, avoiding the bedroom” (00829_T3_0017), Lang2LTL-2 grounds bedroom to a floor object inside that room (object_1) rather than the bedroom region (region_2).

These methods likewise do not reliably propagate route constraints to earlier grounding decisions. NavGPT+ASG achieves higher Full IS on Hard44, while the released LTL-based pipelines are limited by unsupported constraint operators and spatial relations.

Comments on the paper

1 comment

We thank the reviewers for their feedback and suggestions. We appreciate Hemz’s recognition of the contributions of our benchmark and formulation, BLWh’s recognition of the importance of our research problem, and 4z11’s suggestions to discuss related formal-planning work, including CaStL and LLM+P.

Changes in the revised paper are marked in blue. The anonymous repository provides code, benchmark data, construction and validation tools, prompts, and output schemas. The project page provides task examples and real-robot demonstration videos.

We summarize the main clarifications, evidence, and paper revisions below.

  1. Research problem and contributions. We study how scoped hard and soft constraints propagate across instruction interpretation, grounding, and complete-route planning in constrained long-horizon VLN. Figure 1 illustrates one consequence: route constraints and preferences can determine the target after semantic and spatial matching. Our contributions are a 192-task, nine-scene benchmark exposing gaps in existing methods; an instruction contract formulating these requirements as a problem solvable by formal solvers; and ReCoNav, which uses scene and route evidence to derive, verify, and revise judgments. The contribution concerns the problem formulation and use of formal evidence across stages. We agree that existing languages such as PDDL can encode the resulting problem and do not claim novelty in the underlying solver.

  2. Benchmark validity and evaluation scope. Tasks are constructed with feasible routes and uniquely resolved targets, then verbalized using Gemini 3.7 Flash or GPT-5.6 Sol. GPT-5.6 Sol reviews every instruction against its symbolic requirements; 63/192 instructions were revised or clarified and reviewed again before finalizing the benchmark. We also manually inspected tasks. Final scoring uses a separate evaluator to check actual routes against benchmark annotations, which are withheld from the planner. We use ground-truth scene graphs in the experiments to isolate task reasoning from scene reconstruction errors.

  3. Baseline comparisons and findings. Existing instruction-following VLN methods test applicability to our benchmark; their low Full IS reveals limitations on these constrained tasks. MapGPT and +ASG adaptations examine the value of broader scene information, including approaches that combine it with formal planning. On Hard44 without the added wall-time limit, ASG access raises NavGPT from 4.55% to 29.55% Full IS: global context helps but does not ensure full satisfaction. Direct and Direct-Feedback test a straightforward application of language-to-formal-specification planning: the VLM predicts a grounded contract for the solver, with Direct-Feedback also revising contracts and bindings using failure feedback. They share ReCoNav's ASG, backbone, contract representation, and solver. Their 20.45% and 38.64% Full IS, versus 81.82% for ReCoNav on Hard44, show that a formal contract and solver alone are insufficient; how formal evidence informs decisions across navigation stages also matters.

  4. Rules and types of constraints. Rules encode relations required by scene and task definitions and are predefined in the implementation. They are distinct from the semantic judgments proposed by VLMs. Our insight is that “uncertainty in individual judgments does not preclude deterministic relations between them.” ReCoNav uses these relations to derive judgments, verify their consequences, and provide evidence for repair. The revised paper adds the core rule table in Appendix B.1, Table 7. We also distinguish spatial qualifiers from route constraints: spatial qualifiers such as IN and NEAR restrict candidate entities, whereas ordered visits, scoped AVOID and distinct-entity COUNT constraints, and preferences govern complete routes, including encounters between requested visits. These route requirements can further determine target identities after semantic and spatial matching.

  5. Role of verification and repair. Verification and repair form one component of ReCoNav, one of our three contributions alongside the benchmark and instruction contract. ReCoNav highlights evidence from connected derivations to guide VLM repair, then recomputes dependent conclusions after revision. Across 765 task–backbone runs completed by both No Verify/Repair and ReCoNav, this stage corrects 27 of 71 previously incorrect outcomes (38.0%), retains all 694 correct outcomes, and introduces no regressions (Appendix C.4). These results support the combined benefit of verification, repair, and recomputation within the system. How to provide evidence that makes VLM repair more effective is an interesting question, but a systematic comparison of repair strategies is beyond the scope of this work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.