acceptodds
Under review as a conference paper at ICLR 2027

Schedule-Overcooked: Multi-Task Allocation for LLM Agents under Multiple Constraints

Abstract

Large language model (LLM) based multi-agent systems increasingly execute concurrent tasks over a shared pool of agents and tools, making the allocation of dependent subtasks a central determinant of system efficiency. Yet allocation is evaluated only through end-to-end task success, where it is confounded with low-level execution and simplified constraints. We introduce Schedule-Overcooked, a benchmark that fixes task decomposition and execution to isolate subtask ownership and dispatch timing. It pairs a four-level task-complexity suite with a five-level suite of composable agent, task, and resource constraints, and exposes the same allocation interface in TaskBench, Minecraft, and Factorio. Evaluating rule-based, LLM, and GNN-PPO allocators, we find that (i) the evaluated allocators vary substantially across settings, and near-full agent utilization often coexists with unfinished workflows; (ii) under compound temporal constraints, a GNN-PPO allocator attains low success already on its training configurations, and revealing capability information at evaluation time gives little benefit to the trained policy; and (iii) frozen policies transfer well between workload levels that share workflow structure but asymmetrically across constraint scenarios, and an Overcooked-trained policy remains operational on TaskBench, Minecraft, and Factorio, where limited adaptation further improves TaskBench success. Schedule-Overcooked provides a controlled testbed for developing allocators that coordinate time, resources, and uncertainty across concurrent tasks.

Primary area:
datasets and benchmarks
Keywords:
LLM-based multi-agent systems, multi-task allocation, constrained scheduling, multi-agent benchmarks

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_kTEXOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces Schedule-Overcooked, a benchmark that evaluates how agents are assigned to subtasks and when those subtasks are dispatched. It pairs a four-level task-complexity suite with a five-level suite of agent, task, and resource constraints. The paper evaluates rule-based, LLM, and GNN-PPO allocators and examines transfer across workload levels, constraint scenarios, and domains, including TaskBench, Minecraft, and Factorio.

Critical strengths
  1. The benchmark offers a novel combination of cross-task agent allocation, capability uncertainty, and shared-resource contention.

  2. The constraint design is comprehensive, covering agent capabilities, temporal dependencies, deadlines, dynamic arrivals, resource limitations, and failures.

  3. The experiments are detailed, investigating generalization across workloads, constraint configurations, and application domains.

Critical weaknesses
  1. The main evaluation lacks stronger optimization-based or established learned scheduling baselines.

  2. Despite some generalization ability, GNN-PPO achieves limited performance and often underperforms LLMs under complex constraints. Exploring trained LLM allocators would help assess whether learning can improve upon these stronger starting points.

  3. The difficulty levels change multiple factors simultaneously, making cross-level performance differences difficult to interpret.

Questions for authors

N/A

5 comments

Dear Reviewer kTEX,

We sincerely thank the reviewer for the thoughtful and constructive feedback. We address each concern below.


W1: The main evaluation lacks stronger optimization-based or established learning-based scheduling baselines

We thank the reviewer for raising this important point. We agree that LLMs have stronger representation and reasoning abilities than lightweight networks, so LLM-based trained baselines may achieve better allocation quality. In real systems, however, the response latency of the allocation policy must also be considered. For tool-calling tasks such as TaskBench, a single LLM allocation decision can already take about as long as a sub-agent needs to execute one subtask. It is precisely because of this trade-off between allocation quality and efficiency that the paper focuses on lightweight learning-based allocators.

Nevertheless, LLM-based allocators are an indispensable reference. In Table A we therefore add trained LLM baselines from the Qwen3 family (Qwen3-1.7B, Qwen3-4B, Qwen3-8B) in three settings: (i) zero-shot; (ii) SFT on trajectories from different teachers (a heuristic teacher / a Gemini 3.8 Flash teacher); and (iii) SFT followed by RL fine-tuning with PPO (SFT+PPO, Qwen3-1.7B on C3–C5). As with GNN-PPO, every SFT and PPO model is trained separately per difficulty level, and GNN-PPO is also retrained for each level under the same split. Because the paper's core tasks have no train/test split, training on them directly would leak the test set. We therefore split the core tasks of each level 2:1:2 into training (M1/M2), validation (M3, used only for model selection) and test (M4/M5) sets, and evaluate on the multi-constraint suite (C1–C5). For SFT+PPO, PPO starts from the SFT model of the same level and teacher, is trained on M1/M2, and we report the checkpoint with the best M3 validation success within the first 1,500 training episodes. We run PPO only on C3–C5: on C1/C2, SFT is already nearly optimal (100% on C1, and 88.8–95.8% on C2 with the heuristic teacher), which leaves little headroom for RL. In addition, Table C reports the average latency per allocation decision of each method.

Table A. Core-split test completion rate (%), 10 environment seeds [95% CI].

