Paper deep dive

Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study

Yuyu Zhang

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 76

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%

Last extracted: 10/12/2026, 6:05:19 AM

Summary

This study conducts a controlled computational experiment comparing Monte Carlo Tree Search (MCTS) against a randomized-restart list scheduler for scheduling Directed Acyclic Graph (DAG) workflows. Using a preregistered protocol with equal search budgets (2048 evaluated schedules), the study finds that MCTS performs 2.88% worse than the restart scheduler on held-out instances with positive headroom. The deficit is attributed to MCTS's selection rule locking onto the first-expanded child, whereas restarts benefit from diverse sampling. Swapping to a textbook UCT rule reduces the deficit but does not reverse it. Results suggest restarts are superior for sparse, irregular workflows, while MCTS offers no advantage in the tested synthetic domain.

Entities (8)

Monte Carlo Tree Search · algorithm · 98%Randomized-Restart List Scheduler · algorithm · 97%DAG Workflows · problem-domain · 95%Makespan · metric · 93%UCT · algorithm-variant · 92%WfCommons · dataset · 90%CPOP · algorithm · 85%HEFT · algorithm · 85%

Relation Signals (6)

Monte Carlo Tree Search → comparedwith → Randomized-Restart List Scheduler

confidence 98% · We run that comparison under a controlled protocol. All arms receive an identical budget... an MCTS scheduling method... a randomized-restart list scheduler... as the control

Monte Carlo Tree Search → appliedto → DAG Workflows

confidence 95% · Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows

Monte Carlo Tree Search → performsworsethan → Randomized-Restart List Scheduler

confidence 95% · At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts

Randomized-Restart List Scheduler → outperforms → Monte Carlo Tree Search

confidence 90% · restarts win on sparse irregular workflows... MCTS is 2.88% worse than the restarts

UCT → reducesdeficitof → Monte Carlo Tree Search

confidence 88% · Swapping the rule for textbook UCT removes most of the deficit (-0.26%...)

HEFT → partofbaselineportfolio → CPOP

confidence 80% · M0 is the per-instance best of a four-heuristic portfolio (HEFT, CPOP, PEFT, OCT)

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows, yet most studies never run the comparison that could refute it - giving a much simpler method the same search effort. We run that comparison under a controlled protocol. All arms receive an identical budget - the same number of candidate schedules built and evaluated: an MCTS scheduling method, preregistered as the main arm; a randomized-restart list scheduler with no search tree as the control; and a textbook-UCT MCTS arm as a registered follow-up on the same domain. The analysis plan was locked before data collection; an independent checker confirmed all 768 confirmation-stage schedules valid with correct finish times. At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts (95% CI [-3.62%,-2.15%]; the 72 of 96 held-out instances with positive baseline-relative headroom). The deficit is not budget starvation: on the separate exploration pool restarts self-improve by 1.85% where MCTS gains 0.24%, and 700 of 720 of MCTS's first results are merely the warm start it was handed. The studied selection rule locks deterministically onto the first-expanded child, keeping its trials correlated while restarts draw gains from the tails; the causal link to makespan remains an inference. A structural map locates where the tree stops paying: restarts win on sparse irregular workflows, no difference is detectable on regular layered ones, and dense ones leave no room to improve. Swapping the rule for textbook UCT removes most of the deficit (-0.26%, 95% CI [-0.71%,+0.23%]) without reversing its sign. Results are confined to a controlled synthetic domain (N in {8,16,32} tasks, 2-8 processors, budgets up to 2048); we make no claim about larger budgets.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

72,262 characters extracted from source content.

