今日arXiv最热大模型论文：Agent也疯狂！FoA方法对智能体做树结构搜索，超越ToT

夕小瑶科技说 原创
作者 | 谢年年
大模型agents包揽了从理解问题、规划任务、记忆输入输出、精准调用工具，执行任务解决问题的全过程，更厉害的是，它们还有自我检查和反馈的本事。对于用户来说，不再需要与原始大模型输出直接交互，只需提出需求，便可将与大模型的交互以及行动全权委托给agents。

然而，agents并非万无一失。在应对网络搜索或复杂游戏等不确定环境时，它们需在风险中决策，根据其所知选择下一步行动，但每步都可能遭遇挑战。显然，agents“防患于未然”的能力还不够，让任务走向“死胡同”是常有的事。

为了优化这个问题，可以把这个过程看成是一种搜索，目的是发现、探索并比较通往解决方案的不同路径。这样一来，就可以用常规的搜索算法来解决新问题。搜索过程通常结合了对搜索空间的局部探索和一个启发式价值函数，该函数提供关于搜索树中路径的反馈，并可以激励进行剪枝决策。

今天介绍的这篇论文提出了一个名为“Fleet of Agents”（FoA）的框架，将遗传粒子过滤的概念应用于动态树搜索。

在这个机制中，首先组建了一个由N个agents组成的舰队，共同搜索解决方案。在粒子过滤的变异阶段，每个agent都会独立探索搜索空间。随后，在选择阶段，根据启发式价值函数对agents进行重新采样，确保它们在探索与利用之间达到最佳平衡。如果某个agent发现了极具潜力的解决方案，将通过重新采样创建其多个副本。相反，如果所有agents的表现相近，将保持舰队的多样性。这种机制实现了动态的分支因子调整，使得舰队能够在广泛探索和专注前景之间自然切换。

通过在“24点游戏”和“迷你填字游戏”上进行验证，FoA在性能与成本上都优于“One of the Tree of Thoughts (ToT)”。

论文标题:
Fleet of Agents: Coordinated Problem Solving with Large Language Models using Genetic Particle Filtering

论文链接：
https://arxiv.org/pdf/2405.06691

传统树搜索算法 Vs. 遗传过滤方法

在介绍本篇论文之前，我们先来了解一下传统的树搜索算法与遗传过滤方法有何区别。两者的搜索过程如下图所示：

左侧是传统树搜索算法，右侧是作者采用的遗传过滤方法。

树搜索类似于广度优先搜索（BFS），它按需扩展搜索树。每当出现新节点时，会调用启发式价值函数以预测其价值，并扩展c个最有希望的节点，每个节点进一步生成b个新子节点。随后，对bc个节点进行价值预测，除了价值最高的b个节点外，其余将被舍弃，搜索继续进行。这种方法正是“One of the Tree of Thoughts (ToT)”论文所采纳的。

而遗传过滤搜索在以下两方面实现了改进：

1. 它追踪一组N个状态，允许在评估之前进行k次独立的变异步骤，打破了树搜索中变异与评估的固定顺序，对高成本评估任务尤为重要。
2. 它采用重采样机制，根据状态价值决定是否保留所有有希望的状态或克隆高价值状态，从而灵活调整搜索的广度与深度。

此外，通过追踪状态历史及价值估计，遗传过滤搜索还能利用回溯机制纠正错误决策，使agents团队从不利情况中恢复。

Fleet of Agents

Fleet of Agents包含N个agents,每个agent在时间t处于状态。在选择行动时，agent根据其策略中采样。随后，agent按照环境的动态规律转移到新状态，表示为。随着每个agent寻找解决方案，整个系统共同逐步探索了更多的状态空间。用来描述在时间步t的状态集合，用.来表示到目前为止访问过的所有状态集合。

假设能够识别出找到的解决方案，即可以判断某个状态是否为解决方案，记为。根据任务的不同，还能识别出无效状态、失败的任务和其他形式的死胡同，这些称为终止状态，记为。

对于某些任务，一旦找到解决方案即可停止搜索；对于其他任务，可能会收集一组解决方案候选，只有在时间或采样预算耗尽时才停止搜索。

假设可以访问一个价值函数，该函数可以指导搜索。对于解决方案状态，价值函数代表了该解决方案的效用。对于其他状态，价值函数是考虑到最终达到解决方案的不确定性及其预期效用的一种启发式方法。相应地，终止的非解决方案状态的价值为0。

遗传粒子滤波

系统中的每个agent都独立行动，试图在当前状态下选择最佳动作。经过k步独立步骤后，使用价值函数重新采样状态集，并将更多的agent分配到高价值状态。整体算法实现了一种遗传型粒子过滤器，它捕捉了粒子群体（即agent）的动态，包括一系列的变异和选择步骤。整体算法如下图，包含变异阶段和选择阶段：

变异阶段