MethodC1C2C3C4C5
Qwen3-1.7B zero-shot52.5 [11.0, 92.5]46.5 [10.6, 88.0]32.4 [23.8, 42.5]27.3 [20.9, 34.0]4.0 [0.0, 9.3]
Qwen3-1.7B SFT (heuristic teacher)100.0 [100.0, 100.0]88.8 [66.2, 100.0]53.6 [37.5, 69.4]50.5 [41.5, 58.8]11.2 [7.1, 17.0]
Qwen3-1.7B SFT (Gemini teacher)100.0 [100.0, 100.0]64.4 [23.8, 100.0]57.9 [47.0, 66.3]45.3 [30.0, 61.3]15.9 [12.7, 20.7]
Qwen3-1.7B SFT+PPO (heuristic teacher)––53.9 [47.1, 60.0]53.1 [44.0, 60.5]12.5 [5.0, 21.3]
Qwen3-1.7B SFT+PPO (Gemini teacher)––57.0 [49.5, 62.5]44.8 [33.0, 56.3]13.4 [0.0, 26.0]
Qwen3-4B zero-shot95.0 [80.0, 100.0]62.1 [18.8, 99.0]47.9 [42.0, 52.9]35.9 [27.6, 43.4]10.7 [8.9, 12.3]
Qwen3-4B SFT (heuristic teacher)100.0 [100.0, 100.0]92.5 [77.5, 100.0]51.0 [42.5, 60.6]50.0 [41.5, 59.4]6.7 [0.0, 14.7]
Qwen3-4B SFT (Gemini teacher)100.0 [100.0, 100.0]89.5 [71.9, 100.0]43.6 [36.8, 49.3]38.5 [27.0, 48.8]6.3 [0.0, 15.7]
Qwen3-8B zero-shot82.0 [55.0, 100.0]48.8 [10.0, 94.0]38.5 [28.0, 50.0]25.5 [18.0, 33.8]4.0 [0.0, 9.7]
Qwen3-8B SFT (heuristic teacher)100.0 [100.0, 100.0]95.8 [85.0, 100.0]48.1 [34.5, 59.4]47.8 [39.0, 55.0]6.0 [0.0, 13.3]
Qwen3-8B SFT (Gemini teacher)100.0 [100.0, 100.0]62.9 [21.3, 98.5]56.8 [50.1, 62.9]32.6 [19.0, 45.6]13.8 [11.4, 15.5]
GNN-PPO83.2 [77.7, 88.0]71.0 [40.5, 98.4]32.6 [26.3, 38.2]34.4 [29.6, 39.6]9.8 [4.3, 15.7]

These results suggest the following:

  1. The scale of the open-source models we tested does not close the gap to the specifically optimized GNN-PPO and the heuristic methods. Although all three models are far larger than the GNN-PPO network, in the zero-shot setting only 4B exceeds GNN-PPO on both C3 and C4 (47.9/35.9 vs. 32.6/34.4); 8B exceeds it only on C3 (38.5), and 1.7B does not exceed it on any of C3–C5. In the other cases, the zero-shot models fall short of the specifically optimized GNN-PPO and the heuristic methods. This indicates that dedicated policy optimization of GNN-PPO can partly compensate for its smaller model size and weaker representation ability. Moreover, a case study shows that zero-shot 8B more often issues allocations on C3/C4 that exceed resource capacity and are filtered by the safety check, which wastes decision steps. This suggests that richer language priors do not necessarily translate directly into a better allocation policy.

To understand where the PPO gains go, Table B compares, for each level and teacher, the SFT model and the PPO checkpoint selected on validation on the training, validation and test tasks.

Table B. Qwen3-1.7B SFT → SFT+PPO (validation-selected checkpoint) on training (M1/M2), validation (M3) and test (M4/M5) tasks, completion rate (%). 10 environment seeds, paired difference [95% CI].

Level / teacherSelected checkpointTraining (M1/M2)Validation (M3)Test (M4/M5)
C3 / heuristicep 30443.4 → 45.2 (+1.8)39.6 → 46.2 (+6.6)52.4 → 53.9 (+1.5 [−15.0, 18.5])
C4 / heuristicep 46437.6 → 43.6 (+6.0)45.0 → 50.0 (+5.0)52.0 → 53.1 (+1.1 [−7.5, 9.4])
C5 / heuristicep 150024.5 → 25.9 (+1.4)15.0 → 15.0 (+0.0)11.2 → 12.5 (+1.3 [−2.1, 5.0])
C3 / Geminiep 105635.9 → 52.9 (+17.0)30.0 → 44.2 (+14.2)55.6 → 57.0 (+1.4 [−7.5, 11.8])
C4 / Geminiep 30435.8 → 35.6 (−0.2)32.9 → 38.3 (+5.4)43.4 → 44.8 (+1.4 [−8.1, 11.5])
C5 / Geminiep 120019.4 → 32.1 (+12.7)11.4 → 20.8 (+9.4)16.2 → 13.4 (−2.8 [−17.9, 11.0])

