Streaming Tensor Programs: A Streaming Abstraction for Dynamic Parallelism

Gina Sohn, Genghan Zhang, Konstantin Hoßfeld, Jungwoo Kim, Nathan Sobotka, Nathan Zhang and 2 others

Spatial dataflow accelerators lay a computation out as a fixed pipeline of compute and memory tiles and stream data through it, which is extremely efficient for tensor programs with fixed shapes — but modern models, especially LLMs with variable-length sequences and mixture-of-experts routing, have data-dependent shapes and control flow that prior accelerator abstractions could only handle by padding to the worst case or leaving them unoptimized; this paper (Stanford — Gina Sohn, Genghan Zhang, Konstantin Hossfeld, Jungwoo Kim, Nathan Sobotka, Nathan Zhang, Olivia Hsu, Kunle Olukotun) presents STeP, a streaming abstraction with flexible routing operators, an explicit memory hierarchy, and symbolic shapes that expose dynamic data rates and dimensions, unlocking dynamic tiling, dynamic parallelization, and time-multiplexing that adapt the accelerator to dynamic behavior while keeping dataflow efficiency — improving latency about 2.72 times and compute utilization about 2.64 times over prior abstractions.

The argument in one glance

Problem

Dataflow accelerators are fast for fixed-shape tensors, but models are getting dynamic

Spatial dataflow accelerators (SDAs) are reconfigurable chips built as a fabric of compute and memory tiles wired together, onto which you map a computation as a dataflow graph — operations become tiles, data dependencies become hardware connections — and data streams through the resulting pipeline. This is wonderfully efficient for tensor programs, because it avoids control overhead and enables aggressive operator fusion, pipelining, and fine-grained parallelism. The catch is that this efficiency assumes the computation is static: fixed tensor shapes and a fixed graph. Modern machine-learning models break that assumption. LLMs and other widely used models have data-dependent tensor shapes (variable-length sequences, ragged tensors) and data-dependent control flow (like mixture-of-experts routing that sends different tokens to different experts). The accelerator that thrives on regularity now has to run workloads whose shapes and paths are decided at run time.
What people did

Force the dynamic behavior into a static dataflow program

Because prior programming abstractions for SDAs assume static shapes and structure, the way to run a dynamic model on them is to make it static: pad every variable-length tensor to a worst-case maximum size so the shapes are fixed, and encode data-dependent control flow into a graph that covers all cases. The dataflow graph is then fixed and maps cleanly onto the spatial fabric, the way the accelerator expects.
Why it fell short

Static workarounds waste compute and memory, or go unoptimized

Forcing dynamism into a static mold is expensive. Padding tensors to their worst-case shape means the accelerator computes over, and stores, large amounts of padding that carries no real data — wasted compute and wasted on-chip memory. Encoding data-dependent routing statically means running or reserving resources for paths that a given input never takes. And because the prior abstractions cannot express the dynamic data rates and shapes, the compiler cannot even see the opportunities to tile, parallelize, or schedule according to the actual, run-time sizes — so the dynamic behavior is either implemented statically at a heavy cost or left unoptimized. The result is that SDAs, which are among the most efficient hardware for tensor work, deliver far less than their potential on exactly the dynamic models that now dominate, because the programming abstraction hides the dynamism the hardware would need to exploit.
This paper's idea

A streaming abstraction that makes dynamism first-class

STeP (Streaming Tensor Programs) is an asynchronous dataflow abstraction for SDAs with first-class support for dynamism. Tensors flow as streams whose dimensions are marked by stop tokens, and STeP adds three capabilities the old abstractions lacked. Flexible routing and merging operators express data-dependent control flow (such as routing tokens to experts) directly in the dataflow, rather than baking it into a static graph. An explicit memory hierarchy exposes off-chip and on-chip memory in the abstraction so the compiler can reason about and optimize data movement across tiers. And symbolic-shape semantics represent tensor dimensions and data rates with symbols, so dynamic and ragged dimensions are expressed rather than padded away. Because the abstraction now exposes the dynamic data rates and shapes, it unlocks optimizations that adapt execution to run-time behavior while preserving dataflow efficiency: dynamic tiling (tile to the actual shape instead of padding), dynamic parallelization (adjust parallelism to the real work), and configuration time-multiplexing (time-share the fabric across configurations). A symbolic frontend and performance model extract metrics like off-chip traffic and on-chip memory need at the abstraction level. On LLM layers and a full model with real traces, dynamic tiling breaks the prior Pareto frontier, dynamic parallelization improves latency about 2.72 times, and time-multiplexing raises compute utilization about 2.64 times over prior SDA abstractions.

