Research map / Architectures and efficiency / Attention and transformers
REOrdering Patches Improves Vision Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that patch order matters for long-sequence vision models (Transformer-XL, Longformer, Mamba/ARM) and proposes REOrder, which learns a task-specific patch ordering via a Plackett-Luce policy trained with REINFORCE, initialized by a compressibility prior.
Problem
Long-sequence transformers and state-space models use architectural approximations that break permutation equivariance, so the flattening order of image patches affects accuracy, and the best fixed order is not known a priori.
Approach
Treat patch ordering as a stochastic policy over permutations parameterized by per-patch logits (Plackett-Luce, sampled via Gumbel-top-k), initialized from the least-compressible fixed ordering and trained jointly with the classifier using REINFORCE with a running baseline and a three-stage curriculum.
Key results
- REOrder improves Mamba (ARM) Hilbert-order top-1 accuracy on ImageNet-1K by 3.01% (±0.23 pp).
- On Functional Map of the World, REOrder improves Mamba diagonal ordering by 13.35% (±0.21 pp).
- Transformer-XL with REOrder reaches 61.40% vs 60.80% row-major on ImageNet-1K at 100 epochs; Longformer shows no gains.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn a patch ordering with REOrder from Hilbert initialization | Mamba · ImageNet-1K | top-1 accuracy: 3.01% (±0.23 percentage points) | Helped |
| Learn a patch ordering with REOrder from diagonal initialization | Mamba · Functional Map of the World | top-1 accuracy: 13.35% (±0.21 percentage points) | Helped |
| Learn patch ordering with REOrder | Mamba · ImageNet-1K | average top-1 accuracy across patch orderings: 2.20% (±0.22 percentage points) | Helped |
| Learn patch ordering with REOrder | Mamba · Functional Map of the World | average top-1 accuracy across patch orderings: 9.32% (±0.22 percentage points) | Helped |
| Learn patch ordering with REOrder from Hilbert initialization | Transformer-XL · ImageNet-1K | top-1 accuracy: 1.50% (±0.21 percentage points) | Helped |
| Learn patch ordering with REOrder from column-major initialization | Transformer-XL · Functional Map of the World | top-1 accuracy: 1.10% (±0.21 percentage points) | Helped |
| Apply REOrder to Longformer | Longformer · ImageNet-1K and Functional Map of the World | top-1 accuracy | No clear effect |
| Use one random patch permutation for all training epochs instead of REOrder's adaptive exploration (ablation) | Transformer-XL · ImageNet-1K | top-1 accuracy: 61.40 -> 53.10 | Hurt |
| Sample a random patch permutation for every batch instead of REOrder's adaptive exploration (ablation) | Transformer-XL · ImageNet-1K | top-1 accuracy: 61.40 -> 50.23 | Hurt |
| Use the final learned ordering throughout training without reinforcement learning (ablation) | Transformer-XL · ImageNet-1K | top-1 accuracy: 61.40 -> 53.07 | Hurt |
| Train with REOrder from row-major initialization without horizontal flips (ablation) | Transformer-XL · ImageNet-1K | top-1 accuracy: 57.95 -> 59.53; +1.58% | Helped |
| Train with REOrder from Hilbert initialization without horizontal flips (ablation) | Transformer-XL · ImageNet-1K | top-1 accuracy: 50.29 -> 53.22; +2.94% | Helped |
Surprising findings
- Using a learned ordering alone (without the RL exploration process) does not recover the gains; a fixed best learned ordering reached 53.07% vs 61.40% with REOrder.
- Lower LZMA compressibility of a patch sequence does not consistently predict better downstream accuracy.
Limitations
- Learns a single global ordering shared across all images in a dataset rather than per-image ordering.
- Search and curriculum were not extensively tuned due to compute constraints; policy exploration is short (30 epochs).
- Longformer does not benefit from REOrder; experiments limited to 224x224 images with 16x16 patches and base-size models.
Experimental setup
Datasets: ImageNet-1K Functional Map of the World
Benchmarks: ImageNet-1K Functional Map of the World
Metrics: top-1 accuracy standard error of the mean (bootstrap)
Baselines: ViT Transformer-XL row-major Longformer row-major Mamba (ARM) row-major random permutation baselines
Builds on: REINFORCE Plackett-Luce model Gumbel-top-k trick Transformer-XL Longformer ARM
Closest papers by meaning
- Scaling Laws in Patchification: An Image Is Worth 50,176 Tokens And More (ICML 2025 · similarity 0.86)
- Patch Rebirth: Fast and Transferable Model Inversion of Vision Transformers (NeurIPS 2026 · similarity 0.86)
- Near, far: Patch-ordering enhances vision foundation models' scene understanding (ICLR 2025 · similarity 0.86)
- Vision Transformers with Self-Distilled Registers (NeurIPS 2025 · similarity 0.85)
- An Image is Worth More Than 16x16 Patches: Exploring Transformers on Individual Pixels (ICLR 2025 · similarity 0.85)
- Vision Transformers Need Registers (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.