基于时变需求的约束赌博机在线LLM选择

# 基于时变需求的约束赌博机在线大语言模型选择
来源: https://arxiv.org/html/2606.17489
黄寅 刘庆松 徐洁\. 黄寅和徐洁就职于佛罗里达大学电气与计算机工程系\. 邮箱: {yin\.huang, jie\.xu}@ufl\.edu\. 刘庆松就职于马萨诸塞大学阿默斯特分校信息与计算机科学学院曼宁学院\. 邮箱: qingsongliu@umass\.edu\.

###### 摘要

大型语言模型（LLM）越来越多地部署在边缘-云端推理系统中，以处理具有异构准确性、延迟和成本特征的多样化用户任务。为每个传入任务选择合适的LLM对于确保服务质量和高效资源利用至关重要。然而，模型的异构性、随机且未知的性能特征以及时变的任务需求使得静态选择策略不再适用。实际部署中往往施加硬性资源预算（如货币支出限制）以及软性服务水平要求（如延迟保证）。这些约束给在线决策带来了额外挑战。我们将此问题建模为一种约束随机赌博机学习任务，其中学习器在同时存在打包型（硬）约束和覆盖型（软）约束的情况下顺序选择模型，并适应时变的任务需求。学习器无法获取底层奖励、成本或延迟分布，必须依赖部分反馈。我们开发了一种新颖的在线学习算法，利用置信界估计和需求预测来平衡奖励最大化与长期约束满足。我们提供了理论保证，表明相对于拥有完整信息的离线基准，该算法实现了亚线性遗憾和亚线性覆盖约束违反。在合成工作负载上的实验结果表明，我们的方法在动态、资源受限的环境中具有有效性和鲁棒性。

###### 索引词：

协同边缘推理，多臂赌博机，LLM选择，赌博机约束。

## 1 引言

