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

• URL: http://arxiv.org/abs/2506.17670v1
• Date: Sat, 21 Jun 2025 10:01:46 GMT
• Title: Online Multi-LLM Selection via Contextual Bandits under Unstructured Context Evolution
• Authors: Manhin Poon, XiangXiang Dai, Xutong Liu, Fang Kong, John C. S. Lui, Jinhang Zuo,
• Abstract summary: Large language models (LLMs) exhibit diverse response behaviors, costs, and strengths.<n>We develop a LinUCB-based algorithm that provably achieves sublinear regret without relying on future context prediction.<n>Our algorithms are theoretically grounded and require no offline fine-tuning or dataset-specific training.
• Score: 31.385024956599676
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Can Prompt Difficulty be Online Predicted for Accelerating RL Finetuning of Reasoning Models? [62.579951798437115]
  This work investigates iterative approximate evaluation for arbitrary prompts.<n>It introduces Model Predictive Prompt Selection (MoPPS), a Bayesian risk-predictive framework.<n>MoPPS reliably predicts prompt difficulty and accelerates training with significantly reduced rollouts.
  arXiv  Detail & Related papers  (2025-07-07T03:20:52Z)
• Towards Efficient Multi-LLM Inference: Characterization and Analysis of LLM Routing and Hierarchical Techniques [14.892995952768352]
  Language Models (LMs) have excelled at tasks like text generation, summarization, and question answering.<n>Their inference remains computationally expensive and energy intensive in settings with limited hardware, power, or bandwidth.<n>Recent approaches have introduced multi LLM intelligent model selection strategies that dynamically allocate computational resources based on query complexity.
  arXiv  Detail & Related papers  (2025-06-06T23:13:08Z)
• Scaling Autonomous Agents via Automatic Reward Modeling And Planning [52.39395405893965]
  Large language models (LLMs) have demonstrated remarkable capabilities across a range of tasks.<n>However, they still struggle with problems requiring multi-step decision-making and environmental feedback.<n>We propose a framework that can automatically learn a reward model from the environment without human annotations.
  arXiv  Detail & Related papers  (2025-02-17T18:49:25Z)
• LLM-Lasso: A Robust Framework for Domain-Informed Feature Selection and Regularization [59.75242204923353]
  We introduce LLM-Lasso, a framework that leverages large language models (LLMs) to guide feature selection in Lasso regression.<n>LLMs generate penalty factors for each feature, which are converted into weights for the Lasso penalty using a simple, tunable model.<n>Features identified as more relevant by the LLM receive lower penalties, increasing their likelihood of being retained in the final model.
  arXiv  Detail & Related papers  (2025-02-15T02:55:22Z)
• LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routing [3.090041654375235]
  We present a novel framework that formulates the LLM selection process as a multi-armed bandit problem.<n>Our approach incorporates a preference-conditioned dynamic routing mechanism, allowing users to specify their preferences at inference time.<n>Our method achieves significant improvements in both accuracy and cost-effectiveness across various LLM platforms.
  arXiv  Detail & Related papers  (2025-02-04T22:09:43Z)
• Multi-Agent Conversational Online Learning for Adaptive LLM Response Identification [31.120233988281328]
  This paper introduces textitMACO (underlineMulti-underlineAgent underlineConversational underlineOnline Learning for Adaptive LLM Response Identification)<n>A novel conversational mechanism is proposed to adaptively conduct conversations for soliciting user preferences.<n>cadi significantly outperforms the current state-of-the-art in online LLM response identification.
  arXiv  Detail & Related papers  (2025-01-03T14:59:38Z)
• Self-Instructed Derived Prompt Generation Meets In-Context Learning: Unlocking New Potential of Black-Box LLMs [30.333277284839053]
  Large language models (LLMs) have shown success in generating high-quality responses. Existing methods to enhance response quality often involve a prompt refinement model. We introduce a self-instructed in-context learning framework that empowers LLMs to deliver more effective responses.
  arXiv  Detail & Related papers  (2024-09-03T02:42:39Z)
• QPO: Query-dependent Prompt Optimization via Multi-Loop Offline Reinforcement Learning [58.767866109043055]
  We introduce Query-dependent Prompt Optimization (QPO), which iteratively fine-tune a small pretrained language model to generate optimal prompts tailored to the input queries.<n>We derive insights from offline prompting demonstration data, which already exists in large quantities as a by-product of benchmarking diverse prompts on open-sourced tasks.<n> Experiments on various LLM scales and diverse NLP and math tasks demonstrate the efficacy and cost-efficiency of our method in both zero-shot and few-shot scenarios.
  arXiv  Detail & Related papers  (2024-08-20T03:06:48Z)
• Self-Exploring Language Models: Active Preference Elicitation for Online Alignment [88.56809269990625]
  We propose a bilevel objective optimistically biased towards potentially high-reward responses to actively explore out-of-distribution regions. Our experimental results demonstrate that when fine-tuned on Zephyr-7B-SFT and Llama-3-8B-Instruct models, Self-Exploring Language Models (SELM) significantly boosts the performance on instruction-following benchmarks.
  arXiv  Detail & Related papers  (2024-05-29T17:59:07Z)
• Query-Dependent Prompt Evaluation and Optimization with Offline Inverse RL [62.824464372594576]
  We aim to enhance arithmetic reasoning ability of Large Language Models (LLMs) through zero-shot prompt optimization. We identify a previously overlooked objective of query dependency in such optimization. We introduce Prompt-OIRL, which harnesses offline inverse reinforcement learning to draw insights from offline prompting demonstration data.
  arXiv  Detail & Related papers  (2023-09-13T01:12:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.