- 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
-
The benchmark offers a novel combination of cross-task agent allocation, capability uncertainty, and shared-resource contention.
-
The constraint design is comprehensive, covering agent capabilities, temporal dependencies, deadlines, dynamic arrivals, resource limitations, and failures.
-
The experiments are detailed, investigating generalization across workloads, constraint configurations, and application domains.
Critical weaknesses
-
The main evaluation lacks stronger optimization-based or established learned scheduling baselines.
-
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.
-
The difficulty levels change multiple factors simultaneously, making cross-level performance differences difficult to interpret.
Questions for authors
N/A
5 comments
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 / teacher | Selected checkpoint | Training (M1/M2) | Validation (M3) | Test (M4/M5) |
|---|---|---|---|---|
| C3 / heuristic | ep 304 | 43.4 → 45.2 (+1.8) | 39.6 → 46.2 (+6.6) | 52.4 → 53.9 (+1.5 [−15.0, 18.5]) |
| C4 / heuristic | ep 464 | 37.6 → 43.6 (+6.0) | 45.0 → 50.0 (+5.0) | 52.0 → 53.1 (+1.1 [−7.5, 9.4]) |
| C5 / heuristic | ep 1500 | 24.5 → 25.9 (+1.4) | 15.0 → 15.0 (+0.0) | 11.2 → 12.5 (+1.3 [−2.1, 5.0]) |
| C3 / Gemini | ep 1056 | 35.9 → 52.9 (+17.0) | 30.0 → 44.2 (+14.2) | 55.6 → 57.0 (+1.4 [−7.5, 11.8]) |
| C4 / Gemini | ep 304 | 35.8 → 35.6 (−0.2) | 32.9 → 38.3 (+5.4) | 43.4 → 44.8 (+1.4 [−8.1, 11.5]) |
| C5 / Gemini | ep 1200 | 19.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.
- 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).
| Allocator | Time per decision | Relative to EDF |
|---|---|---|
| EDF | 0.11 ms | 1× |
| HEFT | 9.2 ms | 86× |
| GNN-PPO (CPU / GPU) | 12.0 / 13.6 ms | ≈110–130× |
| Qwen3-1.7B | 91 ms | ≈860× |
| Qwen3-4B | 146 ms | ≈1,400× |
| Qwen3-8B | 152 ms | ≈1,400× |
| Qwen3-8B (thinking) | 13.5–65 s | ≈10⁵× |
| Closed-source API (GPT-5.6-Sol) | 3.2 s | ≈3×10⁴× |
- 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?
-
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.
-
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] |
- 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) | L1 | L2 | L3 | L4 | L5 | Mean 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% |
- 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.
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].
These results suggest the following: