acceptodds
Under review as a conference paper at ICLR 2027

Don't Miss a Deadline: Online Temporal Planning for Multi-Goal LLM Agents under Partial Observability

Abstract

Many real-world applications require Large Language Model (LLM) agents to complete multiple tasks subject to strict temporal constraints. Existing methods often assume a static environment where all task specifications are known a priori. However, in many practical robotic domains, agents only have partial observability due to limited sensory capabilities, and critical task information must be actively gathered through exploration or exploratory actions. To address these challenges, we propose a novel online temporal multi-goal planning framework for LLM agents under partial observability. Specifically, we first construct a partial Simple Temporal Network (STN) derived from the agent's current knowledge base. Then, this partial STN serves as a guide for the LLM to balance the exploration-exploitation trade-off while strictly adhering to temporal constraints during action selection. Additionally, we leverage the STN to monitor action validity; when a constraint violation is detected, semantic feedback is integrated into the prompt to trigger iterative action refinement. To empirically evaluate our approach, we construct a new benchmark, DeadlineBench, which requires LLM agents to execute multi-goal tasks under both temporal constraints and partial observability. Experimental results show that our approach consistently outperforms the state-of-the-art methods in terms of success rate across all benchmarks.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
LLM agents, temporal reasoning, Simple Temporal Networks, partially observable planning, long-horizon multi-goal tasks

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_cq34OpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies multi-goal planning for LLM agents under partial observability, where information gathering consumes time and concurrent processes must satisfy hard temporal windows. It introduces DeadlineBench, comprising 38 household and 33 laboratory tasks, with feasibility verified by a full-information oracle. The proposed Online-STN framework compiles public observations into a partial Simple Temporal Network, whose temporal summaries guide deterministic goal ranking, candidate pruning, LLM action selection, and limited guard-based repair. An optional experience module reuses observed locations, temporal bounds, and textual advice across repeated attempts at the same task. Experiments report higher success rates than the evaluated baselines, alongside network-maintenance and memory ablations. These results provide encouraging evidence for the effectiveness of the integrated framework.

Critical strengths
  1. The benchmark couples costly information acquisition, concurrent processes, and hard temporal windows, creating a useful diagnostic setting where locally valid actions can still undermine completion of other required goals.
  2. The proposed Online-STN framework achieves higher first-trial success than all evaluated baselines in both domains, while repeated trials further improve completion, providing encouraging evidence that the integrated system benefits deadline-sensitive task execution.
Critical weaknesses
  1. Appendix C states that two five-task additions were accepted based on baseline failure or improvement with experience, and all remain in the reported sets. This method-dependent selection weakens evaluation independence; aggregate gains therefore do not establish comparable advantages on tasks selected without such criteria.
  2. The paper emphasizes discovering temporal requirements, but Tables 1 and 4 mainly provide domain-level aggregates. They offer limited analysis of performance across hidden-bound and information-source settings, or of decisions following revealed outcomes, making it difficult to assess the method’s benefits on these distinctive challenges.
Questions for authors
  1. Could you separate all main results into the original task families and the two five-task additions, and report whether the method ranking and experience gains persist? Please clarify the generation and rejection criteria used before freezing each subset, including any dependence on observed agent performance.
  2. Could you provide within-domain results stratified by hidden temporal bounds and mandatory versus optional information sources, where task counts permit? For outcome-dependent responses, could you analyze representative successes and failures to clarify how newly revealed requirements affect decisions?
  3. Could you provide a representative case explaining the large laboratory gap between Rolling-STN and Online-STN? Ideally, compare their temporal states under the same public history, identify the first differing event or constraint, and show how this difference changes the selected action and eventual outcome.
3 comments

Thank you for your review and suggestions. Below, we separate the core and diagnostic sets and report results stratified by hidden constraints to clarify which mechanisms correspond to the advantage of our method. We also provide a concrete trajectory example to explain the source of the difference between Rolling-STN and Online-STN.

W1 / Q1 | Task-Set Separation and Independence

Appendix C explicitly states that the two five-task additions were constructed according to specific behavioral criteria after analyzing the earlier task families. We deliberately designed these additional tasks to increase the challenge posed by key scheduling difficulties. Beyond testing whether a workflow can be completed, we seek to examine whether a method can adapt in time when a fixed execution order no longer works or initial exploration consumes a critical part of the time budget. The household additions target the former challenge, and the laboratory additions target the latter. Both situations are common in practice and have diagnostic value.

