acceptodds
Under review as a conference paper at ICLR 2027

World Model-Guided Adaptive Lookahead for Dynamic Multi-Objective Neural Routing Problems

Abstract

We introduce a world-model-guided neural solver for dynamic multi-objective routing problems, where graphs change during route execution. Although neural combinatorial optimization (NCO) models can re-encode graphs after changes, training only on static instances may limit decision quality in evolving environments. Moreover, direct node selection may not fully account for the impact of alternative choices on final route quality. We establish a standardized training and evaluation framework that incorporates five event families into partially executed trajectories: node addition, node removal, attribute drift, addition with drift, and removal with drift. This enables dynamic adaptation without modifying the NCO architecture. We further propose world-model-guided adaptive lookahead, where a learned controller selectively evaluates Top- route completions at decision points that benefit from additional computation, refining node selections without predicting future events. A cost-to-go signal for each node further improves credit assignment in dynamic training. Experiments on MOTSP and MOCVRP across diverse dynamic profiles and problem sizes demonstrate improved solution quality, efficient inference, and strong cross-scale and large-scale generalization. Adaptive lookahead also improves frozen NCO policies on static instances.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Dynamic Multi-Objective Optimization, Routing Problems, World Models, Adaptive Lookahead, Credit Assignment

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_Umx5OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a framework for dynamic multi-objective routing that uses a learned controller to selectively branch out at each step to roll out to the end of the route to find candidate routes. The framework is evaluated on multi-objective traveling salesman and capacitated vehicle routing tasks.

Critical strengths

Selectively allocating compute via a learned controller is a useful design for expanding candidate search while maintaining inference efficiency

Critical weaknesses
  • The world model operates on the fixed graph GtG_t and does not predict future events, making the claim about the world model an overstatement.
  • The generality and efficiency of the framework are insufficiently demonstrated. Only one base solver is considered in the manuscript. See questions below.
Questions for authors
  • The authors claim that the framework can "extend to other autoregressive NCO solvers". Could the author provide results using at least one additional base solver? This could further solidify the claim of the proposed framework's effectiveness and generality.
  • The runtime of WECA-WM can be significantly higher than that of Static WECA. Could the author provide a more systematic quality-computation analysis with the additional base solvers?
6 comments
AuthorsOpenReview ↗

Response to R3-CW1: Clarification of the World Model Formulation

We thank the reviewer for highlighting this concern. We agree that our World Model does not learn environmental transition dynamics or predict future exogenous events. However, it explicitly models the downstream consequences of candidate decisions to guide current action selection. We clarify this distinction below.

1. Regarding the World Model formulation. Our approach adopts a task-specific, decision-oriented World Model, motivated by the use of imagined future outcomes to guide present decisions (Ha & Schmidhuber, 2018; Hafner et al., 2019). Rather than predicting environmental changes, our formulation focuses on action-conditioned solution consequences, which are directly relevant to neural combinatorial optimization.

2. Regarding the fixed-graph rollout. Although the observed graph remains fixed during imagination, the routing state evolves as candidate routes are constructed, including visited nodes, feasibility masks, and remaining capacity. Specifically, the frozen NCO policy completes the route conditioned on each candidate action, and the resulting terminal objective estimates its downstream consequence (Eq. 5). These imagined outcomes guide the current decision, while subsequent environmental changes are incorporated through graph updates and replanning. Thus, our formulation provides decision-level foresight rather than environmental-event prediction.

3. Regarding the potential overstatement. We acknowledge that our formulation is narrower than conventional learned-dynamics world models. We will explicitly clarify its task-specific, rollout-based scope, distinguish it from environmental dynamics prediction, and emphasize that the primary methodological novelty lies in the learned controller that adaptively determines when and how extensively to perform lookahead.

References

[1] Ha, D., & Schmidhuber, J. (2018). World Models. Advances in Neural Information Processing Systems (NeurIPS). https://doi.org/10.5281/zenodo.1207631

[2] Hafner, D., Lillicrap, T., Ba, J., & Norouzi, M. (2019). Dream to Control: Learning Behaviors by Latent Imagination. International Conference on Learning Representations (ICLR).

AuthorsOpenReview ↗

Response to R3-CW2: Generality and Efficiency

We thank the reviewer for this important observation. We have conducted additional experiments to address both the generality and computational efficiency of our framework.

Generality (Q1): We extended WECA-WM to a second autoregressive NCO backbone, CNH, and evaluated it on Bi-TSP and Bi-CVRP across different problem sizes and dynamic settings. The results demonstrate that our framework is not limited to the original WECA solver. Please see our response to R3-Q1 for detailed results.

