RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings
Byeongchan Kim, Arijit Sehanobish, Avinava Dubey, [0.1em] Min-hwan Oh, Krzysztof Choromanski · 2026
Read RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings by Byeongchan Kim, Arijit Sehanobish, Avinava Dubey, [0.1em] Min-hwan Oh, Krzysztof Choromanski (2026) 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-2605-10706.txt.
Introduction
Byeongchan Kim and colleagues present RelFlexformers, fast focus 3D models for tied-place codes that sum. Standard models fit 3D learning poorly. Point-cloud tokens have no set order and sit at uneven gaps, pulled hard by tied places. Exact focus costs grow with the square of input size. RelFlexformers build on non-uniform Fourier transform theory, spreading fast tied-place focus from plain grids to mixed spreads in 3D space.
The models readily take in tied-place codes from any tuning rule that can be summed. Focus is worked out in near-linear time for the input length. Performer-style fast focus never builds the focus matrix, so shape tuning must fit the kernel form with fast matrix-vector products, a bar the models meet. Wide tests on many 3D data sets show quality gains from Fourier-driven focus tuning, with point clouds as a leading use.
Catalog record
| CREATOR | Byeongchan Kim, Arijit Sehanobish, Avinava Dubey, [0.1em] Min-hwan Oh, Krzysztof Choromanski |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66287 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10706
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings Byeongchan Kim, Arijit Sehanobish, Avinava Dubey, [0.1em] Min-hwan Oh, Krzysztof Choromanski Abstract We present a new class of efficient attention mechanisms applying universal 3D Relative Positional Encoding (RPE) methods given by arbitrary integrable modulation functions f f . They lead to the new class of 3D-Transformer models, called RelFlexformers , flexibly integrating those RPEs, and characterized by the O ( L log L ) O(L\log L) time complexity of the attention computation for the L L -length input sequences. RelFlexformers builds on the theory of the Non-Uniform Fourier Transform (NU-FFT), naturally generalizing several existing efficient RPE-attention methods from structured settings with tokens homogeneously embedded in unweighted grids into general non-structured heterogeneous scenarios, where tokens’ positions are arbitrarily distributed in the corresponding 3D spaces. As such, RelFlexformers can be applied in particular to model point clouds. Our extensive empirical evaluation on a large portfolio of 3D datasets confirms quality improvements provided by the NU-FFT-driven attention modulation techniques in the RelFlexformers. † † footnotetext: Correspondence to: [email protected] , [email protected] . 1 Introduction Attention-based Transformers ( 74 ) have become dominant architectures for 3D learning, but their standard form is not aligned well with point cloud (PC) data modality and other geometric data. In these settings, the input tokens are unordered, irregularly spaced in Euclidean space, and often carry strong inductive bias through relative positions 48 . This has motivated a large family of relative positional encoding (RPE) methods, which inject geometry into attention and improve performance in 3D classification and segmentation 92 . At the same time, the quadratic cost of exact attention remains a major bottleneck, especially for large point sets and dense geometric models. Efficient attention mechanisms, such as Performers 12 , offer a compelling alternative by replacing the softmax kernel with linear kernels but in the nonlinearly transformed domains, reducing the cost of attention from quadratic to linear time. However, integrating geometric modulation into such models is not straightforward. Unlike standard attention, Performers do not materialize the attention matrix explicitly, so a geometric mask cannot simply be inserted as an element-wise correction. Any viable modulation must instead be compatible with the kernelized formulation and admit fast matrix-vector products 11 . This requirement is essential: without it, the geometric bias would destroy the computational advantage that makes the architecture useful in the first place. In this work, we introduce RelFlexformers , a class of efficient 3D Transformers that incorporate a broad family of RPEs through an arbitrary integrable modulation function f . Our key observation is that the resulting masked attention operator can still be applied efficiently, provided the modulation admits a fast subquadratic matrix-vector multiplication. We provide such an implementation and show that it can be realized in O(L\log L) time for L -length sequences, using a Non-Uniform Fast Fourier Transform (NU-FFT) formulation. This allows geometric information to be incorporated directly into Performer-style attention without reverting to explicit L\times L attention computation. RelFlexformers generalize several existing efficient RPE attention methods, typically designed for structured token layouts such as regular grids or homogeneous spatial lattices. In contrast, our formulation applies to arbitrary 3D token configurations, making it well suited to point clouds, depth images (with tokens embedded into 3D spaces, for instance via lifting with the average depth signal across pixels in the patch) and other irregular geometric inputs. The resulting framework is flexible: different modulation functions induce different geometric priors, while the underlying attention computation remains efficient. We evaluate RelFlexformers on a range of 3D point cloud benchmarks for classification and segmentation. Across these tasks, the proposed NU-FFT-driven modulation consistently improves performance over strong Performer-based baselines and yields a practical route for combining geometric expressivity with subquadratic attention. RelFlexformer is closing the accuracy gap, as compared to the regular quadratic Transformer’s attention, often outperforming it. Our main contributions are: 1. We formulate a general class of 3D RPE-modulated efficient attention mechanisms based on arbitrary L_{1} -integrable functions. We derive an O(L\log L) implementation via NU-FFT, enabling fast masked attention without materializing the attention matrix (Sec. 3 ). 2. We validate RelFlexformer as a versatile, drop-in replacement across diverse backbones (PCT, PTv3, DFormer), consistently elevating baseline Performer attention across synthetic models, sparse LiDAR, and multi-sensor RGB-D data. We also show that RelFlexformer not only bridges the performance gap inherent to efficient linear attention, but actually surpasses standard O(L^{2}) Transformers on various datasets. Moreover, we show that our distance-based RPE modulation is orthogonal and highly complementary to token-level encodings like PointRoPE and can be combined together (Sec. 4 ). 2 Related Work Efficient Transformers and Kernel Attention. Standard Transformers scale quadratically, O(L^{2}) , with sequence length L 74 . To mitigate this, one line of research focuses on sparse or local attention 31 ; 4 ; 101 . Another approach uses kernel-based linear attention to rewrite the softmax operator, achieving O(L) complexity 30 . Specifically, Performers 12 replace softmax kernels with linear (dot-product) kernels, but in new spaces, obtained via nonlinear transformations of queries and keys. Those mechanisms include in particular techniques applying randomized maps (via random features) to unbiasedly approximate original softmax kernel. While efficient, these kernelized methods often struggle to integrate structured biases like RPEs without reverting to quadratic cost. 3D Point Cloud Transformers. Transformers are naturally suited for 3D point clouds due to their permutation equivariance. Architectures like PCTs 23 and Point Transformers 106 (and their successors) have achieved state-of-the-art results by applying self-attention to local neighborhoods or global point sets. However, these models typically rely on O(L^{2}) attention or local grouping heuristics to handle geometric relationships. While some models incorporate RPEs via Euclidean distances, they do not provide a mechanism for global, sub-quadratic attention that maintains a general integrable RPE mask. Separately, Point Transformer V3 (PTv3) ( 83 ) improves scalability by serializing point clouds with space-filling curves and applying dot-product attention within serialized patches. By replacing KNN-based neighborhood construction and explicit RPE with serialized neighbor mapping and sparse-convolutional conditional positional encoding, PTv3 achieves a much larger receptive field with improved speed and memory efficiency. Nevertheless, its efficiency comes from restructuring point clouds into serialization-induced local neighborhoods, rather than from a global sub-quadratic attention mechanism with a general integrable RPE mask. Relative Positional Encodings (RPE). RPE enhances Transformers by encoding the spatial relationship between tokens 66 . Recent advances include ALiBi 55 , RoPE 68 and Fourier Positional Encoding 28 , which improve extrapolation. However, most RPE schemes assume a 1D sequence or 2D and 3D grid structures 63 . In 3D point clouds, the RPE should ideally depend on the continuous distance f(\mathbf{x}_{i}-\mathbf{x}_{j}) . Luo et al. 49 demonstrated that 1D RPE can be computed in O(L\log L) via FFT by exploiting Toeplitz structures. 11 provides the first framework to incorporate arbitrary RPE masks in the Performer-style attention, provided the mask matrix supports fast (sub-quadratic) matrix vector multiplication . This idea was utilized in 13 , where relative positional encodings (RPE) are implemented using a tree-based mask. The original graph is approximated by a spanning tree, allowing the mask to be applied efficiently via fast matrix–vector multiplication, and thereby integrated into the Performer architecture. 60 uses the graph random features (GRF) to provide inductive