For example, in a household task with a relatively generous budget, both “clean first, then start the appliance” and the reverse order may meet the deadline. If the appliance must be started within an early window, the same household workflow requires starting it first and cleaning while it runs in the background. In the laboratory, initial searches for samples and reagents may consume a local time window, causing failure even when the procedural steps are known. On a subsequent trial, reusing previously discovered public locations and temporal bounds to reduce repeated exploration may be necessary to finish in time. The original tasks already include search, concurrent processes, and hidden temporal requirements; the additions deliberately intensify the conflicts among these factors to test whether our method can address more complex real-world problems.

Whether the advantage of the core method depends on these tasks can be tested directly by excluding them entirely. Table A1 therefore reports the 33 household and 28 laboratory core tasks, while Table A2 separately reports the two five-task additions. The core and diagnostic sets serve distinct evidential purposes.

Table A1. Results on the original core tasks (successes/total, success rate, %)

MethodtrialHousehold core 33Laboratory core 28
ReAct1st38/99 (38.4)43/84 (51.2)
Reflexion1st31/99 (31.3)43/84 (51.2)
Reflexion3rd40/99 (40.4)42/84 (50.0)
PLANTOR1st60/99 (60.6)27/84 (32.1)
Agent-C1st21/99 (21.2)30/84 (35.7)
Online-STN + Experience1st62/99 (62.6)72/84 (85.7)
Online-STN + Experience3rd75/99 (75.8)72/84 (85.7)

Table A2. Results on the diagnostic additions (successes/total, success rate, %)

MethodtrialHousehold additions 5Laboratory additions 5
ReAct1st4/15 (26.7)0/15 (0.0)
Reflexion1st1/15 (6.7)0/15 (0.0)
Reflexion3rd15/15 (100.0)3/15 (20.0)
PLANTOR1st0/15 (0.0)0/15 (0.0)
Agent-C1st1/15 (6.7)2/15 (13.3)
Online-STN + Experience1st15/15 (100.0)0/15 (0.0)
Online-STN + Experience3rd15/15 (100.0)15/15 (100.0)

After separating the sets, our method still ranks first on the first trial in both domains. Household core-set success is 62.6%, compared with 60.6% for the strongest baseline, PLANTOR. Laboratory core-set success is 85.7%, compared with 51.2% for the strongest baseline, ReAct. This shows that the cold-start advantage of the core method remains even when both five-task additions are excluded entirely, with a laboratory gap of 34.5 percentage points.

W2 / Q2 | Stratified Results and Outcome-Dependent Responses

Appendix C designs and reports the two domains separately because household tasks primarily test competition for time between search and concurrent household activities, while laboratory tasks additionally test local time limits and outcome-dependent responses. To further examine whether the advantage is concentrated in these mechanisms, Table E stratifies the core-set results by the presence of hidden latest-start bounds. We analyze these results together with successful and failed trajectories on the same laboratory task below.

Table E. Stratified results across methods

Method (trial)Household: without hidden bounds (25)Household: with hidden bounds (8)Laboratory: with hidden bounds (22)Laboratory: without hidden bounds (6)
Online-STN + Experience (1st)62/75 (82.7)0/24 (0.0)54/66 (81.8)18/18 (100.0)
Online-STN + Experience (3rd)69/75 (92.0)6/24 (25.0)54/66 (81.8)18/18 (100.0)
Reflexion (1st)30/75 (40.0)1/24 (4.2)25/66 (37.9)18/18 (100.0)
Reflexion (3rd)37/75 (49.3)3/24 (12.5)25/66 (37.9)17/18 (94.4)
ReAct (1st)35/75 (46.7)3/24 (12.5)26/66 (39.4)17/18 (94.4)
PLANTOR (1st)60/75 (80.0)0/24 (0.0)12/66 (18.2)15/18 (83.3)
Agent-C (1st)20/75 (26.7)1/24 (4.2)14/66 (21.2)16/18 (88.9)

The four groups further identify the conditions under which the method is effective:

  1. Laboratory, with hidden bounds (22 tasks): Our method achieves 81.8% success, compared with 39.4% for the strongest baseline, ReAct, and 18.2–37.9% for the other baselines. Our method does not improve on the third trial, indicating that this advantage is already present without cross-trial experience, consistent with the intended role of online temporal control.
  2. Household, without hidden bounds (25 tasks): Our method achieves 82.7% success, compared with 80.0% for the strongest baseline, PLANTOR. Our method reaches 92.0% on the third trial.
  3. Household, with hidden bounds (8 tasks): Our method succeeds in 0 of 24 cold-start episodes, and ReAct is the strongest first-trial baseline. Our method reaches 25.0% on the third trial, exceeding all baselines.
  4. Laboratory, without hidden bounds (6 tasks): All methods achieve success rates between 83.3% and 100%, close to the ceiling, so these tasks have limited ability to distinguish methods.

