cs.CLApr 14, 2026
SaveFrom Myopic Selection to Long-Horizon Awareness: Sequential LLM Routing for Multi-Turn Dialogue
Organizations: School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · WeChat, Tencent Inc, Beijing, China · University at Buffalo, New York, United States
Abstract
Multi-turn dialogue is the predominant form of interaction with large language models (LLMs). While LLM routing is effective in single-turn settings, existing methods fail to maximize cumulative performance in multi-turn dialogue due to interaction dynamics and delayed rewards. To address this challenge, we move from myopic, single-turn selection to long-horizon sequential routing for multi-turn dialogue. Accordingly, we propose DialRouter, which first performs MCTS to explore dialogue branches induced by different LLM selections and collect trajectories with high cumulative rewards. DialRouter then learns a lightweight routing policy from search-derived data, augmented with retrieval-based future state approximation, enabling multi-turn routing without online search. Experiments on both open-domain and domain-specific dialogue tasks across diverse candidate sets of both open-source and closed-source LLMs demonstrate that DialRouter significantly outperforms single LLMs and existing routing baselines in task success rate, while achieving a superior performance-cost trade-off when combined with a cost-aware reward.
Figures & tables
Figure 1: Illustration of LLM routing in single-turn interaction (a) and multi-turn dialogue (b). Green arrows indicate ideal routing decisions. In multi-turn dialogue, different LLM selections induce different user queries. Rewards are distributed across turns, while the total reward reflects overall user intent fulfillment.
Figure 2: Overview of DialRouter. MCTS with a user simulator and reward model is used to explore dialogue branches and collect high-quality routing trajectories, which are then used for offline policy learning via behavior cloning to train a search-free router.
Figure 3: Routing process of DialRouter in multi-turn dialogue. At each turn, the current dialogue state and a retrieved future state approximation from are jointly encoded and fused to predict the LLM selection.
| Method | SR | AT |
|---|---|---|
| Random ( Lu et al., 2024 ) | 79.50 | 5.74 |
| KNN Router ( Hu et al., 2024 ) | 84.23 | 5.22 |
| Avengers ( Zhang et al., 2025b ) | 84.72 | 5.12 |
| DialRouter (Ours) | 88.32 | 5.21 |
| Greedy Router | 90.06 | 5.17 |
| MCTS Router | 94.99 | 5.13 |
Table 2: Performance comparison of DialRouter and baselines on ShareGPT using mixed candidate set of Qwen and Llama models.
Figure 4: SR and cost of DialRouter, Greedy Router, and MCTS Router under different values of the cost weight . Dashed horizontal lines correspond to the ratio-based reward setting.
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | # Training Dialogues | # Test Dialogues | Avg. # Checklist Items |
|---|---|---|---|
| ShareGPT | 750 | 90 | 6.70 |
| JDDC | 750 | 100 | 4.99 |
| MedDG | 750 | 100 | 4.94 |
| ShareGPT-LF | - | 66 | 6.58 |
Table 6: Statistics of dialogue-level data splits. All splits are performed at the dialogue level.
| Topic | Programming | Science | Health | Technology | Culture | Law | Finance | Others |
|---|---|---|---|---|---|---|---|---|
| Train | 419 | 187 | 23 | 23 | 20 | 0 | 0 | 78 |
| Test | 48 | 21 | 6 | 4 | 2 | 0 | 0 | 9 |
| SharGPT-LF | 0 | 0 | 0 | 0 | 0 | 22 | 44 | 0 |
Table 7: Coarse-grained topic distribution of the ShareGPT dataset.
| Category | Content Details |
|---|---|
| Dialogue Instance | User : What are the classic cocktails that every bartender should know how to make and what are their ingredients? Assistant : 1. Old Fashioned: Ingredients - bourbon or rye whiskey, sugar, bitters, ice, orange twist or cherry for garnish. 2. Martini: Ingredients - gin or vodka, dry vermouth, ice, olives or lemon twist … User : I’ve had all of these classic cocktails, but I’m looking for something new to try. Do you have any recommendations? Assistant : Sure, here are a few modern cocktail recommendations to try… User : The Elderflower Sour sounds interesting. I love trying new cocktails with unique ingredients. Assistant : The Elderflower Sour is a great cocktail… User : Definitely going to try the Elderflower Sour tonight! Do you have any other unique cocktail recommendations with interesting flavors? I’m in the mood to experiment. Assistant : Sure, here are a few more unique cocktail recommendations… User : The Smoked Maple Old Fashioned sounds intriguing. How exactly do you use a smoking gun in a cocktail? Assistant : To use a smoking gun in a cocktail like the Smoked Maple Old Fashioned… User : Wow, I never knew you could use a smoking gun in cocktails. That’s a really cool technique! Do you have any other creative cocktail techniques that I should know about? Assistant : Yes, there are several creative cocktail techniques… User : Wow, these techniques are really cool! I’ve never heard of fat-washing before. Do you have any tips for getting the proportions right? Assistant : Fat-washing is a fun technique… |
| User Profile | User Intent Chain with Trigger Logic : (I1) Request classic cocktails with ingredients and preparation methods; triggered initially when the user seeks foundational cocktail knowledge and re-triggered if recipes are insufficient. (I2) Request modern cocktail recommendations with recipes; triggered after (I1) is fulfilled and re-triggered if preparation details are incomplete. (I3) Request unique or creative cocktail recipes with distinctive flavors; triggered when the user expresses interest in experimentation and re-triggered if diversity is lacking. (I4) Request creative cocktail-making techniques; triggered when the user shows interest in how creative cocktails are prepared and re-triggered if key techniques are omitted. |
| Checklist | (1) Whether the model’s recommended classic cocktails include Old Fashioned and Bloody Mary. (2) Whether the model’s recommended modern cocktails include Elderflower Sour. (3) Whether the model’s output includes at least 5 classic cocktails. (4) Whether the model’s output includes at least 5 modern cocktails. (5) Whether the model provides the recipe and basic preparation method for each cocktail. (6) Whether the model avoids repeating cocktails or other information already provided. (7) Whether the model avoids self-contradictions across multiple turns. |
Table 8: An example dialogue from ShareGPT used for user profiling and checklist construction. Some content is omitted for brevity.
| Category | Content Details |
|---|---|
| Dialogue Instance | User : Can you help me change the delivery address for my order? (可以帮我改下订单的地址吗？) Customer Service : If the address is within the same city, you can contact the courier to update it. (同一市内可以联系配送员直接修改的哦。) User : It’s not the same city. The current address is in Shanghai, but I’ll be returning to Anhui tomorrow. (不在同一个城市，现在地址是上海，但是我明天要回安徽。) Customer Service : Sorry, cross-city address changes are not supported. We recommend placing a new order instead. (抱歉，地址在不同城市不能操作的，只能建议您重新下单哦。) User : If I cancel the order, how long will it take to receive the refund? (那我取消订单的话退款多久到账呢？) Customer Service : Refund times depend on the payment method: one business day for digital wallets, 1–7 business days for debit cards, and 1–15 business days for credit cards. (微信零钱1个工作日内到账，储蓄卡1-7个工作日内到账，信用卡1-15个工作日内到账的哦！) User : Why can’t the address be changed? This is really inconvenient. (为什么不能改地址，你们这也太不方便了。) Customer Service : We apologize for the inconvenience. Our logistics system still has limitations. (非常抱歉，我们物流还有待完善呢。) User : This is quite troublesome—I need the item urgently. (这也太麻烦了，我还急着用呢。) Customer Service : We understand your urgency and will continue to improve our service. (非常抱歉！如果是我的话我也会很着急的，我们会改进的！) User : Alright. (行吧。) Customer Service : Thank you for your understanding. Is there anything else we can help with? (谢谢您的理解！还有什么能帮到您的吗？) |
| User Profile | Behavior Patterns : Attempts to change the delivery address across cities; expresses urgency and dissatisfaction; proactively inquires about refund timing. General Context : Currently in Shanghai and returning to Anhui the next day; has an urgent need for the item. User Goals : (1) Change the delivery address from Shanghai to Anhui. (2) Inquire about the refund processing time if the order is canceled. |
| Checklist | (1) Whether the agent identifies or confirms the location involved in the address change request. (2) Whether the agent clearly explains that delivery addresses can only be modified within the same city and explicitly states that cross-city address changes are not supported. (3) Whether the agent acknowledges and soothes the user’s urgency and dissatisfaction. (4) Whether the agent suggests placing a new order as an alternative solution. (5) Whether the agent provides accurate refund processing times for different payment methods. |
Table 9: An example dialogue from JDDC used for user profiling and checklist construction. The original dialogue, user profile, and checklist are in Chinese and are translated into English for presentation, with some content omitted for brevity.
| Category | Content Details |
|---|---|
| Dialogue Instance | User : Since yesterday, I have been experiencing persistent abdominal pain and intermittent diarrhea, about 7–8 times. Last night my temperature was 37.3 ∘ C. What medication should I take? (Female, 30 years old) (从昨天开始到今天肚子一直痛，断断续续拉了7.8次大便，昨晚测量体温37.3度，请问医生我该吃点什么药?（女，30岁）) Doctor : Have you eaten any contaminated food, greasy or spicy food, or consumed alcohol? Do you smoke, feel stressed, or have poor sleep? Have you undergone any medical examinations or taken any medication? Acute gastroenteritis is a possible cause. You may take montmorillonite powder and levofloxacin capsules. (你好，请问你是吃不干净的东西了吗？有没有油腻食物，辛辣刺激性食物，喝酒抽烟，精神压力大，睡眠不好之类有没有做过什么其他检查，有吃过什么药物吗。考虑急性肠胃炎可能性比较大。可以吃蒙脱石散，左氧氟沙星胶囊。) User : I ate some greasy food a few days ago. I have not had any examinations recently and have not taken any medication. (前几天吃了点油腻的食物，近期也没有做什么检查，也没有吃什么药。) Doctor : That is fine. Both medications are available at pharmacies. I recommend having a stool routine test. (嗯呢。可以的。这两种药药店都有。建议查一个大便常规。) User : Okay, thank you. (好的，谢谢。) Doctor : Good health relies on self-care rather than only doctors or medications. Sunlight, a positive mindset, and reducing stress are also important. (健康，是靠自己的养护，不是靠医生，和药物，阳光，微笑，就是健康，别给自己压力太大，加油哦。) User : Hello doctor, my spouse still has diarrhea after taking the medication, with abdominal pain and diarrhea shortly after meals. Should we continue the medication and observe? (”医生你好，我爱人吃了药后，还是拉稀，和刚吃完饭后，肚子痛，又闹肚子，这个还要接着吃药，看看吗。) Doctor : Have you had a stool test or blood test? I suggest going to the emergency department for further evaluation. We need to check for possible electrolyte imbalance and abnormal blood counts. Further treatment may be required, and it is difficult to assess without examinations. (有没有做大便检查。抽血了吗。建议你去急诊看看。观察有没有电解质紊乱和血象增高。是需要进一步治疗的。不化验不好说。) |
| User Profile | Demographics : Female, 30 years old. Chief Complaint : Abdominal pain and diarrhea. Symptom Details : (1) Abdominal pain : Located in the lower abdomen; cramping in nature. (2) Diarrhea : 7–8 episodes; watery stool; no blood observed. (3) Fever : Body temperature of 37.3 ∘ C; duration within one day. Suspected Trigger : Consumption of greasy food a few days prior. Medical History : None reported. Current Medication : None. User Goals : (1) Symptom assessment; (2) Medication recommendation; (3) Examination recommendation; (4) Diagnosis clarification. |
| Checklist | (1) Whether the doctor identifies the patient’s key symptoms, including abdominal pain, diarrhea, and fever. (2) Whether the doctor recommends appropriate medications, such as montmorillonite powder and levofloxacin capsules, for treating diarrhea and abdominal pain. (3) Whether the doctor advises relevant examinations, such as a stool routine test. (4) Whether the doctor determines the underlying condition to be acute gastroenteritis. |
Table 10: An example dialogue from MedDG used for user profiling and checklist construction. The original dialogue, user profile, and checklist are in Chinese and are translated into English for presentation, with some content omitted for brevity.
| Model | Input ($/1M tokens) | Cached Input ($/1M tokens) | Output ($/1M tokens) |
|---|---|---|---|
| Qwen3-Max | 0.459 | 0.0918 | 1.836 |
| DeepSeek-Chat-V3.2 | 0.28 | 0.028 | 0.42 |
| GPT-5.1 | 1.25 | 0.125 | 10 |
Table 11: Pricing of closed-source language models.
| MCTS | Training | Inference | |
|---|---|---|---|
| Time | 3h 40min (750 dialogues) | 1.3 s / batch | 0.03 s / decision |
| GPU Memory | – | 18.9 GB | 3636 MiB |
Table 12: Time and GPU memory consumption for MCTS, training, and inference.
| ShareGPT ( ) | JDDC ( ) | MedDG ( ) | ||||
|---|---|---|---|---|---|---|
| Method | Qwen3-Max | GPT-5.1 | Qwen3-Max | GPT-5.1 | Qwen3-Max | GPT-5.1 |
| Qwen3-14B | 83.24 | 77.77 | 77.19 | 78.76 | 72.50 | 70.17 |
| KNN Router ( Hu et al., 2024 ) | 83.37 | 76.45 | 78.44 | 78.67 | 71.99 | 68.74 |
| Avengers ( Zhang et al., 2025b ) | 83.93 | 78.29 | 78.34 | 78.14 | 71.69 | 69.29 |
| DialRouter (Ours) | 87.46 | 81.01 | 83.45 | 84.39 | 79.03 | 76.26 |
| MCTS Router | 94.11 | 87.00 | 88.42 | 89.30 | 86.77 | 83.54 |
Table 13: Task success rates evaluated by two independent evaluators (Qwen3-Max and GPT-5.1), with Spearman’s indicating consistent method rankings across domains.
Figure 5: Per-turn routing selection distributions (stacked proportion plots) and inter-turn routing transition heatmaps for the Qwen (left) and Llama (right) candidate sets across three datasets. The stacked areas show the proportion of dialogue trajectories selecting each model at each turn; the total height decreases in later turns as fewer dialogues extend to longer horizons.
Figure 6: System prompt for the ShareGPT user simulator.
Figure 7: System prompt for the ShareGPT reward model.
Figure 8: System prompt for the JDDC user simulator.
Figure 9: System prompt for the JDDC reward model.
Figure 10: System prompt for the MedDG user simulator.
Figure 11: System prompt for the MedDG reward model.
Figure 12: Case study on multi-turn e-commerce customer service in JDDC with Llama candidate set.
Figure 13: Case study on multi-turn script writing in ShareGPT with closed-source LLM candidate set.
Figure 14: Case study on multi-turn medical consultation in MedDG with Qwen candidate set.