Over the first 1,500 episodes, training success rises steadily for every run (by up to about 20 points), whereas validation success stays roughly flat after the first few hundred episodes. A greedy re-evaluation on the training tasks confirms that the late checkpoints have genuinely improved there (C3/heuristic +11.7 [6.0, 17.4], C4/heuristic +6.8 [1.2, 12.2] points over SFT). The gains on the tasks seen during training and model selection (up to +17 points) do not carry over to the test tasks, where every paired difference to SFT is within about ±3 points.

  1. SFT brings the clearest improvement; PPO mainly makes the policy more deterministic but overfits. After per-level SFT, the LLMs of all three sizes outperform GNN-PPO on C3 (43.6–57.9 vs. 32.6). PPO on top of SFT lowers the policy entropy and makes the allocations more deterministic: on C3/C4 the test confidence intervals become narrower and their lower bounds rise (e.g., C3: 37.0 → 47.1 with the heuristic teacher and 44.0 → 49.5 with the Gemini teacher), i.e., the worst-case behaviour improves. However, PPO overfits to the training tasks: its gains on the training and validation tasks (Table B) do not transfer to the test tasks, whose task and resource distributions differ substantially, and its improvement over the SFT baseline on the test set is very limited (all paired differences include zero; C5 remains hard for every method). This reveals an open RL problem for allocation policies: generalizing beyond the task and resource distributions seen in training, rather than fitting them. In our observation, this is compounded by a complex decision space caused by coupled constraints, the trade-off between global return and individual tasks, and sparse rewards in long-horizon tasks.

Table C. Average wall-clock time per allocation decision (local LLMs served with vLLM on a single H800, including serialization and parsing).

AllocatorTime per decisionRelative to EDF
EDF0.11 ms1×
HEFT9.2 ms86×
GNN-PPO (CPU / GPU)12.0 / 13.6 ms≈110–130×
Qwen3-1.7B91 ms≈860×
Qwen3-4B146 ms≈1,400×
Qwen3-8B152 ms≈1,400×
Qwen3-8B (thinking)13.5–65 s≈10⁵×
Closed-source API (GPT-5.6-Sol)3.2 s≈3×10⁴×
  1. LLM allocators have much higher latency than lightweight methods. Whether locally trained or accessed through a closed-source API, LLMs take about 3–5 orders of magnitude longer per decision than EDF, and are also substantially slower than GNN-PPO (Table C). With thinking enabled, Qwen3-8B takes 13.5–65 s per allocation, which is 1.4–5.5× the average execution time of the subtasks it allocates. For time-sensitive MAS, the choice of allocation policy therefore requires an additional trade-off between quality and latency.


W2: Are trained LLM baselines better under multiple constraints? How well do they generalize across tasks?

  1. Generalization to unseen tasks under the same constraints (Table A). See the multi-constraint suite experiments in W1; the test tasks of each level never appear during training. In this setting, the per-level SFT students generally outperform GNN-PPO on C3 (e.g., the 1.7B/4B students with the heuristic teacher reach 53.6/50.5 and 51.0/50.0 on C3/C4, whereas GNN-PPO reaches 32.6/34.4). This indicates that, under the same constraints, SFT lets the LLM baselines generalize to new tasks to some extent. PPO on top of SFT does not further improve this generalization: although it clearly improves performance on the training and validation tasks, the 1.7B SFT+PPO models stay on par with their SFT starting points on the unseen test tasks of C3–C5 (Table B), i.e., the additional gains from RL are specific to the tasks seen during training.

  2. Transfer across constraint levels. We train and select the Qwen3-1.7B models using only C3 data, both the per-level SFT models (heuristic / Gemini teacher) and the SFT+PPO models of W1. We then test them directly on C2, C4 and C5 without any adaptation, on the same test tasks as Table A. Consistent with our previous findings, the SFT students keep a reasonable completion rate under unseen constraint combinations, while the new combination of constraints (especially C5) remains the main difficulty (Table D). PPO does not improve cross-constraint transfer: on every target level, the SFT+PPO models are statistically indistinguishable from their SFT starting points. This is consistent with Table B: what PPO learns is largely specific to the training tasks and does not transfer to new tasks, let alone to new constraints.

Table D. Cross-constraint transfer of Qwen3-1.7B models trained and selected on C3 only (test completion rate %, 10 environment seeds [95% CI]).

Method (trained on C3 only)C2 (transfer)C3 (in-distribution)C4 (transfer)C5 (transfer)
Qwen3-1.7B SFT (heuristic teacher)92.5 [73.8, 100.0]52.4 [37.0, 66.9]45.0 [30.0, 58.1]6.7 [0.0, 13.3]
Qwen3-1.7B SFT+PPO (heuristic teacher)100.0 [100.0, 100.0]53.9 [47.1, 60.0]46.1 [37.0, 54.4]7.7 [0.0, 16.3]
Qwen3-1.7B SFT (Gemini teacher)86.3 [62.5, 100.0]55.6 [44.0, 64.4]50.1 [42.5, 57.1]7.5 [3.6, 11.7]
Qwen3-1.7B SFT+PPO (Gemini teacher)87.6 [66.2, 100.0]57.0 [49.5, 62.5]47.1 [39.5, 53.8]7.6 [5.7, 9.7]
  1. Cross-dataset transfer to TaskBench. We deploy the same C3-trained SFT and SFT+PPO models directly on the TaskBench extension in the paper, without any TaskBench training, tuning or model selection. Consistent with our previous findings, SFT on Overcooked brings no consistent gain on TaskBench for the 1.7B model, whose zero-shot completion rate is already high because TaskBench states are simpler and its policy is conservative. PPO does not improve cross-dataset transfer either: with the heuristic teacher, SFT+PPO is on par with SFT on all five levels; with the Gemini teacher, SFT+PPO is lower than SFT on several levels, significantly so on L4.

