# Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution

arXiv: https://arxiv.org/abs/2506.17670 · HTML: https://mlsanity.com/paper/2506.17670/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 21 Jun 2025.

## Builds on (most cited first, 30 of 33)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [PromptAgent: Strategic Planning with Language Models Enables Expert-level Prompt Optimization](https://mlsanity.com/paper/2310.16427/) (2023)
- [More Agents Is All You Need](https://mlsanity.com/paper/2402.05120/) (2024)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Alita: Generalist Agent Enabling Scalable Agentic Reasoning with Minimal Predefinition and Maximal Self-Evolution](https://mlsanity.com/paper/2505.20286/) (2025)
- [Universal Model Routing for Efficient LLM Inference](https://mlsanity.com/paper/2502.08773/) (2025)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [MixLLM: Dynamic Routing in Mixed Large Language Models](https://mlsanity.com/paper/2502.18482/) (2025)
- [Offline Reinforcement Learning for LLM Multi-Step Reasoning](https://mlsanity.com/paper/2412.16145/) (2024)
- [MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs](https://mlsanity.com/paper/2407.10834/) (2024)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Efficient Prompt Optimization Through the Lens of Best Arm Identification](https://mlsanity.com/paper/2402.09723/) (2024)
- [Optimizing Model Selection for Compound AI Systems](https://mlsanity.com/paper/2502.14815/) (2025)
- [Eagle: Efficient Training-Free Router for Multi-LLM Inference](https://mlsanity.com/paper/2409.15518/) (2024)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Hierarchical Conversational Preference Elicitation with Bandit Feedback](https://mlsanity.com/paper/2209.06129/) (2022)
- [A Multi-Agent Conversational Bandit Approach to Online Evaluation and Selection of User-Aligned LLM Responses](https://mlsanity.com/paper/2501.01849/) (2025)
- [Improving Large Language Model Planning with Action Sequence Similarity](https://mlsanity.com/paper/2505.01009/) (2025)

## Built on by (most cited first, 19 of 19)

- [Slm-mux: Orchestrating small language models for reasoning](https://mlsanity.com/paper/2510.05077/) (2025)
- [Federate the Router: Learning Language Model Routers with Sparse and Decentralized Evaluations](https://mlsanity.com/paper/2601.22318/) (2026)
- [WISERouter: LLM Routing with Workload Budget Constraint](https://mlsanity.com/paper/2607.23765/) (2026)
- [Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation](https://mlsanity.com/paper/2608.04333/) (2026)
- [AGFT: An Adaptive GPU Frequency Tuner for Real-Time LLM Inference Optimization](https://mlsanity.com/paper/2508.01744/) (2025)
- [Ghost in the Transformer: Detecting Model Reuse with Invariant Spectral Signatures](https://mlsanity.com/paper/2511.06390/) (2025)
- [A Component-Based Survey of Interactions between Large Language Models and Multi-Armed Bandits](https://mlsanity.com/paper/2601.12945/) (2026)
- [CASCADE: Case-Based Continual Adaptation for Large Language Models During Deployment](https://mlsanity.com/paper/2605.06702/) (2026)
- [Latency-Quality Routing for Functionally Equivalent Tools in LLM Agents](https://mlsanity.com/paper/2605.14241/) (2026)
- [Large Language Model Selection with Limited Annotations](https://mlsanity.com/paper/2605.24981/) (2026)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)
- [Large Language Model Selection with Limited Annotations](https://mlsanity.com/paper/2510.09418/) (2025)
- [POLAR: Online Learning for LoRA Adapter Caching and Routing in Edge LLM Serving](https://mlsanity.com/paper/2604.16583/) (2026)
- [Bandit Learning in General Open Multi-agent Systems](https://mlsanity.com/paper/2605.06202/) (2026)
- [PYTHALAB-MERA: Validation-Grounded Memory, Retrieval, and Acceptance Control for Frozen-LLM Coding Agents](https://mlsanity.com/paper/2605.08468/) (2026)
- [Iterative Critique-and-Routing Controller for Multi-Agent Systems with Heterogeneous LLMs](https://mlsanity.com/paper/2605.08686/) (2026)
- [Dead text or binding clause? Measuring and restoring constraint influence in black-box LLM dialogues](https://mlsanity.com/paper/2608.12599/) (2026)
- [OrchSLM: Probing the Dynamics of Small Language Model Orchestration](https://mlsanity.com/paper/2609.13470/) (2026)
- [CERA-MoA: Co-Evolving Routing Mechanisms with Continually Learning LLM Agents](https://mlsanity.com/paper/2609.18779/) (2026)

## Abstract (arXiv)

Large language models (LLMs) exhibit diverse response behaviors, costs, and strengths, making it challenging to select the most suitable LLM for a given user query. We study the problem of adaptive multi-LLM selection in an online setting, where the learner interacts with users through multi-step query refinement and must choose LLMs sequentially without access to offline datasets or model internals. A key challenge arises from unstructured context evolution: the prompt dynamically changes in response to previous model outputs via a black-box process, which cannot be simulated, modeled, or learned. To address this, we propose the first contextual bandit framework for sequential LLM selection under unstructured prompt dynamics. We formalize a notion of myopic regret and develop a LinUCB-based algorithm that provably achieves sublinear regret without relying on future context prediction. We further introduce budget-aware and positionally-aware (favoring early-stage satisfaction) extensions to accommodate variable query costs and user preferences for early high-quality responses. Our algorithms are theoretically grounded and require no offline fine-tuning or dataset-specific training. Experiments on diverse benchmarks demonstrate that our methods outperform existing LLM routing strategies in both accuracy and cost-efficiency, validating the power of contextual bandits for real-time, adaptive LLM selection.