Parallel Sequence Modeling via Generalized Spatial Propagation Network

Hongjun Wang, Wonmin Byeon, Jiarui Xu, Jinwei Gu, Ka Chun Cheung, Xiaolong Wang, Kai Han, Jan Kautz, Sifei Liu · 2025

Read Parallel Sequence Modeling via Generalized Spatial Propagation Network by Hongjun Wang, Wonmin Byeon, Jiarui Xu, Jinwei Gu, Ka Chun Cheung, Xiaolong Wang, Kai Han, Jan Kautz, Sifei Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12381.txt.

Introduction

Hongjun Wang and eight co-authors present a new attention scheme that reads images as true two-dimensional scenes instead of flattening them into lines. Their paper appeared in two thousand twenty-five. Transformers and their kin force pictures into one-dimensional order. That loses the layout of the scene and wastes compute.

Their network, GSPN, links every point to others through a line-scan that respects the grid. A stability rule keeps the signal flow steady and context-aware. For a square image, the effective path shrinks to the square root of the pixel count. Weights are learned from the input itself, with no position stamps needed. Tests top charts in image sorting and both kinds of image generation. It also sped up a big text-to-image model hugely at very high resolutions.

Catalog record

CREATORHongjun Wang, Wonmin Byeon, Jiarui Xu, Jinwei Gu, Ka Chun Cheung, Xiaolong Wang, Kai Han, Jan Kautz, Sifei Liu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12381

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Sequence Modeling via Generalized Spatial Propagation Network Hongjun Wang, Wonmin Byeon, Jiarui Xu, Jinwei Gu, Ka Chun Cheung, Xiaolong Wang, Kai Han, Jan Kautz, Sifei Liu Abstract We present the Generalized Spatial Propagation Network (GSPN), a new attention mechanism optimized for vision tasks that inherently captures 2D spatial structures. Existing attention models, including transformers, linear attention, and state-space models like Mamba, process multi-dimensional data as 1D sequences, compromising spatial coherence and efficiency. GSPN overcomes these limitations by directly operating on spatially coherent image data and forming dense pairwise connections through a line-scan approach. Central to GSPN is the Stability-Context Condition, which ensures stable, long-context propagation across 2D sequences and reduces the effective sequence length to N \sqrt{N} for a square map with N elements, which significantly enhances computational efficiency. With learnable, input-dependent weights and no reliance on positional embeddings, GSPN achieves superior spatial fidelity and state-of-the-art performance in vision tasks, including ImageNet classification, class-guided image generation, and text-to-image generation. Notably, GSPN accelerates SD-XL with softmax-attention by over 84 × 84\times when generating 16K images. Project page: https://whj363636.github.io/GSPN/ 0 0 footnotetext: \dagger Hongjun Wang was an intern at NVIDIA during the project. 1 Introduction Transformers have revolutionized machine learning, driving significant advances in fields such as natural language processing [ 8 , 50 , 83 ] and computer vision [ 24 , 82 , 65 , 10 , 74 ] . Their attention mechanisms—self-attention for in-depth context modeling and cross-attention for multi-source integration—offer exceptional flexibility in capturing intricate dependencies across data elements. Despite their impact, transformers face two core limitations. First, their quadratic computational complexity hampers efficiency at large scales, making them computationally intensive, especially when processing long context sources such as high-resolution images. Second, transformers treat data as structure-agnostic tokens that overlook the spatial coherence. This disregard for spatial structure diminishes their suitability for vision tasks, where maintaining positional relationships is crucial. To address the efficiency limitations of transformers, recent approaches have aimed to reduce computational complexity from quadratic to linear with respect to sequence length. Linear attention methods [ 76 , 75 , 33 ] either leverage kernel methods [ 15 , 75 ] , or reorder computations to exploit the associative property of matrix multiplication [ 47 , 67 ] . For instance, by changing the computation order from the standard (QK^{\top})V to Q(K^{\top}V) , the overall computational complexity can be reduced from \mathcal{O}(N^{2}) to \mathcal{O}(N) . Alternatively, State-Space Models (SSMs), such as Mamba [ 31 ] , leverage linear recurrent dynamics to capture long-range dependencies efficiently with \mathcal{O}(N) complexity. However, both methods abstract away spatial structure, a crucial element for vision tasks that rely on spatial coherence. Figure 1 : Comparison of attention mechanisms and computational efficiency. Top: Softmax attention (left), mamba (middle), and our GSPN (right). Bottom: Inference speed comparison across different input sizes on A100 GPU, demonstrating GSPN’s superior efficiency for high-resolution input. Dashed lines indicate quadratic extrapolation due to memory explosion. Global and local GSPN are detailed in Section 4.1 . One way to enhance spatial coherence is to extend 1D raster scan to 2D line scan , i.e., to perform linear propagation across rows and columns [ 84 , 62 ] . However, 2D linear propagation presents significant challenges: In 2D, scalar weights become matrices that link each pixel to its neighbors of the previous row or column, leading to accumulated matrix multiplications during propagation. If these matrices have large eigenvalues, instability may arise with exponential growth; if too small, signals may decay quickly, causing information to vanish [ 31 , 62 ] . Reducing the weights to maintain stability limits the receptive field and weakens long-distance dependencies. Balancing stability with a large receptive field remains challenging for 2D linear propagation. In this work, we introduce the Generalized Spatial Propagation Network (GSPN), a linear attention mechanism optimized for multi-dimensional data such as images. Central to GSPN is the Stability-Context Condition, which ensures both stability and effective long-range context propagation across 2D sequences by maintaining a consistent propagation weight norm. This condition allows information from distant elements to influence large spatial areas meaningfully while preventing exponential growth in dependencies, thus enabling stable and context-aware propagation essential for vision tasks. With a linear line-scan operation, GSPN parallelizes propagation across rows and columns, reducing the effective sequence length to \sqrt{N} , significantly enhancing the computational efficiency, as illustrated in Figure 1 . This makes GSPN a robust and scalable framework that overcomes the key limitations of existing attention mechanisms by inherently capturing 2D spatial structures. During propagation, GSPN computes a weighted sum for each pixel using pixels from its previous row or column, with weights that are learnable and input-dependent. Retaining key designs from [ 62 ] , GSPN uses a 3-way connection for parameter efficiency, while a 4-direction integration ensures full pixel connectivity, thereby forming dense pairwise connections through the line-scan manner. We present two variants of GSPN: one that captures global context across the entire input and another that focuses on local regions for faster propagation. These variants allow GSPN to seamlessly integrate into modern vision architectures as a drop-in replacement for existing attention modules. In addition, we introduce a learnable merger that aggregates spatial information from all scanning directions, which enhances the model’s ability to adapt dynamically to the 2D structure of visual data. Specifically, by inherently incorporating positional information through scanning, GSPN eliminates the need for positional embeddings and avoids common aliasing issues [ 93 , 20 ] . As a new sub-quadratic attention block tailored for vision, it is crucial to comprehensively benchmark GSPN to showcase its effectiveness and efficiency. To this end, we conduct extensive evaluations across a diverse range of visual tasks, including deterministic tasks like ImageNet classification, and generative tasks such as class-conditional generation (DiT) and text-to-image (T2I) generation. Our results are compelling: GSPN achieves competitive performance compared to CNNs and Transformers in recognition tasks, and surpasses SoTA diffusion transformer-based models in class-conditional generation while using only 65.6\% of the parameters. In text-to-image generation, GSPN demonstrates its sublinear scaling with pixel count, matching original performance on high-resolution tasks (e.g., 16K) while reducing inference time by up to 84\times on the SD-XL model. These findings position GSPN as a powerful, efficient alternative to traditional transformers for 2D vision tasks. 2 Related work Vision Transformers. The emergence of transformer architectures challenges the traditional dominance of CNNs [ 51 , 35 , 66 ] in computer vision. Vision Transformer (ViT) [ 24 ] pioneers this paradigm shift by processing images as sequences of embedded patches, catalyzing numerous architectural innovations [ 10 , 65 , 65 , 82 , 11 ] . Due to the versatility of attention from different modalities, Transformer-based models are also widely employed in multimodal tasks [ 38 , 54 ] . However, their quadratic computational complexity in attention mechanisms poses significant challenges for processing long sequences, limiting their broader application to high-resolution or long-context tasks. Efficient Vision Transformers. The quadratic computational complexity of the attention module catalyzes diverse optimization strategies in the field. Early approaches introduce sparse attention mechanisms [ 13 , 90 , 49 , 87 , 96 , 61 ] . To reduce the overall computational complexity \mathcal{O}(N^{2}) for computing (QK^{\top})V , parallel developments

Read the complete text