Table E. Cross-dataset transfer to TaskBench of the Qwen3-1.7B models trained on C3 only (completion rate %, 12 cases × 10 repeats per level [95% CI]).

Method (trained on C3 only, zero-shot transfer to TaskBench)L1L2L3L4L5Mean allocation time / share of time limit
Qwen3-1.7B SFT (heuristic teacher)100.0 [100.0, 100.0]75.0 [50.0, 100.0]99.2 [97.5, 100.0]91.2 [76.2, 99.6]86.7 [68.1, 98.5]121 ms / 17.9%
Qwen3-1.7B SFT+PPO (heuristic teacher)100.0 [100.0, 100.0]76.4 [51.4, 100.0]97.7 [92.7, 100.0]91.6 [76.7, 99.6]83.5 [63.5, 98.1]123 ms / 18.0%
Qwen3-1.7B SFT (Gemini teacher)100.0 [100.0, 100.0]88.0 [68.4, 100.0]97.9 [92.7, 100.0]96.3 [92.7, 99.1]84.0 [64.2, 98.4]131 ms / 17.9%
Qwen3-1.7B SFT+PPO (Gemini teacher)100.0 [100.0, 100.0]75.1 [50.9, 97.9]94.8 [84.4, 100.0]85.4 [72.4, 94.5]81.4 [62.3, 95.6]130 ms / 16.3%
  1. Measured allocation latency on TaskBench. Under real wall-clock execution, the allocation time of the LLM allocators directly eats into the execution time (Table E): each decision takes on the order of a hundred milliseconds, and in total the allocation occupies a substantial share of the task time limit, whereas EDF takes about 0.45 ms per decision and less than 0.1% of the time limit. PPO does not change this cost. This directly supports our argument in W1: for real-time tasks such as tool calling, the decision latency and the quality of an LLM allocator have become a trade-off that must be made.

Reviewer_hkFLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Schedule-Overcooked is a benchmark for allocating concurrent tasks among agents under capability, dependency, timing, and resource constraints. It fixes task decomposition and local execution so that allocators can be compared under a common execution policy. The benchmark provides four workload-complexity levels and five cumulative constraint levels, with a shared allocation interface extended to TaskBench, Minecraft, and Factorio. Experiments compare rule-based, LLM, and GNN-PPO allocators, then study constraint relaxations, learning behavior, and policy transfer. Results show that high agent occupancy can coexist with low task completion and that performance varies substantially across constraint settings.

Critical strengths
  1. Holding task decomposition and execution policy fixed provides a useful controlled setting for comparing allocation decisions. The graded workloads and composable constraints retain dependencies, resource competition, and timing requirements that matter when multiple workflows share agents.

  2. The experiments combine rule-based, LLM, and learned allocators with paired constraint interventions and cross-domain tests. They expose the gap between agent occupancy and completed workflows and demonstrate native TaskBench execution, with more limited feasibility checks in Minecraft and Factorio. This supports diagnostic use of the benchmark and its implementation beyond the kitchen setting.

Critical weaknesses
  1. The attainable completion rates on C3–C5 are not calibrated against a strong reference, making it difficult to separate allocation failures from limitations imposed by the instances. The CP-SAT results in Appendix A concern a separate ParaCook diagnostic.

  2. Each constraint level contains five core task families, and the manuscript does not clearly report independent seeds or run-to-run variability. This limits confidence in the stability of the reported method rankings and transfer effects.

Questions for authors
  1. How were representative C3–C5 instances checked for attainable completion under their original constraints? Are feasible schedules or strong reference results available?

  2. How many independent training seeds and evaluation runs underlie the key stochastic results, and how variable are the reported comparisons?

2 comments

Dear Reviewer hkFL,

We sincerely thank the reviewer for the thoughtful and constructive feedback, and for recognizing the contributions of our work. We address each concern below.


W1: Missing feasibility reference

We thank the reviewer for pointing out the absence of a feasibility reference. A feasibility reference is indeed important to show that the benchmark tasks are well designed. However, exact solver-based planning is hard to scale since multi-task allocation is NP-hard, and its solution space grows combinatorially as constraints accumulate.

  • For tasks with simple constraints (i.e., C1–C2), our CP-SAT solver returns optimal plans within a bounded time budget.
  • For tasks with more complex constraints (e.g. C3–C5, with stochastic agent behavior and environment sampling in addition to the constraints), our CP-SAT solver could not produce competitive plans within the decision-time budget.

