From Myopic Selection to Long-Horizon Awareness: Sequential LLM Routing for Multi-Turn Dialogue
Authors: Jiarui Zhang, Xiangyu Liu, Yong Hu, Chaoyue Niu, Hang Zeng, Shaojie Tang, Fan Wu, Guihai Chen
Organizations: School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · WeChat, Tencent Inc, Beijing, China · University at Buffalo, New York, United States
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 st and a retrieved future state approximation sj+1′ from Dsearch 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
Appendix
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
Appendix
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.
Appendix
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.
Appendix
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.
Appendix
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
Appendix
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
Appendix
Table 12: Time and GPU memory consumption for MCTS, training, and inference.
ShareGPT ( ρ=0.9 )
JDDC ( ρ=0.7 )
MedDG ( ρ=0.9 )
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
Appendix
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.
Large language models exhibit complementary strengths, motivating routing methods that dispatch each query to the most suitable model. Although existing routers are effective in single-turn settings, they do not directly transfer to multi-turn dialogue, where routing performance critically depends on how historical context is segmented, retained, and incorporated into the current prompt. This introduces two fundamental challenges: preventing information loss and information confusion during context construction, and evaluating routing quality without conflating model selection with prompt construction quality. In this paper, we propose SWRouter, a Similarity-Contractive Window Router for multi-turn large language model routing. SWRouter combines a similarity-based context segmentation mechanism for prompt construction with a dual-metric evaluation framework that decouples construction accuracy from router performance. Experiments on multi-turn dialogue benchmarks demonstrate that SWRouter consistently surpasses strong baselines, achieving a 16.26% improvement in evaluation accuracy over the best individual large language model and an additional 8.22% gain over the Conv-ID Context baseline. Our results highlight that multi-turn large language model routing requires a joint design of context construction and evaluation, rather than a direct extension of single-turn routing methods.
Yu Wang, Yuchen Li, Rui Kong +11
Department of Big Data Management and Application, Shanghai Jiao Tong University, Shanghai, China · School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · Baidu Inc., Beijing, China +3
Large language model (LLM) based multi-turn dialogue systems often struggle to track dependencies across non-adjacent turns, undermining both consistency and scalability. As conversations lengthen, essential information becomes sparse and is buried in irrelevant context, while processing the entire dialogue history incurs severe efficiency bottlenecks. Existing solutions either rely on high latency external memory or lose fine-grained details through iterative summarization. In this paper, we propose Self-Recall Thinking (SRT), a framework designed to address long-range contextual dependency and sparse informative signals in multi-turn dialogue. SRT identifies helpful historical turns and uses them to generate contextually appropriate responses, enabling the model to selectively recall and reason over context during inference. This process yields an endogenous reasoning process that integrates interpretable recall steps without external modules. SRT incorporates: (1) Dependency Construction: Generating and converting it into self-recall chains; (2)Capability Initialization: Training to enable reasoning chains with recall tokens capability; (3)Reasoning Improvement: Refining accuracy via verifiable rewards to optimize recall and reasoning for correct answers. Experiments on multiple datasets demonstrate that SRT improves F1 score by 4.7% and reduces end-to-end latency by 14.7% over prior methods, achieving a balance between reasoning latency and accuracy, and outperforming state-of-the-art baselines.
Renning Pang, Tian Lan, Leyuan Liu +3
University of Electronic Science and Technology of China
Multi-turn, long-horizon tasks are increasingly common for large language models (LLMs), but solving them typically requires many sequential model invocations, accumulating substantial inference costs. Here, we study cost-aware multi-turn LLM routing: selecting which model to invoke at each turn from a model pool, given a fixed cost budget. We propose MTRouter, which encodes the interaction history and candidate models into joint history-model embeddings, and learns an outcome estimator from logged trajectories to predict turn-level model utility. Experiments show that MTRouter improves the performance-cost trade-off: on ScienceWorld, it surpasses GPT-5 while reducing total cost by 58.7%; on Humanity's Last Exam (HLE), it achieves competitive accuracy while reducing total cost by 43.4% relative to GPT-5, and these gains even carry over to held-out tasks. Further analyses reveal several mechanisms underlying its effectiveness: relative to prior multi-turn routers, MTRouter makes fewer model switches, is more tolerant to transient errors, and exhibits emergent specialization across models. Code: https://github.com/ZhangYiqun018/MTRouter
Yiqun Zhang, Hao Li, Zihan Wang +6
School of Computer Science and Engineering, Northeastern University Shenyang 110819, China · Shanghai Artificial Intelligence Laboratory