BOHM：复合AI系统的零成本层次归因方法

# 零代价层次化归因：面向复合AI系统  
来源：https://arxiv.org/html/2605.22866  

###### 摘要  

复合AI系统通过层次化的专用组件路由任务。这类系统的归因主要基于Shapley值的方法（SHAP），它将联盟值函数分解为每个组件的边际贡献，并预设能够评估系统在任意组件子集上的表现。这一假设在许多实际部署中无法成立：第三方API、不透明端点以及将路由集中在少数工具上的智能编排器，使得大多数联盟要么无法评估，要么只能通过使用与部署时不同的编排器重新提示来评估。我们引入**BOHM**，这是一种直接从系统已维护的路由权重中提取层次化归因树的方法。叶节点归因是根到叶路径权重的乘积；第k层归因是深度k节点上的诱导分布。该方法零边际成本，无需访问组件内部，并能同时提供每一层的多分辨率归因，这是平面方法在任何评估预算下都无法做到的。两种方法回答不同的问题，并且仅在部署的路由器接近最优路由时才会收敛。在包含18个LLM的三层层次结构（涵盖880个LiveCodeBench问题）上，BOHM在种子平均下得到Kendall τ=0.928；SHAP（可在缓存的通过矩阵上计算）在每种子进行9,000倍以上的联盟评估后达到τ=0.980。在一项多智能体驱动的智能体研究（5种驱动×7个基准，每个单元格N=100个问题，35个单元格，完全覆盖）中，驱动将路由集中在一个工具上（最高份额中位数0.65，范围0.39至1.00），导致SHAP联盟格被稀疏采样；在按混合专家架构与密集架构分组的非均匀[3,2]层次上，单元格级τ(BOHM, SHAP)范围从-0.80到+1.00，并且可通过驱动首选工具是否为基准上的经验最优来预测（均值τ=+0.22 vs ≈+0.01，Δ=+0.21，对应n={9,26}个单元格），这是结构上“不同问题”关系的经验实例化。在外部给定的机构层次（美国人口普查，475个叶节点，4层）上，BOHM同时恢复每一层的真实排名（τ最高达0.722）。BOHM满足效率性、单调性、对称性和弱抑制性；在质量差距较小时对噪声敏感，对层次设计敏感，且不满足Shapley的可加性公理。它应被理解为基于联盟归因的互补基元：一种在存在路由状态时即可计算的多分辨率分解，同时也是路由质量的检验——其与Shapley的分歧本身就具有诊断价值。  

## 1 引言  