As an alternative, we provide a best-known achievable reference solution for every scenario × seed (Table 1). It is obtained by simulator-in-the-loop heuristic search:

  1. The search starts from the strongest trajectories among several baselines.
  2. It then backtracks and explores the allocation choices at each decision state, pruning states that are not promising.
  3. Every reported value is certified by replaying its decisions in the unchanged evaluator, which reproduces exactly the same completed orders.

The search depends on its warm starts and its search budget, and it may stop at a local optimum. It therefore does not guarantee global optimality. Even so, it finds solutions that complete far more orders than the strongest current baseline. This shows that substantially higher completion is attainable on every level.

Table 1. C3–C5 completion rate (%), 5 scenarios × 10 seeds [95% CI].

LevelEDFGemini 3.8 FlashBest-known achievable (search)
C347.8 [36.7, 59.0]49.4 [39.8, 59.2]91.7 [86.6, 97.0]
C445.7 [34.6, 56.5]42.8 [30.8, 53.9]87.6 [80.2, 95.2]
C512.2 [6.8, 18.7]18.0 [10.7, 26.5]65.3 [58.8, 71.7]

We will add these results to Section 5.2 and Appendix H (Table 17) of the revised manuscript.


W2: Uncertainty of the results (seeds, episodes per scenario, confidence intervals)

We thank the reviewer for raising this important point.

To model the uncertainty of real-world agents and execution environments, our tasks include stochastic events controlled by environment random seeds. The original experiments used a single environment seed, which keeps them exactly reproducible. GNN-PPO was trained with two training seeds. We understand the reviewer's concern that a small number of seeds may introduce sampling variance and thus affect the reliability of the baseline evaluation. To address this, we further conducted the following experiments with results summarized in Table 2:

  • evaluated all baselines on the C3–C5 multi-constraint suite with 10 environment seeds;
  • trained GNN-PPO with 5 training seeds.

Table 2. Multi-seed evaluation: completion rate (%), mean over 10 environment seeds [95% CI], 5 scenarios per level.

MethodC3C4C5
Serial12.8 [11.0, 15.0]22.3 [18.6, 26.3]15.6 [14.5, 16.8]
Random-Feasible23.3 [15.2, 31.3]24.7 [17.0, 33.0]8.2 [5.6, 11.3]
EDF47.8 [36.7, 59.0]45.7 [34.6, 56.5]12.2 [6.8, 18.7]
Greedy-Time36.3 [16.2, 54.0]40.8 [27.4, 52.5]14.9 [6.0, 24.1]
HEFT14.4 [4.4, 27.8]12.8 [4.1, 25.6]3.8 [1.5, 6.3]
GNN-PPO (5 training seeds)32.1 [25.3, 38.7]32.1 [23.3, 40.0]19.9 [14.1, 26.4]
Gemini 3.8 Flash49.4 [39.8, 59.2]42.8 [30.8, 53.9]18.0 [10.7, 26.5]
Grok 4.640.5 [32.9, 49.1]36.6 [23.6, 48.8]16.3 [8.5, 26.4]
GPT-5.6-Sol45.0 [33.9, 55.7]43.0 [30.3, 56.4]16.4 [10.6, 24.7]

These results suggest the following:

  1. The main conclusions hold. The environment seed shifts the effective difficulty of a scenario within a certain range. Even so, the relative ranking of the heuristic, LLM and GNN-PPO baselines on C3–C5 remains qualitatively unchanged across seeds, so the main conclusions of the paper still hold.
  2. GNN-PPO is reliable. Its variability across seeds stays within a reasonable range (CI width of 12–17 pp on C3–C5), confirming the reliability of its reported results.

We thank the reviewer for this valuable suggestion. We will add the full multi-seed report, including the per-scenario breakdown, to Appendix I (Table 18) of the revised manuscript.


We thank the reviewer again for the insightful comments, which have helped us improve the paper. We hope our responses address your concerns, and we would be happy to provide any further clarification.

Best regards,

The Authors

Thank you for your response. I will maintain my current rating.

Reviewer_g3C2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies multi-task allocation in LLM-based multi-agent systems, where multiple concurrent tasks compete for a shared pool of agents and resources. Existing evaluations often measure allocation only through end-to-end task success, making allocation quality difficult to separate from task decomposition and low-level execution, while also covering limited operational constraints or task domains.

The main contribution is Schedule-Overcooked, a benchmark that fixes task decomposition and execution so that evaluated methods primarily decide subtask ownership and dispatch timing. The benchmark provides four workload-complexity levels and a five-level constraint suite covering agent capabilities, temporal constraints, dynamic task arrivals, and shared-resource restrictions. A common allocation interface is further instantiated in TaskBench, Minecraft, and Factorio to support transfer evaluation.

For validation, the authors compare rule-based methods, LLM allocators, and a learned GNN-PPO allocator. They analyze performance as workload and constraints become more complex, conduct paired constraint-relaxation experiments, evaluate transfer between benchmark levels, and test cross-domain deployment and adaptation. The results show substantial differences between allocators, that high agent utilization does not necessarily imply task completion, and that learned policies have difficulty under compound temporal and resource constraints.

