acceptodds
Under review as a conference paper at ICLR 2027

Propose-and-Refine: Multi-Turn LLM Routing for Long-Horizon Tasks with Virtual-Rollout MCTS

Abstract

Large language models (LLMs) are increasingly deployed for long-horizon tasks, where inference costs accumulate over multiple turns and different turns may require different model capabilities. Unlike episode-level routing, multi-turn routing selects a model at each interaction step to better balance performance and cost under user preferences. However, learning effective multi-turn routers remains challenging because the long-term value of a routing action depends on future routing plans, and high-quality supervision is difficult to obtain under a limited real-environment rollout budget. We propose ProRe, a propose-and-refine multi-turn routing framework. At each state, a generative proposer samples routing plans composed of variable-duration macro-actions, and a plan-conditioned refiner ranks them by predicted terminal performance and cumulative cost under a user-specified preference, thereby incorporating future information into the current decision. To train ProRe efficiently, we introduce OnVir, an online data-collection strategy that replaces real-environment rollouts in Monte Carlo tree search (MCTS) with ProRe-generated virtual rollouts, discovering higher-quality routing trajectories under a fixed sampling budget. Extensive experiments show that ProRe and OnVir jointly improve routing performance across diverse long-horizon tasks and user preferences.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-turn LLM routing, Cost–performance trade-off, MCTS with virtual rollouts, Online data collection

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_4RBaOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ProRe, a Propose-and-Refine multi-turn routing framework designed for long-horizon tasks, and OnVir, an online data-collection strategy that augments Monte Carlo Tree Search (MCTS) with virtual rollouts. ProRe utilizes a generative proposer to sample future routing plans comprising variable-duration macro-actions, and a plan-conditioned refiner to rank these plans based on predicted terminal performance and cumulative inference costs according to specific user preferences. OnVir mitigates the high costs of real-environment MCTS rollouts by substituting them with ProRe-generated virtual rollouts.

Critical strengths
  • Innovative Data Collection Strategy: The introduction of OnVir to replace expensive real-environment MCTS rollouts with virtual rollouts—evaluated by the evolving ProRe router itself—is a clever and cost-effective approach to mitigating the data collection bottleneck in long-horizon routing.

  • Explicit Future Modeling: Unlike existing multi-turn routers that model future trajectories implicitly, ProRe explicitly generates and evaluates complete future routing plans. This provides a more interpretable and grounded estimation of long-horizon performance-cost trade-offs.

Critical weaknesses
  • Unquantified Training Overhead: While the paper successfully argues that OnVir lowers rollout costs compared to traditional MCTS, the computational overhead of the iterative training itself (updating the proposer, performance predictor, and cost predictor over multiple rounds) is not systematically compared against the training costs of the baselines. The absolute experimental cost (~3000 USD) is buried in the appendix, leaving the comparative efficiency of training ProRe unclear.

  • Method Presentation and Figure Clarity: The method presentation, particularly Figure 2, is highly abstract and confusing. It relies heavily on color-coded blocks without providing a concrete grounding example (e.g., an actual interaction trace in a task like "Fix the CSV bug"), which obscures the practical mechanism of macro-actions and plan refinement, negatively impacting reproducibility. Furthermore, the title of Figure 1(b) ("Lack of high-quality traning data") does not align with its visual content, which actually illustrates "High Real-Environment Rollout Costs".

  • Cross-Domain Generalization & Fine-Tuning Dependency: It is unclear if the trained router (specifically the task-conditioned predictors) requires complete retraining or fine-tuning when transferred to entirely new domains. A strong dependency on domain-specific training data severely limits the practical out-of-the-box utility of the proposed framework.

Questions for authors
  1. Training Overhead Comparison: Could you provide a quantitative comparison of the total training costs (compute and API costs) between ProRe/OnVir and the primary multi-turn baselines (e.g., SeqRouter, MTRouter)? How does the iterative optimization of the three predictors impact the overall training budget compared to offline baseline methods?
  2. Predictor Convergence and Dynamics: How does the accuracy of the predictors (performance and cost) evolve during the Q=3Q=3 online collection rounds? Does the predictor effectiveness heavily bottleneck the final routing quality, and do they converge early or require continuous optimization?
  3. Cross-Domain Fine-Tuning: Does ProRe require domain-specific fine-tuning to maintain its routing accuracy in entirely new domains? How robust are the predictors to zero-shot out-of-domain evaluation without any in-domain bootstrap data?
  4. Role of Macro-actions: In the ablation study (Table 2), removing the macro-action design only resulted in a marginal utility drop (e.g., Overall from 0.34 to 0.33). The text mentions its main role is to "reduce the number of routing decisions". Does this reduction translate to measurable improvements in wall-clock time or significant savings in the router's own inference overhead? Please quantify this benefit in the rebuttal.