For a representative outcome-dependent response, we use the laboratory example in Q3 to analyze one success and one failure. Inspecting the experimental instructions reveals the reagents required for positive and negative results and the time limit for adding a reagent after reading the result. In the successful trajectory, the agent prepares both reagents before reading the result and adds the appropriate one within the required window once the outcome is known. In a failed baseline trajectory, the agent may miss the response window or choose the wrong branch. In our method, newly revealed requirements enter the STN and can therefore affect the agent’s decisions.

Q3 | A Representative Divergence Between Rolling-STN and Online-STN

Both Rolling-STN and Online-STN have access to the public interaction history. They differ in the types of information incorporated into the network: Rolling-STN reconstructs the temporal network from events such as appliance starts and completion notifications, but does not translate temporal rules in textual instructions into STN constraints. Online-STN additionally incorporates and persistently retains these interaction-revealed rules in the network, allowing them to inform the temporal summary and candidate ranking.

For example, a notification that an appliance has finished is event information that both methods can handle. By contrast, a note stating that “a specified follow-up action is required before a particular appliance runs or after it finishes” is an interaction-revealed temporal rule. The Rolling-STN selector can see the latter requirement in the public history, but it does not enter STN construction and scheduling as an explicit constraint. Online-STN translates it into a network constraint, so subsequent scheduling can directly account for the response window.

Appendix G emphasizes that we do not claim that persistence provides greater STN representational power. Access to public history and the actual incorporation of its constraints into the network for summarization and candidate ranking are distinct issues. The example and trajectory comparison below illustrate how Rolling-STN and Online-STN differ in STN construction and scheduling when using temporal constraints discovered through environment interaction.

Consider a representative laboratory task. The agent starts at the entrance, and the environment contains three rooms: the entrance, a cold-storage room, and a laboratory-bench room. The task requires completing three workflows:

  1. Sample preparation (8 ticks): Retrieve the sample from cold storage and bring it to the laboratory bench.
  2. Incubation and testing (12 ticks): Incubate the sample on the assay plate. After incubation, read the result, select and add the appropriate reagent, and deliver the treated product.
  3. Medium sterilization (8 ticks): Sterilize the medium.

The task must be completed within 78 ticks. The agent needs to retrieve samples and reagents from containers. A hidden requirement specifies that stop solution must be used for a positive result and recovery buffer for a negative result; in either case, the reagent must be added within 5 ticks of reading the result. The agent learns this requirement by executing inspect on the experimental instructions at the laboratory bench.

In this replay, the Rolling-STN public history includes the instructions, but the corresponding response window does not enter the temporal state used for decision-making. Online-STN identifies the 5-tick window between reading the result and adding the reagent, so the agent prepares both reagents before reading the result. With Rolling-STN, the agent searches for the required reagent only after reading the result and ultimately fails to complete the task.

Table D. Replay under a shared prefix

ItemRolling-STNOnline-STN
Shared prefix0–2 min 15 s: Go to cold storage, retrieve the sample, bring it to the laboratory bench, and inspect the instructionsSame as Rolling-STN
First differing constraintAt 2 min 15 s, learn the outcome-dependent branch from the instructions, but fail to extract their temporal constraintAt 2 min 15 s, learn the outcome-dependent branch and extract the temporal constraint from the instructions
Corresponding temporal summaryIncubate the sample first and search for reagents only after the result becomes availablePrioritize searching for reagents and incubate the sample only after confirming reagent locations
First differing action2 min 30 s: Take the assay plate2 min 30 s: Inspect the reagent cabinet
Subsequent trajectoryStart incubation/testing at 3 min; read the result at 6 min and then search for the reagent. Fail to add the appropriate reagent in time; delivery is rejected and the task fails.Start incubation at 3 min 30 s; read the result at 6 min 30 s and then add stop solution; finish sterilization at 9 min and succeed.
Reviewer_NPKnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies online multi-goal planning for LLM agents when information gathering and task execution share a clock and important temporal requirements are initially hidden. The proposed Online-STN framework incrementally compiles public observations into a partial Simple Temporal Network, uses temporal summaries and heuristic margins to construct candidate actions, and combines LLM selection with a limited guard, repair, and fallback mechanism. An optional experience module reuses publicly observed facts and bounds across attempts at the same task. Validation uses DeadlineBench, comprising 38 household and 33 laboratory tasks, with baseline comparisons, network and memory ablations, and failure analyses. Cold-start success reaches 67.5% and 72.7% in the two domains.

