基于代理奖励的上下文感知上下文赌博机用于LLM路由

# 面向相关性的上下文强盗算法与替代奖励用于大语言模型路由
来源：https://arxiv.org/html/2607.09015
Ajay Narayanan Sridhar, Ronak Singh, Mehrdad Mahdavi, Vijaykrishnan Narayanan
宾夕法尼亚州立大学 \{afs6372,rjs7006,mzm616,vxn9\}@psu\.edu

###### 摘要
本文研究具有相关性臂和机器学习模型生成的替代奖励信号的上下文强盗问题，其动机源于大语言模型（LLM）路由等应用。与仅依赖强盗反馈并假设臂间条件独立的经典上下文强盗不同，我们的场景允许上下文相关的臂间相关性以及可能带有噪声或 misspecified 的辅助奖励信息。我们提出两种互补设计来利用此类替代奖励：一种耦合的奖励混合方法，在替代信号可靠时将真实奖励与替代奖励合并以加速学习；另一种解耦的预测混合方法，分别维护强盗反馈和替代奖励的估计器，并自适应地组合它们的预测。这种解耦对替代 misspecification 具有鲁棒性，在最坏情况下恢复与仅奖励强盗方法相当的遗憾保证，同时在替代预测足够信息时实现改进的遗憾。我们为这两种方法提供理论遗憾分析，并在 LLM 路由基准上评估它们在准确性与成本权衡下的表现。结果表明，与标准上下文强盗基线和强静态路由方法相比，采样效率更高，准确性-成本权衡持续更优。

