RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings

Byeongchan Kim, Arijit Sehanobish, Avinava Dubey, Min-hwan Oh, Krzysztof ChoromanskiarXiv 2026 · arXiv

TL;DR

RelFlexformers introduce a novel class of 3D Transformers that efficiently integrate Relative Positional Encodings (RPE) for unstructured, irregular 3D data like point clouds. By leveraging the theory of the Non-Uniform Fast Fourier Transform (NU-FFT), the architecture bypasses the need to materialize the full attention matrix, reducing computation complexity to $O(L \log L)$. This allows the model to match or even exceed the accuracy of standard quadratic attention mechanisms while maintaining subquadratic efficiency.

What Problem Does This Paper Address?

While attention-based Transformers excel at 3D learning tasks, standard self-attention scales quadratically ($O(L^2)$) with sequence length $L$. This creates a massive computational bottleneck for dense geometric data and large point clouds.

Linear attention alternatives, such as Performers, reduce this cost to $O(L)$ by avoiding the explicit materialization of the attention matrix. However, they struggle to incorporate Relative Positional Encodings (RPE)—a crucial inductive bias for 3D data that scales attention weights based on spatial distance. Because linear attention factorizes the kernel before computing pairwise interactions, you cannot simply apply an element-wise geometric mask. Existing subquadratic RPE methods are typically restricted to highly structured layouts like regular 1D sequences or 2D/3D grids. They fail when applied to irregular, non-equispaced 3D point clouds.

Methods

The authors introduce RelFlexformers, which utilize the Non-Uniform Fast Fourier Transform (NU-FFT) to apply arbitrary integrable modulation functions as RPE masks on unstructured 3D data.

The core mathematical insight is that applying a spatial relative position mask can be framed as a spatial convolution in the frequency domain. By using stochastic quadrature methods to approximate this continuous convolution, the authors design an algorithm called FastMultM. This method enables fast matrix-vector multiplication with the mask matrix in $O(L \log L)$ time.

This fast multiplication routine is directly injected into a low-rank, kernelized linear attention framework (like the Performer). Crucially, this formulation generalizes existing multidimensional encodings (like STRING) and can perfectly recover discrete rotational shifts like Rotary Position Embeddings (RoPE) in 1D settings.

Execution time and accuracy analysis of the FastMultM algorithm compared to standard Transformer and naive approaches.

Datasets

The RelFlexformer was evaluated across a diverse portfolio of 3D and RGB-D benchmarks:

  • Object Classification: ModelNet40 (synthetic CAD models) and ScanObjectNN (real-world scanned objects with occlusions and background clutter).
  • 3D Semantic Segmentation: ScanNet, ScanNet200 (long-tailed class distributions), ScanNet++ (high-fidelity indoor scenes), nuScenes (large-scale outdoor sparse LiDAR), and S3DIS (indoor spaces evaluated via 6-fold cross-validation).
  • RGB-D Semantic Segmentation: NYU Depth v2 and SUN RGB-D (multi-sensor indoor scenes with varying intrinsics).

Key Insights and Ideas

  • Frequency Domain Speedup for Irregular Spaces: The use of NU-FFT allows non-equispaced tokens to be processed efficiently in the frequency domain. This shifts the quadratic spatial masking problem into a subquadratic spectral multiplication problem.
  • Implicitly Learnable Prior Modulations: The quadrature coefficients and frequency samples used in the approximation can be made learnable parameters. This means the network can implicitly learn the optimal geometric modulation function directly from the data.
  • Complementary Positional Pathways: Distance-based RPE modulation (which alters interaction strength by distance) is orthogonal and highly complementary to token-level coordinate encodings like PointRoPE (which encode geometry directly into token representations). Combining both pathways yields the highest performance.
Behavior analysis of the RelFlexformer mask matrix showing smooth decay mimicking standard RBF and Laplace kernels.

Key Results

  • Memory and Scaling Efficiency: Standard Transformers encounter Out-of-Memory (OOM) errors at sequence lengths $L \ge 16k$. RelFlexformers scale gracefully up to $64k$ tokens and beyond.
  • Closing the Linear Attention Gap: On semantic segmentation tasks, replacing standard attention with a vanilla Performer significantly degrades performance (e.g., dropping mIoU on ScanNet from 77.6 to 74.8). RelFlexformer recovers this loss, boosting ScanNet mIoU back up to 76.8.
  • Surpassing Quadratic Baselines: On several challenging datasets, RelFlexformers actually outperform the standard $O(L^2)$ Transformer. For instance, on ScanObjectNN, it achieves an Overall Accuracy (OA) of 84.45% versus the Transformer's 84.0%. On ScanNet++, it reaches an mIoU of 48.7 compared to the Transformer's 48.2.
  • State-of-the-Art RGB-D Fusion: When integrated into the DFormer architecture for RGB-D segmentation, RelFlexformer outperforms the recent STRING method on both NYU Depth v2 (55.32 vs 54.96 mIoU) and SUN RGB-D (51.04 vs 50.87 mIoU) while saving approximately 70K parameter overhead.

Limitations and Future Work

The authors primarily utilize an exponential decay function ($\exp(-\lambda \|x\|)$) as their spatial modulation function throughout the experiments. While the framework mathematically supports any $L_1$-integrable function, finding the optimal modulation function for specific domains remains an open question. Furthermore, the current implementation is strictly limited to functions that possess well-defined Fourier transforms; expanding the framework to accommodate any arbitrary smooth function remains a challenge for future work.

Summary updated

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$. They lead to the new class of 3D-Transformer models, called \textit{RelFlexformers}, flexibly integrating those RPEs, and characterized by the $O(L \log L)$ time complexity of the attention computation for the $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.
BibTeX
@misc{kim2026relflexformer,
  author = {Byeongchan Kim and Arijit Sehanobish and Avinava Dubey and Min-hwan Oh and Krzysztof Choromanski},
  title = {{RelFlexformer: Efficient Attention 3D-Transformers for Integrable Relative Positional Encodings}},
  year = {2026},
  eprint = {2605.10706},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.10706},
}
Figure