Efficiency (Q2): We added systematic quality–runtime comparisons against Fixed-K4, uncertainty-triggered rollout (UT), and SGBS, together with HV–runtime Pareto plots. These results demonstrate the computational advantages of adaptive allocation, particularly on larger instances. Please see our response to R3-Q2 for detailed comparisons.

Together, these additional experiments provide evidence of both backbone generality and computational effectiveness beyond the original experiments.

AuthorsOpenReview ↗

R3-Q1: Generality Across Autoregressive NCO Solvers

We thank the reviewer for asking whether our framework can generalize beyond the original WECA backbone. Yes. We have conducted additional experiments using Conditional Neural Heuristic (CNH; Fan et al., 2025) as a second autoregressive NCO backbone. The results demonstrate consistent improvements across both dynamic and static environments, supporting the transferability of our framework across different NCO architectures.

1. Integration with an additional NCO backbone.

We integrated our framework with CNH without modifying its original encoder–decoder architecture. Specifically:

  • Candidate generation: We construct candidate actions from CNH's feasible-action probability distribution.

  • Lookahead evaluation: The frozen CNH policy completes each candidate into a full route under the currently observed graph.

  • Adaptive allocation: The learned controller determines whether to invoke lookahead and how many candidates to evaluate.

  • Online execution: Only the selected next action is executed. Subsequent environmental events are observed and incorporated before the next decision.

This integration demonstrates that our framework is not restricted to WECA and can operate with another autoregressive NCO solver through its action-distribution interface.

2. Results across dynamic and static environments.

We evaluated both backbones on Bi-TSP and Bi-CVRP with 20, 50, and 100 nodes. Dynamic experiments cover D1–D3, while static experiments evaluate the framework without environmental events.

The following table summarizes the results. Dynamic HV values are averaged over D1–D3. Each entry reports baseline → WM, with the absolute HV improvement in parentheses.

ProblemDynamic CNH → CNH-WMStatic CNH → CNH-WM
Bi-TSP200.7073 → 0.7173 (+0.0100)0.6270 → 0.6275 (+0.0005)
Bi-TSP500.7921 → 0.8056 (+0.0134)0.6387 → 0.6410 (+0.0023)
Bi-TSP1000.8039 → 0.8211 (+0.0173)0.7019 → 0.7055 (+0.0036)
Bi-CVRP200.4432 → 0.4497 (+0.0065)0.4287 → 0.4301 (+0.0014)
Bi-CVRP500.4493 → 0.4595 (+0.0103)0.4087 → 0.4100 (+0.0013)
Bi-CVRP1000.4741 → 0.4813 (+0.0072)0.4065 → 0.4077 (+0.0012)

The results show that:

  • Dynamic environments: CNH-WM improves over CNH in all 18 task–size–profile configurations, with absolute HV gains ranging from 0.0018 to 0.0234.

  • Static environments: CNH-WM improves over CNH in all six configurations. Importantly, WECA-WM also improves over WECA in all six configurations.

  • Cross-scale consistency: Improvements are observed across both routing tasks and all three problem sizes, rather than being limited to a particular problem scale or backbone.

Notably, the static results provide additional evidence that the benefit of lookahead does not depend on environmental changes. Even when no events occur, evaluating alternative route completions can improve current action selection.

3. Implications for generality.

These additional experiments provide empirical evidence that the proposed adaptive lookahead mechanism is transferable across two autoregressive NCO backbones, WECA and CNH. The consistent improvements across two routing tasks, three problem sizes, and both dynamic and static environments support the generality of the proposed framework.

We have added the CNH integration details and the complete dynamic and static experimental results to Appendix K (Tables 10 and 11) of the revised manuscript.

References

[1] Fan, M., Wu, Y., Cao, Z., Song, W., Sartoretti, G., Liu, H., & Wu, G. (2025). Conditional Neural Heuristic for Multiobjective Vehicle Routing Problems. IEEE Transactions on Neural Networks and Learning Systems, 36(3), 4677–4689. https://doi.org/10.1109/TNNLS.2024.3371706