Reviewer_acANOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies multi-turn LLM routing for long-horizon tasks. To address long-range dependencies in this setting, it introduces ProRe, a propose-and-refine framework for multi-turn routing. The proposer generates multiple plans for future model calls, while the refiner predicts final task performance and remaining cost based on the current state and candidate plans. To address the scarcity of high-quality supervision, the paper further introduces OnVir, which replaces real-environment rollouts in MCTS with proposer-generated plan completions and refiner predictions, and iteratively updates the router using collected real-environment trajectories. Experiments on ScienceWorld, HLE, and SWE-bench Verified demonstrate that the proposed approach improves routing performance.

Critical strengths
  1. The paper addresses the practically relevant problem of balancing task performance and cost in multi-turn LLM routing. The experimental results also demonstrate the proposed method’s substantial advantages in reducing task costs.
Critical weaknesses
  1. After executing a proposer-generated plan, OnVir discards the other previously generated virtual rollouts. Given the long-range dependencies in long-horizon tasks, this strategy may lead to suboptimal or unusable rollouts. Moreover, the paper lacks comparisons with and discussion of alternative MCTS simulators.
  2. The method involves numerous hyperparameters, raising concerns about its sensitivity to their settings.
  3. The paper notes that methods such as offline Q-learning suffer from out-of-distribution value estimation errors, but does not convincingly explain how the proposed approach mitigates this issue.
Questions for authors
  1. In the “Effectiveness of OnVir” section, the results in Fig. 3 do not appear to support the claim that virtual rollouts provide more informative search signals.
  2. Several aspects of the paper are described unclearly. For example, neither the function g(∙) in Eq. (2) nor the evaluation metric U in Table 1 is adequately defined.
6 comments
AuthorsOpenReview ↗

Gentle Reminder to Reviewer acAN

Dear Reviewer acAN,

Thank you again for your careful review and helpful comments. We would be grateful if you could take a look at our responses when you have a moment.

Your first concern is that OnVir discards previous virtual rollouts. This is an intentional design, because a virtual rollout is not actually executed: the refiner directly estimates its performance and cost. Following AlphaGo, we take the current state as the root and roll out from there. Because it is virtual, it cannot be reused in the next state or inserted into the Monte Carlo tree of next state.

Discarding them does not remove long-range dependency, because each state already uses many virtual rollouts and ProRe considers the future through an explicit plan. Instead, keeping them would make the design unreasonable. We have also compared alternative MCTS simulators in our work.

Your second concern is sensitivity to hyperparameters. All hyperparameters are fixed. ProRe has only two core hyperparameters, and OnVir uses common hyperparameters for online data collection. We have ablated the key ones in extensive experiments.

Your third concern is the out-of-distribution issue in offline Q-learning. That discussion is only an example to explain our motivation. We do not claim to solve that problem. Higher-quality training data by Onvir can alleviate this concern.

Please let us know if you have any further comments. If anything is still unclear, we would be happy to discuss it.

Thank you again.

Reviewer_acANOpenReview ↗

Response to Authors for ID 13074

Thanks for the clarification, which addresses most of my concerns. However, one major issue remains. The method involves six key hyperparameters, and the results in Figs. 5 and 7–8 indicate that performance is substantially affected by the choice of values for some of them. The need to tune multiple sensitive hyperparameters makes it difficult to assess the merits of the method’s core design and its practical value.

AuthorsOpenReview ↗

Response to the Remaining Concern on Hyperparameter Sensitivity

We thank the reviewer for the follow-up very much. We address the remaining concern from two angles: (1) the gains of our core design are robust to hyperparameter choices, and (2) most of hyperparameters do not require delicate tuning, and the default values are sufficient

To begin with, we briefly restate our two contributions:

  • ProRe lets each routing action be evaluated under explicit future information. A generative proposer samples future routing plans, and a plan-conditioned refiner ranks them by predicted performance and cost under the user preference.
  • OnVir augments MCTS with virtual rollouts generated and evaluated by ProRe, improving training-trajectory quality under a fixed sampling budget.

It is worth noting that we propose a routing method and a data collection strategy rather than just one. So our work will have more hyperparameters.