Critical strengths

1. The benchmark targets an important evaluation problem.\textbf{1. The benchmark targets an important evaluation problem.} Separating allocation decisions from low-level execution is useful because end-to-end MAS performance alone makes it difficult to determine whether failures originate from poor allocation or poor execution.

Critical weaknesses

1. The benchmark does not establish the feasibility or optimal achievable performance of its difficult instances.\textbf{1. The benchmark does not establish the feasibility or optimal achievable performance of its difficult instances.} The central metric is the fraction of high-level tasks completed within their deadlines. However, for the more difficult C3–C5 settings, all evaluated methods obtain relatively low success, and no optimal solver or oracle allocation is provided to establish how many tasks are actually achievable under the specified deadlines, resources, failures, and episode horizons. The paper itself acknowledges that low performance may partly reflect instance-feasibility limitations.

This makes some of the main diagnostic conclusions difficult to interpret. For example, low success under compound constraints may indicate poor allocation, but it could also indicate that a non-negligible fraction of the benchmark workload is infeasible regardless of the allocator. Since the paper's primary goal is to evaluate allocation efficiency, I believe an oracle/optimization-based upper bound, or at least explicit feasibility validation of the core evaluation instances, is important for interpreting the reported scores.

Questions for authors

Can the authors provide an oracle- or optimization-based estimate of the achievable success rate for the C3–C5 core instances, or otherwise verify that the evaluated workloads are feasible under their deadlines and resource constraints?

3 comments

Dear Reviewer g3C2,

We sincerely thank the reviewer for the thoughtful and constructive feedback, and for recognizing the contributions of our work. We address each concern below.


W: Missing feasibility reference

We thank the reviewer for pointing out the absence of a feasibility reference which is we fully agree indeed important to show that the benchmark tasks are well designed. However, exact solver-based planning is hard to scale, since multi-task allocation is NP-hard [1], and its solution space grows combinatorially as constraints accumulate.

  • For tasks with simple constraints (i.e., C1–C2), our CP-SAT solver returns optimal plans within a bounded time budget.
  • For tasks with more complex constraints (e.g. C3–C5, with stochastic agent behavior and environment sampling in addition to the constraints), our CP-SAT solver could not produce competitive plans within the decision-time budget.

As an alternative, we provide a best-known achievable reference solution for every scenario × seed (Table 1). It is obtained by simulator-in-the-loop heuristic search:

  1. The search starts from the strongest trajectories among several baselines.
  2. It then backtracks and explores the allocation choices at each decision state, pruning states that are not promising.
  3. Every reported value is certified by replaying its decisions in the unchanged evaluator, which reproduces exactly the same completed orders.

The search depends on its warm starts and its search budget, and it may stop at a local optimum. It therefore does not guarantee global optimality. Even so, it finds solutions that complete far more orders than the strongest current baseline. This shows that substantially higher completion is attainable on every level.

Table 1. C3–C5 completion rate (%), 5 scenarios × 10 seeds [95% CI].

LevelEDFGemini 3.8 FlashBest-known achievable (search)
C347.8 [36.7, 59.0]49.4 [39.8, 59.2]91.7 [86.6, 97.0]
C445.7 [34.6, 56.5]42.8 [30.8, 53.9]87.6 [80.2, 95.2]
C512.2 [6.8, 18.7]18.0 [10.7, 26.5]65.3 [58.8, 71.7]

We will add these results to Section 5.2 and Appendix H (Table 17) of the revised manuscript.

Reference

[1] J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259–271, 1990.


We thank the reviewer again for the insightful comments, which have helped us improve the paper. We hope our responses address your concerns, and we would be happy to provide any further clarification.

Best regards,

The Authors

Dear Reviewer g3C2,

Could you please review the authors’ rebuttals and follow up with any further comments or questions?

Many thanks for your time and efforts.

Best regards, AC

Thank the authors for their detailed response. My concerns have been addressed, and I maintain my positive rating.

Reviewer_pmSGOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how LLM-based multi-agent systems should allocate the dependent subtasks of concurrent tasks to a shared pool of agents, arguing that allocation is currently evaluated only through end-to-end task success, where it is confounded with low-level execution. Schedule-Overcooked, built on Overcooked-AI, fixes decomposition (each task is a subtask DAG) and execution (an Assignment-to-Action Adapter carries out each subtask–agent pair), so the allocator controls only subtask ownership, dispatch timing and batch order. A four-level task-complexity suite (B1–B4) is paired with a cumulative five-level constraint suite (C1–C5), and the same interface is exposed in TaskBench, Minecraft and Factorio. The authors compare five rule-based allocators, three LLM allocators and a GNN-PPO allocator, and further probe GNN-PPO with paired constraint relaxations and frozen-policy transfer across levels and domains.

Critical strengths