Critical strengths
  1. The problem formulation captures a consequential interaction between exploration and scheduling. Acquiring information can itself consume the opportunity to satisfy a deadline, making the setting more informative than planning under an action-count limit alone. This gives the work a useful motivation for interactive agents and online scheduling.

  2. The system carefully separates observed facts and temporal constraints from model-generated advice, and the main table separates cold-start results from later attempts. The substantial cold-start improvements in both domains provide meaningful evidence for the complete system beyond benefits from repeated exposure to the same task.

Critical weaknesses
  1. Part of the evaluation is selected according to the outcomes it is intended to demonstrate. Appendix C, pages 14–15, describes two five-task additions accepted under conditions involving baseline failure and proposed-method success, or cold-start failure and experienced success. These are legitimate diagnostic cases, but pooling them into the headline results limits the independence of the comparison. Without separating these additions from the original tasks, I cannot determine how much of the reported advantage persists outside this outcome-dependent selection.

  2. The network ablation does not establish the proposed mechanism. Table 2 reports laboratory success of 30.3% for Rolling-STN and 72.7% for Online-STN, although Rolling-STN receives the public history. Appendix G correctly acknowledges that equivalent constraint graphs have identical closure. The manuscript does not identify the actual constraint or state differences responsible for this gap. Together with substantial deterministic candidate construction, this leaves the gains attributable to the complete controller rather than clearly to persistent STN maintenance or LLM decision-making.

Questions for authors
  1. Clarification of the existing evaluation. Can you provide separate cold-start and experience results for the original task families and the two five-task additions, including per-task outcomes? This would materially affect my assessment of the comparative evidence.

  2. Clarification of the implementation and ablation. Given the same public history, which events, constraints, or temporal summaries first differ between Rolling-STN and Online-STN? Please provide a representative divergence and its effect on action selection. Also clarify how frequently the candidate set is a singleton or fallback is used, since these frequencies determine how much decision-making remains with the LLM.

6 comments

Thank you for your careful review. Your questions concern the evaluative role of the diagnostic tasks and how public history is converted into the temporal state actually used for decision-making. Below, we provide core-set results, per-task outcomes, and trajectory comparisons under a shared prefix to examine these two issues directly.

W1 / Q1 | Task Families and Per-Task Outcomes

Appendix C explicitly states that the two five-task additions were constructed according to specific behavioral criteria after analyzing the earlier task families. We deliberately designed these additional tasks to increase the challenge posed by key scheduling difficulties. Beyond testing whether a workflow can be completed, we seek to examine whether a method can adapt in time when a fixed execution order no longer works or initial exploration consumes a critical part of the time budget. The household additions target the former challenge, and the laboratory additions target the latter. Both situations are common in practice and have diagnostic value.

For example, in a household task with a relatively generous budget, both “clean first, then start the appliance” and the reverse order may meet the deadline. If the appliance must be started within an early window, the same household workflow requires starting it first and cleaning while it runs in the background. In the laboratory, initial searches for samples and reagents may consume a local time window, causing failure even when the procedural steps are known. On a subsequent trial, reusing previously discovered public locations and temporal bounds to reduce repeated exploration may be necessary to finish in time. The original tasks already include search, concurrent processes, and hidden temporal requirements; the additions deliberately intensify the conflicts among these factors to test whether our method can address more complex real-world problems.

Whether the advantage of the core method depends on these tasks can be tested directly by excluding them entirely. Table A1 shows that, on the remaining 61 tasks, our method achieves the highest first-trial success rate in both domains. Tables S1 and S2 give per-task outcomes for the original tasks and additions, respectively, making the sources of the overall advantage and experience gains more transparent.

Table A1. Results on the original core tasks (successes/total, success rate, %)

MethodtrialHousehold core 33Laboratory core 28
ReAct1st38/99 (38.4)43/84 (51.2)
Reflexion1st31/99 (31.3)43/84 (51.2)
Reflexion3rd40/99 (40.4)42/84 (50.0)
PLANTOR1st60/99 (60.6)27/84 (32.1)
Agent-C1st21/99 (21.2)30/84 (35.7)
Online-STN + Experience1st62/99 (62.6)72/84 (85.7)
Online-STN + Experience3rd75/99 (75.8)72/84 (85.7)

