# Sampled Transformer for Point Sets

arXiv: https://arxiv.org/abs/2302.14346 · HTML: https://mlsanity.com/paper/2302.14346/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 52 references that are in the map.
- First posted on arXiv 28 Feb 2023.

## Builds on (most cited first, 30 of 42)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [ShapeNet: An Information-Rich 3D Model Repository](https://mlsanity.com/paper/1512.03012/) (2015)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [BEiT: BERT Pre-Training of Image Transformers](https://mlsanity.com/paper/2106.08254/) (2021)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Point Transformer](https://mlsanity.com/paper/2011.00931/) (2020)
- [KPConv: Flexible and Deformable Convolution for Point Clouds](https://mlsanity.com/paper/1904.08889/) (2019)
- [PointCNN: Convolution On X-Transformed Points](https://mlsanity.com/paper/1801.07791/) (2018)
- [PCT: Point cloud transformer](https://mlsanity.com/paper/2012.09688/) (2020)
- [Point-BERT: Pre-training 3D Point Cloud Transformers with Masked Point Modeling](https://mlsanity.com/paper/2111.14819/) (2021)
- [SE(3)-Transformers: 3D Roto-Translation Equivariant Attention Networks](https://mlsanity.com/paper/2006.10503/) (2020)
- [Stand-Alone Self-Attention in Vision Models](https://mlsanity.com/paper/1906.05909/) (2019)
- [Revisiting Point Cloud Classification: A New Benchmark Dataset and Classification Model on Real-World Data](https://mlsanity.com/paper/1908.04616/) (2019)
- [Masked Autoencoders for Point Cloud Self-supervised Learning](https://mlsanity.com/paper/2203.06604/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Relation-Shape Convolutional Neural Network for Point Cloud Analysis](https://mlsanity.com/paper/1904.07601/) (2019)
- [An End-to-End Transformer Model for 3D Object Detection](https://mlsanity.com/paper/2109.08141/) (2021)
- [SpiderCNN: Deep Learning on Point Sets with Parameterized Convolutional Filters](https://mlsanity.com/paper/1803.11527/) (2018)
- [Voxel Transformer for 3D Object Detection](https://mlsanity.com/paper/2109.02497/) (2021)
- [Unsupervised Point Cloud Pre-Training via Occlusion Completion](https://mlsanity.com/paper/2010.01089/) (2020)
- [Spatio-temporal Self-Supervised Representation Learning for 3D Point Clouds](https://mlsanity.com/paper/2109.00179/) (2021)
- [Stratified Transformer for 3D Point Cloud Segmentation](https://mlsanity.com/paper/2203.14508/) (2022)

## Built on by (most cited first, 1 of 1)

- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)

## Abstract (arXiv)

The sparse transformer can reduce the computational complexity of the self-attention layers to O(n), whilst still being a universal approximator of continuous sequence-to-sequence functions. However, this permutation variant operation is not appropriate for direct application to sets. In this paper, we proposed an O(n) complexity sampled transformer that can process point set elements directly without any additional inductive bias. Our sampled transformer introduces random element sampling, which randomly splits point sets into subsets, followed by applying a shared Hamiltonian self-attention mechanism to each subset. The overall attention mechanism can be viewed as a Hamiltonian cycle in the complete attention graph, and the permutation of point set elements is equivalent to randomly sampling Hamiltonian cycles. This mechanism implements a Monte Carlo simulation of the O(n2) dense attention connections. We show that it is a universal approximator for continuous set-to-set functions. Experimental results on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.