Toward Neural Streaming Scheduling: A Memory-Augmented Reinforcement Learning Model with Critical Structure Encoding

Ruijia Wang, Mengmei Zhang, Jiansong Zhang, Jie WuOpenReview 2026 · Submission to ICLR 2026 · Rejected · OpenReview

TL;DR

MACE is a novel reinforcement learning framework designed to schedule streaming data processing jobs—represented as Directed Acyclic Graphs (DAGs)—more efficiently. By explicitly encoding "critical paths" (the bottlenecks of a job) and utilizing a memory mechanism to learn from historical scheduling decisions, MACE reduces average job completion times by up to 9.38% compared to current state-of-the-art models like Decima.

What Problem Does This Paper Address?

In modern distributed systems like Apache Spark or Flink, computational jobs are structured as Directed Acyclic Graphs (DAGs), where nodes are processing stages and edges represent dependencies. Scheduling these jobs is a nightmare: you have to decide which stage to run next and how many resources (parallelism) to give it, all while new jobs arrive continuously in a "streaming" fashion.

The authors identify two major gaps in existing learning-based schedulers:

  1. Structural Blindness: Most models don't explicitly recognize the "critical path"—the longest sequence of dependent stages that dictates the minimum time a job will take. If you don't prioritize the critical path, the whole job drags on.
  2. Short-sightedness: Standard neural networks are often "reactive," making decisions based only on the current snapshot of the cluster. They lack a mechanism to remember how previous decisions (like giving a job 20 executors instead of 10) actually impacted performance over time.

Methods

The authors propose MACE (Memory-Augmented reinforcement learning model with Critical structure Encoding), which consists of two primary innovations:

  • CSformer (Critical Structure Transformer): This component builds hierarchical embeddings (Stage $\rightarrow$ Job $\rightarrow$ Global). Unlike standard Graph Neural Networks, it uses critical-path-aware positional encodings. It calculates how deep a stage is along the critical path and feeds that into a Transformer. It also uses an extended attention field, allowing stages to "look" at neighbors several hops away to understand long-range dependencies.
  • Memory-Augmented Scheduler: This acts as the model's long-term memory. It maintains a fixed-size recurrent state (a memory matrix) for each job. When deciding on parallelism, the scheduler queries this memory using the current job state and the rewards from the previous step. This allows the model to adjust its strategy based on what worked (or didn't) in the recent past.

The entire system is trained end-to-end using the REINFORCE algorithm, a policy gradient method, with the goal of minimizing the average Job Completion Time (JCT).

Datasets

The researchers evaluated MACE using the TPC-H benchmark, a gold standard for data analytics workloads.

  • Workload Generation: They simulated a streaming environment where jobs arrive via a Poisson process.
  • Scales: They tested across seven data scales ranging from 2GB to 100GB of raw data.
  • Baselines: MACE was compared against traditional heuristics (FIFO, SJF-CP, Fair Scheduling, HEFT, SRPT) and the leading RL-based scheduler, Decima.

Key Insights and Ideas

  • The Critical Path is the Secret Sauce: The ablation studies revealed that the critical-path-aware positional encoding was the most influential component. Removing it caused a much larger performance drop than removing the memory or the extended attention field.
  • Contextual Awareness beats Raw Speed: While heuristic schedulers like FIFO have near-zero decision latency, MACE’s slightly higher latency (~5.5ms) is a drop in the bucket compared to job runtimes (seconds or minutes). The "smarter" decision pays for itself many times over.
  • Generalization to the Unknown: MACE showed superior "template-level generalization." When trained on only a few types of queries and tested on entirely new ones, its performance degraded much more slowly than Decima's, likely because it learns the structural motifs of DAGs rather than just memorizing specific job shapes.

Key Results

  • Performance Boost: MACE achieved the lowest average JCT in 7 out of 9 test scenarios, outperforming Decima by up to 9.38%.
  • Robustness: Under "stress tests"—such as high-load scenarios (frequent job arrivals) or limited resource capacity—MACE maintained a significant lead over both heuristics and other RL models.
  • Efficiency: Visualization of scheduling traces showed that MACE packs tasks more densely into available executor slots, leading to earlier job completions and fewer idle "purple regions" in the cluster timeline.

Limitations and Future Work

While MACE is a step forward, the authors note a few areas for improvement:

  • Homogeneous Assumptions: The current model assumes all executors (CPUs/Nodes) are identical. In the real world, clusters are often heterogeneous (different RAM, CPU speeds, etc.).
  • Communication Costs: The model does not yet explicitly account for the time it takes to move data between executors, which can be a major bottleneck in large-scale shuffles.
  • Future Directions: The authors plan to extend MACE to handle these complexities and explore even more diverse, large-scale scheduling environments.

Summary updated

Abstract

Many large-scale data analytics and AI systems execute jobs structured as Directed Acyclic Graphs (DAGs), which encode precedence constraints among interdependent stages. Efficient DAG scheduling is crucial for maximizing system throughput, especially in streaming settings where diverse jobs arrive continuously and require real-time decisions. Despite progress by heuristic and learning-based scheduling methods, capturing execution-critical structures and leveraging historical scheduling context remain key challenges. Building on this motivation, we propose MACE, a Memory-Augmented reinforcement learning model with Critical structure Encoding, which implements a scheduling policy for streaming jobs by sequentially selecting runnable stages and assigning parallelism based on cluster state. The policy is trained to minimize average job completion time using defined rewards. Specifically, MACE consists of two core components: (i) CSformer builds hierarchical embeddings that integrate stage-job-global information, capturing execution-critical structures through critical-path-aware positional encodings and a tunable attention field. This design guides the policy toward latency-sensitive and structurally related stages. (ii) A memory-augmented scheduler then uses the learned embeddings and a job memory to exploit historical contexts for the final stage and parallelism selection. Extensive experiments on Spark using the TPC-H benchmark demonstrate that MACE outperforms state-of-the-art baselines by up to 9.38% under diverse workload conditions.
BibTeX
@misc{wang2026toward,
  author = {Ruijia Wang and Mengmei Zhang and Jiansong Zhang and Jie Wu},
  title = {{Toward Neural Streaming Scheduling: A Memory-Augmented Reinforcement Learning Model with Critical Structure Encoding}},
  year = {2026},
  url = {https://openreview.net/forum?id=rnrENwgDsn},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2026},
}
Figure