Why this problem is worth solving

Spatial dataflow accelerators are among the most efficient ways to run tensor computations, so making them handle modern models well is high-value.

A spatial dataflow accelerator is a reconfigurable chip made of many compute units and memory units distributed across the die and connected by on-chip links. Instead of a conventional processor that fetches and executes instructions one stream at a time, an SDA runs a computation by mapping its dataflow graph directly onto the hardware: each operation in the graph is placed on a compute or memory tile, and each data dependency (edge) becomes a physical connection — a hardware queue or a path through the on-chip network — so data flows from tile to tile and is processed as it arrives. This spatial mapping avoids much of the control overhead of instruction-based execution and enables aggressive operator fusion (chaining operations so intermediate data never leaves the chip), deep pipelining, and fine-grained parallelism, which is why SDAs can be very fast and energy-efficient for tensor workloads. The storage is organized in tiers — local tile storage, on-chip memory, off-chip memory — and keeping data in the faster tiers is central to performance. All of this works beautifully when the computation is regular and known ahead of time, because you can lay out the graph and the data movement statically and stream data through at full rate. The efficiency is real and demonstrated, which is exactly why it is worth extending these accelerators to the workloads they currently struggle with, rather than abandoning the architecture.

The reason dynamism is so damaging is that it collides with the static assumption the whole model rests on.

The power of a spatial dataflow accelerator comes from committing to a fixed plan: a fixed graph of operations mapped to fixed tiles, moving fixed-shaped tensors at predictable rates. Dynamic behavior violates every part of that. Data-dependent tensor shapes — a sequence whose length depends on the input, a ragged batch, a sparsity pattern decided at run time — mean the sizes are not known when the graph is laid out. Data-dependent control flow — mixture-of-experts routing that sends each token to a different expert, early exit, conditional branches — means which operations run, and how much data each receives, depends on the input. If the abstraction can only describe static computation, the compiler must eliminate the dynamism before mapping: pad every tensor to the largest size it could ever take so the shapes become fixed, and materialize all possible control-flow paths. Padding is the expensive part: the accelerator then spends compute cycles multiplying padding by weights and burns scarce on-chip memory storing values that are not real data, and because tensor work is often memory-bound, that wasted memory traffic translates directly into lost performance. Worse, since the abstraction never exposed the true, dynamic sizes, the compiler cannot tile or parallelize to the actual work — it optimizes for the worst case it was forced to assume. The dynamism is not merely unhandled; it is actively hidden, which is the gap STeP sets out to close by making the dynamic shapes and rates visible in the abstraction itself.

What people did before, and where it broke

Pad dynamic tensors to worst-case shapes. Fix every variable dimension at its maximum so the shapes are static and map onto the fabric. Where it broke. The accelerator computes over and stores large amounts of padding, wasting compute and, critically, scarce on-chip memory, which for memory-bound tensor work directly costs performance.
Statically encode data-dependent control flow. Bake all possible paths (for example all experts in a mixture-of-experts layer) into a fixed graph. Where it broke. Resources are spent or reserved for paths a given input never takes, and the fixed graph cannot adapt to which path actually runs.
Leave the dynamic parts unoptimized. Run the dynamic behavior in a fallback manner outside the accelerator’s optimized dataflow. Where it broke. It forfeits the fusion, pipelining, and parallelism that make SDAs fast, so the dynamic portions run far below the hardware’s potential.
Prior SDA abstractions with static shapes. Use existing dataflow programming models that assume fixed shapes and rates. Where it broke. They cannot even express dynamic data rates and dimensions, so the compiler is blind to run-time sizes and cannot tile, parallelize, or schedule to the actual work.
The gap. No SDA abstraction made dynamism first-class — expressing dynamic shapes, data rates, and data-dependent routing while exposing an explicit memory hierarchy — so that a compiler could adapt tiling, parallelization, and scheduling to run-time behavior without sacrificing dataflow efficiency.