Table A2. Results on the diagnostic additions (successes/total, success rate, %)

MethodtrialHousehold additions 5Laboratory additions 5
ReAct1st4/15 (26.7)0/15 (0.0)
Reflexion1st1/15 (6.7)0/15 (0.0)
Reflexion3rd15/15 (100.0)3/15 (20.0)
PLANTOR1st0/15 (0.0)0/15 (0.0)
Agent-C1st1/15 (6.7)2/15 (13.3)
Online-STN + Experience1st15/15 (100.0)0/15 (0.0)
Online-STN + Experience3rd15/15 (100.0)15/15 (100.0)

The advantage of the core method remains after excluding both five-task additions. In Table A1, first-trial success on the household core set is 62.6%, numerically higher than the strongest baseline, PLANTOR, at 60.6%. On the laboratory core set, it is 85.7%, exceeding the strongest baseline, ReAct, at 51.2% by 34.5 percentage points. Thus, the advantage does not arise solely from additions constructed according to behavioral criteria. Experience gains can also be observed independently on the core sets: household success increases from 62.6% to 75.8%, compared with 40.4% for Reflexion on the same third trial. Laboratory core-set success remains 85.7% on both trials, while success on the diagnostic additions increases from 0/15 to 15/15.

Table S1. Per-task outcomes on the original household tasks (each cell gives the number of successes across three independent rounds)

TaskOurs trial 1Ours trial 3Reflexion trial 1Reflexion trial 3ReActPLANTORAgent-C
household_task13/33/31/31/33/33/31/3
household_task23/33/33/33/33/33/33/3
household_task30/33/31/32/31/33/31/3
household_task43/33/30/30/30/33/30/3
household_task53/30/30/30/30/33/30/3
household_task63/33/30/32/30/33/30/3
household_task73/33/31/31/31/33/31/3
household_task83/33/33/33/33/30/31/3
household_task93/33/30/31/30/33/30/3
household_task103/33/33/33/33/33/33/3
household_task113/33/30/32/30/33/31/3
household_task123/33/33/33/33/33/32/3
household_task133/33/33/33/33/33/30/3
household_task143/33/33/33/33/33/30/3
household_task152/33/30/30/30/33/31/3
household_task160/30/30/31/30/33/32/3
household_task170/33/30/30/31/33/30/3
household_task183/33/31/30/30/33/30/3
household_task193/33/31/30/30/33/32/3
household_task203/33/30/31/31/33/30/3
household_task213/33/33/32/33/30/30/3
household_task223/33/32/32/31/30/30/3
household_task233/33/30/32/33/30/31/3
household_task240/33/32/31/33/30/30/3
household_task253/33/30/31/30/33/31/3
household_task260/30/30/31/30/30/30/3
household_task270/30/31/31/33/30/30/3
household_task280/30/30/31/30/30/31/3
household_task290/30/30/30/30/30/30/3
household_task300/33/30/30/30/30/30/3
household_task310/30/30/30/30/30/30/3
household_task320/33/30/30/30/30/30/3
household_task330/30/30/30/30/30/30/3

Table S1. Per-task outcomes on the original laboratory tasks (each cell gives the number of successes across three independent rounds)

TaskOurs trial 1Ours trial 3Reflexion trial 1Reflexion trial 3ReActPLANTORAgent-C
laboratory_task13/33/30/32/31/30/30/3
laboratory_task23/33/33/33/33/30/33/3
laboratory_task33/33/32/33/30/30/30/3
laboratory_task43/33/33/33/33/30/33/3
laboratory_task53/33/30/32/31/30/30/3
laboratory_task63/33/33/32/33/30/33/3
laboratory_task73/33/30/30/31/30/30/3
laboratory_task83/33/31/30/33/30/33/3
laboratory_task93/33/30/31/30/33/30/3
laboratory_task103/33/32/31/32/30/32/3
laboratory_task113/33/30/30/30/33/30/3
laboratory_task123/33/33/30/33/30/30/3
laboratory_task133/33/30/30/30/33/30/3
laboratory_task143/33/33/33/33/33/33/3
laboratory_task153/33/33/33/33/30/33/3
laboratory_task163/33/30/30/30/33/30/3
laboratory_task170/30/32/33/32/30/30/3
laboratory_task180/30/33/32/31/30/30/3
laboratory_task190/30/31/32/31/30/30/3
laboratory_task200/30/32/31/32/30/30/3
laboratory_task213/33/30/30/30/30/30/3
laboratory_task223/33/30/30/30/30/30/3
laboratory_task233/33/30/30/30/30/30/3
laboratory_task243/33/30/30/30/30/30/3
laboratory_task253/33/33/33/33/33/32/3
laboratory_task263/33/33/33/33/33/33/3
laboratory_task273/33/33/32/32/33/32/3
laboratory_task283/33/33/33/33/33/33/3
Reviewer_SuMNOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper raises an interesting practical question for LLM agents: whether LLM agents can reliably complete multiple tasks under strict temporal constraints and partial observability. To address this problem, the paper proposes a novel online temporal multi-goal planning framework for LLM agents under partial observability. It first constructs a partial Simple Temporal Network (STN) based on the agent’s current knowledge base. The STN then helps the LLM balance the exploration–exploitation trade-off during action selection while strictly adhering to temporal constraints. In addition, the STN is used to monitor action validity. To evaluate this method, the authors construct a new benchmark, DeadlineBench. The experiments report that the proposed method consistently outperforms the state-of-the-art methods in terms of success rate across all benchmarks.

