Fleet of Agents: Coordinated Problem Solving with Large Language Models
Authors: Lars Henning Klein
Nearchos Potamitis
Roland Aydin
Robert West
Caglar Gulcehre
Akhil Arora
Venue: ICML 2025 poster (2025)
Keywords: large language models
genetic particle filtering
heuristic search
general problem solving
decision making
explore vs exploit
efficiency
cost-quality trade-off
Primary area: applications->language_speech_and_dialog
TL;DR: We introduce Fleet of Agents (FoA), where LLM agents solve complex problems using genetic particle filtering for adaptive tree searches. Tested on 4 benchmarks with 4 LLMs, FoA boosts quality by ~5% while reducing costs to ~35% of SOTA baselines.

Abstract: While numerous frameworks have been developed to enhance the reasoning abilities of large language models (LLMs), there is a scarcity of methods that effectively balance the trade-off between cost and quality. 
In this paper, we introduce Fleet of Agents (FoA), a novel and intuitive yet principled framework utilizing LLMs as agents to navigate through dynamic tree searches, employing a genetic-type particle filtering approach. 
FoA spawns a multitude of agents, each exploring the search space autonomously, followed by a selection phase where resampling based on a heuristic value function optimizes the balance between exploration and exploitation. 
This mechanism enables dynamic branching, adapting the exploration strategy based on discovered solutions. 
We conduct extensive experiments on four benchmark tasks, \``Game of 24\'', \``Mini-Crosswords\'', \``WebShop\'' and \``SciBench\'', utilizing four different LLMs, GPT-3.5, GPT-4, LLaMA3.2-11B, and LLaMA3.2-90B. 
On average across all tasks and LLMs, FoA obtains an absolute quality improvement of $\simeq 5\%$ while requiring only $\simeq 35\%$ of the cost of previous SOTA methods. Notably, our analyses reveal that (1) FoA achieves the best cost-quality trade-off among all benchmarked methods, and (2) FoA+ LLaMA3.2-11B surpasses the Llama3.2-90B model. FoA is publicly available at [https://github.com/au-clan/FoA](https://github.com/au-clan/FoA).

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Lars Klein
Nearchos Potamitis
Roland Aydin
Robert West
Caglar Gulcehre
Akhil Arora
Abstract
FoA
40
While numerous frameworks have been devel- oped enhance the reasoning abilities of large language models (LLMs), there is a scarcity of methods that effectively balance the trade-off be- tween cost and quality. In this paper, we intro- duce FLEET OF AGENTS (FOA), a novel and intu- itive yet principled framework utilizing LLMs as agents to navigate through dynamic tree searches, employing a genetic-type particle filtering ap- proach. FoA spawns multitude of agents, each exploring the search space autonomously, fol- lowed by selection phase where resampling based on a heuristic value function optimizes the balance between exploration and exploita- tion. This mechanism enables dynamic branch- ing, adapting the exploration strategy based on discovered solutions. We conduct extensive exper- iments on four benchmark tasks, "Game of 24". Mini-Crosssords", "WebShop" and "SciBench", utilizing four different LLMs, GPT-3.5, GPT-4. LLaMA3.2-1 IB, and 1...MA3.2-908. On aver- age across all tasks and LLMs, FoA obtains an absolute quality improvement of 5% while requiring only 35% of the cost of previous SOTA methods. Notably, our analyses reveal that (1) FoA achieves the best cost-quality trade-off among all benchmarked methods, and (2) FoA LLaMA3.2-118 surpasses the Llama3.2-90B model. FoA publicly available at https
ToT
GoT
Quality (%)
30
MCTS
RAFA
20
10
0
2
3
4
5
Cost ($)
Figure I: Analyzing the trade-off between cost and quality of representative SOTA methods with GPT-3.5 on the Game of 24 task. FOA achieves the best cost-quality trade-off.
2024 and PaLM (Anil et al. 2023), have sparked new- found interest in building general-purpose autonomous agents. LLM-based agents have portrayed excellent perfor- mance on reasoning and knowledge-intensive tasks (Cobbe ct al. 2021], often requiring interactions with complex envi- ronments, such as playing complex video games (Fan et al.
2022 performing web navigation (Yao al. 2022). or enabling tool-use (Schick et al. 2023
Naturally, the rise of LLLM-based agents has contributed to the prosperity of prompt- based reasoning frameworks (Wei
et al. 2022 Besta et al.
2024 Yang et al. 2024 Yao et al.
2024
Lingam et al. 2025 Shinn et al.) 2023 Yao et al.
2023 that further enhance the problem-soleee
and reason-
//github. comt://.coocuuue www.///owwaucacaoaaeoo
ing abilities of L.MMs. Broadly, the reasoning frameworks can be categorized into categories: (1) single-query reasoning and (2) multi-query reasoning. As the name im- plies, single-query methods (Wei et al. 2022 Wang et al.
1. Introduction
With strong reasoning and problem-solving abilities, large language models (LLMs) such as GPT-4 (Achiam et al. 2024), LLaMA (Touvron et al. 2023a aal Grattationi et al.
2023 Sel et al. 2024 Nye et al. 202
Kojima et al. 2022)
obtain an answer by querying the LLM only once, whereas,
multi-query methods (Yoo al. 2024 Besta et al. 2024
Zhou et al. 2024 Shinn al., 2023 Yao al. 2023 per- form multiple LLM queries identify different plausible reasoning paths or to plan ahead. It is important note that none of the two aforementioned paradigms is perfect.
'Equal contribution: authors listed in alphabetical or- der. 'EPFL" "Aarhus University "TUHI. Correspondence to: Nearchos Potamitis ncaarchos, Encarchos.potmmitiss au au.dk>, Lars Klein clars.klein @ @pppl.ch..................>>>>.. Akhil Arora aakhil.arora@eoo .....
On the one hand, despite being cost-effective by design, single-query methods require one or more of the following: intricate prompt engineering, high-quality demonstrations,
Proceedings of the nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
ToT
GoT
LATS/ / RAP
FoA
Input
Input
Input
Input
Positive thought
Negative thought
Action
Merging thoughts
Reflexion
Resampling
Output
Output
Output
Output
Figure 2: Comparison between SOTA tree-search-based reasoning Yao et al. 2024
Besta et al. 2024 Zhou al. 2024
Hao et al., 2023) and our FOA frameworks. FOA offers precise control over the tree width (n agents) and depth (t steps), leading to predictable latency and cost. However, by expanding the most promising states at each step, tree-search methods offer no such control and their search trees might grow exponentially.
or knowledge distilled from informative historical reasoning processes, to achieve competitive quality. More importantly, even then, these methods are not well-suited for sequen- tial decision-making tasks that require interactions with an environment, such as web navigation (Yao et al.) (2022).
ploitation. We provide early empirical evidence in Fig. which compares the performance of tree-based SOTA meth- ods with FOA for varying price points. We find that FoA substantially outperforms the existing SOTA methods at all possible price points, thereby achieving the best cost-quality trade-off among the benchmarked methods.
On the other hand, multi-query methods decompose plex problem into series of simpler sub-problems and search over all plausible reasoning paths. This allows them to obtain competitive quality but also renders them inef- ficient and expensive. To devise a reasoning framework applicable to both general problem-solving and sequential decision-maker makinn tasks, our focus in this paper on improv- ing the cost-efficiency of multi-query methods.
Contributions.
We propose an intuitive yet principled framework, FLEET OF AGENTS (FoA), for improving the cost-quality trade-off' of LLM-based reasoning ($ 3.
Ours is the first work to explore the concept of genetic particle filtering in the context of Al agents (cf. $ 2 for a detailed literature review).
Present work. We introduce FLEET OF AGENTS (FoA), novel and intuitive yet principled framework that brings the concept of genetic-type particle filtering (Holland [992] to dynamic tree searches. Fig. 2 provides an overview of
At its core, FOA is a runtime that can readily integrate any existing Al agent, without having change their behav- ior. We compare FoA against various SOTA reasonsers by incorporating their agents, unchanged, into our framework.
our framework, while at the same time highlighting the
conceptual differences between state-of-the-ar (SOTA) tree-
We conduct extensive experiments on four benchmark tasks using four LLMS as base models. On average across all tasks and LLMs, FOA obtains quality improvement of ~ 5% while requiring only 2r 35% of the cost of previous
search-based methods (Yao et al. 2024 Besta et al. 2024 Zhou et al., 2024: Hao et al. 2023 and FOA.
FoA spawns a multitude of agents, each exploring the search space autonomously, followed by selection phase where resampling based on heuristic value function op- timizes the balance between exploration and exploitation. If an agent has discovered promising solution approach indicated by a state with a high value, the resampling mech- anism may create multiple copies of this agent. Conversely, if none of the agents is ahead, or in other words, there are multiple promising states, the resampling mechanism may retain all of them, thereby maintaining fleet of high diver- sity. This mechanism enables dynamic branching. adapting the exploration strategy based on discovered solutions.
SOTA methods ($ 4 and 5
2. Related Work
In this section, we review works that overlap closely with our study (cf. Appx. for additional related work).
Prompt-based reasoning. Recent research focuses on de- veloping strategies to enhance the reasoning capabilities of LLMs. Few-shot prompting employs demonstrations of high-quality input/output samples to exploit the eagerness of the L.MMs to imitate patterns seen in their context window
Cost-quality trade-off. The biggest advantage of FoA is its ability to strike balance between exploration vs.
(Brown et al. 2020). Algorithm of thoughts (AoT) (Sel al.) 2024), goes a step further by including algorithmic exam-
2

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
ples within the prompt propel the LLM through algorith-
Particle filtering. Genetic particle filters have been used successfully across large variety of domains, ranging from vehicle routing (Marinakis & Marinaki 2010), to fuzzy cog- nitive maps in time series forecasting (Salmeron & Froelich 2016), to the positioning of industrial robots (Li et al. 2022). Near-universally, the efficacy of a genetic particle optimiza- tion approach has, in these contexts, been demonstrated on standard artificial neural networks, however, to the best of our knowledge, it has not been employed on LLMs.
mic reasoning pathways. Chain-of-Thoughee (CoT) prompt-
ing (Nye et al., 2021 Wei et al. 2022 Kojima et al. 20222 as
well as other variants such as Decomposed Prompting (Khot
eet al. 2023) and Least-to-Most (Zhou et al. 2023) guide
LLMs to decompose a complex question into a sequence of thoughts and then synthesize an answer by resolving them methodically. It has been shown that Consisseeeyy (CoT-SC) (Wang et a (022) can be used to augment such methods by generating multiple thought sequences and then selecting the most accurate answer through majority voting. Recent meta-prompiing techniques (Suzgun & Kalai 2024) employ a uniform, bask-independent prompting framework across multiple tasks, enabling a single LLM to iteratively refine its responses and dynamically adapt to diverse input queries. The Buffer of Thoughts (BoT) (Yang et al.) 2024) framework extracts task- specife information, uses it to trieve relevant thought templates from its meta-buffer, and then instantiates them with more task-specific reasoning structures before continuing with the reasoning process.
Key differences. FOA exhibits fundamental differences from all aforementioned methods. First, it does not require extensive or intricate prompt engineering, unlike AoT (Sel
et al. 2024) and meta prompting (Suzgun & Kalai 2024
Additionally, it is well-suited for sequential macisonn tasks that require interactions with an environment, such as
web navigation (Yao et al. 2022 Arora et al. [022 West ct al. 2009), which can be challenging for methods such as
CoT (Wei et al. 2022) and BoT (Yang et al.
2024). Fur-
thermore, FOA distinguishes itself from approaches like
Reflexion (Shinn et al., (023) and RAFA (Liu al.) 2024) by utilizing refinement strategy based
Refinement. Closed-loop approaches that allow LLM to interact with an external environment can help in choos- ing and potentially revising an action. Notable examples
genetic-type particle filter, instead of linguistic feedback. Lastly, unlike tree-search-based methods (Yao et al. 2024 Zhou et al..
are ReAct ( (Yo et al. (023). REFINER (Paul et al. 2023)
2024 Besta et al. 2024). FOA employs a more principled approach to search tree exploration, achieving a better bal- ance between exploration and exploitation. This structured approach also grants FOA precise control over the tree's width and depth, leading to predictable latency and cost. Please refer to 88 for a side- side-by-side comparison of the branching mechanism of ToT and FLEET OF AGENTS.
and Self-Refine (Madaan et al., 2023 Reflexion (Shinn
et al. 2023) provides further linguistic feedback based on
previous attempts while AdaPlanner (Sun et al.] 2023) also
incorporates positive and negative feedback of an individual trajectory. Reason for future, act for now (RAFA) (Liu et al. 2024) develops further by planning a trajectory, gathering feedback for the potential planned actions, and then revising the trajectory based on the feedback.
3. FLEET OF AGENTS
Tree search. Thoughts are individual ideas or steps in rea- soning, and when connected together, they can be modeled as a tree data structure. Tree search algorithms can then be used to explore the tree of thoughts and optimize the search for final answer. In "Tree of Thoughts" (ToT), the authors utilize a value function that compares different branches to describe both DFS and BFS flavors of a guided tree-search (Yao et al.
3.1. Overview of FOA
Fig. provides a pictorial overview of FOA. FOA spawns fleet of n agents that collectively search for a solution. The genetic filtering search has mutation phase during which each agent explores the search space autonomously. Specifically, it tracks the n agent states and allows k: inde- pendent mutation steps before evaluating the values of the current states. During the selection phase, we resample, with replacement, the population of agents. The resampling mechanism is based on heuristic value function and al- lows us to optimize the trade-off between exploration and exploitation. The FOA algorithm is comprehensively de- scribed in Algorithm in the Appendix.
2024). The closely related "Graph of Thoughts" (GoT) approach relaxes the assumption of a strict tree struc- ture (Besta et al.) 2024). Reasoning via Planning (RAP)
(Hao et al. 2023) augments I.LMs with a world model and employs Monte Carlo Tree Search (MCTS)-based planning to reduce the search complexity. Language Agent Tree Search (LATS) (Zhou et al. 2024) extends this concept by leveraging environment interactions, thereby eliminating the need for a world model. ReST-MCTS* (Zhang et al.) 2024) builds on this line by integrating process-leve rewards into MCTS, by identifying high-quality reasoning traces.
Preliminaries. The fleet consists of agents. At time t agent i has the state 8i,t. When choosing an action, the agent samples from its policy ag,t ~ TT (a)ss))) The agent then transitions to a new state, following the dynamics of the environment s,,- ~ PPs|aa,, st,). With each agent
3

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Input
the stochasticity of the decision of the agent as well the response of the environment, 81,++1 =({)S1,)) We use the same notation for multi-step state transitions by marginal- izing over intermediate states, i.e., $t,++k IT ([Ss,,+*|$ss. After each mutation step, we can check whether a solution has been found and decide to stop the search. Following the concept of genetic filtering, we apply two optimizations:
State
Active node
Deadend node
Mutation
Enforced Mutation: The agent must mutate its state; can not remain stationary.
Evaluation
Resampliigg
Depending on the task, some solution attempts may result in invalid states. For example, in a crossword puzzle, an agent might propose a word with an incorrect number of characters, resulting in an ill-defined state. It is standard practice, across algorithms (e.g. ToT, GoT), to prevent the search from continuing in such cases. For FOA, agent enters an invalid state, it is deleted, and another agent is randomly duplicated to fill the gap. The replacement agent is chosen uniformly at random, avoiding additional calls to the value function.
Sudden Death:
Value marker, size value
Set of clones
Output
simple filtering mechanism: when an
Figure 3: Fleet-of-Agents (FoA) comprising n = 5 agents that think autonomously for k steps and are then resampled to focus the search on promising regions.
searching for the solution, the fleet jointly discovers more and more of the state space. We describe the current set of states at timestep as St = {8i,), = 1..n and the set of all states visited so far as S, Ug S, 1..1
Selection phase. The selection phase resamples the popula- tion of agents based on an importance sampling mechanism. We observe the value estimates v(st,:) for all current states and calculate a resampling weight Pi,-- This framework can capture many resampling schemes, such as linear, greedy, or exponential weighting of values:
We assume that we can identify solutions when they are found, i.e., we can decide whether a state s is solution, sotution (s). Depending on the task, we may also be able to identify invalid states, failed tasks, and other forms of dead-ends; we denote them as terminal states Iterminat
püi (8i.)) = cvu(si,)) + B,
v(Si.t)
Peap(8t,1) = exp
For some tasks, can stop as soon solution is found; for other tasks, we may instead collect set of solution candidates and stop the search only if we run out of time or sampling budget. We assume we are given access to a value function us)) that can guide the search. For a solu- tion state s, the value function represents the utility of the solution. For other states, 8, the value function is a heuristic considering the uncertainty of eventually reaching solution and its expected utility. Accordingly, the value of terminal, non-solution states is O.
8
1,
if si,t arg max o(55z)
Poreedy (Bi,))
aj...=1...N
0, otherwise
We then resample, with replacement, to select new set of agent states:
pr(0) Σ Σ, j=1 Np3,1
Pi,t
Sen, (s), categorical resampling
81, Rid (s()), resampling with replacement
3.2. Genetic particle filtering
81,1 = 8 1.NN
Each agent in the fleet of agents acts autonomously and tries to choose the best action given its current state. After k independent steps, we use the value function to resample the set of states and allocate more agents to high-value states. Our algorithm implements a genetic-type particle filter that captures the dynamies of a population of particles, i.c., agents, with a series of mutation and selection steps.
Backtracking, Additionally, by keeping track of a history of states and the associated value function estimates, we ex- tend the resampling process with an intuitive backtracking mechanism. Backtracking undoes localized mistakes and allows our fleet of agents recover from catastrophic sce- nario in which all agents might have made wrong decision. Instead of resampling states from the set of current states S., we consider all previously visited states Š,. To incentivize the fleet of agents push forward and explore new regions
Mutation phase. During the mutation phase, each agent in FOA independently samples state transitions. To simplify the notation, we introduce model æ which captures both
4

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
of the state space, we introduce discount factor 7. The value of a state that was visited timesteps ago is discounted by 7². The mutation phase of our genetic particle filter com- prises & steps of individual exploration, before evaluating and resampling in the selection phase. Therefore, we may not have a value estimate for all previously visited states S.. Depending on the task, and the corresponding cost of computing the value e()). we may limit the backtracking mechanism to subset of St which only contains states with known value estimate.
Table I: Comparing FOA with previous methods using success rate ( better) and cost (L better) on the Game of 24 task (base model: GPT-4). The best performance is shown in blue whereas the second best is shown in orange Owing to its exorbitant cost (~ 600 US$). we could not run RAFA (Liu et al. 2024) (not shown in the table).
Method
Success Rate (%)
Cost (USS)
10
6.0
0.65
CoT (Wii et al.
2022
6.0
6.98
CoT-SC WWang al. 2023
10.0
49,40
AoT See al
2024
49.0
20.98
4. Experiments
ToT Yao et al
2024
74.0
75.02
GoT (Besta et al.
2024
63.0
70.01
We assess the effectiveness of our proposed FOA frame- work through comparisons with representative SOTA meth- ods on judicious mix of tasks that require a variety of reasoning, planning, and general problem-solving skills. Additional experimental details, e.g., hyperparameter tun- ing, additional results, etc. are present in Appx. C The resources for reproducing our experiments are available at https://githin com/ http:/auuccaan/aae
ReST-MCTS* (Zhang al.
2024
38.0
104.62
FoA (Present Work)
76.0
62.93
though the code is available, an important resource (the meta-buffer) to reproduce their results is unavailable. We include ReST-MCTS* (Zhang et al., 2024) as its code is available for SeiBench. However, since no implementation was provided for other tasks, we re-implemented the method ourselves for Game of 24 to enable broader comparison.
Base model. Following convention in the literature, we use GPT-4P as the base model for the main results presented in this paper. To showcase the generalizability of our findings, we report results with other base models, namely, GPT-3.5, Llama3.2-11B, and Llama3.2-90B, in Appx. D We also use these models for the model and ablation analyses 5 and $ 6 primarily for practical cost-related reasons.
4.1. Game of 24
Task and data. Game of 24 a mathematical puzzle, where four numbers are given, and the objective is to form an arithmetic expression that equals 24 using each number exactly once. The benchmark data consists of 1362 puzzles. Following ToT (Yao et al. 2024). we use the puzzles indexed 901-1000 as the test set (cf. Appx. C. for details).
Number of runs. For cost reasons, experiments with GPT-4 were run only once. However, for other base models (results in Appx. D). we run each experiment 5 times and report the mean of the evaluation metrics.
Evaluation metries. We use success rale, i.e., the per- centage of solved puzzles, to evaluate the quality of the benchmarked methods. For efficiency, we use cost (in US$).
Prompts. Unlike all existing works, we do not craft cus- tom prompts for FOA, but instead, we reuse the prompts (cf. Appx. C.3 for details) provided by ToT (Yao et al. 2024) for the "Game of 24" and "Mini Crosswords" tasks, 2024) for the "WebShop" task, and ReST-MCTS* (Zhang et al. 2024) for the "SciBench" task. This ensures a direct and fair comparison of the reasoning abilities of the benchmarked frameworks and controls for the impact of prompt quality, which is a confounder.
Baselines. We compare FoA with: (1) Standard IO prompt-
ing, (2) CoT (Wei et al.) 2022).
(3) CoT-SC (Wang et al.
2023), (4) AoT (Sel et al.
2024 (5) ToT (Yao et al. 2024).
LATS (Zhou et al.
(6) GoT (Besta et al. 20244, and
(7) RAFA (Liu et al.
2024
Owing to the unavailability of their code for Game of 24, we do not compare with LATS (Zhou et al. 2024).
Results. T shows that FoA outperforms all existing baselines and achieves the best quality. Taking GPT-4 as a baseline, FOA achieves a whopping 70% improvement in quality. On the one hand, 10 and CoT (Wei et al. 2022) are the most cost-effective methods, their success rate extremely low at just 6%. On the other hand, sophisticated reasoning frameworks like ToT (Yao et al. (024) achieve high success rate (74%) but also incur a high cost (75$), Striking a good balance between exploration vs. exploita- tion, our FOA obtains a 2% absolute improvement in quality over the second best method, ToT, simultaneously lowering the cost requirement by 25%
Baselines. We only compare with methods that have made their code available for the tasks benchmarked in this study (cf. Appx. C.2 for details). Thus, we do not compare with LLMCompiler (Kim et al. 2024), TouT (Mo & Xin 2024
RAP (Hao et al. 2023), and RecMind (Wang et al.) 2024b
Moreover, we exclude BoT (Yang et al. 2024), where al-
'Owing to the exorbitant cost of running GPT-4 (details in App. C.3). we use GPT-3.5 instead for WebShop (Yao et al. 2022 and SciBench (Wang et al. 2002a)..
5

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Table 2: Comparing FOA with previous methods using overlap (t better) and cost (1 better) on the Crosswords task (base model: GPT-4). The best performance is shown in blue whereas the second best is shown in orange
Table 3: Comparing FOA with previous methods using average score (t better) and cost (L better) on the WebShop task (base model: GPT-3.5). The best performance shown in blue whereas the second best is shown in orange
Method
Overlap (%)
Cost (US$)
Type
Method
Avg Score
Cost (USS)
11.
Yao et al.
2022
59.9
NA
10
36.8
0.51
Super- vised
TI
Yao et al. 2022
62.4
NA
CoT (Wei et al. 2022
39.4
1.06
WebN-TS
Gur al.
2023
61.0
NA
CoT-SC Wang al.
2023
39.4
2.82
WebGUM (Furuta et al 2024
67.5
NA
ToTo
Yao et al. 2024
39.7
48.99
Yao al.
2023
58.1
0.10
GoT Besta et al.
2024
41.2
30.28
RcAct Yao ct al. 2023
48.7
0.17
Reflexion (Shinn ct al. 2025
56.3
0.65
FoA (Present Work)
46.0
12.94
context
LASER Ma ct al.
2025
57.2
0.41
LATS
Zhou al.
2024
66.1
232.27
FoA (Present Work)
75.6
1.68
4.2. Mini Crosswords
Hum. experts Yao al.
2022
82.1
NA
Task and data. Mini Crosswords a puzzle, where, given 5 vertical and 5 horizontal clues, the objective is to use the clues to identify answers and place them on 5 x 5 cross- word board. The benchmark data consists of 156 puzzles. Following ToT (Yao et al. 2024), we use the puzzles 0, 5, .... 90, and 95 as the test set (cf. Appx. C.I for details).
Evaluation metries. The quality of a purchase is assessed generated reward, which measures the percent overlap between the purchased product and the user-specified attributes. We use average score, i.e., the average of subtask rewards, to evaluate the quality of the benchmarked methods. For efficiency, we cost (in US$).
using an environment savironment-eenerated
Evaluation metrics. For quality, we use overlap, i.e., the percentage of correct letters in the proposed solution. For efficiency, we compute the cost (in US$).
Baselines. We compare FOA with: (1) Act (Yao al.
2023 (2) ReAct (Yao et al., 2023), (3) Reflexion (Shinn) et al. 2023). (4) LASER (Ma et al. 2023), (5) LATS (Zhou
Baselines. We compare FOA with: (1) Standard 10 prompt- ing, (2) CoT (Wei et al., 2022), (3) CoT-SC (Wang et al. 2023), (4) ToT (Yoo et al. 2024). and (5) GoT Besta et al. 2024). Owing to the unavailability of their code for Mini Crosswords, we do not compare with AoT (Sel et al. 2024).
2024). and (6) multiple fine-tuned models from Yao et al.
Yao et al. (022). We also use the performance of human experts as an upper bound for quality. Owing to the unavailability of their code for WebShop, we do not compare with RAP (Kagaya et al. 2024).
ct al.
Results. Table 2 shows that FoA outperforms all existing baselines and achieves the best quality. Once again, 10 and CoT (Wei et al. 2022) are the most cost-effective methods. Moreover, they obtain good performance with their quality being comparable to ToT (Yao et al. 2024) and GoT (Bestal let al. 2024) just a fraction (2.5%) ) of the cost. Notably, our FOA reports the best cost-quality trade-off among all the benchmarked methods. We obtain a 5% absolute im- provement in quality over the second best method, GoT, simultaneously lowering its cost requirement by 60%.
Results. Table 3 shows that FoA outperforms all existing baselines, even the supervised fine- tunet models (Yao et al.) 2022 Gur et al. 2023 Furuta et al., 2024). and achieves the best quality. While Act (Yao et al. (003) is by far the cheapest method (0. it obtains moderate average score (58.1%). LATS (Zhou al.) 2024), the other hand, obtains better average score (66.1 1%), it suffers from an ex- orbitant cost footprint (2325). Yet again, our FoA achieves the best cost-quality trade-off: obtaining a 10% absolute improvement in quality over the second-bes method, LATS, requiring only I 1 of its cost.
4.3. WebShop
Task and data. WebShop (Yao et al.) 2022) is a simulated e-commerce website environment, where, given textual instruction specifying product and its properties, the ob- jective is to find the product by navigating webpages using a variety of actions and purchase it. The benchmark data consists of 12,087 subtasks. Following (Yao et al., [023] Zhou et al. 2024; Shinn et al., 2023), we use 50 randomly sampled subtasks as the test set (cf. Appx. C.T for details).
4.4. SciBench
Task and data. SciBench (Wang et al., 2024a) is bench- mark suite of scientific reasoning tasks, where the objective is to answer complex, multi-step scientific questions that require integrating knowledge, reasoning over evidence, and applying scientific principles. The benchmark data consists of questions across physics, chemistry, and biology domains,
6

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
FoA
FoA
102
Quality (%)
60
SOTA
60
SOTA
Cost ($)
40
40
10
20
20
100
0
0
Game 24
Crosswords SciBench
Game 24 Crosswords WebShop
Webshs SciBench
Figure 4: Comparing (Left) quality and (Right) cost of FoA with the second most efficacious method (labeled SOTA in the plot) on each benchmark task. Note that the cost plot (Right) uses a split y-axis (indicated by the vertical dashed line) to accommodate the wide range of cost values: a linear scale for Game 24 and Crosswords, and a logarithmic scale for WebShop and SeiBench.
with each domain containing a different number of ques- tions. We use the first 15% of each domain's 's questions as the validation set and the remaining 85% as the test set.
5. Model Analysis
FOA vs. SOTA, To better understand the improvements obtained by FOA, we compare it with the second most ef- ficacious method (SOTA hereafter) on all four benchmark tasks. Specifically, ToT (Yao et al. 2024). GoT (Besta et al. 2024 LATS (Zhou et al. (0224) and ReST-MCTS* (Zhang ct al. 2024) are the SOTA methods for the Game of 24, Crosswords, WebShop, and SciBench tasks, respectively. As stated in 4 we use GPT-4 as the base model for Game of 24 and Crosswords, and GPT-3.5 for WebShop and SeiBench. Fig. sigows that FoA not only achieves the best quality but also the lowest cost all tasks. On aver- age, FOA obtains a quality improvement of = 5% while requiring only ~ 35% of the cost of SOTA methods.
Evaluation metries. The quality is measured using accu- racy, which reflects the proportion of final responses match- ing exactly with the oracle answer. For efficiency, we use cost (in USS).
Baselines. We compare FOA with: (1) Standard IO
prompting, (2) CoT (Wei et al. 2022), (3) CoT-SC (Wang
2023). (4) ToT Yao et al. 2024 and (5) ReST-
MCTS (Zhang et al. 2024).
Results. In Table we present the averaged results across domains (cf. Table 7 for domain-specific results). FoA outperforms all existing baselines and achieves the best quality. Even though, 10 is by far the cheapest baseline (0.01S) its accuracy (5.9%) is almost half of FOA. Finally, FoA achieves the best cost-quality trade-off: obtaining 1.7% absolute improvement in quality over the second-best method, ReST-MCTS", requiring only 14% of its cost.
Trade-off between Cost and Quality. We analyze the trade-off between cost and quality for the top five methods, namely, ToT Yaoo et al. 2024), GoT (Besta et al., 2024
RAFA (Liu et al. 2024., ) ReST-MCTS* (Zhang et al. 2024
and FOA, in the Game of 24 task. For cost reasons, we use
GPT-3.5 as the base model. Following RAFA (Liu et al.)
2024), we allow each method to perform multiple trials (A) and consider them successful if they generate valid solution in any of the A trials. To ensure faireess in the allocated resources, we allocate a fixed budget of 5$ per method, which governs the number A of trials for each method (5 for ToT and GoT, 6 for FOA, and 10 for RAFA).
Table 4: Comparing FOA with previous methods using
accuracy (f better) and cost (L better) on the SeiBench task (base model: GPT-3.5). The best performance shown in blue whereas the second best is shown in orange
Fig. (right) shows that FOA substantially outperforms the existing SOTA methods at all possible price points. Based the portrayed trends, ToT might be able to close the qual- ity gap or even surpass FOA with higher budget, however, FOA is always favorable for resource-constriin
Method
Accuracy (%)
Cost (USS)
10
5.9
0.01
settings. Overall, FOA achieves the best cost-quality trade-off.
CoT Wei et al.
2022
8.4
0.03
CoT-SC Wang Wong
2023
8.7
0.64
ToT Yao
7.2
10.34
ReST-MCTS*
Zhang et al. 2024
9.3
5.11
Trade-off between Model-size and Quality. Fig. 5 (left)
FoA (Present Work)
11.0
0.80
shows that on their own, both the 11B and 90B Llama3.2
7

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
100
90B + FoA
FoA ToT GoT
MCTS RAFA
40
Quality (%)
80
90B
11B + FoA.
30-
60
11B
20-
40
10-
20
0-
Game 24
Crosswo WebShop SciBench
woosswordsoom
1
2
3
5
Cost ($)
Figure 5: Evaluating the trade-off between (Left) model size and quality on the benchmarked tasks with Llama3.2-1 and 90B as base models, and (Right) cost and quality of representative SOTA methods with GPT-3.5 on Game of 24.
models (Grattafiori et al. 2024 achieve poor quality the benchmarked tasks. However, FoA boosts the perfor- mance of both models by portraying significant (5x-6x) quality improvements. What's more, Llama3.2-11BB + FOA surpasses the larger Llama3.2 2-B0BBBBBBB model. Overall, FOA enables smaller models obtain comparable or even better performance than larger models, thereby bridging the gap between their reasoning abilities.
With y 1, all past states are considered during resampling, thereby increasing the spectrum of states to explore but at the risk of overwhelming the resampling mechanism with noisy value estimates of (relatively older) past states. This explains the reduction in success rate and a slight increase in cost owing to potentially futile explorations (Fig. (+))
Impact of Caching, Similar to ToT Yao et al. 2024) and LATS (Zhou et al. 2024), FOA utilizes a caching mecha- nism (details in Appx. C.3 to enhance its cost efficiency, which ensures that given state is evaluated only once by an LLM. As expected, disabling the cache leads FOA to incur higher cost, but interestingly, it also leads to lower success rate (Fig. (I). We hypothesize that frequent re-evaluations of the same state while solving a puzzle might introduce inconsistencies, further disrupting the flow of reasoning structures, thereby leading to a reduction in quality.
6. Ablation Analysis
In this section, we report results on Game of 24 with GPT- 3.5 and Llama3.2 (1 (1IB&90B) as base models. We observed similar trends for the other three tasks, results in Appx. D.2
Impact of the Selection phase. We remove the selection phase by setting the resampling frequency l = 0. Thus, each agent constantly remains its own mutation phase, and independently works towards its goal until a solution is found, a terminal state is found, time runs out. As expected, FoA (without selection) obtains an extremely low success rate but is also cheaper (Fig. (h). This is because, without the selection phase, the fleet does not evolve into a composition of more high-value states with each time step.
Impact of Batching. Similar to ToT (Yao et al. 2024 and LATS (Zhou et al., 2024). FoA utilizes a batching mechanism (details in Appx. C.3 to enhance its cost ef- ficiency, which groups many individual LLM calls into a single combined call (one input prompt leading to many output responses). Disabling batching leads FoA incur higher cost with no noticeable impact quality (Fig. (p).
Impact of Resampling, Instead of using a resampling strat- egy, we assign each agent to the highest-value state during the selection phase. If there are multiple such states, the first one is randomly chosen by all agents. When there are multiple promising states, a meaningful resampling strategy may decide to explore all of them in the next time step, how- ever, retaining only the fighest-value state reduces the fleet diversity. Thus, FoA (no/max resampling) obtains slightly lower success rate but also incurs a lower cost (Fig. (o)).
In sum, Fig. shows that each component of the FOA frame- work has an overall positive impact on its performance.
7. Discussion and Concluding Insights
7.1. Summary of Findings
FOA achieves better quality than all existing methods. Based on the results presented in $ 4 and Appx. D FoA consistently outperforms all existing SOTA methods across all benchmarked tasks and base models.
Impact of the Backtracking mechanism. We vary the discount factor yy to study two aspects of the backtracking 0 (no backtracking) and (2) y = 1 (no decay). When 7 O. resampling from a past state is not permitted, and thus, FoA cannot undo localized mistakes, resulting in a lower success rate but also lower cost (Fig.
mechanism: (1)
FOA achieves a better cost-quality trade-off. Our results show that FOA is cost-efficient, much more so than other SOTA reasoning frameworks. Moreover, our analysis in
8

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
selection
resampling
y=1 (no decay)
y=o (no backtrack)
caching
batching
0.3
0.3
0.3
0.3
0.3
0.2
0.2
0.1
0.1
0.1-
0.0
0.0
0.0
0.0
2
2-
Cost
1-
1-
GPT-3.5
Llama-118 -18
Llama-908
GPT-3.5
Liama-1k 118
Liama-908
GPT-3.5
Llama-111
Llama-908
GPT-3.5
Llama-118 118
Llama-908
GPT:3.5
Llama-118 11B
Llama-908
(a) Selection
(b) Resampling
(c) Backtracking
(d) Caching
(e) Batching
Figure 6: Ablation analysis to study the impact of (a) Selection phase, (b) Resampling, (c) Backtracking, (d) Caching, and (e) Batching on the performance of FOA using the Game of 24 task with GPT-3.5, 1amaa.2-11B. and 90B as base models.
$ reveals that FOA substantially outperforms all SOTA methods at all possible price points.
introduce further coordination between the individual agents with a hierarchical organizational structure. For instance, what if agents could spawn other agents in nested particle filtering framework? Finally, as a runtime that embraces modular compatibility with any agent, FoA will also enable research into complex fleet compositions.
Other advantages. Beyond better performance, FoA of- fers many important practical advantages. First and most importantly, FoA is not prompting scheme but runtime. Unlike existing prompt-based frameworks, e.g. ToT (Yao et al. 2024). GoT (Besta et al., 2024), etc., FoA does not require custom-crafted prompts, but, instead, can used in combination with any existing agent or prompting strategy. Next, FOA offers precise control over the tree's width (n agents) and depth (l steps), leading to predictable latency and cost. In particular, it is possible to tune the size n of the fleet to the available resources, such as an optimal batch size for given hardware configuration. Finally, as evidenced by a smaller standard error (Appx. D). FoA generates consis- tent responses across multiple runs and is relatively more stable than other methods.
Overall, we hope that our work will motivate further re- search in the combination of (genetic) filtering algorithms for the orchestration of Al agents.
Acknowledgements
We thank Anja Šurina, Bhavyajeet Singh, André Charnea, Laurent Bindschaedler, Krishna Gummadi, Chris Schwiegelshohn, and Niket Tandon for insightful discus- sions. West's lab is partly supported by grants from the Swiss National Science Foundation (200021 185043 and 211379). Arora's lab is partly supported by grants from the Novo Nordisk Foundation (NNF240C0099109) the Pi- oneer Centre for AI, and EU Horizon 2020 (101168951), We also gratefully acknowledge generous gifts from Google and Microsoft.
7.2. Limitations and Future work
Constant fleet size. Currently, we assign fixed number n of agents to each task. However, it may be advantageous to allocate more agents to more difficult tasks to enhance sample efficiency. the future, we would like to explore the possibility of adaptive fleet size.
Impact Statement
Throughout an LLM's lifecycle, the majority of costs are in- curred during inference rather than training (Fu al. 2024). Thus, it is crucial to benchmark the cost incurred by various SOTA reasoning frameworks. Our work is the first report, analyze, and include a discussion the trade-off between cost and quality of variety of SOTA LLM reasoning frame- works. To the best our knowledge, it is also the first to propose the use of genetic-style algorithms the context of agentic AI. We hope that this work will spark further discussions on the cost-efficiency of LLM reasoning frame- works and eventually lead to the development of practically feasible and more sustainable Al technologies.
Resampling mechanisms. One avenue for improvement is the design of more intelligent value functions, for example, pooling information from neighboring states and smoothing predictions. Building on precise value estimates, can investigate different resampling mechanisms, to tune FoA towards either more risk-secking careful behavior, i.c., different tradeoffs between exploration and exploitation.
Fleet organization. Currently, we consider a homogenous fleet of identical agents. In the future, we would like to

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
References
Hao, S., Gu, Y., Ma, H., Hong, J., Wang, Z., Wang. D. Z., and Hu, Z. Reasoning with language model is planning with world model. In EMNLP, 2023.
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774. 2024.
Holland, J. H. Adaptation in natural and artificial systems: introductory analysis with applications to biology. control, and artificial intelligence. MIT press, 1992.
Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z. et al. Palm technical report. arXiv preprint arXiv:2305. 2023.
Hong, S., Zheng, X., Chen, J., Cheng, Y., Wang. J., Zhang, C., Wang, Z., Yau, S. K. S., Lin, Z., Zhou, L., Ran, C., Xiao, L., and Wu, C. Metagpt: Meta program- ming for multi-agent collaborative framework. CoRR, abs/2308.002 00355, 2023. 00352.
Arora, A., Gerlach, M., Piccardi, T., Garcfa-Durán, A., and West, R. Wikipedia reader navigation: When synthetic data is enough. In WSDM, pp. 16-26, 2022.
doi: 10.48550/ARXIV:2300.
Josifoski, M., Klein, L., Peyrard, M., Li, Y., Geng, S., Schnitzler, J. P., Yao, Y.. Wei, J., Paul, D., and West, R. Flows: Building blocks of reasoning and collaborating ai. arXiv preprint arXiv:2308.01288 2023.
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Pod- stawski, M., Gianinazzi, L., Gajda, J., Lehmann, T., Niewiadomski, H., Nyczyk, P., et al. Graph of thoughts: Solving elaborate problems with large language models. In AAAI, volume 38, pp. 17682 18622-76600 17690, 2024.
Kagaya, T., Yuan, T. J., Lou, Y., Karlekar, J., Pranata, S., Ki- nose, A., Oguri. K., Wick, F., and You, Y. Rap: Retrieval- augmented planning with contextual memory for mul- timodal Ilm agents. arXiv preprint arXiv:2402.03610 2024.
Brown, T., Mann, B., Ryder, N., Subbiah, M.. Kaplan, D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. In NeurlPS, volume 33, pp. 1877-1901, 2020.
Chase. H. Langchain.
https://qitie com/ twchase17/langchee. 2022.
Khot, T., Trivedi, H., Finlayson, M., Fu, Y., Richardson, K., Clark, P., and Sabharwal, A. Decomposed prompting: A modular approach for solving complex tasks. In ICLR, 2023.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. arXiv preprint arXiv:2110.1416. 2021.
Kim, S., Moon, S., Tabrizi, R., Lee, N., Mahoney, M. W., Keutzer, K., and Gholami, A. An LLM compiler for parallel function calling. In ICML. 2024.
Fan, L., Wang, G., Jiang, Y., Mandlekar, A., Yang, Y., Zhu, H., Tang, A., Huang, D.-A., Zhu, Y., and Anandkumar, A. Minedojo: Building open-ended embodied agents with internet-scale knowledge. In NeurlPS: Datasets and Benchmarks Track, 2022.
Kojima, T., Gu, S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. In NeurlPS, pp. 22199-22213, 2022.
Li, B., Tian, W., Zhang, C., Hua, F., Cui, G., and Li, Y. Positioning
compensation of an industrial robot using neural networks and experimental study. Chinese Journal of Aeronautics, 35(2):346-333 3606 2022.
Fu. Z., Chen, F., Zhou, S., Li, H., and Jiang, L. Llmco2: Advancing accurate carbon footprint prediction for Ilm inferences. arXiv preprint arXiv:2410.02955 2024.
Li, G., Hammoud, H. A. A. K., Itani, H., Khizbullin, D., and Ghanem, B. Camel: Communicative agents for" mind" exploration of large scale language model society. arXiv preprint 1xXxv:2333.177000 2023.
Furuta, H., Lee, K.-H., Nachum, O., Matsuo, Y., Faust, A., Gu, S., and Gur, I. Multimodal web navigation with instruction-finetunee foundation models. In ICLR, 2024.
Grattafiori, A. et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21778 2024.
Lingam, V., Omidvar-Tehrrni, B., Sanghavi, S., Gupta, G., Ghosh, S., Liu, L., Huan, I.,, and Deoras, A. Enhancing language model agents using diversity of thoughts. 2025.
Gur, I., Nachum, O., Miao, Y., Safdari, M., Huang, A. V., Chowdhery, A., Narang, S., Fiedel, N., and Faust, A. Understanding HTML with large language models. In EMNLP, 2023.
Liu, Z., Hu, H., Zhang, S., Guo, H., Ke, S., Liu, B., and Wang, Z. Reason for future, act for now: A principled architecture for autonomous L.M agents. In ICMI, 2024.
10

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Lu, P., Peng, B., Cheng, H., Galley, M., Chang, K.-W., Wu, Y. N., Zhu, S.-C., and Gao, J. Chameleon: Plug-and- play compositional reasoning with large language models. ArXiv, hts/2304.09842, 2023.
Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and
Yao, S. Reflexion: language agents with verbal reinforce- ment learning. In NeurlPS, pp. 8634-8652, 2023.
Sun, H., Zhuang, Y., Kong, L., Dai, B., and Zhang. C. Ada- planner: Adaptive planning from feedback with language models. In NeurlPS, volume 36, pp. 58202-58245, 2023.
Ma, K., Zhang, H., Wang, H., Pan, X., and Yu, D. LASER: LLM agent with state-space exploration for web naviga- tion. In NeurlPS Workshops, 2023.
Suzgun, M. and Kalai, A. Meta-promptine Enhancing language models with task-agnostic scaffolding. arXiv preprint arXiv:2401112954 2024.
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.1765/1 2023.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation language models. ArXiv, abs/2302.13971, 2023a.
Marinakis, Y. and Marinaki, M. A hybrid genetic- particle swarm optimization algorithm for the vehicle routing problem. Expert Systems with Applications, 37(2):1446 1455, 2010.
Touvron, H., Martin, L., Stone, K. R., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint urXiv:2307.09288, 2023b.
Mo. S. and Xin, M. Tree of uncertain thoughts reasoning large language models. In ICASSP, pp. 12742-12746, 2024.
Wang, X., Wei, J., Schuurmans, D., Le, Q. Chi, E.,, Narang, S., Chowdhery, A., and Zhou, D. Self-consistency im- proves chain of thought reasoning language models. arXiv preprint arXiv:2203.11177, 2022.
Nakajima, Y. BabyAGI
httpps://ithub.com com/
yobeinakajiim//bbbaaag 2023.
Nye, M. I., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., Sutton, C., and Odena, A. Show your work: Scratchpads for intermediate computation with language models. CoRR, abs/21 12.001 14, 2021.
Wang. X., Wei, J., Schuurmans, D., Lc, Q. V., Chi, E. H., Narang, S., Chowdhery, A., and Zhou, D. Self- consistency improves chain of thought reasoning in lan- guage models. In ICLR, 2023.
Wang, X., Hu, Z., Lu, P., Zhu, Y., Zhang, J., Subramaniam, S., Loomba, A. R., Zhang, S., Sun, Y., and Wang, W. Scibench: Evaluating college-level scientific problem- solving abilities of large language models, 2024a. URL https: /tte:///rxivv wttpaaaxvvv.oo www.vvoorrggaaae abbs////////// 2307. 10635
Paul, D., Ismayilzada, M., Peyrard, M., Borges, B., Bosse- lut, A., West, R., and Faltings, B. Refiner: Reasoning feedback on intermediate representations. arXiv preprint arXiv:2304.01904 2023.
Richards, T. B. AutoGPT. https:///ithi:n com/ Significant-Gravv
Wang, Y., Jiang, Z., Chen, Z., Yang, F., Zhou, Y., Cho, E., Fan, X., Lu, Y., Huang, X., and Yang. Y. Recmind: Large language model powered agent for recommendation. In NAACL-HLT (Findings). pp. 4351 13644, 2024b.
Auto-APto GPT 2023.
Salmeron, J. L. and Froelich, W. Dynamic optimiza- tion of fuzzy cognitive maps for time series forecasting. Knowledge-Band Based Systems, 105:29-37, 2016.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E.,, Le, Q. V., and Zhou, D. Chain-of-thougge prompting elicits reasoning in large language models. In NeurIPS, pp. 24824 24837, 2022.
Schick, T., Dwivedi-Yon J., Dessi, R., Raileanu, R., Lomeli, M.. Hambro, E., Zettlemoyer, L., Cancedda, N., and Scialom, T. Toolformer: Language models can teach themselves to use tools. In NeurlPS, 2023.
West, R., Pineau, J., and Precup, D. Wikispeedia: An online game for inferring semantic distances between concepts. IJCAI, pp. 1598-1603, 2009.
Sel, B., Tawaha, A., Khattar, V., Jia, R., and Jin, M. Al- gorithm of thoughts: Enhancing exploration of ideas in large language models. In ICML., 2024.
Wu, Q. Bansal, G., Zhang, J., Wu, Y., Ziang, S., Zhu, E., Li, B., Jiang, L., Zhang, X., and Wang, C. Autogen: Enabling next-gen LLM applications via multi-agent conversation framework. CoRR, abs/2308.08155, 2023. doi: 10.48550/ ARXIV.2308.081 1.555
Shen, Y., Song, K., Tan, X., D. S., Lu, W., and Zhuang, Y. T. Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface. ArXiv, abs/2303. 17580, 2023.

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Yang, L.., Yu, Z.,, Zhang, T., Cao, S., Xu, M., Zhang, W., Gonzalez, J. E.,, and Cui, B. Buffer of thoughts: Thought- augmented reasoning with large language models. In NeurlPS, 2024.
solving with large language models. NeurIPS, 36, 2024.
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y. and Tang, J. ReST-MCTS*; LLM self-training via process reward guided tree search. NeurIPS, 2024.
Yao, S., Chen, H., Yang, J., and Narasimhan, Web- shop: Towards scalable real-world web interaction with grounded language agents. In NeurIPS, pp. 20744-20757, 2022.
Zhou, A., Yan, K., Shlapentokh- and Wang, Y.-X. Language agent tree search unifies reasoning, acting, and planning in language models. In ICMI., 2024.
M., Wang, H.,
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. ReAct: Synergizing Reasoning and Acting in Language Models. In ICLR, 2023.
Zhou, D., Schärli, N., Hou, L.,, Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q. V., and Chi, E. H. Least-to-man massst prompting enables complex reasoning large language models. In ICLR, 2023.
Yao, S., Yu, D., Zhao, J., Shafran, L.. Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem
12

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
A. Additional Related Work
AI agents extend the capabilities of LLMs by integrating external tools or orchestrating collaborations between multiple LLMs. To solve task, such an AI agent may take many individual steps, usually one depending on the other, e.g., querying database, searching with a web browser, running computations in code interpreter, etc. There exists a diverse and quite fragmented ecosystem of frameworks and libraries that motivate specific interaction patterns are designed to offer the flexibility to implement new forms of collaboration. A well-established library is LangChain (Chasel 2022). but many practitioners chose to accompany their research with a custom solution. Camelcon (Lu ct al. (023). Camel (Li ct al. 2023) )
Hug (Shen et al. 2023), AutoGPT (Richards, 2023). Baby AGI (Nakajima 2023). 3). MetaGPT (Hong et al. 2023
Flows (Josifokii et al. 2023). and AutoGen eWu al. 2023). all these works present some form of blueprint or framework for building Al agents.
Building on these works, creating highly sophisticated AI agents is possible. Nevertheless, even if an action is only taken after many steps of deliberation and careful consideration, the agent must ultimately follow sequential chain of actions on its way toward solution. This is fundamentally similar to structured reasoning. i.e., the agent approaches solution in smaller discrete steps, each step following logically from the previous steps. In many scenarios, multiple actions may be promising; the agent is faced with uncertainty and large state space to explore. In this setting, the perspective of a single agent is necessarily a myopic and localized worldview. We overcome this limitation by instantiating flect of individual agents and coordinating joint search process between them. This research is orthogonal existing work on optimizing Al agents: Instead of novel way build improve specific Al agent, we implement runtime that can readily accommodate any existing agent and multiply its capabilities.
B. FLEET OF AGENTS: Additional Details
Algorithm 1 Fleet of Agents: A genetic particle filter.
Initialize
2: ++0
3: 81, Xp, i- = 1..N (setting initial state)
4: loop
5: Mutation phase
6: 81,++ + Call Algorithm with 81,, i = N..N and S.
7:
8: Selection phase
9: Si,t+k + Call Algorithm 3 with Se4k
10:
11: 1 1- 1
12: end loop
B.1. Comparison of FLEET OF AGENTS with standard tree-search algorithm
We posit that any multi-step structured reasoning prompt will rely current state of the reasoning process is advanced, and evaluation steps, in which different states are judged and compared. The key difference between structured reasoning algorithms lies in how these steps are orchestrated. In Fig. g we show a standard tree search algorithm, based on one of the Tree-of- -fe-uof-Thought (ToT) algorithms, side by side with FLEET OF AGENTS.
flavors of prompts: mutation steps, in which the
At every step during the search for solution, ToT keeps track of thoughts, generates follow-up thoughts for each, estimates their value, and from the cb candidate thoughts, selects the b best. is important note:
Mutation and evaluation prompts called in lockstep; each new thought is immediately evaluated.
At every step, eb- b candidate thoughts are discarded. Depending on the parametrization, the majority of mutation and value calls correspond to thoughts that immediately become dead ends.
The number promising states selected and the number of follow-up thoughts are fixed, resulting in a constant branching factor.
13

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Algorithm 2 Mutation Phase
Input: List of current states 8i,t, 1..N and states St at time t
2: Output: List of states $1,++k, 1..N at time + k
3: for = 1 to & do
4: Each agent independently mutates its state
5: $1,++1 ~ x ( 1..N
6: 1- 1+1
7:
Check for solution
8: 3s E St Loluution (s) then
9: We have found solution: early exit
10: end if
11:
Identify and prune terminal states,
12:
resample across all viable states S, discovered so far
13:
B + terminal (st,e)
14:
G - {s|s E S, 8 $ B}
15:
for: E do
Uniform ()
Si, $
18: end for
19: end for
Algorithm 3 Selection Phase
1: Input: Set of states S, at time
2: Oufput: Resampled list of states St,r, I..N at time t
3: Evaluate heuristic value function
4: U, v(s), St
5: Calculate the resampling distribution
6: Pa = exp(1Bv.)) E St, (resampling weight]
p(s) Exes Pı E.Es (s) {categorical resampling distribution}
8: 84 vid Pc(s),i L..N (resampling with replacement)
9: 81,1 8;,1 1..N
This ToT algorithm closely resembles beam search using value function as a heuristic. By comparison, FLEET OF AGENTS follows different design philosophy. Instead of modeling the multi-step reasoning process as a graph traversal or heuristic tree search, we take inspiration from the concept of individual AI agents exploring a complex search space on their own. We believe that for many real-world applications, it is best to trust the individual agent to make local decisions based on their best judgment. Rather than exploring branches at each step, we allow our fleet of N agents to make series of educated guesses.
We evaluate the states of individual agents only every k steps. Instead of selecting the b best states, we then resample with replacement. If one of the agents has found an extremely promising state, it is duplicated and the search focuses on the region that agent is exploring. This corresponds to a decision to exploit the findings of this agent. Conversely, all agents have a similar value, none them may be duplicated during the resampling process, keeping maximum diversity in the fleet of agents. This corresponds to a decision to explore further.
Refer the first resampling stage in Fig. g which shows that one agent duplicated (replacing agent of very low value) while three others kept. In practice, this means that allocate branching factor of 2 to the duplicated agent and branching factor of to the rest of the fleet. This is reasonable choice: When we have yet to observe distinct difference in thought value, then it is better to explore further before concentrating the search. In the second resampling stage, we note that one thought has a much higher value than the others. The resampling creates four copies this thought but also retains one medium-valuu state. In this toy scenario, ToT always explores the dynamic search tree with a fixed branching factor of whereas FLEET OF AGENTS selects branching factors dynamically, ranging from 4.
14

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
12-6-600tt
2
13-10-3
073
State potantial
seluution
12/9
6/5
[termina) astution
Volue marker (stee st volue]
12/354
4 (4cf:224)
8 (left
Rosampting
[13- (13-10)112//0)-3
Figure 7: Example of Fleet of Agents runtime applied to the Game of 24. Three agents deployed, and the runtime undergoes the selection phase every k = 1 steps. A positive discount factor > 0 is retained to allow backtracking to previous states. During the resampling in the mutation phase, agents that have taken incorrect actions are corrected by replacing their state with one that has a potential solution.
Notable properties of FLEET OF AGENTS include:
Individual decisions made according to each agent's localized best judgment. This enables quick and efficient spread across the search space.
Resampling (i.e., discarding some agents) occurs only every k steps. Ideally, only thoughts clearly worse than their competitors are discarded.
The resampling process provides an intuitive trade-off between exploitation and exploration. In practice FLEET AGeNTS dynamically choose a branching factor between 1 (all agents retained, maximizing exploration) and N (one agent finds highly promising state and the search is focused accordingly).
C. Additional Experimental Details
C.1. Detailed Task Descriptions
C.1.1. GAME OF 24
Game of 24 is a mathematical puzzle where the participants are presented with four numbers, and their objective is to find a combination arithmetic operations (+-*/) to construct an arithmetic expression that uses each given number exactly once obtain final total of 24.
15

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Value marker,
State
Mutation
size x value
Active node
Evaluation
Set of clones
Deadend node
Resampling
Input
Input
Output
Output
Figure 8: (Left) Search-tree for Tree-of-thoughts (ToT) that generates 3 candidates for the next thought step and maintains set of b most promising states each step. (Right) Fleet-of-Agents (FoA) comprising N = 5 agents that think autonomously for k steps and are then resampled to focus the search promising regions.
The benchmark consists of 1362 such puzzles scraped from 4nums.com which sorted in increasing order of their difficulty. The input data in each puzzle are the four initial numbers and the expected output is an equation that equals 24. Following ToT Yao et al., (2024). we use the puzzles indexed 901-1000 as the test set. We also created a validation set from the puzzles indexed 876-900 and 1001-1025. The validation set constructed such that, in expectation, its overall difficulty similar to the test set.
C.1.2. MINI CROSSWORDS
Mini Crosswords is puzzle where participants are given 5 vertical and 5 horizontal clues. Each clue leads 5-letter word, and the objective is to the clues to identify answers and place them 5 5 crossword board. We use the percentage of correct letters to measure the quality of proposed crossword solution. For letter to be correct, it has to match both the letter and its position on the ground truth board.
The benchmark constitutes 156 such puzzles scraped from GooBix Following ToT Yao et al. 2024), we use the puzzles 0, 5, 5...., 90, and 95 as the test set. We also created a validation set from the puzzles indexed 3, 8, ..., 93, and 98.
C.1.3. WEBSHOP
WebShop Yao et al. 2022 is simulated e- e-commerce website environment comprising 1.18 million real-worle products and 12,087 crowd-sourced textual instructions. The participants are provided with textual instructions specifying product and its properties, and their objective is to find and purchase the product by navigating webpages using variety of actions.
The benchmark data consists of 12,087 subtasks. We noticed that the website environment randomizes the set of subtasks upon every initialization. Thus, to fix the test set across all the experiments and methods benchmarked in this study, we add fixed random seed to the website environment. Following (Yao et al. 2023 Zhou et al., 2024 Shinn et al., 2023). we
16

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
50 subtasks to construct the test set. Specifically, we use the subtasks indexed 5-54 as the test set. We also created validation set from subtasks indexed 55-69.
C.1.4. SCIBENCH
SciBench is a benchmark designed to evaluate large language models on college-level scientific problem-solving tasks across mathematics, physics, and chemistry. Each task is open-ended and free-response, requiring multi-step reasoning, conceptual understanding, and the application of domain-specific knowledge.
The benchmark consists of 692 problems curated from widely- undergraduate textbooks. The input for each task includes a textual problem statement, and the expected output is a correct, well-reasoned answer solution. Tasks span diverse set of scientific domains, including calculus, differential equations, electromagnetism, thermodynamics, and quantum chemistry.
We retain 15% of the questions from each domain as the validation set, and use the remaining 85% as the test set.
C.2. Detailed Baseline Descriptions
C.2.1. GAME OF 24
Input-Output (IO) prompting uses the LLM to directly generate an output, with no intermediate steps.
Chain-of- Thought (CoT) (Wei et al. 2022) solves the problem step by step by decomposing into a sequence of thoughts.
Chain-of-Thougee (Wei et 2022 with Self-Consistency (Wang al. 2022 CoT-SC, generates multiple responses for the same CoT prompt and then selects the best one based majority voting.
Algorithm-of Thorighh (AoT) (Sel et al. 2024) (AoT), guides the reasoning through algorithmic pathways by including such examples in its prompt.
Treo-of-Thoughts (ToT) Yao et al., 2024). decomposes the problem into multiple chain of thoughts, organized a tree structure. Thought evaluation and search traversal algorithms are utilized to solve the problem.
Graph of Thoughts (GoT) (Besta et al. 2024 allows the organization of thoughts in a graph structure. It introduces arbitrary graph-basee based thought transformations such as thought aggregation and thought refinement.
Reason for futre, act for now (RAFA) (Liu et al.) 2024) structures its reasoning by initially implementing potential plan for trajectory. Then, feedback is gathered for actions included in the plan. Finally, a new plan is generated with the gathered feedback in context. Even though we compared with RAFA using models GPT3.5 and Llama 3.2 11B, we did not compare with GPT4 or Llama 3.2 90b as its cost would be prohibitive.
Reasoning via Planning (RAP) (Hao al. 2023) augments LLMs with a world model and employs Monte Carlo Tree Search (MCTS) planning to generate and traverse its thought process. Language Agent Tree Search (LATS) (Zhou et al.) 2024) extends this concept by leveraging environment interactions, thereby eliminating the need for world model. We did not compare with any of these two methods as code for the game of 24 task was not available.
The Buffer of Thoughts (BoT) YYang et al. 2024) framework extracts task-specific information, uses it to retrieve relevant thought templates from its meta-buffer, and then instantiates them with more task-specific reasoning structures before continuing with the reasoning process. For BoT (Yang et al., 2024) we were unable to reproduce the results reported in their paper as component of their method imeta-buffert is not available and we have no detailed instructions how recreate ourselves.
The I.MMCopillrr (Kim et al. 2024) is an LLM compiler that optimizes the parallel function calling performance of LLMs. There was no code available for the task of Game of 24, so we do not compare against it.
Tree of uncertain Thoughts (TouT) (Mo & Xin 2024) leverages Monte Carlo Dropout to quantify uncertainty scores associated with LLMs' diverse local responses at intermediate thoughts. This local uncertainty quantification is then united with global search algorithms. There was no code available so we do not compare against TouT.
17

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
ReST-MCTS* Zhang et al. 2024) introduces self-training framework that modified Monte Carlo Tree Search (MCTS*) guided by process-level rewards. Instead of relying solely final answers, it infers per-step rewards to identify and reinforce high-quality reasoning traces, improving the LLM's reasoning ability over successive iterations. In our experiments, we only tested the MCTS* component for inference-time reasoning, without the full iterative self-training loop, to ensure a fair comparison, as all other baselines were also evaluated purely in the inference-time setting.
C.2.2. MINI CROSSWORDS
Input-Output (IO) prompting uses the LLM to directly generate an output, with no intermediate steps.
Chain-of-Thougee (CoT) (Wei et al. 2022) solves the problem step by step by decomposing it into sequence of thoughts
Chain-of- Thoughh (Wei et al. 2022) with Self-Conistency (Wang et al. 2022) CoT-SC, generates multiple responses for the same CoT prompt and then selects the best one based on majority voting.
Algorithm-or Thirugght (AoT) (Sel et al. 2024) (AoT), guides the reasoning through algorithmic pathways by including such examples in its prompt. For its Mini Crosswords implementation, AoT utilizes prompts that need to be sequentialy and provides both of them. However, in between the two prompts necessary step is performed which extracts the word combination of the highest "compatibility. No further details are found about this step and since it can be interpreted in a number of ways we chose not to move on with it.
Tree-of-Thoughhs (ToT) Yao et al., 2.24). decomposes the problem into multiple chain of thoughts, organized a tree structure. Thought evaluation and search traversal algorithms are utilized to solve the problem.
Graph of Thoughts (GoT) (Besta et al. 2024 allows the organization of thoughts in a graph structure. It introduces arbitrary graph-based thought transformations such as thought aggregation and thought refinement.
C.2.3. WEBSHOP
Act Yao et al.
2023 simply prompts the framework to perform an action within closed loop.
2023) integrates reasoning into Act by allowing the model to think instead of explicitly performing an action the environment.
ReAct (Yao et al.
Reflexion (Shinn et al. 2023) generates linguistic feedback that is utilized during subsequent runs.
Agent with State-Space ExploRation (LASER) (Ma ct al. (023) models environment interactive tasks as state-space exploration. This is achieved by allowing the LLM agent to transition among a pre-defined set of states by performing actions to complete the task.
Language Agent Tree Search (LATS) (hou al. 2024 employs Monte Carlo Tree Search (MCTS)- planning to generate and traverse its thought process, leveraging environment interactions. Even though compare with LATS using GPT3.5, we do not repeat the experiment for any other model as it is prohibitively expensive.
Multiple deep learning approaches(Yan) Yao et al. 2022). We also compare with a variety of deep learning approaches such as supervised, reinforcement and imitation learning. We report their average score as given in their published paper.
Human Experts: human annotators have been recruited by the Webshop authors (Yao al. 2022) to study their trajectories. Based on their results, thirteen of them are recruited and trained further. Finally, the top 7 performers are selected experts. Yao al. 2022)
Retrieval-Augmennt Planning (RAP) (Kagaya et al. (024) dynamically leverage past experiences corresponding to the current situation and context in both textual and multimodal environments.
The LLMCompiler (Kim et al. 2024 is an LLM compiler that optimizes the parallel function calling performance of LLMss. There was no code available for the task of WebShop, so we do not compare against it.
18

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
C.2.4. SCIBENCH
Input-Output (IO) prompting uses the LLM to directly generate output, with no intermediate steps.
Chain-of-Though (CoT) (Wei et al. 2022 solves the problem step by step by decomposing it into a sequence of thoughts.
Chain-of-Thought (Wei al. 2022 with Self-Conistency (Wang et al. 2022) CoT-SC, generates multiple responses for the same CoT prompt and then selects the best one based on majority voting.
Tree-of- Theoughs (ToT) Yao et al. 2024). decomposes the problem into multiple chain of thoughts, organized tree structure. Thought evaluation and search traversal algorithms are utilized to solve the problem.
ReST-MCTS* (Zhang et al., 2024) introduces a self self- traininiing framework that uses modified Monte Carlo Tree Search (MCTS*) guided by process-level rewards. Instead of relying solely on final answers, it infers per-step rewards to identify and reinforce high-quality reasoning traces, improving the LLM's reasoning ability over successive iterations. In our experiments, we only tested the MCTS* component for inference-time reasoning, without full iterative self-training loop, to ensure fair comparison, as all other baselines were also evaluated purely in the inference-time setting.
C.3. Implementation Details
Platforms. GPT models were were accessed through the OpenAl API while the utilization of the Llama models was facilitated by the TogetherAl API
Model checkpoints and prices. To compute the costs of our experiments we used the current model prices indicated OpenAl and Together AI, accordingly to the model. The specific models snapshot we used, along with their respective prices are presented in 5
USS per Im prompt tokens
US$ Per Im completion tokens
gpt-3.5-turbo-0125
0.5
1.5
gpt-4-0613
30.0
60.0
1.2
0.06
22--11--ision--Isstuct----- Turbu
0.18
0.18
Table 5: Model snapshot prices. OpenAl and TogetherAl prices for each model used, during the implementation of the project.
Model configurations. Generation parameters specified when making calls to any of the models used throughout this project. These parameters were not defined by us, but by the implementation where the respective prompts where introduced. Specifically, Game of 24 and Mini Crosswords parameters were used from (Yao et al., 2024), WebShop step request
parameters was taken from Yao al., 2023), WebShop evaluate request parameters from (Zhou et al. 2024) and SeiBench
parameters taken from (Zhngg al. 2024). Configurations presented in Table 6
max_tokens
temperature
top-p
stop
Game of 24
100
0.7
1
null
Mini Crosswords
1000
0.7
null
WebShop (step)
100
1
["'nn"]
WebShop (eval)
100
null
SeiBench
1000
0.7
null
Table 6: Generation parameters. Generation parameters specified when making requests to any model.
Base model selection strategy. We selected GPT4 to be our base model as was the one for which the prompts we used were originally designed for. Excepions were made for the RAFA (Liu al. 2024) and LATS (Zhou et al.) 2024 baselines
19

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
their was prohibitive for to run using GPT4. Additionally, for the task of WebShop (Yao al. 2022). did not repeat any baseline for GPT4. That because firstly, the price was extremely steep for some of the baselines and secondly because some of the baselines had already achieved near-human level of performance. Finally, for the SciBench task (Wang et al., 2024a), we did not replicate any baselines for GPT-4 or Llama-3.2 1.ama-3.2-90B due to the fact that SciBench spans 10 datasets across different domains, incurring prohibitívely high computational costs.
Prompts.
This section provides all the prompts used for the models evaluated in our experiments. We include the exact phrasing and formatting of each prompt to ensure reproducibility and allow for detailed examination of how the tasks were presented to the models.
Input: 8
Possible next steps: 2 + 8 - 10 (left: 8 10 14)
2 4 (left: 4 8 14)
14
16 (left:
16)
* 16 (left: 14 16)
8 - -2 = (left: 6 14)
14 - 8 = 6 (left: 2 6 8)
14 2 = (left: 8 8)
2 12 (left: 8 12)
Input: (input}
Possible next steps:
Prompt I: Game of Step prompt The prompt used to generate candidate new states. Taken from
Yao et al. 2024
Use numpers and basic arithmetic operations (+ /1 to obtain 24. Each step, you are only all owed to choose of the remaining numbers to obtain new number.
Input:
Steps:
+ 8 = 12 (left: 4 6 12)
(left: 2 12)
12 = 24 (left: 24)
Answer: (6 4) * (4 + 8) 24
Input: 2 9 10 12
Steps:
12 2 24 (left:
24)
10 9
(left: 24)
24 + 1 1= 24 (left: 24)
Answer: (12 2) * (10 9) - 24
Input: 9 10 13
Steps:
13 10- 3 (left: 4 9)
9 - 3 - 6 (left: 4 6)
24 (left: 24)
Answer:
(9 (13 10))
Input: 14 8
Steps:
8 4 = (left: 1 2 8)
+
(left: 3 8)
+ 24 (left: 24)
Answer: (1 8 4) * = 24
Input: 5 5
Staps:
10 (left: 9 10)
10 5 15 (Leit: 15)
15 9 24 (left: 24)
Answer: ((5 + 5) + 5) 9 24
Input: (input)
Prompt 2: Game of 24 Last step prompt In the game of 24, once all initial numbers combined. if the resulting number is 24, then the following chain of thought prompt was used to summarized the operations that have taken place to get there Yao et al. 2024
20

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Evaluate if given numbers can reach (sorr//1ielly/mmpsssllll.
10 14
10 14
24
sure
11 12
11 12
12 11 1
11 12 132
11 12 0.91
impossible 10
+ + 10
8
10 - 18
10
4
40
36
(10 4)
24
sure
9 11
+ 11 4 20 + 4 = 24
sure
578
+ 7
12 20
(8 5) 7 7 21
cannot obtain 24 but numbers are within reasonable range likely
6
+ 6 17
(6 5) * 6 6 6
cannot obtain 24 now, but numbers within reasonable range likely
10
10 + 10 + 11 31
(11 - 10) 10 = 10
10 10 10 all too big
impossible
1
1 3
(1 3) 12
all small impossible (input)
Prompt 3: Game of 24 Value prompt The prompt used to evaluate a state Yao et al. 2024
Let's play 5 5 mini crossword, where each word should have exactly letters.
(input)
Given the current status, list all possible answers for unfilled changed words, and your confidence levels weettain/highmmdiuun /ow) using the format "hl. apple (medium) Use "certain" cautiously and only when you are 1008 sure this the correct word. You can list more then one possible answer for each word.
Prompt 4: Mini Crosswords Step prompt The prompt used to generate candidate new states Yao et al. 2024).
Evllute if there exists five letter word some meaning that fit sone letter constraints muure//aybe//mposiblle)
Incorrect; to injure:
The letter constraint is: letters, letter is w, letter 3 is o, letter 5 is g.
some possible words that mean "Incorrect; to injure"; wrong (w r (wron g): letters, letter is w, letter is o, letter 5 is g. fit! surc
person with all-consuming mg enthusiasm, such for computers or anine:
The letter constraint. is: letters, letter 5 is u.
21

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Some possible words that mean person with an all-consuming enthusiasm, such for computers or anime":
geek (g e k): 4 letters, not 5
otaku Kotaku u): 5 letters, letter 5 is
Dewy; roscid: r
The letter constraint is: 5 letters, letter 1 is r, letter 5 is 1.
Some possible words that mean "Dewy; rescid"; t): letters, letter is m, not humid (h u i d): letters, letter is h, not
moist (m o
cannot think of any words now. Only 2 letters are constrained, it is still likely maybe
de The letter constraint is: letters, letter 2 is 1, letter 4 is d, letter 5 is e. Some possible words that mean "A weedland";
woodland:
forest (f
t); letters, not
woods (w o
s): letters, letter is o, not
grove (g r c v e): letters, letter is E, not
cannot think of any words now. 3 letters are constrained, and d seems commor.
pattern
maybe
An inn: d d W
The letter constraint is: 5 letters, letter 2 is d, letter 4 is w, letter 5 is f. Some possible words that mean "An inn":
hotel (h t 1): letters, letter is o, not
lodge (1 g e): letters, letter is o, not
cannot think of any words now. 3 letters are constrained, and it is extremely unlikely to have word with pattern d w to mean "An inn"
impossible
Chance; a parasitic worm; a fish: w I rrak The letter constraint is: 5 letters, letter 1 is w, letter 2 is r, letter 3 is a, letter 4
is k.
Some possible words that mean "Chance; a parasitic worm; fish":
Eluke (f 1 k e): letters, letter is f, not cannot think of any words now. 4 letters are constrained, and it is extremely unlikely k to mean "Chance; parasitic worm; fish"
to have word with pattern impossible
(input)
Prompt 5: Mini Crosswords Value prompt The prompt used to evaluate a state. Specifically, this prompt evaluates a potential solution of out the 10 questions of the Crossword. To get the value the overall state this prompt was called for each row/column of the crosswords board with a potential solution Yao al. 2024).
Webshop Instruction:
would like a ounce bottle of bright citrus deodorant for sensitive skin, and price
Lower than 50.00 dollars
[Search]
Action: search[3 cunce bright citrus deodorant sensitive skin]
Observation:
[Back to Search]
Page 1 (Total results: 50)
[Next >]
[B078GWRC1J]
Bright Citrus Decdorant by Earth Mama Natural and Safe for Sensitive Skin, Pregnaney and Breastfeeding, Contains Organic Calendula 3-Ounce
$10.99
[B078GTMM 7GGTKXX]
22

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Ginger Fresh Deedcrant by Earth Mama Natural and Safe Sensitive Skin, Pregnancy Breast feeding, Contains Organic calendula 3-Ounce
$10.99
[B08KBVJ4XN]
Barrel and Oak Aluminum-Free Decdcrant, Deodorant for Men, Essential Oil- Scent, 24-Hour Odor Protection, Cedar Patchouli Blend, Gentle on Sensitive Skin (Mountain sage, 2.7 oz, 2-Pack) $15.95
action: (AALKK/077GWRCLL and B078GIKVXY are bright citrus deodorant less then 50 dollars. I can check H078GWRC1J first.] Observation: OK.
Action: B078CRR078
Observation:
[Back to Search]
[< Prev]
scent [assorted scents] [bright citrus] [calming lavender] [ginger fresh] [simply non-scents] size [travel set (4-pack) [3 ounce (pack 1) [3-ounce (2-pack) Bright Citrus Decdorant by Earth Mama Natural and Safe for Sensitive Skin, Pregnancy and Breastfeeding, Contains Organic Calendula 3-Ounce
Price: $10.99
Rating: N.A.
[Descripticn] [Features] [Reviews] [Buy Now]
think[For ounce bottle bright citrus deodorant for sensitive skin, the item has options 'bright citrus' and '3 ounce (pack of 1)' and seems good to buy.] Observation: OK.
Action:
Action: alick(bright citrus]
Observation: You have clicked bright citrus.
Action: click[3 cunce (pack of 1)] Observation: You have clicked cunce (pack of
Action: Bli Now
Prompt 6: WebShop Step prompt The prompt used to generate the next action so that after performing the action new state would be achieved. The observation and action history of the agent would be appended the end of this prompt. Taken from Yao al. 2023).
Given item purchase and trajectory that aims to buy item that exactly matches the specification, which corresponds to the ideal score of 1.0, analyze the following trajectory, then at the last line conclude "Thus the correctness score is (8)", where s is an integer from 1 to 10.
Here are examples
Webshop
Instruction:
am looking for dairy free and apple variety pack of chips, and price lower than 30.00
dollars
[Search]
Action: tearch/dairg free and apple variety pack of chips]
Observation: [Back to Scarch]
Page 1 (Total results: 50)
[Next >]
[B07HRFJWP8]
Enjoy fi Foods Soft Baked Ovals, Breakfast Bars, Nut Bars, Soy Free, Dairy Free, Non GMO, Gluten Free, Vegan, Variety Pack, Boxes (20 Bars Total)
23

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
$100.0
[B01KMHY5PG]
Enjoy Life seft Baked Chewy Bars, Variety Pack, Nut free Bars, Soy Free, Dairy Pree, Gluten Free, Boxes (30 Total Bars)
$21.49
[B008D2X8C4]
Enjoy Life Lentil chips Variety Pack, Dairy Free chips, soy Frec, Nut Frec, Non GMO, Vegan Gluten Free, 24 Bags (0.8 oz)
$100.0
Action: Chink(The first two items are not what I want. The third item is the dairy ry free and apple variety pack of chips want.]
Observation: Ok.
Action: [B08D(000022
Observation:
[Back to Search]
K Prev]
flavor name [dill and sour cream] [garlic parmesan] [light sea salt] [nargherita pizza] [ thai chili 1ime] [variety pack]
size [0.8 cunce (pack of 24) ] [4 ounce (pack of 12)]
Price: $100.0
Rating: N.A.
[Descripticn]
[Features]
[Reviews] [Buy Now]
Action:
think The item has options 'variety pack' and 00.8 ounce (pack 24) and seems good to buy.]
Observation: OK.
Action:
click(variety pack]
Observation: You have clicked variety pack.
Action: click[0.8 8 ounce (pack of 24)]
Observation: You have clicked 0.8 cunce (pack of 24).
Action: click|Buy Now]
Reflection:
In this attempt, was unsuccessful. accidentally bought product that $100, which more than my budget $30. Bither way, the initial search results were not good. Next time, I will do search search["variets ["variety pack of chips"] and then check if the results meet the dairy free and the $30 budget constraints. I will continue to refine searches that can find more products. Thus the correctness
is
Webshop
Instruction
would like cunce bottle of bright citrus deodorant for sensitive skin, and price lower than 50.00 dollars
[Search]
Action: search/3 ounce bright citrus deodorant sensitive skin]
Observation:
[Back to Search]
Page 1 (Total results: 50)
[Next >]
[B078GWRC1J]
Bright Citrus Decdorant by Earth Mama Natural and Safe for Sensitive Skin, Pregnancy and Breastffeedng, Contains Organic Calendula 3-Ounce
$10.99
[B0786TKVXY]
Ginger Fresh Decdorant by Earth Mana Natural and Safe for Sensitive Skin, Pregnancy and Breastieeding, Contains Organic Calendula 3-Ounce
24

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
$10.99
[B08KBVJ4XN]
Barrel and Oak Aluminum-Free Decderant, Deodorant for Men, Essential Oil-Based Scent, 24-Hour Odor Protection, Cedar Patchouli Blend, Gentle on Sensitive Skin (Mountain Sage, 2.7 oz, 2-Pack) $15.95
Action: think (B778GWR11 and BО78CТкVXY are bright citrus deodorant less then 50 dollars. can check B078GWRC1J first.] Observation: OK.
Reflection:
Although the task is not yet complete, the first search is correct and returns relevant results. The thought is also logical caal and has patential to lead to the correct selection.
Thus the correctness score is (input)
Prompt 7: WebShop Value prompt The prompt used to evaluate a state. The observation and action history of the agent would be appended the end of this prompt (Zhou al. 2024).
Given science problem, you need to answer the problem based on your existing knowledge. The input may include sone existing steps solve the question and you should continue to complete the solution based on these existing steps.
If the input does net provide any existing steps, you need give the first step in solving calculating the problem. If partial solution steps the next step along the lines the existing steps.
provided, you need output
The output format is limited to: "Next step: ..." where
indicates onitted output information, which is the next step in the answer that you should give. Your output must be complete step, which may include detailed calculations, reasening, choosing answers, etc. but no reasoning.
If the existing steps are already sufficient, you can output "The final answer is: $...8" where indicates the final anawer to the question.
Please provide MULTIPLE aiternative next steps. Use the following format: "Next step: $
Next step: $...$
Next step: $.
Below the input, please follow the specified format for your output.
Problem: (preblem)
Existing steps:
(existing_stcps)
Output:
Prompt SeiBench Step prompt The prompt used to generate candidate new states, Taken from Zhang et al. 2024
Given math problem and its corresponding solution, your task is to extract the final answer obtained the solution.
You should summarizz the answer using the format: "The final answer is S...s". Replace
"..." with the answer obtained in the solution. Problem: (preblen)
Solution: (existing_sten)
Extracted answer:
Prompt 9: SeiBench Summary prompt This prompt applied after solution is found to adjust the output into the expected format. Taken from (Zhang et al. 2024
Your task is to assess whether the provided solution steps can successfully solve the given ocieeccemmthhmaate The score should be decimal between and If all the provided steps are incorrect every step is wrong), the score ahould be C. If all steps are correct and the final
problem and output score.
25

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
answer is successfully calculated, the score should be 1. The more errers there are the steps, the closer the score should be to 0. The closer the steps are to the final correct answer, the closer the score should be to 1.
Steps that only contain verbal descriptions without any mathematical expressions should generally receive a low score. score equal to or greater than 0.9 can only be given if the answer has already been calculated to a specific numerical value. the thought process is complete but the answer is not computed, or only the mathematical expression is written without solving it, the score must be below 0.9.
First provide an analysis, then the score. Your analysis and scoring should be entirely based on the given steps. Do not continue solving the problem. Please study the foll following examples.
(examples)
Below is a problen and the existing steps, with analysis and scoring. Be careful not to output the next steps in the analysis, and the scoring should be based entirely on the steps given in the input.
The output format limited to: "Analysis:... AnScores..."" where indicates omitted output content, which is the part you need to fill in.
Input:
Problem: (preblem)
Existing steps:
texisting_steps
Output:
Prompt 10: SciBench Value prompt This prompt used to evaluate state. The original prompt was taken from Zhang
et al. 2024 but was translated from Chinese to English using Google Translate.
Practical extensions in the FOA framework.
The caching mechanism is utilized during the evaluation phase of our method enhance its efficiency. It operates by ensuring that given state is evaluated only once by the language model. This is achieved through temporary state-to-value map maintained for the duration of single run of the algorithm. Consequently, only when an agent encounters a previously unseen state, the LLM evaluates it and stores it in the cache. However, if different agent (or the same agent at a later step) revisits that state, the LLM does not re-evaluate it; instead, the value retrieved from the state-to-value cache. comparison other baselines such as ToT (Yao et al. 2024) and LATS (Zhou et al., 2024h, no additional caching being performed.
Caching:
Batching:
During the mutation selection phase (depending the task) prompts callected by all agents. Once that happens, if duplicated prompts occur, instead of making several individual requests for the same prompt, we make single request and ask for multiple outputs. Employing batching in this way, ensures competitive fairness to methods such as ToT which utilize the this mechanic in the same way. This approach enhances efficiency and resource management by reducing network latency, server requests, on top of lowering the costs, as the user pays for the input tokens only once. Additionally, batching ensures consistency, slight changes in the model's 's state data processing the provider's side, affect individual requests differently.
Task Task-specific modifications.
For the Scibench task (Wang et al. 2024a), we used the prompts provided in the ReST-MCTS* paper Zhhng et al., 2024). However, from our understanding, the evaluation prompt used in that paper was written in Chinese, and no official English version was available. To ensure better control over the evaluation process and to align the task with the predominantly English-language setup of our experiments, we translated the original Chinese prompt into English. This allowed to directly inspect, adjust, and verify the evaluation inputs, ensuring consistency and clarity across all baselines.
26

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
C.4. Hyperparameter Tuning
We perform hyperparameter grid-search on the validation set, explore trade-off's between success rate and cost. For this search, we use GPT-3.5-turbo, since GPT-4 would be prohibitively expensive. The hyperparameters consider the number of agents, the total number of steps each agent is allowed to perform, the discount factor y, the resampling frequency k and the resampling method.
The grid search implemented in two steps. Initially, a broader, more general grid search is conducted to obtain an approximate understanding where the optimal configurations are located. Subsequently, a more precise grid search is performed based on the findings from the initial step. The results of the second grid search for Game of 24 are presented in Figure 9 for Mini Crosswords in Figure and for WebShop in Figure 11
C.4.1. GAME OF 24
The strategy for selecting the optimal configuration for the Game of 24 involves choosing the configuration that yields the best performance at the lowest cost. Following this approach, it is evident that the optimal number of agents and steps is achieved when the either hyperparameter is set to 9 or 12. However, since the cost is lowest at 9, this value is chosen for both the number of agents and the number of steps. Regarding the resampling frequency, resampling after every step (i.c., 1) results in significantly better performance and is therefore selected. For the discount factor 7 no notable differences in performance or cost observed. Thus, 7 0.5 chosen as represents balanced choice between not allowing backtracking (y 0) and maximally encouraging backtracking by rendering the discount factor inconsequential (? 1). Finally, the linear filtered resampling method provides similar results to the linear method but at significantly lower cost, making it the preferred choice.
The linear filtered resampling method essentially the same as linear resampling, but only considers states whose values are equal to or greater than the value the current best-evaluated state. Across the different tasks, we found that this method advantageous only when multiple states with sparse values are taken into consideration during resampling.
Table 7: Comparing FOA with previous using accuracy (f better) and cost ( better) on the detailed SciBench domains (base model: GPT-3.5). The best performance shown in blue whereas the second best shown orange
Accuracy (%)
Cost (USS)
Dataset
I0
CoT
CoT-SC
ToT
ReST-MCTS*
FoA
I0
CoT
CoT-SC
ToT
ReST-MCTS*
FoA
atkins
1.1
7.6
8.1
11.1
15.5
14.5
0.01
0.07
1.37
18.35
9.41
1.54
calculus
4.6
0.4
0.3
3.4
14.1
10.2
0.01
0.02
0.45
6.00
3.78
0.52
chemme
16.8
14.3
10.2
15.4
17.5
0.01
0.02
0.44
6.81
1.22
0.51
class
0.3
12.3
12.6
2.1
3.7
5.8
0.01
0.03
0.31
7.97
4.94
0.63
diff
4.9
1.0
3.5
7.9
12.1
14.3
0.01
0.03
0.58
9.12
8.54
0.67
fund
8.3
7.3
7.1
8.9
15.4
13.3
0.01
0.04
0.76
11.98
5.77
1.02
matter
2.4
9.4
10.3
3.7
6.1
8.1
0.01
0.03
0.69
10.33
5.43
0.77
quan
5.1
7.2
5.9
5.9
7.5
9.7
0.01
0.02
0.44
6.47
1.99
0.44
stat
13.7
21.1
20.3
16.4
3.3
16.4
0.01
0.04
0.68
12.65
3,78
0.9
thermo
1.8
3.4
4.8
0
0
0
0.01
0.04
0.65
13.68
6.21
0.98
Average
5.9
8.4
8.7
7.2
9.3
11.0
0.01
0.03
0.64
10.34
5.11
0.80
27

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Game Hyperparameter tuning
(4)
1.00
1.00
Number agents
Number agents
0.50
0.50
0.25
0.25
0.00
0.00
6
12
12
1.00
1.00
Number steps
steps
0.75
0.50
0.50
0.25
0.25
0.00
0.00
6
12
12
1.00
1.00
Resampling frequency
Resampling fraquency
0.50
0.50
0.25
0.25
0.00
0.00
1
2
1.00
Discount factor (y)
Discount factor (y)
0.50
0.50
0.25
0.25
0.00
0.00
0.1
0.2
0.5
0.1
0.2
0.5
1.00
Resampling method
0.75
0.50
0.50
0.25
0.25
Resempling
0.00
0.00
Linear
Linear (fittred)
Lincar
Linear (fiitered)
Figure 9: Results of the final grid-search for Game of 24. Each subplot illustrates the performance (left) and cost (right) as function of varying hyperparameter. The values of the remaining hyperparameters are set to those of the final, optimal configuration.
C.4.2. MINI CROSSWORDS
For the Mini Crosswords task, our final grids-search we observed that performance plateaued approximately 0.4 overlap percentage, with minimal variation. Consequently, our primary strategy for this task to minimize cost. The overlap remained similar when tuning the number of agents, number of steps, and the resampling frequency. However, in each case, there was always specific value that significantly minimized cost, and this value was selected. Thus, we opted for agents, steps. For the discount factor and the resampling method, there was
running for 6 steps each, and resampling every no clear advantage in terms of performance or cost. Therefore, we selected the most moderate options in each category: a discount factor of 7 = 0.5 and the linear resampling method.
28

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Crosswords Hyperparameter tuning
Overiap
(4)
1.00
1.00
agents
agents
0.50
0.50
0.25
0.25
0.00
0.00
2
2
1.00
1.00
Number steps
steps
0.75
0.50
0.50
0.25
0.25
0.00
0.00
6
10
10
1.00
1.00
Resampling frequency
Resampling fraquency
0.50
0.50
0.25
0.25
0.00
0.00
1
2
1.00
Discount factor (y)
Discount factor (y)
0.50
1
0.50
0.25
0.25
0.00
0.00
0.0
0.2
0.5
0.0
0.2
0.5
1.00
Resampling method
Resaimpling method
0.75
0.50
0.50
0.25
0.25
0.00
0.00
Linear
Linear (fittred)
Lincar
Linear (fiiteed)
Figure 10: Results of the final grid-search for Mini Crosswords. Each subplot illustrates the performance (left) and cost (right) as function of varying hyperparameter. The values of the remaining hyperparameters are set to those of the final, optimal configuration.
C.4.3. WEBSHOP
Finally, for the WebShop task, we reverted to our original strategy: achieving the best performance at the lowest possible cost. It is noteworthy that, due the complexity of the WebShop task, more agents and steps required for optimal performance. Consequently, we tested a broader range of values for both resampling frequency and discount factor compared to the previous tasks. The results indicated that the best average scores at the lowest cost were achieved with 15 agents running for 10 steps each. For the resampling frequency, the best scores were obtained with y E (2, 5,), with and being the most cost-effective. Since there was no significant cost difference between 4 and 5, we selected to allow for more frequent resampling. Finally, we omitted filtering during resampling as it provided no additional advantage.
29

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
WebShop Hyperparameter tuning
Average
(4)
1.00
1.00
agents
0.80
0.50
0.25
Number agents
0.40
0.00
10
15
20
10
15
20
1.00
1.00
[
0.75
steps
0.80
0.50
0.25
Number
0.40
0.00
10
15
20
10
15
20
1.00
1.00
Resampling fraquency
0.80
0.50
0.25
Resampling frequency
0.40
0.00
3
5
1.00
Discount factor (y)
0.13
0.80
0.50
0.25
Discount
0.40
0.00
0.0
0.3
0.5
0.8
0.0
0.3
0.5
0.0
1.00
Resampling method
0.75
0.80
0.50
0.25
Resampling
0.40
0.00
Linear
Linear (fittred)
Lincar
Linear (fiitere))
Figure 11: Results the final grid-search for WebShop. Each subplot illustrates the performance (left) and cost (right) as a function of varying hyperparameter. The values of the remaining hyperparameters are set to those of the final, optimal configuration.
D. Additional Results
D.I. Generalizability of the findings with other base models.
In the following section, present results for various models and demonstrate that the findings generalize across different settings. You can find the results for the task of Game of 24 in Table Mini Crosswords in Table 9 WebShop in Table 10 and SciBench in Table II
Note the performance of Act and ReAct. Act and ReAct have essentially the same architecture in the sense that an initial prompt is repeatedly being given the L.M while it's being updated by the actions that have been chosen and the resulting enviromment observations. The only difference is that the ReAct prompt introduces the possibility of a new action for the LLM "Think". When this action chosen the LLM does not interact with the environment, simply states its thoughts and aims to come up with a strategy to solve the problem. However, these prompts came up years ago where much less powerful models were used. As result, more contemporary models interast differently with them.
30

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Table 8: Comparing FOA with previous methods using success rate (f better) and cost (L better) on the Game of 24 task. The best and second best performances are shown in blue and orange respectively. Owing to its exorbitant cost (= 600 USS), we could not run RAFA (shown as DNR).
Task: Game of 24
Model
Method
Success Rate (%)
Cost (US$)
10
0.05
CoT
3.6
0.12
CoT-SC
1.40
AoT
1.0
0.32
GPT-3.5
ToT
13.6
1.71
GoT
11.2
1.60
RAFA
8.0
10.47
FoA
25.1
1.55
I0
6.0
0.65
CoT
6.0
6.98
CoT-SC
10.0
49.39
GPT-4
AoT
20.98
ToT
74.0
75.02
GoT
63.0
70.00
RAFA
DNR
DNR
FoA
62.93
10
2.6
0.01
CoT
3.6
0.01
CoT-SC
4.8
0.05
Llama 3.2-1IB
AoT
5.1
0.12
ToT
2.7
0.37
GoT
1.4
0.31
RAFA
0.0
23.10
FoA
6.0
0.32
10
6.0
0.03
CoT
6.8
0.05
CoT-SC
0.33
Llama 3.2-90B
AoT
36.8
0.81
ToT
35.5
2.51
GoT
2.11
RAFA
DNR
DNR
FoA
39.7
2.05
D.2. Ablation analysis for the remaining tasks
In the following section, we present the remaining ablation studies we performed and display that our findings generalize across different settings. You can find the results for the Mini Crosswords ablation in Figure 12 for WebShop in Figure 13 and for SeiBench in Figure [4
D.3. Details on RAFA Results and Metric Differences
In our evaluation RAFA (Liu et al. 2024) for the Game 24 task, we used the official implementation provided by the authors. However, the results we report differ from those presented in the original RAFA paper. This difference stems from variation in the definition the success rate evaluation metric.
31

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Table 9: Comparing FOA with previous methods using overlap (1 better) and cost () better) on the Crosswords task. The best performance shown in blue whereas the second best shown orange
Task
Mini Crosswords
Model
Method
Overlap (%)
Cost (USS)
10
31.2
0.01
CoT
33.2
0.02
CoT-SC
33.1
0.06
GPT-3.5
ToT
33.3
0.48
GoT
34.5
0.40
FoA
36.2
0.25
10
36.8
0.51
CoT
39,4
1.06
GPT-4
CoT-SC
39.4
2.82
ToT
39.7
49.99
GoT
41.2
30.28
FoA
46.0
12.94
0.01
CoT
21.0
0.01
Llama 3.2-1IB
CoT-SC
21.0
0.04
ToT
46.5
0.44
GoT
41.5
0.57
FoA
50.9
0.16
10
5.0
0.04
CoT
30.6
Llama 3.2-90B
CoT-SC
30.6
0.13
ToT
62.8
6.01
GoT
62.5
4.72
FoA
64.92
1.55
Specifically, the RAFA paper reports results using a relaxed version of the success rate metric (see Footnote 1, page 50, ICML'24 camera-ready), which differs from the stricter formulation used in other benchmarks. To ensure consistency and fairness across all methods evaluated in our study, we applied the success rate implementation defined in the original ToT (Yao et al. 2024) paper uniformly across all baselines.
As shown Table when we apply the relaxed success rate metric used in the original RAFA paper, our results align closely with those reported by its authors. This adjustment ensures that readers can understand the basis of any apparent discrepancies and interpret our comparisons across methods accurately.
32

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
Table 10: Comparing FoA with previous methods using average score ( better) and cost (1 better) the WebShop task. The best performance is shown in blue whereas the second best is shown in orange
Task WebShop
Model
Method
Average scure
Cost (USS)
Act
58.1
0.10
ReAct
48.7
0.17
Reflexion
56.3
0.65
GPT-3.5
LASER
57.2
0.41
66.1
232.27
FoA
75.6
Act
28.2
0.10
ReAct
Llama 3.2-11B
Reflexion
24.8
0.50
LASER
54.0
FoA
77.2
TL Yao al.
2022
59.9
DL
T. Yao al.,
2022
62.4
WebN-TS
al.
61.0
WehGUM Furuta al.
2024
67.5
Human experts Yao al. 2022
82.1
Table 11: Comparing FOA with previous methods using accuracy (f better) and cost (4 better) on the SciBench task. The best performance shown in blue whereas the second best shown in orange
Task SeiBench
Model
Method
Accuracy (%)
Cost (USS)
10
5,9
0.01
CoT
8.4
0.03
CoT-SC
8.7
GPT-3.5
ToT
7.2
10.34
ReST-MCTS*
9.3
5.11
FoA
11.0
0.80
10
0.9
0.02
1.6
Llama 3.2-1IB
CoT-SC
2.4
0.11
ToT
1.9
2.35
R
4.2
2.04
FoA
5.1
0.27
RAFA results (Game-of-24) Our with RAFA metric Our run with ToT metric RAFA run with RAFA metric
Accuracy (%)
Low interval
High interval
26
23
28
8
6
9
29
Table 12: Comparison of RAFA results across different runs and evaluation metrics.
33

---

Fleet of Agents: Coordinated Problem Solving with Large Language Models
FoA
No selection
resampling
y=1 (no decay)
(no backtrack)
caching
No batching
0.4
0.0
0.0
0.0
0.0
0.0
1.5
1.0
1.0
0.5
0,5
GPT-3.5
Llama-118
Liama-908
GPT-33.5
Liama-118
Liama-900
GPT-3.5
Llama-115
Llama-908
GPT-3.5
Llama-110
Llama-908
GPT-3.5
Llama-111 11ma
Llama-900
(a) Selection
(b) Resampling
Backtracking
(d) Caching
(e) Batching
Figure 12: Ablation analysis to study the impact of (a) Selection phase, (b) Resampling, (c) Backtracking, (d) Caching, and
(e) Batching on the performance of FOA using the Mini Crosswords task with GPT-3.5, Llama3.22 1B, and 90B as base models.
selection
resampling
y=1 decay)
y=0 (no backtrack)
caching
batching
Average Score
0.75
0.75
0.75
0.50
0.50
0.25
0.00
0.00
0.00
0.00
0.00
2-
2-
Cost
GPT-3.5
Liama-118 118
GPT-3.5
Llama-114 118
GPT-3.5
Llama-118
GPT-3.5
Llama-118
GPT-3.5
Llama-118
(a) Selection
(b) Resampling
(c) Backtracking
(d) Caching
(e) Batching
Figure 13: Ablation analysis to study the impact of (a) Selection phase, (b) Resampling, (c) Backtracking, (d) Caching, and
(e) Batching on the performance of FoA using the WebShop task with GPT-3.5 and Llama3.2. base models.
FoA
No selection
No resampling
y=1 (no decay)
y=0 (no backtrack)
No caching
No batching
0.75-
0.6
0.75
0.4
0.4
0.50-
0.2
0.25
0.25
0.0
GPT-3.5
Llama-118
0.0
G
Llama-118
0.00
GPT-3.5
Llama-118
0.0
GPT-3.5
Llama-118
0.00
GPT-3.5
Llama-118
(a) Selection
(b) Resampling
(c) Backtracking
(d) Caching
(e) Batching
Figure 14: Ablation analysis to study the impact of (a) Selection phase, (b) Resampling, (c) Backtracking, (d) Caching, and
(c) Batching on the performance of FoA using the SciBench task with GPT-3.5 and Llama3. 2- 1BB base models.
34


Reviews:
[{"review_id": "eXNIi3gEBe", "reviewer": "Reviewer_RBUc", "summary": "The paper introduces Fleet of Agents , a framework that coordinates multiple LLM agents using a genetic-type particle filtering approach to optimize the balance between exploration and exploitation in problem-solving tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and overall positive assessment. We hope to have comprehensively clarified all the questions and concerns of the reviewer with our responses below. We will be happy to answer any further questions that the reviewer may have and hope that the reviewer considers adapting the overall assessment of our paper.\n\n**Are the evaluation tasks adequate?** We thank the reviewer for bringing this point up. Following is our point-by-point response to answer their concern.\n\n1. **Vetted benchmarks:** We believe that we have chosen a **judicious mix** of tasks. It is important that these tasks are well established in the literature, primarily to enable meaningful comparisons with prior work. Moreover, a recent [survey on LLM agents]((https://paperswithcode.com/paper/survey-on-evaluation-of-llm-based-agents#datasets)) highlights that our tasks are among the most commonly used in the field and remain representative of current evaluation standards, a point also recognized by the other two reviewers.\n\n2. **Tasks appear easy.** While the tasks may appear easy from their description, they continue to pose a significant **challenge**, even to powerful proprietary methods. For example, using a carefully designed **CoT prompt, GPT-4 solves only 6%** of the GameOf24 challenges (our first task). Moreover, as portrayed by additional evaluation of open-source models in the appendix, our choice of tasks poses a **significant challenge for these smaller models**. For example, as shown in Table 8 in the appendix, while most methods achieve a high \"average score\" (>0.5) using GPT-3.5, only FoA portrays strong performance (average score ~0.75) with Llama 3.2-11B, whereas other methods struggle. This result corroborates the difficulty of the tasks and the strength of our FoA framework to work well with small open-source models.\n\n3. **New task.** Finally, given the suggestion from **Reviewer JAyM**, we were able to successfully add results (cf. our response to **Reviewer JAyM** under **Comparison with ReST-MCTS\\* [NeurIPS’24]**) on a new benchmark task, **SciBench**. [Table 4](https://pasteboard.co/yZGwwm3MNgY6.png) shows that on average, FoA outperforms ReST-MCTS* by obtaining a quality improvement of \\~2% while reducing the cost by \\~10%.\n\n**Would it be possible to use a dynamic number of agents in an adaptive fleet-size mechanism?**   \nWe completely agree with the reviewer that this is an interesting question and a great idea. In fact, we already highlighted this point under the limitations section (Section 7.3) of our paper. In the same section, we also bring up the concept of an adaptive fleet size as future work.\n\nOverall, we hope that our answers have satisfied the reviewer. We are confident in the strength of our contributions and believe that the experimental setup and results amply demonstrate the relevance and rigor of our work.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Good", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Weakness:\n1. I believe the three tasks are easy and a little bit too old. \n2. Current FOA implementation uses a fixed number of agents per task, while an adaptive mechanism could improve efficiency.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R5VxRl0ZIa", "reviewer": "Reviewer_JAyM", "summary": "The paper proposes Fleet of Agents (FOA), a novel multi-agent framework leveraging genetic particle filtering to enhance problem-solving capabilities of Large Language Models (LLMs). FOA achieves improved reasoning quality and significantly reduces computational costs compared to state-of-the-art methods, demonstrating strong performance across various benchmark tasks and different sizes of language models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. We are encouraged by their overall positive assessment, recognizing the novelty, strong performance, and cost-effectiveness of our method, and the extensive nature of our experiments involving diverse benchmark tasks, multiple baselines, and LLMs of different sizes. We hope to have comprehensively clarified all the concerns of the reviewer with our responses below. We will be happy to answer any further questions that the reviewer may have and hope that the reviewer considers adapting the overall assessment of our paper.\n\n**Comparison with ReST-MCTS\\* [NeurIPS’24]**: We thank the reviewer for this suggestion. So far, we were able to perform the following new experiments, which, have only strengthened the paper further. Based on the reviewer’s feedback, we are willing to extend ReST-MCTS* to the remaining two tasks within the author feedback period. All new implementations are in our GitHub repository linked from the paper.\n\n1. **ReST-MCTS\\* on SciBench**: To ensure a correct understanding of their codebase and setup, we run MCTS* (as shown in the README) for the SciBench benchmark. Not only were we able to reproduce their results (with minor variations due to inherent LLM stochasticity) but also obtained prompts for SciBench, which allowed us to extend FoA to this new benchmark with minimal added efforts. [Table 4](https://pasteboard.co/yZGwwm3MNgY6.png) shows that on average, **FoA outperforms ReST-MCTS\\* by obtaining a quality improvement of ~2% while reducing the cost by ~10%**. Once again, we’d like to highlight this point for all reviewers: **we do not craft custom prompts for FoA, but instead, we reuse the prompts provided in the official implementations, corroborating the strength of FoA as an algorithm**.\n\n2. **ReST-MCTS\\* on Game of 24**: With our improved understanding of the ReST-MCTS* codebase, we extended it to our Game of 24 benchmark. \n    1. **Tuning:** Similar to other benchmarked methods in our paper, we tuned the ReST-MCTS* hyperparameters using GPT-3.5 as the base model. We found that the branch parameter $b=5$ and iteration number $T=50$ led to the best success rate (cf. results [tuning b](https://pasteboard.co/GWbNwKHeq2sr.png) and [tuning T](https://pasteboard.co/GfuTCe4zvJqC.png)). \n    2. **Main results:** [Table 1](https://pasteboard.co/evCa1SRTigqo.png) presents results with GPT-4 as the base model and shows that FoA substantially outperforms ReST-MCTS* by being **\\~40% better in quality while requiring only \\~50% of the cost**. Owing to its exorbitant cost (~300 USD), we could not run ReST-MCTS* with $T=50$, and the presented results instead use $T=10$, thereby providing ReST-MCTS* with a similar cost budget as other baselines.\n\n**RAFA results**: We thank the reviewer for bringing this point up. We used the official implementation of RAFA provided by the authors. The difference in the results reported in our and the original RAFA paper stems from a **difference in the definition of the success rate evaluation metric**. RAFA used a relaxed version (cf. footer 1, page 50, ICML’24 camera-ready) of the success rate metric. However, for a fair comparison across all the benchmarked methods (ToT, GoT, RAFA, and FoA), we used the original implementation introduced in the ToT paper for all the baselines. As shown in [Table 5](https://pasteboard.co/5LIOBtxZKdmc.png), **using the relaxed success rate metric, our results align well** with those reported in the original RAFA paper.\n\n**Clarity in writing**: We thank the reviewer for their suggestions regarding writing clarity. Following is our point-by-point response to answer their concerns. We will utilize the extra page available for the final version to weave these details more cleanly into the main text.\n1. **Firming up mathematical formulations.**  In our theoretical discussion (lines 185-194), we describe a resampling mechanism with replacement, where samples are drawn i.i.d. from a categorical distribution. We completely agree with the reviewer’s suggestion and will fix the equations by avoiding abbreviations in the notation, including terms such as ‘i.i.d.’ in preliminaries, and providing textual explanations of the equations.\n2. **Invalid states and Sudden Death.** Depending on the task, some solution attempts may result in invalid states. For example, in a crossword puzzle, an agent might propose a word with the wrong number of characters, leading to an ill-defined state. It is standard practice, across algorithms (e.g. ToT, GoT), to prevent the search from continuing in such cases. For FoA, we use a simple filtering mechanism: when an agent enters an invalid state, it is deleted, and another agent is randomly duplicated to fill the gap. This is what we refer to as sudden death. The replacement agent is chosen uniformly at random, avoiding additional calls to the value function. We will include the aforementioned short description in Sec. 3.2 of the paper in the final version.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence. Specifically, the authors present extensive experimental results across three diverse benchmark tasks (\"Game of 24,\" \"Mini-Crosswords,\" and \"WebShop\") using multiple LLMs (GPT-3.5, GPT-4, LLaMA3.2-11B, and LLaMA3.2-90B). Their primary claims regarding FOA’s effectiveness in improving reasoning quality (~5% increase) and substantially reducing computational costs (~60% decrease) compared to state-of-the-art methods are substantiated by detailed comparisons against multiple baselines (e.g., IO, CoT, CoT-SC, AoT, ToT, GoT, RAFA, LASER, LATS) on clearly defined metrics.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are appropriate and make sense for the problem at hand.", "theoretical_claims": "1. In line188, right column, ‘, cat. resampling distr.’ are those typos? Could you make this mathematical part clearer, and also ‘iid’ maybe you should specify those preliminaries  in your articles? I mean while use those terminology, maybe also write those in lines, to better understand \n\n2.  What do you want to express in line 194, right column", "experimental_designs_or_analyses": "Yes\n\n Why RAFA results don’t align with the paper “Reason for Future, Act for Now: A Principled Architectur for Autonomous LLM Agents” , what’s the difference between the origin codebase and your experiment", "relation_to_broader_scientific_literature": "Related to test-time scaling method for LLM reasoning such as COT, TOT", "essential_references_not_discussed": "I would like to see comparison and discussion with ReST-MCTS", "other_strengths_and_weaknesses": "Strengths:\n\n1. **Innovative Method** – The paper introduces a novel approach that advances the current state of the field.\n2. **State-of-the-Art Results** – The proposed method achieves competitive or superior performance compared to existing benchmarks.\n3. **Cost-Effective Solution** – The approach demonstrates strong performance while maintaining efficiency in terms of computational or resource costs.\nWeaknesses:\n\n**Clarity in Writing** – Some parts of the manuscript, particularly the mathematical formulations, lack clarity and could benefit from improved explanations and notation consistency.", "other_comments_or_suggestions": "1. In table 1, if you could not run RAFA, maybe just don’t present it.", "questions_for_authors": "1. In line 166, how do u define an invalid state, , and how do the resembling of it uniform, it’s not quiet Clear. And since the bullet point here is sudden death, but you don’t mention what’s actually is define as sudden death which is ill writing", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "w54DxQWO8e", "reviewer": "Reviewer_Mfui", "summary": "The word produces a novel framework, FOA, that employes LLMs agents for dynamic tree search using genetic-type particle filtering approach. The multiple agents provide dynamic branching and adapting the exploration strategy. A major claim is to improve the cost-efficiency of multi-query methods. The paper compares FOA against several benchmarks like IO prompting, CoT, AoT, ToT, GoT, over tasks like Game of 24, Mini Crosswords, WebShop\",with favorable results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and thoughtful review. We appreciate the positive assessment, recognizing the new state-of-the-art performance of our method and its extensive evaluation. We are grateful for the reviewer’s thoughtful engagement, and hope that our clarifications help address the concerns raised. We will be happy to answer any further questions that the reviewer may have and would appreciate it if the reviewer would consider updating their score in light of this response.\n\n**Is this mainly an engineering work, and as such, a good fit for ICML?** We believe that the reviewer’s main concern originates from a misunderstanding about the nature of our work, which we clarify below with a point-by-point response.\n\n1. **FoA is a principled algorithm.** We completely agree with the reviewer that our research is built on a significant engineering effort. However, our work also makes a meaningful contribution beyond architectural or engineering work. To the best of our knowledge, the application of genetic particle filtering to LLM-based reasoning processes is novel. We present a principled formulation of the algorithm and provide a deep empirical analysis of its behavior through extensive ablations.\n\n2. **FoA is a runtime and doesn’t rely on crafted prompts.** We would like to highlight that unlike all existing works, we do not craft custom prompts for FOA, but instead, we reuse the prompts (cf. Appx. C.3 for details) provided by ToT (Yao et al., 2024) for the “Game of 24” and “Mini Crosswords” tasks and LATS (Zhou et al., 2024) for the “WebShop” task. This ensures a direct and fair comparison of the reasoning abilities of the benchmarked frameworks and controls for the impact of prompt quality, which is a confounder. (Lines 240-247, paper). Moreover, we would also like to highlight our response to **Reviewer JAyM** under **Comparison with ReST-MCTS\\* [NeurIPS’24]**, where FoA was extended to a new benchmark task, SciBench, without any prompt tuning, **corroborating its strength as an algorithm**.\n\n3. **ICML's historical inclination towards Applied ML research.** Finally, we believe our work aligns well with ICML’s long-standing interest in applied machine learning research, particularly work that enables new capabilities, systematically explores trade-offs, and provides reproducible insights grounded in empirical evaluation. Few examples below:\n    1. Fast support vector machine training and classification on graphics processors (ICML 2008) https://dl.acm.org/doi/10.1145/1390156.1390170\n    2. Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures (ICML 2013)https://proceedings.mlr.press/v28/bergstra13.html \n    3. Scaling Laws for Fine-Grained Mixture of Experts (ICML 2024) https://proceedings.mlr.press/v235/ludziejewski24a.html\n\n**Access to supplementary material**\n\nAll artifacts of our research, including code, data, and prompts, are publicly available at: https://anonymous.4open.science/r/FoA-4D83. Our results are fully reproducible.\n\n**Note:** Humbly and politely, it is our impression that the reviewer's comment in **Claims and Evidence** is cut-off. We welcome any feedback coming our way. If the reviewer would clarify their intention, we would greatly appreciate it and act upon it.", "claims_and_evidence": "The claims are fairly evident as the method is developed through thr paper. They are\n. FOA i", "methods_and_evaluation_criteria": "The benchmark tasks appear appropriate because they require different reasoning, planning, and problem-solving skills. Using success rate (for \"Game of 24\"), overlap (for \"Mini Crosswords\"), and average score (for \"WebShop\") appears to be standard, judging from benchmark results being there.", "theoretical_claims": "There aren't any.", "experimental_designs_or_analyses": "This is a design oriented work. But it justifies the choices made with bnchmarking, ablation studies, and cost-quality trade-off and model size and quality analyses.", "relation_to_broader_scientific_literature": "Figure 2 IMV is a broad juxtaposition. \n\nUnless the LR is insufficient, I see a good amount of positioning arounf *-of-thought reasoning models.", "essential_references_not_discussed": "I'm not well positioned to enunciate that.", "other_strengths_and_weaknesses": "It is an architectural, engineering work. Unless the culture at icml is shifting, that is peripheral to   the former.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers reached an agreement on weak accept. Hope the authors can address the weaknesses in the camera-ready version.
Decision: Accept (poster)