精读笔记
Problem Setting
[Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters]（arXiv preprint / 2026）
这篇论文实际处理的是一个“未知 service-rate response 的 queueing control”问题，而不只是 malleable job scheduling。系统有固定数量 cores，两类 observable jobs，class-specific speed-up function 的形式已知但参数未知；控制目标是最小化 steady-state mean number of jobs。难点在于 speed-up 参数不是直接观测量，只能通过在不同系统状态和分配比例下产生的 departure times 间接识别。
关键矛盾是 exploitation 与 identification：如果当前策略已经偏向某一类或某些状态，它会改变未来观测到的 allocation/state distribution，从而影响参数估计；而参数估计又决定下一轮策略。已有工作通常假设 speed-up 曲线已知，因此只需解 MDP 或分析某些结构性策略；这里真正卡住的是 speed-up uncertainty 进入了 service intensity，使得调度问题变成了统计推断与平均成本控制的闭环。
Motivation
已有路线不够的地方很明确：malleable scheduling 文献擅长在已知 speed-up 下优化 allocation，但现实云 GPU / 大规模训练场景中，parallel efficiency 会随 workload、硬件、interconnect、训练阶段变化而漂移。把 speed-up function 当作固定输入，本质上把最难的系统辨识问题外包掉了。
作者的核心观察是：在指数 job size 和 Markovian queueing 假设下，speed-up 参数虽然不可直接看见，但它决定每个状态下的 departure hazard；因此 departure process 本身携带了关于 parallelizability 的统计信息。缺口不是缺一个更复杂的 scheduler，而是缺一个能把 operational data 转换成 speed-up estimate、再反馈给 scheduler 的机制。
Core Idea
核心思想是把 speed-up learning 放进 queueing control 的自然统计结构里：不是用外部 profiling 或 benchmark 测 speed-up，而是从真实运行轨迹中的 state-dependent inter-departure times 估计参数。由于在相邻事件之间系统状态和 allocation 不变，class-i departure rate 是 n_i μ s_i(z_i;p_i)，于是每段 observation window 可以被拆成 piecewise-constant hazard 的 survival/product likelihood。
本质区别在于信息流被重新组织了。prior work 是“给定 speed-up → 求策略”；本文变成“策略产生状态访问分布 → departure hazard 暴露 speed-up → MLE 更新参数 → MDP 更新策略”。新的 inductive bias 是强 queueing-structural bias：假设系统演化足够 Markovian，且 speed-up 参数只通过低维 parametric hazard 影响观测。这比黑箱 RL 更 sample-efficient、更可解释，但泛化范围也被这些结构假设强烈限制。
Method
方法上真正必要的机制只有几个。
第一，class 内 equal sharing / equi restriction 用来压缩控制空间。每个状态只决定给 class 1 的 core fraction，class 内 job 平分资源。这不是无关实现细节，而是让 departure rate 可写成低维函数，并继承已有 MDP formulation；代价是排除了 class 内 size/age/heterogeneity-aware policies。
第二，MLE 基于 inter-departure decomposition。两次同类 departure 之间可能有 arrivals 和另一类 departures，导致 rate 改变；论文把这些区间切成状态不变的小段，likelihood 是所有无同类 departure survival 项乘以最终 departure hazard。它解决的是“只观测事件轨迹而非 job intrinsic service demand”时如何估计 speed-up 参数。
第三，固定参数后用 finite-state CTMC uniformization 和 average-cost Bellman equation 求策略。这个步骤主要复用已有 MDP 思路，核心作用是把统计估计转为控制动作；它不是论文最原创的部分。
第四，两个 learning loop 的差别是数据窗口选择：Algorithm 1a 用最近窗口，适合非平稳但方差更大；Algorithm 1b 累计历史数据，stationary 下更稳但对参数漂移迟钝。这是 bias-variance / adaptivity-stability tradeoff，而不是新的控制理论。
Key Insight / Why It Works
这篇论文最有价值的 insight 是：malleable-job speed-up 参数可以通过 departure hazard 被动识别，不一定需要显式 profiling。只要策略让系统经历足够多有区分度的 per-job allocation z，参数 p 会在 log hazard 和 cumulative hazard 两个项中留下可估计信号。这里的“学习”本质上不是 representation learning，而是 parametric identification under controlled stochastic dynamics。
方法成立依赖三个核心条件。第一，指数服务时间让 residual work 不需要进入状态，否则 departure intensity 不能只由 job count 和 allocation 决定。第二，speed-up family 必须 identifiable；如果不同 p 在系统实际访问到的 z 区间上几乎产生相同 s(z;p)，MLE 会出现 quasi-identifiability，论文实验中低 p 收敛慢就是这个问题。第三，policy 必须避免 starvation 并产生足够数据，否则某一类或某些 allocation regimes 的参数无法可靠识别。
最可能的核心贡献是 likelihood construction 与 fixed-policy consistency proof，而不是 value iteration 或在线循环本身。Bellman update 是已有框架的 plug-in；Algorithm 1a/1b 更像 engineering choices。数值增益主要来自模型内 MLE 的 sample efficiency 和低维参数化，而不是某种深层 adaptive planning 能力。若放到更复杂真实系统，收益是否来自机制本身还是来自 Amdahl-law-like parametric fit，文中未充分说明。
这不是 scaling 方法，也不是 retrieval/memory reuse；它是强 inductive bias 的结构化统计控制。优点是 data-efficient 和可解释，缺点是模型错配时会系统性偏。
Relation To Prior Work
最接近的是 Berg et al. 一类 parallel scheduling / malleable jobs MDP 工作，以及 queueing statistical inference 文献。和前者相比，本文真正新增的是 unknown speed-up parameters 下的 estimation layer；和后者相比，新增的是被估计对象不是 arrival/service primitive，而是 allocation-dependent parallelization response。
看似新的在线算法其实是 certainty-equivalent adaptive control：估计参数，然后把估计值当真值解控制。这个思想并不新，实质创新在于把 malleable scheduling 的 departure process 写成可操作的 likelihood，并给 fixed policy 下的强一致性论证。
它属于“model-based adaptive queueing control”谱系，而不是 RL scheduling 谱系。相比黑箱 RL，它没有学习 value function 或 policy representation，而是利用 queueing model 将未知性压缩为少数 speed-up 参数。这个选择使理论证明更干净，但也牺牲了对复杂 workload dynamics 的覆盖。
Dataset / Evaluation
evaluation 完全是数值仿真，没有真实集群/GPU traces，也没有真机 deployment。任务覆盖主要是两类 jobs、Amdahl speed-up、少数组合的 λ/μ/c/α/p 设置，以及一个手工设计的非平稳参数变化实验。它验证的是在作者模型闭包内，MLE 能收敛、策略 heatmap 会改变、Algorithm 1b 比 1a 更快利用历史数据。
这些实验支持“估计-控制闭环可运行”这个 claim，但不充分支持更强的 deployment claim。尤其是没有比较非 parametric profiling、Bayesian adaptive control、RL/approximate DP、或者 exploration-aware policies；也没有系统分析 model misspecification、heavy-tailed job sizes、class misclassification、time-varying arrival rates。benchmark 没有明显 leakage 问题，因为是仿真；但 evaluation bias 很明显：数据生成机制基本等于模型假设本身。
Limitation
最根本限制是理论与算法之间有 gap。强一致性只在 fixed allocation policy 下证明，而实际算法每轮都更新 policy；Algorithm 1b 还把不同 policy 下产生的数据混在一起做 MLE。文中承认这一点，但没有给出 adaptive setting 下的一致性、稳定性、regret 或 asymptotic optimality 证明。
第二，identifiability 被低估了。论文在证明中用“speed-up 参数唯一决定函数”来支撑 KL identifiability，但实际可辨识性取决于系统访问到哪些 z。如果策略很少给某类 job 超过 1 个 core，或者不同 p 在访问区间内曲线接近，那么估计会很弱；这不是样本数简单变大就一定解决的 engineering 问题，而是 exploration design 问题。
第三，scalability 上限明显。两类状态是 (n1,n2)，多类扩展会造成状态空间爆炸；连续 action 的 Bellman minimization 也会变重。论文说可扩展到多类，但真正瓶颈被转移到 MDP 求解。
第四，模型假设偏强：Poisson arrivals、exponential sizes、known μ、observable class、parametric speed-up、finite n_max、class 内 equal sharing。这些假设使 likelihood 漂亮，但真实训练作业有阶段性、非指数完成时间、placement/interconnect constraints、job-level heterogeneity 和 interference。泛化是否真实存在，文中未充分说明。
第五，非平稳实验只是展示 Algorithm 1a 可追踪手工变参；没有 change-point detection、forgetting factor 理论、或 tracking error 分析。所谓适应动态 speed-up 更像窗口化 MLE 的直觉收益，而不是完整的 non-stationary control solution。
Takeaway
- 最值得记住的第一点：在 malleable scheduling 中，speed-up function 不必被视为外部 profiling 输入；如果模型足够 Markovian，它可以从 departure hazard 中在线识别。
- 第二点：这篇论文真正推动的是把 parallel scheduling 从“known model control”推向“model-based adaptive control”，而不是提出一个全新的 scheduler。
- 第三点：可迁移 insight 是把 unknown system response 参数放进 event intensity，再用 operational traces 做 likelihood-based learning；这对 cloud autoscaling、server allocation、bandwidth sharing 等 queueing-control 问题都适用。
- 第四点：未来真正值得做的是 exploration-aware allocation 与 scalable approximate control，而不是继续在两类 finite MDP 上调窗口。
一句话总结
这篇论文是 malleable-job scheduling 从已知 speed-up 的 MDP 优化走向结构化自适应控制的一步，核心贡献是用 departure-process likelihood 识别并行化参数，而非提出本质上新的调度策略。