REOrdering Patches Improves Vision Models
Authors: Declan Kutscher
David M. Chan
Yutong Bai
Trevor Darrell
Ritwik Gupta
Venue: NeurIPS 2025 poster ()
Keywords: long sequence model
tokenization
Primary area: deep_learning
TL;DR: The way we rasterize images to 1D sequences to feed into long sequence models is sub-optimal! We show that orders other than row major can be better, and provide an RL method to learn the optimal ordering.

Abstract: Sequence models such as transformers require inputs to be represented as one-dimensional sequences. In vision, this typically involves flattening images using a fixed row-major (raster-scan) order. While full self-attention is permutation-equivariant, modern long-sequence transformers increasingly rely on architectural approximations that break this invariance and introduce sensitivity to patch ordering. We show that patch order significantly affects model performance in such settings, with simple alternatives like column-major or Hilbert curves yielding notable accuracy shifts. Motivated by this, we propose _REOrder_, a two-stage framework for discovering task-optimal patch orderings. First, we derive an information-theoretic prior by evaluating the compressibility of various patch sequences. Then, we learn a policy over permutations by optimizing a Plackett-Luce policy using REINFORCE. This approach enables efficient learning in a combinatorial permutation space. _REOrder_ improves top-1 accuracy over row-major ordering on ImageNet-1K by up to 3.01% and Functional Map of the World by 13.35%.

REOrdering Patches Improves Vision Models
Declan Kutscher
David M. Chan?
Yutong Bai
Trevor Darrell
Ritwik Gupta²
University of Pittsburgh
University of California, Berkeley
Abstract
Sequence models such as transformers require inputs to be represented as one- dimensional sequences. In vision, this typically involves flattening images using a fixed row-major (raster-scan) order. While full self-attention is permutation- equivariant, modern long-sequence transformers increasingly rely on architectural approximations that break this invariance and introduce sensitivity to patch ordering. We show that patch order significantly affects model performance in such settings, with simple alternatives like column-major major or Hilbert curves yielding notable accuracy shifts. Motivated by this, we propose REOrder, two-stage framework for discovering task-optimal patch orderings. First, we derive an information- prior by evaluating the compressibility of various patch sequences. Then, we learn a policy over permutations by optimizing Plackett-Luce policy using REINFORCE This approach enables efficient learning in a combinatorial permutation space. REOrder improves top-1 accuracy over row-major ordering ImageNet- I by up to 3.01% and Functional Map of the World by 13.35%.
1 Introduction
Autoregressive sequence models have become the backbone of leading systems in both language and vision. These models operate on images by first converting their 2-D grid structure into a 1-D sequence of patches. Conventionally, row-major order is used for this linearization under the assumption that full self-attention is utilized by the model. As self-attention, augmented with positional embeddings, permutation--equiaaiiie the exact patch order has been treated inconsequential.
However, this assumption does not hold in the context of modern, long-sequence models which introduce strong inductive biases such as locality [1]. recurrence [2], input-dependen state dynamics [3] that are sensitive to input ordering. Through mechanisms such as sparse attention via masking summarizing early parts of long-sequence into latent representations, these methods are able to model long-sequences a computationally tractable fashion. However, these design choices introduce strong dependency patch ordering, something that has previously been overlooked.
In this work, we demonstrate that merely swapping the row-major scan for an alternative, such as column-major Hilbert curves, yields measurable accuracy gains across multiple long-sequence backbones. Further, we introduce REOrler, a method to learn an optimal patch ordering. REOrder first approximates which patch ordering may lead to best performance and then learns rank patches in order importance with reinforcement learning. Specifically, to convert the 2-D image into 1-D sequence, first quantify the compressibility resulting from each of six different patch orderings. Then, a Plackett- ranking model initialized with the least compressible ordering and further trained minimize classification loss with REINFORCE. REOrder improves performance ImageNet- K by up to 3.01% (+0.23%) and Functional Map of the World by 13.35% (+0.21%). Code and animations available on the project page.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Major
Major
Hilbert
Spiral
Diagonal
Figure Visualizations of alternate patch sequence orderings. Six different patch orders row-major, column-majjr, Hilbert curve, spiral, diagonal, and aakke-are shown as trajectories over a 14 x 14 grid of patches. Each trajectory begins at the red dot and progresses to the black dot, illustrating the 1-D ordering imposed the 2-D patch grid.
2 Related Works
Transformers as sequence models for vision. The concept of treating visual data as linearized sequences for generative modeling and other tasks has been explored for some time, with early work using models like LSTMs on sequences of visual frames [4]. Building on the success of transformers in image-sequence modeling, the Image Transformer [5] adapted this architecture to single images by dividing each image into patches and processing these patches as 1-D sequence. To manage the computational cost for images, the original Image Transformer employed self-attention mechanisms constrained to local neighborhoods of patches. The Vision Transformer (ViT) [6] expanded this attention approach, applying global self-attention over the entire sequence of image patches. However, this global attention mechanism, while effective, an O(n²) operation in computation and space w.r.t. the number of patches, becoming computationally prohibitive for long-sequences. To overcome this challenge and enable the application of transformers to larger images, subsequent research has developed various strategies, including hierarchical tokenization and more efficient attention mechanisms. Hierarchical tokenization, for instance, involves processing images at multiple scales to reduce the sequence length at higher levels. Gupta et al. [7] show how such hierarchical tokenization can be used for tractably modeling the resulting pong-sequence.. Motivated by this history of linearizing 2-D images into 1-D sequences for transformer processing and the methods developed to handle the resulting sequence length and computational complexity, in this work, we explore whether the specific order in which 2-D image is converted to 1-D sequence matters for model performance.
Long-sequence vision models. As established, the quadratic computational cost of full self- attention with respect to sequence length makes processing long-sequences of patches very expensive for standard Vision Transformers. To address this, significant research has focused developing efficient transformer architectures and long-sequence models that reduce this complexity, such as Sparse Attention [8], Longformer []], Transformer-XL. [2], and Mamba [3, 9]. While making modeling tractable, these methods often introduce specific inductive biases in how they process sequences, potentially making them sensitive the order of the input tokens (which we discuss further in Section 3.3). In this work, we study the effect of patch ordering on Longformer, Transformer- XL, and Mamba, demonstrating that the inductive biases inherent in these different long- -equence modeling approaches lead to substantial accuracy variance across different patch orders.
Patch order sensitivity. Qin et al. [10] provided in-depth study of the self-attention mechanism, establishing its property of permutation equivariance. However, a comparable analysis for long- sequence models that process vision tokens remains largely unexplored. This gap is significant, especially when considering findings from NLP, where studies like [11] revealed that long context models tend to neglect tokens in the middle of a sequence. Motivated by these observations and the underexplored nature of token ordering in long visual sequences, our work aims to investigate these effects. While some initial work in vision, such as ARM [9], has touched upon sean order for Mamba models (settling on small, row-wise clusters), this exploration did not comprehensively cover the wider space possible orderings. Our research addresses this limitation by more rigorously examining the search space through experiments with six different orderings across multiple sequence models. Furthermore, move beyond predefined arrangements, our method, RFOrder, employs reinforcement learning to explore the space of possible permutations for the patch sequence.

---