How STeP works

Making dynamic shapes and routing first-class in a dataflow abstraction

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Make the dynamism visible in the abstraction, not hidden by padding. The organizing insight of STeP is that the accelerator could exploit dynamic behavior if only the programming abstraction let the compiler see it; prior abstractions destroyed the information by forcing everything static, so the fix is a representation in which dynamic shapes, data rates, and routing are expressed directly. STeP does this with a stream-centric design where tensors flow as streams delimited by stop tokens and dimensions carry symbolic shapes, so a ragged or variable-length tensor is a first-class object rather than a padded block. Building an abstraction whose whole purpose is to capture irregular, data-dependent structure so downstream tooling can optimize against it, rather than flattening the structure away, is the same design philosophy the work on composable abstractions for sparse compilation covered elsewhere on this site is built on, making irregularity a first-class citizen of the representation. STeP applies that philosophy to dynamic tensor programs on spatial hardware.

Express control flow and data movement as dataflow, so the mapping stays efficient. It is not enough to describe dynamism; it must be described in a form the spatial fabric can still run efficiently, or you lose the fusion and pipelining that justify the accelerator. STeP keeps everything within an asynchronous dataflow model: routing and merging operators handle data-dependent control flow as stream operations, and an explicit memory hierarchy makes data movement across tiers part of the program. Compiling a computation into an explicit dataflow form so it maps cleanly onto spatially distributed compute and memory is the same discipline the work on compiling Einstein summations to locality-aware dataflow covered elsewhere on this site pursues, turning a computation into an efficient dataflow schedule. STeP extends that discipline to dynamic control flow, so dynamism and dataflow efficiency coexist rather than trade off.

Turn exposed dynamism into concrete run-time optimizations. The payoff of a dynamism-aware abstraction is that the compiler can finally adapt execution to the actual work. Dynamic tiling sizes tiles to the real shapes, removing padding and breaking the prior trade-off between off-chip traffic and on-chip memory; dynamic parallelization matches parallelism to the real amount of work; and configuration time-multiplexing time-shares the reconfigurable fabric across configurations so it is not left idle. Reconfiguring and time-sharing a spatial fabric of compute and memory to fit the workload, rather than committing to one static mapping, is the same flexibility the work on a framework for heterogeneous reconfigurable-array realization covered elsewhere on this site is built on, treating the spatial substrate as something to be adapted. STeP supplies the abstraction and the symbolic model that make such adaptation possible for dynamic tensor workloads, so the accelerator keeps its efficiency while gaining flexibility.

Following a dynamic layer through STeP

Running a mixture-of-experts LLM layer with variable-length input

A trace, drawn from the paper, of how STeP expresses and optimizes a dynamic tensor layer on a spatial dataflow accelerator.

Step 1 of 5

The layer has variable shapes and data-dependent routing

A mixture-of-experts layer receives a batch whose sequences vary in length and must route each token to a data-dependent expert. On a static abstraction this would be padded to a worst-case shape and all experts would be materialized in the graph.

The dynamism is in both the shapes and the control flow.

Why it works

Symbolic shapes expose the real work instead of the worst case. Padding to worst-case shapes hides the true sizes and wastes compute and memory → but symbolic-shape semantics express the actual dynamic dimensions → so the compiler can tile and schedule to the real work rather than the padded maximum.
Streams with stop tokens make ragged tensors natural. A fixed-block representation forces variable-length data into padded rectangles → but streams delimited by stop tokens carry dynamic and ragged dimensions directly → so no padding is needed to represent irregular tensors.
Routing operators keep control flow inside the dataflow. Materializing every control-flow path statically wastes resources on untaken paths → but routing and merging operators direct streams by run-time values → so only the paths actually taken consume compute and memory.
An explicit memory hierarchy lets the compiler manage data movement. Hidden memory tiers leave data-movement optimization out of reach → but exposing off-chip and on-chip memory operators makes tiering part of the program → so the compiler can cut off-chip traffic and fit data on chip.
Exposed dynamism unlocks adaptive optimizations at no efficiency loss. Static mappings cannot adapt to run-time sizes → but with dynamism visible, dynamic tiling, parallelization, and time-multiplexing adjust execution while staying in the dataflow model → so the accelerator gains flexibility without losing pipelining and fusion.

