Video models waste most of their compute on frames that barely change, so methods that merge or drop repeated tokens can remove half the input. The catch is that the computer never sees those savings unless the low-level GPU code is fast for whatever token count is left. After pruning, that count changes from video to video and from step to step. Portable compilers and auto-tuners (search tools that try many ways of tiling and scheduling a computation on a given chip and keep the fastest) assume one fixed tensor shape, and tuning even one shape can take hours. In practice, people pad the input back to its maximum size, which throws away the savings, or they accept slow generic code.
We propose to tune kernels for a whole family of shapes by walking along the shape axis. Each shape's search starts from the best schedule found for its neighbor. A structured "perturb and re-improve" step, known as basin-hopping, lets the search escape when that inherited starting point leaves it stuck in a poor local optimum. Stuck searches are common here because GPU performance jumps discontinuously when tile sizes or pipeline depths cross hardware thresholds. The same procedure moves a tuned table from an NVIDIA GPU to an AMD GPU. The bet is that cheap warm starts plus targeted escapes can produce near-exhaustive kernel quality for every shape a pruned video model actually produces, at a small fraction of the cost of tuning each shape from scratch.
Core Claim
The claim is that the schedule search space has two properties at once. Adjacent token counts usually share an optimal schedule, or have optima close to each other, which makes warm-starting worthwhile. At a minority of shape thresholds the optimum jumps, and there plain warm-starting gets trapped. If both hold, a continuation tuner with basin-hopping escapes should match independently tuned per-shape kernels at a fraction of the tuning cost. It should also clearly beat coarse shape bucketing on the irregular shape distributions produced by temporal token compression.
Stated as an optimization, let $s$ be the post-pruning shape (tokens kept, sequence length), $c$ a kernel schedule (tile sizes, warp count, pipeline stages), and $T_h(c; s)$ the measured runtime on hardware $h$. We seek $c^\star(s) = \arg\min_c T_h(c; s)$ for every $s$ in the empirical shape distribution, under a total tuning budget, using $c^\star(s_{k-1})$ as the starting point for $s_k$.
Temporal redundancy plays two roles here. Pruning it creates the problem, because it produces ragged, slowly varying shapes. It also supplies the empirical shape trace that decides which shapes to tune and in what order. Local-optimum escape is the core mechanism. Portability is both the constraint and the test: the tuner must work unchanged on two vendors.
Why This Is Not Already Done
The closest work splits along the three directions without joining them. DyCoke merges static tokens across adjacent frames and keeps a "recycle bin" of pruned tokens that can be restored during decoding. It reports a 1.54× speedup on LLaVA-OneVision-7B, but it runs in standard PyTorch with no custom or portable kernels. Its token counts are exactly the ragged workload we target. STTS likewise selects frames and patches dynamically, reporting a 33% FLOP cut at under 0.7% accuracy loss, and it too ignores how varying shapes run on hardware. These two papers motivate the work: they show the FLOP savings exist and leave wall-clock conversion open.
On the portability side, Axe gives a unified layout abstraction that reaches cuBLAS-level throughput across NVIDIA and Trainium. The research file notes that it relies on static shapes and requires manual specialization for ragged inputs. Enhancing Transformer Performance and Portability through Auto-tuning Frameworks reports that TVM's Ansor scheduler needed nearly 30 hours for one Transformer block, and it tested only uniform, static sequences. Hawkeye shows that modern accelerator performance is discontinuous, because coupled primitives must be configured together before any speedup appears. That observation constrains our perturbation design: moving one knob at a time will look like no gain. These papers frame the cost and the shape of the search space, but none tunes across a family of dynamic shapes.
On the optimization side, Hybro alternates GPU gradient descent with structured perturbations to escape local optima in chip placement. ImprovEvolve splits search into generate, improve, and perturb steps inside a basin-hopping loop. We reuse this improve/perturb decomposition as our method. Both papers note the perturbation-size dilemma: small kicks fall back into the same basin, while large kicks reduce to random restarts. Mobahi's analysis of Gaussian continuation tracks a minimum while a smoothing parameter shrinks, and it identifies the central failure mode: the tracked minimum can bifurcate or vanish. Our "continuation" parameter is the shape rather than a smoothing width. The perturbation step is our answer to the path disappearing. To our knowledge, no work in the file applies continuation or basin-hopping to kernel tuning across dynamic shapes or across vendors.
Research Program
The workload is LLaVA-OneVision-7B with DyCoke-style temporal merging and dynamic pruning, as in the DyCoke paper. We instrument it on MVBench and Video-MME videos to record the actual trace of post-pruning shapes. These are prefill token counts and KV lengths at each decoding step. We then write the dominant kernels in Triton, which compiles to both CUDA and ROCm, following the cross-vendor practice in the fused-Triton ICU SSM work. The dominant kernels are attention over the variable-length pruned KV cache and the projection matrix multiplies over merged tokens. Triton's exposed knobs define the schedule space: block sizes, warps, stages, and split factors.
The tuner first sorts the shapes that occur by frequency-weighted proximity. It runs an exhaustive or long search on a seed shape. For each next shape, it starts from the neighbor's best schedule and runs a short local improvement measured on the device. When improvement stalls, it applies a coupled perturbation that changes tile size, pipeline depth, and warp count jointly, chosen to keep shared-memory and register occupancy feasible. It then re-improves, and accepts the result only if it beats the inherited schedule. The perturbation scale adapts: it grows when repeated kicks return to the same schedule and shrinks when kicks produce infeasible configurations. This directly addresses the dilemma Hybro and ImprovEvolve describe.
The output is a dense shape-to-schedule table plus a fallback rule for unseen shapes, which warm-starts online from the nearest table entry. Cross-vendor transfer uses the finished H100 table as the seed sequence on MI300X.
A secondary workload tests generality outside video LLMs. STTS-style dynamic frame retention on Kinetics-400 produces a different ragged distribution.
Baselines
The naive reference is DyCoke's pruning with tensors padded back to the full token count and compiled by torch.compile on each vendor. It shows how much of the FLOP savings is lost without shape-aware kernels. We run it on the same model, videos, and GPUs.
The published system reference is DyCoke as released, in standard PyTorch eager mode. On MVBench it reports a 57.5 average score against 58.0 for the full-token model, with a 1.54× inference speedup and 1.4× memory reduction on LLaVA-OV-7B (from the DyCoke paper). Our kernels are numerically equivalent up to floating-point reordering, so accuracy should match. The comparison is end-to-end latency. Beating it means a clear additional wall-clock speedup at unchanged MVBench and Video-MME scores, on both NVIDIA and AMD. We found no reported result on Lacuna for DyCoke on AMD hardware.
The strongest tuning competitor is independent per-shape search with a full budget. This means Triton's autotuning (or Ansor-style evolutionary search where applicable) run from scratch on each shape. The file reports nearly 30 hours for Ansor on one Transformer block. We define "per-shape best" as the best schedule found by this search given a generous budget. Our tuner beats it if it reaches at least 95% of per-shape-best throughput on frequency-weighted shapes while using a small fraction of total tuning GPU-hours.
The practical competitor is shape bucketing: a fixed number of buckets, each tuned independently with full budget, with shapes rounded up to the bucket boundary. We give bucketing the same total tuning GPU-hours as our method and sweep the bucket count.
Two ablations isolate the key ingredient. Pure continuation, which warm-starts but never perturbs, measures how often inherited schedules get trapped at threshold shapes. Basin-hopping without warm start, which uses random seeds with perturbation, measures how much the shape ordering itself contributes. A third ablation uses single-knob perturbations instead of coupled ones, testing Hawkeye's claim that coupled primitives must move together.
Why not just…?
Why not just pad to the maximum shape and let torch.compile handle it? Padding recomputes the very tokens that pruning removed, so the speedup is capped by the dense-model cost. Hawkeye also reports that torch.compile trails hardware-aware kernels by 1.13× geomean in BF16 even on standard workloads. The naive baseline above measures this gap directly. If padding loses little because pruned shapes cluster near the maximum, the shape traces will show it and the project's premise fails early.
Why not just bucket shapes and tune each bucket offline? This is the real threat. If optimal schedules are flat across wide shape ranges, a handful of buckets tuned from scratch will match us, and our contribution shrinks to a modest tuning-cost saving. We do not argue around this; we measure it. The first experiment checks how often the optimal schedule changes between adjacent shapes, and how much is lost by rounding up to a bucket boundary. If losses are small, we report that bucketing suffices and redirect the method toward the cross-vendor transfer setting, where every bucket must otherwise be re-tuned per chip. Bucketing should lose where optima jump inside a bucket, or where many buckets are needed and their summed tuning cost exceeds ours. The equal-budget comparison settles this.
Why not just warm-start, or just use random restarts, without basin-hopping? The two ablations answer this directly. Evidence from other domains favors guided perturbation: in Hybro, perturbation plus descent improved average rank from 4.17 to 2.67 over plain DREAMPlace, and CoRR reports simulated annealing breaking down beyond 10 dimensions. But kernel schedule spaces are small and discrete, so random restarts may be competitive. We will report the budget at which each strategy reaches 95% of per-shape-best throughput.
Why not just let an LLM agent like Hawkeye write the kernels? Hawkeye targets producing one strong kernel per operator and hardware. It does not address hundreds of runtime shapes, and calling an agent per shape is expensive. It is complementary: a Hawkeye-generated kernel could define the schedule space our tuner walks. We will treat that combination as an extension rather than a competitor.
Proposed Experiments
The first, decisive experiment characterizes the landscape before building anything elaborate. On H100 and MI300X, we exhaustively tune a sampled subset of shapes from the real DyCoke traces. For adjacent shapes, we measure the rank correlation of schedule runtimes, the frequency of optimum switches, and the slowdown from using a neighbor's optimum. High correlation with occasional sharp switches supports the method. Uniformly flat optima point to bucketing. Uncorrelated landscapes point to independent search.
The main experiment compares all baselines at matched tuning GPU-hours. It reports four quantities: kernel throughput relative to per-shape best, end-to-end prefill and decode latency on MVBench and Video-MME, the share of DyCoke's FLOP reduction realized as wall-clock reduction, and accuracy to confirm equivalence. A transfer experiment seeds MI300X tuning with the H100 table and measures GPU-hours to reach 95% of independently tuned AMD performance, testing whether cross-vendor optima are near each other or separated by the same threshold effects. The STTS-on-Kinetics-400 run checks that conclusions hold for a second ragged distribution. Finally, an unseen-shape test holds out 20% of trace shapes and compares the online fallback against nearest-bucket lookup.
References
- DyCoke: Dynamic Compression of Tokens for Fast Video Large Language Models
- Efficient Video Transformers with Spatial-Temporal Token Selection
- Axe: A Simple Unified Layout Abstraction for Machine Learning Compilers
- Enhancing Transformer Performance and Portability through Auto-tuning Frameworks
- Hawkeye: Hardware-Aware GPU Kernel Optimization with Minimal Supervision
- Escaping Local Optima in Global Placement
- ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search
- A Theoretical Analysis of Optimization by Gaussian Continuation
- From 805 ms to 23 ms: Accelerating State-Space Models for Real-Time ICU Monitoring with Fused Triton Kernels