Interactive Speculative Planning: Enhance Agent Efficiency through Co-design of System and User Interface
Authors: Wenyue Hua
Mengting Wan
JAGANNATH SHASHANK SUBRAMANYA SAI VADREVU
Ryan Nadel
Yongfeng Zhang
Chi Wang
Venue: ICLR 2025 Poster (2025)
Keywords: large language model
agent
efficiency
human-computer interaction
Primary area: infrastructure, software libraries, hardware, systems, etc.
TL;DR: This paper accelerates LLM-based agent planning by interactive speculative planning with system design as well as human-computer interaction

Abstract: Agents, as user-centric tools, are increasingly deployed for human task delegation, assisting with a broad spectrum of requests by generating thoughts, engaging with user proxies, and producing action plans. However, agents based on large language models often face substantial planning latency due to two primary factors: the efficiency limitations of the underlying LLMs due to their large size and high demand, and the structural complexity of the agents due to the extensive generation of intermediate steps to produce the final output. Given that inefficiency in service provision can undermine the value of automation for users, this paper presents a human-centered efficient agent planning method – Interactive Speculative Planning – aiming at enhancing the efficiency of agent planning through both system design and user interaction. Our approach advocates for the co-design of the agent system and user interface, underscoring the importance of an agent system that can fluidly manage user interactions and interruptions. By integrating human interruptions as a fundamental component of the system, we not only make it more user-centric but also expedite the entire process by leveraging human-in-the-loop interactions to provide accurate intermediate steps.

Published as a conference paper at ICLR 2025
INTERACTIVE SPECULATIVE PLANNING: ENHANCE AGENT EFFICIENCY THROUGH CO-DESIGN OF SYSTEM AND USER INTERFACE
Wenyue Hua *1
Mengting Wan', Shashank Vadrevu', Ryan Nadel?, Yongfeng Zhang' and Chi Wang
Rutgers University, New Brunswick, MiiCoosoft, "Google Deepmind
ABSTRACT
Agents, as user-centric tools, are increasingly deployed for human task delega- tion, assisting with broad spectrum of requests by generating thoughts, engaging with user proxies, and producing action plans. However, agents based on large language models (LLMs) often face substantial planning latency due to two pri- mary factors: the efficiency limitations of the underlying LLMs due to their large size and high demand, and the structural complexity of the agents due to the ex- tensive generation of intermediate thoughts to produce the final output. Given that inefficiency in service provision can undermine the value of automation for users, this paper presents human-centered efficient agent planning method - Interac- tive Speculative Planming aiming at enhancing the efficiency of agent planning through both system design and human-Al interaction. Our approach advocates for the co-design of the agent system and user interface, underscoring the impor- tance of an agent system that can fluidly manage user interactions and interrup- tions. By integrating human interruptions as a fundamental component of the sys- tem, not only make it more user-centric but also expedite the entire process by leveraging human-in -nman-in-the-loop interactions to provide accurate intermediate steps.
INTRODUCTION
Large language models (LLMs) have demonstrated strong reasoning abilities (Zhang et al. 2024c Qiao et al. 2022: Fan et al. 2023 2024 Jin et al. 2024), enabling them to plan and interact with external tools and the real world. This has led to the development of LLM-based agents, which have become popular as task solvers and human assistants. Various agent frameworks have been created to facilitate these applications, including single-agent systems such Langchain (Topsakal & Akinci 2023), OpenAGl (Ge et al., 2024), and HuggingGPT (Shen et al. 2024), as well as multi- agent systems like AutoGen (Wu et al.) 2023), MetaGPT (Hong et al. (023). ) BabyAGI (Nakajima 2023). and Camel (Li et al.) 2023). Numerous methods have also been proposed to enhance the
performance of LLM-based agents, ranging from chain-of-thought (eei al. 2022). tree-of-thought
Yao et al. 2024), ReAct (Yao et al. 2022). Reflexion (Shinn et al. 2024 to mulli-agent discussion
(Cha et al. 2023) systems.
These geghhrerformin advancements in agents often come at the expense of time efficiency (Zhou al. al.]] [ et [2024]] Zhang al. (024b)) which can be attributed two main factors: (1) the underlying backbone language model can be inefficient due to its growing size and high request volume, and (2) the complex agent structure, such as tree-of-thought and ReAct, requires generating prolonged thought before the final answer, leading to extended waiting time and increased token generation costs, and blue (3) the sequential nature of action steps in plans, where one action must be completed before the next can begin, also exacerbates the situation. However, not all steps in agent
"ork done as Microsoft Research intern. Work done while working Microsoft Research.

---

Published as a conference paper at ICLR 2025
planning necessitate computationally intensive thought processes, making the universal application of complex agent architectures or agents with advanced backbone LLMs inefficient.
Moreover, demonstrated in classic human-computer interaction studies (MacKenzie & Ware [993), system latency is critical factor in shaping user experience. Prolonged delays during human- computer interaction can lead to increased stress levels, frustration, decreased task performance, and reduced user satisfaction (MacKenzie & Ware 1993 Jota et al. 2013 Barron et al. 2004 [Simpson al. 2007 Carr et al., (992). While LLM-based agent systems are designed to assist users, few have been designed to prioritize user experience, which is arguably one of the most important aspects of any human-Al interactive systems. Particularly in scenarios where complex tasks are delegated to LLM-based agents, often involving high stakes and complex decision decision-making processes, users may not anxiously wait for the agent to respond all at once, but rather expect the agent provide timely feedback so that they can effectively direct the process (Lubars & Tan, 2019; Hemmer et al. 2023) Thus we argue that fully automated "blackbox" agent system with prolonged response delays is suboptimal for user experience- prevalent issue in most LLM-based agent systems today. Instead, a responsive time-efficient mixed-initiative system is required to address this challenge (Horvitz, 1999). Thus focus designing synchronous user interaction where human is in the loop and waiting for agent response real time.
This work aims to address the time efficiency and perceived latency issue from both algo- rithmic system design and human interaction perspectives. We introduce an interactive ef- ficient planning algorithm, Interactive Specu- lative Planning, marking the first LLM-based agent system dedicated to enhancing time ef- ficiency well as managing human interac- tions and interruptions. As demonstrated in Figure []] this approach seamlessly integrates time efficiency and numan-in-the-lowt tion, anticipating and managing user engage- ment during periods of extended latency. By treating input intermediate results, the system accelerates the overall process, thereby improving both system time efficiency and user experience. Consequently, this system offers more user-centric and time-efficient solution for agents as human delegates.
Speculative Planning
approximation agent
target agent
Split money
Verify A's Venmo
Verify B's Venmo
Verify C's Venmo
Query
interac-
Handle Active User Interaction
Reschedue Mechanism
Progress
Interaction
Split money
System-Level Parallelization The system- level algorithm, speculative planning, is in- spired by recent advancements in speculative decoding (Leviathan et al. 2023 Liu et al. 2023a; Chen et al. [023 Spector & Re 2023
Verify A's Venmo
Verify B's Venmo
Verify C's Venmo
Interfaee
Figure 1: Interactive Speculative Planning: user query handled by speculative planning with approximation and target agent. Then rescheduling mechanism serializes the computed result on UI and enables the user to actively interact with the system for further acceleration. Finger-pointed action is the action intervened by the user.
Liu et al. 2024; Cai et al. 2024). It lever- ages dual-agent framework:
efficient yet less capable approximation agent, and slower but more powerful target agent. For each task, the approximation agent generates action steps sequentially. Concurrently, for every step pro- duced by the approximation agent, the target agent is asynchronously invoked to generate the subsequent step, using the current trajectory from the approximation agent as a provisional prefix. In this setup, calls to the approximation agent are sequential, whereas those to the target agent are asynchronous. For each action step, if the outputs of both agents match, the process continues; otherwise, the approximation agent is halted, and its output is replaced by the target agent's output to maintain performance integrity. This strategy potentially reduces the time a target agent takes to complete the task that of the approximation agent, thereby enhancing time efficiency. It should
2

---

Published as a conference paper at ICLR 2025
be noted that while consider a single user interface of the agent system, the system backend can be built with various architectures, including a multi-agent design.
UI-Level Rescheduling Note that under the speculative planning algorithm, target agent calls are asynchronous, leading to non-sequential outputs. To facilitate user interaction, we introduce UI- level rescheduling algorithm (Oh et al. 2024, [hhng al.) 2024) Mei et al.] [0244] Jawahar et al.]
2023 Srivatsa et al.) 2024) that presents both the approximation and target agent's 's results sequen- tially. This sequential presentation enables users to accurately perceive the computational latency imposed by the target agent. Consequently, they may intervene at their discretion, such when computation step is prolonged or yields erroncous results. Therefore, Interactive Speculative Plan- ning enables active human involvement in the decision-making process, allowing users to interrupt extended processes and evaluate whether to accept or rectify the algorithm's outputs. This human- loop approach complements the algorithmic evaluation of the approximation agent's results, making the system more user-centric.
In summary, with active user intervention, Interactive Speculative Planning be viewed as an interactive framework involving three agents: the approximation agent, the target agent, and the human agent. These three agents collaborate and interleave their operations to collectively accelerate the overall agent planning process.
RELATED WORK
Various agent systems (Xi et al. 2023 Liu et al.
2023b Ge al. 2023) have been developed
including single agent such as Hugginggpt (Shen et al. 2024). OpenAGl (Ge et al., 2024). and
BGI (Nakajima 2023), and multi-agent systems (Du et al. 2023) such AutoGien (Wu al.,
Zhang et al. 2024a) and Camel (Li et al. 2023). based on the strong reasoning ability (Wu al. 2024 Zhang et al. 2023b) and common sense knowledge (Kwon et al. 2024) encoded in LLMs. To improve the performance of LLM- agents, various methods have been proposed. The most basic approach is the chain-of-thougle (Wei et al., (022)) where the LLM generates a step- by-step thought process for each action. More advanced methods include ReAcc (Yao et al., (022), where the agent thinks before acting, and Reflexion (Shinn et al. 2024), where the agent thinks, acts, and reflects on its decisions. The tree-of-thoughts (Yao et al. 2024) method involves the agent thinking several steps ahead before acting. Additionally, multi-agent discussion systems (Du et al.) 2023 Hua et al. 2023 Lin al.) 2024 Wu al. 2023) have been developed, where multiple agents discuss and debate to enhance performance. It generally observed that stronger backbone models and more complex multi-LLM interaction usually leads to better performing agents (Wang et al., 2024
2023
Li et al. 2024 Chen et al., 2024).
However, these improvements in agent performance often come at the expense of time efficiency as longer thought processes result in extended waiting times. Although agent task can be intricate, and sometimes only the most powerful models may be capable of executing them effectively as suggested by (Xie et al. 2024), not all steps within a task are equally challenging to plan and generate (Zhang et al., [023a] Saha et al. 2024). Therefore, a dynamic selection of appropriate LLMs for specific tasks can be viable strategy to balance performance and efficiency/cost.
Numerous methods have been developed to enhance agent efficiency (Zhang al. 2023a Ding
et al. 2024a| Saha et al. 2024). EcoAssistant (Zhang et al. (023a) is the first system aimed at cost- efficient agents, initiating tasks with the most economical agent and switching more capable and expensive agents only upon failure of the cheaper alternative. The System-1.x Planner (Saha et al.) 2024] introduced a controllable planning framework using language models, capable generating hybrid plans and balancing between complex and simple agent planning strategies based on problem difficulty, potentially offering both time and cost efficiency. However, the System-l.x Planner is limited to specific planning strategies and necessitates extensive training. In contrast, our proposed Interactive Speculative Planning can adopt any combination of approximation and target agent in a training- free manner, guaranteeing performance that is at least equivalent to, and potentially superior to (with user interventions), that of the target agent alone.
INTERACTIVE SPECULATIVE PLANNING
Interactive Speculative Planning is a collaborative framework that enhances the efficiency and accu- racy of agent planning by integrating the efforts of three agents: the approximation agent, the target
3