1. The gains of the core design are robust to hyperparameter choices.

  • ProRe is effective without any OnVir hyperparameters. Trained on MTRouter data (Table 11), where QQ, BB, SVS_V, and η\eta play no role, ProRe still improves Overall utility on SW from 0.24 (MTPref) to 0.35.
  • OnVir data benefits other routers. Training MTPref, SeqRouter, and DialRouter on OnVir data, where SIS_I of ProRe plays no role, improves Overall utility in 5 of 6 cases (Fig. 4).
  • Each ProRe component contributes, and OnVir + ProRe clearly outperforms existing methods. Averaged over SW and SWE-V (Tables 2 and 10), removing any component lowers Overall utility from 0.34 to 0.25–0.33. Yet every variant, trained on OnVir data, still exceeds one of the strongest baselines, Adaptive (0.17).

Therefore, the first two points show that ProRe and OnVir are each effective independently, and the third confirms the effectiveness of the core design of ProRe. To the best of our knowledge, the idea of ProRe and OnVir is novel and highly meaningful for future work that uses our OnVir for data collection.

2. A closer look at each hyperparameter.

Our method, including the data collection method and routing method, has only six core hyperparameters: two for ProRe (NN, SIS_I) and four for OnVir (QQ, BB, SVS_V, η\eta). QQ and BB are standard budget controls; MCTS also has a similar real rollout hyperparameter to SVS_V, and NN follows a fixed rule. Moreover, performance is generally not sensitive to them, so they do not require dedicated tuning.

HyperparameterRoleEvidenceSensitivity
N=L/10N=L/10Fixed rule from the turn limit; reduces routing-decision latency (see our response to Q4 of Reviewer 4RBa)N=1N=1 gives the same Overall utility (SW 0.44, SWE-V 0.23; Table 10)Negligible
SV=128S_V=128Virtual budget, no environment cost. MCTS has similar parameter for real rolloutFrom SV=8S_V=8 to 128128, regret changes by ≤0.012; at SV=8S_V=8, 92–95% of executed actions already match (Fig. 6)nearly Negligible; a default large value suffices
Q=3Q=3, B=4B=4Real-data budgetHit@1 improves steadily over rounds (Fig. 8), like a learning curve; chosen by real-rollout budgetthe same as the budget of existing work MTRouter or a little fewer is also enough owing to our OnVir Design
η=0.5\eta=0.5Mixes real and virtual statisticsRegret decreases consistently with η\eta (Fig. 7); we use 0.5 as default without tuning.Smooth
SI=8S_I=8Candidate plans at inference, no retrainingFor SI≥4S_I\ge 4, no systematic trend; SI=16S_I=16 or 6464 is often better than our default. Only SI=2S_I=2 is clearly worse, as it leaves the refiner too few candidates, further confirming the value of refiner of ProRe (Fig. 5)Stable for SI≥4S_I\ge 4; less sensitive

Although we analyze each hyperparameter above, they can be left at default settings, e.g., N=L/10N=L/10, SI=8S_I=8, and SV=128S_V=128. This indicates that they are stable in practice, and further suggests that the effectiveness of our method stems from its core design.

3. One configuration, no per-setting tuning.

All hyperparameters are kept fixed without per-setting tuning across three benchmarks, three preferences, and both ID and OOD splits. Moreover, the same configuration accommodates different cache rates without retraining (Table 3), which is difficult for existing routers. This further verifies the practical value of our method.

We hope this clarifies that the advantages of ProRe and OnVir come from their core design rather than careful tuning, and we would be grateful if the reviewer would take this into account in the final assessment. If you have any concerns, please feel free to ask us.

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

The paper studies how to choose LLM during a long-horizon task to balance performance and cost. It proposes ProRe, which compares future model-use plans and executes the first part of the best plan before planning again. It also introduces OnVir, which uses predicted outcomes in tree search to reduce expensive real rollouts when collecting training data.

Critical strengths

The paper focuses on an important problem in long-horizon tasks: choosing models during long-horizon tasks to balance performance and cost. It compares future model-use plans before making the next decision, and the ablation results provide some evidence that this design improves routing.

Critical weaknesses

The cost evaluation relies on a simplified caching assumption. The main experiments assume no cache hits, and the cache experiments use fixed hit rates to reprice trajectories. In practice, cache reuse depends on the model-selection history. Switching models can require processing a long conversation prefix again, while staying with one model can preserve cache reuse. Given the large price difference between cached and uncached inputs, this simplification may overstate savings over fixed-model baselines. Actual cache hits and billed costs should be measured for each routing policy to support the practical cost-efficiency claim.

Questions for authors

Q1: Reliability of virtual rollouts. The search relies on the refiner’s predictions, but it is unclear whether they are accurate for newly generated plans. Search may favor plans whose value is overestimated. I recommend the authors compare predicted and actual outcomes for these plans.

