High-resolution segmentation of satellite scenes, street scenes, or 4K video runs into two problems at once. A vision transformer (a network that splits the image into small square patches, called tokens, and lets every token exchange information with others) costs memory that grows with the number of tokens. The usual escape is to cut the image into tiles, which leaves visible seams and broken predictions where tiles meet. Methods that skip computation on easy regions instead tend to change the number of tokens from image to image. That breaks the spatial grid dense decoders expect, and it produces irregular memory access that edge accelerators handle poorly. Classical compressed sensing solved a close cousin of this problem decades ago. In a wavelet decomposition, which splits an image into a coarse version plus detail corrections at successively finer scales, the detail that matters forms a connected tree. If a coarse region is smooth, its finer descendants are smooth too, so computation can be withheld from whole subtrees.
We propose to build a windowed vision transformer that represents the image as a dense coarse feature map plus sparse fine-scale residuals, the way a wavelet represents an image as an approximation plus sparse detail. Fine-scale windows are computed only on a rooted subtree of a quadtree, and each level has a fixed budget of windows. Every window that is not computed is filled with its upsampled parent instead of being dropped. Two consequences follow, and both are the point. First, because each level has a fixed budget, peak memory and tensor shapes are known before the image arrives, which is what edge compilers need. Second, the filled windows give every computed window real neighboring context at the same scale, so there are no tile seams and no hard cutoffs between computed and skipped regions. The core claim is that this "fill from parent, compute residual on a budgeted tree" design matches dense or tiled accuracy on ultra-high-resolution segmentation with a hard, input-independent memory ceiling, and that it shows measurably fewer boundary errors than flat window pruning or prior-gated sparse refinement at the same compute.
What exists and where the gap is
Hierarchical sparsity supplies the method. The sparsity in levels model of The benefits of acting locally assigns each scale its own sparsity budget and thresholds locally per level. Its recovery guarantees for this local thresholding do not depend on the number of levels, and it shows that a single global top-$s$ selection lets high-energy bands starve fine detail. We reuse this per-level budgeting directly. Compressive Imaging Using Approximate Message Passing and a Markov-Tree Prior shows that modeling persistence across scales buys nearly 3 dB over a tree-ignorant reconstruction. Convex Approaches to Model Wavelet Sparsity Patterns encodes the same parent-child coupling convexly. Both motivate the prior, but neither touches neural feature computation. Model-based Sketching and Recovery with Expanders supplies the linear-time dynamic-programming projection onto tree-structured supports, which we adopt as our window selector.
The closest neural work splits into three camps, and each is missing one piece. Quadtree Attention for Vision Transformers routes each query coarse-to-fine through top-$K$ parent regions to make attention linear. However, it sparsifies which keys a query sees, not which tokens are computed: every fine token is still materialized. Its authors also note that dense kernels can beat it in wall-clock time, and it was not tested at 4K. SparseViT prunes whole $7\times 7$ windows so the remaining work runs as dense batches. This is the hardware lesson we keep. Its selection, however, is flat per layer by activation magnitude, with no cross-scale coupling and nothing done about context lost next to pruned windows. SparseMat gates full-resolution sparse convolutions with a low-resolution prior network, but any boundary the prior misses can never be recovered later. IdleViT avoids irreversible loss by keeping skipped tokens in the sequence as identity pass-throughs. That is the right instinct, but it means storing every full-resolution token, which is exactly what fails at 4K.
On the segmentation side, BPT merges homogeneous patches by density-peak clustering within one scale and says clustering overhead on edge devices is open. GPWFormer uses invertible wavelet downsampling inside a heavier dual-branch model. On the seam side, Continuous Patch Stitching shows that seams come from padding hallucinating context at tile edges, and it removes them by giving each tile exactly the context its receptive field needs. That principle constrains our design: computed windows must see true neighboring features, not padding. CPS derives this only for fixed-receptive-field convolutions with uniform dense compute.
Our design differs from all of these on one specific axis. Skipped regions are neither removed (SparseViT, Quadtree, SparseMat) nor kept at full cost (IdleViT). They are represented cheaply by the parent's upsampled features, as a zero wavelet detail coefficient is. The set of computed regions is a rooted subtree with fixed per-level sizes.
Core Mechanism
Let $f_\ell$ be the feature map at quadtree level $\ell$, where level 0 is a dense coarse pass over a downsampled image that fits in memory. Let $U$ be learned upsampling by a factor of two, and let $R_\ell$ be a stack of windowed transformer blocks at level $\ell$. Let $M_\ell$ be a binary mask over level-$\ell$ windows. Each level is then built as
$$f_\ell = U(f_{\ell-1}) + M_\ell \odot R_\ell\big(U(f_{\ell-1}),\, x_\ell\big),$$
where $x_\ell$ is the input image patch embedding at that resolution. $R_\ell$ runs only on windows with $M_\ell=1$, but its attention halo reads keys and values from all neighboring windows of $U(f_{\ell-1})$, whether they were computed or filled. Following CPS's logic, the halo width is set to cover the attention neighborhood of a window, so no computed window ever sees padding.
The masks are chosen jointly by solving
$$\max_{M_1,\dots,M_L} \sum_{\ell}\sum_{w} M_\ell(w)\, a_\ell(w) \quad \text{s.t.}\quad M_\ell(w)\le M_{\ell-1}(\mathrm{parent}(w)),\ \ \textstyle\sum_w M_\ell(w)=s_\ell .$$
Here $a_\ell(w)$ is a window score, the first constraint makes the selection a rooted subtree, and $s_\ell$ is a fixed per-level budget. The score combines two signals. One is the uncertainty of the coarse prediction, as in SparseMat. The other is the energy of Haar wavelet detail coefficients of the raw input inside the window. That second signal is nearly free to compute and can flag thin structures, such as roads and building edges, that the coarse network blurred away. This is our answer to SparseMat's unrecoverable-miss problem.
The objective is solved by the tree dynamic program of the expander-sketching paper, which runs in linear time in the number of windows. Because each $s_\ell$ is fixed, every level executes as a dense batch of exactly $s_\ell$ windows. Peak activation memory is therefore bounded by the coarse map plus $\max_\ell s_\ell$ windows with their halos, regardless of image content. Training uses a straight-through relaxation of the masks with budgets sampled at random, as in SparseViT's sparsity-aware adaptation, so that one model can be deployed at several memory ceilings.
Research Program
The work has three parts. First, we build the model on a Swin-Tiny-style windowed backbone with three or four quadtree levels above the coarse pass. Fine levels stream window batches through a fixed-shape kernel, and we export it to an edge runtime on a Jetson-class device. Second, we study where the budgets $s_\ell$ should go. Sparsity in levels predicts that per-level budgets beat a global budget when detail energy is unevenly distributed across scales. We test this by sweeping budget allocations at fixed total compute, and we also fit budgets per dataset, since road networks and building footprints have very different detail statistics. Third, we characterize seams directly rather than only through mIoU. We measure prediction disagreement and boundary F1 in narrow bands along two kinds of interface: the image-tile lines a tiled baseline would use, and the interfaces between computed and filled windows in our model. We also measure consistency against a dense full-resolution model on crops small enough for the dense model to fit.
Baselines
The naive reference points are two. One downsamples the full image until a dense Swin-Tiny segmenter fits in memory. The other tiles the full-resolution image with 25% overlap and fuses predictions, following the overlapping-grid recipe of The Power of Tiling for Small Object Detection. That paper reports that tiling raised VisDrone mAP from 11% to 36% for a lightweight detector. Tiling is therefore a serious competitor, not a strawman. Both naive baselines use the same backbone, pretraining, and training schedule as our model. Our model beats them if it matches tiled accuracy at lower measured latency and memory, and if it beats downsampling in accuracy at equal memory.
The strongest existing method on our main benchmarks is BPT. It reports 76.6% mIoU at 2074 MB GPU memory on DeepGlobe, 77.1% mIoU on Inria Aerial, and 78.5% mIoU on Cityscapes. GPWFormer reports 75.8% mIoU at 2380 MB on DeepGlobe and is the wavelet-based comparison. We compare against BPT's published numbers using its evaluation protocol, and we retrain it with our backbone if code permits. Beating it means reaching at least 76.6% DeepGlobe mIoU below 2074 MB peak memory, or matching its accuracy at substantially lower memory and edge latency. No reported result was found on Lacuna for BPT or GPWFormer latency on edge hardware, so we measure both ourselves on the same device.
The strongest sparsity competitor is SparseViT. It reports a 1.3× speedup on Cityscapes over dense Swin-T but no Cityscapes accuracy figure in the file. We reimplement it on the identical backbone and compare at matched GMACs and matched peak memory, with an equal search and tuning budget. Its evolutionary layerwise search gets the same number of GPU-hours as our budget sweep.
Four ablations isolate the ingredients. Replacing parent-fill with zeroing skipped windows tests the seam claim. Replacing tree projection with per-level flat top-$s_\ell$ selection tests whether the tree constraint matters at all. Removing the raw-wavelet score, leaving coarse uncertainty only, tests the recovery claim. Setting the halo to zero tests the context claim.
Why not just…?
Why not just run SparseViT's flat window pruning at full resolution? Flat pruning chooses windows by activation magnitude within each layer and leaves pruned windows empty. The file notes that SparseViT has no mechanism for context next to pruned windows. Flat pruning also gives no guarantee that a fine-scale window's surroundings carry meaningful features. Our zero-fill ablation is essentially SparseViT's treatment of skipped regions inside our architecture. If it matches parent-fill on seam-band boundary F1, then parent-fill is not doing the work and we will say so. Separately, the flat top-$s_\ell$ ablation is a real threat to the tree constraint. If per-level flat selection matches tree projection, we drop the tree and keep per-level budgets plus parent-fill, which is simpler and still distinct from SparseViT's design.
Why not just gate full-resolution refinement with a low-resolution prior, as SparseMat does? This works well for matting, where SparseMat reports 7.90 MAD on HHM2K. But it cannot recover structure the prior misses, and roads one or two pixels wide at satellite resolution are exactly what a downsampled prior misses. The coarse-uncertainty-only ablation reproduces this policy inside our model. We additionally report recall of thin-structure pixels in DeepGlobe road extraction separately from overall mIoU. As a cross-domain check, we train our model on HHM50K and compare against SparseMat's 7.90 MAD on HHM2K.
Why not just use overlapping tiles with an efficient dense model? Tiling is simple, hardware-friendly, and effective. Its costs are duplicated compute in the overlaps and heuristic fusion at seams. If our model cannot beat 25%-overlap tiling in wall-clock latency on the edge device at equal accuracy, the sparsity is not paying for itself on real hardware. That outcome would be a negative result we would report. The seam-band metrics will show whether tiling's fused seams are measurably worse than our filled interfaces.
Proposed Experiments
The main experiments train on DeepGlobe land cover and Inria Aerial, using Inria's city-held-out split, and use Cityscapes as a third, non-aerial check. We report mIoU, seam-band boundary F1, peak GPU memory, and latency on both a desktop GPU and a Jetson-class device. Every comparison uses matched backbones and matched GMACs. The decisive checks are three. First, at the budget that keeps peak memory below BPT's 2074 MB on DeepGlobe, our model reaches or exceeds 76.6% mIoU. Second, the parent-fill model shows lower prediction disagreement than both zero-fill and overlap tiling in the seam bands, and it agrees with dense full-resolution predictions on crops where the dense model fits. Third, memory and latency stay flat when we vary image content at fixed resolution, while SparseViT-style dynamic selection and BPT clustering vary. This flatness is the edge-deployment property that a fixed-shape design is supposed to buy.
A clean failure of the second check would show that boundary continuity needs more than cheap filled context. A failure of the tree-versus-flat ablation would narrow the contribution to per-level budgets with parent-fill. Either outcome is informative.
References
- The benefits of acting locally: Reconstruction algorithms for sparse in levels signals with stable and robust recovery guarantees
- Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
- Convex approaches to model wavelet sparsity patterns
- Model-based Sketching and Recovery with Expanders
- Quadtree Attention for Vision Transformers
- SparseViT: Revisiting Activation Sparsity for Efficient High-Resolution Vision Transformer
- Ultrahigh Resolution Image/Video Matting with Spatio-Temporal Sparsity
- No Token Left Behind: Efficient Vision Transformer via Dynamic Token Idling
- Ultra-High Resolution Segmentation via Boundary-Enhanced Patch-Merging Transformer
- Guided Patch-Grouping Wavelet Transformer with Spatial Congruence for Ultra-High Resolution Segmentation
- Continuous Patch Stitching for Block-Wise Image Compression
- The Power of Tiling for Small Object Detection