Learning to rank with reinforcement learning. The foundation of learning to rank from pairwise comparisons was established by Bradley and Terry [12] who proposed a probabilistic model to estimate item scores via maximum likelihood. More recent work has extended learning to rank with reinforcement learning frameworks, particularly in information retrieval [13] and recommendation systems [14]. Wu et. al. [15] assign importance scores to image tokens based on their impact on CLIP's predictions then trains a supervised predictor to replicate these scores for efficient token pruning. Learning to rank patches can be reformulated to learning permutation resulting from the ordering of patches by rank. Büchler et. al. learns to select effective permutations of patches or frames through reinforcement policy that maximizes the improvement in self-supervised permutation classification accuracy in a discrete action space. In contrast, REOrder models a stochastic policy over permutations using Plackett- Luce distribution [16, 17] and optimizes it with REINFORCE [18] and Gumbel Top-k sampling which allows for more flexible orderings.
3 Preliminaries
We first establish the properties of the self-attention mechanism, specifically its equivariance under conjugation by permutation matrices and the matrix multiplication that lends it O(n²) complexity. We then examine how Transformer-XLe Longformer, and Mamba model relationships between long- sequences and the design choices they make to side-step the quadratic complexity of self atteeintnnion. This establishes the sensitivity of long- sequence models patch ordering.
3.1 Self-attention and permutation equivariance
Self-attention is the primary mechanism used in the Vision Transformer. Let the n image patches form the matrix
X [in...:;n E Raxd
Self-attention can then be computed as
Attn(X) softmax
(XW (XW (XWx)) va
XW..
W W. W. Raxd
(1)
where W g. WA. and W, v are learnable query, key, and value matrices, respectively.
The n x n similarity matrix inside the softmax is O(n)) which is undesirable for large X. However, full self-attention has useful symmetry.
Proposition 3.1 (Permutation equivariance of self-attention). For every permutation matrix P E {0, 1 1
(PX) = P (t).
Equation (2) states that self-attention equivariant to arbitrary permutations of the patch ordering. Hence, the Vision Transformer, composed entirely of self-attention, is also permuration-equivarianl proof for Proposition (3.1) in Appendix B; thorough analysis is conducted by Xu et. al. [19].
3.2 Position embeddings
The permutation equivariance of full self-attention undesirable for image processing tasks. The spatial arrangement of patches in an image carries critical semantic information that must be preserved or made accessible to the model. Positional embeddings were introduced to explicitly provide the model with information about the original 2-D location of each patch within the image grid by summation with the image tokens. This allows the model to understand the spatial relationships between patches, regardless of their position in the input I-D sequence.
We use learned absolute position embeddings across our models. Transformer-Xi these are incorporated in conjunction with its native relative positional encoding. When specific base patch ordering is adopted for an experiment, the positional embeddings are learned align with that particular fixed sequence. Crucially, the positional embedding for the [CLS] token is consistently learned for the initial sequence position and not reordered with the patch tokens, thereby maintaining stable reference for classification tasks.
3

---

3.3 Self-attention approximations and sensitivity to patch order
Recent work reduces the Onn2) cost of full attention by sparsifying the attention pattern, factoring the softmax kernel, or replacing it with learned recurrence. These changes, however, also break the full cetnuutttttoneuivriiiiiin guarantee of Eq. (2). Below we inspect three representative models. Their attention patterns are visualized in Appendix G.
Transformer-XL. Transformer-XI. [2] adds segment-level recurrence with memory. After segment of length is processed, each layer caches its hidden states as memory MER At the next step the layer concatenates that memory with the current segment's hidden states H HeRLxd,
H concat [M), H]
[R(++)xxd
where SG(.) a stop-gradient. Following Eq. (1), we define a single set of projection matrices as
Q = HW,
K = W
==HW,
Let P permute the L patches of only the current segment (but not the memory). Memory corresponds to previous segments, so its rows are fixed under permutation.
PH [MG(M); PH
Because second and third logit terms of (i,j) depend on the relative index i i- conjugating by P does not commute with the soft-max:
A TXL
PHH) + P A TXL
Thus, Transformer-XL. is permutation-sensinn even though its content-content term alone would be equivariant.
Longformer. Longformer [1] uses a sliding-window pattern of width w plus g global tokens with their own projections w! w W!l) Because the local mask Micca fixes which (i,j) pairs are valid, applying P to the rows/columns re-labels many entries as illegal (-oo) and others as legal, so A P softmax(MMea)) PT.
(oft
The same holds for the global mask unless P preserves the hand-picked global positions. Therefore, Longformer sensitive to patch ordering by design. It converts O(n²) complexity ((ww) under rigid spatial prior.
Mamba and ARM. Mamba [3] does not implement quadratic attention and instead introduces content-dependent state-space update.
h. A, B. Y: C, h
with inputs x2 produced by scanning the patch sequence left-to-right. A permutation P re-orders the stream, changing (B,, Cz, A.) and the sequence of matrix multiplications, so the recurrence yield different. Therefore Mamba is also permutation sensitive. Its O(n) complexity comes at the price of a fixed processing order.
In this work, we use ARM as introduced by Ren et. al. [9]. In ARM, every Mamba layer runs four causal scans in different directions and sums their outputs before the channel-mixing MLP.
For each d E (-,+,4. t) let (d) be the patch encountered at time step when traversing the image in direction d. The direction-specife recurrence is
h (d) = A (4) h1th B
yt (d)
= c.(() h
and the layer output combines the four via
Σ
Yz
dE J.
Similar Mamba, because each scan is individually directional, arbitrary permutation P of the patch order both re-orders the input streams (x(") and alters the learned parameter sequences
c( }. Hence the mapping still violates permutation equivariance (PXX) + P (X)). {A (d) B c
Further discussion in regards to the symmetry and performance implications of ARM with different
orderings is discussed in Appendix A

---

ImageNat-1K
Functional Map
9.5
24
0 &romm Row Major (pp)
3.4
13
A from Row Major
1.7
0.0
0.0
3.4
1.0
4.9
-1.4
WT
Longtomer
Mamta
VI1
Longforeer
Mambo
Column
Hilbert
Diagonal
Sptral
Figure 2: Patch order affects the performance of long-sequence models. This figure compares the top-1 accuracy of Vision Transformer (ViT), Longformer, Mamba, and Transformer-Xi XL (T (T-XL) on ImageNet- IK and Functional Map of the World when using alternate patch orderings, relative to their standard row-major performance. As expected, VIT remains equivariant patch sequence permutations. In contrast, long-sequener models exhibit substantial performance variability depending the patch ordering. No single ordering consistently outperforms others across models or datasets, necessitating dynamic patch ordering strategics.
Does Patch Order Matter?
Conventional autoregressive vision models default to a raster-scan (row-major) order for flattening 2-D images into 1-D sequences. We investigate the question of whether the sequence in which image patches are presented to autoregressive vision models has an impact on their performance. We begin by outliming the datasets and models used in empirical evaluation, followed by details of our training methodology. We then present results demonstrating that variations in patch ordering, even simple like column-major scans, lead to differences in model outcomes, thereby motivating a search for more optimal, potentially learned, orderings. We define and explore six fixed patch orders: row-major, column-major, Hilbert curve, spiral, diagonal, and snake. These visualized in Figure and formally defined in Appendix F.
Datasets. Images captured in different contexts demonstrate varying structural biases. To study whether such datasets are susceptible to patch ordering effects to different degrees, we run experiments on two datasets: ImageNet- 1K [20] (natural images) and Functional Map of the World [21] (satellite). We train on their respective training sets and report results on the validation sets. Details on the dataset licenses are provided Appendix
Models. We experiment with the Vision Transformer (ViT) [6], Transformer-XL (TXL) [2], Long- former [1], and ARM model as our Mamba variant [3, 9]. These three long-sequence architectures were chosen to represent distinet approaches to efficient sequence modeling: Transformer-X XXL em- ploys segment-level recurrence and relative positional encodings to extend context length; Longformer reduces the quadratic attention and Mamba introduces a structured state-space model with linear-time complexity and constant mem- ory scaling. Together, they span the major design paradigms for long-range dependency modeling. We then test whether patch-ordering effects persist across fundamentally different inductive biases.
through combination of sliding-window and global attention;
We utilized the timm implementation for the Vision Transformer (ViT) and the HuggingFace imple- mentation for Longformer. Both were adapted with minor modifications to accommodate varying patch permutations. TXL is based the official implementation and includes newly introduced, learned absolute position embedding to account for changing patch orders across batches. We use vision Mamba model of choice due to its training stability. For all of the models, the
ARM [9] image size is 224x224 with patch size of 16x 16. The Transformer-Xi memory length (M) was 128 and the attention window size (Mlocal) for Longformer was set to 14. All four models prepend a learnable class [CLS] token as a fixed-length representation for image classification. The [CLS] token is always retained the first token in the sequence. All models their respective Base configurations. Complete details about the model configurations are in Appendix C.
Training. Experiments are conducted on machines equipped with either 8x80GB A100 GPUs or 4x40GB A100 GPUs. We apply basic data augmentations of resizing to 256 256, center crop to 224x224 and then a horizontal flip with p- = 0.5. We ablate this augmentation choice in Appendix D.3. All models are trained for 100 epochs the AdamW optimizer using 3 0.9,
5

---

32 = 0.999, weight decay of 0.03, and a base learning rate of a - 1.0 x 10 Batch sizes are held constant for all runs across all model-dataset pairs (details Appendix D). We apply cosine learning rate decay with linear warmup over 5 epochs. For the reinforcement learning experiments introduced Section 6, we use the same optimizer configuration but with reduced base learning rate of a = 1.0 x 10-5 and no decay.
4.1 Performance Variation Across Orderings
We evaluated top-1 accuracy validation sets, estimating the Standard Error of the Mean (SEM) using a non-parametric bootstrap method with 2,000 resamples. Our analysis focused on how model performance varied with different patch orderings across datasets.
As anticipated, the Vision Transformer (ViT) demonstrated permutation equivariance, achieving consistent 1 accuracy (approx. 37.5% on ImageNet-IK IK and 46.5% on FMoW) irrespective of patch order (Figure 2). In contrast, long-sequence models like Longformer, Mamba, and Transformer- XL (T-XI.) showed performance variations dependent on patch order. T-XL and Mamba were particularly sensitive; on ImageNet-IK: T-XI'ss accuracy increased by 1.9.2 percentage points) with column-major ordering and decreased by 6.43%(40.21 percentage points) with spiral. Longformer also benefited from alternative orderings (column-majj) Hilbert, snake) on ImageNet-IK: improving by up to 1.83% 1.8%%(*0.) (=0.22 percentage points) over row-major.
Dataset characteristics altered these trends. On FMoW, Longformer's optimal ordering shifted (e.g.. diagonal increased accuracy by 1.3%(#0.22 percentage points) while column major was detrimental). T-XL still favored column-major but also benefited from diagonal ordering on FMoW. Overall, FMoW exhibited less sensitivity to patch ordering than ImageNet, likely due to the greater homogeneity of satellite imagery compared to diverse natural images. Mamba consistently performed worse with non-row/column major orderings, likely because its fixed causal scan directions (d E (+,,,,,, f)) conflict with other patch sequences. Adapting Mamba's 's scan order to the patch ordering could potentially mitigate this performance drop.
These results highlight that there is one ordering that works best for all models or datasets. Given that in many cases an alternate ordering outperforms the standard row-major order, this raises an important question: can we discover an optimal ordering tailored to a specific model and dataset? Moreover, are there useful priors we can identify to guide the search for such orderings?
Learning an Optimal Patch Ordering with REOrder
The observation that patch order influences model performance suggests the existence of an optimal ordering for each model-dataset pair. To find such orderings, we introduce REOrder, unified framework that combines unsupervised prior discovery with task-specific learning. We begin with an information-theoreiie analysis, examining the link between sequence compressibility and downstream performance. REOrder automates this process to derive prior over effective patch orderings. Building on this, it employs reinforcement learning approach to directly learn task-specific orderings, leveraging the prior as guidance.
Enformation-Theorett Initialization The order in which image patches are arranged affects the compressibility of the resulting sequence. For example, in conventional raster-scan order, adjacent patches often contain similar content, making the sequence more compressible. This local redundancy might make the prediction task more trivial, as the model could focus on learning simple local correlations rather than capturing more complex, long-range dependencies. We first explore whether compression metrics could serve as a proxy for evaluating different patch orderings. Specifically, we discretize images using a VQ-VAL VAE based model [22] and encode the resulting token sequence codes using both unigram and bigram tokenization. For each configuration, we measure the compression ratio achieved by LZMA, which provides a quantitative measure of local redundancy in the sequence.
In Figure 3, we observe that different patch orderings indeed lead to varying compression ratios. The row-major order, which commonly used in vision transformers, achieves higher compression ratios, suggesting strong local redundancy. Interestingly, the Hilbert curve ordering, which aims to preserve spatial locality, shows similar compression characteristics to row-major order. contrast, the column-mane majummsajor/spirrll orderings exhibit lower compression ratios, indicating less local redundancy.

---

Longformer
Transformer-XL
15.0
38.5
Top-1 Acc (%5)
38.0
INIK
34.
60.0
$4.0
36.0
13.0
57.0
$2.0
34.0
56.0
0.11
Acc (16)
FNOW
$5.0
66.0
66.0
53.0
41.3
1731
17.03
17.00
17.31
17.61
18:57
17.31
17.9
18:30
18.77
17:31
17463
37.50
15.20
Campression reduction
Compression % reducction
Compression % reduction
Compression reduction
Row
Column
Hilbert
Diagonal
Spiral
Snake
IN1K
FMOW
Figure 3: Compression of 1-D sequences accuracy is compared to percentage reduction different patch orderings across four models for ImageNet- IK and FMoW.
weak prior for optimal patch ordering. Top-1
This result highlights the limitations of applying a 1D compression algorithm (LZMA) to sequences derived from 2D data. While Hilbert curves preserve 2D locality better, this may not translate to higher compressibility for ID algorithm.
While this analysis provides a useful lens for examining patch dependencies, it produces only a weak and model-dependent correlation with downstream accuracy. That is, lower compressibility does not consistently imply improved task performance. For instance, while column-major ordering Figure shows lower compression ratios, does not consistently lead to better model performance across all architectures. This result is itself significant as it demonstrates that no simple, universal heuristic exists for 1-D sequence of image tokens.
This insight motivates the second stage of our approach, in which we employ reinforcement learning to discover task-specific orderings. We use compressibility exploration. We assess the importance of such initializations in Appendix D.2.
weak prior give start
6 Learning to Order Patches
Our findings Section 4 reveal that patch ordering can significantly affect the performance of long- sequence vision models. This suggests the potential value of discovering data- and model-specific ordering to improve task performance. Unfortunately, learning discrete permutation poses a unique challenge. For an image with N patches, there are N! possible orderings. For N 196, there are more than 10365 options. Searching this combinatorial space exhaustively is infeasible. A naïve approach would require evaluating each permutation's 's classification loss on every training example, which is computationally intractable and incompatible with gradient-based learning. We instead treat the selection of patch orderings stochastic policy learning problem, where the policy outputs distribution over permutations. This allows us to sample permutations during training and optimize the policy against the downstream classification loss with reinforeement learning.
6.1 Learning the Permutation Policy via REINFORCE
Because permutations are discrete and non-differentiable, we adopt the REINFORCE algorithm [18, 23]. score-function estimator, to search over the space of all possible permutations and optimize a permutation policy. REOrder is outlined in Algorithm 1. This formulation treats the permutation sampler stochastic policy, whose parameters are updated based the classification reward.
REINFORCE is unbiased but can have high variance. mitigate this, we subtract a running baseline by from the reward, giving A, r -b, where b++1 b, + (1 - -33 r., with / (= 0.99) controlling the baseline's 's momentum. The vision transformer's parameters 0 depend only on the cross-entropy loss LCE. while the policy model receives gradients from LCE and the REINFORCE loss.
7

---

Algorithm REOrder with Plackett-Luce policy
Require: mini-batch ((x(0), .8 )] backbone Sa, logits 2, Gumbel temperature т, baseline 6, momentum
I: g (0mbel(O, 1)"
2: argsort (2 T9)
Gumbel-top-k permutation
3: (b) + PERMUTE(11 (b)
4b
4: g()) + )
(0)) y1b)
5: Lex -
log
6: r +----- LCR
D. Reward
7: b < 3b + B)r
8: A
Advantage
Cpoliey + + log P( 2)
10: Liotal + LCE + Cpolicy
11: Back-propagate V0, and update with Adam
6.2 The Plackett-Luce Policy for Patch Orderings
To parameterize the permutation distribution, we use the Plackett-L_cc (PL. model [16, 17]. This model defines distribution over permutations based on learned logit vector z E R" associated with the image patches, Each patch gets a single parameter, so a 224 224 image with patch size 16x 16 results in model with 196 parameters. This negligible added overhead for training. A permutation is sampled sequentially: at each step, yet-unplaced patch is selected according to softmax over the remaining logits:
exp Zm.. 1=1 k=j exp 2TT))
P(T II
Sampling from this distribution naively requires drawing patch at time in sequential loop, which is inherently slow and difficult to parallelize across a batch. To make training efficient, we use the Gumbel-top-k trick [24] which generates samples from the Plackett-Luce distribution by perturbing logits with Gumbel noise and sorting. A policy π is sampled as ग argsort(z + Tg) where 9i Gumbel(0, 1) and 5 0 is temperature parameter that trades off exploration and exploitation. The Gumbel-top-A sampler is fully parallelizable and faster than iterative sampling, allowing permutation sampling in (n log n) time.
The log-probability of sampled permutation is computed in closed form:
log P(T 22)
log
exp( (2me)
(4)
which we implement efficiently using cumulative logsumexp in reverse.
The logit vector is initialized linear ramp from 0 to 11, then permuted according to the information-thhoreee prior described Section 5. This gives the model a sensible starting point that reflects structural cues discovered during unsupervised analysis, while still allowing gradients to adapt the ordering throughout training.
During training, single set of Gumbel samples is drawn per batch so that every image shares the same permutation. At test time, we compute a deterministic maximum-likelihon permutation # argsort(2). To ensure stability, permute only the positional embeddings of image tokens with म, keeping the [CLS] token fixed.
Curriculum for Policy Learning
We adopt three-stage curriculum that cleanly separates representation learning from policy learning. For the first N epochs the classifier is trained with the canonical row-major patch order. This gives the vision transformer stable starting point before any permutation noise is introduced. Beginning epoch the Plackett-Laue policy is activated and trained with REINFORCE for M epochs. Sampling uses the Gumbel-top-k trick with temperature schedule 7, that climbs to peak value

---

Colurn
Row
Epoch 15
Epoch 22
Epoch
Epoch 37
Epoch 44
Figure 4: The legits of the Plackett- Luce model, and therefore the permutation order, changes over the course of training. Longformer is initialized with column and row-major patch ordering and optimized with REOnder on ImageNet- KK The image is of the class "keyboard." We track two patches over the course of the policy curriculum: a keyboard key (light red arrow) and an irrelevant orange beak (dark red arrow). As the policy learns to order patches, we see the patches move toward the back of the sequence (i.e., are back-loaded) reflecting the dataset's center bias.
before decaying to zero. While > 0 the permutation remains stochastic, encouraging exploration and allowing the policy discover beneficial orderings. Once the temperature hits epoch permutation Ω = argsort(z). The
N + M, sampling collapses to the single policy gradients vanish, freezing the permutation, and the remaining epochs let the backbone finish optimizing with its now-determinate input order.
For experiments. the curriculum pattern where it increases linearly from = 0.0 at epoch to M/2 with T = 0.2. It then decreases linearly from epoch M/2 to M ending at r = 0. The optimizer for the policy was AdamW(3, =0.99, $2=0.999, weight decay 0.03) with a learning rate of x 10-1 The evolution the policy over training is visualized in Figure 4, demonstrating how salient patches for the target class of "keyboard" move to the end of the sequence to maximize classification accuracy.
set with N = 15 and M 30. Ti follows triangle
6.4 Effectiveness of Learned Patch Ordering
The Plackett-Luce policy introduced by REOrder is a simple drop-in addition to model training, and as visualized in Figure in almost all cases, improves performance over their respective base patch order runs. Mamba observes gains of 2.20% (+0.2 percentage points) on average across different patch orderings for INIK, and 9.32% (+0.22 percentage points) on FMoW. For ImageNet, the Hilbert curve ordering for Mamba is improved by 3.01% (=0.23 percentage points) while for Functional Map of the World, the diagonal ordering improved by 13.35% (+0.21 percentage points). Transformer-X XL demonstrates modest gains with REOrder. On INIK, Transformer-X accuracy improves by an average of 0. 0.70% (+0.22 percentage points) but sees significant gains with the Hilbert curve (1.50% (+:0.21 percentage points)) and spiral (1.09% (=0.21 percentage points)) patch orderings. On FMoW, REOrler improves the rest-performing column-major order by an additional 1.10% (+-0.21 percentage points), demonstrating that simply using a basic patch ordering alone may not be sufficient to get best performance. Longformer is unable to improve its accuracy on the model that was initially also the least susceptible to changes in patch ordering due to its near-full approximation of self-attention, is unsurprising that the use of REOrder does not achieve any noticeable performance gains.
either dataset. However, since Longformer
To verify that these gains are not artifacts of training dynamics or limited training duration, we conducted two complementary robustness analyses (see Appendix D.2 and D.1). The first examines the role of policy-driven exploration by comparing static and dynamic random permutation strategies. The second extends Transformer-Xi training from 100 to 300 epochs to test stability under longer optimization schedules. Together, these experiments confirm that performance improvements arise from the reinforeement learning process itself and persist under extended training.

---

ImageNet-1K
Functional Map of the World
60
Accuracy
50-
40
30
Longtormar
Mamba
Transformr
AL Improves
Hurts
Figure 5: REOrder finds improvements over the best patch ordering prior almost cases. Across all models, REOrder can find better patch ordering than a static prior and improve accuracy across both ImageNet- IK and Functional Map of the World.
In summary, REOrder's approach of learning patch ordering proves to be a broadly effective strategy for boosting classification performance with long-sequence models, consistently elevating results even beyond the strongest baseline patch orderings for nearly all tested models and datasets. We outline current limitations of our study and potential future directions in Appendix A. We also provide a thorough interpretability analysis in Appendix H.
7
Conclusion
This work establishes that contemporary vision models are sensitive patch order and that row-major patch ordering, an extremely common way of converting 2-D images to 1-D sequences, can be suboptimal in many cases. Architectural modifications in models like Transformer-XI., Mamba, and Longformer, while enabling the processing of long-sequences, break permutation equivariance, leading significant accuracy variations with different scan orders. We introduce REOrder, method to learn optimal patch orderings by first deriving an information-theoree prior and then learning patch ranking by optimizing Plackett-Luce policy with REINFORCE. This learned policy, implemented as simple drop-in addition to model training, demonstrably improves classification accuracy for multiple long-seque long-sequence models on datasets such as ImageNet-1 and Functional Map of the World by up to by up to 3.01% and 13.35%, respectively, surpassing the best fixed orderings.
A Acknowledgements
Thank you to Jiaxin Ge and Lisa Dunlap for generously reviewing this paper for clarity and content. Stephanic Fu lent her keen design instinct and helped make the figures look pretty. Anand Siththa- ranjan and Sanjeev Raja were always game for late night discussions about how search over combinatorial space and the pitfalls of reinforcement learning. As part of their affiliation with UC Berkeley, the authors were supported in part by the National Science Foundation, the U.S. Department of Defense, and/or the Berkeley Artificial Intelligence Research (BAIR) Industrial Alliance program. The views, opinions, and/or findings expressed are those of the authors and should not be interpreted as representing the official views policies of any supporting entity, including the Department of Defense or the U.S. Government. This work utilized the infrastructure at the DoD's High Performance Computing Modernization Program (HPCMP).
References
[1] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer, 2020.
[2] Zihang Dai, Zhilin Yang. Yiming Yang, Jaime Carbonell, Quoc V. Le, and Ruslan Salakhutdinov, Transformer-xl Attentive language models beyond a fixed-length context, 2019.
[3] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2024.
10

---

[4] Subhashini Venugopalan, Marcus Rohrbach, Jeffrey Donahue, Raymond Mooney, Trevor Darrell, and Kate Saenko. Sequence Sequence Video Text. In Proceedings the International Conference on Computer Vision, pages 4534 4542, 2015.
the IEEE
[5] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam M. Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In International Conference on Machine Learning, 2018.
[6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An Image is Worth 16x 16 Words: Transformers for Image Recognition at Scale. In International Conference Learning Representations, Octoher 2020.
[7] Ritwik Gupta, Shufan Li, Tyler Zhu, Jitendra Malik, Trevor Darrell, and Karttikeya Mangalam. xT: Nested Tokenization for Larger Context in Large Images. In Proceedings of the 41st International Conference on Machine Learning, pages 17060-17071. PMLR, July 2024.
[8] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers, 2019.
[9] Sucheng Ren, Xianhang Li, Haoqin Tu, Feng Wang, Fangxun Shu, Lei Zhang, Jieru Mei, Linjie Yang, Peng Wang, Heng Wang, Alan Yuille, and Cihang Xie. Autoregressive Pretraining with Mamba in Vision, June 2024.
[10] Yao Qin, Chiyuan Zhang, Ting Chen, Balaji Lakshminarayanann Alex Beutel, and Xuezhi Wang. Understanding and improving robustness of vision transformers through patch- based negative augmentation, 2023.
[1I] Nelson Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. arXiv preprint arXiv:2307.083 172, 2023.
[12] Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-34) 1952.
[13] Tie- Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-331, 2009.
[14] Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi. Learning to rank for recommender systems. Proceedings of the 7th ACM conference on Recommender systems, 2013.
[15] Cheng-En Wu, Jinhong Lin, Yu Hen Hu, and Pedro Morgado. Patch ranking: Efficient clip by learning to rank local patches, 2024.
[16] R. Duncan Luce. Individual Choice Behavior. Individual Choice Behavior, John Wiley, Oxford, England, 1959.
[17] R. L. Plackett. The Analysis of Permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24(2):193-202, June 1975.
[18) Ronald J Williams. Simple statistical gradient-followwin algorithms for connectionist reinforce- ment learning. Machine learning, 1992.
[19] Hengyuan Xu, Liyao Xiang, Hangyu Ye, Dixi Yao, Pengzhi Chu, and Baochun Li. Permutation Equivariance Transformers and Its Applications, January 2024.
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large- scale hierarchical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pages 248-255, June 2009.
[21] Gordon Christie, Neil Fendley, James Wilson, and Ryan Mukherjee. Functional Map of the World. In 2018 JEFF/CVF Conference on Computer Vision and Puttern Recognition, pages 6172-6180 Salt Lake City, UT, USA, June 2018. IEEE
11

---

[22] Chameleon Team. Chameleon: Mixed-modal early-fusion foundation models. arXiv preprint arXiv:2405.09878, 2024.
[23] Junzi Zhang, Jongho Kim, Brendan O'Donoghue, and Stephen Boyd. Sample Efficient Re- inforcement Learning with REINFORCE. Proceedings of the AAAI Conference Artificial Intelligence, 35(12):10887-10895 May 2021.
[24] Wouter Kool, Herke van Hoof, and Max Welling. Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement, May 2019.
12

---

Appendix
A Discussion and Limitations
There are many details and nuances to our experiments that are worth discussing further. Particularly, there are areas for improvements that we would like to introduce in future versions of this work.
Directional Asymmetry and ARM Interpretation. While our work primarily focuses on improv- ing the permutation sensitivity of sequence based vision models through REOnder, it is important to contextualize the architectural behavior of ARM. Although ARM's four-directional scanning mechanism symmetric in principle, our experiments show that its performance varies across different input orderings due to the anisotropic statistics of natural images and the model's fixed directional composition. particular, ARM achieves higher accuracy with a row-major ordering than with polumn-major one, reflecting the stronger horizontal correlations inherent in natural scenes. This empirical asymmetry persists despite theoretical symmetry between the two configurations, revealing how data bias and architectural inductive bias jointly shape model behavior. Moreover, a Hilbert-curve ordering, which maximizes spatial locality, performs significantly worse because it disrupts ARM's directional continuity. ARM's recurrence dynamics optimized for specific scanning patterns rather than spatial adjacency alone.
REOrder addresses these mismatches by learning adaptive permutation of the input sequence that jointly benefits all four directional seans. When initialized from a row-major order, it improves validation top-1 accuracy to 58.22 58.25%, and from column-major order to 58 58.58% on ImageNet- IK. Even from a suboptimal Hilbert initialization, REOrder recovers much of the lost performance, reaching 43.42%. These results indicate that the learned permutations do not merely refine existing scan but instead adaptively reorganize the patch sequence to better align the input statistics with ARM's directional processing. This demonstrates that REOrder serve practical mechanism for reconciling architectural symmetry with anisotropic visual data.
Random baseline. A random baseline for a learned permutation baseline involves sampling a random ordering of patches for every batch during training. We set up this baseline with Transformer- XL on the ImageNet-I1 IK dataset. This model achieved a maximum top-1 accuracy of 39.07% which is 15.25 percentage points worse than the worst patch ordering tested for T-XL on INIK (spiral). While random baseline should be run for every model and dataset combination, the drastically lower performance of the random baseline gives confidence in the veracity of results.
Unper-explored and under-tuned policy. Images with N = 196 patches have more than 10 permutations. Searching this space exhaustively is computationally infeasible (it is estimated that there are between 1078-1022 atoms in the observable universe- our quantity is slightly larger than that). The Plackett- luce policy exploration runs for a vanishingly small amount of time. The curriculum, tested in our experiments, is only active for 30 epochs. The majority of these epochs is spent warming up and cooling down the Gumbel noise temperature, with the peak noise (and therefore exploration) occurring for only one epoch. We were not able to tune these parameters due to computational constraints. Therefore, much is left "on the table" with respect to improving results with REOrder.
Dynamic Image Policy. A key limitation of the present work is that REOrder learns a single global ordering shared across all samples within a dataset. While this design enables clean isolation of ordering effects and ensures stable optimization, it constrains the model's flexibility in adapting to maage-specific structures. A promising future direction is to extend REOrder toward dynamic, per-image ordering, where lightweight policy network predicts ordering logits conditioned on patch embeddings. Such an approach would allow the ordering to adapt to spatial and semantic content, potentially capturing intra-dataset variability while preserving the benefits of learned sequencing. Investigating the trade-offs between global stability and dynamic adaptability represents an important next step for our future work.
Long Sequence Training. To assess scalability, we initiated experiments on ultra-high-resolution images (5888x5888), setting where standard ViT models exceed GPU memory limits. These
13

---

experiments are ongoing, and we plan to include results in future work exploring how REOrder behaves in extended sequence regimes.
B Proof of Proposition 3.1
Theorem (Permutation equivariance of self-attention). Let X E RRdd and let P E {0, 1jnxn be any permutation matrix. With Attm(-) defined in Eq. (I), we have
Att) = P At).
Proof. Let
(XW (XW:)
S(X) softmax
R
Vd
Conventionally, softmax for Attn is applied row-wise over (XW, ( (XW)) )T so that the ensuing multiplication by the value matrix serves normalized weighted sum over value columns. Since permutation merely re-orders rows and columns, it satisfies the conjugation property
(oftmax(PMP) = softmax(M) Pd
for any square matrix M and any permutation matrix M. Then,
(PXW. o PXW.
Attn(PXX softmax
vd
PXX,, PXW,
softmax
vd
PS(X) PT PXW.
XW(
(P'P=II
P (X).
Hence self-attention is permutation equivariant.
C Model Details
Table 1: Patch Order Models
Model
Size
of Parameters
Width
Depth
ViT
Base
86 570 728
768
12
Transformer-Xi
Base
93 764 584
768
12
Longformer
Base
107 683 048
768
12
Mamba
Base
85 036 264
768
12
ViT
Large
304 330 216
1024
24
Transformer-XL
Large
329 601 512
1024
24
Longformer
Large
379 702 760
1024
24
Mamba
Large
297 041 352
1024
24
We attempt to parameter match each model we experiment with in an effort to remove one axis of variability from our results. We experiment with the Base variant of each model in our experiments. Despite the intention for the Base variants to be roughly equivalent to each other, Longformer-Bass and Mamba-Base vary by ~22M parameters. To contextualize how width and depth affect the number of parameters, provide details for Base and Large variants in Table 1.
14

---

D Additional Model Training Details
Each training run required 100 epochs for completion. ImageNet experiments were run 8x 80GB A100 GPUs, while Functional Map of the World experiments were run on 4x 40GB A100 GPUs. Tra VIT and Mamba, and the Plackett-Luce policy were compiled with TorchDynamo using the Inductor backend. The Longformer encoder provided by HuggingFace was unable to be compiled. For ImageNet runs, Vision Transformer runs took -8.5 hours run, Transformer-X runs took -10 hours, Longformer rums took -12 hours, and Mamba runs took -19 hours. For Functional Map of the World, Vision Transformer runs took -17.5 hours, Transformer-Xe XL runs took -21 hours, I Longformer runs took -26 hours, and Mamba runs took -31 hours. All runs were executed on dedicated datacenters accessed remotely.
All runs nearly maximized the available VRAM on their respective GPUs. The breakdown of models and batch sizes is provided below:
Table 2: Batch sizes for every model-dataset pairing.
Model
Size
Dataset
Batch Size
ViT
Base
IN1K
896
VIT
Base
FMOW
448
Transformer- XL Transformer-XI
Base
INIK
640
Base
FMOW
320
Longformer
Base
INIK
640
Longformer
Base
FMOW
320
Mamba
Base
INIK
640
Mamba
Base
FMOW
320
In sum, the total set of experiments required total of ~ 9, 336 A100 GPU hours.
Models were trained with minimal set of augmentations, namely: resize 256 x 256 pixels, center crop to 224 x 224 pixels, and a random horizontal flip with 0.50.
D.1 Increased Training Time
We continued training our Transformer-Xe XL Row and Transformer-XI REOrder Row models from 100 epochs to 300 epochs to test the robustness of our conclusions with longer training. The models trained with the same recipe and learning curriculum. The gains from REOrder maintained and even increased after 300 epochs. At 100 epochs (Table 3), Transformer-2 XL Row achieves 60.80% Top-1 Validation accuracy whereas REOrder improves on this by 0.6 percentage points to 61.40%. Extending training to 300 epochs, Transformer-X XL Row achieves 61.20%, a 1.19 percentage points increase over 100 epochs; however, Transformer-X REOrler Row, increases performance 63.34% which is a 2.14 percentage points increase over the Transformer-XX XL Row model at the same epoch. These findings show that REOrder continues to provide consistent gains under extended optimization. supporting its robustness beyond the initial training regime.
Table REOrder widens the gap between standard models when training is extended. When training is extended from 100 epochs to 300 epochs, REOrder still shows significant Top-1 Validation Accuracy gains over training without REOrder.
Model
Dataset
Patch Order
RL
Top-1 Validation Accuracy
Gain at 300 Epochs
T-XL
INIK
Row
60.80
+1.19 pp
T-XL
INIK
Row
61.40
+1.94 pp
D.2 Random and Static Permutation Results
To better understand the effects of the REOrder learning process on the performance of the models we performed three additional runs with Transformer-XL. on ImageNet-Ik,
15

---

1. Using fixed random permutation for the entire training
2. Sampling a random permutation for every batch through all of training
3. Using the final learn permutation of our best performing REOrder Transformer-Xe model for all of training
The results in Table indicate that simply picking random patch orderings is not sufficient (and therefore, any random ordering will also perform poorly). The structured exploration provided by REOrder is necessary to improve performance. A novel outcome of this exploration is that simply using learned patch ordering is sufficient for gains performance; the guided exploration process introduced by REOrder is necessary for improved performance.
Table 4: Top-1 validation accuracy ImageNet-IK using Transformer-X1 under four alterna- tive permutation schemes. Each variant controls how patch sequences are presented during training. Only REOrder's reinforcement-eeumin curriculum (second row) adaptively explores the ordering space, leading to large performance gain over all static or unguided random strategies.
Permutation Strategy
RL
Top-1 1 Accuracy
Row Major
60.80
REOrder Row-major initialization
61.40
One random permutation for all epochs
53.10
Every batch random
50.23
Best learned ordering
53.07
D.3 Results Without Flips
We additionally run experiments where the only data processing steps applied are resize to 256 256 pixels and center crop to 224 x 224 pixels with no flips at all. The results presented in Table show the effects observed in the main experiments are maintained albeit with different accuracy magnitudes. With no augmentations, the effect of REOrder is even greater. All tested patch orders exhibit performance gains when optimized by REOrler. The performance boost ranges from 1.58% with row-major to 2.94% with the Hilbert curve ordering. Diagonal and spiral orderings get moderate gains of 2.4 2.41% and 2.47% respectively, while column-major and snake orderings show more modest improvements of 1.67% and 1.82% respectively. These results confirm that REOrder consistently enhance task accuracy across the patch orderings even without extensive data augmentation.
Table 5: REOrder consistently improves performance across all patch orders with no augmenta- tions. Top-1 validation accuracy on INIK using different patch orders with and without our REOrder using minimal data processing (resize and center crop only).
Model
Dataset
Patch Order
RI.
Top-1 1 Accuracy Difference
Transformer-XI.
IN1K
Row
57.95
Transformer-Xl.
IN1K
Row
59.53
+1.58%
Transformer-Xe XL
IN1K
Column
57.33
Transformer-XI.
INIK
Column
59.01
+1.67%
Transformer-X
INIK
Diagonal
52.79
Transformer-ii XL
INIK
Diagonal
55.20
+2.41%
Transformer- XL
INIK
Hilbert
50.29
Transformer-XI.
IN1K
Hilbert
/
53.22
+2.94%
Transformer-ye XL
INIK
Spiral
49.93
Transformer-Xi
IN1K
Spiral
52.40
+2.47%
Transformer-Xi
INIK
Snake
52.20
Transformer-Xi
INIK
Snake
54.02
+1.82%
16

---

E Dataset Licenses and References
In this work, Challenge [20] and the RGB version of Functional Map of the World [21]. ImageNet-Il IK obtained from the official download portal and Functional Map of the World is obtained from their official AWS S3 bucket.
ImageNet-IK IK provided by the 2012 ImageNett Large-Scale Visual Recognition
ImageNet-IK IK is licensed non-commereial research and educational purposes only described on their homepage. Functional Map of the World licensed under custom version of Creative Commons license available on their GitHub.
F Rasterization Orders
Let an image be composed of N H W patches, arranged in grid of height H (number of rows) and width (number of columns). Each patch is identified by its zero-indexed 2D coordinates (r. c). where 0 S H and 0 I W. A rasterization order (or order) is bijection that maps ID sequence index k E {0, 10,,,...,NN .N 1] to the 2D coordinates of the k-tth patch in the sequence. We denote this mapping formula for (rk, Ck) from & is not provided; the order is algorithmically defined by their respective procedures.
rlk) (rk; CR). In all cases besides row- and column-major, direct
F1 Row-Major Order
Row-major order, also known as raster scan, is the most common default. Patches are scanned row by row from top to bottom. Within each row, patches are scanned from left to right. The coordinates (rk, ck) for the k-th patch are given by:
k W
Ck = (mod W)
F.2 Column-Major Order
In column-majo order, patches are scanned column by column from left to right. Within each column, patches scanned from top to bottom. The coordinates (rk, for the k-th patch given by:
H
rk k (mod H)
F.3 Hilbert Curve Order
The Hilbert curve is continuous fractal space-fillingg curve. Ordering patches according to a Hilbert curve aims to preserve locality, meaning that patches close in the ID sequence often (but not always perfectly) close in the 2D grid. The coordinates (rk, G&) for the k-th patch are given by:
T(k)= =
(Tk: cx) = H w (k)
where H.H.w w (k) denotes the coordinates of the k-th point generated by Hilbert curve algorithm adapted for an H x W grid.
F.4 Spiral Order
In spiral scan, patches are ordered in an outward spiral path. typically starting from corner patch, e.g.. (0, 0). The path moves along the perimeter of increasingly larger (or remaining) rectangular sections of the grid. The coordinates (rk, (x) for the k-th patch are:
T(k) (Fk)
These are k-th unique coordinates visited by path that starts (0, 0) and spirals outwards. The path typically moves along segments of decreasing lengths (or until a boundary previously visited cell is encountered) in a sequence of cardinal directions (e.g., right, down, left, up, then right again with shorter segment, etc.), effectively tracing successive perimeters of nested rectangles.
17

---

E,5 Diagonal Order (Anti-diagonal Scan)
In a diagonal scan, patches are ordered along anti-diagonals, which are lines where the sum of the row and column indices (r + c) is constant. These anti unti-diagonals are typically scanned in increasing order of this sum, starting from r + c = 0. Within each anti-diagonal, patches are typically ordered by increasing row index (or, alternatively, by increasing column index c). The coordinates (Tk, C&) for the k-th patch are:
((k) (rk, ck)
such that (rk, ) is the k-th patch when all patches (r, c) are ordered lexicographically according to row index, Patches with
the tuple r'), where s = r + c is the anti-diagonal index and r' = r is the smaller anti-diagonal sums 8 come first. For patches on the same anti-diagonal (i.e., with the same s), those with a smaller row index r' come first.
F.6
Snake Order
This scan traverses patches along anti- anti-diagonals (where the sum of row and column indices, r is constant). The anti-diagonals are processed in increasing order of s. The direction of traversal along each anti- anti-diagonal alternates. For example, for 8, patches visited by increasing column index c, and for odd s, by decreasing column index c.
Let s; = Tk + Ck be the anti-diagonal index for the k-th patch x (kk) (rk: ck). The sequence of patches π (k:) is generated by iterating from 0 to + W 2. For each s:
1. Define the set of coordinates on the anti- diti-dia S ((,,e) s, H.
c < W}.
2. Order the coordinates in S.. For instance, by increasing column index e: P. =
[(ro, co), (ri,c),..... (Tm, cm)] where co < ci <... < Cm-
3. If is odd (or based on an alternating flag), reverse the order of P..
4. Append the (potentially reversed) Ps to the overall sequence.
G
Attention Patterns for Tested Models
VIT
Tran TransformerxXL
Longformer
Mamba
17
26
26
50
25
12
11
20
16
16
26
26
50
80
58
56
13
13
12
22
20
50
50
55 55
Figure 6: Token-level attention coverage across different model architectures. Each grid cell represents patch in a 224x224 input image split into 49 overlaaalgp 32x32 patches. plus [CLS] token. Numbers indicate how many tokens attend to each patch. VIT and Mamba exhibit full attention all patches. In contrast, Transformer-XIa causal attention and Longformer's local attention restrict the number of tokens that can attend to each patch, leading to a strong asymmetry and localized attention, respectively.
To produce Figure 6, we visualized how many tokens attend each patch in a 224x224 image divided into 49 patches (plus a [CLS] token), using the following methods for each model.
We extracted the raw attention weights across all layers and heads during forward pass. After computing the element-wise maximum across layers and heads, we obtained a binary N N matrix indicating whether token attends to token j. Summing over rows yields how many tokens attend to each patch.
ViT and Transformer-XI.
18

---

Longformer: Due to its local attention structure, we reconstructed dense N x N attention matrix by extracting local and (if applicable) global attention indices. We then counted how many tokens had access to each patch through these sparse connections.
Mamba: Since Mamba does not use attention, we used gradient-based saliency method. We computed the gradient of the L2 norm of each output token with respect to the input embeddings. This yielded sensitivity matrix indicating the influence of each input token each output. Thresholding non-zero entries allows us to analogously count how many tokens "attend" to each patch.
These results reveal how the structural design of each model affects its ability to aggregate spatial information. ViT and Mamba attend to all patches uniformly, while Transformer-X causal structure and Longformer's locality lead uneven and limited attention coverage. These patterns explain their respective sensitivities to input token ordering.
H
Policy Evolution During Training
Calumi
How
Epoch 15
Epoch 22
Epoch 30
Epoch 37
Epoch 44
Figure Mamba observes patches most related to class label move the end of the sequence. Mamba trained with column- (top) and row-major (bottom) patch orderings and optimized with REOrder. The image is of the class "keyboard." We track two patches over the course of the policy curriculum: a keyboard key (light red arrow) and irrelevant orange beak (dark red arrow). As training progresses, the keyboard- related patches shift into the final indices of the sequence.
The REOrder policy learned distinct and consistent rearrangements of image patches that reflect both dataset structure and model-specific inductive biases. As seen in the "keyboard" example from
Calumn
Epoch 15
Epoch 22
Epoch
Epoch 37
Epoch 44
Figure Transformer-X observes patches most related the class label move the end of the sequence. Transformer-X XI. is initialized with column- (top) and row-major (bottom) patch orderings and optimized with REOrder. The image of the class "keyboard." We track two patches keyboard key (light red arrow) and irrelevant orange beak (dark red arrow). As training progresses, the keyboard-related patches shift into the final indices the sequence.
the course of the policy curriculum:
19

---

Figure 5, REOrder progressively shifts semantically important patches toward specific sequence positions, indicating that the learned permutations encode spatial continuity and capture architectural preferences in how visual information should be processed.
To quantify these effects, we analyzed how REOrder repositions patches originating from the central region of an image relative to their initial raster order. Both ImageNet-IK, and FMoW exhibit pronounced center bias, where salient content typically lies near the image's center. We observed that REOrder with different long-sequence architectures exploit this bias in distinct ways.
Mamba consistently front-loads central patches, shifting them earlier in the sequence (mean shift of +6.8 positions). This ordering aligns with Mamba's recurrent state-space mechanism as processing salient central regions early allows the model to form strong initial hidden state that informs subsequent token processing.
Transformer-XI and Longformer exhibit the opposite tendency, back-loading central patches (average shifts of -2. and 20..4 positions, respectively). For Transformer-Xl, this allows these tokens to utilize information from the entire image rather than only from half of it. For Longformer, the attention window accumulates context over the sequence which positioning maximizes contextual support from earlier tokens for the salient tokens.
This contrast demonstrates that REOrder does not converge to a trivial or dataset-wide ordering. Instead, it learns model-depended strategies that align spatial inductive biases with sequence- processing dynamics, revealing that ordering optimization can adapt meaningfully to the architecture's internal computation pattern.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state that the order in which patches are pro- vided long sequence models changes downstream performance. They also discuss the introduction of an RL-based method to learn better sequencing. The paper covers exactly those topics.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We consistently discuss the limitations of our work throughout the paper. For example, in Section 5, we detail why our compression prior is weak. For completeness, provide a discussion of the paper's limitations in Appendix A.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
21

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems, formulas, and proof's are numbered. Section 3 and Appendix B provide key background on self-attention and approximate attentions mechanisms and how their properties under permutations.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All model configurations and paper-paraeeerss for training are detailed in the main body and supplement. Fixed seeds are used for all runs. The anonymized repository for this work made available here.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
22

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use open datasets for evaluations which can be downloaded from their respective websites. The anonymized code is made available here, and instructions to run experiments are the README.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. ca/
public/ htt//guddees//ee guides/CodeSubmi httee//ooSuuuisssooooooo commiiissiiiicc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. wtccc//pbbb. wwcppblic//acccccccccccccccceccc guides CCodeSubmis asionoliccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: These details are provided in Section 4, and additional, but non-critical, details are added in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Yes, we report the standard error of the mean for all of our experimental results. The calculation of SEM explained in Section 4.1. Our figures include the necessary error bars.
23

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are of range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 4, we detail the necessary GPUs needed to reproduce our experi- ments. Appendix D provides complete details runtimes and experiment configurations.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ewrrps...... cc/ cccppbbiiiic ipppllc//eaaaeeepplee h/Ettiiicihieeeeeeeeeeeeeee iesuuideeines??
Answer: [Yes]
Justification: Our research conforms to the NeurlPS Code Ethics completely. As our experiments are pointing out overlooked inductive bias in the modeling process, we removing a bias from model training.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
24

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work has neither positive nor negative societal impacts as it is foundational research. There is direct path any negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper presents foundational research and as such does not present a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We appropriately cite the original papers for ImageNet- KK and Functional Map of the World. Complete details on where access these datasets and their licenses are in Appendix E.
25

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper did not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
26

---

Justification:
This paper was not subject to IRB/HSR as it did not involve any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were only utilized for writing and editing. None of the core methods were derived from any LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: http://eeeneccc///e///e http://pp..ccoooeeeeeee/e/////// for what should or should not be described.
27


Reviews:
[{"review_id": "2hQaYzzAx6", "reviewer": "Reviewer_pVqq", "summary": "The paper investigates the effect of the patch order on the performance of transformer-influenced image classification models that are not equivariant to permutations of patches (together with positional embeddings).\n\nThe paper presents the hypothesis that the standard row-major patch ordering might not be the optimal one and proposes a policy learning algorithm that learns the patch ordering in parallel with the classifier (for some number of epochs before freezing the policy). The policy learning uses the REINFORCE algorith with a policy model with the number of parameters corresponding to the number of patches (Plackett-Luce model).\n\nThe paper tests one equivariant architecture, ViT, and 3 non equivariant ones, Linformer, Transformer-XL, and Mamba (ARM). First, we see that changing the patch order of the model degrades the performance of non-equivariant models. For example, ImageNet-1k top-1 accuracy drops most on the Mamba model (around 6%) when a trained model is tested on different patch orders (row-major to column-major, spiral, ...).\n\nTraining the model with the proposed algorithm improves the performance with respect to the sub-optimal patch orderings, and the learned model performs similarly to the model trained with the row-mayor patch ordering.", "questions": "**Questions:**\n\n1. Please address weakness points 1 - 3.\n2. Why is the patch size selected to be 32×32?\n\nI hope that the authors will be able to address all the important weaknesses. I apologize for any errors on my part.", "limitations": "The paper comments on some limitations in the appendix. Additional limitations seem to be the lack of experiments with fixed previously learned patch orderings and low baseline accuracies.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1. The source code for reproducing the experiments is provided will publicly available.\n2. The paper is written well, has clear hypotheses, and presents an original investigation.\n3. The research questions of the paper make sense.\n\n**Weaknesses**\n\n1. Validation experiments could be improved.\n\t1. If I understand correctly, the main paper does not include experiments with supervised classification training from the start with a learned patch ordering and with a random ordering, but only concurrently with permutation learning. Experiments singling out the effect of the learned permutation would be valuable.\n\t2. An experiment with a random patch ordering is included in the appendix but not mentioned in the main paper. I think that the substantially worse performance on a random patch ordering is a valuable data point.\n2. Clarity could be improved.\n\t1. What is $M_\\text{TXL}$?\n\t2. I understand that all the Mamba experiments use ARM (Ren at al.), but I am not sure. Please consider clarifying it.\n\t3. Figure 2:\n\t\t1. Is the y-axis relative change or absolute (percentage points)? ()\n\t\t2. Does Figure 2 use a single training run?\n\t\t3. L190: \"We evaluated top-1 accuracy on validation sets, estimating the Standard Error of the Mean (SEM) using a non-parametric bootstrap method with 2,000 resamples.\" What is the sizes of the samples? Is the standard error of the mean 0 if the size equals the whole validation dataset?\n\t4. Figure 3. Why is the ImageNet-1k top-1-accuracy of the ViT (ViT-B/32?) baseline (Row) only around 38%?\n3. The discussion about REOrder experiments (Section 6.4 and Conclusion) could be improved.  \n\t1. I think that there is too much focus on the results of improving patch orderings that are worse than the default row-major ordering (Hilbert curve and diagonal), while what matters most is the improvement over row-major.\n\t2. How does the validation accuracy vary over different training runs?\n\t3. The percentages can be ambiguous. I suggest saying \"pp\" (percentage points).  \n4. Presentation could be improved (easy to address).  \n\t3. Not all appendix sections are referenced in the main paper, while some are quite valuable (for example, Appendix A).  \n\t4. Some more model details could be presented in the main paper for better information availability and sanity-checking. For example, it takes some searching to find out that \"ViT\" is ViT-Base and that the patch size is 32×32 (if I am correct). Also, is the Mamba in the experiments ARM?  \n\t5. Figure 3: The y-axes of the ViT experiments is a bit broken. Some numbers occur on multiple ticks.  \n\t6. Missing details:  \n\t\t1. For how many epochs is the patch ordering learned? (What is the value of $M$?)  \n\t\t2. What is the shape of the temperature schedule?  \n\nMinor suggestions:\n- The notation seems inconsistent: some matrices are not in bold.", "was_revised": true, "final_justification": "I anticipate that the paper will be updated based on the discussion, including various clarifications and the already performed experiment that shows the importance of patch-ordering evolution during training. Therefore, I have increased my score to borderline accept.", "rebuttal": "Thank you for your time and thoroughness in your review! Your feedback is incredibly valuable. We appreciate that you find our work interesting and find the writing to be well-done. Based on your review, we have conducted some additional experiments and re-organized the paper for clarity. We discuss each point in depth below:\n\n**Including more supervised learning experiments for the baselines**: We previously ran these experiments but under-estimated the importance of including them in the main body of the paper. We will put these in the main body of the paper for the camera-ready version. You suggested running two experiments: (1) picking a static, random permutation once at the start of training, and (2) taking a previously-learned ordering and statically training with it. In addition to what you suggested, we added an additional experiment: (3) For every iteration during training, pick a random permutation ordering.\n\n1. tests if any arbitrary permutation produces better or worse results than row-major or REOrder.\n2. tests whether the learned permutation is what matters most, or the process of guided exploration added by REOrder\n3. tests whether if unguided exploration is better than guided exploration\n\nFor the results below, we use Transformer-XL Base with all of the same parameters as described in the paper and report the top-1 accuracy on ImageNet-1K. We first repeat results from the paper for row-major and REOrder with a row-major prior, and then provide results for (1), (2), and (3).\n* Row major: 60.80\n* Row major with REOrder (row prior): 61.40\n* (1) We pick a random permutation ahead of training and then use that for the entire learning process: 53.10\n* (2) Take the best learned ordering from (b), fix that, and use that to train from the beginning: 53.07\n* (3) Random permutation for every batch during training: 50.23\n\nAll together, these results add to the narrative of our paper: simply picking random patch orderings is not sufficient (and therefore, any one random ordering will also perform poorly). The structured exploration provided by REOrder is necessary to improve performance. A novel outcome of this exploration is that simply using a learned patch ordering is not sufficient for gains in performance; the guided exploration process introduced by REOrder is necessary for improved performance.\n\n**Paper clarity**: We will re-organize the paper for experimental clarity. To answer your specific questions, $M_{TXL}$ is the length of the memory for T-XL, which was 128 in our experiments). We use ARM as our Mamba implementation of choice and mention this on L150 in the Preliminaries section. However, we will re-label our figures to be explicit about ARM. For all experiments, we use a patch size of 16. For visualization purposes only, Figure 6 in the Appendix shows a patch size of 32. We will be sure to address the clarity comments you highlighted in our revision.\n\n**Figure related comments**: In general, our reported numbers (and Figure 2) reports percentage points. We will clarify this explicitly. We report results using multiple training runs. There are instances in which our figures have broken y-axes, such as Figure 3. These are issues caused due to rounding and will be rectified!\n\n**Top-1 Accuracy on ImageNet-1K**: Our goal with this work was to isolate the effects of patch ordering. To do so, we simplified the training recipe to its basics and kept it static across all runs: 100 epochs, $1\\times10^{-4}$ learning rate, no augmentations, and a cosine learning rate decay. For this rebuttal, we increased the training length to 300 epochs. For T-XL, this improved performance to ~62% top-1 accuracy on ImageNet-1K. For T-XL with REOrder (row-major prior), this improved performance to ~63.5%. The ordering in our results from epoch 100 to epoch 300 did not change, nor did the relative magnitude of the results.\n\nThe original ViT paper achieved 77.91% top-1 accuracy on ImageNet-1K, but their training and evaluation setup is drastically different, which explains their higher performance. Dosovitskiy et. al. first pre-train on ImageNet at 224px resolution for 300 epochs, and then fine-tune on ImageNet at 384px resolution. In comparison, our work is trained fully-supervised from random initialization for 100 epochs (300 epochs in the above experiment). The gap in performance to the ViT paper is then largely explained by pre-training and high-resolution inference. Training for longer maintains the ordering of our results."}, {"review_id": "3y1Dle6PPI", "reviewer": "Reviewer_bd6c", "summary": "This paper addresses the problem that the design of patch ordering in autoregressive vision models has a significant impact on performance. Based on the hypothesis that conventional fixed patch ordering does not guarantee optimality, the authors propose a method to dynamically determine the ordering using reinforcement learning. By applying the proposed method to the Mamba architecture, for instance, the authors demonstrate significant performance improvements on the FMoW dataset.", "questions": "1 Can you please explain why ViT's accuracy (37.5%) on ImageNet-1k is significantly lower and how this affects your assessment of the proposed method's effectiveness?\n\n2 Could you elaborate on the reasons for selecting Transformer-XL, Longformer, and Mamba as baselines and the significance of each comparison?\n\n3 In light of recent developments such as the 2D extension of Mamba and bidirectional processing, what do you think is the practical standing of this research?\n\n4 Have you verified the performance of the proposed method on out-of-distribution data or downstream tasks to rule out the possibility of overlearning to a particular order? Or do you have any future plans to do so?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The description is clear and well-structured throughout the paper.\n\n2. The issue of the effect of patch order on autoregressive image models is novel and interesting in that it has not been fully explored.\n\n3. The proposed method provides a framework for dynamically optimizing the patch order based on information-theoretic initialization and reinforcement learning, and is applicable to implementations. In particular, the approach of designing the initial order in terms of information compression is unique and suggestive.\n\nWeaknesses \n\n1. Concerns about insufficient training in the experimental setting:\nFigure 2 shows only performance differences and omits absolute accuracy. On the other hand, line 194 of the text states that ViT achieves only 37.5% in Top-1 Accuracy for ImageNet-1k. This is extremely low compared to the performance of standard ViT (in the upper 70% range in the original ViT paper), probably due to the lack of convergence caused by the short training period of 100 epochs. In evaluating the effectiveness of the proposed method, a comparison under more fully trained conditions would be desirable, and it is difficult to draw strong conclusions from the current experimental results. This concern is similar for the other architecture, the other data (FMoW).\n\n2 Basis for selection of baseline models is unclear:\nTransformer-XL, Longformer, and Mamba are selected, but the reasons for their selection and their relationship to this method are not clearly presented. breaking Permutation-invariance While there are many variants of Transformer, why these three were chosen and what comparative insights can be gained from them?\n\n3. Ambiguous positioning with the technical context:\n Although the proposed method focuses on sequential image models, many efficient and high-performance approaches have already been proposed for application to image tasks using Mamba and other methods, such as 2D extensions of SSM and bi-directional processing. In such a technological context, it is somewhat unclear what practical and theoretical contributions this study has to offer.\n\n4. Overlearning Concerns for Patch Order:\n Even if the proposed method is effective in a particular pre-training task, it is unclear whether it will generalize to out-of-distribution data and downstream tasks. This is a major practical concern. In particular, additional experiments on out-of-distribution generalization performance and transition learning tasks are desirable to eliminate the possibility that the patch order is overfitting the training data.", "was_revised": true, "final_justification": "This paper can be evaluated for providing a new perspective on the fundamental problem of patch ordering in vision models using patch tokens. It also proposes a method for reinforcement learning to find appropriate patch ordering. Taking into consideration the comments and discussions from other reviewers, I will maintain our original score.", "rebuttal": "Thank you for providing a detailed and insightful review for our paper. We appreciate your recognition of the novelty of exploring the effects of for-granted architectural decisions such as patch ordering, especially as the community moves increasingly to long-sequence models. Below, we answer the questions you posed in your review, present some extra experimental details, and attempt to clarify any misconceptions that may have arisen in our writeup:\n\n**Top-1 Accuracy on ImageNet-1K**: Our goal with this work was to isolate the effects of patch ordering. To do so, we simplified the training recipe to its basics and kept it static across all runs: 100 epochs, $1\\times10^{-4}$ learning rate, no augmentations, and a cosine learning rate decay. For this rebuttal, we increased the training length to 300 epochs. For T-XL, this improved performance to ~62% top-1 accuracy on ImageNet-1K. For T-XL with REOrder (row-major prior), this improved performance to ~63.5%. The ordering in our results from epoch 100 to epoch 300 did not change, nor did the relative magnitude of the results.\n\nThe original ViT paper achieved 77.91% top-1 accuracy on ImageNet-1K, but their training and evaluation setup is drastically different, which explains their higher performance. Dosovitskiy et. al. first pre-train on ImageNet at 224px resolution for 300 epochs, and then fine-tune on ImageNet at 384px resolution. In comparison, our work is trained fully-supervised from random initialization for 100 epochs (300 epochs in the above experiment). The gap in performance to the ViT paper is then largely explained by pre-training and high-resolution inference. Training for longer maintains the ordering of our results.\n\n**Selection of T-XL, Longformer, and ARM (Mamba)**: We selected Transformer-XL, Longformer, and Mamba (specifically the ARM implementation) as they represent three distinct and influential architectural approaches to handling long-sequence data. Transformer-XL introduces a segment-level recurrence mechanism and a novel relative positional encoding scheme. This design allows the model to capture dependencies beyond a fixed length by reusing hidden states from previous segments, effectively creating a memory. Longformer addresses the quadratic complexity of the Transformer's self-attention mechanism by employing a combination of a sliding window (local) attention and a global attention mechanism. Mamba introduces a structured state-space model that operates with linear-time complexity and constant memory scaling. Each of these models were SOTA on benchmarks such as WikiText-103, One Billion Word, etc. at the time of release and are still near-SOTA today.\n\nOur work shows that regardless of the long-sequence modeling philosophy, patch order effects have a significant impact on downstream task performance.\n\n**Improvement to Mamba and bi-direction scan**: This is a good point, and we apologize that our paper was not more clear about this point.The Mamba implementation we utilize throughout our work is ARM (Autoregressive Pretraining with Mamba in Vision) [0], a model that incorporates multi-directional scanning. As we detail in our Preliminaries (Section 3.3) and Methods (Section 4), ARM is specifically designed for vision tasks and extends the base Mamba architecture significantly. Specifically, for each layer, ARM processes the input by running four parallel, causal scans in different directions (left, right, up, down) and then combines their outputs. This architecture inherently includes the bidirectional (e.g., forward and backward) and multi-axis (e.g., row-wise and column-wise) processing that you mentioned. Our work shows that even with these multi-directional scanning mechanisms, the model's performance remains highly sensitive to the initial 1-D patch ordering. We show that the challenge of patch ordering is not a relic of simpler, unidirectional models but a persistent issue in state-of-the-art architectures like ARM. REOrder is able to drastically improve performance even for these SOTA SSM architectures.\n\n**Pre-training and out-of-distribution performance**: REOrder is fully-supervised with respect to the images, while the patch ordering is learned without supervision with an RL setup. The core premise of our work is that the optimal patch ordering is not universal, but is instead dependent on the specific pairing of a model’s architecture and a dataset’s intrinsic properties. REOrder is designed to discover and exploit this pairing. However, your suggestion of pre-training brings up an interesting idea for future work: in lieu of an information-theoretic prior, a model and the REOrder policy would be pre-trained together on a large-scale dataset. The resulting learned policy would then serve as a prior for natural images in future tasks. During fine-tuning on a new downstream task, both the model weights and the policy logits could be updated, allowing the learned prior patch ordering to further adapt to the specific requirements of the new task.\n\n[0] https://arxiv.org/abs/2406.07537v1"}, {"review_id": "3T4RY8E4sH", "reviewer": "Reviewer_C815", "summary": "This manuscript presents an interesting question; whether the ordering of patches affects the performance of variants of ViT.\nIt is well known that the vanilla self-attention is permutation-invariant. However, some variants of ViT do not feed all the low-level patches. This would make a limited window of tokens like limited perceptive field.\n\nThe authors empirically showed that the ordering matters in Longformer, Mamba and Trransformer-XL.\nTo alleviate (ot to utilize) this phenomenon, The authors propose RL-based solution.", "questions": "It is not clear why RL-based method is not effective for Longformer.\nIt would be better to explore nontent-aware dynamic re-ordering method.", "limitations": "This method is effective Mamba models.\nThough, the authors argue that there is a hidden opportunity of improving performance using better reordering, the   RL method did not add up extra gain over fixed ordering in ViT-variant.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "This paper presents an interesting problem and empirically shows the significance of ordering in some models.\nThe RL-based approach shows significant improvement in Mamba model.\nThe evaluation is clean and somewhat through.\n\nHowever, the proposed method basically work only for Mamba.  In case of Mamba, as well discussed in Section 3.3, the architecture is not permutation-invariant from the beginning. It is also well know that Mamba is sequence-dependent.\nIt may not be proper to the ordering of patched in Mamba and ViT-variant together.\n\nBased on the limited benefit/cost of the proposed method in ViT-variants, I don't think this method would be adopted to ViT-based models.", "was_revised": true, "final_justification": "Based on the authors's rebuttal to reviews, I am willing to increase the scores.", "rebuttal": "We thank the reviewer for their positive assessment of our paper’s quality, clarity, and the interesting nature of the problem. We appreciate the opportunity to clarify some key aspects of our work and address the valid questions raised. The central thesis of our paper is that many modern, efficient vision models, regardless of whether they are based on attention approximations, recurrence, or state-space models, sacrifice the permutation equivariance of the original Vision Transformer. Our goal was to investigate this shared sensitivity to patch ordering across different architectural families. We deliberately chose Longformer, Transformer-XL, and Mamba not as “ViT-variants” vs. “Mamba”, but as representative examples of three distinct strategies for achieving efficiency, all of which, as we demonstrate in Section 3.3, become sensitive to input order as a result. We address your questions in depth below:\n\n**A perceived lack of improvement in performance for ViT-variants**: Our results show that REOrder provides significant and consistent performance gains for Transformer-XL as well. Specifically, on ImageNet-1K, REOrder improved Transformer-XL's accuracy by 1.50% over the fixed Hilbert curve ordering and 1.09% over the spiral ordering. On the Functional Map of the World dataset, REOrder improved Transformer-XL's best-performing baseline (column-major) by an additional 1.10%. While the gains in performance for T-XL and Longformer are not as drastic as they are for Mamba, they are statistically significant across the board.\n\n**Cost of REOrder**: REOrder adds as many parameters as there are patches. For a standard 224x224 image with 16x16 patches, this is 196 parameters. This increases parameter count for a ViT-Large-equivalent model by ~$2.0\\times10^{-4}$%. This makes REOrder an extremely efficient method that adds negligible runtime and memory overhead to a standard supervised learning setup.\n\n**Effectiveness for Longformer**: This is an important nuance that speaks to the model's architecture. As we note in our conclusion, Longformer's design, which combines a sliding-window attention with global attention tokens, is a closer approximation of full self-attention compared to Transformer-XL or Mamba. Because it was the least susceptible to patch ordering changes among the three models to begin with (as seen in Figure 2), it is expected (and we observe that) that REOrder has less room for improvement. This finding supports our overall thesis that the degree of ordering sensitivity is tied to the degree to which a model deviates from full, permutation-equivariant self-attention.\n\n**Exploring a content-aware mechanism**: We appreciate this suggestion. REOrder is a content-aware method insofar that the learned patch ordering is specific to a model/dataset pair. A permutation is then sampled based on these logits. This means the final patch order is determined by the learned relevance of different parts of the image content for the specific task, making it inherently content-aware. Interesting future work can include conditioning the RL-policy on __every__ image rather than a dataset at large. We will ensure this aspect of our method is described more clearly in the main text."}, {"review_id": "gDcGNh7sJQ", "reviewer": "Reviewer_L4Dr", "summary": "This paper explores how the order of image patches affects the performance of vision models. They especially focus on processing images as long sequences like Transformer-XL, Mamba, and Longformer. While standard vision transformers such as ViT are not sensitive to patch ordering due to full self-attention, newer efficient models introduce inductive biases that make them more sensitive to the sequence of input patches. They show that simply changing the patch order from the common row-major format to alternatives like column-major, spiral, or Hilbert curves can lead to noticeable differences in accuracy depending on the model and dataset. By this experiment, they figured out that the order of patch is non-trivial. To solve this, they propose REOrder, a method that learns task-specific patch orderings using reinforcement learning. REOrder models the patch order as a distribution over permutations using the Plackett-Luce model, and optimizes it with reinforcement learning and Gumbel-top-k sampling. The learned ordering consistently improves classification performance across models and datasets, showing that rethinking patch order is a promising direction for enhancing long-sequence vision models.", "questions": "1. It would strengthen the paper to include an analysis or ablation of per-image or per-class adaptive ordering strategies. Such results could help validate whether a single global ordering is sufficient or whether dynamic ordering could further improve performance.\n\n2. Beyond the example shown in Figure 4, could you provide a broader analysis of the learned patch orders across classes or datasets? This would help readers understand what structural or semantic properties the ordering policy captures.\n\n3. It would be helpful to include experiments that evaluate REOrder when initialized from random or very weak patch orderings. This would clarify how much the method relies on having a good prior and whether it remains robust across different starting points.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Insightful approach: The paper convincingly identifies and analyzes a practical inductive bias in long-sequence vision models, sensitivity to patch ordering, which has been largely underexplored. This sheds light on a subtle but impactful limitation in common transformer variants and challenges the assumption that input ordering is inconsequential. It's a fresh perspective that could influence how future vision architectures are designed and trained.\n\n2. Generalizable Solution: The proposed method, REOrder, is easy to be plugged into many transformer-based models without architectural changes. The use of a Plackett-Luce distribution with REINFORCE and Gumbel-top-k sampling is well-motivated and makes the optimization over permutations tractable. It’s a rare case where a relatively simple reinforcement learning setup yields consistent and non-trivial gains across diverse architectures and datasets.\n\n3. Clarity of paper and their experiences: The experiments are quite comprehensive covering different patch orderings, multiple models. Furthermore, their supplementary further show their training details which further demonstrates their effectiveness and robustness. \n\nWeakness\n\n1. Global ordering limits flexibility: REOrder learns a single patch permutation shared across all inputs for each model-dataset pair. This approach may not capture per-image structural differences, especially in diverse datasets like ImageNet. The paper does not discuss this limitation or possible dynamic extensions.\n\n2. Lack of interpretability or analysis of learned orderings: Beyond a single illustrative example, the paper does not analyze what kinds of patterns the learned orderings reflect or why they help. There is little insight into how orderings vary across classes, datasets, or models, which limits understanding and generalizability.\n\n3. Limited analysis on the impact of patch ordering priors: While the paper uses six predefined patch orderings as priors, it lacks a deeper analysis of how the choice of initial ordering affects REOrder’s performance. In some cases, REOrder appears to achieve substantial gains even when starting from a weak prior (e.g., Snake for Mamba with 'Functional Map of the world' dataset), but this is not explicitly discussed. Furthermore, there is no comparison against random patch orderings, which would help clarify how much the method relies on having a reasonable starting point. Without this, it’s difficult to assess the robustness and sensitivity of REOrder to the choice of prior.", "was_revised": true, "final_justification": "I believe this work can contribute to further research on the impact of patch ordering, as the results suggest that the order of patches significantly affects performance. In addition, the authors have clearly addressed most of my concerns raised in the earlier review. Therefore, I remain positive about the acceptance of this paper.", "rebuttal": "We thank the reviewer for their detailed and constructive review of our work. We appreciate that you recognize the value in how our RL-based approach can lead to positive outcomes across a diverse set of architectures and datasets. The weaknesses you’ve identified are excellent points that give us a clear pathway to improving our paper. We address these in depth below:\n\n**Global ordering limits flexibility**: We agree with the reviewer that learning a single global ordering for an entire dataset is a limitation and that dynamic, per-image ordering is an exciting direction for future work. Our primary goal in this paper was to first prove conclusively that (1) patch ordering effects are real and significant in modern long-sequence models, and (2) that reinforcement learning is a viable strategy for discovering superior orderings. By learning a single, global permutation, we deliberately isolated the effect of the ordering itself, providing a clean and stable experimental setup without the confounding variance of a more complex, dynamic policy network. One way to break global ordering-associated limitations is to modify REOrder to use a small policy network that takes image patch embeddings as input and generates the ordering logits $z$ dynamically. We will update our Limitations and Future Work section accordingly.\n\n**Lack of interpretability**: We thank the reviewer for this point, which prompted us to conduct a deeper analysis of the patterns learned by REOrder. The “keyboard” example in Figure 4 suggested a link to semantic importance, but we agree a broader analysis is needed. Our new investigation reveals that REOrder learns to align the spatial structure of a dataset with the specific inductive biases of different model architectures.\n\nOur analysis is grounded in two key observations: (1) long-sequence models are sensitive to input order, and (2) ImageNet-1K and Functional Map of the World (FMoW) exhibit a strong center bias, where the most semantically critical content is usually in the middle of the image. To investigate this, we quantified how REOrder repositions patches from the image’s central region relative to their initial ordering. This can reveal whether the learned policy prioritizes central patches by moving them to the beginning (“front-loading”) or the end (“back-loading”) of the sequence. We discovered two distinct, model-dependent strategies:\n\n1. Mamba prefers to front-load central tokens. REOrder systematically moved central patches towards the start of the sequence (on average, a shift of +6.8 positions). This “front-loading” strategy intuitively aligns with Mamba's recurrent state-space mechanism. By processing the most salient patches first, the model establishes a strong initial state ($h_t$​) that informs the processing of the entire sequence. This allows the model to build a robust understanding of the image’s core subject from the outset.\n\n2. Longformer and Transformer-XL prefer to back-load central tokens. Both models learned to shift central patches towards the __end__ of the sequence (average shifts of -20.4 and -2.2 positions, respectively). Transformer-XL’s recurrent memory can summarize information from earlier, less critical patches. By positioning central patches later in the sequence, these tokens can utilize information from the entire image rather than only from half of it. Comparatively, Longformer’s sliding-window attention, which accumulates context over time, would provide greater information for patches near the end. This could maximize the contextual information available for the local and global attention mechanisms when classifying objects.\n\nThis contrast between “front-loading” for Mamba and “back-loading” for Transformer-XL/Longformer on the same ImageNet dataset demonstrates that REOrder is not finding a single, trivial ordering. Instead, it is learning sophisticated, model-specific policies that exploit how each architecture processes information. We will add this detailed analysis and discussion to the final version.\n\n**Limited choice of priors**: This is a great point to highlight. Since the search space of possible permutations is prohibitively large (~10^{365} for 196 patches), we provide an information-theoretic strategy such that we can start with a strong prior for our learning process. To directly test the importance of this initialization and the robustness of our RL algorithm, we have performed the ablation study you suggested. We ran additional experiments on ImageNet-1K with Transformer-XL to compare REOrder's performance when initialized with structured priors versus a completely random permutation. The Top-1 accuracy results are as follows:\n* Baseline (row-major): 60.81\n* REOrder with a row-major prior: 61.40\n* REOrder with a column-major prior: 62.78\n* REOrder with a completely random prior: 53.10\n\nThese results demonstrate that the choice of prior is critical. While our RL algorithm can explore the permutation space, its ability to find a high-performing solution is significantly hampered by a random, unstructured start. This finding validates our core approach: using an information-theoretic strategy to select a sensible prior is crucial for making the learning process tractable and effective."}, {"review_id": "IZAuMv8Cxz", "reviewer": "Reviewer_zkbe", "summary": "Applying a sequence model on image patches is an increasingly common paradigm in modern computer vision. This paper explores the impact of patch ordering on performance when full self-attention is dropped in favor of more efficient (but permutation-sensitive) alternatives like Mamba, Longformer, and Transformer-XL. This paper finds that simple alternatives to the usual row-major patch order (such as column-major and hilbert order) yield significantly different image classification performance on ImageNet-1K and Functional Map of the World. However, the optimal ordering varies per dataset-model pair and is only weakly correlated with compressibility, so the paper proposes a novel RL formulation to learn the best patch ordering by optimizing a Plackett-Luce distribution over permutations with a REINFORCE objective.", "questions": "I’ve embedded most of my questions and suggestions for the authors within the Strengths and Weaknesses section.\n\nOne other miscellaneous suggestion: Consider training the random permutation baselines for each model-dataset pair and including them in Figure 2. The paper slates this for future work, but if done, it’ll better contextualize the performance of the 6 explicitly considered orderings.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. **Novel premise and RL formulation**. To the best of my knowledge, this is the first paper that explores patch ordering for vision models. As vision models are scaled, the proposed ideas may become increasingly relevant. The resulting RL formulation to optimize over a distribution of permutations is also elegant and can serve as a template, even for other use cases.\n2. **Clarity**. The paper is very well-written and does a great job of prefacing its contributions with bits of essential background, such as on Mamba, Longformer, Transformer-XL, and the Pluckett-Luce distribution.\n\n**Weaknesses**\n\n1. **Unclear takeaways**. The paper does a great job of probing the impact of patch ordering and bringing to light that the typical row-major order may not always be optimal. However, it remains unclear what the actual optimal patch ordering may be. Some extra analysis may help pick out the signal from the noise here. Questions I have in this direction:\n   - On lines 205-208, the paper notes that Mamba/ARM doesn’t perform well with many orderings, likely because of its fixed scan directions (forwards, backwards, up, down). Can you visualize these scan orders? I can imagine what the forwards and backwards scan orders may look like, but what about up and down? If those scan orders contain many spatial discontinuities, that may explain the poor results and render many of those results uninterpretable. If so, can you adapt the scan orders or the patch orderings appropriately, to induce better performance?\n   - Compression percent is only weakly correlated with performance, and the sign of the correlation also seems to depend on the model. Can you do a study on the robustness or noisiness of this metric? Why is Hilbert ordering less compressible than column ordering? This is surprising, as the paper points out. Could it be a sign of a noisy measure of compressibility? Are there other metrics that may show stronger correlations, e.g. using JPEG compression?\n   - What do the patch orderings that are learned through RL look like? Do they converge to any patterns, by model or by dataset? Similarly, in Figure 4, why should the patches related to the “keyboard” class move to the end of the patch order? Was that trained on a single image? If not, what’s special about the “keyboard” class such that it dictates the optimal patch order across the entire dataset?\n2. **Missing evaluation in the long sequence regime**. For all experiments in the paper, resolution is set to 224x224 input images, a regime where O(n^2) full self-attention is viable. In this regime, patch ordering is not really a consideration, since full self-attention is permutation invariant. Results would be more persuasive if tested on a truly long sequence regime, such as higher resolution images or videos.\n\nAddressing these weaknesses may improve my rating.", "was_revised": true, "final_justification": "The paper's strengths are its novel premise, RL formulation for learning patch ordering, and clarity in its explanation of the proposed method. Rebuttals have largely clarified some misunderstandings in the narrative of the paper, which were originally leading to unclear takeaways. Nevertheless, the primary weakness of the work remains in that evaluations are done in a regime where full self-attention is quite feasible. For this reason, I'm keeping my original score.", "rebuttal": "We sincerely thank the reviewer for their detailed and insightful review. We are thrilled that you found our paper to have a novel premise, an elegant RL formulation, and to be well-written. The weaknesses you've identified are helpful and highlight areas where we can provide deeper analysis. We agree with your assessments and address each of your points below:\n\n**ARM scan ordering and spatial continuity**: ARM does not use a single scan but instead uses an ensemble of four fixed, competing scan directions and sum their outputs to form the final representation: (1) forward row-major (top-left to bottom-right), (2) backward row-major (bottom-right to top-left), (3) forward column-major (top-left to bottom-right), and (4) backward column-major (bottom-right to top-left). Figure 1 in our paper visualizes row-major and column-major scan orders.\n\nA standard row-major patch ordering is optimal for the row-forward scan, but it is simultaneously suboptimal for the row-backward scan and the two column-based scans. This creates an inherent architectural tension. The final output of the Mamba block depends on the sum of these four scans, so the ideal input sequence is not one that is perfect for a single scan, but one that provides the best compromise for all four simultaneously.\n\nREOrder, meanwhile, does not re-learn a basic row-major or column-major sequence. Instead, it learns a permutation of that base ordering. Therefore, we learn a data- and model-specific patch sequence to maximize the combined effectiveness of the entire multi-scan ensemble. This provides improved performance against even a row-major or column-major patch order, as seen in Figure 5.\n\n**The information-theoretic approach is a weak prior**: Our exploration of compressibility was intended to see if a simple, information-theoretic heuristic could serve as a useful prior. The resulting weak and model-dependent correlation is, in itself, a key finding of our paper: it demonstrates that no simple, universal prior across a search space spanning ~10^{365} options exists, thus motivating our more powerful (but complex) reinforcement learning approach. Your point about Hilbert vs. column ordering is excellent and likely highlights the limitations of applying a 1D compression algorithm (LZMA) to sequences derived from 2D data. While Hilbert curves preserve 2D locality better, this may not translate to higher compressibility for a 1D algorithm. \n\nJPEG compression is a good suggestion for an alternative compression strategy to explore. Unfortunately, JPEG is designed for continuous-tone 2D images. Since the sequence models we test operate on 1D sequences, JPEG is not an applicable compression scheme that we can test. In fact, JPEG on shuffled 1D sequences, such as those following a Hilbert curve, would likely result in sequences that are less compressible than row-major due to sharp patch boundaries.\n\n**Interpretability of learned orderings**: We thank the reviewer for this point, which prompted us to conduct a deeper analysis of the patterns learned by REOrder. The “keyboard” example in Figure 4 suggested a link to semantic importance, but we agree a broader analysis is needed. Our new investigation reveals that REOrder learns to align the spatial structure of a dataset with the specific inductive biases of different model architectures.\n\nOur analysis is grounded in two key observations: (1) long-sequence models are sensitive to input order, and (2) ImageNet-1K and Functional Map of the World (FMoW) exhibit a strong center bias, where the most semantically critical content is usually in the middle of the image. To investigate this, we quantified how REOrder repositions patches from the image’s central region relative to their initial ordering. This can reveal whether the learned policy prioritizes central patches by moving them to the beginning (“front-loading”) or the end (“back-loading”) of the sequence. We discovered two distinct, model-dependent strategies:\n\n1. Mamba prefers to front-load central tokens. REOrder systematically moved central patches towards the start of the sequence (on average, a shift of +6.8 positions). This “front-loading” strategy intuitively aligns with Mamba's recurrent state-space mechanism. By processing the most salient patches first, the model establishes a strong initial state ($h_t$​) that informs the processing of the entire sequence. This allows the model to build a robust understanding of the image’s core subject from the outset.\n\n2. Longformer and Transformer-XL prefer to back-load central tokens. Both models learned to shift central patches towards the __end__ of the sequence (average shifts of -20.4 and -2.2 positions, respectively). Transformer-XL’s recurrent memory can summarize information from earlier, less critical patches. By positioning central patches later in the sequence, these tokens can utilize information from the entire image rather than only from half of it. Comparatively, Longformer’s sliding-window attention, which accumulates context over time, would provide greater information for patches near the end. This could maximize the contextual information available for the local and global attention mechanisms when classifying objects.\n\nThis contrast between “front-loading” for Mamba and “back-loading” for Transformer-XL/Longformer on the same ImageNet dataset demonstrates that REOrder is not finding a single, trivial ordering. Instead, it is learning sophisticated, model-specific policies that exploit how each architecture processes information. We will add this detailed analysis and discussion to the final version."}]

Author rebuttal:

Meta-review: The paper makes an empirical observation that despite transformers being generally permutation-invariant over the input tokens, vision transformers, are sensitive to the image tokenization process (patchification). That is, the advanced vision transformers use techniques (such as for computational efficiency) that renders them dependent on the ordering of the patches. This is due to the 2D nature of images where no flattening into a 1D sequence would be perfect. The paper, then, proposes a process to optimize the order (permutation) of the patches based on the task (loss) at hand using REINFORCE. They demonstrate significant improvement in the classification accuracy of ImageNet and FMoW.

The paper received five expert reviews. The authors provided a thorough rebuttal which was attended and discussed by the reviewers. Eventually, all reviewers leaned towards acceptance, highlighting the originality and importance of the observation, the relevance of the proposed method, and the significance of the achieved results. There remained some concerns on the lack of dynamic per-image ordering or low baseline results on which the reviewers did not agree in the AC-reviewers discussion.

The AC does not see any outstanding major concern with the paper. Vision transformers are becoming increasingly common in computer vision research, particularly those versions with efficiency tricks that make them potentially more sensitive to ordering. The paper makes an important observation and study of on the often-neglected importance of the ordering which reveals significant dependency of the optimal ordering to the task/dataset and architectures. This, by itself, is worth disseminating. It further proposes a method to improve the initial ordering and mitigate the dependence on it which shows the promise in such future direction. Based on these two significant contributions and the unanimous reviewers' recommendation, the AC suggests acceptance.
Decision: Accept (poster)