Q2: Possible bias from plan length. Training plans come from completed trajectories, so short plans may reflect early success. Could the refiner learn that short plans imply success and overrate generated short plans? Please also explain how remaining costs are counted when a plan ends before the task is complete.

4 comments
AuthorsOpenReview ↗

Gentle Reminder to Reviewer kLT9

Dear Reviewer kLT9,

Thank you again for your careful review and helpful comments. We would be grateful if you could take a look at our responses when you have a moment.

Your main concern is that our cost evaluation relies on a simplified caching assumption. We agree. Our method is compatible with different cache rates under our existing training, without re-training on the target cache rate, which can be validated in our original paper. So we argue that this is an advantage of our approach over existing work.

Please let us know if you have any further comments. If anything is still unclear, we would be happy to discuss it.

Thank you again.

Thanks for the author's rebuttal and additional experiments.

Regarding W1, the cache-rate compatibility experiments demonstrate the flexibility of cost repricing. However, the methodology behind Table 14 remains unclear. In particular, it is not explained how the real cache rates were obtained, whether different routing methods use their own observed cache rates, or whether the reported costs account for routing-dependent cache behavior in multi-turn interactions. Therefore, I believe this concern has only been partially addressed.

Regarding Q2, I appreciate the additional analysis of prediction bias across different plan lengths. However, this analysis is based on completed trajectories rather than newly generated plans, and therefore does not fully rule out potential biases toward generated short plans. Additionally, it remains unclear how the refiner accounts for the remaining costs when a generated plan ends before task completion.

Therefore, I believe my main concerns remain only partially addressed. I will therefore maintain my original rating.

AuthorsOpenReview ↗

Further Response for Reviewer kLT9

Dear Reviewer kLT9,

Thank you for your timely reply very much.

W1: Thank you for asking about Table 14. We're sorry we didn't specify this.

Table 14 doesn't apply one shared cache rate. For each call in a method's own evaluation trajectory, we take the number of cached prompt tokens the provider reports. We charge those tokens at that model's cached-input price and the rest of the prompt at the standard input price. The episode cost is the sum over all calls. We'll add this protocol to the caption of Table 14.

Each routing method is therefore billed for its own observed cache hits, so the reported costs reflect routing-dependent cache behavior. For example, an episode-level router uses one model for the whole episode, so later calls can often reuse that model's cached prompt prefix. A multi-turn router, including ours, may switch models. A call made right after a switch can't reuse the previous model's cache. If the router later returns to a model it has already used, that can still read the prefix cached for that model, as long as the cache hasn't expired. In every case, we bill exactly the cached tokens the provider reports for that call.

Q2: Thank you for asking how the remaining cost is counted when a plan ends before the task is complete. We're sorry we didn't specify this either.

As described in lines 246–252, at each routing state, the proposer generates several candidate plans, each consisting of several macro-actions. The refiner then predicts the cost and performance of each plan. ProRe executes only the first macro-action of the top-ranked plan. It then repeats propose-and-rerank at the new state until the task ends.

The refiner only prices the plan it is scoring. If that plan ends before the task is finished, its predicted cost can't include the turns that come after it, because those turns haven't happened yet and aren't part of the plan. However, after the first macro-action runs, propose-and-rerank starts again from the observed next state, and the refiner prices a new plan from there. Any cost beyond the earlier plan is covered by these later decisions, based on what actually happened during execution.

You also noted that this analysis uses completed trajectories rather than newly generated plans. We used completed trajectories because, during routing, ProRe executes only the first macro-action of a generated plan, not the full plan. A newly generated plan is therefore not run to completion, so its realized terminal performance is not observed. Following your suggestion, we will run the same analysis on newly generated plans and share the results as soon as possible.

Thank you again for taking part in the discussion. We will provide another analysis for your Q2 as soon as possible.

AuthorsOpenReview ↗

Further Response for Q2 of Reviewer kLT9 (complete version)

Dear Reviewer kLT9,

Q2: You also noted that this analysis uses completed trajectories rather than newly generated plans.

We used completed trajectories because, during routing, ProRe executes only the first macro-action of a generated plan, not the full plan. A newly generated plan is therefore not run to completion, so its realized terminal performance is not observed.

Following your suggestion, we will run the same analysis on newly generated plans and share the results as soon as possible. And we also analyze whether the training data has position bias towards short plans.

  • The position-bias results for newly generated plans.