---

Published as a conference paper at ICLR 2025
time scale
Approximation
money
requasst money from A
apprcc maaloo RgArt prOCuES
Target
split money
canceled appirs appacsiration procece
carolled tegel
veriy Vanmo
gerwented Injerney
cation
and larget mammatinne
approvimation
Approximation
spli verily A's Venin
verify B's Vermo
verty Cs
request money from A
requeest money
Target
split money, verily A' Venma
vartty B's Vanmo
request money from A
request money
Approximation
split money
verily Venmo, request money from A, request money from
verily
request money from request money from C terminaste
veriy C's Venmo,
vartly Als Venmo, vertly C's Venmo, request money from request money from B
spil
verify B's Vermoo.
Target
request money
request from
teminaate
A demonstration of the Speculative Planning Algorithm, where the cross symbol indicates the step where the A's computed result differs from that of T.
Figure 2:
agent, and the human agent. The approximation agent generates quick but potentially inaccurate steps, while the target agent verifies and refines these steps. The human agent intervenes to correct or optimize the speed of planning process, ensuring that the final plan aligns with user expectations. This interactive approach accelerates the overall planning process and enhances user experience by reducing response delays and allowing for real sal-timme adjustments.
In this section, we introduce the system-level speculative planning algorithm, provide detailed analysis of its time efficiency, and then discuss the anticipated user interaction paradigm and how is incorporated into the system.
Speculative Planning Algorithm is technique designed to accelerate the planning process of slow but powerful target agent T.Ir utilizes fast and efficient approximation agent A to draft the plan step by step. Instead waiting for to finish all preceding steps, .A's action history is used as a prefix for to generate the next step. This approach allows T begin processing subsequent steps sooner, effectively speeding up the overall planning process by leveraging the groundwork laid by A. For every length-i prefix (the first steps) generated by A, both agents generate the (i+ (i+h)-th step simultancously, without waiting for T to finish the i-th step. If the i-th step of the plan generated by both agents matches after T finishes it, then the more efficient but less capable agent A is deemed to have correctly computed the step, and T's (i+1)-th) step computed based on it is usable. Time thus saved because the time for to compute steps and i+1 is reduced to the time taken by A to compute step i and T to compute step i+1. However, if there is mismatch, it implies that A has erred at the i-th step, and we will replace i-th step with I's result. Furthermore, all concurrent calls of A and T with prefixes longer than i must be halted and discarded, they are based on an incorrect prefix and their results are unusable. In short, this algorithm achieves time savings by having T utilize the result generated by the fast as prefix generate the next step, rather than waiting for prefix steps from the slower T to be completed.
Figure illustrates scenario where person and their friends A, B. and C go to restaurant, pay the bill, and need to split the cost among themselves. In this example, the time to compute the first two steps "Split money, verify A's Venmo" using speculative planning is shorter than using normal

---

Published as a conference paper at ICLR 2025
Y the number of planning steps for a task the time the approximation agent AA takes to generate step in the plan the time the target agent T takes to generate step s in the plan ceeee the time to execute step in the plan and return an observation
time AA, 8) time (T.e)T.)) c(()
--===1 (lime (A, 8,) + e(s,)) which indicates
equals to "j=b+1
start_time (T, s.)
the start time of T to generate step s; since the one previous breaking point b.
Notice that start coirrtttmeeT__... s2) start terrttttmee.....
it equals Σ "j=r= -o.. comt -...............................
-j=b+1 (lime 8,) + c(5))) (imeeTT,s)) which indicates
................................ ......
end_lime 8.)
the end time of T of generate step 9; since the one previous breaking point b
Table 1: Notation Summary
agent planning: Speculative Planning requires the sum of A's time to compute the first step and T's time to compute the second step; In contrast, normal agent planning requires the sum of T's time to compute the first step and T's time to compute the second step. However, as the second step computed by A "requesst money from A" does not match T's output - "verify A's Venmo", all following steps based on the action trajectory that includes A's incorrect second step become invalid. This includes the third process of T, the third step from A, and on.
To prevent an excessive number of concurrent target agent processes, we introduce hyperparam- eter l to the speculative planning algorithm. This parameter sets a limit on the maximum number of steps that A that can sequentially generate and being executed before all corresponding target agent processes are completed. By controlling the value of k, users can flexibly manage the maxi- mum number of concurrent target agent processes. Speculative planning algorithm is presented in Algorithm Tin in Appendix A
Here analyze the time efficiency improvement brought by the spec- ulative planning algorithm. We summarize the notations in Table When we do not utilize specula- tive planning, the time taken to generate and execute the whole plan is Eisn (time(T, 8.) e(s,))- To compute the time when employing speculative planning, we first define the list of breaking steps B, which consists of indices of steps the plan where the sequential generation of A is halted, iee. when A's prediction a, = A(i)) differs from T's prediction t; Tii) for the i-th step in the planning, as well as when the number of consecutive speculative steps generated by the approxima- tion process reaches the hyperparameter A
Time Efficiency Analysis
The time taken to generate and execute the entire plan is then determined by the following equation, where the time to compute each sequence of steps between two consecutive elements B; and B in B, which is determined by step that takes longest time to compute for the target agent T:
(max (endJlime (82) B 1 s s Ba+))
Best case scenario is that no step generated by A differs from the step generated by T. Thus in this specific case, the breaking points B is simply all numbers smaller than n that are divisible by k, and the computing time for the best case is:
Eje(i mod k=Olism)( max end.time s,)))
(2)
isjeitk
Worst case scenario is that all steps generated by A are rejected by T. In this extreme case, the set of breaking steps, B comprises all integers from 0 to n - 1. Under these circumstances, the time taken generate and execute the plan downgrades to normal agent planning, as no steps from A is usable and no time can be saved. Assuming there is no latency to compare A's result and 7's result, the total time is simply calculating the sum of the time taken generate and execute each step in the plan by T sequentially:
1 st) + e(s;))
The aforementioned worst-case scenario demonstrates that, in terms time efficiency, specu- lative planning is upper-bounded by the time taken in non-speculative planning. More analysis
For notational convenience, we add -1 as the first element and 1 the last element in the list
5

---

Published as a conference paper at ICLR 2025
on different aspects of speculative planning including total token generated which correspond the cost and maximum number concurrent LLM/API calls required are presented in Appendix The impact of different settings time efficiency including speed and accuracy of A, the choice of and their interleaved relationship are presented in Appendix C.4
User Interface and Interaction Design Now we present the interaction component of Interactive Speculative Plamning. The user interface (UT) has two main objectives: (1) from the aspect of perception, it aims to provide the user with an easy-to-follow result and a basic understanding of the algorithm's inner workings, allowing the user to T's computation time for each step and how A is saving time; (2) from the aspect of interaction, it aims to provide system support for the user to actively interact with interrupt the ongoing agent processes when T taking too long for step or neither A nor T provides a satisfying step proposal during generation. Therefore, the user interface, together with the underlying system mechanism design, primarily addresses two key aspects: (1) what the users should see and (2) how the system can handle user interactions.
Asstep
Asstop 4
Tistep
Tistep
User Interface
Asstop B
Asstep
T: stop
approximation
actions that not printed misordered printed actions
action step that approximatoo and target mismatches
target
Figure 3: User interface issues stemming from immediate presentation computed action steps. For the first goal, notice that immediately printing the outputs of A and T upon generation can be very confusing for two reasons: (1) some outputs of A and T should not be shown to the user all, and (2) the outputs of T are misordered. Figure 3 presents an example scenario for the two issues. For issue 1: AAs output the second step of the plan mismatches with T's output, and thus all results generated by .A based on the mistaken "step 2" will ultimately be discarded. However, an immediate output of the agent's generation will present A's computed steps "step 3, 5" and T's computed steps "step 3, 4" which are generated based on the wrong prefix. For issue 2: as all T's calls are asynchronous, the time for each step to finish will follow sequential order, and thus an immediate printing out of the generated output will not be sequential either. Therefore, rescheduling mechanism is needed provide clear presentation of the algorithm.
To ensure an understandable user interface to track the agents' progress and facilitate user interven- tion, the presented output rescheduled by Reschedule Mechanism. This mechanism allows the user to view verified and to-be-verified computed steps of AA and T with minimal perceived latency. The Reschedule Mechanism, shown in Algorithm 2 in Appendix B takes the queue A processes and the queue of T processes input, tracing the last printed out message from either A and T. and then decide which message to present next to the user: (1) it presents the i-th step from A only after all preceding steps from A have been confirmed to be consistent with T. ensuring that steps computed based on unverified prefixes are presented (2) it presents the i-th step from only after all preceding steps from T have been presented, ensuring sequential order. This design not only

---

