Sampled Transformer for Point Sets
Authors: Shidi Li
Christian Walder
Alexander Soen
Lexing Xie
miaomiao Liu
Venue: Submitted to ICLR 2023 (2023)

Abstract: 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(n^2)$ dense attention connections. We show that it is a universal approximator for continuous set-to-set functions.  Experimental results for classification and few-shot learning on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.

Under review as a conference paper at ICLR 2023
SAMPLED TRANSFORMER FOR POINT SETS
Anonymous authors
Paper under double-blind review
ABSTRACT
The sparse transformer can reduce the computational complexity of the self- attention layers to O(n), whilst still being a universal approximator of continu- sequence-to-sequeeee
functions. However, this permutation variant operation is not appropriate for direct application to sets. In this paper, we proposed an (n)) complexity sampled transformer that can process point set elements directly without any additional inductive bias. Our sampled transformer introduces ran- dom 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 plete attention graph, and the permutation of point set elements is equivalent to randomly sampling Hamiltonian cycles. This mechanism implements Monte Carlo simulation of the ( dense attention connections. We show that it is a universal approximator for continuous set-to-sct functions. Experimental results for classification and few-shot learning on point-clouds show comparable bet- ter accuracy with significantly reduced computational complexity compared to the dense transformer alternative sparse attention schemes.
Hamiltonian cycle in the com-
INTRODUCTION
Encoding structured data has become focal point of modern machine learning. In recent years, the defacto choice has been to use transformer architectures for sequence data, egg., in lan- guage (Vaswani al. 2017) and image (Dosovitskiy al., 2020) processing pipelines. Indeed, transformers have not only shown strong empirical results, but also have been proven to be universal approximators for sequence-tor tosuuuencee functions (Yun et al., 2019). Although the standard trans- former is a natural choice for set data, with permutation invariant dense attention, its versatility is limited by the costly (nn) computational complexity. To decrease the cost, a common trick is to sparse attention, reducing the complexity from O(n²) to O(n) (Yun et al. 2020 Zaheer et al. 2020 Guo et al.) 2019). However, in general this results in an attention mechanism that is not per- mutation invariant swapping two set elements change which elements they attend. As result, sparse attention cannot be directly used for set data.
Recent work has explored the representation power of transformers in point sets plug-in mod- ule (Lee et al.) 2019), a pretraining-fintuune hierarchical structure (Zhao et al.] (202T). However, these set transformers introduced additional inductive biases to (theoretically) approach the same performance as the densely connected case in language and image processing applications. For example, to achieve permutation invariance with efficient computational complexity, previous work has required nearest neighbor search (Zhao) al. 202T) or inducing points sampling (Lee et al. 2009)). Following the above analysis, a research question naturally arises to avoid introducing unneeded inductive bias:
pipeline YYu et al.) [022 Pang et al. 2022). and with
Can (n)) complexity sparse attention mechanisms be applied directly to sets?
We propose the sampled transformer to address this question, which is distinguished from the orig- inal sparse transformer by mapping the permutation of set elements to the permutation of attention matrix elements. Viewing this permutation sampling as attention matrix sampling, the proposed sampled attention approximates O(n²) dense attention. This achieved with the proposed random element sampling and Hamiltonian self-attention. To be specific, in random element sampling the input point set is first randomly split into several subsets of n, points (Fig. [b). each of which will be processed by shared self-attention layers. In addition, sparse attention mechanism namely

---

Under review as a conference paper at ICLR 2023
(a) Dense Attention
(b) After Sampling
(c) Hamiltonian Attention
(d) Cycle Attention
(c) Swap Points
Sampled Attention
Figure I: Attention mechanisms: (a) original dense attention; (b) the attention matrix after random of sparse attention Hamiltonian (self-)attention for each subset; (d) combining all subsets (which have overlapping element per (b)) connects the individual Hamiltonian attention sub-matrices, gives cycle attention which is Hamiltonian cycle: (e) permu- tation of points permutes the elements in cycle attention matrix; (f) the resulting sampled attention, viewed as sampled Hamiltonian cycle from the edges of the complete attention graph.
element sampling; (c) a special
Hamiltonian self-attention (Fig. Ic applied reduce complexity of the subset inputs, so that n, point connections are sampled from O connections. The combination of all Hamiltonian self-attention mechanism for all subsets namely cycle attention (Fig. [Td] can be viewed Hamiltonian cycle in the complete attention graph. As result, the permutation of set elements is equivalent to the permutation of nodes in Hamiltonian cycle (Fig- [Te.. which is in fact randomly sampling Hamiltonian cycles from the complete graph thereby yielding the proposed sampled at- tention (Fig. Ifp. Finally, viewing this randomization as a Monte Carlo sample of attention pairs, repeated sampling be used to approximate the complete O(n²) dense connections. Further- more, our proposed sampled transformer is proven to be a universal approximator for set data any continuous set-to-set functions can be approximated arbitrary precision.
The contributions of this paper are summarized as follows.
We propose the sampled attention mechanism which maps the random permutation set elements to the random sampling of Hamiltonian cycle attention matrices, permitting the direct processing of point sets.
We prove that the proposed sampled transformer is a universal approximator of continuous set-to-set functions, Corollary [
Compared previous transformer architectures, the empirical results show that our pro- posed sampled transformer achieves comparable (or better) performance with less inductive bias and complexity.
2 RELATED WORK
The transformer Vaswani al. 2017 is widely used in languages (Raffel et al. 2020 Dai al.
2019 Yang et al. 2019b) and images Dosovitskiy et al. 2020 Liu et al. 2002 Touvron et al. 2021
Ramachandran 2019). For example, Raffel al. (2020) explored the transformer by unifying
2

---

Under review as a conference paper at ICLR 2023
suite of text problems to a text-to-text format; Dai et al. 2019) modeled very long-term dependency by reusing previous hidden states; Dosovitskiy et al. (2020) demonstrated that the pure transformer can be effectively applied directly sequence of image patches; and Liu et al. (2021) proposed transformer with hierarchical structure to learn various scales with linear computational complexity. In addition, the representation power of the transformer has been explored by the pre-training and
fine-tuning models (Devlin et al., 2018: Bao et al.) 2021: Yu et al. 2022 He et al. (022).
Recently, an increasing number of researchers begin to explore the representation power of the trans- former in 3D point clouds (sets) data. |ii et al. (2018) applied multi-layered dense transformers to scall-scale point clouds directly; Yang et al. (2019a) further proposed the Group Shuffle attention to deal with size-varying inputs by furthest point sampling; Han et al. (2022) aggregated point-wise and channel-wise features by directly adding two self-attention layers. To avoid the tricky tokeniza-
tion step. [ee et al. (211)) tried to deal with points directly with (mm) complexity by introducing inducing points, and proved universal approximation; Mazur & Lempitsky (202T) further proposed a hierarchical point set mapping, grouping. and merging structure with nearest neighbors defining the sparse attention mechanism. Yu et al. (2022) and Pang et al. (2022) further introduced the trans- formers the pre-training and fine-tuning pipelines the area of 3D point clouds. Last but not the least, transformers have also been widely used in other such works on 3D (point cloud) data as Liu
al. 2019at Misra al. (2021): Mao al. (2021): Fuchs al. 22000; Sander al. (2022)
Another important line of work seeks to theoretically demonstrate the representation power of the transformer by showing the universal approximation of continuous sequence-to-sequene func- tions (Yun et al.) 2019 2020 Zaheer et al.) 2020;; Shi et al., [202]] Kratsios et al., [022]. To be specific, Yun al. (2019) demonstrated the universal approximation property of the transformer; Yun et al. (2020) and Zaheer et al. (2020) demonstrated that the transformer with sparse attention matrix remains a universal approximator; Shi al.) (202I) claimed that the transformer without diag-attention is still universal approximator. Kratsios et al. (2021) proposed that the universal approximation under constraints is possible for the transformer.
In comparison with the above works, we proposes the ((n) sampled transformer a universal approximator of continuous set-to-set functions. To our knowledge, the use of approximating dense attention by sampling Hamiltonian cycle attention matrices is new.
3
PRELIMINARY
3.1 NOTATION
Given an integer a we define [a] - a1.....a). For matrix M E Raxm for l [m]] the k-th column is denoted by Mg. Given an (ordered) index set C [m] the submatrix MA Rax|Al consists of the matrix generated by concatenating the columns determined by indices in A. See the notation guide in $ in the supplementary material.
3.2 TRANSFORMER
The transformer X + ((X) Vaswani et al. 2017 Dosovitskiy et al. 2020 implements a function from point clouds to point clouds with input points self-attention layer and feed-forward layer:
Rd is formally defined by a multi-head
Head' (X) = (W) X)
as ( K
X) W
(1a)
Head" (X)
Attn( X) = X + Wo
(lb)
Head (x)
TB(X) = Attn (X + W₂ ReLU(W,Atm(>)
(1c)
where is the number of points and d is the feature dimension. Head(-) is the self-attention layer, and Attn(-) is the multi-head self-attention layer with the parameter Wo E Rdxmh Wi. W W are W Rmxd are value, key, and query parameters; W, Rexd and W2 E Rdxr layer parameters. We utilize a positional embedding E in the input X, defined by E = W,P. where P E R3x* is the (αyz) coordinate, and Wp Rdx3 is MLP layer. To
3

---

Under review as a conference paper at ICLR 2023
simplify the notation, here X X E so that all the inputs X in this paper will include the positional embedding unless specifically stated otherwise. The attention mechanism for a dense transformer is the matrix for elements/tokens, same similarity matrix/attention graph but with sparse connections instead. As tokenization may not be necessary in dealing with point clouds, for clarity we use the terminoloyy points, elements, and tokens are all to refer to points (which may be thought of as tokens in a traditional transformer context) in point cloud (set).
attention matrix (W x in Eq. la which is in fact similarity
complete attention graph. Sparse Attention also refers to the
3.3 UNIVERSAL APPROXIMATION
Let F. be the class of continuous sequence-to-sequeene functions f RRdxn + [dXx defined on any compact domain. Further define Th,ma. as the set of transformer blocks t(.) with h attention heads of each of size m, and with hidden layer width ( (Yun et al. [2019] 2020). To measure the distance between functions in F, we define the standard ép distance function by the corresponding norm:
1/p
12) - (LLi(X) 52( ((()( dx
(2)
which is clement-wise continuous (w.r.t the bp norm) for 1 S 20.
Theorem (Universal Approximation, Yun et (019)), Let 1 1 p < 30 and > then for any given f E F, there exist a Transformer network T A, such that df S.
The proof of Theorem| I makes three stages of approximations, which are chained together via the triangle inequality to give the e bound Yunn et al. 2019). In particular, C any f F is approximated by a piece-wise linear function E FF (over a discretized input space). Then @ the piece-wise linear function is approximated by modified transformer 7 where the widely used ReLU and os activation functions (as per Eq. [ are replaced by the hardmax function σи. Finally, @ it is shown
that the class of transformer T 2.14 can upproximate any regular transformer g E 2
The key step comes in the proof of the second approximation @ In Yun et al. (2019). the approx- imation is proved by showing that multi-head self-attention layers of the modified transformer can implement any contextual map 9e Rdxx m R"
Definition 3.1 (Contextual Mapping). Consider a finite set C Rddxn, map 4: + Rlxn defines contextual map if the map satisfies the following:
For any L E L,, the n entries in q L(L) are all distinct.
2. For any L, L' E L, with L + L', all entries of (LL) and (') are distinct.
Intuitively, a contextual map can be thought of as a function that outputs unique "id-values". The only way for token (column) in Rdxx to share an "id-value" (element of (LL) is to map the exact same sequence. As each token in the sequence is mapped to unique value, an appropriately constructed feed-forward neural network can map a sequence to any other desired sequence, provid- ing a universal approximation guarantee. In Yun et al. (2020), such contextual map is implemented via selective shift operators and all-max-shift operators through careful construction of multi-head self-attention layers.
4 METHODOLOGY
We propose a variation of the sparse attention transformer sampled sparse attention transformer applicable to point sets. We deviate from the typical sparse attention transformer in two ways. First, we randomly sub-sample the input point set times, with each sub-sample being evaluated through
a shared multi-head self-attention layer. Secondly, we propose a simple Hamiltonian self-attention mechanism, special case of the sparse attention mechanism, to reduce the computation complexity of considering point sets. This ultimately yields the variant of the typical sparse transformer (Eq. [ which can be interpreted as using sampled attention mechanism, as depicted in Fig. [ To study the approximation capabilities of our proposed architecture, we prove that our sampled sparse attention transformer is universal approximator of set-to-set functions.

---

Under review as a conference paper at ICLR 2023
4.1 RANDOM ELEMENT SAMPLING
For a point set input X E Rdx,, instead of directly applying the transformer attention layer to n tokens, we process / many sub-sampled inputs X' & Rddx, for E [1] and 2 S fy S n. For
simplicity, we assume that (n, 1) n. The sub-sampled inputs x can be defined by taking various column submatrices:
x X RiURT! 7(0)=11 (v mod 1),
where R!,... R' are randomly selected ordered index sets, such that [R = n, and R'RR' = for: i o j. The index element Ri denotes the first index in the ordered set R The cycle function y: [1] + [1] ensures that the edge-case of X is well defined, i.e., y())
Intuitively, the sequence of sub-sampled inputs X ,.... x' can be interpreted as a rolling window of (n, - -1)- n many sampled point set elements. Indeed, by concatenating the index sets in order, X' is sliding window of the elements with size nt and stride nt, 1 (with wrapping).
It should be noted that X can be treated as a random variable. As such a singular realization of the sampled elements can be viewed as Monte Carlo sample over the set of ordered point sequences (Metropolis & Ulam 1949). Computationally. by applying dense self-attention layer to each of the sub-sampled elements X", the total complexity of evaluating / many self-attention layer O(1 n²)) We however note that the / self-attention layers can be evaluated parallel, which yields trade-off between individual self-attention complexity O and computation time.
To gain intuition, consider the "limiting behaviours" of our random element sampling: taking n, = + 1 can be interpreted as taking the whole sequence with I 1, i.e., X' X which under dense attention would result in complexity O On the other end, if we take n, = 2, we get 1 = pairs of points X = 2; processing every such pair with dense self-attention results in n many 0(1) self-attention evaluations. Random element sampling with dense attention layers can be interpreted as instance of sparse attention, see Fig. lb
4.2 HAMILTONIAN SELE-ATTENTION
The random element sampling discussed in the previous section reduces the computational com- plexity of dense self-attention-laeers from O(n²) O(1 n²)) O(n²/1) /t) (as (n, 1) n) by processing each sampled set of points X' through individual self-attention layers. Despite this improved computational complexity, the quadratic scaling of can still be costly for point clouds.
As such, instead of evaluating each sampled element X _ x' with a dense self-attention layer, we propose a sparse attention layer. Sparse attention mechanisms can formally defined via the attention patterns {.Ax) { ke[m_]) where j E A implies that the j-th token will attend to the k-th token. We propose the use of an attention mechanism, dubbed as Hamiltonian self-attention, which is defined by the following attention patterns:
[k, {k}
ifl k <n, otherwise le T1
A
(4)
which ensures that the set of attention patterns [ARJkE[n.) define Hamiltonian path. Indeed, if we fix a subset of elements X by starting at x and following the attended elements (ignoring self-attention A E A&), we visit every token exactly once. Fig. [c shows the corresponding at- tention matrix, where the Hamiltonian path corresponds to off-diagonal elements and self-attention corresponds to the diagonal elements, respectively.
For Hamiltonian self-attention, computing the attention mechanism according to Eq. Jonly requires 2n, = O(n)) many evaluations. Thus by using our proposed sparse attention for each X ,..., x in comparison to dense attention, the computational complexity reduces from O(n²² /t²) O(n/l).
The proposed Hamiltonian self-attention mechanism is rather simple and general. For instance, in the general case sparsity patterns can be defined for each individual layer (resulting in addition superscript for each A₂). Despite this, the attention patterns {Ap ].ej.. satisfy important key as- sumptions for proving that the attention pattern will result in sparse transformer that is universal
5

---

Under review as a conference paper at ICLR 2023
approximator Yun et al. 2020, Assumption 1). In particular, by stacking (ng 1) many attention layers, our Hamiltonian self aetfnattenio will allow any element to indirectly or directly attend all other element in X'. The proposed Hamiltonian self-attention could also be viewed as a special case of window attention in Zaheer et al. (2020), where elements are linked undirectedly.
4.3 SAMPLED SPARSE ATTENTION MRANSFORMER
Given the setup of random element sampling and Hamiltonian self-attention, we can define our proposed sampled transformer for continuous set-to-set function approximation:
SHead' (x') (W.X)) X A as
[>([(W (W X
R An x W
(5a)
SHead (x')
(x(') = + Wo
(5b)
SHead"
SAuth x) = ox(xx) "g'''"""' 1000(xX' "x gxx)
(5c)
(TB(X) SAtt( + W2- ReLU (W1SAim(X)).
(5d)
(5e)
In Eq. 5c. composition is w.r.t. the induced linear maps from matrices given by Eq. 5b The learnable parameters of the sampled transformer are the same as the usual dense transformer in Eq.
As the attention pattern of each X' forms a Hamiltonian path, and each X shares an element with the proceeding (²(1), the joint attention map makes a Hamiltonian cycle path. In other words, the shared index R2(6+1) in Eq. links each individual Hamiltonian path given by Eq. 4 leading the attention matrix to form a cycle attention as shown in Fig. Td Furthermore, the permutation of elements in cycle attention corresponds to the swapping of nodes in the Hamiltonian cycle, with corresponding links and swapping of element values in the attention matrix, see in Fig. [T] As a result, the combined randomization from using random element sampling and Hamiltonian self- attention can be thought of as sampling from the set of Hamiltonian cycle graphs from the complete attention graph, resulting in the sampled attention depicted in Fig. If
Unlike dense attention, sparse attention patterns are not generally permutation invariant. Indeed, if we permute the columns of X', the elements attended according to {A]kkEn.] are not the same. As such, applying {AA [e([r.] directly to X is not valid for point clouds, which requires a per- mutation invariant operation. However, in case the sparse attention heads being applied to randomized sub-sampled element sets X' Ignoring computation, if we continue sample the ran- domized elements X' and average the resulting attention (w.r.t. the entire point set X), the attention will converge to dense attention through randomization of X', the event that any non-self-edge appears a sampled attention graph (as per Eq. 4 is cquiprobable. This also holds when fixing the order of elements while applying randomly sampled Hamiltonian cycle attention. As such, the sampled transformer can be used to approximate a permutation invariant operator, and thus be used to approximate set-to-set functions.
Of course, sampling sufficiently many realizations Hamiltonian cycle attention to converge to dense attention is impractical. Instead, in practice, re-sample the attention pattern only for each batch and epoch. Although this may seem like a crude approximation to dense attention, similar methods are successful in Dropout (Srivastava et al. 2014). which even induces desirable model regularization. Furthermore, our empirical results indicate that sampled sparse attention closely approximates the more expensive (and infeasible at the typical point set scales) dense attention.
4.4 SAMPLEED TRANSFORMER AS UNIVERSAL. APPROXIMATOR
We formally guarantee the representation power of the proposed sampled transformer by proving universal approximation for set-to-set functions. As our sampled transformer Eq. 5c is similar to dense sparse transformers presented by Yun et al. (2019 2020). we follow their framework (Sec. (..3 to prove our universal approximation property.
Corollary 1 (Sampled Transformer a Universal Approximator). There exist sampled (sparse)
Transformers that universal approximators in the sense of Theorem

---

Under review as a conference paper at ICLR 2023
Table 1: Object classification on ModelNet40. Here [ST] denotes that model adopts the standard (dense) transformer, while [T] denotes all other transformers.
Supervised Methods
Accuarcy
Scpe-Supervised Methods
Accuarcy
PointNet (Qiet
2017a
89.2%
PointNet++ Qr
2017b
90.7%
OcCo
(Wang 2021
93.0%
PointCNN
[L at. 2018
92.5%
STRI.
[Fiann 2074
93.1%
KPConv Thomas et al. 2019
92.9%
IAE
Yam el 4022
93.7%
DGCNN Wang el at. 1
92.9%
et
2022
92.1%
RS-CNN
2019b
92.9%
[ST]Point-BERT et al.
2020
93.2%
[T] PCT
Guo al
2021
93.2%
[ST]Point-MAE (Pang ct 2022
93.8%
T PVT
Zhang et al. [U2 [22
93.0%
[ST]MAF-dense (ours)
93.6%
Point Transtormer (Zhap ct al. 2021
93.7%
[T]MAE-sampled (ours)
93.7%
Transformer Yu at 2022
91.4%
To prove our Corollary, we extend the proof of Yun al. (2019) 2020) by showing that our sparse attention mechanisms with random element sampling also implement a selective shift operator. As a result, we show that the proposed sampled sparse attention transformer is universal approxi- mator in the context of set-to-set functions. See S in the supplementary material for the full proof of the universal approximation property.
5 EXPERIMENTS
We evaluate our proposed sampled attention in popular raanformer-basee frameworks well basic setting. We compare our sampled attention (Fig. If with dense attention via the pre-training and fine-tuning framework Yu et al., 2022 Pang et al. 2022). where pre-train model on ShapeNet (Chang et al., (013)) via the reconstruction task, and further evaluate the performance on two downstream fine-tuning tasks: classification and few-shot learning in ModelNet40 (Wu al.) 2015). In addition, to eliminate the influence of other factors, we compared the dense, sparse, sam- pled, and ANN attention (Definition [III) in a basic classification setting consisting of a transformer block with a single attention layer for feature aggregation, as well as minimal number of MLPs for feature mapping. Finally, we compare the sampled attention with the &NN attention in the hier- archical grouping and merging structure following the Point-Trann coint-Tranffomer (Zhao et al. 2021).
5.1 COMPARSION ON PRE- TRAINING AND FINE-TUNING FRAMEWORK
Pre-training. We adopted the masked auto-encoder (MAE) (He et al., 2022) to process the point cloud data, denoted as MAE-dense, for pre-training. This framework is the concurrent work with Point-MAE (Pang et al. and decoder network. To evaluate the effectiveness of our claimed contribution, we replace the dense-attention layer in MAE-dense with our sampled-attention layer (Fig. If while keeping the other components fixed. It is denoted as MAE-sampled.
2022 Note that MAE-dense adopts dense-attention layers in its encoder
To pre-train the MAE-dense and MAB-sampled, ShapeNet [Chang et al. 2013), which is also adopted by |ang et al. (2022); Yu et al. (2022). and develop the following training strategy. To begin with, each input point cloud consisting of 1024 points was divided into 64 groups / tokens of size 32 points each. The Furthest Points Sampling (FPS) and nearest neighbour search were adopted in tokenization (Yu et al.) 2022). Tokens were further mapped to 256-dimensional latent vectors by MLP layers and max max-poolingg In addition, we have 12 stacked transformers in the encoder (masking ratio of 70%) and I single transformer in the decoder, both with h 8, d 32 and r 256. The batch size is 64 and the epoch num- ber 300. We used the Adam W (Loshchilov & Hutter 2017) optimizer with cosine learning rate decay (Loshchilov & Hutter 2016). an initial learning rate of 0.0005, and weight decay of 0.05.
follow the standard train-test split of
The pre-trained MAE-dense and MAE-sampled models are first evaluated on the classification task in ModelNet40 (Wu et al. 2015). with the standard training and testing splits defined in Yu et al. (2022); ; Pang al. (2022) Specifically, encoder structure and weights of the pre- pre-trained MAE-dense and MAE-sampled models, followed by nax-pooling well as fully connected layer of dimension [256, 256, 40) to map the global
Classification
build the classifier by keeping the
7

---

Under review as a conference paper at ICLR 2023
Table 2: Mcan + std. dev. accuracy (%) for 10 independent Few-shot classification experiments.
Methods
5-way, 10-shot
5-way.20-shot
10-way, 20-shot
DGCNN-rand Wang et al.. 2021
31.6
40.8 4.6
19.9 +
16.9 1.5
AGCNN-OcCo (Wang et a 2021
90.6 + 2.8
92.5 + 1.9
82.9 + 1.3
86.5 2.2
Transformer-ram Yu al. 2122
87.8 + 5.2
93.3 + 4.3
84.6 + 5.5
89.4 = 6,3
Transfommer-oee Yu el al 2022
94.0 + 3.6
95.9 + 2.3
89.4 5.1
92.4 = 4,6
Point-REKK Yu et al. 2022
+.1
96.3 + 2.7
+1.0+5.4
92.7 5.1
Point-MAE (Pang
2022
96.3 + 2.5
97.8 1.8
1..6..11
95.0 3.0
MAE-dense (ours)
95.9 + 3.1
97.2 + 2.1
90.8 + 5.0
92.8 3,9
MAE-sampled (ours)
97.0 + 2.3
98.3 + 1.6
92.7 + 5,4
93.8 3.5
Table 3: Object classification accuracy (%) for different attention mechanisms in the basic setting. OM denotes out of memory.
#Points
256
512
768
1024
2048
3072
4096
8192
MLP + FC (no attention)
85.96
86.24
85.43
85.96
85.84
86.61
86.32
86.
Dense Attention
87.78
88.72
88.11
88.47
88.39
OM
OM
OM
Sparse Attention
87.09
88.03
87.54
87.74
87.58
87.42
87,42
87.58
Sampled Attention
87.34
87.93
87.66
88.03
87.82
87.18
87.46
87.73
ANN Attention
85.80
84.74
85.35
84.70
82.95
82.58
82.26
OM
token of dimension of 256 to the 40 categories. Similar to Yu et al. (022), we further data- augment the point cloud training set via random scaling and translation during training. shown in Tab. the proposed method achieved the second best performance compared with the most recent state-of-the-arn alternatives. Our sampled attention can achieve an accuracy improvement of 0.1% when compared to dense attention, while reducing the complexity from (nn²) to O(n).
Few Shot Learning The pre-trained MAE-dense and MAE-sampled models are also evaluated on a few shot learning task. Following (Sharma Kaul (2020); Wang et al. (202T); Yu al.] (2022); Pang et al. (2022). the few-shot learning adopted an k-way, m-shot training setting the Model- Net40 (Wu et al. 2015) dataset, where represents the number randomly sampled classes and the number of randomly sampled examples per class. The testing split is 20 randomly sampled unseen examples from each class. We set & E {5, 10} and m E {10, 20). and report the mean accuracy with standard deviation for 10 independent experiments. As shown in Tab, 2 our pro- posed MAE-sampled model outperformed all state-of-the-an methods on 3 out of 4 settings, while MAB-sampled consistently outperformed MAE-dense.
5.2 COMPARSION ON BASIC CLASSIFICATION SETTING
Our inputs clouds of n points with 3D coordinates position and its normal information as features. The feature and position are first transformed by two separate MLP layers with hidden dimensions [64, 256], and then added together as the input of single layer transformer with h 8, r 256, and d 32, as per Eq. [ and Eq. 5 The transformer output of Rmx256 is then summarized by max-pooling to obtain global feature with dimension of 256, followed by fully connected layer to map it to the category vector. Here we tested this basic pipeline with E (256, 512, 768, 1024, 2048, 3072, 4096, 8192) for each of the dense, sparse, kNN, and the proposed sampled attention layers, including an additional case without attention layer (MLP+Full Connected layer) as the baseline.
As shown in Tab. and Tab. 4 the model with dense attention layers achieves the best performance as it considers all (n²²) connections directly with relatively few parameters to train. However, runs out of the 24 Gigabytes memory when the number of points n 3072, due to the quadratic complexity. While both sparse and sampled transformers have computational complexity (n)), model with sampled attention outperformed the sparse one, in line with the strong theoretical guarantees we provide. We conjecture that the improvements of sampled transformer over the sparse transformer may indicate that the additional randomness (randomly shuffling points, w attention)
8

---

Under review as a conference paper at ICLR 2023
Table 4: Memory usage (Gb) for different attention mechanisms in the basic classification setting. All are trained on single RTX 3090 with 24 Gb on board RAM. OM denotes out of memory.
#Points
256
512
768
1024
2048
3072
4096
8192
MLP FC (no transformer)
0.9
0.9
0.9
1.0
1.1
1.1
1.2
1.5
Dense Attention
1.2
1.8
2.7
3.9
11.9
OM
OM
OM
Sparse Attention
1.0
1.1
1.2
1.3
1.7
2.1
2.5
4.3
Sampled Attention
1.0
1.1
1.2
1.3
1.7
2.1
2.5
4.2
KNN Attention
1.9
2.8
3.7
4.4
8.5
11.4
16.5
OM
Table 5: Classification accuracy (%) for sampled and &NN attention with hierarchical model struc- ture.
#Layers
2
4
sampled attention
74.55
88.0
90.5
91.0
91.8
kNN attention
66.23
82.8
90.1
91.0
91.4
leads to a better approximation of the (n²²) connections in a manner analogous to Dropout (Srivas- lava et al. 2014). In addition, the transformer with ANN attention layers has the worst performance, as the permutation could not extend its receptive field. Finally, the memory usage comparison in Tab. 4 shows that the dense transformer has the largest memory usage due to its O complexity. The sparse transformer and sampled transformer have comparable memory usage due to the same Onn) complexity.
5.3 COMPARSION ON HIERARCHICAL TRANSFORMER STRUCTURE
We further compare our sampled attention with ANN attention by adopting the hierarchical structure for the classification task under the framework of Zhao et al. (2021). Each hierarchical layer is obtained by FPS, followed by the nearest neighbour search the grouping, using MI.s with max- pooling for feature merging, and transformers for feature mapping. The grouping stage within each hicrarchical layer summarizes the point cloud into key (subset) points.
The total hierarchical layer number is 5, the parameters for which we chose the number & of nearest neighbours {8, 16, 16, 16, 16), strides {4, 4, 4, 4, 4), self-attention feature dimensions f22, 64, 128, 256, 512), and transformer blocks {2. 3, 4. 3}. The scalar attention (Eq. I or Eq. is adopted specifically for comparison. Results shown in Tab. dab.{]demonstrate that our sampled attention outperforms the ANN attention in line with our randomly sampled receptive field. Furthermore, the performance of the ANN layer improved greatly from / = to = 2 and from / = 2 to = 3 as its receptive field extends due to the multiple hierarchical layers. Finally, ANN with vector attention (Yu) et al. 2022) (reported in Tab. [ on the TrinnTransformer row) achieved a better performance, in line with the observation that replacing the softmax with learnable MLPs y in the transformer can easier make I:NN attention a universal approximator of continuous functions. Detailed analysis is provided $B. the supplementary material. The performance difference between scalar attention and vector attention is shown in the Tab. 7 of Yu et al. 2022), and is also analyzed in Yun al. (2020).
CONCLUSION
In this paper, we present (nn) complexity sparse transformer sampled transformer which directly handles point set data. By relating the permutation of set elements to the sampling of Hamiltonian cycle attention, we relieve the model inappropriate permutation variance. The result is sampled attention scheme that implements Monte Carlo simulation approximate a dense attention layer with a prohibitive O(n²) number of connections. To guarantee the representation power of the proposed sampled transformer, set functions. Motivated also by the strong empirical performance that our model achieves, we hope this work will help shed light the sparse transformer in dealing with data.
showed that it is universal approximator of set-to-

---

Under review as a conference paper at ICLR 2023
REFERENCES
Hangho Bao, Li Dong, and Furu Wei. Beit: Bert pre-training of image transformers. arXiv preprint arXiv:2/06. /00.02206 2021.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer. Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake Van- derPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the scikit-learn project. In ECMI. PKDD Workshop: Languages for Data Min- ing and Machine Learning. pp. 108-122, 2013.
Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. arXiv preprint arXiv:1512.03012. 2015.
Zihang Dai, Zhilin Yang. Yiming Yang, Jaime Carbonell, Quoe V Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02550 0286600 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 2018.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. /929, 2020.
Fabian Fuchs, Daniel Worrall, Volker Fischer, and Max Welling. Se transsfofoss:::s:: 3d roto- translation equivariant attention networks. Advances in Neural Information Processing Systems, 33:1970-1981, 2020.
Meng-Hap Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. Pot: Point cloud transformer. Computational Visual Media, 7(2):187-199 2021.
Qipeng Guo, Xipeng Qiu, Pengfei Liu, Yunfan Shao, Xiangyang Xue, and Zheng Zhang. Star- transformer. arXiv preprint 19Xiv:1902.09113. 2019.
Xian-Feng Han. Yi-Fei Jin, Hui- Hui-Xiin Cheng, and Guo- Buo-Qiang Xiao. Dual transformer for point cloud analysis. IEEE Transactions on Multimedia, 2022.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16000-16009, 2022.
Siyuan Huang, Yichen Xie, Song-Chur Zhu, and Yixin Zhu. Spatio-temporal self-supervised repre- sentation learning for 3d point clouds. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6535-6544 2021.
Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. Universal approxima- tion under constraints is possible with transformers. arXiv preprint arXtv:2110.03303, 2021.
Xin Lai, Jianhui Liu, Li Jiang, Liwei Wang, Hengshuang Zhao, Shu Liu, Xiaojuan Qi, and Jiaya Jia. Stratified transformer for 3d point cloud segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. $500-8509, 2022.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based ceemmutationiivaaiinn neural networks. In Interna- tional conference on machine learning, pp. 3744-3753. PMLR, 2019.
Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen. Pointenn: Convolu- tion on x-transformed points. Advances in neural information processing systems, 31, 2018.
Xinhai Liu, Zhizhong Han, Yu-Shen Liu, and Matthias Zwicker. Point2sqquence: Learning the shape representation of 3d point clouds with an attention- sequence to sequence network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 8778-8785, 2019a. 201..
10

---

Under review as a conference paper at ICLR 2023
Yongcheng Liu, Bin Fan, Shiming Xiang, and Chunhong Pan. Relation-shapp convolutional neural network for point cloud analysis. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8895-8904, 2019b.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer. Hierarchical vision transformer using shifted windows. In Proceedings the IEEE/CVF International Conference on Computer Vision, pp. 10012-10022, 2021.
Hya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.66 03988, 2016.
lya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv: 101, 2017.
Jiageng Mao, Yujing Xue, Minzhe Niu, Haoyue Bai, Jiashi Feng, Xiaodan Liang, Hang Xu, and Chunjing Xu. Voxel transformer for 3d object detection. In Proceedings of the IEEF/CVF Inter- national Conference Computer Vision pp. 3164-3173 2021.
Kirill Mazur and Victor Lempitsky. Cloud transformers: universal approach to point cloud pro- cessing tasks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10715-10724, 2021.
Nicholas Metropolis and Stanislaw Ulam. The monte carlo method. Journal of the American statis- tical association, 44(247):335-341 1949.
Ishan Misra, Rohit Girdhar, and Armand Joulin. An end-to-end transformer model for 3d object detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2906 2917, 2021.
Yatian Pang. Wenxiao Wang, Francis EH Tay, Wei Liu, Yonghong Tian, and Li Yuan. Masked autoencoders for point cloud sule-supe learning. arXiv preprint arXiv:2203. 06604, 2022.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical fea- ture learning point sets in a metric space. Advances in newral information processing systems, 30, 2017b.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21 21(110): 2020.
Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jon Shlens. Stand-alone self-attention in vision models. Advances in Neural Information Processing Systems, 32, 2019.
Michael E Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transform- ers with doubly stochastic attention. International Conference on Artificial Intelligence and Statistics, pp. 3515-3530 PMLR, 2022.
Charu Sharma and Manohar Kaul. Self-supervised few-shot learning on point clouds. Advances in Neural Information Processing Systems, 33:7212-7221, 2020.
Han Shi, Jiahui Gao, Xiaozhe Ren, Hang Xu, Xiaodan Liang, Zhenguo Li, and James Tin-Yes Yau Kwok. Sparsebert: Rethinking the importance analysis in self-attention. In International Confer- ence on Machine Learning, pp. 9547-9557. PMLR, 2021.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, (5(1):199-11953 2014.
11

---

Under review as a conference paper at ICLR 2023
Hugues Thomas, Charles R Qi, -aaa--emaauel Deschaud, Beatriz Marcotegui, François Goulette, and Leonidas J Guibas. Kpconv: Flexible and deformable convolution for point clouds. In Proceedings the the IEEE/CVF international conference computer vision, pp. 6411-64200 2019.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pp. 10347-10357. PMLR, 2021.
Mikaela Angelina Uy Quang-Hiea Hieu Pham, Binh-Son Hua, Thanh Nguyen, and Sai-Kit Yeung. Revis- iting point cloud classification: A new benchmark dataset and classification model real-world data. In Proceedings of the JEEF/CVF international conference on computer vision, pp. 1588- 1597, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- lion processing systems, 30, 2017.
Hanchen Wang, Qi Liu, Xiangyu Yue, Joan Lasenby, and Matt Kusner. Unsupervised point cloud pre-training via occlusion completion. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9782-9792, 2021.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
Saining Xie, Sainan Liu, Zeyu Chen, and Zhuowen Tu. Attentional shapecontextnet for point cloud recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4606-4615, 2018.
Yifan Xu, Tianqi Fan, Mingye Xu, Long Zeng, and Yu Qiao. Spiderenn: Deep learning on point sets with parameterized convolutional filters. In Proceedings of the European Conference Computer Vision (ECCV), pp. 87-102, 2018.
Siming Yan, Zhenpei Yang, Haoxiang Li, Li Guan, Hao Kang, Gang Hua, and Qixing Huang. Implicit autoencoder for point cloud self-supervised representation learning. arXiv preprint arXiv:2201.00785 2022.
Jiancheng Yang, Qiang Zhang, Bingbing Ni, Linguo Li, Jinxian Liu, Mengdie Zhou, and Qi Tian. Modeling point clouds with self-attention and gumbel subset sampling. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 3323 2333,,32, 2019a
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding, Advances in neural information processing systems, 32, 2019b.
Xumin Yu, Lulu Tang, Yongming Rao, Tiejun Huang, Jie Zhou, and Jiwen Lu. Point-bert: Pre-training 3d point cloud transformers with masked point modeling. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 19313-19322, 2022.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint /91i 2019.
Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and San- jiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse trans- formers. Advances in Neural Information Processing Systems, 33:13783-13794, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang. et al. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 33:17283-17297 2020.
12

---

Under review as a conference paper at ICLR 2023
Cheng Zhang, Haocheng Wan, Xinyi Shen, and Zizhao Wu. Pvt: Poxet transformer for point cloud learning. arXiv preprint arXiv:208.00076, 2021.
Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16259-16268, 2021.
13

---

Under review as a conference paper at ICLR 2023
A
NOTATIONS
continuous function
g
transformer
g
modified transformer
F
the class of continuous sequence-ro-sequeeee function
Fs
the class of continuous set-to-set function
F
the class of piece-wise constant sequence-to--eqqueee function
Fs
the class of piece- wisce-wise constant set-to-set function
T.mmar
class of (sparse) transformers with h attention heads, m head size, and hidden layer width
T m.
the class of the modified transformers with attention heads, m head size, and hidden layer width r
03
softmax activation
OH
hardmax activation norm
t
G8
grid {0, 60,6,...,1 8]dxn extend grid {-5- o........11 8)dxn
G5
number of points/elementt/tokess
point/clement/token feature size
head size
h
heads number
r
hidden layer width
8
step size
X
transformer input
x
i-th subset of transformer input ryz coordinates for point cloud (set)
P
E
positional embedding quantized transformer input
L
AL
desired output for the input L
W
value parameter in i-th single-head attention layer key parameter in i-th single-head attention layer query parameter in i-th single-head attention layer multi-head attention parameter
W
W
Wo
W1
forwafr layer parameter
W2
feed-forward layer parameter
W.
parameter for position embedding
14

---

Under review as a conference paper at ICLR 2023
query, key, and value parameter used in universal approximation proof indicator vector (1,0, O, 0) E Rd
e
In
vector with all ones (I,..., 1) E R vector with all zeros .0.....0) E R
O,
Head'())
i-th single-head attention layer
SHead (.)
i-th sparse/sampled single-head attention layer
Attn(-)
multi-head attention layer
S-ut(())
multi-head attention layer with sampled sparse attention transformer block
TB(-)
STB(.)
sampled transformer block
t(-)
series of any number of transformer blocks
ga(+)
contextual mapping selective shift operation
(;;ba, 122
b(:be)
single-head attention in selective shift operation
:c(:))
distance between two functions
B ADDITIONAL INFORMATION ON THE BASIC CLASSIFICATION SETTING
B.1 ANN TRANSFORMER
Definition B.1 (KNN Attention). For k [n]. kNN attention has the attention pattern A₁ kNN(k) for all points, where kNN(.) represents the Euclidean k-nearest neighbourhood of the input. Definition B.2 (KNN Transformer). The kNN transformer is the transformer defined in Eq. but with the KNN attention of definition
In addition, in the case of vector attention (Eq. (Zhao et al. 2021)) universal approximation holds the learnable mapping 7(-) (an MLP) universal approximator, This may helps to explain why vector attention could outperform scalar attention Tab. (Zhao et al. 2021).
Finaly, in Tab. the performance of the ANN transformer drops with the increasing number of points. This is because as the point number increase, the fix & nearest neighbor number relatively reduced. As result, the receptive field shrink. So the performance drops.
B.2 IN COMPARISON WITH INDUCTING POINTS (SET TRANSFORMER)
We additionally compared the proposed sampled attention with learnable inducting points strat- egy (Lee et al. 2019) in Tab The inducting points here implemented by simply replacing the multi-heads atte-ntnn transformer block in Eq. 5e with the Induced Set Attention Block (IS Eq. (9) of Lee et (011). And the positional embedding is added in the key and value input as our sampled attention. Our implementation of the basic classification in (.22 different from the one (Lee al. a 2019) with respect the data pre- prepprocsssnn:: our data pre-processing with Zhao al. 1)02 Yu et al. (2022). while Lee et al. (2019) follow Zaheer et al. (2017) without positional embedding. As we can see in Tab. 6, our proposed sampled attention outperformance the
line
inducting point strategy (Lee al. 2019 with linear complexity in the attention matrix.
As the performance of Lee et al. (2099) on the two implementations quite different, we further compared the sampled attention and inducting points strategy in the implementation provided by the lofficial implementation of Lee et (2019) To begin with, our proposed sampled attention could be applied to the inducting points strategy directly to reduce its complexity from O(mr) O(n),
15

---

Under review as a conference paper at ICLR 2023
Table 6: Additional object classification accuracy (%) for different attention mechanisms in the basic setting. OM denotes out of memory.
#Points
256
512
768
1024
2048
3072
4096
8192
MLP FC (no attention)
85,96
86.24
85.43
85.96
85.84
86.61
86.32
86.13
Inducting Points (Lee ct al., 2019
84.21
81.25
82.55
81.57
80.96
76.18
75.13
75.65
Stratified Strategy (Lai et al.
2022
87.21
87.
86.69
85.99
85.34
84.32
OM
OM
Sampled Attention
87.34
87.93
87.66
88.03
87.82
87.18
87.46
87.73
Table 7: Object classification in the setting of Lee et al.
2019 measured accuracy (%).
#Points
100
200
1000
2000
3000
5000
ISAB(16) + PMA
80.52
85,38
84.43
85,99
85,49
86.99
ISAB(16) PMA + sampled attention (ours)
81.25
82.65
84.15
85.04
84.48
86.49
where n the number of input points and is learnable inducting points number. Specifically, we use the sampled attention to replace the dense attention in the Induced Set Attention Block(ISAB) from Eq. of Lee al. (019). However, as the inducting points and points have different physical meanings, also the inducting points number m (query in the self-attention) is not equal to the input points number n (key and value), our Hamiltonian cycle attention could not be applied directly. We instead applied different version of sampled attention by randomly sampling two elements per row in the dense attention matrix. This is a loose version of sampled attention as no Hamiltonian cycle constructed. The results could be found in Tab. 7 As still comparable with the set transformer but with less computational complexity.
see, our proposed sampled attention
B.3 IN COMPARISON WITH STRATIFIED STRATEGY
The window-based transformer is another important branch of exploring the representation power of the transformer. Combined with the hierarchical backbone, it has been widely used in processing 2D images, languages, and 3D point clouds, such Liu et al. (2021); Lai et al. (2022). The window- based transformer is proposed to learn the cross-window relationships as well as the non-overlapping local relationship.
Here we compared our proposed sampled attention with the Stratified strategy from Figure 3 of Lai et al. (2022) in Tab. [ The Stratified strategy could be viewed as a combination of dense and sparse keys obtained by the window partition of different sizes. It is efficient design for learn- ing token relationships in the hierarchical backbone. However, in the single-layer setting, directly learning O(n²) connections in the attention matrix may be a better solution as it could reach the full receptive field. As our proposed sampled attention mechanism could estimate (n?)) connections by implementing the Monto Carlo simulation, outperformed the Stratified strategy in the basic classification setting as per Tab.
C AMORTIZED CLUSTERING WITH MIXTURE OF GAUSSIANS
We additionally tested the proposed sampled attention in 2D set datasets in the encoding-decoding framework introduced by (Lee et al.) 2019). And the task is about using neural network to learn the parameters the mixture Gaussian distribution from the input set data.
To begin with, the mixture Gaussian distribution is defined by weighted sum of & number of Gaus- sian distribution. Given a dataset X (.I,..., , the log-likelihood the mixture Gaussian distribution is defined follows:
log (X;p((X)))))) log Na diag diag(o;)))
(6)
Generally, the parameters of the mixture Gaussian distribution are inferred by maximizing the log- likelihood 0* (X) arg max log ((x;)) using Expeetation-MMxxinssstee (EM) algorithm the
16

---

Under review as a conference paper at ICLR 2023
Table 8: Amortized clustering results. The number in ISAB()) indicates the number of learnable inducting points used in ISAB as per Lee et al. (2019). The evaluation metric LLO/data is the average log- likelihood value, and LL the average log- likellihoodd value after a single EM update (implemented by scikit-learn package (Buitinck et al. 2013
Architecture
LLOkdata
LLl/data
IFF Pooling
-2,0006 = 0.0123
-1.6186 0.0042
ISAB(16) + PMA
-1,5034 + 0.0072
-1.4908 + 0.0044
ISAB(16)- PMA sampled attention (ours)
-1,5663 = 0.0074
-1.5272 + 0.0052
closed-form solution could not be inferred directly by setting the gradient equals to zero. Here we instead use the transformer to infer 0* (X).. Specifically, given the input, the neural network f outputs mixture Gaussian parameters f(x) { (x(x), ), {x)( oj (X) by maximing the log likelihood in Eq. (and replacing all parameters as functions of X).
The 2D set data X is randomly sampled from a given mixture Gaussian distribution with k 4. And the number of elements is randomly sampled from [100, 500). Namely, when setting the dimension of Gaussian distribution as 2. each sampled point could be viewed as a 2D data point, so the sampled collection is a 2D set dataset.
The baseline we compared with the Set transformer (Lee et al. 2019) with two Induced Set Attention BIock(ISAB) in the encoder, one Multi- Attention (PMA) and two Set Attention Block (SAB) in the decoder, as per the official implementation. The inducting points refer to the additional learnable points I iRmxa proposed in Eq. 9 of (Lee et al. 2019). with d dimension and m number of inducting points. Here we have a mixture usage of points, tokens, and elements to represent single sampled data point 24.
As the computation complexity of the inducting points block (ISAB) is O(nm), our sampled atten- tion may be adopted in the ISAB to reduce the computation complexity to (n). However, the number of inducting points m (regarded as the query in Lee et al. (2019)) is not equal to the num- ber of input points n (regarded key and value) (in fact inducting points and points have different physical meanings), our Hamiltonian cycle attention could not be applied directly. In fact, the dense attention matrix in the inducting points layer is different version of sampled attention by randomly sampling two elements per row in the attention matrix. This loose version of sampled attention as no Hamiltonian cycle constructed. As we can see in Tab. [ the sampled attention could be a plug-in in module to replace the dense attention in the inducting points structure with competitive performance but theoretically less computational complexity.
rather than X n. We instead applied
D TRANSFER LEARNING
We additionally included the transfer learning as a fine-tuning classification task with respect to the pre-training and fine-tuning framework in Sec. 5.1 to demonstrate that the proposed sampled transformer also has a good transfer ability. The fine-tuning task is implemented on the ScanOb- jectNN (Uy et al., (019) dataset with 2902 point clouds from 15 categories. We follow the data pre-processing and fine-tuning setting from Point-BERT (Yu et al. 2022) with the same three vari- ants: OBJ-BG, OBJ-ONLY, and PB-T50-RS. As we can see in Tab. [9] our sampled attention layer achieved a competitive performance in comparison with dense attention while reaching state-of-the- art performance.
E UNIVERSAL APPROXIMATOR PROOF
As we only changed the dense/sparse attention to the sampled attention, the steps @ and 3 in 3.3 remain the same as Yun et al. (2019) 2020) and found in the $C and F in Yun et al. 2020). Here need only cover the proof of step @
A proof of Corollary follows the steps described in 3.3
First, we have Fs(.) (+) is the class of continuous set-to-set function, and Fs(-) is the class of piece- wise constant set-to-set function.
17

---

Under review as a conference paper at ICLR 2023
Table Transfer learning on the classification task, measured by the Accuracy (%).
Methods
OBJ-BG
OBJ-ONLY
PB-T50-RS
PointNet Qi ct al. 2017a
73.3
79.2
68.0
SpiderCNN Xu ct al 201 8
77.1
79,5
73.7
PointNet++ (Qi cf al.. 70
82.3
84.3
77.9
PointCNN (Li al. 2018
86.1
85.5
78.5
DGCNN et al. 2002
82.8
86.2
78.1
BGA-DGUNN (Uy al.
2019
79.7
BGA-PN++ (Uy ct al. 2019
80.2
Point-BERg Yu et al.
2022
87.43
88.12
83.07
Point-MAE (Png ct 2022
90.02
88.29
85.18
MAE-dense (ours)
90.36 89.68
88,50
83.41
MAE-sampled (ours)
88.81
82.44
co, 3g 7
Lemma 2 (Modified Universal Approximation.). For each J Fs(6) and S such that f(x)= T(X) for all X E D.
Without loss of generality, here D [0, 1)dd, As in Yun al. 2019 2020 The proof of Lemma could then be separated into four steps:
1. Use the positional embedding E in 3.2 such that each column of the input X + Eg are in disjoint intervals.
2. The input X ++ quantized into with values {0, 60,6,.... .., n2 by series of modified feed-forward layers.
3. The contextual mapping q defined in Definition 3.1 is implemented by a series of modified
sampled multi-head self-attention layers (modified version of Eq. 5c) with the input of L.
4. Another series modified forward layers implements the value mapping such that each element in the unique id (L) is mapped to the desired output Ax.
As modified feed-forver fordord layers are all the of step 2 is available in $D.2 and E. 1 in (Yun et al. 2020). while the definition and proof step could be found in the $D.4 and E.3 in (Yun et 2020). Here we mainly explain steps and 3,
in Yun al. (020), the definition and proof
E. POSITIONAL EMBEDDING
The positional input for point sets in its zyz coordinate P E R3x" We adopted a matrix Wp Rdx3 (a permutation invariant operation) such that the input of the sampled transformer will be X - W. And there exists a case such that:
E = (n 1)1n, and E = (i 2)1n, for i E n1..
(7)
In this case, the first column will be (X + E) E [n 1, n) and (X + E), (i- 1 2, 1)d for i [2 r1). So the requirement of step 1 satisfied, that each column lies in disjoint intervals.
E.2 CONTEXTUAL MAPPING FOR STACKED MULTI-HEADS SELF-ATTENTION LAYERS
After the step 2, the quantized input L will be in the set Hg C Rdxn, such that:
Hg = (G + E E Rdxa G E Gs},
(8)
with C5 5,. 8}. Then the adaptive selective shift operation V is defined so that the learnable parameter u Rd could map u T (L) into unique scalars (ids). Finally, with the help of the all-max-shift operation Ω, the output of series of those two operations will be scalar in disjoint intervals w.r.t each column of L, as well as different inputs L and L', thereby implementing the contextual mapping in Definition. 3.1
18

---

Under review as a conference paper at ICLR 2023
Adaptive Selective Shift Operation. With 2 heads and hidden layer width modified multi-
heads attention layer, the adaptive selective shift operation (-) may be defined as:
(I': b()
V 1 (2. 11)= = L' + c 1,,11
(9a)
(L', 122)
3' (LL' = u LOL [(uT axt)" (a("""" L - bbq)
maxxEA L minjEA u" L'
if u² _ L > li2
(9b)
if u² L < bo:
where assign query, key, and value parameters as u², and we introduced the superscript / to denote different attention layers of self-attention layer With the help of hardmax, the k-th row of the attention matrix will be one-hot vectors to select the max min vector in Al.- Wo c|1 - 1 E R*.x2 is used to make sure only the first element in feature dimension are changed se in selective shift operation. Specifically, the 1, k-entity of the self-attention output reads:
v v''''; be, 1o), k Tn + c c ((''
(10)
I + (maxjeA u² L² min u²L1)) if u L $ [bl. 1/2
if be < u u <
1/2
Lixx
(11)
Without loss of generality, the sampled transformer in $. 4.3 may be viewed as a series of stacked masked attention A for [n], such that:
1 mod n) = (i, + (i 2 + mod n)}
(12a)
A (i}
(12b)
A mod n} 0,
(12c)
for & E [n]. This is in fact the n point pairs in the Hamiltonian cycle. So the stack of all the masked
attention is the cycle attention in Fig. reffeeete across the diagonal line. Then the Eq. [d will be
SAun L) = (((L,,)) (LA,,, .......................... ...
(LA,),
(13)
noting that the updated column for previous g' will be applied to the next g In conclusion, the contextual mapping holds as the masked attention A is designed to aggregate information from all elements / tokens by applying the g(-) about (n)) times, which matches the design of (Yun al., 2020).
8 -d+1), the mapping 4 (L,) u L, is bijective as all input point features L; are different with at least one element having gap of 8. In addition. without loss of generality, the order la < la <... < ln positional embedding E. Further, as each I; has 5-4 intervals, and as the tokens are disjoint with each other, we need nō- d adaptive selective operations achieve the bijective mapping of unique ids.
Now consider -d (1.8-1.8
holds as in YYun et al. 2020) because of the
First 5-d selective shift operations. The first 5-d layers are applied to the second column
(token) within 12 E [0: 5: 5-d+1 - 6]. and each selective shift operation will match one interval within b2 b 16 A3 = 21, and is empty otherwise. So all 5-d layers are only applied on the first two token embeddings, then the maximum value is l and the minimum value is lz. We have the output after those selective shift operations:
6 1 for b [0: 6: 8-d+1 8) Also A² is in fact Af {1).
1 12 + 5- (max 15
min 43) = l2 5- 122, jEAl
(14)
SEA
where with constant value 5-d in Eq.
9b Note that i, > 1 because
12 + 8 8 12)
<> (0 - () 12) 0,
(15)
which is true. So the current order becomes 1/ < 4 < ... < L < 4 < Tg So in the next 8 6-d selective shift operations, the maximum value will be 12 and the minimum will be lg.
19

---

Under review as a conference paper at ICLR 2023
Second 5 selective shift operations. (token embedding) within intervals la E
The next 8 layers will be applied the third column
Ei 0 o=; 8: EiD 0= + 8-d+1 -8 which results in
is = 11 1 1 (12
12) = 1a 1 (12 13) + 5-24(11 12).
(16)
which is again I3 > 12 because
1 ++-5-(122 13) > 122 + (5- 1)(62 - 12)) > 0.
(17)
So we have a new maximum la and new minimum 44.
Repeat after (n 1)8- operations. (n 1)5-a operations we have
The next 8d will operate the fourth column. After all
d-1
(n 1)
Σ 8 8-
S <
.......4 <.,
(18)
For j-th column, we will have the output
==41 h,
(19a)
12 = 12 + 8 (41 12),
(19b)
j-2
Σ 8
kd (ly-x - (z-k+1) 8-(1-1))(11 -22).
(19c)
And we also know the interval of each 4
4 E [nn- - 1)4 : 8: (: 1)4 + d+1 - 66]
(20)
8 d+1 - 6), 4 E (i 2)4 :0: (i- ()-2)4
(21)
with - 8<A A == Σi= 8 - < 1 < 1.2 So we have
11 1 E [(n - 1)4 - 5 d+1 +0: 6: (n 1)4 + 8 d+1 -
(22)
1, 4.444 441 E 8 8 d+1 + 5 - A + 5 --++1 8) for i E f2,3, n 11.
(23)
Then the interval of outputs
7 E [nn - 1)4, (n - 1)A
+
8-d-1
d-1 - 8]
(24)
1 E [(n 1)A8 - 2
+ 8-11 (n 1)20- 8-224+1
2d+1 -6]
(25)
i-2
i-2
7, e (i 2)4
Σ
kd A
5- d+1 8) 8 (i-- (n 1)4 --1--1) 6),
k=1
1-2
(i- 2)4 8
d+1
kd A
8- (d d+1 - 8) (1((-1) 1 - -8],
(26)
20

---

Under review as a conference paper at ICLR 2023
and to check whether intervals are disjoint or not, we take the difference between the lower bound of 1,41 and the upper bound of 1,
1
A
5
1)d A (8-id- - (n
1)A (8-4t1
-8) 5)
(27)
i-2
5 d+1
-6) -6) 2 Σ
8
kd hd (8-d+1 8)
(28)
8 16 d+1 5) - (i- 1)d (5- g-d+1 - 5)
(29)
nd 1)d
+ (n 1)6 1)8- id
A
1 + 8-
28
0 (i--
+ 28- (i-1)d + t0-id) (8 -5)
(30)
1 6-d
8-d
28-d
28 d
(1- 2)d
(n + 2)8
(1-1)d 2
+ (n -
(m-2))8tt 2)8-td id
(8-0t1 8)
8 d
8-d
(31)
2 8 (1-2)d
28-d d
(n + 2)8
d + (n - 2)8 2)8-2d 2d (0 (5-at1-0) -6)
(32)
8-d - 1
2 21-2) [-4 - (n + 2)5
d + (n - 2)5- 2d (5- - 8),
(33)
which is not guaranteed to be above 0, so the addition operations should be introduced.
Further, the adaptive shift operation is one-to one-to-one map as the map L + u L is one-to-one, and
the permutation of columns is one-to-one, and so it sufficies to prove that the map [/1 ... [n] + 4 is also one-to-one. See the detailed analysis in $F.2.3 in (Yun et al. 2022)).
Preliminaries.
As in Yun et al.
2020). the upper bound for the unique id I is:
4==4 4 +
8
id (1-) - 441-5) + 8 (1- (1) 12)
j=l
1-2
54 +0 8 d
Σ
(4 4+41 +8 (1(11)) (2)
j=1
= 4, 4. (12 41) + 8 (11 - 12)
= 8 11-0 (5 (1-1)/ - 8 3-1161 1/2 - (8-a 1)4
(34)
50- (1- 1)01 S (1-1)) 1)d ((n 1) + 8-d+1 5)
(35)
+ 5)(0 - 1) S no id 5. 58-1111)
(36)
Similarly, we have
4n S nd- -8.
(37)
Also, for any n 2 1, we have
(2n + 1)
22n + 1) 2
1)
(2n+1) 1) 2
1 n
S
S ...
(38)
2n
2n
2n
All-max-shift operations. Following (Yun et al. joint with each other, the all-max-shiff operation Q as follows:
2020 to make the interval between 4 are dis- Ruxa
- Raxn is self-attention layer defined
s'(L;c) = L L 10
(39)
The (1, k) entry of 52' (Z:c) reads
22 (L;c)),+ = LA, + cal (L;0); = In, + c max of Lj-
(40)
SEA
21

---

Under review as a conference paper at ICLR 2023
The main idea of all-max-shift operation is that, in the i-th layer, we will 'replace' the current 'column' by the maximum column within reach of sparse attention pattern A'. the next layer, the shifted max column will again be 'replaced' by the column. After n steps or layers, all the first elements of each column will be replaced by the one in the maximum column, which is the dominated value. The steps within the dominated element greater than the intervals of the whole Ln. So, for two different inputs L, they n entries are distinct, and the requirement
maximum value within reach of the shifted
2 in Definition
3.1 satisfied.
Without loss of generality, in contrast with the case of the cycle attention Eq. 12 in the adaptive selective operation, the case of the stacked sampled attention the same as in Fig. ld with / 1.
First layer of all-max-shift. The input of the first all-max-shift operation is É E Rdxx. Recall and each element is 0 < h < l2 < l3 <... < Ln < nō-nn - 6. The
that n = 1, 12, 1s.... In last inequality holds in Eq. 36 Let the output of the first layers be M The k-th element in the first row reads
M := : + 2n28-nd-
max u² L = L1,* + 2n28-nd-22 nd- L8+1 mod n jEAL
(41)
where with constant value c= bn=2d-nd-3 nd in Eq. 40 and for each column we will have u M =u= Lx 2n 2 nn--ddl
L841 mod n>
(42)
as the first element of is 1. Next, we see that u MMM is dominated by the right term 2n 2n28-nd- -nd-ndll u L8+1 mod n. which is defined by for any k.K' [m].
u² Le41 mod < v L mod + u² M < u² My.
(43)
This is because the minimum gap between u" LLt1 8, and we have
u Lb nd n8-nd 2n28nd nd-1 8,
(44)
so if we have u La+1 mod n < u L mod n. it could determine the order u² M < <u'Ma M because u La is within the minimum gap of the right term of Eq. 42 and so cannot change the overall value.
Second layer of all-max-shift. As the first layer, we define the output of this layer as M and the k-th element in the first row reads
M M1, + 2n²5-ma nd-1
max u uuM,, M3 M1, + 2n²0 nd un M mod
(45)
SEA
so for each column, we have
n" M = u" M + 2
nd- u²
M mod n
=u - + 2n2 28 1222--nd- nd 1 un" Hat1 mod n
2 (u" H8t1 mod n + 2n -n---- n²= Hat2 mod n)
u T H, + 4n 28 ud-1 1nT HEt1 mod + (2n25 nd 1) H mod
(46)
The last term domains nd M because the minimum gap of u² TuTTM M M++1 mod is at least 8, and
u² T M (2n²d nd 1 1222" u HH42 mod = = H + 4n nd --- HH+1 mod n
- )no < (1 + 2
nd < (1+ 28 2nd < (2n² 20222-nd-e -on-d-113.. 8.
(47)
The last inequality holds due
1 + 2n
< + 1+ 4n 4
(48)
2n
from Eq. 38
22

---

Under review as a conference paper at ICLR 2023
Repeat all- all-max-shifts.
After all layers get M and u ME is dominated by
(2n 8 -an--ddyy 1 max u T H = (2n 8--n-nd nd 1 1
(49)
jEA
Because the remains in u² ME have strictly upper-bound
u M (2n2d-nd-1y)) 1n
Σ
n (2n28
no nd
(50)
i
n
(2n)² (nd-nd-11) nd ind-inn- no ndd
(51)
((1 + 2n)" (2n)") (nd-nd
1o---nd-1 nd 1mm 5 & (2m2 nd -n (52)
The last inequality used (1 + 2n) (2n)* - (2n) from Eq. 38
Verifying Contextual Mapping. This matches the analysis in $1.2.5 of Yun al. 2020). As all selective-shift operations and all-max operations are bijective, and u map each column (token) of the input the unique id. the requirement in the Definition holds. As u MM are all dominated by (2n28-nd-1)j, and different inputs have different i, as l, is influenced by all [4,, 12. .n... not all columns are the same for different inputs L, and u is the unique mapping. The interval may be written
2d M [(2n28 "n (2n28 nd nm (Tn + 5)].
(53)
The upper bound holds as other terms are less than (2n28-nd-1)n in total (not the dominated term). So as we can see the interval for all u Mø are disjoint for different inputs, and the require- ment 2 in the Definition] 3.1 holds.
23


Reviews:
[{"review_id": "Yl06mU1ePIM", "reviewer": "Reviewer_cTVx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed an O(n) complexity sampled transformer that can process point set elements directly without additional inductive bias. The 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 dense attention connections. The paper shows that it is a universal approximator for continuous set-to-set functions.  Experimental results for classification and few-shot learning on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.", "summary_of_the_review": "This paper proposed an O(n) complexity sampled transformer that can process point set elements directly without additional inductive bias.  Experimental results for classification and few-shot learning on point-clouds show comparable or better accuracy with significantly reduced computational complexity compared to the dense transformer or alternative sparse attention schemes.\n\nOverall I feel this is a good paper and hopefully can be very useful for a lot of follow up works.", "strength_and_weaknesses": "+: The sampled attention mechanism which maps the random permutation of set elements to the random sampling of Hamiltonian cycle attention matrices, permitting the direct processing of point sets.\n+: It proves that the proposed sampled transformer is a universal approximator of continuous set-to-set functions.\n+: Compared to previous transformer architectures, the empirical results show that our proposed sampled transformer achieves comparable (or better) performance with less inductive bias and complexity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WdMOL_5qxfe", "reviewer": "Reviewer_AbVu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an O(n) self-attention layer based on the sparse transformer that is permutation equivariant. The paper shows that their proposed architecture is a universal approximator, and present experiments on set-input datasets.", "summary_of_the_review": "The main narrative around \"inductive biases\" is unclear to me, and the experiments lack a comprehensive comparison to O(n) attention mechanisms.", "strength_and_weaknesses": "The sparse transformer requires only O(n) computation but is not permutation invariant. This paper proposes a randomized linear-compute method that is permutation invariant in expectation and is a universal approximation of set-to-set functions.\n\nThe narrative around inductive bias is not clear to me. As the authors point out, existing works (Zhao et al, Lee et al) propose O(n) operations that are permutation invariance. Both papers prove the universal approximation property. The paper claims in the introduction that these methods “introduced additional inductive biases” and “a research question naturally arises to avoid introducing unneeded inductive bias”. Can you elaborate more on (1) why the inductive bias imposed by nearest neighbor search or learned inducing points is unneeded and (2) what evidence or intuition you have for your sampled attention having less of an inductive bias than both of these approaches?\n\nI skimmed through the theory and proofs, and I did not find any major errors.\n\nFor some of the experiments such as Tables 3 and 5, you could also consider the learned inducing point method from Lee et al as a baseline, which I think can be better suited to this problem setting compared to kNN attention.\n\nFor Table 1, 3, 5: do you have error bars?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5zWH_MKAtCA", "reviewer": "Reviewer_YJ8Q", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a novel transformer model for dealing with point set data, with the main focus on achieving linear time complexity in the attention mechanism. By utilizing the idea of random sampling-based approximation to the vanilla attention from sampled Hamiltonian cycle attention, the authors show that the proposed model can be a universal function approximator of set-to-set functions. Experiments on point cloud data are studied with comparison to several baseline methods, showing that the proposed model can achieve comparable performance with better efficiency.", "summary_of_the_review": "I believe the problem studied in this work is interesting and this work made some contributions.", "strength_and_weaknesses": "- This paper is well written and easy to follow. The motivation is clear and the overall structure is well organized.\n- It seems like the theoretical discussion on the universal approximation property is heavily based on the work of [1,2], while the authors also briefly touched on the role of contextual map. However, the definition 3.1 and the paragraph followed do not seem very self-explanatory to me and it's in fact a bit confusing about what are the novel part exactly in the proof. I wonder if the authors can provide more details on this part.\n- One major contribution of this work focuses on achieving linear time complexity on set data. However, the experiments are only conducted on point cloud data, which is a special case of set data. I wonder if the authors can provide more experiments on other set data, such as graph data, to show the generalization of the proposed model. Also, there exists a lot of works on efficient attention in the past few years, but in recent benchmarks and scaling studies, the vanilla transformer is still the best performing one. In a similar spirit, how do the authors think about the contributions of the proposed model in this context?\n\n[1] Yun, Chulhee, et al. \"Are transformers universal approximators of sequence-to-sequence functions?.\" arXiv preprint arXiv:1912.10077 (2019).\n[2] Yun, Chulhee, et al. \"O (n) connections are expressive enough: Universal approximability of sparse transformers.\" Advances in Neural Information Processing Systems 33 (2020): 13783-13794.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-0R2Szi-3GB", "reviewer": "Reviewer_V8rM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an efficient sampled transformer with O(n) complexity. The developed method splits the point set into subsets, each one being processed by a shared Hamiltonian self-attention mechanism. The proposed strategy is well-supported theoretically. The method is evaluated on ModelNet40 under self-supervised learning and few-shot learning. ", "summary_of_the_review": "This paper is well-written and the proposed method is interesting. However, more experiments are needed.\n\n== Post-Rebuttal ==\n\nIn the response, the authors respond that they do not conduct experiemnts on the large-scale data, and only on the 2048 points, due to the limited time and computational resources. Alothugh the reported results can show that the proposed method yields comparable performance in comparison with previous methods while requiring less resources, I still think it would be better to conduct comparison on large-scale data, which is important for the application of transformer on large-scale data. ", "strength_and_weaknesses": "=== strength ===\n\n1. this paper is well-written and organized clearly. \n\n2. the proposed method is efficient, according to Tab.3. the proposed method is well supported theoretically.\n\n=== weaknesses ===\n\n1. From Tab.3, we can observe that the proposed method is efficient. I would like to see the performance on large-scale point cloud, such as S3DIS and SemanticKitti for segmentation. In addition, the performance on other datasets, like ScanObjectNN is also expected to show the effectiveness. \n\n2. As the proposed method splits point sets into subsets, maybe it would be better if the authors could show the difference from the window-based transformer, like Stratified Transformer [1].\n\n[1] Lai et al., Stratified Transformer for 3D Point Cloud Segmentation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject