A camera-based perception system on a car does not need to recompute every part of every frame. A patch of empty sky can be reused for a second; a patch containing a cyclist cutting across the lane cannot. Seen this way, choosing which image regions to recompute at each frame is a patrolling problem, the problem of sending a limited set of agents to revisit locations often enough that no location goes stale for too long. Here the agent is the accelerator's compute budget for each frame, the locations are image tiles, and each tile's importance is set by how fast its content is changing. Theory for this problem already exists. Afshani et al. turn continuous-time patrolling into a discrete "time-window" problem in which each site must be visited once inside each window, with window width inversely proportional to the site's weight. They also round weights to powers of two so that only a small set of windows needs to be considered (Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency).
That theory assumes a visit costs the same however it is grouped, and on GPUs that assumption fails. Recomputing 40 scattered tiles in separate small launches can take longer than recomputing the whole frame densely. Low-arithmetic operations that move a lot of memory, irregular gather and scatter, and kernel launch overhead all mean that operation counts (FLOPs) predict wall-clock time poorly (ShuffleNet V2; Latency-aware Spatial-wise Dynamic Networks). The proposal replaces the per-visit cost in patrol scheduling with a measured, hardware-specific cost for a batch of tiles. That cost has a fixed overhead plus a per-tile term limited by memory bandwidth. The structure is the same as speed scaling with a sleep state, where a fixed wake-up penalty makes it optimal to "race to idle" and never to run below a critical speed (A Fully Polynomial-Time Approximation Scheme for Speed Scaling with a Sleep State). The prediction is that good streaming schedules refresh tiles in a few synchronized groups on power-of-two periods, and skip a frame entirely rather than run a refresh batch smaller than a hardware-determined critical size.
Core Claim
Let tile $i$ have weight $w_i$, a predicted motion magnitude. Let $L_i$ be the longest time between two consecutive recomputations of tile $i$; between recomputations its features are carried forward. Let $c(B)$ be the measured latency of one fused pass that recomputes a batch of $B$ tiles. The scheduler picks the set of tiles $S_f$ to recompute at each frame $f$ so as to solve
$$\min \max_i \; w_i L_i \quad \text{subject to} \quad c(|S_f|) \le \tau \text{ for every frame } f,$$
where $\tau$ is the frame interval, about 33 ms at 30 frames per second.
The cost model is $c(B) = C + \beta B$ for $B$ up to the point where the hardware saturates. Here $C$ is the fixed cost of launching and fusing the pass, and $\beta$ is the per-tile cost set by memory bandwidth. Both are fitted per device, so they reflect measured behaviour rather than a FLOP count. Under this model, the throughput cost per tile, $c(B)/B$, falls as $B$ grows. Accumulating refresh demand and paying $C$ once beats paying it every frame, up to the point where the deadline $\tau$ binds. This yields a critical batch size $B^\ast$, playing the role of the critical speed $s_{crit}$ in the sleep-state analysis: below $B^\ast$ it is cheaper to idle and let staleness build up.
Following Afshani et al., weights are rounded to powers of two. Each tile then receives a refresh period of $2^{j}$ frames, and every frame recomputes the union of the classes whose period divides the frame index. Two consequences follow. First, the rounding loses at most a factor of two in weighted staleness, inherited from the dyadic rounding argument. Second, the batch shapes repeat with a known cycle, so each shape can be compiled once into a fixed fused kernel.
The new element relative to all cited work is the combination. Discretizing the timeline into dyadic windows makes the schedule provably near-optimal and predictable. Building the measured batch cost into that discretization makes the schedule fast on real hardware rather than only cheap in FLOPs.
Relation to Prior Work
Three works motivate the gap. Towards Streaming Perception defines streaming AP, accuracy scored against the world state at the moment the answer is produced. It also proposes shrinking-tail scheduling, which decides whether to idle and wait for a fresher frame. This is the closest prior work, but it makes a whole-frame decision for a black-box model with fixed latency. We make the decision per tile, with weights, and with a cost that depends on batch size. The ASAP benchmark shows that high-FLOP models lose rank on weaker GPUs because they overrun the frame interval. It compares statically chosen models and does not adapt compute over time. StreamYOLO forecasts the next frame's boxes to hide latency but assumes a uniform one-step delay. We reuse its forecasting head as the mechanism that carries forward stale tiles.
Two works supply methods. LASNet supplies tile-level execution and an analytical latency model built from hardware specifications. It showed that coarse patches plus fused gather and scatter turn FLOP savings into real speedups, though only on single images (Latency-aware Spatial-wise Dynamic Networks). We add the time axis and replace its per-image sparsity ratio with a schedule across frames. NetAdapt supplies the practice of building lookup tables from on-device measurements. We use it to fit $C$ and $\beta$.
Three results constrain the design. Afshani et al. prove that for weighted sites, splitting the work into fixed independent routines (their "disjoint zigzags") is suboptimal and that coordination is required. That argues against giving each tile its own independent refresh timer. All You Need Is a Few Shifts and Polyline Path Masked Attention show that fine-grained or dynamic masking can erase theoretical savings. That rules out per-pixel refresh. Finally, the FPTAS of Antoniadis et al. is far too slow to run online. We borrow only its structural insight, the critical-speed threshold, and not its algorithm.
Research Program
The work has four parts.
The first is a tile-dynamic YOLOX detector. It uses 8×8 or 16×16 feature tiles, a halo of neighbouring features so that convolutions near tile borders see correct context, and a feature cache. Tiles that are not refreshed take their cached features, advanced by a StreamYOLO-style dual-flow forecast.
The second is per-device cost profiling. We measure $c(B)$ for fused refresh passes on an RTX 3090, an RTX 2070S, a GTX 1060 and a Jetson TX2. This tests whether the affine-then-saturating form holds, and it locates $B^\ast$ on each device.
The third is the scheduler. Weights come from a cheap motion estimate on the incoming frame. Weights are rounded to dyadic classes, classes are packed so that each frame's batch respects $\tau$, and any batch smaller than $B^\ast$ is held over to a later frame.
The fourth is analysis. Using offline oracle weights, we compute a lower bound on achievable weighted staleness for each sequence, so every policy can be reported as a ratio to that bound. We then check whether the predicted factor-of-two rounding loss and the $B^\ast$ threshold appear empirically.
Baselines
The naive reference is full-frame YOLOX-L under the standard streaming protocol. StreamYOLO reports 31.2 streaming AP for this baseline on Argoverse-HD.
The strongest existing method is StreamYOLO itself, which reports 36.1 streaming AP on Argoverse-HD. Our detector shares its backbone and forecasting head, so any gain must come from scheduling. For whole-frame scheduling we also run shrinking-tail scheduling (Towards Streaming Perception), which reported raising Mask R-CNN from 6.2 to 17.8 streaming AP.
The second strong competitor is per-frame LASNet-style dynamic tiling. Here each frame independently thresholds tile change and recomputes the selected tiles, with the same fused kernels and no cross-frame schedule.
Two ablations isolate the key ingredients. The first keeps the patrol schedule but replaces the measured $c(B)$ with a FLOP count, which removes the hardware-aware critical batch. The second keeps the measured cost but gives each tile its own independent periodic timer, which is the zigzag analogue.
All methods share the same backbone weights, training data, forecasting head, kernel library and tuning budget, which is a grid over thresholds or budgets selected on the validation split. All are timed on the same device under the same background-load protocol. Beating StreamYOLO means a statistically reliable streaming AP gain at matched hardware, or an equal streaming AP on a weaker hardware tier, with a deadline-miss rate no higher than the baseline's.
Why not just…?
Why not just run a smaller static model, since ASAP shows lighter models win on weak hardware? This is the do-nothing-clever alternative, and ASAP's rank shuffle supports it (ASAP). We include a sweep of YOLOX sizes. The proposal only matters if tile scheduling of the large model beats the best static size on the same device. If it does not, that is a clean negative result.
Why not just greedily refresh the most stale-weighted tiles up to the frame budget each frame? This is a real threat. Greedy refresh by weighted staleness is a natural online policy and may come close to the dyadic schedule. The proposal differs from greedy in two ways that experiments can separate. One is the $B^\ast$ idle rule, which greedy lacks unless it is added explicitly; we will test greedy with and without that rule. The other is the repeating batch shapes, which allow precompiled kernels. If greedy-plus-$B^\ast$ matches our scheduler on both streaming AP and tail latency, we will report that the contribution is the cost model and the threshold, not the dyadic structure. The oracle lower bound still shows how much room any policy has left.
Why not just use FLOPs in the scheduler and rely on fused kernels to make them accurate? LASNet's own need for a separate latency model, and ShuffleNet V2's guideline that fragmented, element-wise-heavy computation is slow despite low FLOPs, both suggest that FLOPs misrank batch sizes. The FLOP-cost ablation tests this directly. The expected failure is many small refresh batches that overrun the deadline on the GTX 1060 and TX2 but not on the 3090.
Proposed Experiments
The primary benchmark is Argoverse-HD streaming AP at 30 frames per second. Secondary evaluation uses nuScenes-H under the ASAP protocol across the RTX 3090, 2070S and GTX 1060, where ASAP reports that velocity-based forecasting with BEVDepth-Sv gave about a 16% streaming mAP improvement on the GTX 1060. Tile scheduling there is applied to the image backbone only.
Alongside accuracy we report three things: measured weighted maximum staleness as a ratio to the oracle bound, the deadline-miss rate, and the 99th-percentile frame latency.
Three checks are decisive. The first is whether the fitted cost $c(B)$ has a substantial fixed term $C$ on every device. If it does not, the critical-batch argument collapses and the work reduces to LASNet over time. The second is whether the measured-cost scheduler beats the FLOP-cost ablation more on weak hardware than on strong hardware, which is the discrepancy the proposal claims to exploit. The third is whether the dyadic schedule beats independent per-tile timers in weighted staleness on scenes with many objects moving at different speeds, mirroring Afshani et al.'s weighted-site result.
A transfer check reuses the RTX 3090 profile on the Jetson TX2 without re-fitting. It measures how much accuracy is lost when the cost model is wrong, which tests the brittleness of hardware-specific lookup tables noted for NetAdapt-style methods.
References
- Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Latency-aware Spatial-wise Dynamic Networks
- A Fully Polynomial-Time Approximation Scheme for Speed Scaling with a Sleep State
- Towards Streaming Perception
- Are We Ready for Vision-Centric Driving Streaming Perception? The ASAP Benchmark
- Real-time Object Detection for Streaming Perception
- NetAdapt: Platform-Aware Neural Network Adaptation for Mobile Applications
- All You Need Is a Few Shifts: Designing Efficient Convolutional Neural Networks for Image Classification
- Polyline Path Masked Attention for Vision Transformer