Published as a conference paper at ICLR 2025
ensures sequential presentation but also highlights the time difference between A and T, allowing the user to identify which action is bottlenecking the program.
For the second goal, we enable users to actively interrupt the program at any time. Unlike current user interface designs in various agent systems (Wu et al., 2023) where users are allowed to interact with the system when being passively prompted to input information opinions, users are more inclined to actively engage in the agent task delegation process (Lubars & Tan 2019). We handle user interaction in two common scenarios: (1) when noticing excessive perceived latency between the last presented output of AA and the next output of 'T (assuming A's generation speed is sufficiently fast that users would not typically interrupt it), and (2) when dissatisfied with the outputs of T for a given step. For the first scenario, since the user interface presentation for the i-th step of the plan can indicate the latency 4 between the presentation of the i-th approximation output and the i-th target output 1,, users can choose to interrupt during the time of 1, and input their own value. The underlying system will handle this keyboard interruption by halting the i-th process of T. incorporating the user's input into the agent action trajectory without disturbing other concurrent processes. In the second scenario, users are able to interrupt the program if they deem the results from T unsatisfactory for given step. During the brief presentation of the output t; for any step i, users can intervene and input their preferred optimal step for step as an oracle. The algorithm 2 is presented in Appendix B The experiment study the impact of user interruption and time efficiency is provided in Appendix C.4
believe that
4 EXPERIMENT
This section presents the results agent planning benchmarks: OpenAGl (Ge et al. 2024) and TravelPlanner validation (Xie et al. 2024). For each benchmark, we implement speculative planning with four different configurations.
Benchmarks OpenAGI is benchmark designed for agent planning with complex tasks, built on computer vision and natural language processing-related tasks. Tools accessible to the agents in- clude "Sentiment Analysis", "Machine Translation", "Object Detection", "Visual Question Answer- ing," etc. An example task in the benchmark is "Restore noisy, low- resolutiot,,,, blurry, and grayscale images to regular images," " whose solution sequence of tool usage: "Image Super-resolution, Image Denoising, Image Deblurring, Colorization." This benchmark contains 117 multi-step tasks.
TravelPlanner is a benchmark focusing on travel planning. It provides rich sandbox environment, various tools for accessing nearly four million data records, and meticulously curated planning in- tents and reference plans. These plans also involve many constraints, including budget constraints, environmental constraints, etc. An example task is "Please plan a travel itinerary for me. I'm depart- ing from Cincinnati and heading to Norfolk for three days. The dates of travel are from March 10th to March 12th, 2022. I have a budget of $1,400 for this trip." whose solution contains sequence of actions such as "FlightSearch( tion name for the action while "Cincinnati, Norfolk, 2023-03-12" is the natural language free-form parameter for "FlightSearch". We experiment on the validation dataset containing 180 datapoints.
Norfolk, 2023-03- where "FlightSearch" is the func-
Speculative Planning Settings To experiment with Interactive Speculative Planning in real-life scenarios, we demonstrate the performance by four different combinations of A and T as settings containing the most commonly used agent architecture as T.
Setting 1 A employs direct-generation-bbaee based planning with GPT-4-turbo backbone, while T uti- lizes ReAct-based planning (Yao al., 2022)) with the same backbone. For each step in the plan, T uses ReAct to first deliberate on the action and then generate it through two separate API calls, whereas A directly generates the action for that step.
Setting 2 A uses direct-generation based planning with a GPT-4-turbo backbone, and T employs chain-of-thought (CoT)-based planning with the same backbone. For each step in the plan, uses CoT to first reason and then generate the result in single API call, while A directly generates the action for that step.
Setting 3 A uses CoT-based planning with a GPT-4-turbo backbone, and T system uses multi- agent-debate (MAD) including 2 agents with rounds of discussion on every step of the plan with a GPT-4-turbo backbone. For each step in the plan, T system has two agents discuss with each other and finalize the action to take for the current step, and the while A uses CoT to first reason and then generate the result in single API call for the step.
7

---