Critical strengths

The paper considers a novel setting that combines multiple goals, hard temporal windows, and costly information acquisition, while most existing methods have not focused on this combination of challenges or are unable to solve this setting.

The paper constructs a new benchmark called DeadlineBench, containing 38 household tasks and 33 laboratory tasks, all of which are verified to be feasible through the public action interface. Although this is not the first work to combine LLMs with temporal planning, the paper still makes some positive methodological explorations.

Critical weaknesses
  1. Part of the benchmark construction involves method-aware selection, which weakens the credibility of the strongest empirical conclusions. For example, in Appendix C, the authors explicitly state that the five additional household tasks were selected such that the fixed-order baseline fails while the proposed method starts the bounded process within its window. The laboratory tasks were selected based on the criterion that “cold start fails while the experienced one succeeds,” but both sets are included in the final reported results.

  2. The comparison in the main results is not fully fair because different methods have different trial / memory budgets. For example, Section 5.1 explicitly states that PLANTOR and Agent-C are run for only 1 trial, whereas Online-STN+Experience is run for 3 trials and can use information obtained from previous trials. The authors should preferably use a matched-budget comparison as the main result.

Questions for authors
  1. The authors should first exclude the two sets of five tasks described in Appendix C and then report all main results. In particular, what are the cold-start success rate and the experienced-agent success rate in the laboratory domain after excluding the five laboratory additions?

  2. If the same STN, temporal summary, candidate construction, guard, and deterministic fallback are retained, but the LLM selector is replaced with a deterministic action-selection rule, what is the resulting performance? This experiment would help determine whether the performance improvement mainly comes from the symbolic temporal control mechanism or from the action-selection capability of the LLM.

  3. Do the authors have a test set that was generated and frozen only after the complete method was finalized? If so, please report the results on this test set. If not, can the authors provide an evaluation on newly generated tasks that were not selected based on the behavior of Online-STN?

  4. All experiments use only a single LLM, namely deepseek-v4-flash. Can the authors reproduce the results with at least one additional LLM? Since both the proposed method and the baselines currently use the same frozen external model, it is still unclear whether the advantage of Online-STN generalizes to other models.

  5. The estimated margin in the method uses hand-set fixed allowances. What are the exact values of these parameters, and how sensitive are the results to them?

  6. Can the authors report uncertainties or statistical significance regarding the main results and ablation experiment results? Confidence intervals or other statistical data would help determine which of the reported differences are reliable.

3 comments

Thank you for your careful reading and specific suggestions. We address three key issues: whether the core task sets independently support the advantage of our method, whether the cold-start comparison uses a matched budget, and the respective roles of the symbolic temporal layer and the LLM selector. Below, we report the 33 household and 28 laboratory tasks separately from the two diagnostic five-task additions, comparing methods with the same number of trials. Additional experiments with a deterministic selector, a second LLM, margin sensitivity analysis, and paired confidence intervals further examine these conclusions.

W1 / Q1 | Task Selection and Main Results

Appendix C explicitly states that the two five-task additions were constructed according to specific behavioral criteria after analyzing the earlier task families. We deliberately designed these additional tasks to increase the challenge posed by key scheduling difficulties. Beyond testing whether a workflow can be completed, we seek to examine whether a method can adapt in time when a fixed execution order no longer works or initial exploration consumes a critical part of the time budget. The household additions target the former challenge, and the laboratory additions target the latter. Both situations are common in practice and have diagnostic value.