现代AI系统日益复杂且层次化。混合专家架构[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4)]、多阶段流水线和智能编排器[37 (https://arxiv.org/html/2605.22866#bib.bib5)]将专用组件组合成树状结构，其中路由器在每一层选择子节点。这并非小众用例。随着AI应用变得更加智能化和工具化，它们越来越多地由相互作用的组件组装而成，这些组件包含中间路由、委派和选择决策[37 (https://arxiv.org/html/2605.22866#bib.bib5),1 (https://arxiv.org/html/2605.22866#bib.bib6)]。在此类系统中，归因需要在组件层面而非仅输入特征层面进行。一个自然的问题随之产生：每个组件对系统整体性能的贡献是多少？  

组件归因的主流方法是基于Shapley值的：SHAP[21 (https://arxiv.org/html/2605.22866#bib.bib1)]及其变体计算每个组件对联盟值函数的边际贡献。该框架有三个结构性特征限制了其在复合AI系统中的应用。  

*第一*，输出是平面的：SHAP生成一个单一的叶节点归因向量，没有层级或分组的分解概念。  

*第二*，成本高昂：精确Shapley值需要O(2^N)次联盟评估，近似方法需要M个样本的O(MN)次评估。  

*第三，也是最有影响的一点，该框架预设了消融能力*：必须能够测量任意子集S的v(S)。对于黑箱、第三方或专有组件，这种测量无法进行。对于将部署路由集中在少数工具上的智能编排器，未部署子集的v(S)必须通过用受限菜单重新提示编排器来获得，这评估的是*不同于*部署时的编排器。在这种情况下仍可计算SHAP，但其结果并非部署系统的属性。  

我们观察到另一个现象。许多层次化系统已采用自适应路由机制，在每个路由器上维护子节点的权重向量[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4),15 (https://arxiv.org/html/2605.22866#bib.bib12),11 (https://arxiv.org/html/2605.22866#bib.bib17)]。这些权重会随观察到的结果随时间变化。在运行中的任何时刻，当前权重状态编码了系统对每个组件的信任程度，无需额外计算。问题在于这种重新框架是否有实质意义。单个路由器上的局部门控分布虽有信息量，但本身并非归因对象：它不将信用分配给叶节点，不跨层次分解，且没有超越“路由器当前选择偏差”的定义语义。BOHM的贡献在于将局部路由权重所诱导的全局对象形式化：一种通过路径乘积实现的多分辨率分解，具有明确的性质（效率性、单调性、对称性、弱抑制性）和明确的范围。这将权重检查从局部诊断转变为结构化的归因基元，可与事后基线比较，可对照外部参考排名评估，并用于驱动操作决策。实质不在于提取过程，而在于对象本身。  

BOHM和SHAP回答不同的问题：SHAP估计每个组件的反事实边际贡献，而BOHM从路由状态中提取部署系统当前的信任分配。当部署的路由器接近最优路由时，两者重合；在次优路由下的分歧具有信息价值（第5.4节）。本文将此观察形式化为BOHM（Byproduct-Of-Hierarchy Method，层次副产品方法），一种面向复合AI系统的零代价层次化归因方法。其主要作用是解释性的：将层次化系统中的组件信任进行归因。  

我们的贡献是：  
1. 1.**层次化归因树**：一种通过路由权重的路径乘积定义的多分辨率归因基元，同时分解每一层的组件信任（第3.3节）。四个性质（效率性、单调性、对称性、弱抑制性），其中效率性直接证明，其余三个来自底层均衡结果（第4节）。零边际成本，适用于不透明组件：BOHM可在SHAP结构上不可用的部署中计算（附录A.5，τ=1.000）。  
2. 2.在18个真实LLM上的定量验证（880个LiveCodeBench问题）：种子平均下τ=0.928，与SHAP基线（τ=0.980）相当，但每种子在缓存的通过矩阵上评估次数减少9,000倍（第5.2节）；在外部给定的美国人口普查层次（475个叶节点，4层）上，BOHM同时恢复每一层的真实排名，τ最高达0.722（第5.3节）。  
3. 3.一项多智能体驱动研究（第5.4节），涵盖5个编排器和7个基准（35个单元格，约112,000条带子集条件的路由），实证了结构上的“不同问题”关系：驱动将路由高度集中在一个工具上（最高份额中位数0.65，范围0.39至1.00），导致大多数SHAP联盟未被部署，而单元格级τ(BOHM, SHAP)可通过驱动首选工具是否为经验最优来预测。同时，我们明确了方法的范围和局限性（第6节）。  

## 2 相关工作  

##### 基于Shapley的归因。  
SHAP[21 (https://arxiv.org/html/2605.22866#bib.bib1)]在Shapley值框架[28 (https://arxiv.org/html/2605.22866#bib.bib2)]下统一了多种特征归因方法。Chen等人[6 (https://arxiv.org/html/2605.22866#bib.bib13)]综述了超过二十种计算或近似Shapley值的算法，均基于联盟边际贡献框架。Ghorbani和Zou[12 (https://arxiv.org/html/2605.22866#bib.bib14)]将该框架从特征归因扩展到数据估值，证明Shapley值可量化单个数据点对模型性能的贡献。所有变体均通过联盟边际贡献生成平面归因向量，且均要求联盟值函数v(S)可在任意子集S上评估。  

BOHM解决不同的问题：通过部署路由器当前权重状态表达的层次化组件信任，而非联盟边际贡献。两者互补（第6节），其在次优路由下的分歧本身具有信息价值（第5.4节）。其他事后归因家族包括局部替代方法如LIME[25 (https://arxiv.org/html/2605.22866#bib.bib19)]和梯度方法如Integrated Gradients[30 (https://arxiv.org/html/2605.22866#bib.bib20)]；这些针对输入特征归因，而非层次化组件归因。  

##### 注意力作为解释。  
Transformer中的注意力权重被提议作为归因信号。Jain和Wallace[17 (https://arxiv.org/html/2605.22866#bib.bib7)]表明注意力通常与基于梯度的特征重要性不相关；Wiegreffe和Pinter[35 (https://arxiv.org/html/2605.22866#bib.bib8)]则认为它仍可提供合理的解释。BOHM的路由权重与注意力在一个关键点上不同：BOHM从跨轮次基于观察结果更新的有状态权重中提取归因，而非从单次前向传递计算的权重中提取（因此它也不从标准MoE架构中输入条件门控中提取归因，参见第3.2节的范围讨论）。  

##### 层次化和模块化AI。  
Jacobs等人[15 (https://arxiv.org/html/2605.22866#bib.bib12)]引入了自适应局部专家混合，其中门控网络学习对专家输出加权。现代混合专家架构[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4),18 (https://arxiv.org/html/2605.22866#bib.bib21)]通过稀疏路由将规模扩展到数千个专家。复合AI系统[37 (https://arxiv.org/html/2605.22866#bib.bib5)]将模型、检索器和工具组合成流水线。这些系统为BOHM提供了结构场景：组件按层次排列，每层有路由决策。BOHM不提出新的路由架构；它在系统已维护的任何路由状态上定义了一个多分辨率归因对象。先前工作将这些门控权重作为专家使用的每路由器诊断进行检查，但未定义叶节点上的全局归因、跨层次的分解或具有明确性质的正式对象。BOHM定义了那个全局对象（第3.3节）。  

##### 层次强化学习中的信用分配。  
选项框架[31 (https://arxiv.org/html/2605.22866#bib.bib22)]将时间扩展的动作形式化。Dayan和Hinton[8 (https://arxiv.org/html/2605.22866#bib.bib16)]提出了封建强化学习，将控制分解为多层次的管理者和子管理者。Vezhnevets等人[34 (https://arxiv.org/html/2605.22866#bib.bib10)]通过FeUdal Networks将其现代化，其中管理者通过转移策略梯度为工人设定子目标。Samejima等人[27 (https://arxiv.org/html/2605.22866#bib.bib15)]研究模块化RL中的模块间信用分配，通过门控信号将奖励传播到独立模块。这些是策略优化意义上的信用分配：哪一层或模块做出了正确决策？BOHM解决一个相关但不同的问题：基于观察结果，哪个组件值得信任，无需基于梯度的策略更新。  

##### 在线学习。  
加权多数算法[11 (https://arxiv.org/html/2605.22866#bib.bib17)]和EXP3[4 (https://arxiv.org/html/2605.22866#bib.bib9)]维护动作上的权重向量并根据观察到的奖励进行更新。Arora等人[3 (https://arxiv.org/html/2605.22866#bib.bib11)]综述了乘法权重框架及其在优化、博弈论和在线学习中的应用。我们实验中使用的自适应路由基础（第3.2节）属于该家族。BOHM的贡献不在于路由机制本身，而在于观察到其权重状态定义了一个层次化归因对象。Armstrong[2 (https://arxiv.org/html/2605.22866#bib.bib23)]对这里使用的路由基础进行了形式化处理，包括市场完整性、信号保真度、单选择子均衡以及层次组合下的边际组成。  

总结区别：BOHM不是SHAP的层次化变体。SHAP将联盟值函数分解为每组件的边际贡献。BOHM从路由状态中提取层次化信任分解。两者从不同输入出发，回答不同问题，产生不同结构的输出。  

## 3 方法  

### 3.1 设定：层次化组件系统  

考虑N个组件，作为树T的叶节点排列，树深度为D。每条根到叶的路径经过D个路由器（深度0,...,D-1）。每个路由器v具有局部分支因子b_v（同一深度不同路由器的子节点数可能不同），并维护其子节点上的权重向量w_v(t) = (w_{v,1}(t), ..., w_{v,b_v}(t))，初始化为均匀分布；N是T的叶节点数。每轮t，路由器按其权重比例选择子节点，从根级联到叶。所选叶节点j产生二元结果o(t) ~ Bernoulli(p_j)，其中p_j是叶节点j的未知质量。记π(j) = (v_0, ..., v_{D-1}, j)为根到叶路径，并且ch...  

(Note: The original text cuts off at "ch...". I will assume it continues with "and children" etc. But since the provided text ends, I'll stop here. I have translated up to the cut-off point.)  

Let me ensure the translation is complete for the provided portion. The source text ends with "π\(j\)=\(v0,...,vD−1,j\)\\)for the root\-to\-leaf path andch". I'll assume the intended continuation is "child nodes" but since not provided, I'll end the translation at that point.  

Thus, the translated output is the above.# 零代价层次化归因：面向复合AI系统  
来源：https://arxiv.org/html/2605.22866  

###### 摘要  

复合AI系统通过层次化的专用组件路由任务。这类系统的归因主要基于Shapley值的方法（SHAP），它将联盟值函数分解为每个组件的边际贡献，并预设能够评估系统在任意组件子集上的表现。这一假设在许多实际部署中无法成立：第三方API、不透明端点以及将路由集中在少数工具上的智能编排器，使得大多数联盟要么无法评估，要么只能通过使用与部署时不同的编排器重新提示来评估。我们引入**BOHM**，这是一种直接从系统已维护的路由权重中提取层次化归因树的方法。叶节点归因是根到叶路径权重的乘积；第k层归因是深度k节点上的诱导分布。该方法零边际成本，无需访问组件内部，并能同时提供每一层的多分辨率归因，这是平面方法在任何评估预算下都无法做到的。两种方法回答不同的问题，并且仅在部署的路由器接近最优路由时才会收敛。在包含18个LLM的三层层次结构（涵盖880个LiveCodeBench问题）上，BOHM在种子平均下得到Kendall τ=0.928；SHAP（可在缓存的通过矩阵上计算）在每种子进行9,000倍以上的联盟评估后达到τ=0.980。在一项多智能体驱动的智能体研究（5种驱动×7个基准，每个单元格N=100个问题，35个单元格，完全覆盖）中，驱动将路由集中在一个工具上（最高份额中位数0.65，范围0.39至1.00），导致SHAP联盟格被稀疏采样；在按混合专家架构与密集架构分组的非均匀[3,2]层次上，单元格级τ(BOHM, SHAP)范围从-0.80到+1.00，并且可通过驱动首选工具是否为基准上的经验最优来预测（均值τ=+0.22 vs ≈+0.01，Δ=+0.21，对应n={9,26}个单元格），这是结构上“不同问题”关系的经验实例化。在外部给定的机构层次（美国人口普查，475个叶节点，4层）上，BOHM同时恢复每一层的真实排名（τ最高达0.722）。BOHM满足效率性、单调性、对称性和弱抑制性；在质量差距较小时对噪声敏感，对层次设计敏感，且不满足Shapley的可加性公理。它应被理解为基于联盟归因的互补基元：一种在存在路由状态时即可计算的多分辨率分解，同时也是路由质量的检验——其与Shapley的分歧本身就具有诊断价值。  

## 1 引言  

现代AI系统日益复杂且层次化。混合专家架构[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4)]、多阶段流水线和智能编排器[37 (https://arxiv.org/html/2605.22866#bib.bib5)]将专用组件组合成树状结构，其中路由器在每一层选择子节点。这并非小众用例。随着AI应用变得更加智能化和工具化，它们越来越多地由相互作用的组件组装而成，这些组件包含中间路由、委派和选择决策[37 (https://arxiv.org/html/2605.22866#bib.bib5),1 (https://arxiv.org/html/2605.22866#bib.bib6)]。在此类系统中，归因需要在组件层面而非仅输入特征层面进行。一个自然的问题随之产生：每个组件对系统整体性能的贡献是多少？  

组件归因的主流方法是基于Shapley值的：SHAP[21 (https://arxiv.org/html/2605.22866#bib.bib1)]及其变体计算每个组件对联盟值函数的边际贡献。该框架有三个结构性特征限制了其在复合AI系统中的应用。  

*第一*，输出是平面的：SHAP生成一个单一的叶节点归因向量，没有层级或分组的分解概念。  

*第二*，成本高昂：精确Shapley值需要O(2^N)次联盟评估，近似方法需要M个样本的O(MN)次评估。  

*第三，也是最有影响的一点，该框架预设了消融能力*：必须能够测量任意子集S的v(S)。对于黑箱、第三方或专有组件，这种测量无法进行。对于将部署路由集中在少数工具上的智能编排器，未部署子集的v(S)必须通过用受限菜单重新提示编排器来获得，这评估的是*不同于*部署时的编排器。在这种情况下仍可计算SHAP，但其结果并非部署系统的属性。  

我们观察到另一个现象。许多层次化系统已采用自适应路由机制，在每个路由器上维护子节点的权重向量[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4),15 (https://arxiv.org/html/2605.22866#bib.bib12),11 (https://arxiv.org/html/2605.22866#bib.bib17)]。这些权重会随观察到的结果随时间变化。在运行中的任何时刻，当前权重状态编码了系统对每个组件的信任程度，无需额外计算。问题在于这种重新框架是否有实质意义。单个路由器上的局部门控分布虽有信息量，但本身并非归因对象：它不将信用分配给叶节点，不跨层次分解，且没有超越“路由器当前选择偏差”的定义语义。BOHM的贡献在于将局部路由权重所诱导的全局对象形式化：一种通过路径乘积实现的多分辨率分解，具有明确的性质（效率性、单调性、对称性、弱抑制性）和明确的范围。这将权重检查从局部诊断转变为结构化的归因基元，可与事后基线比较，可对照外部参考排名评估，并用于驱动操作决策。实质不在于提取过程，而在于对象本身。  

BOHM和SHAP回答不同的问题：SHAP估计每个组件的反事实边际贡献，而BOHM从路由状态中提取部署系统当前的信任分配。当部署的路由器接近最优路由时，两者重合；在次优路由下的分歧具有信息价值（第5.4节）。本文将此观察形式化为BOHM（Byproduct-Of-Hierarchy Method，层次副产品方法），一种面向复合AI系统的零代价层次化归因方法。其主要作用是解释性的：将层次化系统中的组件信任进行归因。  

我们的贡献是：  
1. 1.**层次化归因树**：一种通过路由权重的路径乘积定义的多分辨率归因基元，同时分解每一层的组件信任（第3.3节）。四个性质（效率性、单调性、对称性、弱抑制性），其中效率性直接证明，其余三个来自底层均衡结果（第4节）。零边际成本，适用于不透明组件：BOHM可在SHAP结构上不可用的部署中计算（附录A.5，τ=1.000）。  
2. 2.在18个真实LLM上的定量验证（880个LiveCodeBench问题）：种子平均下τ=0.928，与SHAP基线（τ=0.980）相当，但每种子在缓存的通过矩阵上评估次数减少9,000倍（第5.2节）；在外部给定的美国人口普查层次（475个叶节点，4层）上，BOHM同时恢复每一层的真实排名，τ最高达0.722（第5.3节）。  
3. 3.一项多智能体驱动研究（第5.4节），涵盖5个编排器和7个基准（35个单元格，约112,000条带子集条件的路由），实证了结构上的“不同问题”关系：驱动将路由高度集中在一个工具上（最高份额中位数0.65，范围0.39至1.00），导致大多数SHAP联盟未被部署，而单元格级τ(BOHM, SHAP)可通过驱动首选工具是否为经验最优来预测。同时，我们明确了方法的范围和局限性（第6节）。  

## 2 相关工作  

##### 基于Shapley的归因。  
SHAP[21 (https://arxiv.org/html/2605.22866#bib.bib1)]在Shapley值框架[28 (https://arxiv.org/html/2605.22866#bib.bib2)]下统一了多种特征归因方法。Chen等人[6 (https://arxiv.org/html/2605.22866#bib.bib13)]综述了超过二十种计算或近似Shapley值的算法，均基于联盟边际贡献框架。Ghorbani和Zou[12 (https://arxiv.org/html/2605.22866#bib.bib14)]将该框架从特征归因扩展到数据估值，证明Shapley值可量化单个数据点对模型性能的贡献。所有变体均通过联盟边际贡献生成平面归因向量，且均要求联盟值函数v(S)可在任意子集S上评估。  

BOHM解决不同的问题：通过部署路由器当前权重状态表达的层次化组件信任，而非联盟边际贡献。两者互补（第6节），其在次优路由下的分歧本身具有信息价值（第5.4节）。其他事后归因家族包括局部替代方法如LIME[25 (https://arxiv.org/html/2605.22866#bib.bib19)]和梯度方法如Integrated Gradients[30 (https://arxiv.org/html/2605.22866#bib.bib20)]；这些针对输入特征归因，而非层次化组件归因。  

##### 注意力作为解释。  
Transformer中的注意力权重被提议作为归因信号。Jain和Wallace[17 (https://arxiv.org/html/2605.22866#bib.bib7)]表明注意力通常与基于梯度的特征重要性不相关；Wiegreffe和Pinter[35 (https://arxiv.org/html/2605.22866#bib.bib8)]则认为它仍可提供合理的解释。BOHM的路由权重与注意力在一个关键点上不同：BOHM从跨轮次基于观察结果更新的有状态权重中提取归因，而非从单次前向传递计算的权重中提取（因此它也不从标准MoE架构中输入条件门控中提取归因，参见第3.2节的范围讨论）。  

##### 层次化和模块化AI。  
Jacobs等人[15 (https://arxiv.org/html/2605.22866#bib.bib12)]引入了自适应局部专家混合，其中门控网络学习对专家输出加权。现代混合专家架构[29 (https://arxiv.org/html/2605.22866#bib.bib3),10 (https://arxiv.org/html/2605.22866#bib.bib4),18 (https://arxiv.org/html/2605.22866#bib.bib21)]通过稀疏路由将规模扩展到数千个专家。复合AI系统[37 (https://arxiv.org/html/2605.22866#bib.bib5)]将模型、检索器和工具组合成流水线。这些系统为BOHM提供了结构场景：组件按层次排列，每层有路由决策。BOHM不提出新的路由架构；它在系统已维护的任何路由状态上定义了一个多分辨率归因对象。先前工作将这些门控权重作为专家使用的每路由器诊断进行检查，但未定义叶节点上的全局归因、跨层次的分解或具有明确性质的正式对象。BOHM定义了那个全局对象（第3.3节）。  

##### 层次强化学习中的信用分配。  
选项框架[31 (https://arxiv.org/html/2605.22866#bib.bib22)]将时间扩展的动作形式化。Dayan和Hinton[8 (https://arxiv.org/html/2605.22866#bib.bib16)]提出了封建强化学习，将控制分解为多层次的管理者和子管理者。Vezhnevets等人[34 (https://arxiv.org/html/2605.22866#bib.bib10)]通过FeUdal Networks将其现代化，其中管理者通过转移策略梯度为工人设定子目标。Samejima等人[27 (https://arxiv.org/html/2605.22866#bib.bib15)]研究模块化RL中的模块间信用分配，通过门控信号将奖励传播到独立模块。这些是策略优化意义上的信用分配：哪一层或模块做出了正确决策？BOHM解决一个相关但不同的问题：基于观察结果，哪个组件值得信任，无需基于梯度的策略更新。  

##### 在线学习。  
加权多数算法[11 (https://arxiv.org/html/2605.22866#bib.bib17)]和EXP3[4 (https://arxiv.org/html/2605.22866#bib.bib9)]维护动作上的权重向量并根据观察到的奖励进行更新。Arora等人[3 (https://arxiv.org/html/2605.22866#bib.bib11)]综述了乘法权重框架及其在优化、博弈论和在线学习中的应用。我们实验中使用的自适应路由基础（第3.2节）属于该家族。BOHM的贡献不在于路由机制本身，而在于观察到其权重状态定义了一个层次化归因对象。Armstrong[2 (https://arxiv.org/html/2605.22866#bib.bib23)]对这里使用的路由基础进行了形式化处理，包括市场完整性、信号保真度、单选择子均衡以及层次组合下的边际组成。  

总结区别：BOHM不是SHAP的层次化变体。SHAP将联盟值函数分解为每组件的边际贡献。BOHM从路由状态中提取层次化信任分解。两者从不同输入出发，回答不同问题，产生不同结构的输出。  

## 3 方法  

### 3.1 设定：层次化组件系统  

考虑N个组件，作为树T的叶节点排列，树深度为D。每条根到叶的路径经过D个路由器（深度0,...,D-1）。每个路由器v具有局部分支因子b_v（同一深度不同路由器的子节点数可能不同），并维护其子节点上的权重向量w_v(t) = (w_{v,1}(t), ..., w_{v,b_v}(t))，初始化为均匀分布；N是T的叶节点数。每轮t，路由器按其权重比例选择子节点，从根级联到叶。所选叶节点j产生二元结果o(t) ~ Bernoulli(p_j)，其中p_j是叶节点j的未知质量。记π(j) = (v_0, ..., v_{D-1}, j)为根到叶路径，并且ch...