Published as a conference paper at ICLR 2025
Setting 4 A uses tirect-generation- based planning (DG) with GPT-3.5-turbo backbone, and T uses sirect-generation- based planning with a GPT-4-turbo backbone. In this setting, both A and T directly generate the result for each step. Notice that cannot provide results for TravelPlanner in this setting, as direction generation using GPT--,5-turbo fail to provide a valid action in many cases.
In all experiments, we set & 4. We utilized one OpenAl API for experiments under Settings 1, 2, and 4, and two OpenAl APIs (one API for each agent in the multi-agent system) for experiments under Setting 3. For the OpenAGl benchmark, given its limited action space, we used exact match to verify the correctness of the output generated by A against the output of T. This ensured that the output of the speculative planning is the same as that of normal agent planning. For the Trav- elPlanner benchmark, which contains much larger action space, each action is a combination of a function name from a fixed set and natural language free-form parameters. We verified the consis- tency between the output of A and the output of TT based on an exact match of the function name and a soft match of the natural language parameters. The soft match is implemented by computing the Levenshtein distance: if the function name matched and the Levenshtein distance is smaller than 0.3, then the action is verified. As we leverage soft match to verify the output of A, it is not guar- anteed that the result from speculative planning remains the same the result from normal agent planning and therefore we also provide the accuracy performance of both normal agent planning and speculative planning, presented in Appendix D
Metrics
Settings
Setting
ReAct
Setting 2
CoT
Setting
MAD
Setting
DG
TT
33.9
43.63
28.61 3.53
39.96.97.07
105.
182.70
1.63
5.77
Min-TT
6.50
9,16
8.60
28.24
$0.89
1,70
2.23
8.69ga.7 to
5.52 m
21.50_..40
34.84gra nt
Li4gans
Min-ST
2.33
4.11
0.50
3.81
11.70
19.21
0.75
1.03
TO
1920gs7i.77
1812 89 89338333
1770.61
41010.4
1397 90.70.
6781 (3:33005
4075 A41000
107. (33.05
40.1 1333.33
Min-TO
760
652
455
352
1754
144)
47
17
80
288.72
2666 14-
281.92 488.77
229
1885 2200 77
836.65
1112 as
26.47.nm0
10.14 Me
Min-SO
190.00
166.58
143.83
162.8
877
558.33
19.2
MC
4.66vu.3
4.49
1e000
4.5 4.53.0.36
1e0m
4.05
Min-MC
3
cost
50.122
13
$0.074gmmm
50,064
S0.29733
240 1947 50.2160ga.oms
50.0012 22.001 001
50.0012 c00
Table 2: Main experiment results on OpenAGl benchmark.
Evaluation Metrics In terms of time efficiency, we report the cross-dataset average and minimum total generation time (recorded in second), as well as the cross-dataset average and minimum step- wise generation time, for all planning tasks across experimental setting, compared with the normal planning setting. It important to note that the total generation time heavily depends on the number of steps in the plan, which can be influenced by randomness. Therefore, we provide the stepwise generation time, which mitigates the effect of randomness related to the number of steps. To provide a comprehensive understanding of the algorithm, we also include metrics related to the total number of tokens generated during the process and the total API cost.
In total, there are 11 metrics: (1) total time (TT), (2) the minimum total time across the dataset (min-TT), (3) stepwise time (ST), (4) the minimum stepwise time across the dataset (min-ST), (5) Total tokens generated (TO), (6) the minimum total tokens generated across the dataset (min-TO), (7) stepwise tokens generated (SO), (8) the minimum stepwise tokens generated across the dataset (min-SO), (9) maximum concurrent API calls (MC) (10) the minimum maximum concurrent API calls across the dataset (min-MC), (11) the average total cost used to finish the plan (cost).
4.1 MAIN EXPERIMENT RESULT
Table presents the results on OpenAGI dataset. In Setting where T utilizes ReAct, we cut the total running time on average by 22.27% % percentage and the stepwise running time on average by about 31.87%. In Setting where T utilizes COT, we cut the total running time on average by 28.32% and the stepwise running time on average by about 30.83%. In Setting 4 where both A and T uses direct generation but with different backbone models, we cut the total running time on average about 20.37% percentage and the stepwise running time on average by about 23.50%. Setting 3 includes a very slow T using a multi-agent debate; we obtain the largest efficiency improvement: this setting can cut the total time by 42.30% and the stepwise running time on average by 38.2999 29%. But notice that though time efficiency is enhance, there is an increase at cost: in the first and second settings, there is an 70% increase in monetary cost; in the third setting, the computation time decreased by about 40%, at the cost of a 37% increase in monetary cost which is relatively small because multi-agent discussion is itself very expensive prompting method; in the last setting, where
8

---

Published as a conference paper at ICLR 2025
use GPT-3.5 as the approximation agent, the computation time decreased by about 20% at almost no additional cost due to the very cheap nature GPT-3.5. Thus, we can see that the increase in cost can be mitigated if A's prompting method is simpler A''s backbone model is cheaper.
Settings
Metrics
Setting
ReAct
Setting
CoT
Setting
MAD
Setring
DG
TT
137.33
176.28 177.18
98.09
121.37
568.10
733.12
Min-TT
40.78
55.18
29.22
42.09
149.00
127.59
ST
11. 16.5..4
13
10.71+6.00
12.75+4.38
27.53=6
40.03+8.74
Min MT
4,53
7.04
2.65
4,92
12.33
23.06
TO
3751.94
2460.95.gs2.0
3082+225.00
2002, 93 -32-2..44
12353.84 12353.84+65722 do
8976.3946571
Min-TO
1389
1766
833
1329
3443
2049
SO
208.8
1ns
246.13 23 13
220.79
197.08
18 177
591.65
Min-SO
128.13
108.30
85.42
68.06
189.00
186.27
5-0.00 5
1+0.00
5+0.00
1+0.00
5.00-0.00
++0.00
Min.MC
00.11583g0.00 0957
$0.1038g6.00 0033
$0.13933000041 20.004
50.087440.012
$0.5941 9871
S0.3990 2008
Table 3: Main experiment results on TraveIPlanner benchmark.
Table 3 presents the results on TravelPlanner validation dataset. Similar to the experiment Ope- nAGI dataset, we can find noticeable time efficiency improvement when using speculative plan- ning: in Setting 1, the average latency total generation time has decreased for 21.43% while the stepwise generation time has decreased for 29.52%; Setting 2 has decreased average total time by 19.18% and the stepwise generation time by 32.53%: %;; Setting 3 has decreased average total time by 25.46 25.46% and the stepwise generation time by 31 1..%. Similar increase of cost can be observed as in the dataset OpenAGl: all the three settings observe 50% increase in cost.
4.2 ANALYSIS OF TIME IMPROVEMENT BREAKDOWN
Having observed the average time efficiency improvement for the two datasets across the four set- tings, we provide a more granular analysis of the time efficiency improvement based on the quality of A's output across datapoints in the datasets. Specifically, is saved given specific level of AA's accuracy. This analysis will allow us to identify the sources of time savings and determine which datapoints, which levels of accuracy, contribute to time efficiency improvement. For demonstration, for each dataset and each setting, we present two fig- ures: one displaying the distribution of datapoints with different levels of accuracy and the other displaying the average stepwise time efficiency improvement proportion for all levels of accuracy.
aim examine how much time
OpenAGi: Setting1 Accuracy Distribution
OpenAGi: Settingt Stepwise Timesaving
proportion whole dataset
0.5
0.40
percentage of saved
0.35
0.4
0.30
0.3
0.25
0.2
0,20
0.15
0.0
0.10
0.05
-0.
0.00
0.28
0.5 037 ae 2.600/1075 68 6.3 1.0
0.28 6.4 0.42 85 457 3e 0.800.710.35 nás aas 1.0
approximation agent accuracy
approximation agent accuracy
Figure 4: Distribution of .A's accuracy in Setting and corresponding time efficiency improvement
Figure 5 and 6 demonstrate the breaking-down results on OpenAGI dataset. Notably, Setting 1, 2, and 3 contain a significant proportion of datapoints that exhibit a perfect accuracy of AA which correspond to the largest time efficiency improvement. Nevertheless, for datapoints with lower accuracy, substantial reduction in stepwise generation time can also be observed. This trend is consistent across all settings. And notice that in Setting 3, stepwise time saving proportion can achieve almost 60% when .Ass accuracy achieves higher then 80%. Analysis for TravelPlanner dataset is presented Appendix
However, it is important to note that in almost all settings for both datasets, there are data points exhibiting "negative" time efficiency improvement, i.c., longer stepwise running times when ap- plying speculative planning compared normal agent planning. Most of these cases oceur when

---

Published as a conference paper at ICLR 2025
OpenAGl: Setting2 Accuracy
OpenAGl: Setting2 Stepwise Timesaving
proportion over whole detaset
0.4
percentage or time saved
0.4
0.3
0.2
0.2
0.1
0.1
0.0
0.0
0.27
0.75 aaa 10
approximation agent accuracy
approximation agent accuracy
Figure Distribution of .A's accuracy Setting 2 and corresponding time efficiency improvement
OpenAGl: Setting4 Accuracy Distribution
OpenAGi: Setting4 Stepwise Timesaving
proportion over the whole dataset
0.6
percentage saved
0.30
0.25
0.2
0.20
0.15
0.0
0.10
0.2
0.05
0.00
935
22 5
0.03
approximation agent accuracy
approximation agent accuracy
Figure Distribution of A's accuracy Setting and corresponding time efficiency improvement
OpenAGl: Setting3 Accuracy Distribution
OpenAGl: Setting3 Stepwise Timesaving
proportion over the whole dataset
0.5
percentage time saved
0.4
0.20
0.3
0.2
0.15
0.1
0.10
0.0
-0.
0.2
-0.3
0.00
0.4
05
08
1.0
02
925
05 066 0660 0.75 08 1.0
approximation agent accuracy
approximation agent accuracy
Figure 7: Distribution of AA's accuracy in Setting 4 and corresponding time efficiency improvement
the accuracy of AA is relatively low, scenario in which latency efficiency analysis suggests limited time efficiency improvement but no worse than normal agent planning, contrary to what we observe. This discrepancy can be attributed to two assumptions in the theoretical analysis: (1) The speeds of and are constant across different runs on the same data points. However, in actual usage, there is significant randomness involved due to the number of tokens generated in each step, causing variations in speed of both A and T even the same data point. (2) The speeds A and T not affected by multiple concurrent queries. In practice, T runs in parallel, meaning the API for T must process multiple concurrent queries, which may also slow down the overall speed for each individual call of T.
CONCLUSION
This paper introduces Interactive Speculative Planning, novel approach that integrates efficient agent system with an active user interface to enhance and accelerate agent planning with human interaction. By treating human interruptions
integral part of the system, the planning process more user-centric but also accelerate the entire system by providing correct intermediate steps. More analysis and limitations presented in Appendix F andd
not only make
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Kimberly Barron, Timothy W Simpson, Ling Rothroek, Mary Frecker, Russell R Barton, and Chris Ligetti. Graphical user interfaces for engineering design: impact response delay and training on user performance. In International Design Engineering Technical Conferences and Computers and Information Engineering Conference, volume 46962, pp. 11-20, 2004.
Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason Lee, Deming Chen, and Tri Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. arXiv preprint arXiv:2401. 10774, 2024.
David Carr, Hiroaki Hasegawa, Doug Lemmon, and Catherine Plaisant. The effects of time delays on telepathology user interface. In Proceedings of the Anmual Symposium Computer Application in Medical Care, pp. 256. American Medical Informatics Association, 1992.
Chi-Min Chan, Weize Chen, Yusheng Su, Jianxuan Yu, Wei Xue, Shanghang Zhang, Jie Fu, and Zhiyuan Liu. Chateval: Towards better Ilm-based evaluators through multi-agent debate. arXiv preprint N.Xiv::330..072001 2023.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.013/8, 2023.
Lingjiao Chen, Jared Quiney Davis, Boris Hanin, Peter Bailis, lon Stoica, Matei Zaharia, and James Zou. Are more Ilm calls all you need? towards scaling laws of compound inference systems. arXiv preprint urXiv:2403.02419, 2024.
Ke Cheng, Wen Hu, Zhi Wang, Hongen Peng, Jianguo Li, and Sheng Zhang. Slice-level scheduling for high throughput and load balanced Ilm serving. arXiv preprint arXiv:2406. 1351 2024.
Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Ruhle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. Hybrid lIm: Cost-efficient and quality-aware query routing. arXiv preprint arXiv:2404. 1461188444448, 2024a.
Dujian Ding, Bicheng Xu, and Laks VS Lakshmanan. Occam: Towards cost-efficient and accuracy- aware image classification inference. arXiv preprint 2xXiv:2406.04503 2024b.
Yilun Du Shuang Li, Antonio Torralba, Joshua Tenenbaum, and Igor Mordatch. Improv- ing factuality and reasoning in language models through multiagent debate. arXiv preprint a305v:2305. 14325, 2023.
Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, Yongfeng Zhang, and Libby Hemphill. Nphardeval: Dynamic benchmark on reasoning ability of large language models via complex- ity classes. arXiv preprint arXiv:2312. 148.90900..1 2023.
Lizhou Fan, Wenyue Hua, Xiang Li, Kaijie Zhu, Mingyu Jin, Lingyao Li, Haoyang Ling, Jinkui Chi, Jindong Wang, Xin Ma, al. Nphardeval4v: A dynamic reasoning benchmark of multimodal large language models. arXiv preprint arXiv:2403.01777 2024.
Freddy Gabbay and Avi Mendelson. Speculative execution based on value prediction. Citeseer, 1996.
Yingqiang Ge, Yujie Ren, Wenyue Hua, Shuyuan Xu, Juntao Tan, and Yongfeng Zhang. Llm as os. agents as apps: Envisioning aios, agents and the aios-agent ecosystem. arXiv e-prints, pp. arXiv-2312, 2023.
Yingqiang Ge, Wenyue Hua, Kai Mei, Juntao Tan, Shuyuan Xu, Zelong Li, Yongfeng Zhang, et al. Openagi: When Ilm meets domain experts. Advances in Neural Information Processing Systems, 36, 2024.
Patrick Hemmer, Monika Westphal, Max Schemmer, Sebastian Vetter, Michael Vössing, and Ger- hard Satzger. Human-ai collaboration: the effect of ai delegation human task performance and task satisfaction. In Proceedings of the 28th International Conference on Intelligent User Interfaces, pp. 453-463, 2023.
11

---

Published as a conference paper at ICLR 2025
Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, et al. Metagpt: Meta programming for multi- agent collaborative framework. arXiv preprint arXiv:2308.00:3 2023.
Horvitz. Principles of maixed-initiativo user interfaces. In Proceedings the SIGCHI conference on Human Factors in Computing Systems, pp. 159-166, 1999.
Wenyue Hua, Lizhou Fan, Lingyao Li, Kai Mei, Jianchao Ji, Yingqiang Ge, Libby Hemphill, and Yongfeng Zhang. War and peace (waragent): Large language model-based multi-agent simulation of world wars. arXiv preprint
2.:::2311..72222 2023.
Wenyue Hua, Xianjun Yang, Zelong Li, Cheng Wei, and Yongfeng Zhang. Trustagent: Towards safe and trustworthy Ilm-based agents through agent constitution. arXiv preprint arXiv:2402.01586. 2024.
Ganesh Jawahar, Muhammad Abgul-Mageed, Laks VS Lakshmanan, and Dujian Ding. Llm perfor- mance predictors good initializers for architecture search. arXiv preprint arXiv:2310.16712, 2023.
Mingyu Jin, Qinkai Yu, Haiyan Zhao, Wenyue Hua, Yanda Meng, Yongfeng Zhang. Mengnan Du, et al. The impact of reasoning step length on large language models. arXiv preprint 2rXiv:2401.04925 2024.
Ricardo Jota, Albert Ng. Paul Dietz, and Daniel Wigdor. How fast is fast enough? a study of the effects of latency in direct-touch pointing tasks. In Proceedings of the sigchi conference on human factors in computing systems, pp. 2291-222222 23000 2013.
Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, et al. Spectre attacks: Exploiting speculative execution. Communications of the ACM, 63(7):93-101, 2020.
Minae Kwon, Hengyuan Hu, Vivek Myers, Siddharth Karamcheti, Anca Dragan, and Dorsa Sadigh. Toward grounded commonsense reasoning. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pp. 5463-5470. IEEE, 2024.
Yaniv Leviathan, Matan Kalman, and Yossi Matias, Fast inference from transformers via speculative decoding, In International Conference Machine Learning, pp. 19274-19286. PMLR, 2023.
Guohao Li, Hasan Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Com- municative agents for" mind" exploration of large language model society. Advances in Neural Information Processing Systems, 36:51991-52008, 2023.
Junyou Li, Qin Zhang, Yangbin Yu, Qiang Fu, and Deheng Ye. More agents is all you need. arXiv preprint arXiv:2-022.05120, 2024.
Shuhang Lin, Wenyue Hua, Lingyao Li, Che-Jui Chang, Lizhou Fan, Jianchao Ji, Hang Hua, Mingyu Jin, Jiebo Luo, and Yongfeng Zhang. Battleagent: Multi-modal dynamic emulation on historical battles to complement historical analysis. arXiv preprint arX1v.2404.15332 2024.
Fangcheng Liu, Yehui Tang, Zhenhua Liu, Yunsheng Ni, Kai Han, and Yunhe Wang. Kangaroo: Lossless self-speculative decoding via double early exiting. arXiv preprint arXhv:2404.18111, 2024.
Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Ion Stoica, Zhijie Deng, Alvin Cheung, and Hao Zhang. Online speculative decoding. arXiv preprint arXiv:2310.07177, 2023a.
Zijun Liu, Yanzhe Zhang, Peng Li, Yang Liu, and Diyi Yang. Dynamic Ilm-agent network: An Ilm- agent collaboration framework with agent team optimization. arXiv preprint arXiv:2310002170, 2023b.
Brian Lubars and Chenhao Tan. Ask not what ai can do, but what ai should do: Towards a framework of task delegability. Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2025
I Scott MacKenzie and Colin Ware. Lag determinant of human performance in interactive systems. In Proceedings of the INTERACT'93 and CHI'93 conference on Human factors in computing systems, pp. 488 4938-49311 1993.
Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi, Ben L Titzer, and Toon Verwaest. Spectre is here to stay: An analysis side-channels and speculative execution. arXiv preprint 190i::190,.0178, 2019.
Kai Mei, Zelong Li, Shuyuan Xu, Ruosong Ye, Yingqiang Ge, and Yongfeng Zhang. Aios: Llm agent operating system. arXiv preprint arXiv:2403. 16971, 2024.
Yohei Nakajima. Babyagi. Retrieved April, 25:2023, 2023.
Edmund B Nightingale. Peter M Chen, and Jason Flinn. Speculative execution in a distributed file system. ACM SIGOPS operating systems review, 39(5):111-205, 2005.
Hyungjun Oh, Kihong Kim, Jaemin Kim, Sungkyun Kim, Junyeol Lee, Du-seong Chang, and Jiwon Seo. Exegpt: Constraint-aware resource scheduling for IIm inference. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2. pp. 369-384, 2024.
Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen. Reasoning with language model prompting: A survey. arXiv preprint
arXiv:2212.09550 19.09997 2022.
Swamnadeep Saha, Archiki Prasad, Justin Chih- Yao Chen, Peter Hase, Elias Stengel- and Mohit Bansal. System-1. x: Learning to balance fast and slow planning with language models. arXiv preprini arXiv:2407. 14444007.444... 2024.
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugging- gpt: Solving ai tasks with chatgpt and its friends in hugging face. Advances Neural Information Processing Systems, 36, 2024.
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
Timothy W Simpson, Kimberly Barron, Ling Rothrock, Mary Frecker, Russell R Barton, and Chris Ligetti. Impact of response delay and training on user performance with baxe- and graphical user interfaces for engineering design. Research in Engineering Design, 18:49-65. 65, 2007.
Benjamin Spector and Chris Re. Accelerating I1m inference with staged speculative decoding. arXiv preprint arXiv:2308. 230.000338. 2023.
Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, and Yiying Zhang. Preble: Efficient distributed prompt scheduling for IIm serving. 2024.
Oguzhan Topsakal and Tahir Cetin Akinci. Creating large language model applications utilizing langchain: primer on developing 11m apps fast. International Conference on Applied Engi- neering and Natural Sciences, volume 1, pp. 1050-1056, 2023.
Qineng Wang, Zihao Wang, Ying Su, Hanghang Tong, and Yangqiu Song. Rethinking the bounds of Im reasoning: Are multi-agent discussions the key? arXiv preprint arXiv:2402.18877. 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837 2022.
Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen mm applications via multi- agent conversation framework. arXiv preprint arXivv2308..88/5, 2023.
Yiran Wu, Feiran Jia, Shaokun Zhang, Hangyu Li, Erkang Zhu, Yue Wang, Yin Tat Lee, Richard Peng, Qingyun Wu, and Chi Wang. Mathchat: Converse to tackle challenging math problems with Il agents. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, 2024.
13

---

Published as a conference paper at ICLR 2025
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He. Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential large language model based agents: A survey. arXiv preprint arXtv:2309.07864 2023.
Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner: A benchmark for real-world planning with language agents. arXiv preprint arXiv:2202..0162. 2024.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprini arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
Jieyu Zhang, Ranjay Krishna, Ahmed H Awadallah, and Chi Wang. Ecoassistant: Using Ilm assistant more affordably and accurately. arXiv preprint arXiv:2310.03046, 2023a.
Shaokun Zhang, Xiaobo Xia, Zhaoqing Wang, Ling-Hao Chen, Jiale Liu, Qingyun Wu, and Tongliang Liu. Ideal: Influence-driven selective annotations empower in-context learners in large language models. arXiv preprint arXiv:2310.10873, 2023b.
Shaokun Zhang, Jieyu Zhang, Jiale Liu, Linxin Song, Chi Wang, Ranjay Krishna, and Qingyun Wu. Training language model agents without modifying language models. arXiv preprint arXiv:2402. 11359, 2024a.
Shaokun Zhang, Xiawu Zheng, Guilin Li, Chenyi Yang, Yuchao Li, Yan Wang, Fei Chao, Mengdi Wang, Shen Li, and Rongrong Ji. You only compress once: Towards effective and elastic bert compression via exploit-explons stochastic nature gradient. Neurocomputing, 599:128140) 2024b.
Yadong Zhang, Shaoguang Mao, Tao Ge, Xun Wang, Adrian de Wynter, Yan Xia, Wenshan Wu, Ting Song, Man Lan, and Furu Wei. Llm mastermind: A survey of strategic reasoning with large language models. arXiv preprint arXiv:2404.012300 2024c.
Zixuan Zhou, Xuefei Ning, Ke Hong, Tianyu Fu, Jiaming Xu, Shiyao Li, Yuming Lou, Luning Wang. Zhihang Yuan, Xiuhong Li, et al. survey on efficient inference for large language models. arXiv preprint arXiv:2404. 14294, 2024.
14