For example, in a household task with a relatively generous budget, both “clean first, then start the appliance” and the reverse order may meet the deadline. If the appliance must be started within an early window, the same household workflow requires starting it first and cleaning while it runs in the background. In the laboratory, initial searches for samples and reagents may consume a local time window, causing failure even when the procedural steps are known. On a subsequent trial, reusing previously discovered public locations and temporal bounds to reduce repeated exploration may be necessary to finish in time. The original tasks already include search, concurrent processes, and hidden temporal requirements; the additions deliberately intensify the conflicts among these factors to test whether our method can address more complex real-world problems.

Whether the advantage of the core method depends on these tasks can be tested directly by excluding them entirely. Table A1 therefore reports the 33 household and 28 laboratory core tasks, while Table A2 separately reports the two five-task additions. The core and diagnostic sets serve distinct evidential purposes.

Table A1. Results on the original core tasks (successes/total, success rate, %)

MethodtrialHousehold core 33Laboratory core 28
ReAct1st38/99 (38.4)43/84 (51.2)
Reflexion1st31/99 (31.3)43/84 (51.2)
Reflexion3rd40/99 (40.4)42/84 (50.0)
PLANTOR1st60/99 (60.6)27/84 (32.1)
Agent-C1st21/99 (21.2)30/84 (35.7)
Online-STN + Experience1st62/99 (62.6)72/84 (85.7)
Online-STN + Experience3rd75/99 (75.8)72/84 (85.7)

Table A2. Results on the diagnostic additions (successes/total, success rate, %)

MethodtrialHousehold additions 5Laboratory additions 5
ReAct1st4/15 (26.7)0/15 (0.0)
Reflexion1st1/15 (6.7)0/15 (0.0)
Reflexion3rd15/15 (100.0)3/15 (20.0)
PLANTOR1st0/15 (0.0)0/15 (0.0)
Agent-C1st1/15 (6.7)2/15 (13.3)
Online-STN + Experience1st15/15 (100.0)0/15 (0.0)
Online-STN + Experience3rd15/15 (100.0)15/15 (100.0)

The results show that the advantage of the core method does not depend on the additions. On the laboratory core set, first-trial success is 72/84 (85.7%), exceeding the strongest baseline by 34.5 percentage points. On the household core set, it is 62/99 (62.6%), numerically higher than the strongest baseline at 60.6%. Household success further reaches 75.8% on the third trial.

W2 | Matched Budgets for Cold-Start and Experienced-Agent Evaluation

Section 5.1 and Table 1 already report the first and third trials separately and specify that memory is empty on the first trial. These are two intentional evaluation conditions: the first trial measures cold-start execution, while later trials measure the use of experience on the same task. Table 1 therefore already includes a direct comparison in which every method has one attempt and empty memory; the cold-start advantage of our method does not come from additional trials.

On the core sets, this matched-budget comparison yields 62.6% for household tasks and 85.7% for laboratory tasks. In the experienced-agent setting, we compare our method with Reflexion, which also has three trials: third-trial success is 75.8% versus 40.4% and 85.7% versus 50.0%, respectively. In the revision, we will make the column headings 1st trial (one attempt, empty memory) and 3rd trial (same-task experience) more prominent and present the K = 1 comparison separately to clarify the two evaluation objectives.

Q2 | Deterministic Action Selection

Following your suggestion, we added a controlled experiment replacing the LLM selector with a deterministic action-selection rule to assess the role of the LLM in action selection. The results are shown below.

Action-selection comparison (success rate, %)

SelectorHousehold 33Laboratory 28
LLM (1st)62.685.7
LLM (3rd)75.885.7
Deterministic rule18.271.4

Keeping the entire controller and replacing only the selector, we compare the first-trial LLM selector with empty memory against the deterministic rule. Success drops from 62.6% to 18.2% on household tasks and from 85.7% to 71.4% on laboratory tasks, differences of 44.4 and 14.3 percentage points, respectively. This comparison shows that LLM choices still affect final task completion even when the candidate set is heavily constrained. The difference between domains is also consistent with the division of roles in the framework: household exploration relies more on flexible selection, whereas laboratory workflows benefit more from explicit temporal control.

Q3 | New Tasks Generated After the Method Was Finalized

Both five-task additions described in Appendix C were generated and frozen only after the complete method was finalized. The 33 household and 28 laboratory tasks used in the main experiments were not selected based on the behavior of Online-STN. Tables A1 and A2 in Q1 report the original core tasks and diagnostic additions separately. In future work, we will further evaluate generalization on third-party task sets.

