Research map / Architectures and efficiency / Attention and transformers

RelFlexformer: Efficient Attention Transformers for Integrable Relative Positional Encodings

NeurIPS 2026 · Architectures and efficiency › Attention and transformers · approach: Linear attention approximations

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes RelFlexformers, Performer-style linear attention with arbitrary integrable 3D relative positional encoding masks applied via NU-FFT in O(L log L), evaluated on point cloud classification, segmentation and RGB-D tasks.

Problem

Efficient (sub-quadratic) linear attention struggles to incorporate general relative positional encoding (RPE) masks over irregular 3D token positions such as point clouds, and existing fast-RPE methods assume structured grids or incur O(L^2) preprocessing.

Approach

Model the RPE mask as a convolution of a modulation function f with the token point signal, and compute mask-vector products with non-uniform FFT using quadrature over frequency samples, so any integrable modulation can be plugged into Performer attention with O(L log L) cost and no explicit L x L mask.

Key results

• On ScanObjectNN classification, RelFlexformer reaches 84.45% OA vs 83.16% for Performer and 84.0% for dense Transformer.
• On ScanNet segmentation, RelFlexformer improves mIoU from 74.8 (Performer) to 76.8, versus 77.6 for the dense Transformer.
• On NYU Depth v2 RGB-D, RelFlexformer achieves 55.32 mIoU vs 54.44 for Performer and 55.6 for softmax attention.

Surprising findings

• RelFlexformer surpasses dense Transformer attention on ScanObjectNN (84.45 vs 84.0 OA) and on ScanNet++ mIoU (48.7 vs 48.2).
• Adding PointRoPE to Performer gives only marginal or inconsistent gains, and on some ScanNet and ScanNet++ metrics it slightly degrades mIoU.

Limitations

• Gains over dense Transformer are small and inconsistent across benchmarks (e.g., ScanNet mIoU 76.8 vs 77.6 dense).
• Performance is sensitive to choice of lambda and quadrature size S, with task-dependent optima.
• RGB-D warmup schedule needed because applying the RPE mask from epoch 0 gave no gain on NYU.

Experimental setup

Datasets: ModelNet40 ScanObjectNN S3DIS ScanNet v2 ScanNet200 ScanNet++ nuScenes NYU Depth v2 SUN RGB-D

Benchmarks: ModelNet40 ScanObjectNN ScanNet ScanNet200 ScanNet++ nuScenes S3DIS NYU Depth v2 SUN RGB-D

Metrics: overall accuracy mIoU mAcc allAcc

Baselines: Transformer (dense softmax attention) Performer Performer + PointRoPE STRING PointRoPE

Builds on: Performer PCT Point Transformer V3 DFormer STRING PointRoPE

Closest papers by meaning

• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding (NeurIPS 2021 · similarity 0.90)
• GTA: A Geometry-Aware Attention Mechanism for Multi-View Transformers (ICLR 2024 · similarity 0.85)
• Cameras as Relative Positional Encoding (NeurIPS 2025 · similarity 0.84)
• LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions (ICLR 2025 · similarity 0.84)
• DPPE: Rethinking Camera-Based Positional Encoding for Scaling Multi-View Transformers (NeurIPS 2026 · similarity 0.84)
• Proxyformer: Nyström-Based Linear Transformer with Trainable Proxy Tokens (AAAI 2024 · similarity 0.84)