---

Published as a conference paper at ICLR 2025
A
SPECULATIVE PLANNING ALGORITHM
Algorithm 1: Speculative Planning Algorithm.
Input: Approximation agent: A, Target agent: T, task prompt p. action trajectory S = [].
TEMINATE-False, max approximation steps
Output: S i=0
while not TEMINATE do approximation step =
for approxination step k do
DoParallel
create asyne process APPROXIMATION; A(p, // will return i-th action step o, by running A approximation += create asyne process TARGET; = S)
// will return i-th action step t, by running
a, await APPROXIMATION; // wait for A to finish computation sequentially 0, EXECUTION(a))
// execute the generated plan step a; and obtain observation o update p by adding description about a; and o, i+=1
11
12
13
Sappeed([aa, o,))
// cache generated step a and correspending observation o for j do
14
if 1 is computed & 1g # ag then
0 = EXECUTION(tt)
// re-execute the generated plan step io and obtain
observation 0,
S S=$[: S[= [[t
// update cache
update by modifying i-th step based on description about t, and of cancel all ongoing APPROXIMATION processes and TARGET, if >
19
// cancel useless processes
break the outer for loop and go to line
S[-1][0] is "terminate" " then TEMINATE-True break the outer for loop
21
23
24 return S
15

---

well as when the number of times where Published as a conference paper at ICLR 2025
B RESCHEDULING MECHANISM WITH USER INTERRUPTION
Algorithm 2: Rescheduling Mechanism with User Interruption.
Function Register Handderr (target tasks, target task id)
Function Exit -xii-Handllr (signum. frame, target tasks, target.takk..... id)
trggetttskk(targett.cm taske ian.eat
End Function
SeggaalsiinallgggnnnSSTTTTTTIII partial(Exit -aniiittrr.d.r..r target_tasks, target.task_id)
ltarget task user input for action step target_task_id // prompt user input to as oracle result
End Function
Input:
Approximation process queue: As, Target process queue: Ts, Approximation result presentation index tracker a_tracker, Target result presentation index tracker t_tracker, Approximation result list as, Target result list Output: trocker, t tracker, as, ts a tracker L. tracker then
i = t_tracker
if' process As[i] is completed then
11
12
present as {] user interface
13
Tastrtasrgettsss=TTTT... Register-Handler(targe tasks=Ts,, idtttttkkkkddttttrakkee)
// setup signal handler to enable proper handling of user interruption when user is waiting for [s[t] to be computed a. bracker +=
14
15
end
end
17
else
18
i artracker
19
if process T[(]] is completed then
present ts[i] to user interface but allow user to modify ts[i] as ts[i]'
20
// enable user to directly change I's computed result (<[1] after presenting it to user f_tracker +=1
21
22
end
23
end
24
return a. a.tracker, t.tracker, as, ts
C COMPLETE EFFICIENCY ANALYSIS
In this section, we will provide theoretical analysis of the time savings (latency), total token gen- eration requirement, and concurrent API call rate required by the speculative planning approach. Additionally, we will present simulated experiment results to support our analysis and demonstrate the effectiveness of the proposed method.
C.1 TIME EFFICIENCY ANALYSIS
This subsection analyzes the time efficiency improvement brought by the speculative planning algo- rithm. We summarize the notations in Full Notation Summary
When we do not utilize speculative planning, the time taken to generate and execute the whole plan is Eisn (time(T sx)) + e(s;)). To compute the time when employing speculative plamning, first define the list of breaking steps B, which consists of indices i of steps in the plan where the sequential generation of AA is halted, i.e. when A's prediction a; = A(i) differs from T's prediction = T(t) for the i-th step in the planning, continuous speculative steps generated by the approximation process reaches the hyperparameter k. For notational convenience, we include -1 as the first element and n. the last element in B.
16

---

Published as a conference paper at ICLR 2025
the number of planning steps a task the time the approximation agent AA takes to generate step in the plan the time the target agent T takes to generate step 8 in the plan moee the time to execute step in the plan and return an observation the token the approximation agent Á requires to generate step in the plan the token the target agent T requires to generate step in the plan
time A, 8)
time time(T.s. e(s)
token AA
token T.S)
j= equals to j-bb+1 (time(A, 8;) + c(s;)), which indicates
start timeee,,e,,....
the start time of A to generate step s, since the one previous breaking point b
it equals to > j=b+1 the start time T to generate step s; since the one previous breaking point Notice that start start.time(T 8;) = start.fe Sotrrtttmmee.....
- (time( sj) + e(s;)) which indicates
start.time(T 8:)
-= it equals to j==b+1 (time 8,) + e(s;)), which indicates
(nd.time(AAss))
the end time of A generate step s; since the one previous breaking point b
- equals to jj=b+1 (time(AA 8y) + e(x))) lime (T,)) which indicates
end
the end time 7 generate step s; since the one previous breaking point
Table 4: Full Notation Summary
The time taken to generate and execute the entire plan is then determined by the following equation, where the time to compute each sequence of steps between two consecutive elements B; and Bi+1 in B, which is determined by step that takes longest time to compute for the target agent T:
Σ BB[ (mxx time(T .,2) B, 1 is s Bi+1))
(4)
time scale
Approximation
step
step 2
step
step 4
step 6: terminate
Target
step 2
step
step
step 5: terminate
Figure 8: Best scenario, assuming k
Best case scenario is that no step generated by A differs from the step generated by T, as shown Figure & Thus in this specific case, the breaking points B is simply all numbers smaller than such that mod & = 0, and the computing time for the best case is:
Σje(i mod k=olien) max end tidetit isjeith
(5)
Worst case scenario is that all steps generated by A are rejected by A. partial example is presented in Figure In this extreme case, the set of breaking steps, B comprises all integers from 0 to 1.
Under these circumstances, the time taken to generate and execute the plan downgrades to normal agent planning. This equation calculates the sum of the time taken generate and execute each step
17

---

Published as a conference paper at ICLR 2025
in the plan sequentially, without any speculative planning. The total time can be expressed as: 50sisn-1(time(7 s;) + e(s;))
The aforementioned worst-case scenario demonstrates that, in terms of time efficiency, speculative planning is upper-bounded by the time taken in non-speculative planning. This implies that the maximum time required for speculative planning will not exceed the time taken by the traditional, non-speculative approach.
time scale
approximation
step
step 2
step 3
step
step &: terminate
target
step
approximation
step 2
step 3
step
step terminate
target
step
step
Figure 9: Worst case scenario
C.2 TOTAL TOKEN REQUIRED
In this subsection, we analyze the total token generation when using the speculative planning algo- rithm.
When not utilizing speculative planning, the total number of tokens used to generate and execute the plan is Ejen tot.tooenn...... sT) Speculative planning requires more tokens, as both A and T go through the entire plan at least once, potentially generating "wasted" tokens proposed steps that are not used in the final plan which are computed based on incorrect prefix. Between any two breaking points B, and B, the number of tokens generated is the sum of tokens generated by A and T for steps 8, in between as well as "unused/wasted" tokens generated by both A and T for any step B where the process ends before T finishes all the process between any two
sj such that breaking points B, and B;+1- Thus, we represent the tokens generated Tn, between two consecutive breaking points B, and B41 below:
TB, S/=B.11 (Ioken 8;) + token 8T))
Mr Bun (loken(A, 8,) + token 88))
sum of tokces generated by A and T between B, and B
wasted tokces
18