大型语言模型（LLM）越来越多地部署在真实系统中，以支持生成、摘要和问答等任务。在协同边缘-云端推理系统中，移动设备将传入请求卸载到云服务器，在那里可以从一组预部署的LLM中进行选择。一个核心挑战是如何为传入任务选择最合适的模型，因为模型能力存在异构性。大多数现有方法依赖于静态选择，在整个部署过程中固定使用一个LLM\[35 (https://arxiv.org/html/2606.17489#bib.bib6),36 (https://arxiv.org/html/2606.17489#bib.bib7)\]。然而，在新的或不断变化的场景中，这种一刀切的方法往往表现不佳。由于生成多样性\[11 (https://arxiv.org/html/2606.17489#bib.bib39)\]，较小的模型可能更适合某些提示，而数据漂移\[10 (https://arxiv.org/html/2606.17489#bib.bib40)\]可能会随时间改变任务特征。这些问题要求采用一种适应当前工作负载的在线模型选择方法\[45 (https://arxiv.org/html/2606.17489#bib.bib10)\]。重要的是，不同的LLM通常表现出不同且不确定的准确性、延迟和货币成本。这使得在线模型选择问题自然适合赌博机学习框架，系统必须在探索与利用之间取得平衡，同时适应随机的奖励和成本反馈。

在线LLM选择中的另一个挑战在于满足多种资源约束，这些约束在形式和严格程度上往往各不相同。这些约束可以从两个维度大致分类。首先，约束可以是硬性的，意味着必须始终满足，否则系统将停止；也可以是软性的，只要平均性能可接受，偶尔的违反是允许的。其次，约束可以是打包型或覆盖型：打包型约束要求累积资源使用不超过固定预算（即 ≤），而覆盖型约束要求累积服务提供达到最低阈值（即 ≥）\[27 (https://arxiv.org/html/2606.17489#bib.bib20),42 (https://arxiv.org/html/2606.17489#bib.bib26)\]。我们的问题涉及两种类型。首先，LLM通常根据其生成的令牌数产生货币成本——这种成本是随机的，因为令牌数随任务和模型而变化\[44 (https://arxiv.org/html/2606.17489#bib.bib38),21 (https://arxiv.org/html/2606.17489#bib.bib43)\]。在许多部署中，用户或提供商面临固定预算，超出可能导致服务终止。这定义了一个硬性打包约束。其次，许多应用施加延迟服务等级协议（SLA），要求一定比例的任务在目标截止时间内完成\[48 (https://arxiv.org/html/2606.17489#bib.bib41)\]。偶尔的违反是可容忍的，但过多的截止时间错过会降低用户体验。这定义了一个软性覆盖约束。这些双向约束反映了根本不同的目标——成本控制与服务质量的对比——并需要量身定制的算法处理。

第三个挑战来自任务到达率随时间的动态性和不确定性。在边缘-云端推理系统中，每个时隙到达的任务数量可能因用户活动、时间模式或外部条件而显著变化\[8 (https://arxiv.org/html/2606.17489#bib.bib42)\]。为确保低开销并减少冷启动延迟，通常在每个时隙开始时选择一个单一模型来服务该时段内到达的所有任务。虽然这种预选避免了每任务的切换成本，但它使得模型决策对任务量的变化特别敏感。忽略这种波动可能导致性能下降：轻负载可能容忍较慢或更便宜的模型，而重负载可能需要更快、更昂贵的模型以满足延迟约束。幸运的是，实践中通常可以获得预测信息——例如来自历史工作负载轨迹或预测性需求模型——并可在决策前用于估计需求规模。将这些预测整合到学习算法中，可以在条件变化时实现更明智和更鲁棒的模型选择，特别是在预算约束或时间敏感的SLA下。

在本文中，我们针对异构边缘-云端推理系统中的任务卸载场景，形式化了在线LLM模型选择问题，明确解决上述挑战。我们考虑存在多个可用LLM（例如，边缘和云端的不同模型大小或提供商）的设置，其中任务随时间连续到达，必须分配给合适的模型进行推理。我们的公式化捕捉了三个关键方面：(i) 需要在每个决策点动态选择候选模型，而不是承诺静态分配；(ii) 存在基于令牌的推理成本的硬预算约束以及确保服务质量的软延迟SLA；(iii) 存在影响成本和响应性的时变任务量。通过整合这些元素，所提出的框架将经典的卸载和调度公式推广到LLM推理设置，其中货币效率和延迟保证是主要设计考虑。

为了解决这个在线模型选择问题，我们将其建模为一个约束随机多臂赌博机实例，类似于带背包的赌博机框架，其中系统面临硬预算约束和软延迟SLA，分别对应打包型和覆盖型约束。我们开发了一种新的学习算法——COPAC-UCB，它集成了置信引导估计：对奖励和覆盖型约束采用乐观（通过上置信界，UCB），对打包型约束采用悲观（通过下置信界，LCB），并结合拉格朗日正则化以在不确定性下自适应地平衡性能和可行性。为了在需求变化下提高响应性，COPAC-UCB包含一个预测组件，使用黑盒预测器估计累积任务负载。这些需求估计有助于增强决策以更有效地满足约束。同时，该算法通过在线梯度下降更新每个约束的对偶变量（虚拟价格），有效抑制可能违反预算或SLA的模型。通过结合预测性指导、乐观探索和自适应成本信号，COPAC-UCB在时间上平衡了奖励最大化与安全资源使用。本文的主要贡献总结如下：

- •我们提出了边缘-云端协同推理系统中一个新的在线LLM模型选择问题，明确纳入了时变任务需求、货币和延迟约束以及模型异构性。
- •我们将此问题建模为同时具有打包和覆盖约束的随机赌博机，并提出了一种新颖算法——COPAC-UCB，该算法结合了置信界估计与基于拉格朗日的资源平衡。该算法还利用对未来任务负载的预测来指导动态需求下的成本感知模型选择。
- •我们从理论上证明，COPAC-UCB实现了亚线性遗憾，同时以高概率满足预算和延迟约束，确保了随时间的安全高效决策。
- •我们通过在真实工作负载轨迹上的模拟评估了我们的算法，表明在预算下，COPAC-UCB相比几种竞争基线实现了更高的效用和更好的延迟合规性。

## 2 相关工作

推理选择与卸载优化近年来，通过自适应选择和卸载提高LLM推理效率引起了越来越多的兴趣。传统方法\[35 (https://arxiv.org/html/2606.17489#bib.bib6),36 (https://arxiv.org/html/2606.17489#bib.bib7),40 (https://arxiv.org/html/2606.17489#bib.bib8),16 (https://arxiv.org/html/2606.17489#bib.bib9)\]通常采用离线通过基准分数或困惑度选择的静态模型，但忽略了不同LLM之间的输入依赖性变化。最近的工作提出了基于在线学习的模型选择，以在不确定性下平衡准确性、延迟和货币成本。例如，\[45 (https://arxiv.org/html/2606.17489#bib.bib10)\]通过时变赌博机框架对动态性能漂移进行建模。同时，卸载方法决定是否在本地、边缘或云端运行任务，优化延迟、能量或预算\[30 (https://arxiv.org/html/2606.17489#bib.bib12),3 (https://arxiv.org/html/2606.17489#bib.bib13),49 (https://arxiv.org/html/2606.17489#bib.bib14),13 (https://arxiv.org/html/2606.17489#bib.bib15),29 (https://arxiv.org/html/2606.17489#bib.bib45),47 (https://arxiv.org/html/2606.17489#bib.bib46),14 (https://arxiv.org/html/2606.17489#bib.bib47),19 (https://arxiv.org/html/2606.17489#bib.bib3),20 (https://arxiv.org/html/2606.17489#bib.bib4)\]。其中，\[13 (https://arxiv.org/html/2606.17489#bib.bib15)\]引入了一种组合赌博机方法，用于成本约束下的LLM放置。这些工作强调了在动态、资源受限的LLM推理设置中进行原则性在线决策的价值。然而，这些工作都没有同时处理打包和覆盖约束，也没有明确纳入时变需求，而这正是我们公式的核心。

带有臂选择约束的赌博机带有臂选择约束的赌博机对在线决策进行建模，其中每个动作产生奖励的同时消耗资源或满足额外约束。一个典型的例子是带预算约束的赌博机框架\[7 (https://arxiv.org/html/2606.17489#bib.bib16)\]，其中每个臂产生随机奖励和资源消耗，目标是在耗尽固定预算之前最大化累积奖励。后续工作\[2 (https://arxiv.org/html/2606.17489#bib.bib17)\]开发了基于原始-对偶和UCB的算法，在平稳设置下具有亚线性遗憾保证。最近的扩展引入了覆盖型约束以捕捉公平性或服务水平保证。例如，\[25 (https://arxiv.org/html/2606.17489#bib.bib23),15 (https://arxiv.org/html/2606.17489#bib.bib24),46 (https://arxiv.org/html/2606.17489#bib.bib25)\]执行跨臂的长期比例性或跨组的服务覆盖，建模为需要随时间累积满足的软约束。这些设置通常平衡奖励最大化与约束违反最小化。其他工作线探索了对抗性\[23 (https://arxiv.org/html/2606.17489#bib.bib18),17 (https://arxiv.org/html/2606.17489#bib.bib22)\]、非平稳\[12 (https://arxiv.org/html/2606.17489#bib.bib19)\]以及带有预言机预测的时变设置\[33 (https://arxiv.org/html/2606.17489#bib.bib5),18 (https://arxiv.org/html/2606.17489#bib.bib21)\]，表明侧信息可以改善性能。然而，现有模型很少同时处理打包和覆盖约束，也没有考虑时变、随机的需求。我们的工作通过形式化和分析一个整合所有三个维度的设置来填补这一空白。

学习增强在线算法设计我们的工作与学习增强在线算法文献相关，这些算法利用机器学习预测来增强在线决策\[32 (https://arxiv.org/html/2606.17489#bib.bib28),34 (https://arxiv.org/html/2606.17489#bib.bib27)\]。这些方法通过结合对潜在参数的预测来改善性能，同时保持对对抗性输入的鲁棒性。应用涵盖缓存\[32 (https://arxiv.org/html/2606.17489#bib.bib28)\]、调度\[34 (https://arxiv.org/html/2606.17489#bib.bib27),26 (https://arxiv.org/html/2606.17489#bib.bib29)\]、租或买\[37 (https://arxiv.org/html/2606.17489#bib.bib30)\]、集合覆盖\[9 (https://arxiv.org/html/2606.17489#bib.bib31),4 (https://arxiv.org/html/2606.17489#bib.bib32)\]和匹配\[5 (https://arxiv.org/html/2606.17489#bib.bib33)\]，通常假设在视野开始时已知一个静态预测。最近的工作探索了每轮更新的顺序预测\[38 (https://arxiv.org/html/2606.17489#bib.bib34),39 (https://arxiv.org/html/2606.17489#bib.bib35),43 (https://arxiv.org/html/2606.17489#bib.bib36),24 (https://arxiv.org/html/2606.17489#bib.bib37)\]，主要在全反馈或上下文赌博机设置中。然而，这些模型不包含资源约束。我们通过将顺序预测与混合硬性和软性约束相结合来扩展这一范式，引入了新的算法挑战。

## 3 系统模型

我们考虑一个移动边缘-云端推理系统，其中用户设备将LLM推理任务卸载到基于云的服务。由于设备上的计算和内存有限，设备无法本地运行大规模LLM，因此依赖云端进行推理。系统以离散轮次进行，索引为 t=1,2,...,T，每轮代表一个固定持续时间的时隙。在每轮 t 开始时，系统从一个预部署模型池 A 中选择单个 LLM a_t 来服务在该时隙内到达的任务。这种预选避免了频繁的模型切换，减少了冷启动开销。第 t 轮的任务负载 q_t 在选择时未知，并可能随用户活动或应用需求而波动。尽管学习器必须在没有先验知识的情况下适应