Expand or collapse full text

Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study Yuyu Zhang †thanks: Unfunded personal research, conducted independently on personal time and equipment, unrelated to any employment duty. Correspondence: 771262402@q.com Abstract Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows, yet most studies never run the comparison that could refute it—giving a much simpler method the same search effort. We run that comparison under a controlled protocol. All arms receive an identical budget—the same number of candidate schedules built and evaluated: an MCTS scheduling method, preregistered as the main arm; a randomized-restart list scheduler with no search tree as the control; and a textbook-UCT MCTS arm as a registered follow-up on the same domain. The analysis plan was locked before data collection; an independent checker confirmed all 768 confirmation-stage schedules valid with correct finish times. At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts (95% CI [−3.62%,−2.15%][-3.62\%,-2.15\%]; the 72 of 96 held-out instances with positive baseline-relative headroom). The deficit is not budget starvation: on the separate exploration pool restarts self-improve by 1.85% where MCTS gains 0.24%, and 700 of 720 of MCTS’s first results are merely the warm start it was handed. The studied selection rule locks deterministically onto the first-expanded child, keeping its trials correlated while restarts draw gains from the tails; the causal link to makespan remains an inference. A structural map locates where the tree stops paying: restarts win on sparse irregular workflows, no difference is detectable on regular layered ones, and dense ones leave no room to improve. Swapping the rule for textbook UCT removes most of the deficit (−0.26%-0.26\%, 95% CI [−0.71%,+0.23%][-0.71\%,+0.23\%]) without reversing its sign. Results are confined to a controlled synthetic domain (N∈8,16,32N∈\8,16,32\ tasks, 2–8 processors, budgets up to 2048); we make no claim about larger budgets. 1 Introduction A Monte Carlo tree search (MCTS) builds a search tree incrementally and uses statistics collected at each node to decide where to search next; it is a recurring proposal for scheduling directed acyclic graph (DAG) workflows. The appeal is clear: at each step the ready tasks and available processors form a sequential decision, and tree search is a natural tool for such decisions. The literature reports many positive results for MCTS schedulers and their variants (Kung et al., 2022; Zhou et al., 2025). These evaluations, however, rarely include the one comparison that could refute the proposal: an equal-budget search that does not use a tree. Its absence leaves “MCTS works” ambiguous among three unrelated explanations—that the tree structure helps, that repeated randomized sampling helps, or that the warm-start heuristic, a good initial schedule handed to the search, seeds it. An equal-budget, tree-free control removes the second explanation from the list, which is the largest step available to us; it does not isolate the tree as a cause, because our MCTS arm additionally carries a warm start that the control lacks (Section 3). What we compare are therefore two complete procedures, and we ask a preregistered, falsifiable question: RQ1. In a controlled synthetic domain, and under an identical search budget, does the MCTS scheduler outperform randomized-restart list scheduling? Our answer is negative. The reusable part is how we answer it—the protocol. The contributions split into what is learned and what is usable. 1. A falsifiable protocol for budgeted search in scheduling. We pair MCTS against a randomized-restart control that consumes an identical budget, one evaluated candidate schedule per restart, and fix the evaluation in advance: the analysis plan, covering instances, tests, and the reported effect, is locked before data collection; test instances are used once for confirmatory inference; the target quantity is declared beforehand as the mean improvement over instances with positive baseline-relative headroom (H>εH> , defined as instances whose heuristic baseline our lower bound does not already certify as optimal); and an independent verifier checks the final schedule of every confirmation-stage run. 2. The preregistered negative result. At the primary budget of 2048 evaluated schedules, the main MCTS configuration is 2.88% worse than the control (95% confidence interval [−3.62%,−2.15%][-3.62\%,-2.15\%], n=72n=72). Across four structural strata with multiple-comparison correction, two are statistically significant, both favoring the control. A registered follow-up swaps that selection rule for textbook UCT in the same domain and removes most of this deficit—to −0.26%-0.26\%, 95% CI [−0.71%,+0.23%][-0.71\%,+0.23\%]—without reversing its sign (Appendix C): the magnitude belongs to the rule; the ordering does not, and the rule-robust comparison is itself a null, since the interval crosses zero and neither method is shown ahead. 3. A reusable failure taxonomy. Three patterns recur across an exploration stage and a held-out confirmation stage. Budget-monotone reversal: MCTS leads at the smallest budget, by 1.14% in exploration and 1.87% on the confirmation domain, but falls behind once the budget reaches 8, respectively 4. Structural divergence: across our four families, whether restarts win tracks edge density and irregularity—a descriptive pattern, not an isolated mechanism, since family identity is confounded with every structural attribute, namely density, irregularity and depth, at once. Restarts win on sparse, irregular DAGs; the two methods show no detectable difference on regular layered DAGs, an underpowered stratum; dense DAGs leave no room for either method to win; and exploration-stage chains point the same way, outside the confirmation domain. Saturation: by the primary budget the median improvement per added budget has fallen to zero for both methods, so within the tested ladder the reversal is not explained by stopping early; budgets beyond 2048 are untested. We do not claim that MCTS cannot help scheduling, that this implementation stands for all MCTS schedulers, or that these synthetic results carry over to production workflows. What we show is one carefully controlled instance of the question, answered no: in the single setting where we made the comparison falsifiable, the MCTS procedure did not pay for its cost, and where it falls behind is identifiable. For practitioners whose workflows look like ours—sparse, irregular, small—the taxonomy gives a starting guess of when restarts suffice; it should be revalidated on real workloads before use. For researchers proposing MCTS schedulers, the protocol is the reusable part: it can make their next positive claim falsifiable. 2 Related work List scheduling and classical baselines. HEFT and CPOP (Topcuoglu et al., 2002) and PEFT/OCT (Arabnejad & Barbosa, 2014) define the list-scheduling baseline family: greedy processor assignment along a priority order. Our control arm is deliberately built from this family’s components—minimum earliest-finish-time processor selection with deterministic tie-breaks—plus randomization, so the two arms differ in search strategy rather than in the quality of the underlying placement heuristic; the warm-start asymmetry is stated in Section 6 and is not controlled away. The wider DAG-scheduling literature spans list-scheduling heuristics and surveys (Kwok & Ahmad, 1999a; Sih & Lee, 1993; Wu & Gajski, 1990; Kwok & Ahmad, 1999b), lookahead HEFT variants (Bittencourt et al., 2010), optimal two-processor scheduling (Coffman & Graham, 1972), and community workflow suites (Coleman et al., 2022); scheduling hardness and worst-case bounds are classical (Graham, 1969; Ullman, 1975). Anytime and randomized-restart search. Our control arm is grounded in the anytime and randomized-restart tradition: randomized restarts as a boosting strategy for combinatorial search (Gomes et al., 1998; Gomes et al., 2000), optimal restart schedules for Las Vegas algorithms (Luby et al., 1993), anytime algorithms (Zilberstein & Russell, 1996), iterated local search (Lourenço et al., 2003), and greedy randomized adaptive search (Feo & Resende, 1995). This is also where our mechanism lives: independent restarts profit from the tail of the schedule distribution, which connects to the max-K-armed / extreme bandit literature, where the objective is the best single draw rather than the mean (Cicirello & Smith, 2005; Carpentier & Valko, 2014; Achab et al., 2017; Nishihara et al., 2016). That framing explains why an i.i.d. restart sampler, which keeps drawing fresh extremes, can outperform a correlated, low-diversity tree search under an equal evaluation budget. MCTS for workflow scheduling. Direct prior work includes Kung et al. (Kung et al., 2022) and a GNN-heatmap-augmented MCTS (Zhou et al., 2025); we cite these as the motivating family, and our study is an evaluation rather than a new method. A Chinese patent (CN109857532B) (State Grid Corporation of China, 2019) combines critical-path (CPOP) information with MCTS DAG scheduling; our work is an evaluation study, not a method proposal. MCTS foundations and learned variants. The studied selection rule should be read against canonical MCTS. UCT introduced UCB1-style tree selection (Kocsis & Szepesvári, 2006); Monte-Carlo evaluation with selectivity and backup is due to Coulom (Coulom, 2006); rapid action-value estimation (RAVE) (Gelly & Silver, 2011) and progressive strategies (Chaslot et al., 2008) are standard refinements; broad surveys are given by Browne et al. (Browne et al., 2012) and Swiechowski et al. (Świechowski et al., 2023). The exploration constant and randomized multiplier in Eq. (1) are far from these canonical forms, which is why we report it verbatim rather than as representative. Finite-time bandit analysis underlies the exploration term (Auer et al., 2002), and MCTS with learned models produced landmark results in Go (Silver et al., 2016; Silver et al., 2017). A large modern line couples MCTS with learned value/policy models: the MuZero family and sampled variants for large action spaces (Schrittwieser et al., 2021), Gumbel-based policy improvement (Danihelka et al., 2022), multi-agent extensions (Hao et al., 2024), and inference-time tree search for language models (Ugadiarov et al., 2026). Our study targets a heuristic-seeded, model-free scheduler, so these are context rather than baselines; we make no claim about learned MCTS. Evaluation methodology. Our protocol follows the operations-research tradition of designed computational experiments: reporting standards for heuristic comparison (Barr et al., 1995), the call to test heuristics against meaningful baselines rather than convenient ones (Hooker, 1995), and the critique of novelty claims built on uncontrolled comparisons (Sørensen, 2015). On top of that tradition we adopt preregistration with hypothesis–confirmation separation (Nosek et al., 2018). Our held-out set is used once for confirmatory inference; the append-only follow-ups in Appendices C–E reuse the same instances only as non-confirmatory evidence. We cite the reusable-holdout literature (Dwork et al., 2015) with an explicit downgrade, since our confirmatory holdout is one-shot rather than reusable. Broader concerns about reproducibility and evaluation rigor in machine learning motivate the preregistered, verifier-backed protocol we adopt (Henderson et al., 2018; Gundersen & Kjensmo, 2018). Datasets and artifacts. We use archived Pegasus workflow instances from WfCommons (WfCommons, 2023) as background reference material (Zenodo DOI 10.5281/zenodo.7865734, other-open license); all quantitative results in this paper are on our synthetic domain, whose generator is deterministic and committed. The companion artifacts for this paper are archived with DOIs: the benchmark suite, covering instance generators, scheduler arms, independent verifier, and result tables, at 10.5281/zenodo.22929494, and the evaluation audit protocol, covering the placebo standard and instrumentation contract, at 10.5281/zenodo.22930513. Notation Symbol Meaning B evaluated-search budget (candidate schedules built and evaluated) N number of tasks in a DAG instance P number of (equal-speed) processors, P∈2,4,8P∈\2,4,8\ CCRCCR communication-to-computation ratio H improvement headroom, (M0−L)/M0(M_0-L)/M_0 (unrelated to H-arm) M0M_0 per-instance best of a four-heuristic portfolio (HEFT, CPOP, PEFT, OCT) L lower bound, max⁡(Lwork,Lcp) (L_work,L_cp) ε headroom threshold (00) εinc _inc incumbent-improvement tolerance (10−910^-9) Δ per-instance relative gap, (control−mcts)/control(control-mcts)/control; Δ>0 >0 favors MCTS F finish time (Fdispatch≥FprecedenceF_dispatch≥ F_precedence) n conditional-domain sample size (72 of 96) Nv,NviN_v,N_v_i visit counts of node v and child viv_i QviQ_v_i makespan-derived value backed up at child viv_i default_Q per-instance constant (total work plus outgoing communication) rng fresh 32-bit pseudorandom draw, one per scoring c UCB1 exploration constant (c=0.7c=0.7 in Appendix C) W/T/L per-instance win/tie/loss (from the MCTS side) HL Hodges–Lehmann location estimate MDE, dzd_z minimum detectable effect; paired effect size H/R/T original implementation; reimplementation; topology-aware main arm 3 Method 3.1 The scheduler under study and two communication models We study three arms (arm: algorithm configuration) of one scheduler: our own earlier implementation, which predates this study and is kept unmodified here (the H-arm), a deterministic reimplementation proven equivalent to it within bounds (the R-arm), and a topology-aware rewrite that forms the main arm (the T-arm); these arm names carry no relation to the headroom H of Eq. (2). At each node the scheduler scores every child action and selects the argmax of score⁡(vi)=default_QQvi⋅(rngmod5)+105⋅ln⁡NvNvi,score(v_i)= default\_QQ_v_i·(rng 5)+10^5· N_vN_v_i, (1) where NvN_v and NviN_v_i are the visit counts of a node and a child, and QviQ_v_i is the makespan-derived value backed up at child viv_i, with makespan denoting the job’s finish time. The constant default_Q is per-instance: the total task execution time plus the total outgoing communication time. It also initializes a freshly expanded node, and is therefore identical across siblings. The term rng is a fresh 32-bit draw per scoring, and 10510^5 is the exploration constant as given in that implementation. An unexpanded action is scored INT_MAX so it is expanded first. We report Eq. (1) verbatim as the original, nonstandard rule, and we neither “fix” nor tune it. We have since measured the selection distribution directly (Appendix E): in the configuration we report, the value channel is inert—a zero-initialised minimum makespan makes every child’s value term diverge—so under strict-greater comparison the search locks deterministically onto the first-expanded child rather than spreading near-uniformly; the large constant and the (rngmod5)(rng 5) multiplier dominate the score only once the value channel is repaired. The main arm as an anytime search. A search state s carries the scheduled set, each task’s processor and finish time, per-processor availability, the ready set Ready⁡(s)=i:all predecessors of i are scheduledReady(s)=\i:all predecessors of i are scheduled\, and the action prefix; the legal actions are A⁡(s)=Ready⁡(s)×processorsA(s)=Ready(s)×processors. Taking action (i,p)(i,p) sets start⁡(i,p)=max⁡(avail⁡(p),maxj∈pred⁡(i)⁡(finish⁡(j)+comm⁡(j,i)))start(i,p)= (avail(p),\ _j (i)(finish(j)+comm(j,i))) and finish⁡(i,p)=start⁡(i,p)+w⁡(i,p)finish(i,p)=start(i,p)+w(i,p). One search descends from the root by Eq. (1), expands one node, completes the schedule with an earliest-finish-time rollout, and backs up visit counts and makespan statistics along the path; the incumbent is the best complete schedule seen so far. The budget B counts evaluated searches, and a warm-start replay that re-runs a full rollout consumes one of them: it is counted against B but flagged as a duplicate rather than credited as new search—which is why the arm’s B=1B=1 result is usually exactly its warm start. The main arm is seeded with a CPOP warm start, whose asymmetry we return to in Section 6. Scope of the H/R/T correspondence. R is a from-scratch reimplementation of the historical scheduler H; the two are shown to agree in a bounded, correctness sense on a restricted representable slice, namely zero-communication edges, homogeneous unit speed, non-negative integer costs with cumulative default_Q≤INT32_MAXdefault\_Q≤ INT32\_MAX, and bidirectionally consistent DAGs, with an archived per-cell parity receipt in the artifact bundle. This is behavioral parity, not performance parity: we make no runtime-equivalence claim, and the historical performance question is out of scope here. T is the topology-aware rewrite that carries the precedence-aware communication model and forms the main arm. Two communication models appear in the literature and in the code. The precedence-aware model sets each task’s start to the latest parent-arrival time, so communication respects precedence; the dispatch-delay model instead charges an edge delay at dispatch. Writing F for the resulting finish times, Fdispatch≥FprecedenceF_dispatch≥ F_precedence holds as a precondition, because the dispatch-delay model charges communication no earlier than the precedence-aware parent-arrival model does. The main table compares arms within the precedence-aware model, so the MCTS and control arms are scored under identical semantics and pairing is valid; data from the original selection formula are reported separately (Appendix B) and never shown as the main arm. 3.2 The control arm The control arm is a randomized-restart list scheduler. Each restart starts from an empty schedule and, at every step, draws one task uniformly at random from the current ready set, implemented as a Fisher–Yates shuffle of that set with the front taken, and places it on the processor of minimum earliest-finish time with deterministic tie-breaks—matching the processor rule the MCTS arm uses. It is thus a random list schedule, not one up-front permutation of all tasks. The incumbent is replaced only on strict improvement, with εinc=10−9 _inc=10^-9, and each restart consumes exactly one evaluated search, so a budget of B means B evaluated schedules for either arm. The control arm entered the preregistration only after passing four correctness gates: independent-verifier PASS, budget conservation, incumbent monotonicity, and same-seed replay determinism. 3.3 Instances and improvement headroom The generator spans six structural families, chain, fork-join, layered, critical-path-heavy, dense, and sparse-wide, with N∈8,…,128N∈\8,…,128\, three processor counts P=2,4,8P=2,4,8 at equal speed, and communication-to-computation ratio CCR∈0,0.5,2,8CCR∈\0,0.5,2,8\; it replays byte-identically under a fixed seed and covers two cost domains in the exploration stage: dyadic, meaning costs drawn from powers of two, and integer. The preregistered held-out, confirmation domain narrows this grid. It is the four-family subset, dropping chain and critical-path-heavy, with N∈8,16,32N∈\8,16,32\, P∈2,4,8P∈\2,4,8\ and CCR∈0.5,2CCR∈\0.5,2\: 96=4families×2CCR levels×12instance seeds96=4\ families× 2\ CCR levels× 12\ instance seeds, with the 12 seeds in each family–CCR block cycling through the nine (N,P)(N,P) combinations, so that grid is covered but not balanced within a block. Improvement headroom is H=M0−LM0,L=max⁡(Lwork,Lcp),H= M_0-LM_0, L= (L_work,L_cp), (2) where M0M_0 is the per-instance best of the four-heuristic portfolio (HEFT, CPOP, PEFT, OCT) and L is a lower bound taken as the larger of a work bound and a critical-path bound, not their sum; the critical-path bound ignores communication. The threshold ε=0 =0 was fixed before execution. Filtering on H conditions on baseline-relative headroom—a preregistered selection-bias disclosure—so we also report the unfiltered distribution in Appendix A. 3.4 Preregistration and statistics The confirmation-stage manifest was frozen before data collection: 96 held-out instances × 8 arm–seed configurations, comprising two registered MCTS variants × two search seeds plus four control seeds, × 12 budgets =9,216=9,216 rows; an anonymized registration record is available to reviewers. The statistical unit is the DAG instance: repeated seeds are an algorithm configuration rather than independent replicates, so each arm’s per-instance value is its mean over the registered seeds, and the sample size n=96n=96 was fixed in advance. The registered estimand is the conditional mean of Eq. (3), reported with a bootstrap percentile confidence interval from 10410^4 instance-level resamples; the registered confirmatory test is a two-sided paired sign-flip permutation test within each family stratum, with Wilcoxon as reference, Holm-corrected across the four strata, with Hodges–Lehmann (HL) location estimates. These are two distinct objects rather than one: the pooled −2.88%-2.88\% is the descriptive main estimand, and its uncertainty is expressed by the bootstrap interval, whereas the confirmatory decision is made per family stratum by the Holm-corrected permutation test rather than on the pooled number itself; we report both and do not read the pooled interval as a significance test. The Holm family is the four preregistered family strata as declared, which matters once the headroom filter empties one of them: the dense stratum contributes no test and enters the correction with p=1p=1, so the correction divides over m=4m=4 rather than over the three estimable strata—a conservative choice fixed by the registered analysis code, not chosen after the fact. The independent verifier is a separate implementation that consumes only an instance definition and an emitted schedule; it shares no scheduling code with either arm and takes no part in generating candidates. A void-run protocol separates harness crashes from scientific outcomes; there were zero void runs at the confirmation stage. Upon acceptance we will release the registration record, the instance generator, the verifier, and the per-cell parity receipts. The target quantity is the conditional mean [Δ∣H>ε,domain],Δ=control−mctscontrolper instance,E\! [\, H> ,\ domain\, ], = control-mctscontrol\ per instance, (3) with Δ>0 >0 favoring MCTS. Preregistered arms. The frozen manifest declared two MCTS arms—the main arm, using the precedence-aware model, and an auxiliary arm—and asserted that both ran under the control arm’s communication semantics. That assertion was wrong for the auxiliary arm, which is a dispatch-delay arm, so a paired Δ against the precedence-aware control would cross communication models and would measure a change of units rather than a difference in scheduling quality. The mismatch was identified while the confirmation-stage executor was being written—its arm-aware verifier already applies dispatch-delay semantics to that arm, and it was committed before the run produced any outcome—so the exclusion criterion is mechanical and was fixed before any result existed. The auxiliary arm was nonetheless executed exactly as registered: its rows are part of the 9,216 and its within-model statistics are in the released artifact. The main table reports the main arm only, and we log this as a registered erratum. 4 Results Data. Stage 1, the exploration stage, is research-only and excluded from the main table; it comprises 77,760 rows across nine arms: seven MCTS variants plus two controls, one on the integer-cost cells of the exploration matrix and one on its dyadic-cost cells, the latter being the dyadic control referred to below. Under the registered no-deletion rule, 3,351 adverse rows—outside the target domain or unfavourable to our own hypothesis—were retained rather than dropped. Stage 2, the main table, comprises 9,216 arm rows with zero void runs (a void run is a harness failure rather than a scientific outcome); the 96 recorded runs beyond the arm rows are the one-per-instance Portfolio-4 baseline and headroom computation. All 768 of 768 final schedules at the primary budget pass the independent verifier. Baselines are the per-instance Portfolio-4 best (HEFT/CPOP/PEFT/OCT). Main result. On the conditional domain, ⁡[Δ∣H>ε]=−0.0288E[ H> ]=-0.0288 with 95% CI [−0.0362,−0.0215][-0.0362,-0.0215] and n=72n=72; win/tie/loss =7/7/58=7/7/58. Of the 96 held-out instances, 72 pass the preregistered H>εH> filter; the 24 that do not are all dense-family cells with H=0H=0, where the portfolio best already meets the lower bound, so the conditional domain excludes the dense family by construction. After Holm correction, two strata are significant, both favoring the control: fork-join, with p≈1.2×10−7p≈ 1.2× 10^-7, and sparse-wide, with p≈4.8×10−7p≈ 4.8× 10^-7; the layered stratum is not significant, with Holm p=1.0p=1.0 and raw permutation p=0.9613p=0.9613. Table 1 gives the per-stratum statistics, and Figure 1 shows the same estimates with their confidence intervals. Table 1: Per-stratum statistics for the main comparison (main MCTS arm vs. control, precedence-aware model, B=2048B=2048). W/T/L == MCTS win/tie/loss per instance; HL == Hodges–Lehmann estimate. Stratum n W/T/L mean Δ HL Holm sig. fork-join 24 0/0/24 −0.0436-0.0436 −0.0435-0.0435 yes (p≈1.2×10−7p≈ 1.2× 10^-7) sparse-wide 24 0/2/22 −0.0426-0.0426 −0.0402-0.0402 yes (p≈4.8×10−7p≈ 4.8× 10^-7) layered 24 7/5/12 −0.0002-0.0002 −0.0018-0.0018 no (p=1.0p=1.0) dense 0 — — — — (n=0n=0) pooled 72 7/7/58 −0.0288-0.0288 −0.0277-0.0277 — Figure 1: Per-stratum effect, shown as the Hodges–Lehmann estimate with 95% CI, for the main comparison. Fork-join and sparse-wide exclude zero on the control’s side; layered spans zero; the pooled estimate is −2.88%-2.88\%. Negative favors the control. Figure 2: Budget-monotone reversal (exploration stage, 720 cell–seed pairs pooled). The paired gap between the MCTS arm and the control, Δ=(control−MCTS)/control =(control-MCTS)/control in the sign convention of Eq. (3), averaged per budget, starts at +1.14%+1.14\%, with MCTS ahead almost entirely as a warm-start effect, at B=1B=1, crosses zero near B=8B=8, and settles at −0.46%-0.46\% by B=2048B=2048. Positive values favor MCTS. Budgets beyond 2048 are not tested. Is the deficit a budget artifact? Three exploration-stage checks say no, within the tested ladder; complete exclusion at larger budgets remains open work. First, the MCTS anytime curve is flatter than the control’s: self-improvement from B=1B=1 to B=2048B=2048 is 0.24% for MCTS versus 1.85% for the control, and the paired gap itself reverses from +1.14%+1.14\% to −0.46%-0.46\% over the same range (Figure 2). The confirmation domain shows the same reversal, earlier and larger: the paired gap there is +1.87%+1.87\% at B=1B=1 and has already turned negative by B=4B=4, reaching −2.88%-2.88\% at the primary budget. The endpoint magnitudes differ between the two stages because the pools differ—the exploration pool mixes in families that tie exactly and the dyadic cost domain, whereas the confirmation domain is restricted to four families of which two are headroom-rich—so we treat only the confirmation figure as the result. Second, MCTS has plateaued by B=2048B=2048: for the MCTS arm the median per-cell gain over the final budget doubling, from 1024 to 2048, is zero, and all but two cells gain less than 0.06%; one of the two exceptions is a large layered gain. The control has not fully plateaued—a minority of its cells still gain under a percent, which only widens its lead—so within the tested ladder the reversal is not explained by stopping too early (Figure 3). Third, we found no sub-domain in which more budget closes the gap; this is a search that failed to find one, not a proof that none exists beyond B=2048B=2048. At n=72n=72 the minimum detectable effect, with paired SD 3.23%, α=0.05α=0.05, and power 0.8, is 1.07%, well below the observed 2.88%; the paired effect size is dz≈−0.9d_z≈-0.9, with the bootstrap CI excluding zero. Figure 3: Fraction of cells that improve over their B=1B=1 result, versus budget (exploration stage, per arm). The MCTS arm barely rises, with about 4% of cells improving even at B=2048B=2048, whereas the randomized-restart control reaches roughly 45%; the dyadic control, which is the same control arm on the exploration matrix’s dyadic-cost cells, and the original selection formula of Eq. (1) fall in between. More budget buys the tree almost nothing. Mechanism, with selection measured and makespan attribution still inferred. The paired deficit decomposes into a start-point difference and a learning-rate difference. At B=1B=1, the MCTS arm’s +1.14%+1.14\% lead is almost entirely its CPOP warm start: on 720 exploration instances, 700 of the B=1B=1 incumbents are the warm start—the tree has not searched yet. By B=2048B=2048 the control overtakes with a 7.8× larger endpoint self-improvement, 1.85% versus 0.24%, from a worse start; the two percentages are measured from different starting points and are not commensurable learning rates, which is why the quantity we report as the result is the endpoint gap rather than their ratio. We now measure the selection distribution directly (Appendix E); its causal role in the makespan deficit remains an inference rather than a measured quantity. In the configuration we report the value channel is inert—a zero-initialised minimum makespan makes every child’s value term diverge—so under strict-greater comparison the search locks deterministically onto the first-expanded child, with mean top-1 visit share 0.860.86 rising toward 1.01.0 as the root fills, and normalized selection entropy 0.290.29 against 1.001.00 for a value-repaired canary. Successive tree samples stay correlated and carry little new information not because the tree explores near-uniformly but because it barely explores at all, whereas independent restarts keep drawing i.i.d. samples whose extremes pay off. This value-blind, first-child lock-in is the same degeneracy family as the rank-00 selection signature of the original implementation, whose value is 0.820.82; throughout, “original implementation” denotes the earlier MCTS scheduler we wrote before this study and reproduce here verbatim. The degeneracy is a tree with depth but no breadth, the opposite of one that “concentrates too much” by over-exploiting a well-estimated value. The original selection formula of Eq. (1) was additionally run in the exploration stage’s dyadic-cost domain; those raw counts are reported separately in Appendix B and are never shown as the main arm. 5 Failure taxonomy and selector Three reusable patterns locate where the tree stops paying; this is contribution (i). (a) Budget-monotone reversal: the MCTS advantage decays with budget and reverses by B≥8B≥ 8 in the exploration scan, and by B≥4B≥ 4 on the confirmation domain. Where the crossing falls is a property of the seeding protocol, since only the MCTS arm is warm-started; the budget-robust content of this pattern is the difference in slope, not the crossing budget. (b) Structural divergence: across our four families, whether restarts win tracks edge density and irregularity—the losing families, sparse-wide and fork-join, are low-density and irregular, while the layered family, which consists of three complete bipartite layers at depth 3 with E/N≈3.4E/N≈ 3.4, shows no detectable difference. Family identity is confounded with density, irregularity and depth at once, so this describes which cells lose rather than isolating a causal effect of density. Dense DAGs leave no headroom to win, and chains behave alike in exploration-stage data (Figure 4). (c) Saturation: the median per-cell slope over the final budget doubling is zero on both arms, so within the tested ladder the reversal is not explained by stopping early. Figure 4: Self-improvement over the warm start at B=2048B=2048, by family. The control extracts 33–4×4× more than MCTS on every family that has any headroom, namely fork-join, sparse-wide, and layered; chains and dense DAGs have none. The 33–4×4× figure is per family; pooled across all families the ratio is the larger 7.8×7.8× reported in the main text, because pooling aggregates the per-family gains. Mapped to the preregistered strata with evidence levels: sparse-wide and fork-join are the restart-favoring region, confirmed at the confirmation stage and significant after Holm; layered is the no-detectable-difference region, established at the confirmation stage with HL CI [−0.7%,+0.7%][-0.7\%,+0.7\%] and stratum MDE ≈1.2%≈ 1.2\%—that is, underpowered rather than proven equal; dense DAGs are a ceiling region rather than a search outcome, since all 24 held-out dense instances have H=0H=0, so our lower bound already certifies the Portfolio-4 baseline as optimal there, and separately the two arms are observed to tie on these cells (Appendix A); and chains show no difference in exploration-stage data only—the chain family lies outside the confirmation domain, so this cell of the taxonomy is unconfirmed and untested. Selector. For practitioners under equal budget: use randomized restarts outright on low-density irregular structures; expect no detectable difference on regular bipartite structures; and where the heuristic baseline already meets the lower bound, as on our dense DAGs, there is no headroom for either method to exploit and on our cells the two arms tie. For researchers, the transferable part is the protocol—an equal-budget control, an independent verifier, and a conditional estimand fixed in advance. 6 Limitations Domain boundary, primary. All conclusions are confined to the controlled synthetic domain, with integer costs and a unit-speed executor contract. We do not extrapolate to production workflows; heterogeneous-placement criteria are structurally unsatisfiable in this domain, and migrating there is registered as open work. Asymmetric warm start. The main-table MCTS arm carries a CPOP warm start that the control arm lacks. The B=1B=1 lead is almost entirely that warm start; the B=2048B=2048 deficit is the control achieving a 7.8× larger endpoint self-improvement from a worse start. We state the two effects separately wherever both appear. The asymmetry is conservative for the conclusion we draw, which we verify directly rather than assume. Under a preregistered symmetric protocol that hands the control the same CPOP warm start, the deficit persists and, if anything, widens, from −2.88%-2.88\% to −2.93%-2.93\%, while the crossing budget of Figure 2 moves; at the primary budget the warm start is worth a mean +0.05%+0.05\% to the control (Appendix D). We therefore do not rest this on an a-priori argument that symmetrizing could only widen the gap. Warm start is also not the arms’ only difference: tree structure, and the tree’s freedom over processor placement, remain uncontrolled. This experiment addresses the warm-start asymmetry specifically rather than isolating the tree. It is reported as append-only evidence and modifies no frozen confirmation number. Layered-family density cap. The layered family is a three-layer complete bipartite graph with E=O⁡(N2)E=O(N^2) growth; the main-table instances, with N∈8,16,32N∈\8,16,32\, have E/N∈[1.0,6.2]E/N∈[1.0,6.2], and the N=32N=32 value of 6.2 slightly exceeds the real-workflow band, which has E/N∈[2,5]E/N∈[2,5]; this is a genuine consequence of the family’s construction, not a generator artifact. The true artifact, E/N≈4444E/N≈ 4444, appears only in the diagnostic ladder at N≥103N≥ 10^3 and is outside the main table. Scope of comparison. Our claim is a preregistered equal-budget comparison against the list-scheduling family, HEFT, CPOP, PEFT, and OCT, not a comparison against state-of-the-art learning-guided schedulers; extending the protocol to learning-guided baselines is future work. Is this just a broken MCTS? Two results answer this question before it is asked—this is the question the registered follow-up arm of the abstract was designed for. Replacing the studied rule with canonical UCT in the same domain removes most of the deficit—from −2.88%-2.88\% to −0.26%-0.26\% (95% CI [−0.71%,+0.23%][-0.71\%,+0.23\%]; Appendix C)—so the magnitude is rule-specific; yet the direction survives, since under an equal budget canonical UCT still does not overtake independent restarts. With that shield stated, the provenance question remains fair: the rule of Eq. (1) is nonstandard—a 10510^5 exploration constant and a randomized exploitation multiplier—and one might ask whether we have merely tested a broken implementation. We wrote that rule ourselves, for earlier scheduling work, and we report it here verbatim rather than quietly repairing it: it predates this study, it was not constructed for this comparison, and neither arm was tuned after the protocol was registered. Our own authorship of the rule is precisely why provenance cannot settle the question, so we answer it with two experiments. In separate clean-room work, documented in the released bundle, a textbook UCT written from the standard specification without consulting the original implementation, using a standard exploration constant and an earliest-finish-time warm start, did not reproduce the selection degeneration, and produced genuine search improvement rather than restart-style gains. A preregistered, same-domain standard-UCT arm has since been run (Appendix C): the pooled 95% CI [−0.71%,+0.23%][-0.71\%,+0.23\%] places any UCT advantage at no more than +0.23%+0.23\% while leaving open a disadvantage as well. The honest reading of our headline number is therefore that it belongs to the original rule, while the rule-robust statement is the weaker one—no selection rule we tested beats equal-budget restarts in this domain. We do not claim that standard UCT is significantly worse than the control. Three further registered limitations are stated here. Performance-budget gates—wall-clock and memory ceilings per arm—were registered but not executed, so our equal-budget claim covers evaluated schedules only. An earlier real-workflow signal from a Python-era prototype is deprecated rather than refuted: it is excluded from every number in this paper, and we make no claim either way about it. Finally, several exploration-stage sub-pools are small enough that we describe them qualitatively instead of testing them. A fourth registered item, the selection-artifact experiment, has since been executed (Appendix E): it measures the selection distribution directly—the causal step from that distribution to the makespan deficit remains an inference—and, honoring the preregistered honest-reporting clause, reverses its predicted direction, since the reported rule concentrates its trials on the first-expanded child rather than spreading them near-uniformly. 7 Conclusion We asked a simple question: given the same search effort, does an MCTS scheduler beat a method with no tree at all? On our controlled synthetic domain the answer is no. At the preregistered budget the MCTS arm finished 2.88% behind a randomized-restart list scheduler, and its only early advantage was a warm start it was handed—not anything the tree found. Two selection rules under one locked protocol give the same answer: the production rule loses outright, and textbook UCT, run as a registered follow-up on the same domain, closes most of the gap but does not reverse it. The finding is deliberately narrow: one domain, one implementation, budgets up to 2048. What travels is the method—an equal-budget control with no tree, an analysis plan locked before we saw the data, an independent checker on every final schedule, and a target measure fixed in advance. Together they turn “does MCTS help here?” from an untestable intuition into a question that can be answered, and here answered no. For practitioners under a fixed search budget, the taxonomy says where a handful of random restarts is the better buy and where the choice is immaterial; on our domain it contains no region in which the tree pays for itself. For researchers, the next MCTS-scheduling proposal can borrow the protocol and state a claim that could, in principle, be proven wrong—which is the first thing a useful claim should be able to do. Appendix A Unfiltered distribution (preregistration obligation) Per the frozen estimand clause, we report the unfiltered distribution alongside the conditional one, on all 96 held-out cells, at B=2048B=2048 with arm means over seeds and Δ=(control−MCTS)/control =(control-MCTS)/control; see Table 2. Table 2: Unfiltered distribution on the full 96 held-out cells. Family n mean Δ range fork-join 24 −4.36%-4.36\% [−9.21%,−0.52%][-9.21\%,-0.52\%] sparse-wide 24 −4.26%-4.26\% [−11.30%,0.00%][-11.30\%,0.00\%] layered 24 −0.02%-0.02\% [−4.81%,+6.81%][-4.81\%,+6.81\%] dense 24 0.00%0.00\% [0.00%,0.00%][0.00\%,0.00\%] all (unfiltered) 96 −2.16%-2.16\% — The unfiltered pooled mean, −2.16%-2.16\%, is closer to zero than the conditional one, −2.88%-2.88\%, because the 24 dense cells all have H=0H=0, where the portfolio best equals the lower bound, and contribute exact ties. Filtering on H conditions on baseline-relative headroom: the headroom distribution differs by CCR, with median H=0.126H=0.126 at low CCR versus 0.3900.390 at high CCR and ranges [0,0.42][0,0.42] and [0,0.57][0,0.57], and high-CCR instances—where scheduling has the most room—are also where the control’s mean advantage is largest in our cells. That last point is a descriptive reading of the per-cell table, not a CCR-stratified test, which we do not run. Appendix B Original selection formula in the dyadic domain (exploration-stage raw counts) The rule of Eq. (1) was run in the exploration stage’s dyadic-cost domain and reported separately, never as the main arm. It improves on its own start on 224 of 720 instances, versus 221 of 720 for the dyadic control—essentially level. These are raw counts that we do not test, and we read the three-instance difference as no advantage in either direction. Both counts are on the dyadic-cost exploration pool and are not directly comparable to the integer-cost improvement fraction of the main arm in Figure 3, which is a different cost domain and instance pool. Appendix C Same-domain standard-UCT arm (registered follow-up, completed) Section 6 registered an in-domain standard-UCT arm as follow-up work, to turn the “broken MCTS?” rebuttal from clean-room, indirect, into same-domain, direct, evidence. That arm has since been run under a preregistered protocol. We report it here as append-only evidence: it introduces no change to any frozen confirmation-stage number, criterion, or conclusion in the main text. Protocol. We replace the original selection rule of Eq. (1) with a textbook UCT/UCB1 selection, with exploration constant c=0.7c=0.7, and hold everything else in the main arm fixed: the CPOP warm start, the earliest-finish-time rollout, the precedence-aware communication model, the single-unvisited-action-per-evaluated-search expansion, and the evaluated-search budget ladder. Rewards are normalized before they enter UCB1: a rollout’s reward is min⁡(1,warm-start makespan/rollout makespan)∈(0,1] (1,\ warm-start makespan/rollout makespan)∈(0,1] and the exploitation term is the mean of those rewards, so c=0.7c=0.7 is applied on the [0,1][0,1] scale for which it is the textbook default rather than to a raw makespan. Because the ratio is clipped at 11, every rollout at least as good as the warm start receives the maximal reward 11: the exploitation signal saturates above the warm-start makespan, so a schedule that beats the warm start earns no higher reward than one that merely ties it. This arm is therefore textbook UCT selection with this specified clipped reward, not a claim that a single reward shape or exploration constant represents all of standard UCT; we report it as one concrete, canonical selection rule rather than as a universal repair. The arm is scored on the same held-out instances and by the same independent verifier as the main comparison. The formal run comprises 6,9126,912 rows, that is 9696 instances × 12 budgets × two UCT search seeds plus four control seeds, with zero verifier failures; the UCT side therefore carries two seeds against the control’s four, making its per-instance mean the noisier of the two and widening the interval below. Because this arm reuses the same 96 held-out instances, it is a second use of a one-shot holdout: we report it as append-only evidence, its Holm correction is internal to this appendix, and we do not treat its p-values as confirmatory. Result. At the primary budget B=2048B=2048 on the conditional domain, H>εH> with n=72n=72, standard UCT and the randomized-restart control are not distinguishable at α=0.05α=0.05: the paired estimand Δ=(control−uct)/control =(control-uct)/control has mean −0.26%-0.26\% with bootstrap 95% CI [−0.71%,+0.23%][-0.71\%,+0.23\%], Hodges–Lehmann −0.24%-0.24\%, and UCT win/tie/loss =14/25/33=14/25/33, and no family stratum survives Holm correction (Table 3, Figure 5); note that the bootstrap intervals in Table 3 are not Holm-corrected while the p-values are, so a stratum interval that excludes zero, as fork-join’s does, need not be significant after correction. This is a bounded non-rejection rather than an equivalence result: we ran no equivalence test, and what the interval supports is that a UCT advantage beyond +0.23%+0.23\%, or a disadvantage beyond 0.71%0.71\%, lies outside the 95% interval. The stratum directions are heterogeneous—fork-join −0.71%-0.71\%, sparse-wide −0.69%-0.69\%, layered +0.63%+0.63\%; the dense family has n=0n=0 under the headroom filter and, as in the main analysis, still enters the Holm family with p=1p=1. Unlike the original rule, whose anytime curve is nearly flat, standard UCT does improve with budget (Figure 6); it simply does not improve enough to overtake independent restarts under an equal budget. Reading. Textbook UCT selection does not rescue MCTS in this domain under an equal-budget protocol, and the comparison separates two questions that a single headline number conflates. Most of the magnitude of the observed deficit is attributable to that selection rule: swapping in canonical UCT moves the pooled estimate from −2.88%-2.88\% to −0.26%-0.26\%, which is consistent with reading the selection collapse as rule-specific. The direction of the conclusion is not attributable to it: canonical UCT still does not beat equal-budget independent restarts, and the interval places any UCT advantage at no more than +0.23%+0.23\%. We therefore claim neither that standard UCT is significantly worse than the control—the pooled interval spans zero and no stratum passes correction—nor that a single-cause “broken rule” account explains away the negative direction. The registered arm upgrades the “Is this just a broken MCTS?” discussion of Section 6 from clean-room, indirect, to same-domain, direct, evidence, without altering any frozen result. Table 3: Same-domain standard-UCT arm vs. randomized-restart control (precedence-aware model, B=2048B=2048, conditional domain H>εH> ). Δ=(control−uct)/control =(control-uct)/control; W/T/L == UCT win/tie/loss per instance; HL == Hodges–Lehmann; CI == instance-bootstrap percentile with 10410^4 draws; p == paired sign-flip permutation, Holm-corrected across the four family strata, the empty dense stratum entering with p=1p=1 as in the main analysis. Stratum n W/T/L mean Δ HL bootstrap 95% CI Holm p fork-join 24 2/11/11 −0.71%-0.71\% −0.26%-0.26\% [−1.358%,−0.082%][-1.358\%,-0.082\%] 0.1740.174 sparse-wide 24 2/9/13 −0.69%-0.69\% −0.94%-0.94\% [−1.318%,+0.020%][-1.318\%,+0.020\%] 0.2010.201 layered 24 10/5/9 +0.63%+0.63\% +0.11%+0.11\% [−0.264%,+1.603%][-0.264\%,+1.603\%] 0.4060.406 dense 0 — — — — — pooled 72 14/25/33 −0.26%-0.26\% −0.24%-0.24\% [−0.706%,+0.229%][-0.706\%,+0.229\%] — −1.5-1.5−1-1−0.5-0.5000.50.5111.51.5pooledfork-joinsparse-widelayeredΔ=(control−UCT)/control =(control-UCT)/control (%), mean with bootstrap 95% CI Figure 5: Same-domain standard-UCT arm: per-stratum mean Δ with bootstrap 95% CI, and the pooled estimate (B=2048B=2048, H>εH> ). Negative favors the control. The fork-join interval lies entirely below zero but does not survive Holm correction, with p=0.174p=0.174; the sparse-wide, layered and pooled intervals cross zero; no stratum passes correction. The bootstrap intervals shown are not Holm-corrected whereas the p-values are, so an interval that excludes zero does not by itself imply significance after correction. 124816326412825651210242048320320322322324324326326328328evaluated-search budgetmean makespan (lower is better)standard UCTcontrol Figure 6: Anytime curves of the same-domain standard-UCT arm and the control, as pooled mean makespan over all 96 held-out cells—including the 24 zero-headroom dense cells, a wider pool than the n=72n=72 conditional domain of Table 3—per budget, with x giving log2 _2 budget. Standard UCT descends with budget—a genuine search improvement, in contrast to the original rule’s nearly flat curve—but the control descends slightly faster and edges ahead from about B=8B=8 onward, ending marginally lower, that is better. The two curves finish within 0.2%0.2\% of each other, consistent with the non-rejection at the primary budget. Appendix D Symmetric warm-start control arm (registered follow-up, completed) Section 6 named the asymmetric warm start as an uncontrolled difference between the arms—not the only one, since tree structure and the tree’s freedom over processor placement also differ—and argued it was conservative for our conclusion, registering a symmetric-correction experiment as an append-only supplement. That experiment has since been run under a preregistered protocol. We report it here as append-only evidence: it introduces no change to any frozen confirmation-stage number, criterion, or conclusion in the main text. Protocol. The warm-start control is the frozen control arm with exactly one change: the production CPOP schedule is prepended as evaluated search #1\#1, after which the remaining B−1B-1 evaluated searches are the same uniform-random restarts, minimum earliest-finish-time processor selection, and strict-improvement incumbent rule as the frozen control. This mirrors the main arm’s accounting, under which a warm-start replay is counted against the budget rather than credited as new search, and on the exploration matrix 700700 of 720720 of the B=1B=1 incumbents are that warm start. The CPOP schedule is the production baseline, byte-identical to the warm start already carried by the main arm and by the standard-UCT arm of Appendix C. Everything else—held-out instances, seeds, independent verifier, precedence-aware model, and the budget ladder—is held fixed. We report three paired comparisons on the same held-out cells at the primary budget: a reproduction check, comparing the main arm with the empty-start control, which must reproduce the frozen headline; the primary symmetric comparison, comparing the main arm with the warm-start control; and a secondary control-versus-control comparison, warm-start versus empty-start, that isolates what the warm start is worth at the primary budget. Reproduction. Re-running the main arm and the empty-start control from scratch with the committed binaries and the frozen manifest reproduces the confirmation-stage headline. The conditional estimand is −0.0288269-0.0288269 against the frozen −0.0288269-0.0288269, an agreement within 5×10−105× 10^-10, with the same n=72n=72, the same win/tie/loss of 7/7/587/7/58, and the same per-stratum means, fork-join −4.36%-4.36\%, sparse-wide −4.26%-4.26\%, layered −0.02%-0.02\%; the permutation p-values agree to Monte-Carlo error, with layered 0.9610.961. This corroborates the frozen number; it does not change it. Result. Under the symmetric protocol the deficit persists and, if anything, widens (Table 4; Figure 7). The primary estimand Δsym _sym—the gap of the main arm relative to the warm-start control—has mean −2.93%-2.93\% with bootstrap 95% CI [−3.67%,−2.19%][-3.67\%,-2.19\%], Hodges–Lehmann −2.79%-2.79\%, win/tie/loss 4/9/594/9/59, and n=72n=72, against −2.88%-2.88\% for the asymmetric baseline. Both structured strata remain significant after Holm correction and favor the control, with fork-join −4.36%-4.36\% and sparse-wide −4.26%-4.26\%; the layered stratum is again not significant, at −0.17%-0.17\% with Holm p=1p=1. The control-versus-control comparison explains why the two protocols nearly coincide: at the primary budget the CPOP warm start is worth a mean +0.05%+0.05\% to the control, with 95% CI [0%,+0.12%][0\%,+0.12\%], and it is worth exactly nothing on 6969 of 7272 cells, because independent restarts have already found schedules at least as good as CPOP; the three cells where it helps at all are layered. Reading. Removing the warm-start asymmetry confirms that it was conservative for the conclusion. Handing the control the same CPOP warm start does not rescue the main arm; it moves the deficit from −2.88%-2.88\% to −2.93%-2.93\%. The anytime view (Figure 8) makes the mechanism visible: the main arm’s curve is nearly flat, its search barely improving on the warm start it was handed, whereas both control curves descend steeply with budget. The warm-start control starts below the empty-start control—the CPOP head start—but the two converge by the primary budget, and both finish well below the main arm. The deficit is therefore a property of what the tree search does with its budget rather than of which arm was seeded. Table 4: Symmetric warm-start comparison: main arm vs. the CPOP-warm-started control (precedence-aware model, B=2048B=2048, conditional domain H>εH> ). Δsym=(warm-start control−main arm)/(warm-start control) _sym=(warm-start control-main arm)/(warm-start control); W/T/L == main-arm win/tie/loss per instance; HL == Hodges–Lehmann; CI == instance-bootstrap percentile with 10410^4 draws; p == paired sign-flip permutation with 10410^4 draws, Holm-corrected across the four family strata, the empty dense stratum entering with p=1p=1 as in the main analysis. Negative favors the control. Stratum n W/T/L mean Δsym _sym HL bootstrap 95% CI Holm p fork-join 24 0/0/24 −4.36%-4.36\% −4.35%-4.35\% [−5.35%,−3.39%][-5.35\%,-3.39\%] <10−3<10^-3 sparse-wide 24 0/2/22 −4.26%-4.26\% −4.02%-4.02\% [−5.46%,−3.14%][-5.46\%,-3.14\%] <10−3<10^-3 layered 24 4/7/13 −0.17%-0.17\% −0.21%-0.21\% [−0.95%,+0.70%][-0.95\%,+0.70\%] 1.01.0 dense 0 — — — — — pooled 72 4/9/59 −2.93%-2.93\% −2.79%-2.79\% [−3.67%,−2.19%][-3.67\%,-2.19\%] — −6-6−5-5−4-4−3-3−2-2−1-10011pooledfork-joinsparse-widelayeredΔsym _sym (%), mean with bootstrap 95% CI Figure 7: Symmetric warm-start comparison: per-stratum mean Δsym _sym with bootstrap 95% CI, and the pooled estimate (B=2048B=2048, H>εH> ). Negative favors the control. The fork-join and sparse-wide intervals lie entirely below zero and survive Holm correction; the layered interval crosses zero. The pooled estimate −2.93%-2.93\% is marginally more negative than the asymmetric baseline −2.88%-2.88\%. 124816326412825651210242048240240245245evaluated-search budgetmean makespan (lower is better)MCTS main armcontrol (empty start)control (CPOP warm start) Figure 8: Anytime curves of the main arm, the empty-start control, and the CPOP-warm-started control, as pooled mean makespan over the n=72n=72 conditional domain per budget, with x giving log2 _2 budget. The main arm is nearly flat—its search barely improves on the warm start—while both controls descend with budget. The warm-start control starts below the empty-start control, reflecting the CPOP head start, but the two converge by the primary budget, and both finish well below the main arm. Symmetrizing the warm start does not change the endpoint ordering. Appendix E Selection-distribution measurement (registered follow-up, completed) Section 6 registered a selection-artifact experiment—a direct measurement of the tree’s selection distribution—as follow-up work, noting that until it was run the mechanism behind the deficit remained a hypothesis. That experiment has since been run under a preregistered protocol. We report it here as append-only evidence: the selection distribution is orthogonal to makespan, so this section introduces no change to any frozen confirmation-stage number, criterion, or conclusion in the main text; it measures the selection distribution directly, while the causal step from that distribution to the makespan deficit remains an inference rather than a measured quantity. Protocol. We instrument the main arm’s selection step with a probe that, at fixed checkpoints, records the visit-count histogram over the root’s children and derives two quantities: the normalized selection entropy Sroot=−∑ipilogpi/logbS_root=- _ip_i p_i/ b, where pip_i is child i’s visit share and b is the branch width, so Sroot=1S_root=1 is uniform, and the top-1 visit share. We run the probe on a frozen subset of the confirmation domain, 1212 instances with seeds 7,42\7,42\ and budgets 256,2048\256,2048\, against two arms: the main arm exactly as reported, and a value-repaired canary that restores a finite value initialization. The subset and the read-out criteria were fixed before data collection. All 9696 runs completed with zero failures; raw per-run records and the entropy-trajectory figure are in the released bundle. Result. The measurement reverses the direction the preregistration predicted, and we report it as registered. Far from spreading its trials, the reported rule concentrates them: its late-stage normalized entropy is 0.290.29 and its mean top-1 visit share is 0.860.86, rising toward 1.01.0 as the root fills, and it is near-uniform, with Sroot>0.95S_root>0.95, on none of the 4848 late-stage cells, that is 0/480/48. The value-repaired canary is the near-uniform arm instead, with Sroot=1.00S_root=1.00 and top-1 ≈1/b≈ 1/b, near-uniform on 48/4848/48; the two arms’ entropies separate by a paired mean of +0.71+0.71 over 48/4848/48 cells. Reading the visit histograms in child-creation order, the reported arm’s most-visited child is the first-expanded one in 48/4848/48 late-stage runs—a deterministic first-child lock-in—whereas the canary’s mass is scattered across creation indices. The concentration cross-checks against the original implementation’s rank-00 selection signature: rank-00 share 0.800.80 for the reported arm versus 0.280.28 for the canary, consistent with the top-1 shares above (Table 5). Mechanism. The reported arm’s value term is default_Q/Qvidefault\_Q/Q_v_i; a zero-initialized minimum makespan sets Qvi=0Q_v_i=0 on first evaluation, so the term diverges for every child regardless of default_Q. Under strict-greater comparison, ties among diverging scores resolve to the first child in scan order, and once the root is full the fallback score for new children lets the first-created child keep winning—hence the first-child lock-in, a value-blind concentration rather than near-uniform exploration. Repairing the value channel does not yield a healthy selector either: the exploitation term is then of order 1010 while the 10510^5 exploration constant makes the exploration term of order 10410^4, so exploration dominates and the choice reverts to near-uniform. Both regimes are consistent with the nearly flat anytime curve and the 0.24%0.24\% self-improvement: added budget buys the tree almost nothing because it either barely explores or explores without exploiting. Reading. The selection collapse behind the headline deficit is now measured, not conjectured; the causal step from that collapse to the makespan deficit itself remains an inference. Direct measurement shows the reported rule does not degenerate toward near-uniform choice; it collapses onto a single, value-blind branch, so its repeated trials are correlated and carry little new information. This revises the preregistered near-uniform conjecture into a measured first-child lock-in rather than leaving the earlier reading unchanged, and it leaves every frozen number untouched. Table 5: Selection-distribution measurement: the reported main arm vs. a value-repaired canary (frozen confirmation-domain subset, 9696 runs). SrootS_root: normalized selection entropy (11 == uniform); top-1: largest child visit share; near-uniform: fraction of late-stage cells with Sroot>0.95S_root>0.95; first-child: fraction whose most-visited child is the first-expanded one; rank-00: the original implementation’s cross-check share. Arm SrootS_root (late) top-1 (late) near-uniform first-child rank-00 Reported main arm 0.290.29 0.860.86 0/480/48 48/4848/48 0.800.80 Value-repaired canary 1.001.00 ≈1/b≈ 1/b 48/4848/48 scattered 0.280.28 References Achab et al. (2017) Mastane Achab, Stéphan Clémençon, Aurélien Garivier, Anne Sabourin, and Claire Vernade. Max K-armed bandit: on the ExtremeHunter algorithm and beyond. In Machine Learning and Knowledge Discovery in Databases (ECML PKDD), Part I, volume 10535 of Lecture Notes in Computer Science. Springer, 2017. doi: 10.1007/978-3-319-71246-8_24. Arabnejad & Barbosa (2014) Hamid Arabnejad and Jorge G. Barbosa. List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems, 25(3):682–694, 2014. doi: 10.1109/TPDS.2013.57. Auer et al. (2002) Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47, 2002. doi: 10.1023/a:1013689704352. Barr et al. (1995) Richard S. Barr, Bruce L. Golden, James P. Kelly, Mauricio G.C. Resende, and William R. Stewart. Designing and reporting on computational experiments with heuristic methods. Journal of Heuristics, 1(1):9–32, 1995. doi: 10.1007/BF02430163. Bittencourt et al. (2010) Luiz F. Bittencourt, Rizos Sakellariou, and Edmundo R. M. Madeira. Dag scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In 18th Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP), 2010. doi: 10.1109/pdp.2010.56. Browne et al. (2012) Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1–43, 2012. doi: 10.1109/tciaig.2012.2186810. Carpentier & Valko (2014) Alexandra Carpentier and Michal Valko. Extreme bandits. In Advances in Neural Information Processing Systems 27 (NIPS 2014), 2014. Chaslot et al. (2008) Guillaume M. J.-B. Chaslot, Mark H. M. Winands, H. Jaap van den Herik, Jos W. H. M. Uiterwijk, and Bruno Bouzy. Progressive strategies for Monte-Carlo tree search. New Mathematics and Natural Computation, 4(3):343–357, 2008. doi: 10.1142/s1793005708001094. Cicirello & Smith (2005) Vincent A. Cicirello and Stephen F. Smith. The max K-armed bandit problem: a new model of exploration applied to search heuristic selection. In AAAI/ICAPS Workshop on Planning and Learning, 2005. Coffman & Graham (1972) E. G. Coffman and R. L. Graham. Optimal scheduling for two-processor systems. Acta Informatica, 1, 1972. doi: 10.1007/BF00288685. Coleman et al. (2022) Taina Coleman, Henri Casanova, Loïc Pottier, et al. WfCommons: A framework for enabling scientific workflow research and development. Future Generation Computer Systems, 128, 2022. doi: 10.1016/j.future.2021.09.043. Coulom (2006) Rémi Coulom. Efficient selectivity and backup operators in Monte-Carlo tree search. In Computers and Games (CG 2006), Lecture Notes in Computer Science 3846, p. 72–83, 2006. doi: 10.1007/978-3-540-75538-8_7. Danihelka et al. (2022) Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with Gumbel. In International Conference on Learning Representations (ICLR), 2022. Dwork et al. (2015) Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: preserving validity in adaptive data analysis. Science, 349(6248):636–638, 2015. doi: 10.1126/science.a9375. Feo & Resende (1995) Thomas A. Feo and Mauricio G. C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6, 1995. doi: 10.1007/bf01096763. Gelly & Silver (2011) Sylvain Gelly and David Silver. Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence, 175(11):1859–1875, 2011. doi: 10.1016/j.artint.2011.03.007. Gomes et al. (1998) Carla P. Gomes, Bart Selman, and Henry Kautz. Boosting combinatorial search through randomization. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), p. 431–437, 1998. Gomes et al. (2000) Carla P. Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning, 24(1–2):67–100, 2000. doi: 10.1023/A:1006314320266. Graham (1969) R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2), 1969. doi: 10.1137/0117039. Gundersen & Kjensmo (2018) Odd Erik Gundersen and Sigbjørn Kjensmo. State of the art: Reproducibility in artificial intelligence. In AAAI Conference on Artificial Intelligence, 2018. doi: 10.1609/aaai.v32i1.11503. Hao et al. (2024) Shuxin Hao, Xiangyu Hao, Zhen Xiao, You Li, et al. Multiagent Gumbel MuZero: efficient planning in combinatorial action spaces. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024. doi: 10.1609/aaai.v38i11.29121. Henderson et al. (2018) Peter Henderson, Riashat Islam, Philip Bachman, et al. Deep reinforcement learning that matters. In AAAI Conference on Artificial Intelligence, 2018. doi: 10.1609/aaai.v32i1.11694. Hooker (1995) J. N. Hooker. Testing heuristics: We have it all wrong. Journal of Heuristics, 1(1):33–42, 1995. doi: 10.1007/BF02430164. Kocsis & Szepesvári (2006) Levente Kocsis and Csaba Szepesvári. Bandit based Monte-Carlo planning. In Proceedings of the 17th European Conference on Machine Learning (ECML), 2006. doi: 10.1007/11871842_29. Kung et al. (2022) Hao-Tsung Kung, Hui-Chuan Yang, and Cheng-Min Huang. An improved Monte Carlo Tree Search approach to workflow scheduling. Connection Science, 2022. doi: 10.1080/09540091.2022.2052265. Kwok & Ahmad (1999a) Yu-Kwong Kwok and Ishfaq Ahmad. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4), 1999a. doi: 10.1145/344588.344618. Kwok & Ahmad (1999b) Yu-Kwong Kwok and Ishfaq Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. Journal of Parallel and Distributed Computing, 59(3), 1999b. doi: 10.1006/jpdc.1999.1578. Lourenço et al. (2003) Helena R. Lourenço, Olivier C. Martin, and Thomas Stützle. Iterated local search. In Handbook of Metaheuristics. 2003. doi: 10.1007/0-306-48056-5_11. Luby et al. (1993) Michael Luby, Alistair Sinclair, and David Zuckerman. Optimal speedup of Las Vegas algorithms. In 2nd Israel Symposium on Theory of Computing Systems (ISTCS), 1993. doi: 10.1109/istcs.1993.253477. Nishihara et al. (2016) Robert Nishihara, David López-Paz, et al. No regret bound for extreme bandits. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), 2016. Nosek et al. (2018) Brian A. Nosek et al. The preregistration revolution. Proceedings of the National Academy of Sciences, 115(11):2600–2606, 2018. doi: 10.1073/pnas.1708274114. Schrittwieser et al. (2021) Julian Schrittwieser et al. Sampled MuZero. arXiv preprint arXiv:2104.06303, 2021. doi: 10.48550/arXiv.2104.06303. Sih & Lee (1993) Gilbert C. Sih and Edward A. Lee. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Transactions on Parallel and Distributed Systems, 4(2), 1993. doi: 10.1109/71.207593. Silver et al. (2016) David Silver, Aja Huang, Chris J. Maddison, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529, 2016. doi: 10.1038/nature16961. Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, et al. Mastering the game of Go without human knowledge. Nature, 550, 2017. doi: 10.1038/nature24270. Sørensen (2015) Kenneth Sørensen. Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1):3–18, 2015. doi: 10.1111/itor.12001. State Grid Corporation of China (2019) State Grid Corporation of China. DAG task scheduling method based on Monte Carlo tree search, 2019. URL https://patents.google.com/patent/CN109857532B/en. Świechowski et al. (2023) Maciej Świechowski, Konrad Godlewski, Bartłomiej Sawicki, et al. Monte Carlo Tree Search: a review of recent modifications and applications. Artificial Intelligence Review, 56, 2023. doi: 10.1007/s10462-022-10228-y. Topcuoglu et al. (2002) Haluk Topcuoglu, Salim Hariri, and Min-You Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260–274, 2002. doi: 10.1109/71.993206. Ugadiarov et al. (2026) Aleksandr Ugadiarov, Yuri Kuratov, Aleksandr Panov, and Alex Skrynnik. Revisiting tree search for LLMs: Gumbel and sequential halving for budget-scalable reasoning. In International Conference on Automated Planning and Scheduling (ICAPS), 2026. doi: 10.1609/icaps.v36i1.42891. Ullman (1975) J. D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3), 1975. doi: 10.1016/s0022-0000(75)80008-0. WfCommons (2023) WfCommons. wfcommons/pegasus-instances: v1.4 (archived Pegasus workflow instances), 2023. URL https://github.com/wfcommons/pegasus-instances. Wu & Gajski (1990) Min-You Wu and Daniel D. Gajski. Hypertool: a programming aid for message-passing systems. IEEE Transactions on Parallel and Distributed Systems, 1(3), 1990. doi: 10.1109/71.80160. Zhou et al. (2025) Yuandong Zhou, Jiadi Huang, Wei Zhang, and Yeh-Ching Chan. GNN-Heatmap Augmented Monte Carlo Tree Search for Cloud Workflow Scheduling. In Proceedings of the 2025 Winter Simulation Conference (WSC 2025), 2025. doi: 10.1109/WSC68292.2025.11338866. Zilberstein & Russell (1996) Shlomo Zilberstein and Stuart Russell. Approximate reasoning using anytime algorithms. In Imprecise and Approximate Computation. 1996. doi: 10.1007/978-0-585-26870-5_4.

Instant research discovery