- 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
- 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.
- 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
- 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.
- 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
- 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.
- 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?
- 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
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:
- 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.
- 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.
- 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.
- 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:
- Sample preparation (8 ticks): Retrieve the sample from cold storage and bring it to the laboratory bench.
- 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.
- 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
| Item | Rolling-STN | Online-STN |
|---|---|---|
| Shared prefix | 0–2 min 15 s: Go to cold storage, retrieve the sample, bring it to the laboratory bench, and inspect the instructions | Same as Rolling-STN |
| First differing constraint | At 2 min 15 s, learn the outcome-dependent branch from the instructions, but fail to extract their temporal constraint | At 2 min 15 s, learn the outcome-dependent branch and extract the temporal constraint from the instructions |
| Corresponding temporal summary | Incubate the sample first and search for reagents only after the result becomes available | Prioritize searching for reagents and incubate the sample only after confirming reagent locations |
| First differing action | 2 min 30 s: Take the assay plate | 2 min 30 s: Inspect the reagent cabinet |
| Subsequent trajectory | Start 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. |
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, %)
Table A2. Results on the diagnostic additions (successes/total, success rate, %)
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.