The allocation boundary is unusually explicit. Table 11 confines the allocator’s business decisions to “Subtask, owner, dispatch time, and batch order”, leaving paths and facilities to fixed local rules, and handoffs become transfer nodes that the allocator must itself staff (Fig. 8). Rule-based, LLM and learned allocators therefore share one trigger, validator and adapter.

Critical weaknesses
  1. My primary concern is the practical value of this benchmark. Harnesses such as Claude Code and Codex already let a lead agent decompose work and dispatch it to sub-agents, whereas here decomposition is fixed, a heuristic adapter executes every assignment (Sec. 4.1), and the LLM-worker condition defined in App. C.4 is not reported for the B/C suites. Would an allocator that ranks well here improve throughput or deadline compliance as the sub-agent dispatcher of such a harness, and would the per-level rankings still hold under these mature harnesses?

  2. The headline comparisons carry no uncertainty and partly rest on small cohorts. Apart from Fig. 5’s family interquartile bands, the paper reports no seeds, episodes per case or confidence intervals, although each C level has only five families and C-suite execution is stochastic (App. C.4). Sec. 4.2 states that “Evaluation uses the 40 core tasks”, yet all 12 LLM SR values in Table 3 lie on the k/8 (B1) or k/12 (B2–B4) rounding grid, suggesting—an inference the authors should confirm—a single 8- or 12-task case per model and level. What appear to be the same validation-selected GNN-PPO checkpoints also disagree by 10.7 points on C4: 33.92% for the Fig. 5 intervention cohort (App. F) versus 44.6% in Fig. 9(d). Bolded winners are often separated by far less (e.g., GNN-PPO 70 vs. 67 on B2, Table 3), yet Sec. 5.2 concludes that “GNN-PPO is strongest on B2 and B4”. I therefore cannot determine whether the per-level rankings, especially LLM versus rule-based, reflect real differences rather than evaluation noise.

  3. No feasibility ceiling or reference solution is reported for any B or C instance, so C5’s “no method exceeds 28%” (Sec. 5.2) cannot be separated from instance infeasibility—an alternative Sec. 5.3 itself raises—although the authors already used CP-SAT as a reference in decoupled ParaCook (App. A.3).

Questions for authors

N/A

4 comments

Dear Reviewer pmSG,

We sincerely thank the reviewer for the thoughtful and constructive feedback, and for recognizing the contributions of our work. We address each concern below.


W1: Practical value — does an allocator help harnesses such as Claude Code / Codex?

We thank the reviewer for raising the question of practical value.

First, our work studies subtask allocation across multiple concurrent tasks. The allocator must handle constraints and resource contention both between parallel tasks and among the subtasks of a single task. This setting is central to online multi-agent systems that serve concurrent workloads. The problem is far from solved. As shown in Table 4 of the paper, even GPT-5.6-Sol—a strong LLM commonly used in coding agents such as Codex—degrades substantially under the moderately difficult C3 constraints. Multi-task allocation thus remains both challenging and important for current systems.

Second, subtask dispatching within a single complex task, as in Claude Code / Codex, is a special (single-task) case of the problem we study. Better allocation policies can therefore also improve how efficiently the subtasks of one task run in parallel. Our allocator can be integrated into such harnesses in a fairly natural way, requiring no modification to the harness's core execution loop:

  • the lead agent emits a parsable task-dependency graph;
  • a thin layer passes the current state to the allocator, then parses and applies its allocation decisions.

We will add a discussion of this integration path to Section 6 and Appendix C.6 of the revised manuscript.


W2: Uncertainty of the results (seeds, episodes per scenario, confidence intervals)

We thank the reviewer for raising this important point.

To model the uncertainty of real-world agents and execution environments, our tasks include stochastic events controlled by environment random seeds. The original experiments used a single environment seed, which keeps them exactly reproducible. GNN-PPO was trained with two training seeds. We understand the reviewer's concern that a small number of seeds may introduce sampling variance and thus affect the reliability of the baseline evaluation. To address this, we further conducted the following experiments with results summarized in Table 1:

  • evaluated all baselines on the C3–C5 multi-constraint suite with 10 environment seeds;
  • trained GNN-PPO with 5 training seeds.

Table 1. Multi-seed evaluation: completion rate (%), mean over 10 environment seeds [95% CI], 5 scenarios per level.

MethodC3C4C5
Serial12.8 [11.0, 15.0]22.3 [18.6, 26.3]15.6 [14.5, 16.8]
Random-Feasible23.3 [15.2, 31.3]24.7 [17.0, 33.0]8.2 [5.6, 11.3]
EDF47.8 [36.7, 59.0]45.7 [34.6, 56.5]12.2 [6.8, 18.7]
Greedy-Time36.3 [16.2, 54.0]40.8 [27.4, 52.5]14.9 [6.0, 24.1]
HEFT14.4 [4.4, 27.8]12.8 [4.1, 25.6]3.8 [1.5, 6.3]
GNN-PPO (5 training seeds)32.1 [25.3, 38.7]32.1 [23.3, 40.0]19.9 [14.1, 26.4]
Gemini 3.8 Flash49.4 [39.8, 59.2]42.8 [30.8, 53.9]18.0 [10.7, 26.5]
Grok 4.640.5 [32.9, 49.1]36.6 [23.6, 48.8]16.3 [8.5, 26.4]
GPT-5.6-Sol45.0 [33.9, 55.7]43.0 [30.3, 56.4]16.4 [10.6, 24.7]