## 1 引言
大语言模型（LLM）的快速普及使得终端用户越来越难以跟踪进展并针对其特定需求选择最佳模型。目前，存在众多专有 LLM 提供商[38 (https://arxiv.org/html/2607.09015#bib.bib22),23 (https://arxiv.org/html/2607.09015#bib.bib23),51 (https://arxiv.org/html/2607.09015#bib.bib24)]，此外还有数千个通过 Hugging Face[28 (https://arxiv.org/html/2607.09015#bib.bib21)] 等仓库公开可用的模型。这种丰富性带来了一个实际的系统问题：对于给定查询，应该调用哪个模型？答案很少是最准确的模型，因为推理会产生非平凡的成本（例如定价、延迟、计算）。在许多应用中，目标是*准确性与成本权衡*：如果某个模型显著更便宜或更快，那么准确度稍低的模型也可能更可取，且最佳选择随上下文变化。现有的统一接口通过模型级联[11 (https://arxiv.org/html/2607.09015#bib.bib25),26 (https://arxiv.org/html/2607.09015#bib.bib26)]、集成[30 (https://arxiv.org/html/2607.09015#bib.bib28)]和路由[36 (https://arxiv.org/html/2607.09015#bib.bib10),37 (https://arxiv.org/html/2607.09015#bib.bib20),55 (https://arxiv.org/html/2607.09015#bib.bib27),42 (https://arxiv.org/html/2607.09015#bib.bib29),33 (https://arxiv.org/html/2607.09015#bib.bib30)] 来解决这一挑战。我们关注路由：每查询选择一个模型以最大化用户定义的效用。一种常见的简化是将 LLM 路由建模为*上下文多臂强盗*，其中每个 LLM 被视为给定查询上下文的条件独立臂，并且只能观察到所选臂的奖励，从而需要昂贵的探索。在 dd 维线性设置中，上下文由 dd 维嵌入表示，每个臂的期望奖励假设为该嵌入的线性函数，标准方法实现了遗憾 RS=O(dKTlog(T/d))R\_\{S\}=~O(\\sqrt\{dKT\\log\(T/d\)\)[20 (https://arxiv.org/html/2607.09015#bib.bib4)]，给定 KK 个臂（LLM）和 TT 个查询流，其中遗憾是相对于最佳上下文相关动作的累积损失。然而，这种条件独立抽象通常过于粗糙：由于共享的预训练数据、对齐流程和架构，模型表现出查询相关的相关性。利用这种相关性可以减少关于未玩臂的不确定性，并降低有效探索负担。LLM 路由还提供了标准强盗设置中基本缺失的辅助信息来源：离线性能数据。基准测试或历史日志可以训练机器学习（ML）预测器，将查询上下文映射到每个臂的奖励估计。在在线路由过程中，这些估计可以作为未玩臂的*替代奖励*。尽管替代奖励可能有偏或带噪声，它们仍能揭示臂的相对质量。关键挑战是在有用时利用替代奖励，但在其被 misspecified 时不过度信任。这激发了我们的核心研究问题：

> *我们能否设计上下文强盗算法，系统性地利用上下文相关的模型间相关性和辅助的 ML 预测替代奖励来加速学习，同时保持对替代 misspecification 的鲁棒性？*

为解决此问题，我们研究具有*相关性感知*图反馈和辅助*替代奖励*的上下文强盗。每轮，学习器观察到查询上下文以及关于臂间关系的上下文相关辅助信息，这些信息用于形成一个反馈图，该图识别出一个小的附加臂集合，这些臂的反馈在给定所选臂的情况下最具信息量。在选择了臂并观察到其实现的奖励后，学习器还会收到该图所选集合中臂的 ML 预测替代奖励，从而提供超出所选臂的部分多臂辅助信息。我们首先提出一种耦合的*奖励混合*方法，**C**orrelation-**A**ware **B**andits with **S**urrogates **C**oupled (CABS-C)，该方法基于 SquareCB[54 (https://arxiv.org/html/2607.09015#bib.bib11),53 (https://arxiv.org/html/2607.09015#bib.bib45)] 的图反馈变体，通过合并去偏的真实奖励与替代奖励来拟合一个单一的上下文模型。这种耦合有效地增加了每轮的信息观测数量，将探索因子从 KK 改进为 K/(m+1)K/(m+1)，其中 mm 是每轮揭示替代奖励的附加臂数量。耦合这些观测的代价是对替代误差的额外敏感性。对于线性强盗，我们证明遗憾的规模为 RC=O~(dKTlog(T/d)/(m+1)+εnTK2/(m+1))R\_\{C\}=\\widetilde\{O\}\\\(\\left\(\\sqrt\{dKT\\log\(T/d\)/\(m+1\)\}\+\\varepsilon\_\{n\}\\sqrt\{TK^\{2\}/\(m+1\)\}\\right\)，其中 εn\\varepsilon\_\{n\} 量化替代噪声/misspecification 的最坏情况幅度（见假设 4.4 (https://arxiv.org/html/2607.09015#S4.Thmtheorem4)）。前面的遗憾界限明确了这种权衡：准确的替代减少了有效探索负担，而大的替代误差可能占主导地位，使紧密耦合变得脆弱。受此鲁棒性问题启发，我们提出一种解耦的*预测混合*策略，**C**orrelation-**A**ware **B**andits with **S**urrogates **D**ecoupled (CABS-D)，将 (i) 仅奖励上下文强盗；和 (ii) 相关性感知（由替代诱导的图反馈）强盗 (CABS-C) 视为两个专家，并使用自适应专家聚合主控器（类似于自适应 Hedge 方法[1 (https://arxiv.org/html/2607.09015#bib.bib87),17 (https://arxiv.org/html/2607.09015#bib.bib84)]）进行组合。由此产生的元强盗提供了两全其美的保证，RD=O(min{RS,RC})R\_\{D\}=O\\\(\\min\\left\\\{R\_\{S\},R\_\{C\}\\right\\\}\\\)，使我们能够在最坏情况下匹配标准上下文强盗的速率（加上轻微的额外开销），同时在替代反馈可靠时继承相关性驱动的增益。我们评估了我们的 LLM 路由方法，观察到与在线强盗和静态基线相比，采样效率更高，准确性-成本权衡更优。

##### 贡献
总之，我们的贡献包括：
- • 我们引入了*具有替代奖励的相关性感知上下文强盗*，其中上下文相关的臂间关系信号产生图反馈结构，辅助预测器为图指定的臂提供替代奖励，超出所选臂观察到的真实奖励。
- • 我们提出了 CABS-C（耦合*奖励混合*）和 CABS-D（解耦*预测混合*），阐明了何时紧密耦合有益以及何时解耦对鲁棒性必要。
- • 我们建立了遗憾界限，明确分离了相关性驱动的增益（降低的有效探索）与替代噪声/misspecification，包括 CABS-D 的两全其美保证，在最坏情况下匹配标准上下文强盗，同时在温和条件下实现随替代奖励数量逆尺度改进的遗憾。
- • 我们在 LLM 路由基准上评估了我们的方法，并展示了相对于在线强盗基线和静态路由策略更高的采样效率和更强的准确性-成本权衡。

最终，这些结果表明利用预测的替代奖励为 LLM 路由提供了强大的框架，产生了显著的遗憾减少。具体而言，我们的方法有效地在全信息和强盗设置之间进行插值，性能增益根据替代奖励质量和 LLM 间的相关性平滑变化。这一发现可能超出此处考虑的具体场景而具有独立意义。

## 2 相关工作
在本节中，我们讨论与我们的方法最直接相关的工作，并突出与我们方法的区别。关于多臂强盗和 LLM 路由文献的更全面概述，包括遗憾界限和理论保证的详细比较，推迟到附录 A (https://arxiv.org/html/2607.09015#A1)。

##### 上下文强盗、图反馈和专家聚合。
我们的工作建立在诸如 SquareCB[20 (https://arxiv.org/html/2607.09015#bib.bib4)]、LinearUCB[15 (https://arxiv.org/html/2607.09015#bib.bib17)] 和 NeuralUCB[56 (https://arxiv.org/html/2607.09015#bib.bib3)] 等上下文强盗之上，并且与具有图反馈的上下文强盗[53 (https://arxiv.org/html/2607.09015#bib.bib45),54 (https://arxiv.org/html/2607.09015#bib.bib11)] 最为接近。与 SquareCB-G[54 (https://arxiv.org/html/2607.09015#bib.bib11)]（观察图邻居的*真实*奖励）和 SquareCB-UG[53 (https://arxiv.org/html/2607.09015#bib.bib45)]（在动作选择后学习未知图）不同，我们仅观察所选臂的真实奖励，并从动作选择前已知的上下文相关图中接收*替代*奖励。CABS-D 与 Hedge/AdaHedge 风格的专家聚合[22 (https://arxiv.org/html/2607.09015#bib.bib85),17 (https://arxiv.org/html/2607.09015#bib.bib84)] 和 Corral 风格的强盗主控器[1 (https://arxiv.org/html/2607.09015#bib.bib87)] 相关，但特别适应于标准强盗反馈和替代图反馈之间。辅助反馈方法[13 (https://arxiv.org/html/2607.09015#bib.bib76),46 (https://arxiv.org/html/2607.09015#bib.bib77),29 (https://arxiv.org/html/2607.09015#bib.bib78)] 主要使用外部信号来改进对*已玩*臂的估计，而我们则将替代反馈传播到多个臂。参见[31 (https://arxiv.org/html/2607.09015#bib.bib2)] 和附录 A (https://arxiv.org/html/2607.09015#A1) 以获取更广泛的概述。

##### LLM 路由。
LLM 路由在质量、成本或延迟约束下为每个查询选择模型。先前的工作包括从偏好或性能数据训练的离线路由器[37 (https://arxiv.org/html/2607.09015#bib.bib20),55 (https://arxiv.org/html/2607.09015#bib.bib27),42 (https://arxiv.org/html/2607.09015#bib.bib29),12 (https://arxiv.org/html/2607.09015#bib.bib15),18 (https://arxiv.org/html/2607.09015#bib.bib71),41 (https://arxiv.org/html/2607.09015#bib.bib48)]、成本-性能路由基准[25 (https://arxiv.org/html/2607.09015#bib.bib16),41 (https://arxiv.org/html/2607.09015#bib.bib48)]，以及基于上下文强盗或决斗强盗的在线路由方法[36 (https://arxiv.org/html/2607.09015#bib.bib10),33 (https://arxiv.org/html/2607.09015#bib.bib30),48 (https://arxiv.org/html/2607.09015#bib.bib31),50 (https://arxiv.org/html/2607.09015#bib.bib69),16 (https://arxiv.org/html/2607.09015#bib.bib70),14 (https://arxiv.org/html/2607.09015#bib.bib1)]。现有的在线路由策略大多不*明确*建模 LLM 之间的内在相关性（除了隐含的表示共享），这限制了当模型行为高度相关时的采样效率。为了弥补这一差距，我们的相关性感知路由框架利用上下文相关的臂间关系，并整合辅助替代信号，同时保持对替代 misspecification 的鲁棒性，从而在不同成本范围内实现改进的路由效用。

![图例](https://arxiv.org/html/2607.09015/extracted/6228957/Img_GraphicalAbstract.png)
图 1：LLM 路由任务及所提出的 CABS-C/CABS-D 在线学习流水线概述。路由器在成本敏感性参数 ρ\\rho 下选择 LLM，而 AO、RO 和 RS 分别表示 CABS-C/CABS-D 算法使用的亲和性预言机、奖励预言机和回归求解器。

## 3 问题设定
我们考虑一个在线 LLM 路由问题设定，在离散轮次 T 的有限时间范围内进行操作，轮次索引为 t∈[T]:={1,2,...,T}t\\in[T]:=\\\{1,2,\\ldots,T\\\}。路由器（学习器）可以访问一个固定的 KK 个不同 LLM（臂）的池，表示为集合 K=[K]:={1,2,...,K}\\mathcal{K}=[K]:=\\\{1,2,\\ldots,K\\\}。在每一轮 t∈[T]t\\in[T] 中，学习器观察到一个提示及其上下文嵌入向量 xt∈X⊆Rd\\bm{x}\_\{t\}\\in\\mathcal{X}\\subseteq\\mathbb{R}^\{d\}，其中 X\\mathcal{X} 是一个有界的上下文空间，必须选择一个 LLM it∈[K]i\_\{t\}\\in[K] 来处理该提示。所选模型 iti\_\{t\} 产生一个结果 ot\\bm{o}\_\{t\} 并产生一个成本感知的奖励 rt,it(xt)r\_\{t,i\_\{t\}\}(\\bm{x}\_\{t\})；为方便起见，我们写为 rt,itr\_\{t,i\_\{t\}\} 并定义相应的损失 lt,it=1−rt,it\\ell\_\{t,i\_\{t\}\}=1-r\_\{t,i\_\{t\}\}。奖励通常捕捉生成质量（例如准确性、有用性）并权衡其与操作约束（例如延迟、令牌成本）。我们明确将奖励和损失限制在 [0,1][0,1] 区间，这是标准的且对遗憾分析必要。图 1 (https://arxiv.org/html/2607.09015#S2.F1) 提供了此 LLM 路由任务及所提出的 CABS-C/CABS-D 在线学习流水线的概述。

为了利用 LLM 之间查询相关的相关性以及来自离线数据的辅助奖励预测，我们将 LLM 路由公式化为具有替代奖励的相关性感知上下文强盗。在每一轮 tt 中，除了 xt\\bm{x}\_\{t\}，学习器还从亲和性预言机（AO）观察到臂间辅助信息，该信息表现为一个相关性矩阵 Rt∈RK×K\\bm{R}\_\{t\}\\in\\mathbb{R}^\{K\\times K\} 或一个随时间变化、上下文相关的有向反馈图 GtG\_\{t\}，定义在 [K][K] 上，其邻接矩阵为 At∈{0,1}K×K\\bm{A}\_\{t\}\\in\\\{0,1\\\}^\{K\\times K\}，其中 At,(i,j)=1A\_\{t,(i,j)\}=1 表示从臂 ii 到臂 jj 的边。默认情况下，对所有 i∈[K]i\\in[K] 有 At,(i,i)=1A\_\{t,(i,i)\}=1。LLM 之间的辅助信息量化了不同模型在特定上下文下的性能缩放情况。在选择臂 iti\_\{t\} 后，学习器仅观察到所选臂 iti\_\{t\} 的真实实现奖励。然而，对于反馈图指定的其他臂 j≠itj\\neq i\_\{t\}，学习器会从某个来源接收替代奖励 st,js\_\{t,j\}。