Reviewer_BLFGOpenReview ↗
Rating
1(−1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies dynamic multi-objective routing with neural combinatorial optimization (NCO), where the graph can change during route execution. It introduces (i) a training and evaluation protocol that injects five event families (add, delete, attribute drift, and two compound variants) into partially executed trajectories without changing the NCO architecture, (ii) a “world-model-guided adaptive lookahead” that refines next-node decisions by selectively rolling out a frozen base policy to the end of the route under the current graph, and (iii) a node-level cost-to-go signal to improve credit assignment during dynamic training. On bi-objective TSP and CVRP across several dynamic profiles and scales, the approach improves hypervolume over evolutionary and neural baselines and also boosts frozen policies on static instances via test-time lookahead.

Critical strengths
  1. Dynamic multi-objective routing is a timely, important setting where rapid re-planning and consistent Pareto approximation are essential.

  2. Introducing selective, learned test-time lookahead to frozen NCO policies is broadly useful and orthogonal to architectural advances; the improvements on both dynamic and static cases are of practical interest to the NCO community.

Critical weaknesses
  1. The “world model” does not model environment transitions; it is better described as selective rollout or test-time search under a fixed (current) graph. This limits foresight about forthcoming events and may be suboptimal in scenarios where anticipating future arrivals/cancellations matters.

  2. Lookahead evaluates full route completions for Top-K next-node candidates, which can be computationally heavy; the controller’s action set is small (K∈{0,2,3,4}), and the paper does not analyze deeper search vs. cost trade-offs.

  3. The dynamic setting is Euclidean with iid event triggering per step; this omits time windows, travel-time variability, or operational constraints that typically interact with dynamics.

  4. Missing comparisons to closely related inference-time search for NCO (e.g., simulation-guided beam search, rollout beam search, and other rollout/test-time adaptation schemes). Since the proposed benefit is selective test-time refinement, these are important baselines.

  5. Limited discussion and no comparison to resource/budget allocation for test-time search (e.g., direction-focused allocation in LLM test-time scaling) that is methodologically related.

Questions for authors

see weakness

6 comments
AuthorsOpenReview ↗

Response to R2-CW1: World Model Formulation and Future Event Prediction

We thank the reviewer for this important observation. We agree that our World Model does not predict future environmental events. Our goal is to model the consequences of candidate routing decisions under the currently observed graph, rather than to learn exogenous event dynamics. We clarify the formulation and its limitations below.

1. Regarding the World Model formulation. Our approach adopts a task-specific, decision-oriented World Model, motivated by the use of imagined future outcomes to guide current decisions (Ha & Schmidhuber, 2018; Hafner et al., 2019). Specifically, it uses the frozen NCO policy to simulate candidate route completions and estimate their terminal objectives (Eq. 5). Unlike learned-dynamics world models, our formulation focuses on action-conditioned solution consequences, without claiming to predict environmental transitions.

2. Regarding the lack of foresight about future arrivals and cancellations. This is a deliberate design choice for reactive, observation-driven dynamic routing (Pillac et al., 2013). At each decision step, the solver uses only currently available information. Future events are not assumed to be absent: when an event occurs, the graph is updated and re-encoded, and the next decision is made using the newly observed state (Eq. 1). Moreover, only the next action is committed; imagined route completions are discarded. This avoids committing to an entire route based on unobserved future events.

3. Regarding potential suboptimality without event prediction. We acknowledge that accurate forecasts of future arrivals or cancellations could further improve decisions. Nevertheless, our results demonstrate the effectiveness of the proposed approach without such forecasts. In Appendix G, learned gating with K = 4 improves HV in 13 of 18 dynamic settings, matches the baseline in four, and decreases it in only one. In contrast, every-step Top-2 rollout decreases HV in six of nine dynamic KroAB settings. These results support the value of selective lookahead under changing environments.

References

[1] Ha, D., & Schmidhuber, J. (2018). World Models. Advances in Neural Information Processing Systems (NeurIPS). https://doi.org/10.5281/zenodo.1207631

[2] Hafner, D., Lillicrap, T., Ba, J., & Norouzi, M. (2019). Dream to Control: Learning Behaviors by Latent Imagination. International Conference on Learning Representations (ICLR).

[3] Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A Review of Dynamic Vehicle Routing Problems. European Journal of Operational Research, 225(1), 1–11. https://doi.org/10.1016/j.ejor.2012.08.015

AuthorsOpenReview ↗

Response to R2-CW2: Lookahead Complexity and Adaptive Search Width

Response to R2-CW2: Lookahead Complexity and Adaptive Search Width

We thank the reviewer for highlighting the computational cost of full-route completions and the limited controller action space. Our framework addresses this cost through selective computation: it learns when to activate lookahead and how many candidates to evaluate, rather than performing full-route rollouts at every decision step.

1. Why do we use K∈{0,2,3,4}K\in\{0,2,3,4\}?

The action space provides a practical balance between search flexibility and computational cost:

  • K = 0 (SKIP): Directly follows the base policy without additional rollout computation.
  • K = 2, 3, 4: Evaluates the corresponding number of Top-K candidate actions through full-route completion.

Importantly, K controls the branching width, not the rollout horizon. Each candidate is completed to the end of the route using the frozen policy. Only the selected next action is executed; the imagined suffix is discarded. The solver replans after subsequent environmental changes. The bounded action space is a practical design choice, not a claim of optimality.

2. What is the empirical quality–computation trade-off?

We conducted additional comparisons against Fixed-K4 rollout and uncertainty-triggered Top-K rollout (UT) across 24 dynamic configurations covering Bi-TSP and Bi-CVRP.

  • Against Fixed-K4: WECA-WM achieves higher HV in 15/24 configurations (one tie).
  • Against UT: WECA-WM achieves higher HV in 20/24 configurations.
  • At size 100: WECA-WM requires less inference time than both baselines in all eight configurations, while achieving higher HV in 7/8 cases against Fixed-K4 and 6/8 against UT.

Representative results (HV ↑ / Time ↓):

SettingWECA-WMFixed-K4UT
Bi-TSP100-D20.8112 / 1.7m0.7961 / 25m0.8028 / 9.4m
Bi-CVRP100-D10.4664 / 6.0m0.4631 / 25m0.4631 / 25m
Bi-CVRP100-D40.4137 / 33m0.4123 / 3.6h0.4123 / 3.5h

The following Pareto plots further illustrate the quality–runtime trade-off across D1–D4.

Figure 1. Bi-TSP: Mean HV versus mean inference time.

Bi-TSP Pareto comparison

Figure 2. Bi-CVRP: Mean HV versus mean inference time.

Bi-CVRP Pareto comparison

These results show that evaluating more candidates at every decision does not necessarily produce better solutions. Adaptive allocation achieves a more favorable quality–runtime trade-off, particularly on larger instances.

3. Does the current action space cover all search–cost trade-offs?

Our current implementation uses full-route completion with a bounded candidate width. We do not claim to have exhaustively explored larger K values or alternative rollout horizons. Nevertheless, the additional experiments demonstrate that adaptive selection within the current action space provides an effective quality–computation trade-off.

4. Additional results in the revised manuscript.

We have added the complete experimental results and analysis to Appendix I of the revised PDF:

  • Tables 8–9: Complete per-profile HV and runtime comparisons across D1–D4 for Bi-TSP and Bi-CVRP, respectively.
  • Figures 9–10: Mean HV–runtime Pareto comparisons across all three problem sizes.

These results provide the full experimental evidence supporting the effectiveness of adaptive search-width allocation.

In summary, our method maintains full-route evaluation while controlling its computational cost through learned branching-width selection.

AuthorsOpenReview ↗

Response to R2-CW3: Applicability and Generalization of Dynamic Routing Scenarios

We thank the reviewer for raising this concern. While our benchmarks use Euclidean graphs and i.i.d. event triggering, the proposed framework is designed to address general online routing decisions under evolving graph information. We clarify its applicability and generalization below.

1. Regarding the practical relevance of our dynamic scenarios. Our framework captures several fundamental changes encountered in dynamic routing, including request arrivals, cancellations, attribute variations, and their compound events, consistent with established dynamic routing formulations (Pillac et al., 2013; Ojeda Rios et al., 2021). Importantly, these changes occur during route execution, where completed decisions cannot be reversed. The solver must adapt to updated service obligations and feasibility constraints, including vehicle capacity and changing customer demands in MOCVRP. Thus, our setting captures essential online routing challenges beyond static graph optimization.

2. Regarding the generality of the event assumptions. The i.i.d. triggering mechanism is used to generate controlled and reproducible evaluation scenarios, rather than being a requirement of our solution framework. Our solver operates on the currently observed graph and updates its decisions whenever changes occur (Eq. 1). Its rollout mechanism and allocation controller do not require a predefined event-triggering distribution during inference. Therefore, the framework is not structurally restricted to i.i.d. event arrivals, although performance under correlated event processes remains to be evaluated.

3. Regarding empirical generalization. We evaluate the framework across five event families, three dynamic intensity profiles (D1–D3), two routing problems (MOTSP and MOCVRP), and multiple problem scales. Beyond training sizes of 20–100 nodes, we evaluate out-of-distribution sizes of 150 and 200 nodes. Furthermore, on the KroAB and XML benchmark instances with injected dynamic events, our method achieves the highest HV across all 18 size–profile configurations (Figures 6–7). These results demonstrate consistent performance across different dynamic conditions, routing tasks, and instance scales.

References

[1] Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A Review of Dynamic Vehicle Routing Problems. European Journal of Operational Research, 225(1), 1–11. https://doi.org/10.1016/j.ejor.2012.08.015

[2] Ojeda Rios, B. H., Xavier, E. C., Miyazawa, F. K., Amorim, P., Curcio, E., & Santos, M. J. (2021). Recent Dynamic Vehicle Routing Problems: A Survey. Computers & Industrial Engineering, 160, 107604. https://doi.org/10.1016/j.cie.2021.107604

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

This paper proposes a neural solver for dynamic multi-objective routing, where nodes and their attributes can change during route execution. It trains a preference-conditioned routing policy on five types of dynamic events and uses a cost-to-go signal for decision-level credit assignment. A separately trained controller selectively evaluates candidate next moves by completing hypothetical routes with the frozen policy, choosing whether to invoke lookahead and how many candidates to examine. These rollouts hold the current graph fixed rather than predicting future environmental changes.

Critical strengths
  1. The paper provides a useful evaluation setting for dynamic neural routing. The protocol introduces additions, cancellations, and attribute changes during route execution while preserving committed decisions and sharing event schedules across solvers. This enables controlled evaluation of adaptation beyond static routing benchmarks.
  2. The full method achieves the highest hypervolume across the reported dynamic task sizes and also improves frozen policies on static instances. This suggests that selective lookahead has practical value beyond the particular dynamic training setup.
Critical weaknesses
  1. The methodological novelty is narrower than the framing suggests. The “world model” completes routes using a frozen policy on the current graph. It neither learns environmental dynamics nor predicts future events. Since rollout-based candidate evaluation is already established, the contribution rests primarily on the learned allocation controller.
  2. The experiments do not isolate the benefit of adaptive allocation. Comparisons with fixed-K rollouts, simple uncertainty-based triggers, and SGBS under matched computational budgets are missing. Without these controls, it remains unclear whether the gains come from learning when to search or simply from performing additional search.
Questions for authors
  1. How does lookahead performance change as environmental events become more frequent or severe, given that candidate rollouts assume the current graph remains unchanged?
  2. What encourages the controller to skip lookahead or choose a smaller K, given that its reported reward measures solution improvement without an explicit computational cost penalty?
10 comments
AuthorsOpenReview ↗

Response to CW1— World Model Scope and Methodological Novelty

We thank the reviewer for this insightful comment. We address the two concerns separately.

1. Scope of the World Model.

Regarding the concern that our World Model neither learns environmental dynamics nor predicts future events, we agree that our model does not aim to learn general environmental transition dynamics. Instead, we adopt a task-specific, decision-oriented formulation, in which the model estimates the downstream consequences of candidate decisions to guide current action selection. Specifically, given the current observed graph, we fix a candidate node as the next action and use the frozen NCO policy to complete the remaining route, evaluating the resulting terminal objective. Only the selected next action is executed, while the imagined suffix is discarded. Future environmental changes are incorporated only after they are observed. This formulation is motivated by the broader principle of world models and model-based planning, where imagined future outcomes support present decisions (Ha and Schmidhuber, 2018; Janner et al., 2019; Hafner et al., 2025), rather than by a claim that our model learns general environmental dynamics.

2. Methodological novelty beyond rollout-based evaluation.

Regarding the concern that rollout-based candidate evaluation is already established, we agree that the rollout mechanism itself is not our primary novelty. Previous studies have explored simulation-guided search and additional test-time computation for neural combinatorial optimization (Choo et al., 2022; ). Our contribution instead lies in learning when to invoke lookahead and how many candidates to evaluate. Specifically, our PPO-trained controller uses decoder states, candidate-competition features, and environment features to select SKIP or a Top-K budget (K ∈ {2, 3, 4}) before observing any rollout scores. This enables state-dependent allocation of additional computation rather than relying on fixed-frequency rollout strategies.

3. Empirical evidence for adaptive allocation.

To demonstrate the benefit of learned allocation beyond conventional rollout strategies, Appendix G provides a direct comparison. Across 18 dynamic Bi-TSP and KroAB settings, the learned gate with K = 4 improves HV in 13 settings, matches the baseline in four, and decreases it in only one. Under the same Top-2 candidate budget, the largest observed HV decrease is 0.0042 with learned gating, compared with 0.0093 for every-event rollout and 0.0071 for every-step rollout. These results support the benefit of learning when to allocate additional computation, rather than simply increasing the number of rollouts.

References

[1] Ha, D., and Schmidhuber, J. (2018). World Models. Advances in Neural Information Processing Systems (NeurIPS). https://doi.org/10.5281/zenodo.1207631.

[2] Janner, M., Fu, J., Zhang, M., and Levine, S. (2019). When to Trust Your Model: Model-Based Policy Optimization. Advances in Neural Information Processing Systems (NeurIPS), 32.

[3] Hafner, D., Pasukonis, J., Ba, J., and Lillicrap, T. (2025). Mastering Diverse Control Tasks Through World Models. Nature, 640(8059), 647–653. https://doi.org/10.1038/s41586-025-08744-2.

[4] Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., and Gwon, Y. (2022). Simulation-Guided Beam Search for Neural Combinatorial Optimization. Advances in Neural Information Processing Systems (NeurIPS), 35, 8760–8772.

AuthorsOpenReview ↗

Response to R1-CW2: Isolating the Benefit of Adaptive Computation Allocation

We thank the reviewer for this valuable suggestion. To isolate the benefit of learned computation allocation, we conducted additional experiments against Fixed-K4 rollout (WECA-K4), uncertainty-triggered rollout (WECA-UT), and Simulation-Guided Beam Search (WECA-SGBS; Choo et al., 2022). We compare solution quality (HV) and inference time across 24 dynamic configurations covering Bi-TSP and Bi-CVRP, sizes 20/50/100, and profiles D1–D4.

1. Additional baselines and implementation.

All methods use the same frozen WECA backbone and evaluate candidate completions on the currently observed graph.

  • Fixed-K4: Evaluates the Top-4 candidate actions through frozen-policy route completion at every eligible decision.
  • Uncertainty Trigger (UT): Activates Top-K lookahead when mean normalized policy entropy exceeds τ=0.05\tau=0.05, with K=4K=4.
  • SGBS: Adapted from Choo et al. (2022). It expands the Top-γ\gamma actions of each beam, scores branches through greedy route completion, and retains the best-β\beta prefixes. We use (β,γ)=(10,10)(\beta,\gamma)=(10,10) for Bi-TSP and (4,4)(4,4) for Bi-CVRP. SGBS replans following observed environmental changes or invalidated cached routes.

2. Does learned allocation improve the quality–runtime trade-off?

Yes. WECA-WM achieves higher HV than Fixed-K4 in 15/24 configurations (one tie) and outperforms UT in 20/24 configurations. At size 100, WECA-WM achieves higher HV in 7/8 configurations against Fixed-K4 and 6/8 against UT, while requiring less inference time than both baselines in all eight configurations.

Representative results (HV ↑ / Time ↓):

SettingWECA-WMFixed-K4UT
Bi-TSP100-D20.8112 / 1.7m0.7961 / 24.7m0.8028 / 9.4m
Bi-CVRP100-D10.4664 / 6.0m0.4631 / 25.6m0.4631 / 25.5m
Bi-CVRP100-D40.4137 / 33.2m0.4123 / 3.5h0.4123 / 3.5h

The following Pareto plots further illustrate the mean HV–runtime trade-off across D1–D4.

Figure 1. Bi-TSP: Mean HV versus mean inference time.

Bi-TSP Pareto comparison

Figure 2. Bi-CVRP: Mean HV versus mean inference time.

Bi-CVRP Pareto comparison

3. How does learned allocation compare with SGBS?

SGBS achieves higher HV in 11/16 configurations at sizes 20 and 50, but requires substantially more inference time in all 16 configurations.

For example, on Bi-TSP20-D1, SGBS achieves HV 0.6747 in 3.3 minutes, compared with 0.6690 in 17 seconds for WECA-WM. The runtime gap becomes much larger at size 50.

At size 100, the completed Bi-CVRP100-D1 SGBS evaluation requires approximately 15 hours, compared with 6.0 minutes for WECA-WM (approximately 150× faster). WECA-WM also achieves higher HV (0.4664 vs. 0.4644).

The remaining seven size-100 SGBS evaluations are marked N/A because they were not completed due to excessive runtime.

4. Complete results and conclusion.

For completeness, Appendix I provides the full experimental results, including:

  • Appendix I: Implementation details and parameter settings for Fixed-K4, UT, and SGBS.
  • Tables 8–9: Complete per-profile HV and runtime comparisons across all D1–D4 settings, including Bi-TSP and Bi-CVRP at sizes 20, 50, and 100.
  • Figures 9–10: Mean HV–runtime Pareto comparisons across D1–D4.

These results show that the benefit of WECA-WM does not simply come from performing more search. Rather, learned allocation selectively uses rollout computation and achieves a favorable quality–runtime trade-off compared with fixed-width and uncertainty-triggered search. We acknowledge that SGBS can achieve higher HV in some smaller configurations, but its substantially higher computational cost limits its practicality for dynamic routing.

We have incorporated the additional experiments, complete results, and corresponding analysis into Appendix I of the revised manuscript.

References

[1] Choo, J., Kwon, Y.-D., Kim, J., Jae, J., Hottung, A., Tierney, K., & Gwon, Y. (2022). Simulation-Guided Beam Search for Neural Combinatorial Optimization. Advances in Neural Information Processing Systems (NeurIPS), 35, 8760–8772. https://doi.org/10.52202/068431-0637

AuthorsOpenReview ↗

Response to R1-Q1: Impact of Event Frequency and Severity on Lookahead

We thank the reviewer for this important question. To evaluate lookahead under increasingly frequent and severe environmental changes, we extended our experiments from D1–D3 to a new stress-test profile, D4. The results show that adaptive lookahead remains effective under stronger dynamics, outperforming fixed-K4 rollout in all six D4 configurations.

1. How do we increase environmental dynamics?

We systematically vary event frequency, the proportion of affected nodes, and attribute perturbation magnitude:

ProfileEvent probabilityChange ratioAttribute delta
D10.100.050.050
D20.200.100.075
D30.300.150.100
D40.500.200.150

D4 increases event frequency, the proportion of affected nodes, and attribute-change magnitude,

2. Does adaptive lookahead remain effective under stronger dynamics? Yes.

Across Bi-TSP and Bi-CVRP (sizes 20/50/100), WECA-WM achieves higher HV than Fixed-K4 in 3/6 configurations under each of D1, D2, and D3, increasing to 6/6 under D4.

Under D4, the HV results are:

SettingWECA-WMFixed-K4Uncertainty Trigger
Bi-TSP200.86240.86160.8615
Bi-TSP500.79570.78460.7966
Bi-TSP1000.94630.94370.9497
Bi-CVRP200.58300.58200.5820
Bi-CVRP500.46230.45700.4570
Bi-CVRP1000.41370.41230.4123

WECA-WM also outperforms uncertainty-triggered rollout in 4/6 D4 configurations. On Bi-CVRP100-D4, WECA-WM achieves HV 0.4137 in approximately 33 minutes, compared with 0.4123 in approximately 3.6 hours for Fixed-K4.

3. Why does fixed-graph lookahead remain useful under stronger dynamics?

The fixed graph is used only to evaluate the current decision, not to commit to an entire future route. Each rollout evaluates candidate consequences under the latest observed graph, but only the selected next action is executed. When an environmental event occurs, the graph is updated and the solver replans. Furthermore, the learned controller can skip or adjust lookahead when additional rollout computation is not beneficial.

4. Complete results in the revised manuscript.

We have added the complete D1–D4 experimental results and corresponding analysis to Appendix I of the revised PDF:

  • Table 7: Definitions and parameters of the four dynamic profiles.
  • Tables 8–9: Complete per-profile HV and runtime results for Bi-TSP and Bi-CVRP, respectively, including Fixed-K4 and uncertainty-triggered rollout comparisons.
  • Figures 9–10: Mean HV–runtime comparisons across D1–D4.

Overall, these results demonstrate that adaptive lookahead retains its effectiveness under substantially stronger environmental dynamics, even without explicitly predicting future events.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Summary of Revisions

Summary of Revisions

Dear Area Chair and Reviewers,

We thank the reviewers for their constructive comments. We have revised the manuscript and conducted additional experiments on dynamic robustness, adaptive computation allocation, runtime, and generality.

1. Stronger Environmental Dynamics (R1-Q1)

We extended D1–D3 with D4, a stress-test profile with more frequent and substantial environmental changes. D4 uses an event probability of 0.50, a change ratio of 0.20, and an attribute perturbation magnitude of 0.15.

Under D4, WECA-WM achieves higher HV than Fixed-K4 in all six configurations across Bi-TSP and Bi-CVRP at sizes 20/50/100, and outperforms uncertainty-triggered rollout (UT) in four. This shows that adaptive lookahead remains effective under stronger dynamics, although rollouts use the currently observed graph and do not predict future events. D4 results are included in Appendix I.

2. Search Baselines Across D1–D4 (R1-CW2, R2-CW2, R2-CW4)

To isolate learned allocation, we added three baselines using the same frozen WECA backbone: Fixed-K4 (Top-4 rollout at every decision), UT (entropy-triggered Top-K rollout), and SGBS (multi-level beam search with greedy rollout scoring and replanning after observed events).

We evaluated Bi-TSP and Bi-CVRP at sizes 20/50/100 under D1–D4. Across 24 configurations, WECA-WM achieves higher HV than Fixed-K4 in 15 cases (with one tie) and higher HV than UT in 20 cases. Full results and implementation details are in Appendix I.

3. Quality–Runtime Trade-off (R1-CW2, R2-CW2, R2-CW4, R3-Q2)

We report inference time and mean HV–runtime Pareto analyses across D1–D4. At size 100, WECA-WM is faster than Fixed-K4 and UT in all eight configurations, while achieving higher HV in 7/8 cases against Fixed-K4 and 6/8 against UT.

In the completed size-20/50 SGBS comparisons, SGBS achieves higher HV in 11/16 configurations, but WECA-WM is faster in all 16. The completed Bi-CVRP100-D1 SGBS run takes approximately 15 hours, versus 6 minutes for WECA-WM, which also achieves higher HV (0.4664 vs. 0.4644). The other seven size-100 SGBS runs are N/A because they are incomplete. These are measured quality–runtime comparisons, not strictly matched-budget claims.

Bi-TSP Pareto plot:
https://anonymous.4open.science/r/iclr2027-png-figures-FF33/tsp_hv_runtime_pareto.png

Bi-CVRP Pareto plot:
https://anonymous.4open.science/r/iclr2027-png-figures-FF33/cvrp_hv_runtime_pareto.png

4. World Model Scope and Main Contribution (R1-CW1, R2-CW1, R3-CW1)

We clarified that our World Model is a task-specific, decision-oriented model, not a learned environmental transition model. A frozen NCO policy completes candidate routes under the observed graph to estimate downstream objectives. Only the selected next action is executed; the imagined suffix is discarded, and replanning follows newly observed events. We acknowledge that the method does not predict future arrivals or cancellations.

Rollout-based evaluation is not claimed as the main novelty. The central contribution is the learned controller that decides when to invoke lookahead and how many candidates to evaluate.

5. Why the Controller Learns to Skip (R1-Q2)

We added a discussion in Appendix J. The reward measures realized solution improvement, not computational cost. Since later events can make imagined suffixes less relevant, the controller can learn to skip unhelpful rollouts. Training curves show that SKIP reaches 65–75% of decisions, relative reward improves from −1.1% to +0.6–0.7%, and mean search width decreases from 2.4 to 1.5. This behavior emerges from the quality-based reward, not an explicit runtime penalty.

Controller training curves:
https://anonymous.4open.science/r/iclr2027-png-figures-FF33/training_curves.png

6. Generality Across Settings and Backbones (R2-CW3, R3-CW2, R3-Q1)

We clarified that i.i.d. event triggering is used for controlled evaluation, not required by the framework. Experiments cover five event families, multiple dynamic profiles, two routing tasks, and out-of-distribution sizes of 150/200. Additional KroAB and XML results achieve the highest HV across all 18 evaluated size–profile configurations.

We integrated CNH as a second autoregressive NCO backbone. CNH-WM improves HV over CNH in all 18 dynamic and six static configurations across both tasks and sizes 20/50/100. WECA-WM also improves over WECA in all six static configurations. Full results are in Appendix K (Tables 10–11).


We believe these revisions address the reviewers’ main concerns through clearer methodological scope, stronger-dynamics and cross-backbone evaluations, and systematic quality–runtime comparisons. We sincerely thank the reviewers for helping us improve the manuscript.

AuthorsOpenReview ↗

Request for Reviewer Follow-up Before the Discussion Deadline

Dear Area Chair,

Thank you for the time and effort you have devoted to handling our submission and coordinating the review process.

As the rebuttal discussion period is nearing its end, we would be grateful if you could encourage reviewers who have not yet responded to our rebuttal to share whether our responses have addressed their concerns. We would welcome the opportunity to clarify any remaining questions while the discussion is still open.

Thank you again for your time and support.

Best regards, The author

Dear Authors,

Thank you for reaching out.

I have sent a reminder to the reviewers encouraging them to engage with the author response and to reply to the authors before the rebuttal deadline. I will also continue to encourage reviewers to participate in the subsequent reviewer–AC discussion.

I will make my recommendation based on careful consideration of the submission, all review comments, and your responses.

Thank you again for your time and effort.

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.