---

Published as a conference paper at ICLR 2025
where max R1, (endttime(T.s) ss)) is the ending time for all steps between B; and 1
to be computed, and M, = min minmmax(/ ( n end_time(AA s1) s Q), k + B Bi+1 is the number
of wasted steps initiated by A, that is, all processes that ends before Q but computed based on incorrect prefix.
Thus, the ultimate total number of tokens generated is the summation of TB, s:
(8)
Best case scenario is that all steps generated by A matches those generated by T, and therefore we do not have any "wasted" tokens, and then both A and T go through the agent generation plan. In this situation, M, = O in the best case scenario for all i corresponding to B; in B.
E 8,) Loken(T, .x())
Worst case scenario is that none of the steps generated by A matches with those generated by T. Additionally, each T process finishes after all A processes are completed, and the earliest called T process always finishes the last. Figure represents a partial example. Formally, the worst case scenario will occur under the condition which can be expressed as:
Z end.timel $B..) and VB, < & Bu1,, endet sB,+1) 2 end end s1) and
VB, E B,
(10)
(11)
Vi s n - 1, 04 does not match 4/
(12)
In such a case, Q end_timel (B, + 1) and M, k - the worst case scenario. Each A process i will run for (i mod k) + 1 times (for example, the first process where i = 0 runs for time, the will run for & times, and the + 1-th process where = & will run for 1 time), and each T process i is run for i times. Consequently, the total number of tokens generated in this worst-case scenario is:
k-th process where =
- mod k) + 1) (token(A,s)) + tokee(T s;))
(13)
C.3 RATE REQUIRED
This subsection focuses on analyzing the rate required to run the speculative planning algorithm, which is determined by the maximum number of concurrently running agent calls.
When not utilizing speculative planning, all agent calls are executed sequentially. Consequently, the required rate, which is the maximum number of concurrently running agent calls, is 1. When using speculative planning. we naturally have at least concurrent calls: for A and I for T. But it can be more than 2, shown in Figure 2 where we can have many TT processes running the same moment. To determine the maximum concurrent C processes, we identify the target agent process that overlaps with the most other target processes and add for the additional approximation process. For all Ti processes for B; < l Bi+1, we find the j-th process Tj that overlaps with the most other processes by:
T
max B,sjsB,,1
(1 < n start.time(T, st) s start.time s5) s end_time(T, s()
(14)
count the namber of target processes overlapping with process j
We denote the number of overlapping processes to be CT,- Notice that we have hyperparameter set up which controls the number of sequential A calls can be conducted without waiting for all corresponding T calls to be finished. Therefore, Note that Cr; is upper-bounded by k. Since the concurrent processes are the overlapping target process plus the approximation process, Cp, = Cr, 1 which is upper-bounded by k + 1 between any consecutive B, and B
Thus, the maximum concurrent processes the maximum of all Cp,:
C max CB,
(15)
B,EB[:-1]
Best case scenario is where there is exactly concurrent processes running, I A process and 1 T process and there is time overlap between any two 'T processes. This may only oceur when for each step 8; time(T, 8;) $ time(A, s:).
Worst case scenario is when there is sequence of steps to + lo such that Vi < s i k. end time(T, > start time(T, In this case, there exists a time point where &o target processes running concurrently, resulting in a total of l + concurrent processes.
19

---

Published as a conference paper at ICLR 2025
C.4 SIMULATION EXPERIMENT FOR SPECULATIVE PLANNING
To elucidate the relationship between the performance of the Interactive Speculative Planning sys- tem and various hyperparameter configurations, we conducted three series of simulation experi- ments. Two experiments aimed to investigate the impact of different settings in speculative planning. specifically: (1) the choice of approximation agent A, (2) the parameter k; and the third experiment investigates the impact of the number of user interruptions on overall latency. For the impact of A, we examined 's accuracy relative to that of (accuracy computed by treating T result as ground truth), as well as A's computational speed. In the rest of the paper, we use A's accuracy to refer to the relative accuracy of with respect to the result T.
For the simulation experiments, we set the following parameters unchanged: (1) the plan consists of 10 steps, (2) the generation speed of
seconds per action (Lime(T, 8) = 8) (3) for each step, A generates 10 tokens (time(T, s) 10), (4) for each step. T generates 20 tokens (Time(T,5
20),
and (5) for clarity, we set execution time to be (e(s) = O).
The first series of experiments explores the impact of AA's accuracy with respect to T and the hyper- parameter planning time and total tokens generated. We fix the speed of (time(A..) () 2) to be 2 seconds per action and vary A's accuracy in {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0) and the hyperparameter of k in (1,2,3,4,3 6, 7, 103.
Figure 10 (a) provides visual representation of the impact of accuracy and the hyperparameter on the planning time. For each pair of accuracy and k, we run 10 experiments with different random seeds. The mean time and standard deviation of the average step plotted in the figure, providing a comprehensive view of how these factors influence the planning time. We also present the time required for the agent planning when using A only and T only as normal agent planning show the lower bound and upper bound of speculative planning.
is evident that higher accuracy in A results in shorter planning time. Very low l (such as k 2, 3) leads to slower agent planning, regardless of A's accuracy. For other k values, as the accuracy increases, the impact of k becomes more clear: higher i leads to shorter agent planning time. However, when the accuracy is low, the impact is less clear.
Total token genreated for planning
600
agent planning time
400
300
aporocimation only tanget only
10
40
30-
20
100
0.4
02
03
10
approximation agent acoruacy
approximation agent accruacy
(a)
(b)
Figure 10: (a) Relationship between agent planning time, A's accuracy, and (b) Relationship between total token generated, A's accuracy, and
Figure 10 (b) showcases the impact of accuracy and the hyperparameter k on the total number of tokens generated during the planning process. addition, the figure presents the tokens generated when using only A and when using only T. There two obvious trend: (1) higher accuracy in A generally results in a smaller number of tokens generated regardless
& except in the trivial case when i (2) lower & leads smaller number of tokens be generated, especially when & is small the value range of {1,2, 3, 4); otherwise is impact is less clear.
In the second series of experiments, time and generated tokens: We experiment on speed in different values: (1, 2, 3, 4, 5, 6, 7,8) and accuracy in values {0.0, 0,1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0). Here set & to be 5. Figure
study the impact of A's speed and accuracy planning
20

---

Published as conference paper at ICLR 2025
demonstrates the change of planning time: (1) smaller speed values lead to smaller planning time, ie.. quicker planning, regardless of the accuracy of A, and (2) better accuracy also leads to
quicker planning, regardless of speed.
for planning
200
esproerrttoo spent time =
aspiesemmt lime = approwmat agent
agent planning time
800
esprowimet agent time saproxmmat on agent time approsimet agent
500
asprowimet on agent time approwmat on agent time
600
only
tunget unly
total token
20
800
0.
07
04
08
0.0
1,3
0.
0.1
07
0.3
6.
0.5
0.6
0.7
approximation agent accruacy
approximmation agent accruacy
(e)
(b)
Figure 11: (a) Relationship between time and .A's accuracy and speed (b) Relationship between time and A's accuracy and speed
Figure 11 (b) demonstrates the effect on total token generated. When the speed is very quick, higher accuracy monotonically reduces the total token generated. When the speed is around half of the speed of T, accuracy does not have much impact total tokens until it gets very high. When the speed is very slow (more than half of that of the target process), the total token generated first increases and then decreases accuracy improves.
In the third series of experiments, we investi- gate the impact of user interruptions on time ef- ficiency. We conduct simulations with varying interruption times. We assume that the user is actively monitoring the agent planning process and has patience level between the speeds of the approximation agent A and the target agent which assumption is made based on (1) A is designed to be an efficient agent (2) if the user's patience exceeds the speed of T, no terruptions would occur.
approximationn agent time
5
For this simulation experiment, we 10 and the accuracy of A to be 0.5. The user is permitted to interrupt between 0 and 10 times. Each user interruption may occur randomly af- ter waiting periods ranging from I to seconds following the presentation of A's result. For each number of user interruptions, we conduct 5 simulations.
max concurrent API calls
Figure 12: Relationship between maximum concurrent rate required and A''s speed and k
The results of this simulation are presented in Figure 13 which displays the mean stepwise generation time along with the standard deviation. As anticipated, an increase in user interruptions reduces the overall latency of the system.
21

---

Published as a conference paper at ICLR 2025
average stepwise generation time
5.8
4.5
4.8
number of interruptions
Figure 13: Relationship between the number of user interruption simulation and stepwise generation time
22

---

Published as a conference paper at ICLR 2025
D IMPLEMENTATION DETAILS ON TRAVELPLANNER
To evaluate the final plans generated by normal agent planning and speculative planning, we adopt the metrics Delivery Rate and Commonsense Constraint Miero Pass Rate (the only two metries with non-trivial results):
Delivery Rate assesses whether agents can successfully deliver a final plan within a limited num- ber of steps. Falling into dead loops, experiencing numerous failed attempts, or reaching the maxi- mum number of steps (30 steps in our experimental setting) will result in failure.
Commonsense Constraint Micro Pass Rate Commonsense Constraint Pass Rate comprises eight commonsense dimensions, which evaluates whether language agent can incorporate commonsense into their plan without explicit instructions. The Macro Pass Rate indicates the ratio of passed constraints to the total number of constraints.
Below the three set of results:
Setting normal agent planning:
Delivery Rate: 55.6% Commonsense Constraint Miero Pass Rate: 48.6%
speculative planning:
Delivery Rate: 55.6% Commonsense Constraint Micro Pass Rate: 41.7%
Setting 2 normal agent planning:
Delivery Rate: 55.6% Commonsense Constraint Micro Pass Rate: 41.7%
speculative planning:
Delivery Rate: 55.6% Commonsense Constraint Micro Pass Rate: 34.7%
Setting normal agent planning:
Delivery Rate: 55.6% Commonsense Constraint Micro Pass Rate: 54.3%
speculative planning:
Delivery Rate: 55.6% Commonsense Constraint Micro Pass Rate: 48.6%
E ANALYSIS OF TIME EFFICIENCY IMPROVEMENT BREAKDOWN FOR TRAVELPLANNER
Figure and present the results for the TravelPlanner dataset. In TravelPlanner, the distri- bution of datapoints based on accuracy is flatter (we only show accuracy levels where the proportion of datapoints exceeds 2% avoid excessive randomness). In all three settings, the time efficiency improvement can achieve more than 40% when the accuracy exceeds approximately 0.4.
23

---

Published as a conference paper at ICLR 2025
TravelPianner: Setting1 Accuracy Distribution
TravelPlanner: Setting1 Stepwise Timesaving
proportion over the whole dataset
0.12
percentage saved
0.10
0.4
0.06
0.0
0.04
0.2
0.02
0.00
approximation agent accuracy
approximation agent accuracy
Figure 14: Distribution of A's accuracy in Setting and corresponding time efficiency improvement
TraveiPlanner: Setting2 Accuracy Distribution
TraveiPlanner: Setting2 Stepwise Timesaving
0.08
0.07
0.06
0.2
percentage time
0.05
proportion the
0.0
0.04
0.03
0.2
0.02
0.4
-066
approximation agent accuracy
approximation agent eccuracy
Figure 15: Distribution of .A's accuracy in Setting 2 and corresponding time efficiency improvement
TravelPlanner: Setting3 Accuracy Distribution
TravelPlanner: Setting3 Stepwise Timesaving
0.07
tinn sgved
0.06
0..5
0.05
0.04
0.44
proportion
0.02
0.00
8.75
approximation agent accuracy
approximation agent accuracy
Figure 16: Distribution of A's accuracy in Setting 3 and corresponding time efficiency improvement
24

---

Published as a conference paper at ICLR 2025
F ANALYSIS OF USER INTERACTION
One of the motivations behind Interactive Speculative Planning is users' patience. Numerous studies (Horvitz) [999; Barron et al. 2004 Simpson et al. 2007 Carr al. 1992) have demonstrated the physiological and psychological impacts interaction delays on human-computer interaction. Therefore, we aim to quantitatively study how speculative planning enhances user experience by analyzing the frequency with which a user may become impatient and desire to interact with or interrupt the system.
User Patience
User Patience
User Patience
1.0
1.0
1.0
0.8
0.8
0.8
0.0
0.0
0.0
0.28
0:39
0.50
050
0.66
0.72
0.2
2.00
0.28
8:59
0.50
0.6
0,73
0.7
2.00
0.28
8:49
0.50
080
0.6
2.00
User Patience
User Fatience
User Patience 10
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.0
0.0
0.25
8:39
0.50
0G6
1.0g
0.28
8:49
0.50
nds
0,71
0,75
geo
1.00
0.28
8:49
0.50
650
0.66
0.1
0.75
1.00
interactive speculative planning
axis: accuracy approximation agent target agent
normal agent planning
axis: proportion steps when the user gets impatient
Figure 17: Number of Potential User Interruptions with Setting on OpenAGl dataset and corresponding normal agent planning
For the quantitative study, we the OpenAGI dataset with Setting 1, 2, and 3 examples We collect statistics, including the mean and variance, on the number of user interruptions that may occur due impatience by simulating users with different impatience thresholds. For Settings and 2, we simulate users with impatience thresholds of 5, 6, 7, 8, 9, and 10 seconds. For Setting 3, which takes much longer time run, simulate users with impatience thresholds of 11, 13, 19, and 21 seconds. We also collect statistics for normal agent planning for comparison. For each setting, we provide series of six figures. In each figure, the x-axis represents A''s s accuracy, and the y-axis represents the proportion of steps for which the user may become impatient. Each figure demonstrates the number of times the user may become impatient and interact with the system under Interactive Speculative Planning and normal agent planning, with respect to groups of data points with different levels of A's accuracy.
Figures and 19 represent the results for Settings 1, 2, and 3, respectively. As expected, Interactive Speculative Planning exhibits more observable differences for more impatient users.
G LIMITATIONS AND FUTURE DIRECTIONS
Interactive Speculative Planning represents the first attempt at co-designing efficient agent system alongside an active user interface. Consequently, imperfect many aspects, and there are numerous future directions to be explored:
We do not adopt Setting here the average stepwise time for both normal agent planning and speculative planning short.
25

---

axis: proportion of steps when the user gets impatient Published as a conference paper at ICLR 2025
1.0
0.1
0.2
0.2
02
0.0
8:38
0.50
0.6
071
075
0.00
1000
0.0
0:3
0.37
8:38
0.0
1.00
0.31
060
1.00
Ratience
1.0
1.0
0.2
0.2
0.2
0.0
0.0
0.0
0.50
0.0
0.56
0.1
0.75
0,0
0.9
1.0p
0.37
8:36
0.50
0.7
0,75
Bag
0.83
1.00
0.37
0.50
2.00
0,66
071
interactive speculative planning
axis: accuracy of approximation agent target agent
normal agent planning
Figure Number Potential User Interruptions with Setting 2 on OpenAGl dataset and corresponding normal agent planning
1.0
User
1.0
User Patience
1.0
User Ratience
0.8
0.0
0.14
0.20
0.53
8:39
0.50
036
066
0.00
0.00
1.0g
0.0
0.14
0.20
8:49
0.50
0.6
0.0
0.00
1:00
0.0
0,14
0.20
0.33
0:9
0.50
0.6
0.0
0.50
1.00
User Patience 11
Usar Patiance
19
User Pationce 21
1.0
1.0
0.8
0.8
0.8
0.6
0.8
0.6
024
0.20
0.33
8:69
0.50
8:60
0.58
0.75
0.80
0,90
2.0p
0.0
0.14
0.20
0:49
0.50
0.68
0.75
0.80
0,50
3.00
0,20
0.33
0:49
0.50
0.50
0.59
6.75
0,80
0.90
1.00
interactive speculative planning
accuracy of approximation agent target agent
normal agent planning
axis: proportion of steps when the user gets impatient
Figure 19: Number of Potential User Interruptions with Setting 3 on OpenAGI dataset and
corresponding normal agent planning
Spectre Spectre Mcilroy al. 2019: Kocher et al. 2020) refers to vulnerabilities and attacks
involved in speculative execution (Kocher et al.] 22000] Gabbay & Mendelson, [996] Nightingalc
al. 2005). hardware feature that improves processor performance by predicting program's
26

---

Published as a conference paper at ICLR 2025
future execution and executing instructions ahead of the current instruction pointer. This concept analogous to speculative planning. However, speculative exccution is known to create security vulnerabilities that allow attackers to access sensitive data. In algorithm, the execution of A's steps that are unverified or inconsistent with T's steps also introduces vulnerabilities. Studies (Hua et al. 2024) have shown that smaller and weaker models more prone to unsafe and untrustworthy actions. Therefore, the applicability of Interactive Speculative Planning in its current form should be constrained to non-high-staker areas.
To address the security vulnerabilities associated with speculative execution in Interactive Specula-
tive Planning, several solutions can be implemented:
Houman-in-the-Love Verification: Incorporate suman-in-the-loon mechanisms to double- check the security of A's actions before execution. This approach leverages human over- sight ensure that potentially unsafe actions are identified and mitigated before they can cause harm.
2. Isolated Execution Environments: Execute A's actions in isolated environments, such as Docker containers. This isolation ensures that any potentially malicious or untrustworthy actions are contained and do not affect the broader system or access sensitive data.
By implementing these solutions, we can enhance the security of Interactive Speculative Planning, making it more robust and suitable for wider range applications, including those high-stakes environments.
Effectiveness of step-by-step comparison the current version of speculative planning, we em- ploy a simple and straightforward method to determine whether action proposed by A can be accepted: exact match. However, it is widely recognized that completing a task often involves mul- tiple different paths and plans, and "difference" does not necessarily imply "incorrect." There two types of differences to consider: (1) different surface strings may refer to the same step, and (2) different steps may refer to two acceptable paths for the planning. Therefore, step-by-step exact match judgment for whether A'ss output is accepted is overly aggressive and inefficient, as it essentially decreases the accuracy of A.
Consequently, there is a need for more sophisticated methods to relax the conditions for accepting actions from A. Potential solutions may include:
1. Step-by-Step Relaxed Exact Match: While still performing step-by-step checks, this ap- proach does not enforce an exact match between A's result and T's result. Instead, allows for some degree of flexibility in what constitutes match.
2. Postponed Judgment: Instead of performing step-by-step checks, T will judge whether sequence of n steps proposed by A within an acceptable range. This approach allows for more holistic evaluation of AAss proposals.
By implementing these solutions, we can enhance the effectiveness and efficiency of speculative planning, making more adaptable to the variability inherent task completion.
Balancing time and cost efficiency in speculative planning The current version of speculative planning may incur a high additional cost. Therefore, balancing time efficiency and cost efficiency becomes critical topic. Several methods can be employed to reduce the cost effectively:
1. Utilize Cost-Effective A: Employ a cheaper yet well-functioning A. This agent can be trained through knowledge distillation from T. thereby improving performance while maintaining a smaller size.
2. Enhance the Approximation- Target Judgment Method: Implement more sophisticated approximation-tant -tagett judgment method to improve the perceived accuracy of A. This ap- proach ensures that A's outputs more reliably accepted, reducing the need for costly re-evaluations by
By implementing these methods, we can achieve a better balance between time efficiency and cost efficiency in speculative planning.
27

---

Published as a conference paper at ICLR 2025
Limitations of the Current User Interface As mentioned in the algorithm design section, al- though the current user interface can handle active user input, these interactions and interruptions must be made "on time." Specifically, users cannot change the result once it is fully presented in the user interface. This limitation means that users must closely monitor the algorithm's progress, and if they miss the opportunity to intervene, there is way go back and make modifications. In the future, the user interface should support backtracing to allow users to revisit and modify previous steps, enhancing the flexibility and usability of the system.
28


Reviews:
[{"review_id": "0bnqtLUIpM", "reviewer": "Reviewer_SYAX", "summary": "Describes a speculative planning algorithm for LLM agents that assumes an approximate model and a target model. It is assumed that the target model is more capable but slower than the approximate model. Planning is performed by the approximate model until it is deemed to deviate from the target model, at which time the approximate model is corrected. Human interaction is also addressed via a rescheduling algorithm and the ability to interrupt and modify the plan.", "questions": "The evaluation could be improved by comparing a smaller and larger model from a particular model family, i.e. 8b vs. 70b llama using the same approach. \n\nAre there more efficient approaches to validating the approximate models plan without comparing directly to the target models plan?\n\nIf the user interrupts the plan, do you envision that they edit the agents trajectory directly? or provide feedback and have the agent regenerate the step?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is relevant, agents are slow and we should try to make them more responsive.\n\nThe approach is novel afaik.\n\nThe algorithm itself is clearly described.", "weaknesses": "The algorithm trades off time with efficiency. Are there ideas to also improve efficiency?\n\nThe selection of an approximate model and the target model may be difficult to satisfy, and increase system complexity in practical applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": {}}, {"review_id": "7e648Z9eaY", "reviewer": "Reviewer_y5dF", "summary": "The paper presents an interesting approach to reduce the potential latency of LLM-based systems and an approach where user and user interruptions are build into system design. The approach involves two different agents: an faster but more error-prone approximation agent and a slower but more accurate target agent. Depending on the accuracy of approximation agent, the speed of system can be significantly faster , and in the worst case, comparable to a non-speculative planning agent.", "questions": "1. Could a theoretical focus on system latency lead to newer issues in the human-AI interaction? \n2. Is this approach suitable for all tasks? A more detailed discussion would be useful.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Overall, the architecture of using a faster (but potentially inaccurate) agent and a slower (but possibly more accurate) in order to reduce the latency of the system is an interesting idea and can potentially work well for certain tasks with careful UI considerations.", "weaknesses": "1. The method applies to synchronous Human-AI interaction where a human is in the loop and waiting for agent response in real time. An entirely different application of Agents is asynchronous interaction (where a human may not be in the loop in real-time, e.g. perform this action every day at this time ..). I would encourage the authors to highlight this in order to position their work better. \n\n2. I vehemently agree with the statement \"A fully automated “blackbox” agent system with prolonged response delays is suboptimal for user experience\". However, I believe the paper uses the term \"user-centric\" a bit loosely, I am not quite sure how the current method is more \"user-centric\". There are many places of contention:\n\na) Given approximation agent and target agent can (often) disagree, it means initial responses may be overwritten or multiple intermediate responses shown to user. Without careful UI design, this can lead to user confusion and lack of transparency on what is going on. \nb) User in the loop workflow where user can actively take part in the decision making is absolutely necessary. However, in the current system, the window for interruption is basically the time for target agent to execute. The user can potentially take time to read the response from approximation agent, process it, decide if it needs to be revised manually and then potentially frame the revision in text or voice, all of which can take some amount of time.  I am failing to see how this is \"user-centric\" when user is hurried to interrupt within a window of short time.\nc) I did not fully understand how this mechanism can work when the action execution can be anything of consequence in the user interaction (e.g. sending an email or request for money to split bill on a mobile pay application). This in practice would mean, if the approximation agent is wrong, the system would perform tons of incorrect actions that can not be reversed. I would like a more detailed limitations of where this approach can work and where it should not be applied. \n \nMore generally, there are established ways to study human factors aspects of Human-AI interaction, employing carefully controlled user studies. The current \"theoretical approach\" to human factors  is an interesting first step but leave a lot of questions unanswered that could potentially make or break the interaction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": {}}, {"review_id": "xVb28AzwOx", "reviewer": "Reviewer_SCq5", "summary": "The paper introduces a speculative planning framework to improve the time efficiency of agent-based task planning. The paper tackles reducing latency by implementing two agent types. An approximation agent generates initial, potentially incorrect steps, which the more accurate target agent validates. This setup allows speculative planning to proceed concurrently, ideally saving time without sacrificing accuracy. Through experiments with two agent planning benchmarks, OpenAGI and TravelPlanner validation and metrics such as time efficiency, API costs, etc, the paper demonstrates the efficiency gains. It also allows users to get involved in the planning process. However, this aspect is speculative and has not been tested.", "questions": "Since the cost is one of the main issues:\n\n1) Under what circumstances should each evaluation metric (e.g., accuracy vs. speed vs. cost) be prioritised, and how might these impact the framework's configuration, e.g., in terms of k? The cost increase is above 60% in some cases. For example, do the authors believe there is a case for solely focusing on cost and not efficiency and vice versa?\n\n2) Do the authors have insight into reducing costs to make the approach more appealing? The appendix states: \"...Implement a more sophisticated approximation-target judgment method...\" --- What does this look like?\n\nRegarding the ability of the users to intervene, etc.:\n\n3) How do you envision training end-users on the speculative planning interface, particularly in complex tasks where they may need to understand and manage concurrent agent processes?\n\n4) Also, given that user intervention is integral to your framework, how would you design the interface to facilitate timely and accurate user decisions?\n\nRegarding resource-constrained environments:\n\n5) What considerations should be explored for scaling the speculative planning framework in resource-constrained environments, especially where concurrent instances of T may lead to bottlenecks? \n6) Since the approach's success largely depends on the accuracy of A, what do the results and analysis of k (in the appendix) indicate in terms of any minimum thresholds for A's accuracy?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) In terms of writing, the paper is well-organised and engaging. The planning algorithm is discussed well -- the speculative planning process is generally explained well. However, a more detailed discussion with a specific k-value around Fig 1 would be helpful in understanding the various scenarios and how these result due to the accuracy of A. For example, it will help the reader speculate how A's accuracy may impact the number of times replanning may be needed, etc.\n\n2) The paper evaluates various settings (e.g., ReAct, CoT, MAD, and DG), revealing a good level of depth in its potential impacts. The experiments are thorough, with 4 settings and 2 planning benchmarks (OpenAGI and TravelPlanner). Metrics such as time efficiency, API costs, and stepwise validation provide a good depth of analysis, both positive and negative aspects.\n\n3) In terms of novelty, while speculative planning may not be universally applicable, its potential to accelerate high-latency planning tasks is valuable for the AI community, especially for applications requiring real-time or near-real-time responses.", "weaknesses": "1) One downside, not fully addressed or discussed in the paper, is the increased cost. The paper largely supports its claims of time efficiency gains, presenting results indicating speculative planning can save time, especially in complex planning settings. However, cost savings are not fully supported, as all speculative settings incur higher costs. While this increase is expected, as A and T operate concurrently, the paper only highlights positives and does not discuss costs. To balance the discussion, the authors must discuss both sides: pros and cons in Sections 4.1 and 4.2. While time savings are the focus, I assume real-world deployments must balance cost and efficiency, particularly if A has very low accuracy and frequently diverges from the steps produced by T, which increases wasted resources. Therefore, an open discussion about this limitation must be expressed in the same units as efficiency is justified (%) and possibly what strategies may allow users to reduce the cost.\n\n2) Although the title suggests a \"co-design\" with user interface considerations, the paper provides limited insights into UI and user interactions. I find this aspect genuinely troublesome. The paper is technical. Even the UI elements, such as producing the steps in the correct order etc., are technical contributions. This is not co-design from an HCI perspective. I also have a few more questions on this aspect, which are provided in the Questions section later.\n\n3) The framework relies on hyperparameter k. In the experiments, the authors used k=4 -- why? The appendix does provide some insight into the sensitivity of this parameter. Still, since k is central to the scheme, providing some guidance on selecting k would be beneficial. For example, could we employ dynamic tuning of k, etc?\n\n\nMinor issues:\n- 048: and The sequential\n- In Figure 1, please briefly state the reason for using Venmo as an example.\n- Line 100: Statements like \"This strategy [[potentially]] reduces the time a target agent\" suggests either that this gain is not universal or that the authors have doubts about their results. If there are caveats regarding when we expect reduced time, then that needs to be made explicit.\n- I did not find the Venmo case study or the diagrams helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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:

Decision: Accept (Poster)