Experimental setup. Following our response to Q1, we compare predicted and realized performance on newly generated plans for SW and SWE-V. When a plan ends before the task ends, realized performance is defined as in that response. On SW, we take the environment score at the end of the plan. On SWE-V, if the plan ends before the task is finished, we continue with the plan's final model until termination and use that outcome.

Following our initial response to Q2, we use the same comparison. Plans are grouped into 1–10, 11–20, and 21+ environment steps. Bias is predicted normalized performance minus realized performance. The table averages the three preferences (cost, balance, and performance). Each preference–length bin contains 40 newly generated plans from the test split, so each length bin has 120 instances.

Each case starts from its initial state. At that state, the proposer samples several plans, and each plan is assigned to the length bin it falls in. We keep randomly sampling for a case and obtain corresponding plans until every preference–length bin is full.

Benchmark1–1011–2021+
SW+0.170+0.124+0.120
SWE-V−0.063−0.047+0.107

Analysis. A bias toward generated short plans would appear as a higher bias in the shorter bins on both benchmarks. On SW, the bias decreases from +0.170 to +0.120, and the 11–20 bin is nearly the same as the 21+ bin. On SWE-V, however, the short bins are negative, and the 21+ bin is positive, so short plans are not the ones being overrated. This pattern also does not clearly follow the trend in the refiner training data above.

  • The position-bias results for training data

To begin with, we first check whether short plans in the training data reflect early success. Both tables below average the three preferences. For a bin such as 1–10, we keep the episodes whose length falls in that bin, average their normalized terminal performance within each preference, and then average those three means.

Whole trajectories. Each training episode is one pair: its length in environment steps, and its terminal performance.

Benchmark1–1011–2021+
SW0.6550.7040.620
SWE-V0.4530.4090.373
HLE0.1710.3220.109

On SW and HLE, the highest bin is 11–20, so a short episode is not an early success.

Refiner training. Appendix A.2 (Details of Training) builds one example at each routing step of a completed trajectory. The example is the current state sts_t, the history so far ρt\rho_t, the future plan ρt+\rho_t^+ (the remaining suffix), and the realized targets: the episode's terminal performance and the per-turn cost of that suffix. Suffixes of one episode share its terminal performance, so a short suffix is not given a higher label than the rest of the same episode. In this table, each routing step is one pair. The length is the number of environment turns left in the future plan, and the performance is the episode's terminal performance. Bin averages follow the same procedure as the first table.

Benchmark1–1011–2021+
SW0.6600.6450.610
SWE-V0.3910.3800.271
HLE0.1670.1390.080

Shorter suffixes have only slightly higher performance. On SW the gap between the 1–10 and 11–20 bins is 0.015.

Finally, we suggest that, on these training data, a short plan is not marked as an early success.

Thank you for engaging in this discussion. If you have further concerns, please feel free to let us know.

Comments on the paper

2 comments

Dear Reviewer kLT9,

Thank you again for reviewing our paper and for your follow-up feedback.

In our latest response, we addressed your remaining concerns:

  1. How cost is computed. We explained step by step how the billed cost of each routing plan is calculated.
  2. Whether the refiner has a position bias toward short plans. Our experiments show that neither the training data nor the generated plans clearly favor shorter plans.
  3. How the remaining cost is counted when a plan ends before the task is complete. The refiner predicts cost only for the plan it is scoring. ProRe runs only the first macro-action of the top-ranked plan and then repeats propose-and-rerank from the next observed state. Later decisions cover any cost beyond the earlier plan, based on what actually happens during execution.

We hope these clarifications resolve your concerns. We would be glad to discuss anything further. If the issues have been addressed, we would be grateful if you would consider updating your score.

To briefly restate our contributions:

  • ProRe evaluates each routing action using explicit information about future steps. A generative proposer samples future routing plans, and a plan-conditioned refiner ranks them by predicted performance and cost under the user's preference.

  • OnVir adds virtual rollouts, generated and evaluated by ProRe, to MCTS. This improves the quality of training trajectories under a fixed sampling budget.

  • Comprehensive experiments show that both methods are effective.

We believe these contributions are meaningful and novel. In particular, OnVir produces higher-quality training data that can benefit future routers.

Your opinion is very important to us, and we look forward to your feedback.

Best regards,

The Authors

Dear Reviewers kLT9 and acAN,

As the discussion period ends in one day, we would be grateful if you could take a look at our latest response. Your feedback is very important to us.

If our response has addressed your concerns, we would sincerely appreciate it if you would consider raising your score. If any concerns remain, please let us know, and we will do our best to address them before the deadline.

Thank you very much for your time and effort.

Best regards,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.