What it costs (trade-offs and scope)

It is an abstraction plus a simulator study, not a silicon deployment. The paper defines STeP and evaluates it with a cycle-approximate simulator (validated against a cycle-accurate one) on LLM layers and a full model with real traces, and it outlines how the dynamic features would be supported in SDA hardware; realizing those features in a physical accelerator is future work, so the reported gains are simulator-based.
The hardware must support the dynamic features. STeP’s routing, symbolic shapes, and time-multiplexing assume the underlying SDA can be reconfigured and can handle dynamic data rates; existing accelerators may need extensions to support them fully, which the paper sketches but does not build.
Dynamic optimization adds complexity and analysis. Adapting tiling, parallelization, and scheduling to run-time shapes requires the symbolic frontend and performance model to reason about dynamic behavior, which is more involved than compiling a static graph; the benefit is contingent on that analysis being accurate for the workload.
The reported numbers are for specific workloads and baselines. The about-2.72-times latency and about-2.64-times utilization gains, and the broken Pareto frontier, are measured on representative LLM layers and a full model with real-world traces against prior SDA abstractions and their implementations; other models, traces, and hardware assumptions would shift them.
It targets dynamic tensor workloads on spatial dataflow accelerators. The approach is aimed at data-dependent shapes and control flow in tensor programs mapped to SDAs; static workloads already run well on prior abstractions, and non-tensor or non-dataflow settings are outside its scope.

The evaluation

Running dynamic tensor models on spatial dataflow accelerators

Property	Static abstraction with padding	Unoptimized dynamic fallback	STeP
Expresses dynamic shapes
Expresses data-dependent routing
Wasted compute and memory
Preserves dataflow efficiency
Reported outcome

A qualitative comparison of ways to run dynamic tensor models on spatial dataflow accelerators. On LLM layers and a full model with real traces, STeP's dynamic tiling breaks the prior Pareto frontier, dynamic parallelization improves latency about 2.72 times, and configuration time-multiplexing raises compute utilization about 2.64 times over prior SDA abstractions.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (arXiv:2511.07776). The mechanism described is the paper’s: STeP (Streaming Tensor Programs) is an asynchronous dataflow abstraction for spatial dataflow accelerators with first-class support for dynamism, using a stream-centric design with stop tokens, flexible routing and merging operators for data-dependent control flow, an explicit memory hierarchy (off-chip and on-chip memory operators), and symbolic-shape semantics that expose dynamic data rates and tensor dimensions; these enable optimizations — dynamic tiling, dynamic parallelization, and configuration time-multiplexing — that adapt SDA execution to dynamic behavior while preserving dataflow efficiency, and a symbolic frontend and performance model extract metrics such as off-chip traffic and on-chip memory requirement at the abstraction level. The headline figures are the paper’s own, from a cycle-approximate simulator (validated against a cycle-accurate one) on representative LLM layers and a full model with real-world traces: dynamic tiling breaks the Pareto-optimal frontier from prior work, dynamic parallelization improves latency by about 2.72 times, and configuration time-multiplexing increases compute utilization by about 2.64 times over prior SDA abstractions and their implementations. This is a simulator-based study with an outline of hardware support; exact operator semantics, the symbolic model, and the full evaluation should be read from the paper.

Background

Why abstractions decide what hardware can exploit

It helps to see STeP as an instance of a deep truth in computer systems: the programming abstraction you choose determines which optimizations are even possible, because a compiler and a piece of hardware can only exploit what the abstraction lets them see. Spatial dataflow accelerators are a striking case, because their whole efficiency comes from committing to an explicit, static-looking plan — a graph of operations laid out on a fabric — and that commitment is also what makes them brittle when the workload stops being static. For years, dynamic behavior in tensor programs was rare enough that padding it away was acceptable; but machine learning has turned dynamism into the common case, with variable-length inputs, sparsity, and routing everywhere, so the old abstractions now hide exactly the structure that matters most. The response, repeated across the field, is to enrich the abstraction so that irregularity and data-dependence become expressible, and then to build the analyses and hardware support that turn that visibility into speed. This is the same move that reshaped sparse computation, where redesigning the representation around irregular structure unlocked specialized execution — the concern the work on a stream ISA and processor specialization for sparse computation covered elsewhere on this site pursues, specializing both the abstraction and the hardware for irregular data. STeP carries that lesson to dynamic tensor programs on spatial accelerators, arguing that the right streaming abstraction is what lets efficient hardware finally embrace dynamism.