These results suggest the following:

  1. The main conclusions hold. The environment seed shifts the effective difficulty of a scenario within a certain range. Even so, the relative ranking of the heuristic, LLM and GNN-PPO baselines on C3–C5 remains qualitatively unchanged across seeds, so the main conclusions of the paper still hold.
  2. GNN-PPO is reliable. Its variability across seeds stays within a reasonable range (CI width of 12–17 pp on C3–C5), confirming the reliability of its reported results.

We thank the reviewer for this valuable suggestion. We will add the full multi-seed report, including the per-scenario breakdown, to Appendix I (Table 18) of the revised manuscript.


W3: Missing feasibility reference

We thank the reviewer for pointing out the absence of a feasibility reference. A feasibility reference is indeed important to show that the benchmark tasks are well designed. However, exact solver-based planning is hard to scale since multi-task allocation is NP-hard [1], and its solution space grows combinatorially as constraints accumulate.

  • For tasks with simple constraints (i.e., C1–C2), our CP-SAT solver returns optimal plans within a bounded time budget.
  • For tasks with more complex constraints (e.g. C3–C5, with stochastic agent behavior and environment sampling in addition to the constraints), our CP-SAT solver could not produce competitive plans within the decision-time budget.

As an alternative, we provide a best-known achievable reference solution for every scenario × seed (Table 2). It is obtained by simulator-in-the-loop heuristic search:

  1. The search starts from the strongest trajectories among several baselines.
  2. It then backtracks and explores the allocation choices at each decision state, pruning states that are not promising.
  3. Every reported value is certified by replaying its decisions in the unchanged evaluator, which reproduces exactly the same completed orders.

The search depends on its warm starts and its search budget, and it may stop at a local optimum. It therefore does not guarantee global optimality. Even so, it finds solutions that complete far more orders than the strongest current baseline. This shows that substantially higher completion is attainable on every level.

Table 2. C3–C5 completion rate (%), 5 scenarios × 10 seeds [95% CI].

LevelEDFGemini 3.8 FlashBest-known achievable (search)
C347.8 [36.7, 59.0]49.4 [39.8, 59.2]91.7 [86.6, 97.0]
C445.7 [34.6, 56.5]42.8 [30.8, 53.9]87.6 [80.2, 95.2]
C512.2 [6.8, 18.7]18.0 [10.7, 26.5]65.3 [58.8, 71.7]

We will add these results to Section 5.2 and Appendix H (Table 17) of the revised manuscript.

Reference

[1] J. K. Lenstra, D. B. Shmoys, and É. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259–271, 1990.


We thank the reviewer again for the insightful comments, which have helped us improve the paper. We hope our responses address your concerns, and we would be happy to provide any further clarification.

Best regards,

The Authors

Dear Reviewer pmSG,

Could you please review the authors’ rebuttals and follow up with any further comments or questions?

Many thanks for your time and efforts.

Best regards, AC

Dear Reviewer pmSG,

Thank you again for your review.

As the discussion period closes, we would like to check whether our response addresses your concerns.

On practical value (W1), subtask dispatch within a single task, as in Claude Code / Codex, is a special case of the multi-task allocation we study. Even GPT-5.6-Sol degrades substantially under the C3 constraints, so the problem remains open for current systems. Our allocator plugs into such harnesses through a parsable dependency graph and a thin dispatch layer, without changing the core execution loop. We will discuss this in Section 6 and Appendix C.6.

On uncertainty (W2), all baselines are now evaluated over 10 environment seeds with 95% CIs, and GNN-PPO is trained with 5 seeds (Table 1\textcolor{red}{\text{Table 1}}). The ranking of heuristic, LLM and GNN-PPO methods on C3–C5 stays qualitatively unchanged. GNN-PPO's CI width stays within 12–17 pp.

On the feasibility reference (W3), every C3–C5 scenario × seed now has a best-known achievable solution (Table 2\textcolor{red}{\text{Table 2}}). It was found by simulator-in-the-loop search, and each value is certified by replaying its decisions in the unchanged evaluator. These solutions complete 91.7 / 87.6 / 65.3% of orders on C3 / C4 / C5. The strongest baseline completes 49.4 / 45.7 / 18.0%. Substantially higher completion is therefore attainable at every level.

We would be glad to clarify anything further.

Best regards,

The Authors

Comments on the paper

1 comment

Dear Reviewers,

As the AC–reviewer discussion phase is about to begin, please highlight any disagreements or inconsistencies across the reviews, as well as any concerns that remain unresolved after the author rebuttal.

Please share your perspectives on these points and engage with one another to help us reach a well-supported assessment of the paper.

Thank you for your time and contributions.

Best regards, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.