在变异阶段，系统中的每个agent独立采样状态转换。为简化符号记法，坐着引入了一个模型，该模型同时捕捉了agents的决策随机性和环境的响应，表示为。使用相同的符号表示通过边缘化中间状态的多步状态转换，即$s_i,t+k} ∼ π(si,t+ks_{i,t)。

每次变异步骤后，可以检查是否找到了解决方案，并决定是否停止搜索。遵循遗传过滤的概念，作者应用了两种优化：

• 强制变异：Agent必须改变其状态；它不能保持不变。
• 突然死亡：如果发现某个Agent 进入了一个无效的状态，那么将立即从集合中重新采样其状态。这种重新采样可以是均匀的，以避免调用昂贵的价值函数。

整体变异阶段算法流程如下图所示：

选择阶段

选择阶段基于重要性抽样机制对Agent群体进行重新采样。观察所有当前状态的价值估计，并计算一个重新采样权重。这个框架可以捕捉许多重新采样方案，例如线性、贪婪或指数加权的值：

• 线性加权：每个状态的重新采样权重与其价值函数的线性关系，即权重与价值成正比。
• 贪婪加权：主要关注最高价值的状态，可能会给这些状态更高的权重，以便更频繁地被采样。
• 指数加权：采用指数形式加权，赋予高价值状态极高的权重，迅速聚焦于最优解。

然后重新采样，替换，以选择一组新的agent状态:

该阶段的算法描述如下：

回溯

在某些情况下，agent所采取的步骤可能是不可逆的。但对于许多任务，FoA在一个纯粹的模拟环境中运行，可以引入一种回溯机制，将遗传粒子滤波器的选择状态扩展到考虑过去的状态。

这里不是从当前状态集中重新采样状态，而是考虑所有先前访问过的状态。为了激励FoA向前推进并探索状态空间的新区域，作者还引入了一个折扣因子，将t个时间步之前访问过的状态的价值按进行折扣。

遗传粒子滤波器的突变阶段包括k步的个体探索，然后在选择阶段进行评估和重新采样。因此，可能没有所有先前访问过的状态的价值估计。根据任务和计算价值的相应成本，可以将回溯机制限制在仅包含具有已知价值估计的状态的子集中。

最后以上的这些策略和方法共同作用，通过智能地调整搜索过程中的状态选择和变异，如下图所示，从而更有效率地探索状态空间，快速定位到解决方案或有价值的状态。

实验

FoA不仅定义了一个运行时的环境，还提出了一种协调策略，这种策略可以灵活地应用于任何现有的agent。为了验证FoA的实际效能，作者使用ToT的代码库的两大任务进行评估，对比FoA和ToT在使用相同agent和价值函数环境中的表现。

经过详尽的测试和分析，得出结论：FoA的表现始终优于ToT。

24点游戏

24点游戏是一个经典的数学谜题，要求玩家使用四个给定的数字（每个数字只能用一次）和基本的算术运算符（加、减、乘、除），计算出总和为24的表达式。

ToT代码库收录了来自4nums.com的1362个按难度递增排列的此类谜题。其中，索引为901至1000的谜题被用作测试集，而索引为876至900和1001至1025的谜题则构成了验证集。

超参数搜索

作者使用GPT-3.5-turbo在验证集上执行超参数网格搜索，深入探索了成功率和成本之间的最佳平衡。调整的超参数涵盖了agent数量、步数限制、折扣因子γ以及重采样频率k。实验结果显示，FoA在广泛的超参数配置下均显著优于ToT。

为验证这一结论，作者选取了三种超参数配置组合在测试集上进行了评估，并分别运行了每个FoA配置和ToT五次，以计算结果的置信区间。如下表所示，FoA在成功率和成本（以美元计）两方面均显著优于ToT。

在保持成功率相近的情况下，FoA能将成本降低39%；而在成本相同的条件下，FoA能将成功率提升93.3%。

在GPT-4上评估

作者利用GPT-3.5-turbo网格搜索得出的最佳超参数，进一步评估了它们在GPT-4上的性能。鉴于GPT-4的运行成本较高，仅对其中一个配置进行了评估。

如下表所示，FoA在成功率和成本方面均再次超越了ToT。尽管成功率的提升未达到统计学显著水平，但成本的降低却十分显著。

小型填字游戏

Mini Crosswords（小型填字游戏）要求玩家根据给定的5个垂直和5个水平提示，在5×5的填字板上填入对应的5字母单词。

从GooBix上收集了156个谜题，并采用正确字母百分比作为评估解决方案与参考答案匹配度的性能指标。ToT 代码库中选用了索引为0、5、...、90和95的谜题作为测试集，并从索引为3、8、...、93和98的谜题中构建了验证集。

超参数搜索

同样利用GPT-3.5-turbo执行了超参数网格搜索，以优化游戏的成功率和成本之间的平衡。经过筛选，选取了三个超参数组合在测试集上进行评估，并重复五次运行以确保结果的可靠性。

结果显示，相比ToT，FoA在成功率和成本方面均取得了显著优势，具体表现为成功率提升8.7%，成本降低48.7%。在成本相近的条件下，FoA的成功率比ToT高出20.4%；而在保持成功率相当的情况下，FoA的成本降低了64.1%。

在GPT-4上评估

在评估GPT-4时，作者保持与GPT-3.5-turbo相同的超参数设置，以确保结果的公平性和可比性。但发现无法完全复现原始ToT论文中的结果。尽管如此，该结果仍具价值，在相同的提示和价值函数下，FoA在成功率和成本方面均优于ToT。FoA的成本降低了73.6%，而成功率提升了15.8%。

结论

本文提出的FoA算法是一种高效的agent行动搜索策略，其设计初衷在于平衡成本与性能，而非仅仅作为一个提示方案。与依赖精心设计的提示的树搜索算法（如ToT）不同，FoA具备高度的通用性，能够与任何现有的agent或提示策略无缝结合，实现高效且成本优化的搜索。