Q4 | A Second LLM

We reproduced the full main comparison on all 61 tasks using qwen3.8-flash-next.

Success rates across models and domains (%, 1st / 3rd trial)

MethodQwen household (1st / 3rd)Qwen laboratory (1st / 3rd)DeepSeek household (1st / 3rd)DeepSeek laboratory (1st / 3rd)
Ours61.6 / 77.885.7 / 85.762.6 / 75.885.7 / 85.7
PLANTOR60.6 / —32.1 / —60.6 / —32.1 / —
ReAct32.3 / —22.6 / —38.4 / —51.2 / —
Reflexion34.3 / 40.421.4 / 34.531.3 / 40.451.2 / 50.0
Agent-C11.1 / —17.9 / —21.2 / —35.7 / —

Our method ranks first on both the first and third trials across both models and both domains. These results show that our method remains robust when switching to qwen3.8-flash-next.

Q5 | Estimated-Margin Parameters

Section 4.3 deliberately uses a lightweight, auditable heuristic to rank actions, rather than assuming that the agent knows the complete constraints or has obtained an optimal schedule. The estimated margin has three components: published process and appliance durations, observed latest-start bounds (used as upper bounds), and small fixed allowances for remaining delivery or confirmation actions. The first two come from the task and observations; only the third is manually set. Table C-1 lists the exact values.

Table C-1. Fixed allowances in the estimated margin

Goal / workflow typeEstimated remaining costFixed allowance (ticks)
Household: pizza (oven)Oven duration + 22
Household: laundry (washer)Washer duration + 11
Household: tea (kettle)Kettle duration + 33
Laboratory: conditional workflow (result not yet available)Process duration + 55
Laboratory: non-conditional and delivery workflowsProcess duration + 1 (another +1 for delivery goals)1 (+1)

We scaled the fixed allowances in Table C-1 by 0, 1, and 2 and conducted three independent rounds of first-trial experiments on both core task sets. Table C-2 reports the results.

Table C-2. Success rates under allowance scaling (1st trial, pooled over three rounds)

Allowance scalingHousehold 33Laboratory 28
0×62.685.7
1× (default)62.685.7
2×62.685.7

All three settings yield identical overall success rates, and the outcome of every task is also identical within each round: none of the 61 tasks changes outcome when the allowances are varied. Thus, within the tested 0–2× range and on the core task sets, the results do not depend on the exact values of these fixed allowances.

Q6 | Statistical Uncertainty

We use a paired bootstrap with tasks as the clustering unit and 10,000 resamples. Observations for the same task remain paired by round and trial index. Table B reports intervals and paired differences for the main comparisons and network ablations. These intervals use task-level resampling and do not account for between-round variability.

Table B. Main comparisons (percentage points; brackets indicate 95% paired intervals)

ComparisonDomain / task settrialMethod AMethod BA−B
Ours vs PLANTORHousehold 331st62.6 [45.5, 78.8]60.6 [42.4, 75.8]+2.0 [−13.1, +18.2]
Ours vs ReflexionHousehold 333rd75.8 [60.6, 87.9]40.4 [28.3, 53.5]+35.4 [+20.2, +50.5]
Ours vs ReActLaboratory 281st85.7 [71.4, 96.4]51.2 [35.7, 66.7]+34.5 [+14.3, +54.8]
Ours vs ReflexionLaboratory 283rd85.7 [71.4, 96.4]50.0 [34.5, 65.5]+35.7 [+13.1, +57.1]
Online vs RollingHousehold 331st69.7 [54.5, 84.8]66.7 [48.5, 81.8]+3.0 [0.0, +9.1]
Online vs RollingLaboratory 281st85.7 [71.4, 96.4]35.7 [17.9, 53.6]+50.0 [+32.1, +67.9]

On the core task sets, our method exceeds PLANTOR by 2.0 percentage points on first-trial household tasks (95% paired bootstrap interval: −13.1 to +18.2) and ReAct by 34.5 percentage points on first-trial laboratory tasks (+14.3 to +54.8). On the third trial, it exceeds Reflexion by 35.4 percentage points on household tasks (+20.2 to +50.5) and 35.7 percentage points on laboratory tasks (+13.1 to +57.1). In the network ablation, Online-STN exceeds Rolling-STN by 3.0 percentage points on household tasks (0.0 to +9.1) and 50.0 percentage points on laboratory tasks (+32.1 to +67.9).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.