If you remember only three things

1. Spatial dataflow accelerators run tensor computations extremely efficiently by mapping a dataflow graph onto a fabric of compute and memory tiles and streaming data through it — but this assumes static shapes and structure. Modern models, especially LLMs, have data-dependent tensor shapes (variable-length, ragged) and control flow (mixture-of-experts routing), and prior SDA abstractions could only handle these by forcing them static (padding tensors to worst-case shapes, materializing all control-flow paths), which wastes compute and scarce on-chip memory, or by leaving them unoptimized outside the efficient dataflow.
2. STeP (Streaming Tensor Programs) is an asynchronous dataflow abstraction with first-class dynamism. Tensors flow as streams delimited by stop tokens; flexible routing and merging operators express data-dependent control flow within the dataflow; an explicit memory hierarchy exposes off-chip and on-chip memory; and symbolic-shape semantics represent dynamic and ragged dimensions and data rates. Because dynamism is now visible to the compiler, STeP unlocks dynamic tiling (tile to real shapes, no padding), dynamic parallelization (match parallelism to real work), and configuration time-multiplexing (time-share the fabric) — all while preserving dataflow efficiency. A symbolic frontend and performance model extract metrics like off-chip traffic and on-chip memory at the abstraction level.
3. On representative LLM layers and a full model with real-world traces (via a cycle-approximate simulator validated against a cycle-accurate one), STeP's dynamic tiling breaks the prior Pareto-optimal frontier, dynamic parallelization improves latency by about 2.72 times, and configuration time-multiplexing raises compute utilization by about 2.64 times over prior SDA abstractions. It is a simulator-based study with an outline of hardware support, assumes the SDA can support the dynamic features, adds analysis complexity, and targets dynamic tensor workloads specifically.

Check yourself

Check your understanding

1. Why do spatial dataflow accelerators struggle with modern dynamic tensor models?
2. What is STeP's core idea?
3. What optimizations does exposing dynamism unlock, and how do they help?
4. What are the scope and limits of STeP's results?

Sources

The paper is “Streaming Tensor Programs: A Streaming Abstraction for Dynamic Parallelism” by Gina Sohn, Genghan Zhang, Konstantin Hossfeld, Jungwoo Kim, Nathan Sobotka, Nathan Zhang, Olivia Hsu, and Kunle Olukotun (Stanford University), published at ASPLOS 2026 (Volume 2), DOI 10.1145/3779212.3790229. The abstraction is named STeP. It is licensed CC BY.

This explainer is written from the paper’s full text (arXiv:2511.07776). The paper addresses dynamic behaviors — data-dependent tensor shapes and control flow — that are increasingly prevalent in tensor applications like machine learning, and that the limited expressiveness of prior spatial-dataflow-accelerator (SDA) abstractions forces to be implemented statically and/or unoptimized. STeP is a streaming abstraction that enables dynamic tensor workloads to run efficiently on SDAs: it is an asynchronous dataflow abstraction with a stream-centric design using stop tokens, and it introduces flexible routing (and merging) operators, an explicit memory hierarchy (off-chip and on-chip memory operators), and symbolic-shape semantics that expose dynamic data rates and tensor dimensions. These capabilities unlock optimizations — dynamic tiling, dynamic parallelization, and configuration time-multiplexing — that adapt SDA execution to dynamic behaviors while preserving dataflow efficiency, and a symbolic frontend and performance model extract performance-critical metrics (off-chip traffic, on-chip memory requirement, operational intensity) at the abstraction level, validated against a cycle-accurate simulator. Using a cycle-approximate simulator on representative LLM layers and a full model with real-world traces, the reported results are the paper’s own: dynamic tiling breaks the Pareto-optimal frontier from prior work, dynamic parallelization improves latency by about 2.72 times, and configuration time-multiplexing increases compute utilization by about 2.64 times over prior SDA abstractions and their implementations. No numbers beyond the paper’s own have been introduced; exact operator semantics, the symbolic model, the outlined hardware support, and the full evaluation should be confirmed in the paper.